git.sesse.net Git - casparcg/blob - concrt_extras/internal_concurrent_hash.h

   1 /***\r
   2 * ==++==\r
   3 *\r
   4 * Copyright (c) Microsoft Corporation.  All rights reserved.\r
   5 * \r
   6 * ==--==\r
   7 * =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\r
   8 *\r
   9 * internal_concurrent_hash.h\r
  10 *\r
  11 * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\r
  12 ****/\r
  13 #pragma once\r
  14 \r
  15 #include <utility>\r
  16 #include "internal_split_ordered_list.h"\r
  17 #include <concrt.h>\r
  18 \r
  19 namespace Concurrency\r
  20 {\r
  21 namespace details\r
  22 {\r
  23 // Template class for hash compare\r
  24 template<typename _Key_type, typename _Hasher, typename _Key_equality>\r
  25 class _Hash_compare\r
  26 {\r
  27 public:\r
  28     typedef _Hasher hasher;\r
  29 \r
  30     _Hash_compare()\r
  31     {\r
  32     }\r
  33 \r
  34     _Hash_compare(hasher _Hasharg) : _M_hash_object(_Hasharg)\r
  35     {\r
  36     }\r
  37 \r
  38     _Hash_compare(hasher _Hasharg, _Key_equality _Keyeqarg) : _M_hash_object(_Hasharg), _M_key_compare_object(_Keyeqarg)\r
  39     {\r
  40     }\r
  41 \r
  42     size_t operator()(const _Key_type& _Keyval) const\r
  43     {\r
  44         return ((size_t)_M_hash_object(_Keyval));\r
  45     }\r
  46 \r
  47     bool operator()(const _Key_type& _Keyval1, const _Key_type& _Keyval2) const\r
  48     {\r
  49         return (!_M_key_compare_object(_Keyval1, _Keyval2));\r
  50     }\r
  51 \r
  52     hasher        _M_hash_object;        // The hash object\r
  53     _Key_equality _M_key_compare_object; // The equality comparator object\r
  54 };\r
  55 \r
  56 // An efficient implementation of the _Reverse function utilizes a 2^8 or 2^16 lookup table holding the\r
  57 // bit-reversed values of [0..2^8 - 1] or [0..2^16 - 1] respectively. Those values can also be computed\r
  58 // on the fly at a slightly higher cost.\r
  59 const unsigned char _Byte_reverse_table[] =\r
  60 {\r
  61     0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,\r
  62     0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,\r
  63     0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,\r
  64     0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,\r
  65     0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,\r
  66     0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,\r
  67     0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,\r
  68     0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,\r
  69     0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,\r
  70     0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,\r
  71     0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,\r
  72     0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,\r
  73     0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,\r
  74     0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,\r
  75     0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,\r
  76     0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF\r
  77 };\r
  78 \r
  79 // Given a byte, reverses it\r
  80 inline unsigned char _Reverse_byte(unsigned char _Original_byte)\r
  81 {\r
  82     // return ((_Original_byte * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;\r
  83     return _Byte_reverse_table[_Original_byte];\r
  84 }\r
  85 \r
  86 // Finds the most significant bit in a size_t\r
  87 inline unsigned char _Get_msb(size_t _Mask)\r
  88 {\r
  89     unsigned long _Index = 0;\r
  90 \r
  91 #if defined(_M_IX86)\r
  92     _BitScanReverse(&_Index, _Mask);\r
  93 #else\r
  94     _BitScanReverse64(&_Index, _Mask);\r
  95 #endif\r
  96 \r
  97     return (unsigned char) _Index;\r
  98 }\r
  99 \r
 100 #pragma warning(push)\r
 101 #pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it\r
 102 \r
 103 template <typename _Traits>\r
 104 class _Concurrent_hash : public _Traits\r
 105 {\r
 106 public:\r
 107     // Type definitions\r
 108     typedef _Concurrent_hash<_Traits> _Mytype;\r
 109     typedef typename _Traits::_Value_type _Value_type;\r
 110     typedef typename _Traits::value_type value_type;\r
 111     typedef typename _Traits::key_type key_type;\r
 112     typedef typename _Traits::key_compare key_compare;\r
 113     typedef typename _Traits::value_compare value_compare;\r
 114 \r
 115     typedef typename _Traits::allocator_type allocator_type;\r
 116     typedef typename allocator_type::pointer pointer;\r
 117     typedef typename allocator_type::const_pointer const_pointer;\r
 118     typedef typename allocator_type::reference reference;\r
 119     typedef typename allocator_type::const_reference const_reference;\r
 120 \r
 121     typedef typename allocator_type::size_type size_type;\r
 122     typedef typename allocator_type::difference_type difference_type;\r
 123 \r
 124     typedef typename _Split_ordered_list<typename _Traits::value_type, typename _Traits::allocator_type> _Mylist;\r
 125     typedef typename _Mylist::_Nodeptr _Nodeptr;\r
 126 \r
 127     typedef typename std::tr1::conditional<std::tr1::is_same<key_type, value_type>::value, typename _Mylist::const_iterator, typename _Mylist::iterator>::type iterator;\r
 128     typedef typename _Mylist::const_iterator const_iterator;\r
 129     typedef iterator local_iterator;\r
 130     typedef const_iterator const_local_iterator;\r
 131     typedef std::pair<iterator, bool> _Pairib;\r
 132     typedef std::pair<iterator, iterator> _Pairii;\r
 133     typedef std::pair<const_iterator, const_iterator> _Paircc;\r
 134 \r
 135     // Iterators that walk the entire split-order list, including dummy nodes\r
 136     typedef typename _Mylist::_Full_iterator _Full_iterator;\r
 137     typedef typename _Mylist::_Full_const_iterator _Full_const_iterator;\r
 138 \r
 139     static const size_type _Initial_bucket_number = 8;                               // Initial number of buckets\r
 140     static const size_type _Initial_bucket_load = 4;                                 // Initial maximum number of elements per bucket\r
 141     static size_type const _Pointers_per_table = sizeof(size_type) * 8;              // One bucket segment per bit\r
 142 \r
 143     // Constructors/Destructors\r
 144     _Concurrent_hash(size_type _Number_of_buckets = _Initial_bucket_number, const key_compare& _Parg = key_compare(), const allocator_type& _Allocator = allocator_type())\r
 145         : _Traits(_Parg), _M_number_of_buckets(_Number_of_buckets), _M_split_ordered_list(_Allocator), _M_allocator(_Allocator), _M_maximum_bucket_size((float) _Initial_bucket_load)\r
 146     {\r
 147         _Init();\r
 148     }\r
 149 \r
 150     _Concurrent_hash(const _Concurrent_hash& _Right, const allocator_type& _Allocator) : _Traits(_Right._M_comparator), _M_split_ordered_list(_Allocator), _M_allocator(_Allocator)\r
 151     {\r
 152         _Copy(_Right);\r
 153     }\r
 154 \r
 155     _Concurrent_hash(const _Concurrent_hash& _Right) : _Traits(_Right._M_comparator), _M_split_ordered_list(_Right.get_allocator()), _M_allocator(_Right.get_allocator())\r
 156     {\r
 157         _Init();\r
 158         _Copy(_Right);\r
 159     }\r
 160 \r
 161     _Concurrent_hash(_Concurrent_hash&& _Right) : _Traits(_Right._M_comparator), _M_split_ordered_list(_Right.get_allocator()), _M_allocator(_Right.get_allocator()),\r
 162         _M_number_of_buckets(_Initial_bucket_number), _M_maximum_bucket_size((float) _Initial_bucket_load)\r
 163     {\r
 164         _Init();\r
 165         swap(_Right);\r
 166     }\r
 167 \r
 168     _Concurrent_hash& operator=(const _Concurrent_hash& _Right)\r
 169     {\r
 170         if (this != &_Right)\r
 171         {\r
 172             _Copy(_Right);\r
 173         }\r
 174 \r
 175         return (*this);\r
 176     }\r
 177 \r
 178     _Concurrent_hash& operator=(_Concurrent_hash&& _Right)\r
 179     {\r
 180         if (this != &_Right)\r
 181         {\r
 182             clear();\r
 183             swap(_Right);\r
 184         }\r
 185 \r
 186         return (*this);\r
 187     }\r
 188 \r
 189     ~_Concurrent_hash()\r
 190     {\r
 191         // Delete all node segments\r
 192         for (size_type _Index = 0; _Index < _Pointers_per_table; _Index++)\r
 193         {\r
 194             if (_M_buckets[_Index] != NULL)\r
 195             {\r
 196                 size_type _Seg_size = _Segment_size(_Index);\r
 197                 for (size_type _Index2 = 0; _Index2 < _Seg_size; _Index2++)\r
 198                 {\r
 199                     _M_allocator.destroy(&_M_buckets[_Index][_Index2]);\r
 200                 }\r
 201                 _M_allocator.deallocate(_M_buckets[_Index], _Seg_size);\r
 202             }\r
 203         }\r
 204     }\r
 205 \r
 206     static size_type __cdecl _Segment_index_of( size_type _Index )\r
 207     {\r
 208         return size_type( _Get_msb( _Index|1 ) );\r
 209     }\r
 210 \r
 211     static size_type _Segment_base( size_type _K )\r
 212     {\r
 213         return (size_type(1)<<_K & ~size_type(1));\r
 214     }\r
 215 \r
 216     static size_type _Segment_size( size_type _K )\r
 217     {\r
 218         return _K ? size_type(1)<<_K : 2;\r
 219     }\r
 220 \r
 221     /// <summary>\r
 222     ///     Returns the allocator used for this concurrent container. \r
 223     /// </summary>\r
 224     /// <remarks>\r
 225     ///     This function is concurrency safe.\r
 226     /// </remarks>\r
 227     /// <returns>\r
 228     ///     The allocator used for this concurrent container.\r
 229     /// </returns>\r
 230     /**/\r
 231     allocator_type get_allocator() const\r
 232     {\r
 233         return _M_split_ordered_list.get_allocator();\r
 234     }\r
 235 \r
 236     // Size and capacity function\r
 237     /// <summary>\r
 238     ///     Checks whether the number of elements in this concurrent container is non-zero. \r
 239     /// </summary>\r
 240     /// <remarks>\r
 241     ///     This function is concurrency safe.\r
 242     ///     <para>With concurrent inserts, whether or not the concurrent container is empty may change \r
 243     ///     immediately after calling this function, before the return value is even read.</para>\r
 244     /// </remarks>\r
 245     /// <returns>\r
 246     ///     True, if this concurrent container object is empty, false, otherwise.\r
 247     /// </returns>\r
 248     /**/\r
 249     bool empty() const\r
 250     {\r
 251         return _M_split_ordered_list.empty();\r
 252     }\r
 253 \r
 254     /// <summary>\r
 255     ///     Returns the number of elements in this concurrent container. \r
 256     /// </summary>\r
 257     /// <remarks>\r
 258     ///     This function is concurrency safe.\r
 259     ///     <para>With concurrent inserts, the number of elements in the concurrent container may change \r
 260     ///     immediately after calling this function, before the return value is even read.</para>\r
 261     /// </remarks>\r
 262     /// <returns>\r
 263     ///     The number of items in the container.\r
 264     /// </returns>\r
 265     /**/\r
 266     size_type size() const\r
 267     {\r
 268         return _M_split_ordered_list.size();\r
 269     }\r
 270 \r
 271     /// <summary>\r
 272     ///     Returns the maximum size of the concurrent container, determined by the allocator.\r
 273     /// </summary>\r
 274     /// <remarks>\r
 275     ///     This function is concurrency safe.\r
 276     ///     <para>This upper bound value may actually be higher than what the container can actually hold.</para>\r
 277     /// </remarks>\r
 278     /// <returns>\r
 279     ///     The maximum number of elements that can be put into this concurrent container.\r
 280     /// </returns>\r
 281     /**/\r
 282     size_type max_size() const\r
 283     {\r
 284         return _M_split_ordered_list.max_size();\r
 285     }\r
 286 \r
 287     // Iterators \r
 288     /// <summary>\r
 289     ///     Returns an iterator pointing to the first element in the concurrent container.\r
 290     /// </summary>\r
 291     /// <remarks>\r
 292     ///     This function is concurrency safe.\r
 293     /// </remarks>\r
 294     /// <returns>\r
 295     ///     An iterator to the first element in the concurrent container.\r
 296     /// </returns>\r
 297     /**/\r
 298     iterator begin()\r
 299     {\r
 300         return _M_split_ordered_list.begin();\r
 301     }\r
 302 \r
 303     /// <summary>\r
 304     ///     Returns a const_iterator pointing to the first element in the concurrent container.\r
 305     /// </summary>\r
 306     /// <remarks>\r
 307     ///     This function is concurrency safe.\r
 308     /// </remarks>\r
 309     /// <returns>\r
 310     ///     A const_iterator to the first element in the concurrent container.\r
 311     /// </returns>\r
 312     /**/\r
 313     const_iterator begin() const\r
 314     {\r
 315         return _M_split_ordered_list.begin();\r
 316     }\r
 317 \r
 318     /// <summary>\r
 319     ///     Returns an iterator pointing to the location succeeding the last element in the concurrent container.\r
 320     /// </summary>\r
 321     /// <remarks>\r
 322     ///     This function is concurrency safe.\r
 323     /// </remarks>\r
 324     /// <returns>\r
 325     ///     An iterator to the location succeeding the last element in the concurrent container.\r
 326     /// </returns>\r
 327     /**/\r
 328     iterator end()\r
 329     {\r
 330         return _M_split_ordered_list.end();\r
 331     }\r
 332 \r
 333     /// <summary>\r
 334     ///     Returns a const_iterator pointing to the location succeeding the last element in the concurrent container.\r
 335     /// </summary>\r
 336     /// <remarks>\r
 337     ///     This function is concurrency safe.\r
 338     /// </remarks>\r
 339     /// <returns>\r
 340     ///     A const_iterator to the location succeeding the last element in the concurrent container.\r
 341     /// </returns>\r
 342     /**/\r
 343     const_iterator end() const\r
 344     {\r
 345         return _M_split_ordered_list.end();\r
 346     }\r
 347 \r
 348     /// <summary>\r
 349     ///     Returns a const_iterator pointing to the first element in the concurrent container.\r
 350     /// </summary>\r
 351     /// <remarks>\r
 352     ///     This function is concurrency safe.\r
 353     /// </remarks>\r
 354     /// <returns>\r
 355     ///     A const_iterator to the first element in the concurrent container.\r
 356     /// </returns>\r
 357     /**/\r
 358     const_iterator cbegin() const\r
 359     {\r
 360         return _M_split_ordered_list.cbegin();\r
 361     }\r
 362 \r
 363     /// <summary>\r
 364     ///     Returns a const_iterator pointing to the location succeeding the last element in the concurrent container.\r
 365     /// </summary>\r
 366     /// <remarks>\r
 367     ///     This function is concurrency safe.\r
 368     /// </remarks>\r
 369     /// <returns>\r
 370     ///     A const_iterator to the location succeeding the last element in the concurrent container.\r
 371     /// </returns>\r
 372     /**/\r
 373     const_iterator cend() const\r
 374     {\r
 375         return _M_split_ordered_list.cend();\r
 376     }\r
 377 \r
 378     // Modifiers\r
 379     /// <summary>\r
 380     ///     Inserts a value into the concurrent container.\r
 381     /// </summary>\r
 382     /// <param name="_Value">\r
 383     ///     The value to insert.\r
 384     /// </param>\r
 385     /// <remarks>\r
 386     ///     This function is concurrency safe.\r
 387     /// </remarks>\r
 388     /// <returns>\r
 389     ///     A <see cref="pair Class">pair</see> where the first object is an iterator into the container at the insertion point and the \r
 390     ///     second object is a bool indicating whether the value was inserted (true) or not (false).\r
 391     /// </returns>\r
 392     /**/\r
 393     _Pairib insert(const value_type& _Value)\r
 394     {\r
 395         return _Insert(_Value);\r
 396     }\r
 397 \r
 398     /// <summary>\r
 399     ///     Inserts a value into the concurrent container.\r
 400     /// </summary>\r
 401     /// <typeparam name="_Valty">\r
 402     ///     The type of the value inserted into the map.\r
 403     /// </typeparm>\r
 404     /// <param name="_Value">\r
 405     ///     The value to insert.\r
 406     /// </param>\r
 407     /// <remarks>\r
 408     ///     This function is concurrency safe.\r
 409     /// </remarks>\r
 410     /// <returns>\r
 411     ///     A <see cref="pair Class">pair</see> where the first object is an iterator into the container at the insertion point and the \r
 412     ///     second object is a bool indicating whether the value was inserted (true) or not (false).\r
 413     /// </returns>\r
 414     /**/\r
 415     template<class _Valty>\r
 416     _Pairib insert(_Valty&& _Value)\r
 417     {\r
 418         return _Insert(std::forward<_Valty>(_Value));\r
 419     }\r
 420 \r
 421     /// <summary>\r
 422     ///     Inserts a value into the concurrent container.\r
 423     /// </summary>\r
 424     /// <param name="_Value">\r
 425     ///     The value to insert.\r
 426     /// </param>\r
 427     /// <remarks>\r
 428     ///     This function is concurrency safe.\r
 429     ///     <para>The current implementation ignores the first <c>const_iterator</c> argument. It exists for\r
 430     ///     similarity with the <see cref="unordered_map Class">unordered_map</see>, and hints to a location to start the search\r
 431     ///     for an insertion point.</para>\r
 432     /// </remarks>\r
 433     /// <returns>\r
 434     ///     An iterator pointing to the insertion point of the object.  If the key already exists in the container\r
 435     ///     and the container does not support multiple keys, an iterator pointing to the duplicate key location in \r
 436     ///     the map is returned. \r
 437     /// </returns>\r
 438     /**/\r
 439     iterator insert(const_iterator, const value_type& _Value)\r
 440     {\r
 441         // Ignore hint\r
 442         return insert(_Value).first;\r
 443     }\r
 444 \r
 445     /// <summary>\r
 446     ///     Inserts a value into the concurrent container.\r
 447     /// </summary>\r
 448     /// <typeparam name="_Valty">\r
 449     ///     The type of the value inserted into the map.\r
 450     /// </typeparm>\r
 451     /// <param name="_Value">\r
 452     ///     The value to insert.\r
 453     /// </param>\r
 454     /// <remarks>\r
 455     ///     This function is concurrency safe.\r
 456     ///     <para>The current implementation ignores the first <c>const_iterator</c> argument. It exists for\r
 457     ///     similarity with the <see cref="unordered_map Class">unordered_map</see>, and hints to a location to start the search\r
 458     ///     for an insertion point.</para>\r
 459     /// </remarks>\r
 460     /// <returns>\r
 461     ///     An iterator pointing to the insertion point of the object.  If the key already exists in the container\r
 462     ///     and the container does not support multiple keys, an iterator pointing to the duplicate key location in \r
 463     ///     the map is returned.\r
 464     /// </returns>\r
 465     /**/\r
 466     template<class _Valty>\r
 467         typename std::tr1::enable_if<!std::tr1::is_same<const_iterator, \r
 468             typename std::tr1::remove_reference<_Valty>::type>::value, iterator>::type\r
 469     insert(const_iterator, _Valty&& _Value)\r
 470     {\r
 471         // Ignore hint\r
 472         return insert(std::forward<_Valty>(_Value)).first;\r
 473     }\r
 474 \r
 475     /// <summary>\r
 476     ///     Inserts a set of values into the concurrent container from an iterator.\r
 477     /// </summary>\r
 478     /// <typeparam name="_Iterator">\r
 479     ///     The iterator type used for insertion.\r
 480     /// </typeparm>\r
 481     /// <param name="_First">\r
 482     ///     The input iterator pointing to the beginning location.\r
 483     /// </param>\r
 484     /// <param name="_Last">\r
 485     ///     The input iterator pointing to the end location.\r
 486     /// </param>\r
 487     /// <remarks>\r
 488     ///     This function is concurrency safe.\r
 489     /// </remarks>\r
 490     /**/\r
 491     template<class _Iterator>\r
 492     void insert(_Iterator _First, _Iterator _Last)\r
 493     {\r
 494         for (_Iterator _I = _First; _I != _Last; _I++)\r
 495         {\r
 496             insert(*_I);\r
 497         }\r
 498     }\r
 499 \r
 500     /// <summary>\r
 501     ///     Erases an element from the concurrent container.\r
 502     /// </summary>\r
 503     /// <param name="_Where">\r
 504     ///     A <c>const_iterator</c> pointing to the element to erase.\r
 505     /// </param>\r
 506     /// <remarks>\r
 507     ///     This function is not concurrency safe.\r
 508     /// </remarks>\r
 509     /// <returns>\r
 510     ///     An iterator pointing to the location immediately following the deleted object in the container.\r
 511     /// </returns>\r
 512     /**/\r
 513     iterator unsafe_erase(const_iterator _Where)\r
 514     {\r
 515         return _Erase(_Where);\r
 516     }\r
 517 \r
 518     /// <summary>\r
 519     ///     Erases multiple elements from the concurrent container.\r
 520     /// </summary>\r
 521     /// <param name="_First">\r
 522     ///     A <c>const_iterator</c> pointing to the first element to erase.\r
 523     /// </param>\r
 524     /// <param name="_Last">\r
 525     ///     A <c>const_iterator</c> pointing to the location after the last element to erase,.\r
 526     /// </param>\r
 527     /// <remarks>\r
 528     ///     This function is not concurrency safe.\r
 529     /// </remarks>\r
 530     /// <returns>\r
 531     ///     An iterator pointing to the location immediately following the deleted object(s) in the container.\r
 532     /// </returns>\r
 533     /**/\r
 534     iterator unsafe_erase(const_iterator _First, const_iterator _Last)\r
 535     {\r
 536         while (_First != _Last)\r
 537         {\r
 538             unsafe_erase(_First++);\r
 539         }\r
 540 \r
 541         return _M_split_ordered_list._Get_iterator(_First);\r
 542     }\r
 543 \r
 544     /// <summary>\r
 545     ///     Erases an element from the concurrent container.\r
 546     /// </summary>\r
 547     /// <param name="_Keyval">\r
 548     ///     The value to erase from the concurrent container.\r
 549     /// </param>\r
 550     /// <remarks>\r
 551     ///     This function is not concurrency safe.\r
 552     /// </remarks>\r
 553     /// <returns>\r
 554     ///     A count of the number of keys removed from the concurrent_unordered_map.  \r
 555     /// </returns>\r
 556     /**/\r
 557     size_type unsafe_erase(const key_type& _Keyval)\r
 558     {\r
 559         _Pairii _Where = equal_range(_Keyval);\r
 560         size_type _Count = _Distance(_Where.first, _Where.second);\r
 561         unsafe_erase(_Where.first, _Where.second);\r
 562         return _Count;\r
 563     }\r
 564 \r
 565     /// <summary>\r
 566     ///     Swaps the contents of two concurrent containers.\r
 567     /// </summary>\r
 568     /// <param name="_Right">\r
 569     ///     The container to swap elements from.\r
 570     /// </param>\r
 571     /// <remarks>\r
 572     ///     This function is not concurrency safe.\r
 573     /// </remarks>\r
 574     /// <returns>\r
 575     ///     Throws an <see cref="invalid_argument Class">invalid_argument</see> exception if the swap is being\r
 576     ///     performed on unequal allocators.\r
 577     /// </returns>\r
 578     /**/\r
 579     void swap(_Concurrent_hash& _Right)\r
 580     {\r
 581         if (this != &_Right)\r
 582         {\r
 583             std::_Swap_adl(_M_comparator, _Right._M_comparator);\r
 584             _M_split_ordered_list.swap(_Right._M_split_ordered_list);\r
 585             _Swap_buckets(_Right);\r
 586             std::swap(_M_number_of_buckets, _Right._M_number_of_buckets);\r
 587             std::swap(_M_maximum_bucket_size, _Right._M_maximum_bucket_size);\r
 588         }\r
 589     }\r
 590 \r
 591     // Observers\r
 592     /// <summary>\r
 593     ///     Clears all the objects in the concurrent container.\r
 594     /// </summary>\r
 595     /// <remarks>\r
 596     ///     This function is not concurrency safe.\r
 597     /// </remarks>\r
 598     /**/\r
 599     void clear()\r
 600     {\r
 601         // Clear list\r
 602         _M_split_ordered_list.clear();\r
 603 \r
 604         // Clear buckets\r
 605         for (size_type _Index = 0; _Index < _Pointers_per_table; _Index++)\r
 606         {\r
 607             if (_M_buckets[_Index] != NULL)\r
 608             {\r
 609                 size_type _Seg_size = _Segment_size(_Index);\r
 610                 for (size_type _Index2 = 0; _Index2 < _Seg_size; _Index2++)\r
 611                 {\r
 612                     _M_allocator.destroy(&_M_buckets[_Index][_Index2]);\r
 613                 }\r
 614                 _M_allocator.deallocate(_M_buckets[_Index], _Seg_size);\r
 615             }\r
 616         }\r
 617 \r
 618         // memset all the buckets to zero and initialize the dummy node 0\r
 619         _Init();\r
 620     }\r
 621 \r
 622     // Lookup\r
 623     /// <summary>\r
 624     ///     Searches the concurrent container for a specific key.\r
 625     /// </summary>\r
 626     /// <param name="_Keyval">\r
 627     ///     The key to search for.\r
 628     /// </param>\r
 629     /// <remarks>\r
 630     ///     This function is concurrency safe.\r
 631     /// </remarks>\r
 632     /// <returns>\r
 633     ///     An iterator pointing to the location of the searched for key, or points to end() if not found.\r
 634     /// </returns>\r
 635     /**/\r
 636     iterator find(const key_type& _Keyval)\r
 637     {\r
 638         return _Find(_Keyval);\r
 639     }\r
 640 \r
 641     /// <summary>\r
 642     ///     Searches the concurrent container for a specific key.\r
 643     /// </summary>\r
 644     /// <param name="_Keyval">\r
 645     ///     The key to search for.\r
 646     /// </param>\r
 647     /// <remarks>\r
 648     ///     This function is concurrency safe.\r
 649     /// </remarks>\r
 650     /// <returns>\r
 651     ///     A const_iterator pointing to the location of the searched for key.\r
 652     /// </returns>\r
 653     /**/\r
 654     const_iterator find(const key_type& _Keyval) const\r
 655     {\r
 656         return _Find(_Keyval);\r
 657     }\r
 658 \r
 659     /// <summary>\r
 660     ///     Counts the number of times a specific key appears in the container.\r
 661     /// </summary>\r
 662     /// <param name="_Keyval">\r
 663     ///     The key to count.\r
 664     /// </param>\r
 665     /// <remarks>\r
 666     ///     This function is concurrency safe.\r
 667     /// </remarks>\r
 668     /// <returns>\r
 669     ///     The number of times the key appears in the container.\r
 670     /// </returns>\r
 671     /**/\r
 672     size_type count(const key_type& _Keyval) const\r
 673     {\r
 674         size_type _Count = 0;\r
 675         const_iterator _It = _Find(_Keyval);\r
 676         for (;_It != end() && !_M_comparator(_Key_function(*_It), _Keyval); _It++)\r
 677         {\r
 678             _Count++;\r
 679         }\r
 680         return _Count;\r
 681     }\r
 682 \r
 683     /// <summary>\r
 684     ///     Finds the iterators pointing to the being and end locations a specific key appears in the container.\r
 685     /// </summary>\r
 686     /// <param name="_Keyval">\r
 687     ///     The key to search for.\r
 688     /// </param>\r
 689     /// <remarks>\r
 690     ///     This function is concurrency safe. \r
 691     ///     <para>It is possible that concurrent inserts may cause the additional keys to be inserted after the \r
 692     ///     begin iterator and before the end iterator.</para>\r
 693     /// </remarks>\r
 694     /// <returns>\r
 695     ///     A <see cref="pair Class">pair</see> where the first element is an iterator to the beginning and the second element\r
 696     ///     is an iterator to the end of the range..\r
 697     /// </returns>\r
 698     /**/\r
 699     _Pairii equal_range(const key_type& _Keyval)\r
 700     {\r
 701         return _Equal_range(_Keyval);\r
 702     }\r
 703 \r
 704     /// <summary>\r
 705     ///     Finds the const_iterators pointing to the being and end locations a specific key appears in the container.\r
 706     /// </summary>\r
 707     /// <param name="_Keyval">\r
 708     ///     The key to search for.\r
 709     /// </param>\r
 710     /// <remarks>\r
 711     ///     This function is concurrency safe. \r
 712     ///     <para>It is possible that concurrent inserts may cause the additional keys to be inserted after the \r
 713     ///     begin iterator and before the end iterator.</para>\r
 714     /// </remarks>\r
 715     /// <returns>\r
 716     ///     A <see cref="pair Class">pair</see> where the first element is a const_iterator to the beginning and the second element\r
 717     ///     is a const_iterator to the end of the range.\r
 718     /// </returns>\r
 719     /**/\r
 720     _Paircc equal_range(const key_type& _Keyval) const\r
 721     {\r
 722         return _Equal_range(_Keyval);\r
 723     }\r
 724 \r
 725     // Bucket interface - for debugging \r
 726     /// <summary>\r
 727     ///     Returns the current number of buckets in this container.\r
 728     /// </summary>\r
 729     /// <returns>\r
 730     ///     The current number of buckets in this container.\r
 731     /// </returns>\r
 732     /**/\r
 733     size_type unsafe_bucket_count() const\r
 734     {\r
 735         return _M_number_of_buckets;\r
 736     }\r
 737 \r
 738     /// <summary>\r
 739     ///     Returns the maximum number of buckets in this container.\r
 740     /// </summary>\r
 741     /// <returns>\r
 742     ///     The maximum number of buckets in this container.\r
 743     /// </returns>\r
 744     /**/\r
 745     size_type unsafe_max_bucket_count() const\r
 746     {\r
 747         return _Segment_size(_Pointers_per_table-1);\r
 748     }\r
 749 \r
 750     /// <summary>\r
 751     ///     Returns the number of items in a specific bucket of this container.\r
 752     /// </summary>\r
 753     /// <param name="_Bucket">\r
 754     ///     The bucket to search for.\r
 755     /// </param>\r
 756     /// <returns>\r
 757     ///     The current number of buckets in this container.\r
 758     /// </returns>\r
 759     /**/\r
 760     size_type unsafe_bucket_size(size_type _Bucket)\r
 761     {\r
 762         size_type _Count = 0;\r
 763 \r
 764         if (!_Is_initialized(_Bucket))\r
 765         {\r
 766             return _Count;\r
 767         }\r
 768 \r
 769         _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
 770         _Iterator++;\r
 771 \r
 772         for (; _Iterator != _M_split_ordered_list._End() && !_Iterator._Mynode()->_Is_dummy(); _Iterator++)\r
 773         {\r
 774             _Count++;\r
 775         }\r
 776 \r
 777         return _Count;\r
 778     }\r
 779 \r
 780     /// <summary>\r
 781     ///     Returns the bucket index that a specific key maps to in this container.\r
 782     /// </summary>\r
 783     /// <param name="_Keyval">\r
 784     ///     The element key being searched for.\r
 785     /// </param>\r
 786     /// <returns>\r
 787     ///     The bucket index for the key in this container.\r
 788     /// </returns>\r
 789     /**/\r
 790     size_type unsafe_bucket(const key_type& _Keyval) const\r
 791     {\r
 792         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
 793         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
 794         return _Bucket;\r
 795     }\r
 796 \r
 797     // If the bucket is initialized, return a first non-dummy element in it\r
 798 \r
 799     /// <summary>\r
 800     ///     Returns an iterator to the first element in this container for a specific bucket.\r
 801     /// </summary>\r
 802     /// <param name="_Bucket">\r
 803     ///     The bucket index.\r
 804     /// </param>\r
 805     /// <returns>\r
 806     ///     An iterator pointing to the beginning of the bucket.\r
 807     /// </returns>\r
 808     /**/\r
 809     local_iterator unsafe_begin(size_type _Bucket)\r
 810     {\r
 811         // It is possible the bucket being searched for has not yet been initialized\r
 812         if (!_Is_initialized(_Bucket))\r
 813         {\r
 814             _Initialize_bucket(_Bucket);\r
 815         }\r
 816 \r
 817         _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
 818         return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
 819     }\r
 820 \r
 821     // If the bucket is initialized, return a first non-dummy element in it\r
 822 \r
 823     /// <summary>\r
 824     ///     Returns a const_iterator to the first element in this container for a specific bucket.\r
 825     /// </summary>\r
 826     /// <param name="_Bucket">\r
 827     ///     The bucket index.\r
 828     /// </param>\r
 829     /// <returns>\r
 830     ///     A const_iterator pointing to the beginning of the bucket.\r
 831     /// </returns>\r
 832     /**/\r
 833     const_local_iterator unsafe_begin(size_type _Bucket) const\r
 834     {\r
 835         // It is possible the bucket being searched for has not yet been initialized\r
 836         if (!_Is_initialized(_Bucket))\r
 837         {\r
 838             _Initialize_bucket(_Bucket);\r
 839         }\r
 840 \r
 841 \r
 842         _Full_const_iterator _Iterator = _Get_bucket(_Bucket);\r
 843         return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
 844     }\r
 845 \r
 846     // Returns the iterator after the last non-dummy element in the bucket\r
 847 \r
 848     /// <summary>\r
 849     ///     Returns an iterator to the last element in this container for a specific bucket.\r
 850     /// </summary>\r
 851     /// <param name="_Bucket">\r
 852     ///     The bucket index.\r
 853     /// </param>\r
 854     /// <returns>\r
 855     ///     An iterator pointing to the end of the bucket.\r
 856     /// </returns>\r
 857     /**/\r
 858     local_iterator unsafe_end(size_type _Bucket)\r
 859     {\r
 860         // If we've increased the number of buckets, there's a chance the intermediate dummy\r
 861         // node marking the end of this bucket has not yet been lazily initialized.\r
 862         // Inserting from from _M_number_of_buckets/2 to _M_number_of_buckets will recursively\r
 863         // initialize all the dummy nodes in the map.\r
 864         for(size_type _Bucket_index = _M_number_of_buckets >> 1; _Bucket_index < _M_number_of_buckets; _Bucket_index++)\r
 865         {\r
 866             if (!_Is_initialized(_Bucket_index))\r
 867             {\r
 868                 _Initialize_bucket(_Bucket_index);\r
 869             }\r
 870         }\r
 871 \r
 872         _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
 873     \r
 874         // Find the end of the bucket, denoted by the dummy element\r
 875         do\r
 876         {\r
 877             _Iterator++;\r
 878         }\r
 879         while(_Iterator != _M_split_ordered_list._End() && !_Iterator._Mynode()->_Is_dummy());\r
 880 \r
 881         // Return the first real element past the end of the bucket\r
 882         return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
 883     }\r
 884 \r
 885     // Returns the iterator after the last non-dummy element in the bucket\r
 886 \r
 887     /// <summary>\r
 888     ///     Returns a const_iterator to the last element in this container for a specific bucket.\r
 889     /// </summary>\r
 890     /// <param name="_Bucket">\r
 891     ///     The bucket index.\r
 892     /// </param>\r
 893     /// <returns>\r
 894     ///     A const_iterator pointing to the end of the bucket.\r
 895     /// </returns>\r
 896     /**/\r
 897     const_local_iterator unsafe_end(size_type _Bucket) const\r
 898     {\r
 899         // If we've increased the number of buckets, there's a chance the intermediate dummy\r
 900         // node marking the end of this bucket has not yet been lazily initialized.\r
 901         // Inserting from from _M_number_of_buckets/2 to _M_number_of_buckets will recursively\r
 902         // initialize all the dummy nodes in the map.\r
 903         for(size_type _Bucket_index = _M_number_of_buckets >> 1; _Bucket_index < _M_number_of_buckets; _Bucket_index++)\r
 904         {\r
 905             if (!_Is_initialized(_Bucket_index))\r
 906             {\r
 907                 _Initialize_bucket(_Bucket_index);\r
 908             }\r
 909         }\r
 910 \r
 911         _Full_const_iterator _Iterator = _Get_bucket(_Bucket);\r
 912     \r
 913         // Find the end of the bucket, denoted by the dummy element\r
 914         do\r
 915         {\r
 916             _Iterator++;\r
 917         }\r
 918         while(_Iterator != _M_split_ordered_list._End() && !_Iterator._Mynode()->_Is_dummy());\r
 919 \r
 920         // Return the first real element past the end of the bucket\r
 921         return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
 922     }\r
 923 \r
 924     /// <summary>\r
 925     ///     Returns a const_iterator to the first element in this container for a specific bucket.\r
 926     /// </summary>\r
 927     /// <param name="_Bucket">\r
 928     ///     The bucket index.\r
 929     /// </param>\r
 930     /// <returns>\r
 931     ///     A const_iterator pointing to the beginning of the bucket.\r
 932     /// </returns>\r
 933     /**/\r
 934     const_local_iterator unsafe_cbegin(size_type _Bucket) const\r
 935     {\r
 936         return ((const _Mytype *) this)->begin();\r
 937     }\r
 938 \r
 939     /// <summary>\r
 940     ///     Returns a const_iterator to the last element in this container for a specific bucket.\r
 941     /// </summary>\r
 942     /// <param name="_Bucket">\r
 943     ///     The bucket index.\r
 944     /// </param>\r
 945     /// <returns>\r
 946     ///     A const_iterator pointing to the end of the bucket.\r
 947     /// </returns>\r
 948     /**/\r
 949     const_local_iterator unsafe_cend(size_type _Bucket) const\r
 950     {\r
 951         return ((const _Mytype *) this)->end();\r
 952     }\r
 953 \r
 954     // Hash policy\r
 955     /// <summary>\r
 956     ///     Computes and returns the current load factor of the container.  \r
 957     ///     The load factor is the number of elements in the container divided by the number of buckets.\r
 958     /// </summary>\r
 959     /// <returns>\r
 960     ///     The load factor for the container\r
 961     /// </returns>\r
 962     /**/\r
 963     float load_factor() const\r
 964     {\r
 965         return (float) size() / (float) unsafe_bucket_count();\r
 966     }\r
 967 \r
 968     /// <summary>\r
 969     ///     Returns the maximum load factor of the container.  The maximum load factor is the \r
 970     ///     largest number of elements than can be in any bucket before the container grows its \r
 971     ///     internal table.\r
 972     /// </summary>\r
 973     /// <returns>\r
 974     ///     The maximum load factor for the container\r
 975     /// </returns>\r
 976     /**/\r
 977     float max_load_factor() const\r
 978     {\r
 979         return _M_maximum_bucket_size;\r
 980     }\r
 981 \r
 982     /// <summary>\r
 983     ///     Sets the maximum load factor of the container to a specific value.\r
 984     /// </summary>\r
 985     /// <param name="_Newmax">\r
 986     ///     The desired load factor for this container.\r
 987     /// </param>\r
 988     /// <remarks>\r
 989     ///     Throws an <see cref="out_of_range Class">out_of_range</see> exception if the load factor is invalid (NaN or negative)\r
 990     /// </remarks>\r
 991     /**/\r
 992     void max_load_factor(float _Newmax)\r
 993     {\r
 994         // The _Newmax != _Newmax is a check for NaN, because NaN is != to itself\r
 995         if (_Newmax != _Newmax || _Newmax < 0)\r
 996         {\r
 997             throw std::out_of_range("invalid hash load factor");\r
 998         }\r
 999 \r
1000         _M_maximum_bucket_size = _Newmax;\r
1001     }\r
1002 \r
1003     // This function is a noop, because the underlying split-ordered list\r
1004     // is already sorted, so an increase in the bucket number will be\r
1005     // reflected next time this bucket is touched.\r
1006 \r
1007     /// <summary>\r
1008     ///     Sets the the number of buckets for the container to a specific value.\r
1009     /// </summary>\r
1010     /// <param name="_Buckets">\r
1011     ///     The desired number of buckets.\r
1012     /// </param>\r
1013     /// <remarks>\r
1014     ///     The number of buckets must be a power of 2. If not a power of 2, it will be rounded up to\r
1015     ///     the next largest power of 2.\r
1016     ///     <para>Throws an <see cref="out_of_range Class">out_of_range</see> exception if the number of buckets \r
1017     ///     is invalid (0 or greater than the maximum number of buckets)</para>\r
1018     /// </remarks>\r
1019     /**/\r
1020     void rehash(size_type _Buckets)\r
1021     {\r
1022         size_type _Current_buckets = _M_number_of_buckets;\r
1023 \r
1024         if (_Current_buckets > _Buckets)\r
1025         {\r
1026             return;\r
1027         }\r
1028         else if (_Buckets <= 0 || _Buckets > unsafe_max_bucket_count())\r
1029         {\r
1030             throw std::out_of_range("invalid number of buckets");\r
1031         }\r
1032         // Round up the number of buckets to the next largest power of 2\r
1033         _M_number_of_buckets = ((size_type) 1) << _Get_msb(_Buckets*2-1);\r
1034     }\r
1035 \r
1036 private:\r
1037 \r
1038     // Initialize the hash and keep the first bucket open\r
1039     void _Init()\r
1040     {\r
1041         // Allocate an array of segment pointers\r
1042         memset(_M_buckets, 0, _Pointers_per_table * sizeof(void *));\r
1043 \r
1044         // Insert the first element in the split-ordered list\r
1045         _Full_iterator _Dummy_node = _M_split_ordered_list._Begin();\r
1046         _Set_bucket(0, _Dummy_node);\r
1047     }\r
1048 \r
1049     void _Copy(const _Mytype& _Right)\r
1050     {\r
1051         clear();\r
1052 \r
1053         _M_maximum_bucket_size = _Right._M_maximum_bucket_size;\r
1054         _M_number_of_buckets = _Right._M_number_of_buckets;\r
1055 \r
1056         try\r
1057         {\r
1058             insert(_Right.begin(), _Right.end());\r
1059             _M_comparator = _Right._M_comparator;\r
1060         }\r
1061         catch(...)\r
1062         {\r
1063             _M_split_ordered_list.clear();\r
1064             throw;\r
1065         }\r
1066     }\r
1067 \r
1068     void _Swap_buckets(_Concurrent_hash& _Right)\r
1069     {\r
1070         if (_M_allocator == _Right._M_allocator)\r
1071         {\r
1072             // Swap all node segments\r
1073             for (size_type _Index = 0; _Index < _Pointers_per_table; _Index++)\r
1074             {\r
1075                 _Full_iterator * _Iterator_pointer = _M_buckets[_Index];\r
1076                 _M_buckets[_Index] = _Right._M_buckets[_Index];\r
1077                 _Right._M_buckets[_Index] = _Iterator_pointer;\r
1078             }\r
1079         }\r
1080         else\r
1081         {\r
1082             throw std::invalid_argument("swap is invalid on non-equal allocators");\r
1083         }\r
1084     }\r
1085 \r
1086     // Hash APIs\r
1087     size_type _Distance(const_iterator _First, const_iterator _Last) const\r
1088     {\r
1089         size_type _Num = 0;\r
1090 \r
1091         for (const_iterator _Iterator = _First; _Iterator != _Last; _Iterator++)\r
1092         {\r
1093             _Num++;\r
1094         }\r
1095 \r
1096         return _Num;\r
1097     }\r
1098 \r
1099     // Insert an element in the hash given its value\r
1100     template<typename _ValTy>\r
1101     _Pairib _Insert(_ValTy&& _Value)\r
1102     {\r
1103         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Key_function(_Value));\r
1104         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
1105 \r
1106         // If bucket is empty, initialize it first\r
1107         if (!_Is_initialized(_Bucket))\r
1108         {\r
1109             _Initialize_bucket(_Bucket);\r
1110         }\r
1111 \r
1112         long _New_count;\r
1113         _Order_key = _Split_order_regular_key(_Order_key);\r
1114         _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
1115         _Full_iterator _Last = _M_split_ordered_list._End();\r
1116         _Full_iterator _Where = _Iterator;\r
1117         _Nodeptr _New_node = _M_split_ordered_list._Buynode(_Order_key, std::forward<_ValTy>(_Value));\r
1118 \r
1119         _ASSERT_EXPR(_Where != _Last, L"Invalid head node");\r
1120 \r
1121         // First node is a dummy node\r
1122         _Where++;\r
1123 \r
1124         for (;;)\r
1125         {\r
1126             if (_Where == _Last || _Mylist::_Get_key(_Where) > _Order_key)\r
1127             {\r
1128                 // Try to insert it in the right place\r
1129                 _Pairib _Result = _M_split_ordered_list._Insert(_Iterator, _Where, _New_node, &_New_count);\r
1130                 \r
1131                 if (_Result.second)\r
1132                 {\r
1133                     // Insertion succeeded, adjust the table size, if needed\r
1134                     _Adjust_table_size(_New_count, _M_number_of_buckets);\r
1135                     return _Result;\r
1136                 }\r
1137                 else\r
1138                 {\r
1139                     // Insertion failed: either the same node was inserted by another thread, or\r
1140                     // another element was inserted at exactly the same place as this node.\r
1141                     // Proceed with the search from the previous location where order key was\r
1142                     // known to be larger (note: this is legal only because there is no safe\r
1143                     // concurrent erase operation supported).\r
1144                     _Where = _Iterator;\r
1145                     _Where++;\r
1146                     continue;\r
1147                 }\r
1148             }\r
1149             else if (!_M_allow_multimapping && _Mylist::_Get_key(_Where) == _Order_key && \r
1150                 _M_comparator(_Key_function(*_Where), _Key_function(_New_node->_M_element)) == 0)\r
1151             {\r
1152                 // If the insert failed (element already there), then delete the new one\r
1153                 _M_split_ordered_list._Erase(_New_node);\r
1154 \r
1155                 // Element already in the list, return it\r
1156                 return _Pairib(_M_split_ordered_list._Get_iterator(_Where), false);\r
1157             }\r
1158 \r
1159             // Move the iterator forward\r
1160             _Iterator = _Where;\r
1161             _Where++;\r
1162         }\r
1163     }\r
1164     // Find the element in the split-ordered list\r
1165     iterator _Find(const key_type& _Keyval)\r
1166     {\r
1167         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
1168         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
1169 \r
1170         // If _Bucket is empty, initialize it first\r
1171         if (!_Is_initialized(_Bucket))\r
1172         {\r
1173             _Initialize_bucket(_Bucket);\r
1174         }\r
1175 \r
1176         _Order_key = _Split_order_regular_key(_Order_key);\r
1177         _Full_iterator _Last = _M_split_ordered_list._End();\r
1178 \r
1179         for (_Full_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
1180         {\r
1181             if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
1182             {\r
1183                 // If the order key is smaller than the current order key, the element\r
1184                 // is not in the hash.\r
1185                 return end();\r
1186             }\r
1187             else if (_Mylist::_Get_key(_Iterator) == _Order_key)\r
1188             {\r
1189                 // The fact that order keys match does not mean that the element is found.\r
1190                 // Key function comparison has to be performed to check whether this is the\r
1191                 // right element. If not, keep searching while order key is the same.\r
1192                 if (!_M_comparator(_Key_function(*_Iterator), _Keyval))\r
1193                 {\r
1194                     return _M_split_ordered_list._Get_iterator(_Iterator);\r
1195                 }\r
1196             }\r
1197         }\r
1198 \r
1199         return end();\r
1200     }\r
1201 \r
1202     // Find the element in the split-ordered list\r
1203     const_iterator _Find(const key_type& _Keyval) const\r
1204     {\r
1205         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
1206         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
1207 \r
1208         // If _Bucket has not been initialized, keep searching up for a parent bucket\r
1209         // that has been initialized.  Worst case is the entire map will be read.\r
1210         while (!_Is_initialized(_Bucket))\r
1211         {\r
1212             _Bucket = _Get_parent(_Bucket);\r
1213         }\r
1214 \r
1215         _Order_key = _Split_order_regular_key(_Order_key);\r
1216         _Full_const_iterator _Last = _M_split_ordered_list._End();\r
1217 \r
1218         for (_Full_const_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
1219         {\r
1220             if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
1221             {\r
1222                 // If the order key is smaller than the current order key, the element\r
1223                 // is not in the hash.\r
1224                 return end();\r
1225             }\r
1226             else if (_Mylist::_Get_key(_Iterator) == _Order_key)\r
1227             {\r
1228                 // The fact that order keys match does not mean that the element is found.\r
1229                 // Key function comparison has to be performed to check whether this is the\r
1230                 // right element. If not, keep searching while order key is the same.\r
1231                 if (!_M_comparator(_Key_function(*_Iterator), _Keyval))\r
1232                 {\r
1233                     return _M_split_ordered_list._Get_iterator(_Iterator);\r
1234                 }\r
1235             }\r
1236         }\r
1237 \r
1238         return end();\r
1239     }\r
1240 \r
1241     // Erase an element from the list. This is not a concurrency safe function.\r
1242     iterator _Erase(const_iterator _Iterator)\r
1243     {\r
1244         key_type _Keyval = _Key_function(*_Iterator);\r
1245         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
1246         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
1247 \r
1248         // If bucket is empty, initialize it first\r
1249         if (!_Is_initialized(_Bucket))\r
1250         {\r
1251             _Initialize_bucket(_Bucket);\r
1252         }\r
1253 \r
1254         _Order_key = _Split_order_regular_key(_Order_key);\r
1255 \r
1256         _Full_iterator _Previous = _Get_bucket(_Bucket);\r
1257         _Full_iterator _Last = _M_split_ordered_list._End();\r
1258         _Full_iterator _Where = _Previous;\r
1259 \r
1260         _ASSERT_EXPR(_Where != _Last, L"Invalid head node");\r
1261 \r
1262         // First node is a dummy node\r
1263         _Where++;\r
1264 \r
1265         for (;;)\r
1266         {\r
1267             if (_Where == _Last)\r
1268             {\r
1269                 return end();\r
1270             }\r
1271             else if (_M_split_ordered_list._Get_iterator(_Where) == _Iterator)\r
1272             {\r
1273                 return _M_split_ordered_list._Erase(_Previous, _Iterator);\r
1274             }\r
1275 \r
1276             // Move the iterator forward\r
1277             _Previous = _Where;\r
1278             _Where++;\r
1279         }\r
1280     }\r
1281 \r
1282     // Return the [begin, end) pair of iterators with the same key values.\r
1283     // This operation makes sense only if mapping is many-to-one.\r
1284     _Pairii _Equal_range(const key_type& _Keyval)\r
1285     {\r
1286         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
1287         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
1288 \r
1289         // If _Bucket is empty, initialize it first\r
1290         if (!_Is_initialized(_Bucket))\r
1291         {\r
1292             _Initialize_bucket(_Bucket);\r
1293         }\r
1294 \r
1295         _Order_key = _Split_order_regular_key(_Order_key);\r
1296         _Full_iterator _Last = _M_split_ordered_list._End();\r
1297 \r
1298         for (_Full_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
1299         {\r
1300             if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
1301             {\r
1302                 // There is no element with the given key\r
1303                 return _Pairii(end(), end());\r
1304             }\r
1305             else if (_Mylist::_Get_key(_Iterator) == _Order_key && !_M_comparator(_Key_function(*_Iterator), _Keyval))\r
1306             {\r
1307                 iterator _Begin = _M_split_ordered_list._Get_iterator(_Iterator);\r
1308                 iterator _End= _Begin;\r
1309 \r
1310                 for (;_End != end() && !_M_comparator(_Key_function(*_End), _Keyval); _End++)\r
1311                 {\r
1312                 }\r
1313 \r
1314                 return _Pairii(_Begin, _End);\r
1315             }\r
1316         }\r
1317 \r
1318         return _Pairii(end(), end());\r
1319     }\r
1320 \r
1321     // Return the [begin, end) pair of const iterators with the same key values.\r
1322     // This operation makes sense only if mapping is many-to-one.\r
1323     _Paircc _Equal_range(const key_type& _Keyval) const\r
1324     {\r
1325         _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
1326         size_type _Bucket = _Order_key % _M_number_of_buckets;\r
1327 \r
1328         // If _Bucket has not been initialized, keep searching up for a parent bucket\r
1329         // that has been initialized.  Worst case is the entire map will be read.\r
1330         while (!_Is_initialized(_Bucket))\r
1331         {\r
1332             _Bucket = _Get_parent(_Bucket);\r
1333         }\r
1334 \r
1335         _Order_key = _Split_order_regular_key(_Order_key);\r
1336         _Full_const_iterator _Last = _M_split_ordered_list._End();\r
1337 \r
1338         for (_Full_const_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
1339         {\r
1340             if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
1341             {\r
1342                 // There is no element with the given key\r
1343                 return _Paircc(end(), end());\r
1344             }\r
1345             else if (_Mylist::_Get_key(_Iterator) == _Order_key && !_M_comparator(_Key_function(*_Iterator), _Keyval))\r
1346             {\r
1347                 const_iterator _Begin = _M_split_ordered_list._Get_iterator(_Iterator);\r
1348                 const_iterator _End = _Begin;\r
1349 \r
1350                 for (; _End != end() && !_M_comparator(_Key_function(*_End), _Keyval); _End++)\r
1351                 {\r
1352                 }\r
1353 \r
1354                 return _Paircc(_Begin, _End);\r
1355             }\r
1356         }\r
1357 \r
1358         return _Paircc(end(), end());\r
1359     }\r
1360 \r
1361     // Bucket APIs\r
1362     void _Initialize_bucket(size_type _Bucket)\r
1363     {\r
1364         // Bucket 0 has no parent. Initialize it and return.\r
1365         if (_Bucket == 0)\r
1366         {\r
1367             _Init();\r
1368             return;\r
1369         }\r
1370 \r
1371         size_type _Parent_bucket = _Get_parent(_Bucket);\r
1372 \r
1373         // All _Parent_bucket buckets have to be initialized before this bucket is\r
1374         if (!_Is_initialized(_Parent_bucket))\r
1375         {\r
1376             _Initialize_bucket(_Parent_bucket);\r
1377         }\r
1378 \r
1379         _Full_iterator _Parent = _Get_bucket(_Parent_bucket);\r
1380 \r
1381         // Create a dummy first node in this bucket\r
1382         _Full_iterator _Dummy_node = _M_split_ordered_list._Insert_dummy(_Parent, _Split_order_dummy_key(_Bucket));\r
1383         _Set_bucket(_Bucket, _Dummy_node);\r
1384     }\r
1385 \r
1386     void _Adjust_table_size(size_type _Total_elements, size_type _Current_size)\r
1387     {\r
1388         // Grow the table by a factor of 2 if possible and needed\r
1389         if (((float) _Total_elements / (float) _Current_size) > _M_maximum_bucket_size)\r
1390         {\r
1391              // Double the size of the hash only if size has not changed inbetween loads\r
1392             _InterlockedCompareExchangeSizeT(&_M_number_of_buckets, 2 * _Current_size, _Current_size);\r
1393         }\r
1394     }\r
1395 \r
1396     size_type _Get_parent(size_type _Bucket) const\r
1397     {\r
1398         // Unsets bucket's most significant turned-on bit\r
1399         unsigned char _Msb = _Get_msb(_Bucket);\r
1400         return _Bucket & ~(1 << _Msb);\r
1401     }\r
1402 \r
1403 \r
1404     // Dynamic sized array (segments)\r
1405 \r
1406     _Full_iterator _Get_bucket(size_type _Bucket) const\r
1407     {\r
1408         size_type _Segment = _Segment_index_of(_Bucket);\r
1409         _Bucket -= _Segment_base(_Segment);\r
1410         return _M_buckets[_Segment][_Bucket];\r
1411     }\r
1412 \r
1413     void _Set_bucket(size_type _Bucket, _Full_iterator _Dummy_head)\r
1414     {\r
1415         size_type _Segment = _Segment_index_of(_Bucket);\r
1416         _Bucket -= _Segment_base(_Segment);\r
1417 \r
1418         if (_M_buckets[_Segment] == NULL)\r
1419         {\r
1420             size_type _Seg_size = _Segment_size(_Segment);\r
1421             _Full_iterator * _New_segment = _M_allocator.allocate(_Seg_size);\r
1422             _Uninitialized_default_fill_n(_New_segment, _Seg_size, (_Full_iterator *) 0, _M_allocator);\r
1423             if (_InterlockedCompareExchangePointer((void * volatile *) &_M_buckets[_Segment], _New_segment, NULL) != NULL)\r
1424             {\r
1425                 _M_allocator.deallocate(_New_segment, _Seg_size);\r
1426             }\r
1427         }\r
1428         _M_buckets[_Segment][_Bucket] = _Dummy_head;\r
1429     }\r
1430 \r
1431     bool _Is_initialized(size_type _Bucket) const\r
1432     {\r
1433         size_type _Segment = _Segment_index_of(_Bucket);\r
1434         _Bucket -= _Segment_base(_Segment);\r
1435 \r
1436         if (_M_buckets[_Segment] == NULL)\r
1437         {\r
1438             return false;\r
1439         }\r
1440 \r
1441         _Full_iterator _Iterator = _M_buckets[_Segment][_Bucket];\r
1442         return (_Iterator._Mynode() != NULL);\r
1443     }\r
1444 \r
1445     // Utilities for keys\r
1446 \r
1447     _Split_order_key _Reverse(_Map_key _Order_key) const\r
1448     {\r
1449         _Split_order_key _Reversed_order_key;\r
1450 \r
1451         unsigned char * _Original = (unsigned char *) &_Order_key;\r
1452         unsigned char * _Reversed = (unsigned char *) &_Reversed_order_key;\r
1453 \r
1454         int _Size = sizeof(_Map_key);\r
1455         for (int _Index = 0; _Index < _Size; _Index++)\r
1456         {\r
1457             _Reversed[_Size - _Index - 1] = _Reverse_byte(_Original[_Index]);\r
1458         }\r
1459 \r
1460         return _Reversed_order_key;\r
1461     }\r
1462 \r
1463     // A regular order key has its original hash value reversed and the last bit set\r
1464     _Split_order_key _Split_order_regular_key(_Map_key _Order_key) const\r
1465     {\r
1466         return _Reverse(_Order_key) | 0x1;\r
1467     }\r
1468 \r
1469     // A dummy order key has its original hash value reversed and the last bit unset\r
1470     _Split_order_key _Split_order_dummy_key(_Map_key _Order_key) const\r
1471     {\r
1472         return _Reverse(_Order_key) & ~(0x1);\r
1473     }\r
1474 \r
1475     // Shared variables\r
1476     _Full_iterator *                                                _M_buckets[_Pointers_per_table]; // The segment table\r
1477     _Mylist                                                         _M_split_ordered_list;           // List where all the elements are kept\r
1478     typename allocator_type::template rebind<_Full_iterator>::other _M_allocator;                    // Allocator object for segments\r
1479     size_type                                                       _M_number_of_buckets;            // Current table size\r
1480     float                                                           _M_maximum_bucket_size;          // Maximum size of the bucket\r
1481 };\r
1482 \r
1483 #pragma warning(pop) // warning 4127 -- while (true) has a constant expression in it\r
1484 \r
1485 } // namespace details;\r
1486 } // namespace Concurrency\r