19 #pragma pack(push,_CRT_PACKING)
26 template<
typename _Key_type,
typename _Hasher,
typename _Key_equality>
49 bool operator()(
const _Key_type& _Keyval1,
const _Key_type& _Keyval2)
const
67 return _Byte_reverse_table[_Original_byte];
73 unsigned long _Index = 0;
75 #if (defined (_M_IX86) || defined (_M_ARM))
76 _BitScanReverse(&_Index, _Mask);
78 _BitScanReverse64(&_Index, _Mask);
81 return (
unsigned char) _Index;
85 #pragma warning(disable: 4127) // Warning 4127 -- while (true) has a constant expression in it
87 template <
typename _Traits>
100 typedef typename allocator_type::pointer
pointer;
177 for (size_type _Index2 = 0; _Index2 < _Seg_size; _Index2++)
305 const_iterator
end()
const
381 while (_First != _Last)
407 std::pair<iterator, iterator> _Where =
equal_range(_Keyval);
451 for (size_type _Index2 = 0; _Index2 < _Seg_size; _Index2++)
474 iterator
find(
const key_type& _Keyval)
476 return _Find(_Keyval);
490 const_iterator
find(
const key_type& _Keyval)
const
492 return _Find(_Keyval);
505 size_type
count(
const key_type& _Keyval)
const
508 const_iterator _It =
_Find(_Keyval);
509 for (;_It !=
end() && !this->_M_comparator(this->_Key_function(*_It), _Keyval); _It++)
531 std::pair<iterator, iterator>
equal_range(
const key_type& _Keyval)
551 std::pair<const_iterator, const_iterator>
equal_range(
const key_type& _Keyval)
const
667 _Full_const_iterator _Iterator =
_Get_bucket(_Bucket);
732 _Full_const_iterator _Iterator =
_Get_bucket(_Bucket);
757 return ((
const _Mytype *)
this)->begin();
772 return ((
const _Mytype *)
this)->end();
816 if (_Newmax != _Newmax || _Newmax < 0)
818 throw std::out_of_range(
"invalid hash load factor");
846 if (_Current_buckets > _Buckets)
852 throw std::out_of_range(
"invalid number of buckets");
860 template<
typename _ValTy>
876 _Full_iterator _Where = _Iterator;
879 _ASSERT_EXPR(_Where != _Last, L
"Invalid head node");
909 else if (!this->_M_allow_multimapping &&
_Mylist::_Get_key(_Where) == _Order_key &&
910 this->_M_comparator(this->_Key_function(*_Where), this->_Key_function(_New_node->_M_element)) == 0)
925 template<
class _Iterator>
928 for (_Iterator _I = _First; _I !=
_Last; _I++)
940 memset(
_M_buckets, 0, _Pointers_per_table *
sizeof(
void *));
973 _Full_iterator * _Iterator_pointer =
_M_buckets[_Index];
975 _Right.
_M_buckets[_Index] = _Iterator_pointer;
980 throw std::invalid_argument(
"swap is invalid on non-equal allocators");
989 for (const_iterator _Iterator = _First; _Iterator !=
_Last; _Iterator++)
998 iterator
_Find(
const key_type& _Keyval)
1012 for (_Full_iterator _Iterator =
_Get_bucket(_Bucket); _Iterator !=
_Last; _Iterator++)
1025 if (!this->_M_comparator(this->_Key_function(*_Iterator), _Keyval))
1036 const_iterator
_Find(
const key_type& _Keyval)
const
1051 for (_Full_const_iterator _Iterator =
_Get_bucket(_Bucket); _Iterator !=
_Last; _Iterator++)
1064 if (!this->_M_comparator(this->_Key_function(*_Iterator), _Keyval))
1090 _Full_iterator _Where = _Previous;
1092 _ASSERT_EXPR(_Where != _Last, L
"Invalid head node");
1099 if (_Where == _Last)
1130 for (_Full_iterator _Iterator =
_Get_bucket(_Bucket); _Iterator !=
_Last; _Iterator++)
1135 return std::pair<iterator, iterator>(
end(),
end());
1137 else if (
_Mylist::_Get_key(_Iterator) == _Order_key && !this->_M_comparator(this->_Key_function(*_Iterator), _Keyval))
1140 iterator _End= _Begin;
1142 for (;_End !=
end() && !this->_M_comparator(this->_Key_function(*_End), _Keyval); _End++)
1146 return std::pair<iterator, iterator>(_Begin, _End);
1150 return std::pair<iterator, iterator>(
end(),
end());
1155 std::pair<const_iterator, const_iterator>
_Equal_range(
const key_type& _Keyval)
const
1170 for (_Full_const_iterator _Iterator =
_Get_bucket(_Bucket); _Iterator !=
_Last; _Iterator++)
1175 return std::pair<const_iterator, const_iterator>(
end(),
end());
1177 else if (
_Mylist::_Get_key(_Iterator) == _Order_key && !this->_M_comparator(this->_Key_function(*_Iterator), _Keyval))
1180 const_iterator _End = _Begin;
1182 for (; _End !=
end() && !this->_M_comparator(this->_Key_function(*_End), _Keyval); _End++)
1186 return std::pair<const_iterator, const_iterator>(_Begin, _End);
1190 return std::pair<const_iterator, const_iterator>(
end(),
end());
1211 _Full_iterator _Parent =
_Get_bucket(_Parent_bucket);
1231 unsigned char _Msb =
_Get_msb(_Bucket);
1232 return _Bucket & ~(1 << _Msb);
1251 _Full_iterator * _New_segment =
_M_allocator.allocate(_Seg_size);
1252 std::_Wrap_alloc<decltype(_M_allocator)> _Wrapped_allocator(
_M_allocator);
1272 _Full_iterator _Iterator =
_M_buckets[_Segment][_Bucket];
1273 return (_Iterator._Mynode() !=
NULL);
1281 unsigned char * _Original = (
unsigned char *) &_Order_key;
1282 unsigned char * _Reversed = (
unsigned char *) &_Reversed_order_key;
1285 for (
int _Index = 0; _Index <
_Size; _Index++)
1287 _Reversed[_Size - _Index - 1] =
_Reverse_byte(_Original[_Index]);
1290 return _Reversed_order_key;
1302 return _Reverse(_Order_key) & ~(0x1);
1308 typename allocator_type::template rebind<_Full_iterator>::other
_M_allocator;
1313 #pragma warning(pop) // Warning 4127 -- while (true) has a constant expression in it
_Concurrent_hash< _Traits > _Mytype
Definition: internal_concurrent_hash.h:92
_Split_order_key _Split_order_regular_key(_Map_key _Order_key) const
Definition: internal_concurrent_hash.h:1294
static const size_type _Initial_bucket_number
Definition: internal_concurrent_hash.h:119
allocator_type::template rebind< _Full_iterator >::other _M_allocator
Definition: internal_concurrent_hash.h:1308
_Mylist _M_split_ordered_list
Definition: internal_concurrent_hash.h:1307
_Full_iterator _Begin()
Definition: internal_split_ordered_list.h:515
static const size_type _Initial_bucket_load
Definition: internal_concurrent_hash.h:120
float max_load_factor() const
Gets or sets the maximum load factor of the container. The maximum load factor is the largest number ...
Definition: internal_concurrent_hash.h:798
iterator unsafe_erase(const_iterator _First, const_iterator _Last)
Removes elements from the container at specified positions. This method is not concurrency-safe.
Definition: internal_concurrent_hash.h:379
_Mylist::_Full_const_iterator _Full_const_iterator
Definition: internal_concurrent_hash.h:117
#define NULL
Definition: vcruntime.h:236
static _Split_order_key _Get_key(const _Full_const_iterator &_Iterator)
Definition: internal_split_ordered_list.h:536
const_iterator cend() const
Definition: internal_split_ordered_list.h:465
bool _Key_compare(_Key_t _Left, _Key_t _Right)
Definition: xtree:163
~_Concurrent_hash()
Definition: internal_concurrent_hash.h:169
const_local_iterator unsafe_cbegin(size_type) const
Returns an iterator to the first element in this container for a specific bucket. ...
Definition: internal_concurrent_hash.h:755
iterator local_iterator
Definition: internal_concurrent_hash.h:110
size_t _Map_key
Definition: internal_split_ordered_list.h:194
void rehash(size_type _Buckets)
Rebuilds the hash table.
Definition: internal_concurrent_hash.h:842
_Full_iterator _Insert_dummy(_Full_iterator _Iterator, _Split_order_key _Order_key)
Definition: internal_split_ordered_list.h:633
const_iterator end() const
Returns a const_iterator pointing to the location succeeding the last element in the concurrent conta...
Definition: internal_concurrent_hash.h:305
void _Copy(const _Mytype &_Right)
Definition: internal_concurrent_hash.h:947
unsigned int _Count
Definition: xcomplex:668
Definition: internal_split_ordered_list.h:112
iterator _Erase(const_iterator _Iterator)
Definition: internal_concurrent_hash.h:1075
_Mylist::const_iterator const_iterator
Definition: internal_concurrent_hash.h:109
allocator_type get_allocator() const
Definition: internal_split_ordered_list.h:407
void max_load_factor(float _Newmax)
Gets or sets the maximum load factor of the container. The maximum load factor is the largest number ...
Definition: internal_concurrent_hash.h:813
bool _Is_initialized(size_type _Bucket) const
Definition: internal_concurrent_hash.h:1262
const_iterator find(const key_type &_Keyval) const
Finds an element that matches a specified key. This function is concurrency safe. ...
Definition: internal_concurrent_hash.h:490
_Key_equality _M_key_compare_object
Definition: internal_concurrent_hash.h:55
Definition: internal_concurrent_hash.h:27
static size_type const _Pointers_per_table
Definition: internal_concurrent_hash.h:121
size_type max_size() const
Returns the maximum size of the concurrent container, determined by the allocator. This method is concurrency safe.
Definition: internal_concurrent_hash.h:255
size_type unsafe_bucket_count() const
Returns the current number of buckets in this container.
Definition: internal_concurrent_hash.h:563
void swap(_Concurrent_hash &_Right)
Swaps the contents of two concurrent containers. This function is not concurrency safe...
Definition: internal_concurrent_hash.h:424
void _Init()
Definition: internal_concurrent_hash.h:937
Concurrency::details::_Split_ordered_list< typename details::_Concurrent_unordered_map_traits< _Key_type, _Element_type, details::_Hash_compare< _Key_type, _Hasher, _Key_equality >, _Allocator_type, false >::value_type, typename details::_Concurrent_unordered_map_traits< _Key_type, _Element_type, details::_Hash_compare< _Key_type, _Hasher, _Key_equality >, _Allocator_type, false >::allocator_type >::_Full_iterator std::_Flist_iterator< _Mybase > _Full_iterator
Definition: internal_split_ordered_list.h:384
size_type count(const key_type &_Keyval) const
Counts the number of elements matching a specified key. This function is concurrency safe...
Definition: internal_concurrent_hash.h:505
size_type size() const
Returns the number of elements in this concurrent container. This method is concurrency safe...
Definition: internal_concurrent_hash.h:240
void _Insert(_Iterator _First, _Iterator _Last)
Definition: internal_concurrent_hash.h:926
float _M_maximum_bucket_size
Definition: internal_concurrent_hash.h:1310
hasher _M_hash_object
Definition: internal_concurrent_hash.h:54
iterator begin()
Returns an iterator pointing to the first element in the concurrent container. This method is concurr...
Definition: internal_concurrent_hash.h:267
bool operator()(const _Key_type &_Keyval1, const _Key_type &_Keyval2) const
Definition: internal_concurrent_hash.h:49
_Concurrent_hash(size_type _Number_of_buckets=_Initial_bucket_number, const _Key_compare &_Parg=_Key_compare(), const allocator_type &_Allocator=allocator_type())
Definition: internal_concurrent_hash.h:124
The Concurrency namespace provides classes and functions that provide access to the Concurrency Runti...
Definition: agents.h:43
_Full_iterator _End()
Definition: internal_split_ordered_list.h:526
static size_type _Segment_size(size_type _K)
Definition: internal_concurrent_hash.h:196
_Hash_compare()
Definition: internal_concurrent_hash.h:32
allocator_type::const_pointer const_pointer
Definition: internal_concurrent_hash.h:101
_Split_order_key _Split_order_dummy_key(_Map_key _Order_key) const
Definition: internal_concurrent_hash.h:1300
Definition: internal_concurrent_hash.h:88
unsigned char _Reverse_byte(unsigned char _Original_byte)
Definition: internal_concurrent_hash.h:64
std::conditional< std::is_same< key_type, value_type >::value, typename _Mylist::const_iterator, typename _Mylist::iterator >::type iterator
Definition: internal_concurrent_hash.h:108
_Full_iterator _Get_bucket(size_type _Bucket) const
Definition: internal_concurrent_hash.h:1236
iterator end()
Returns an iterator pointing to the location succeeding the last element in the concurrent container...
Definition: internal_concurrent_hash.h:292
void _Set_bucket(size_type _Bucket, _Full_iterator _Dummy_head)
Definition: internal_concurrent_hash.h:1243
std::pair< const_iterator, const_iterator > _Equal_range(const key_type &_Keyval) const
Definition: internal_concurrent_hash.h:1155
bool empty() const
Definition: internal_split_ordered_list.h:471
void _Erase(_Nodeptr _Delete_node)
Definition: internal_split_ordered_list.h:596
void clear()
Erases all the elements in the concurrent container. This function is not concurrency safe...
Definition: internal_concurrent_hash.h:440
_Concurrent_hash & operator=(_Concurrent_hash &&_Right)
Definition: internal_concurrent_hash.h:158
iterator end()
Definition: internal_split_ordered_list.h:450
void _Swap_buckets(_Concurrent_hash &_Right)
Definition: internal_concurrent_hash.h:966
_Concurrent_hash(const _Concurrent_hash &_Right, const allocator_type &_Allocator)
Definition: internal_concurrent_hash.h:130
const_iterator cend() const
Returns a const iterator pointing to the location succeeding the last element in the concurrent conta...
Definition: internal_concurrent_hash.h:329
iterator unsafe_erase(const_iterator _Where)
Removes elements from the container at specified positions. This method is not concurrency-safe.
Definition: internal_concurrent_hash.h:350
const_iterator begin() const
Returns an iterator pointing to the first element in the concurrent container. This method is concurr...
Definition: internal_concurrent_hash.h:279
_Nodeptr _Insert(_Nodeptr _Previous, _Nodeptr _New_node, _Nodeptr _Current_node)
Definition: internal_split_ordered_list.h:608
const_local_iterator unsafe_cend(size_type) const
Returns an iterator to the first element in this container for a specific bucket. ...
Definition: internal_concurrent_hash.h:770
size_type size() const
Definition: internal_split_ordered_list.h:477
size_t operator()(const _Key_type &_Keyval) const
Definition: internal_concurrent_hash.h:44
local_iterator unsafe_end(size_type _Bucket)
Returns an iterator to the last element in this container for a specific bucket.
Definition: internal_concurrent_hash.h:681
const_local_iterator unsafe_begin(size_type _Bucket) const
Returns an iterator to the first element in this container for a specific bucket. ...
Definition: internal_concurrent_hash.h:659
_Traits::value_type value_type
Definition: internal_concurrent_hash.h:97
size_type unsafe_max_bucket_count() const
Returns the maximum number of buckets in this container.
Definition: internal_concurrent_hash.h:575
void swap(array< _Ty, _Size > &_Left, array< _Ty, _Size > &_Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right)))
Definition: array:433
std::pair< iterator, bool > _Insert(_ValTy &&_Value)
Definition: internal_concurrent_hash.h:861
std::pair< iterator, iterator > equal_range(const key_type &_Keyval)
Finds a range that matches a specified key. This function is concurrency safe.
Definition: internal_concurrent_hash.h:531
allocator_type::reference reference
Definition: internal_concurrent_hash.h:102
static size_type _Segment_base(size_type _K)
Definition: internal_concurrent_hash.h:191
iterator _Get_first_real_iterator(_Full_iterator _Iterator)
Definition: internal_split_ordered_list.h:571
size_type max_size() const
Definition: internal_split_ordered_list.h:483
static size_type __cdecl _Segment_index_of(size_type _Index)
Definition: internal_concurrent_hash.h:186
void * _InterlockedCompareExchangePointer(void *volatile *, void *, void *)
_Concurrent_hash(const _Concurrent_hash &_Right)
Definition: internal_concurrent_hash.h:135
_Mylist::_Full_iterator _Full_iterator
Definition: internal_concurrent_hash.h:116
iterator find(const key_type &_Keyval)
Finds an element that matches a specified key. This function is concurrency safe. ...
Definition: internal_concurrent_hash.h:474
_Nodeptr _Buynode(_Split_order_key _Order_key, _ValTy &&_Value)
Definition: internal_split_ordered_list.h:322
size_type _M_number_of_buckets
Definition: internal_concurrent_hash.h:1309
const_local_iterator unsafe_end(size_type _Bucket) const
Returns an iterator to the last element in this container for a specific bucket.
Definition: internal_concurrent_hash.h:718
size_type unsafe_bucket_size(size_type _Bucket)
Returns the number of items in a specific bucket of this container.
Definition: internal_concurrent_hash.h:590
allocator_type::pointer pointer
Definition: internal_concurrent_hash.h:100
void swap(_Mytype &_Right)
Definition: internal_split_ordered_list.h:489
allocator_type get_allocator() const
Returns the stored allocator object for this concurrent container. This method is concurrency safe...
Definition: internal_concurrent_hash.h:208
void _Uninitialized_default_fill_n(_FwdIt _First, _Diff _Count, _Wrap_alloc< _Alloc > &_Al)
Definition: xmemory:477
size_type _Distance(const_iterator _First, const_iterator _Last) const
Definition: internal_concurrent_hash.h:985
#define _InterlockedCompareExchangeSizeT(_Target, _Exchange, _Comparand)
Definition: concrt.h:98
_Split_order_key _Reverse(_Map_key _Order_key) const
Definition: internal_concurrent_hash.h:1277
_Map_key _Split_order_key
Definition: internal_split_ordered_list.h:195
std::pair< iterator, iterator > _Equal_range(const key_type &_Keyval)
Definition: internal_concurrent_hash.h:1116
void _Swap_adl(_Ty &_Left, _Ty &_Right) _NOEXCEPT_OP(_Is_nothrow_swappable< _Ty >
Definition: utility:56
bool empty() const
Tests whether no elements are present. This method is concurrency safe.
Definition: internal_concurrent_hash.h:224
_Traits::_Key_compare _Key_compare
Definition: internal_concurrent_hash.h:94
size_type _Get_parent(size_type _Bucket) const
Definition: internal_concurrent_hash.h:1228
unsigned char _Get_msb(size_t _Mask)
Definition: internal_concurrent_hash.h:71
_Traits::_Value_compare _Value_compare
Definition: internal_concurrent_hash.h:95
allocator_type::difference_type difference_type
Definition: internal_concurrent_hash.h:106
iterator begin()
Definition: internal_split_ordered_list.h:437
allocator_type::const_reference const_reference
Definition: internal_concurrent_hash.h:103
#define _CONCRTIMP
Definition: crtdefs.h:48
_Hash_compare(hasher _Hasharg)
Definition: internal_concurrent_hash.h:36
size_type unsafe_bucket(const key_type &_Keyval) const
Returns the bucket index that a specific key maps to in this container.
Definition: internal_concurrent_hash.h:620
void _Adjust_table_size(size_type _Total_elements, size_type _Current_size)
Definition: internal_concurrent_hash.h:1218
allocator_type::size_type size_type
Definition: internal_concurrent_hash.h:105
_Concurrent_hash(_Concurrent_hash &&_Right)
Definition: internal_concurrent_hash.h:141
std::pair< const_iterator, const_iterator > equal_range(const key_type &_Keyval) const
Finds a range that matches a specified key. This function is concurrency safe.
Definition: internal_concurrent_hash.h:551
_CONCRTIMP const unsigned char _Byte_reverse_table[]
_Hash_compare(hasher _Hasharg, _Key_equality _Keyeqarg)
Definition: internal_concurrent_hash.h:40
Concurrency::details::_Split_ordered_list< typename details::_Concurrent_unordered_map_traits< _Key_type, _Element_type, details::_Hash_compare< _Key_type, _Hasher, _Key_equality >, _Allocator_type, false >::value_type, typename details::_Concurrent_unordered_map_traits< _Key_type, _Element_type, details::_Hash_compare< _Key_type, _Hasher, _Key_equality >, _Allocator_type, false >::allocator_type >::_Nodeptr _Mybase::_Nodeptr _Nodeptr
Definition: internal_split_ordered_list.h:370
iterator _Get_iterator(_Full_iterator _Iterator)
Definition: internal_split_ordered_list.h:543
float load_factor() const
Computes and returns the current load factor of the container. The load factor is the number of eleme...
Definition: internal_concurrent_hash.h:783
Concurrency::details::_Split_ordered_list< typename details::_Concurrent_unordered_map_traits< _Key_type, _Element_type, details::_Hash_compare< _Key_type, _Hasher, _Key_equality >, _Allocator_type, false >::value_type, typename details::_Concurrent_unordered_map_traits< _Key_type, _Element_type, details::_Hash_compare< _Key_type, _Hasher, _Key_equality >, _Allocator_type, false >::allocator_type >::_Full_const_iterator std::_Flist_const_iterator< _Mybase > _Full_const_iterator
Definition: internal_split_ordered_list.h:383
_Key_compare _M_comparator
Definition: concurrent_unordered_map.h:83
_Solist_const_iterator< _Mybase > const_iterator
Definition: internal_split_ordered_list.h:381
const_iterator cbegin() const
Definition: internal_split_ordered_list.h:460
const_iterator const_local_iterator
Definition: internal_concurrent_hash.h:111
local_iterator unsafe_begin(size_type _Bucket)
Returns an iterator to the first element in this container for a specific bucket. ...
Definition: internal_concurrent_hash.h:637
_Split_ordered_list< typename _Traits::value_type, typename _Traits::allocator_type > _Mylist
Definition: internal_concurrent_hash.h:93
_Full_iterator * _M_buckets[_Pointers_per_table]
Definition: internal_concurrent_hash.h:1306
_Hasher hasher
Definition: internal_concurrent_hash.h:30
_Mylist::_Nodeptr _Nodeptr
Definition: internal_concurrent_hash.h:113
_Concurrent_hash & operator=(const _Concurrent_hash &_Right)
Definition: internal_concurrent_hash.h:148
_In_ int _Value
Definition: setjmp.h:173
iterator _Find(const key_type &_Keyval)
Definition: internal_concurrent_hash.h:998
void clear()
Definition: internal_split_ordered_list.h:412
_Traits::allocator_type allocator_type
Definition: internal_concurrent_hash.h:99
_FwdIt _Last
Definition: algorithm:1936
const_iterator cbegin() const
Returns a const iterator pointing to the first element in the concurrent container. This method is concurrency safe.
Definition: internal_concurrent_hash.h:317
_Size
Definition: vcruntime_string.h:36
constexpr const _Ty &() _Right
Definition: algorithm:3591
size_type unsafe_erase(const key_type &_Keyval)
Removes elements from the container at specified positions. This method is not concurrency-safe.
Definition: internal_concurrent_hash.h:405
void _Initialize_bucket(size_type _Bucket)
Definition: internal_concurrent_hash.h:1194
_Traits::key_type key_type
Definition: internal_concurrent_hash.h:98
const_iterator _Find(const key_type &_Keyval) const
Definition: internal_concurrent_hash.h:1036