git.sesse.net Git - casparcg/blob - tbb/include/tbb/internal/_concurrent_unordered_impl.h

   1 /*
   2     Copyright 2005-2011 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   6     Threading Building Blocks is free software; you can redistribute it
   7     and/or modify it under the terms of the GNU General Public License
   8     version 2 as published by the Free Software Foundation.
   9
  10     Threading Building Blocks is distributed in the hope that it will be
  11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with Threading Building Blocks; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18
  19     As a special exception, you may use this file as part of a free software
  20     library without restriction.  Specifically, if other files instantiate
  21     templates or use macros or inline functions from this file, or you compile
  22     this file and link it with other files to produce an executable, this
  23     file does not by itself cause the resulting executable to be covered by
  24     the GNU General Public License.  This exception does not however
  25     invalidate any other reasons why the executable file might be covered by
  26     the GNU General Public License.
  27 */
  28
  29 /* Container implementations in this header are based on PPL implementations
  30    provided by Microsoft. */
  31
  32 #ifndef __TBB_concurrent_unordered_internal_H
  33 #define __TBB_concurrent_unordered_internal_H
  34
  35 #include "../tbb_stddef.h"
  36
  37 #if !TBB_USE_EXCEPTIONS && _MSC_VER
  38     // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
  39     #pragma warning (push)
  40     #pragma warning (disable: 4530)
  41 #endif
  42
  43 #include <iterator>
  44 #include <utility>      // Need std::pair
  45 #include <functional>
  46 #include <string>       // For tbb_hasher
  47 #include <cstring>      // Need std::memset
  48
  49 #if !TBB_USE_EXCEPTIONS && _MSC_VER
  50     #pragma warning (pop)
  51 #endif
  52
  53 #include "../atomic.h"
  54 #include "../tbb_exception.h"
  55 #include "../tbb_allocator.h"
  56
  57 namespace tbb {
  58 namespace interface5 {
  59 //! @cond INTERNAL
  60 namespace internal {
  61
  62 template <typename T, typename Allocator>
  63 class split_ordered_list;
  64 template <typename Traits>
  65 class concurrent_unordered_base;
  66
  67 // Forward list iterators (without skipping dummy elements)
  68 template<class Solist, typename Value>
  69 class flist_iterator : public std::iterator<std::forward_iterator_tag, Value>
  70 {
  71     template <typename T, typename Allocator>
  72     friend class split_ordered_list;
  73     template <typename Traits>
  74     friend class concurrent_unordered_base;
  75     template<class M, typename V>
  76     friend class flist_iterator;
  77
  78     typedef typename Solist::nodeptr_t nodeptr_t;
  79 public:
  80     typedef typename Solist::value_type value_type;
  81     typedef typename Solist::difference_type difference_type;
  82     typedef typename Solist::pointer pointer;
  83     typedef typename Solist::reference reference;
  84
  85     flist_iterator() : my_node_ptr(0) {}
  86     flist_iterator( const flist_iterator<Solist, typename Solist::value_type> &other )
  87         : my_node_ptr(other.my_node_ptr) {}
  88
  89     reference operator*() const { return my_node_ptr->my_element; }
  90     pointer operator->() const { return &**this; }
  91
  92     flist_iterator& operator++() {
  93         my_node_ptr = my_node_ptr->my_next;
  94         return *this;
  95     }
  96
  97     flist_iterator operator++(int) {
  98         flist_iterator tmp = *this;
  99         ++*this;
 100         return tmp;
 101     }
 102
 103 protected:
 104     flist_iterator(nodeptr_t pnode) : my_node_ptr(pnode) {}
 105     nodeptr_t get_node_ptr() const { return my_node_ptr; }
 106
 107     nodeptr_t my_node_ptr;
 108
 109     template<typename M, typename T, typename U>
 110     friend bool operator==( const flist_iterator<M,T> &i, const flist_iterator<M,U> &j );
 111     template<typename M, typename T, typename U>
 112     friend bool operator!=( const flist_iterator<M,T>& i, const flist_iterator<M,U>& j );
 113 };
 114
 115 template<typename Solist, typename T, typename U>
 116 bool operator==( const flist_iterator<Solist,T> &i, const flist_iterator<Solist,U> &j ) {
 117     return i.my_node_ptr == j.my_node_ptr;
 118 }
 119 template<typename Solist, typename T, typename U>
 120 bool operator!=( const flist_iterator<Solist,T>& i, const flist_iterator<Solist,U>& j ) {
 121     return i.my_node_ptr != j.my_node_ptr;
 122 }
 123
 124 // Split-order list iterators, needed to skip dummy elements
 125 template<class Solist, typename Value>
 126 class solist_iterator : public flist_iterator<Solist, Value>
 127 {
 128     typedef flist_iterator<Solist, Value> base_type;
 129     typedef typename Solist::nodeptr_t nodeptr_t;
 130     using base_type::get_node_ptr;
 131     template <typename T, typename Allocator>
 132     friend class split_ordered_list;
 133     template<class M, typename V>
 134     friend class solist_iterator;
 135     template<typename M, typename T, typename U>
 136     friend bool operator==( const solist_iterator<M,T> &i, const solist_iterator<M,U> &j );
 137     template<typename M, typename T, typename U>
 138     friend bool operator!=( const solist_iterator<M,T>& i, const solist_iterator<M,U>& j );
 139
 140     const Solist *my_list_ptr;
 141     solist_iterator(nodeptr_t pnode, const Solist *plist) : base_type(pnode), my_list_ptr(plist) {}
 142
 143 public:
 144     typedef typename Solist::value_type value_type;
 145     typedef typename Solist::difference_type difference_type;
 146     typedef typename Solist::pointer pointer;
 147     typedef typename Solist::reference reference;
 148
 149     solist_iterator() {}
 150     solist_iterator(const solist_iterator<Solist, typename Solist::value_type> &other )
 151         : base_type(other), my_list_ptr(other.my_list_ptr) {}
 152
 153     reference operator*() const {
 154         return this->base_type::operator*();
 155     }
 156
 157     pointer operator->() const {
 158         return (&**this);
 159     }
 160
 161     solist_iterator& operator++() {
 162         do ++(*(base_type *)this);
 163         while (get_node_ptr() != NULL && get_node_ptr()->is_dummy());
 164
 165         return (*this);
 166     }
 167
 168     solist_iterator operator++(int) {
 169         solist_iterator tmp = *this;
 170         do ++*this;
 171         while (get_node_ptr() != NULL && get_node_ptr()->is_dummy());
 172
 173         return (tmp);
 174     }
 175 };
 176
 177 template<typename Solist, typename T, typename U>
 178 bool operator==( const solist_iterator<Solist,T> &i, const solist_iterator<Solist,U> &j ) {
 179     return i.my_node_ptr == j.my_node_ptr && i.my_list_ptr == j.my_list_ptr;
 180 }
 181 template<typename Solist, typename T, typename U>
 182 bool operator!=( const solist_iterator<Solist,T>& i, const solist_iterator<Solist,U>& j ) {
 183     return i.my_node_ptr != j.my_node_ptr || i.my_list_ptr != j.my_list_ptr;
 184 }
 185
 186 // Forward type and class definitions
 187 typedef size_t sokey_t;
 188
 189 // Forward list in which elements are sorted in a split-order
 190 template <typename T, typename Allocator>
 191 class split_ordered_list
 192 {
 193 public:
 194     typedef split_ordered_list<T, Allocator> self_type;
 195     typedef typename Allocator::template rebind<T>::other allocator_type;
 196     struct node;
 197     typedef node *nodeptr_t;
 198
 199     typedef typename allocator_type::size_type size_type;
 200     typedef typename allocator_type::difference_type difference_type;
 201     typedef typename allocator_type::pointer pointer;
 202     typedef typename allocator_type::const_pointer const_pointer;
 203     typedef typename allocator_type::reference reference;
 204     typedef typename allocator_type::const_reference const_reference;
 205     typedef typename allocator_type::value_type value_type;
 206
 207     typedef solist_iterator<self_type, const value_type> const_iterator;
 208     typedef solist_iterator<self_type, value_type> iterator;
 209     typedef flist_iterator<self_type, const value_type> raw_const_iterator;
 210     typedef flist_iterator<self_type, value_type> raw_iterator;
 211
 212     // Node that holds the element in a split-ordered list
 213     struct node : tbb::internal::no_assign
 214     {
 215         // Initialize the node with the given order key
 216         void init(sokey_t order_key) {
 217             my_order_key = order_key;
 218             my_next = NULL;
 219         }
 220
 221         // Return the order key (needed for hashing)
 222         sokey_t get_order_key() const { // TODO: remove
 223             return my_order_key;
 224         }
 225
 226         // Inserts the new element in the list in an atomic fashion
 227         nodeptr_t atomic_set_next(nodeptr_t new_node, nodeptr_t current_node)
 228         {
 229             // Try to change the next pointer on the current element to a new element, only if it still points to the cached next
 230             nodeptr_t exchange_node = (nodeptr_t) __TBB_CompareAndSwapW((void *) &my_next, (uintptr_t)new_node, (uintptr_t)current_node);
 231
 232             if (exchange_node == current_node) // TODO: why this branch?
 233             {
 234                 // Operation succeeded, return the new node
 235                 return new_node;
 236             }
 237             else
 238             {
 239                 // Operation failed, return the "interfering" node
 240                 return exchange_node;
 241             }
 242         }
 243
 244         // Checks if this element in the list is a dummy, order enforcing node. Dummy nodes are used by buckets
 245         // in the hash table to quickly index into the right subsection of the split-ordered list.
 246         bool is_dummy() const {
 247             return (my_order_key & 0x1) == 0;
 248         }
 249
 250
 251         nodeptr_t  my_next;      // Next element in the list
 252         value_type my_element;   // Element storage
 253         sokey_t    my_order_key; // Order key for this element
 254     };
 255
 256     // Allocate a new node with the given order key and value
 257     nodeptr_t create_node(sokey_t order_key, const T &value) {
 258         nodeptr_t pnode = my_node_allocator.allocate(1);
 259
 260         __TBB_TRY {
 261             new(static_cast<void*>(&pnode->my_element)) T(value);
 262             pnode->init(order_key);
 263         } __TBB_CATCH(...) {
 264             my_node_allocator.deallocate(pnode, 1);
 265             __TBB_RETHROW();
 266         }
 267
 268         return (pnode);
 269     }
 270
 271     // Allocate a new node with the given order key; used to allocate dummy nodes
 272     nodeptr_t create_node(sokey_t order_key) {
 273         nodeptr_t pnode = my_node_allocator.allocate(1);
 274
 275         __TBB_TRY {
 276             new(static_cast<void*>(&pnode->my_element)) T();
 277             pnode->init(order_key);
 278         } __TBB_CATCH(...) {
 279             my_node_allocator.deallocate(pnode, 1);
 280             __TBB_RETHROW();
 281         }
 282
 283         return (pnode);
 284     }
 285
 286    split_ordered_list(allocator_type a = allocator_type())
 287        : my_node_allocator(a), my_element_count(0)
 288     {
 289         // Immediately allocate a dummy node with order key of 0. This node
 290         // will always be the head of the list.
 291         my_head = create_node(0);
 292     }
 293
 294     ~split_ordered_list()
 295     {
 296         // Clear the list
 297         clear();
 298
 299         // Remove the head element which is not cleared by clear()
 300         nodeptr_t pnode = my_head;
 301         my_head = NULL;
 302
 303         __TBB_ASSERT(pnode != NULL && pnode->my_next == NULL, "Invalid head list node");
 304
 305         destroy_node(pnode);
 306     }
 307
 308     // Common forward list functions
 309
 310     allocator_type get_allocator() const {
 311         return (my_node_allocator);
 312     }
 313
 314     void clear() {
 315         nodeptr_t pnext;
 316         nodeptr_t pnode = my_head;
 317
 318         __TBB_ASSERT(my_head != NULL, "Invalid head list node");
 319         pnext = pnode->my_next;
 320         pnode->my_next = NULL;
 321         pnode = pnext;
 322
 323         while (pnode != NULL)
 324         {
 325             pnext = pnode->my_next;
 326             destroy_node(pnode);
 327             pnode = pnext;
 328         }
 329
 330         my_element_count = 0;
 331     }
 332
 333     // Returns a first non-dummy element in the SOL
 334     iterator begin() {
 335         return first_real_iterator(raw_begin());
 336     }
 337
 338     // Returns a first non-dummy element in the SOL
 339     const_iterator begin() const {
 340         return first_real_iterator(raw_begin());
 341     }
 342
 343     iterator end() {
 344         return (iterator(0, this));
 345     }
 346
 347     const_iterator end() const {
 348         return (const_iterator(0, this));
 349     }
 350
 351     const_iterator cbegin() const {
 352         return (((const self_type *)this)->begin());
 353     }
 354
 355     const_iterator cend() const {
 356         return (((const self_type *)this)->end());
 357     }
 358
 359     // Checks if the number of elements (non-dummy) is 0
 360     bool empty() const {
 361         return (my_element_count == 0);
 362     }
 363
 364     // Returns the number of non-dummy elements in the list
 365     size_type size() const {
 366         return my_element_count;
 367     }
 368
 369     // Returns the maximum size of the list, determined by the allocator
 370     size_type max_size() const {
 371         return my_node_allocator.max_size();
 372     }
 373
 374     // Swaps 'this' list with the passed in one
 375     void swap(self_type& other)
 376     {
 377         if (this == &other)
 378         {
 379             // Nothing to do
 380             return;
 381         }
 382
 383         std::swap(my_element_count, other.my_element_count);
 384         std::swap(my_head, other.my_head);
 385     }
 386
 387     // Split-order list functions
 388
 389     // Returns a first element in the SOL, which is always a dummy
 390     raw_iterator raw_begin() {
 391         return raw_iterator(my_head);
 392     }
 393
 394     // Returns a first element in the SOL, which is always a dummy
 395     raw_const_iterator raw_begin() const {
 396         return raw_const_iterator(my_head);
 397     }
 398
 399     raw_iterator raw_end() {
 400         return raw_iterator(0);
 401     }
 402
 403     raw_const_iterator raw_end() const {
 404         return raw_const_iterator(0);
 405     }
 406
 407     static sokey_t get_order_key(const raw_const_iterator& it) {
 408         return it.get_node_ptr()->get_order_key();
 409     }
 410
 411     static sokey_t get_safe_order_key(const raw_const_iterator& it) {
 412         if( !it.get_node_ptr() ) return sokey_t(~0U);
 413         return it.get_node_ptr()->get_order_key();
 414     }
 415
 416     // Returns a public iterator version of the internal iterator. Public iterator must not
 417     // be a dummy private iterator.
 418     iterator get_iterator(raw_iterator it) {
 419         __TBB_ASSERT(it.get_node_ptr() == NULL || !it.get_node_ptr()->is_dummy(), "Invalid user node (dummy)");
 420         return iterator(it.get_node_ptr(), this);
 421     }
 422
 423     // Returns a public iterator version of the internal iterator. Public iterator must not
 424     // be a dummy private iterator.
 425     const_iterator get_iterator(raw_const_iterator it) const {
 426         __TBB_ASSERT(it.get_node_ptr() == NULL || !it.get_node_ptr()->is_dummy(), "Invalid user node (dummy)");
 427         return const_iterator(it.get_node_ptr(), this);
 428     }
 429
 430     // Returns a non-const version of the raw_iterator
 431     raw_iterator get_iterator(raw_const_iterator it) {
 432         return raw_iterator(it.get_node_ptr());
 433     }
 434
 435     // Returns a non-const version of the iterator
 436     static iterator get_iterator(const_iterator it) {
 437         return iterator(it.my_node_ptr, it.my_list_ptr);
 438     }
 439
 440     // Returns a public iterator version of a first non-dummy internal iterator at or after
 441     // the passed in internal iterator.
 442     iterator first_real_iterator(raw_iterator it)
 443     {
 444         // Skip all dummy, internal only iterators
 445         while (it != raw_end() && it.get_node_ptr()->is_dummy())
 446             ++it;
 447
 448         return iterator(it.get_node_ptr(), this);
 449     }
 450
 451     // Returns a public iterator version of a first non-dummy internal iterator at or after
 452     // the passed in internal iterator.
 453     const_iterator first_real_iterator(raw_const_iterator it) const
 454     {
 455         // Skip all dummy, internal only iterators
 456         while (it != raw_end() && it.get_node_ptr()->is_dummy())
 457             ++it;
 458
 459         return const_iterator(it.get_node_ptr(), this);
 460     }
 461
 462     // Erase an element using the allocator
 463     void destroy_node(nodeptr_t pnode) {
 464         my_node_allocator.destroy(pnode);
 465         my_node_allocator.deallocate(pnode, 1);
 466     }
 467
 468     // Try to insert a new element in the list. If insert fails, return the node that
 469     // was inserted instead.
 470     nodeptr_t try_insert(nodeptr_t previous, nodeptr_t new_node, nodeptr_t current_node) {
 471         new_node->my_next = current_node;
 472         return previous->atomic_set_next(new_node, current_node);
 473     }
 474
 475     // Insert a new element between passed in iterators
 476     std::pair<iterator, bool> try_insert(raw_iterator it, raw_iterator next, const value_type &value, sokey_t order_key, size_type *new_count)
 477     {
 478         nodeptr_t pnode = create_node(order_key, value);
 479         nodeptr_t inserted_node = try_insert(it.get_node_ptr(), pnode, next.get_node_ptr());
 480
 481         if (inserted_node == pnode)
 482         {
 483             // If the insert succeeded, check that the order is correct and increment the element count
 484             check_range();
 485             *new_count = __TBB_FetchAndAddW((uintptr_t*)&my_element_count, uintptr_t(1));
 486             return std::pair<iterator, bool>(iterator(pnode, this), true);
 487         }
 488         else
 489         {
 490             // If the insert failed (element already there), then delete the new one
 491             destroy_node(pnode);
 492             return std::pair<iterator, bool>(end(), false);
 493         }
 494     }
 495
 496     // Insert a new dummy element, starting search at a parent dummy element
 497     raw_iterator insert_dummy(raw_iterator it, sokey_t order_key)
 498     {
 499         raw_iterator last = raw_end();
 500         raw_iterator where = it;
 501
 502         __TBB_ASSERT(where != last, "Invalid head node");
 503
 504         ++where;
 505
 506         // Create a dummy element up front, even though it may be discarded (due to concurrent insertion)
 507         nodeptr_t dummy_node = create_node(order_key);
 508
 509         for (;;)
 510         {
 511             __TBB_ASSERT(it != last, "Invalid head list node");
 512
 513             // If the head iterator is at the end of the list, or past the point where this dummy
 514             // node needs to be inserted, then try to insert it.
 515             if (where == last || get_order_key(where) > order_key)
 516             {
 517                 __TBB_ASSERT(get_order_key(it) < order_key, "Invalid node order in the list");
 518
 519                 // Try to insert it in the right place
 520                 nodeptr_t inserted_node = try_insert(it.get_node_ptr(), dummy_node, where.get_node_ptr());
 521
 522                 if (inserted_node == dummy_node)
 523                 {
 524                     // Insertion succeeded, check the list for order violations
 525                     check_range();
 526                     return raw_iterator(dummy_node);
 527                 }
 528                 else
 529                 {
 530                     // Insertion failed: either dummy node was inserted by another thread, or
 531                     // a real element was inserted at exactly the same place as dummy node.
 532                     // Proceed with the search from the previous location where order key was
 533                     // known to be larger (note: this is legal only because there is no safe
 534                     // concurrent erase operation supported).
 535                     where = it;
 536                     ++where;
 537                     continue;
 538                 }
 539             }
 540             else if (get_order_key(where) == order_key)
 541             {
 542                 // Another dummy node with the same value found, discard the new one.
 543                 destroy_node(dummy_node);
 544                 return where;
 545             }
 546
 547             // Move the iterator forward
 548             it = where;
 549             ++where;
 550         }
 551
 552     }
 553
 554     // This erase function can handle both real and dummy nodes
 555     void erase_node(raw_iterator previous, raw_const_iterator& where)
 556     {
 557         nodeptr_t pnode = (where++).get_node_ptr();
 558         nodeptr_t prevnode = previous.get_node_ptr();
 559         __TBB_ASSERT(prevnode->my_next == pnode, "Erase must take consecutive iterators");
 560         prevnode->my_next = pnode->my_next;
 561
 562         destroy_node(pnode);
 563     }
 564
 565     // Erase the element (previous node needs to be passed because this is a forward only list)
 566     iterator erase_node(raw_iterator previous, const_iterator where)
 567     {
 568         raw_const_iterator it = where;
 569         erase_node(previous, it);
 570         my_element_count--;
 571
 572         return get_iterator(first_real_iterator(it));
 573     }
 574
 575     // Move all elements from the passed in split-ordered list to this one
 576     void move_all(self_type& source)
 577     {
 578         raw_const_iterator first = source.raw_begin();
 579         raw_const_iterator last = source.raw_end();
 580
 581         if (first == last)
 582             return;
 583
 584         nodeptr_t previous_node = my_head;
 585         raw_const_iterator begin_iterator = first++;
 586
 587         // Move all elements one by one, including dummy ones
 588         for (raw_const_iterator it = first; it != last;)
 589         {
 590             nodeptr_t pnode = it.get_node_ptr();
 591
 592             nodeptr_t dummy_node = pnode->is_dummy() ? create_node(pnode->get_order_key()) : create_node(pnode->get_order_key(), pnode->my_element);
 593             previous_node = try_insert(previous_node, dummy_node, NULL);
 594             __TBB_ASSERT(previous_node != NULL, "Insertion must succeed");
 595             raw_const_iterator where = it++;
 596             source.erase_node(get_iterator(begin_iterator), where);
 597         }
 598         check_range();
 599     }
 600
 601
 602 private:
 603
 604     // Check the list for order violations
 605     void check_range()
 606     {
 607 #if TBB_USE_ASSERT
 608         for (raw_iterator it = raw_begin(); it != raw_end(); ++it)
 609         {
 610             raw_iterator next_iterator = it;
 611             ++next_iterator;
 612
 613             __TBB_ASSERT(next_iterator == end() || next_iterator.get_node_ptr()->get_order_key() >= it.get_node_ptr()->get_order_key(), "!!! List order inconsistency !!!");
 614         }
 615 #endif
 616     }
 617
 618     typename allocator_type::template rebind<node>::other my_node_allocator;  // allocator object for nodes
 619     size_type                                             my_element_count;   // Total item count, not counting dummy nodes
 620     nodeptr_t                                             my_head;            // pointer to head node
 621 };
 622
 623 // Template class for hash compare
 624 template<typename Key, typename Hasher, typename Key_equality>
 625 class hash_compare
 626 {
 627 public:
 628     hash_compare() {}
 629
 630     hash_compare(Hasher a_hasher) : my_hash_object(a_hasher) {}
 631
 632     hash_compare(Hasher a_hasher, Key_equality a_keyeq) : my_hash_object(a_hasher), my_key_compare_object(a_keyeq) {}
 633
 634     size_t operator()(const Key& key) const {
 635         return ((size_t)my_hash_object(key));
 636     }
 637
 638     bool operator()(const Key& key1, const Key& key2) const {
 639         return (!my_key_compare_object(key1, key2));
 640     }
 641
 642     Hasher       my_hash_object;        // The hash object
 643     Key_equality my_key_compare_object; // The equality comparator object
 644 };
 645
 646 #if _MSC_VER
 647 #pragma warning(push)
 648 #pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it (for allow_multimapping)
 649 #endif
 650
 651 template <typename Traits>
 652 class concurrent_unordered_base : public Traits
 653 {
 654 protected:
 655     // Type definitions
 656     typedef concurrent_unordered_base<Traits> self_type;
 657     typedef typename Traits::value_type value_type;
 658     typedef typename Traits::key_type key_type;
 659     typedef typename Traits::hash_compare hash_compare;
 660     typedef typename Traits::value_compare value_compare;
 661     typedef typename Traits::allocator_type allocator_type;
 662     typedef typename allocator_type::pointer pointer;
 663     typedef typename allocator_type::const_pointer const_pointer;
 664     typedef typename allocator_type::reference reference;
 665     typedef typename allocator_type::const_reference const_reference;
 666     typedef typename allocator_type::size_type size_type;
 667     typedef typename allocator_type::difference_type difference_type;
 668     typedef split_ordered_list<value_type, typename Traits::allocator_type> solist_t;
 669     typedef typename solist_t::nodeptr_t nodeptr_t;
 670     // Iterators that walk the entire split-order list, including dummy nodes
 671     typedef typename solist_t::raw_iterator raw_iterator;
 672     typedef typename solist_t::raw_const_iterator raw_const_iterator;
 673     typedef typename solist_t::iterator iterator; // TODO: restore const iterator for unordered_sets
 674     typedef typename solist_t::const_iterator const_iterator;
 675     typedef iterator local_iterator;
 676     typedef const_iterator const_local_iterator;
 677     using Traits::my_hash_compare;
 678     using Traits::get_key;
 679     using Traits::allow_multimapping;
 680
 681 private:
 682     typedef std::pair<iterator, iterator> pairii_t;
 683     typedef std::pair<const_iterator, const_iterator> paircc_t;
 684
 685     static size_type const pointers_per_table = sizeof(size_type) * 8;              // One bucket segment per bit
 686     static const size_type initial_bucket_number = 8;                               // Initial number of buckets
 687     static const size_type initial_bucket_load = 4;                                // Initial maximum number of elements per bucket
 688
 689 protected:
 690     // Constructors/Destructors
 691     concurrent_unordered_base(size_type n_of_buckets = initial_bucket_number,
 692         const hash_compare& hc = hash_compare(), const allocator_type& a = allocator_type())
 693         : Traits(hc), my_solist(a),
 694           my_allocator(a), my_maximum_bucket_size((float) initial_bucket_load)
 695     {
 696         if( n_of_buckets == 0) ++n_of_buckets;
 697         my_number_of_buckets = 1<<__TBB_Log2((uintptr_t)n_of_buckets*2-1); // round up to power of 2
 698         internal_init();
 699     }
 700
 701     concurrent_unordered_base(const concurrent_unordered_base& right, const allocator_type& a)
 702         : Traits(right.my_hash_compare), my_solist(a), my_allocator(a)
 703     {
 704         internal_init();
 705         internal_copy(right);
 706     }
 707
 708     concurrent_unordered_base(const concurrent_unordered_base& right)
 709         : Traits(right.my_hash_compare), my_solist(right.get_allocator()), my_allocator(right.get_allocator())
 710     {
 711         internal_init();
 712         internal_copy(right);
 713     }
 714
 715     concurrent_unordered_base& operator=(const concurrent_unordered_base& right) {
 716         if (this != &right)
 717             internal_copy(right);
 718         return (*this);
 719     }
 720
 721     ~concurrent_unordered_base() {
 722         // Delete all node segments
 723         internal_clear();
 724     }
 725
 726 public:
 727     allocator_type get_allocator() const {
 728         return my_solist.get_allocator();
 729     }
 730
 731     // Size and capacity function
 732     bool empty() const {
 733         return my_solist.empty();
 734     }
 735
 736     size_type size() const {
 737         return my_solist.size();
 738     }
 739
 740     size_type max_size() const {
 741         return my_solist.max_size();
 742     }
 743
 744     // Iterators
 745     iterator begin() {
 746         return my_solist.begin();
 747     }
 748
 749     const_iterator begin() const {
 750         return my_solist.begin();
 751     }
 752
 753     iterator end() {
 754         return my_solist.end();
 755     }
 756
 757     const_iterator end() const {
 758         return my_solist.end();
 759     }
 760
 761     const_iterator cbegin() const {
 762         return my_solist.cbegin();
 763     }
 764
 765     const_iterator cend() const {
 766         return my_solist.cend();
 767     }
 768
 769     // Parallel traversal support
 770     class const_range_type : tbb::internal::no_assign {
 771         const concurrent_unordered_base &my_table;
 772         raw_const_iterator my_begin_node;
 773         raw_const_iterator my_end_node;
 774         mutable raw_const_iterator my_midpoint_node;
 775     public:
 776         //! Type for size of a range
 777         typedef typename concurrent_unordered_base::size_type size_type;
 778         typedef typename concurrent_unordered_base::value_type value_type;
 779         typedef typename concurrent_unordered_base::reference reference;
 780         typedef typename concurrent_unordered_base::difference_type difference_type;
 781         typedef typename concurrent_unordered_base::const_iterator iterator;
 782
 783         //! True if range is empty.
 784         bool empty() const {return my_begin_node == my_end_node;}
 785
 786         //! True if range can be partitioned into two subranges.
 787         bool is_divisible() const {
 788             return my_midpoint_node != my_end_node;
 789         }
 790         //! Split range.
 791         const_range_type( const_range_type &r, split ) :
 792             my_table(r.my_table), my_end_node(r.my_end_node)
 793         {
 794             r.my_end_node = my_begin_node = r.my_midpoint_node;
 795             __TBB_ASSERT( !empty(), "Splitting despite the range is not divisible" );
 796             __TBB_ASSERT( !r.empty(), "Splitting despite the range is not divisible" );
 797             set_midpoint();
 798             r.set_midpoint();
 799         }
 800         //! Init range with container and grainsize specified
 801         const_range_type( const concurrent_unordered_base &a_table ) :
 802             my_table(a_table), my_begin_node(a_table.my_solist.begin()),
 803             my_end_node(a_table.my_solist.end())
 804         {
 805             set_midpoint();
 806         }
 807         iterator begin() const { return my_table.my_solist.get_iterator(my_begin_node); }
 808         iterator end() const { return my_table.my_solist.get_iterator(my_end_node); }
 809         //! The grain size for this range.
 810         size_type grainsize() const { return 1; }
 811
 812         //! Set my_midpoint_node to point approximately half way between my_begin_node and my_end_node.
 813         void set_midpoint() const {
 814             if( my_begin_node == my_end_node ) // not divisible
 815                 my_midpoint_node = my_end_node;
 816             else {
 817                 sokey_t begin_key = solist_t::get_safe_order_key(my_begin_node);
 818                 sokey_t end_key = solist_t::get_safe_order_key(my_end_node);
 819                 size_t mid_bucket = __TBB_ReverseBits( begin_key + (end_key-begin_key)/2 ) % my_table.my_number_of_buckets;
 820                 while ( !my_table.is_initialized(mid_bucket) ) mid_bucket = my_table.get_parent(mid_bucket);
 821                 my_midpoint_node = my_table.my_solist.first_real_iterator(my_table.get_bucket( mid_bucket ));
 822                 if( my_midpoint_node == my_begin_node )
 823                     my_midpoint_node = my_end_node;
 824 #if TBB_USE_ASSERT
 825                 else {
 826                     sokey_t mid_key = solist_t::get_safe_order_key(my_midpoint_node);
 827                     __TBB_ASSERT( begin_key < mid_key, "my_begin_node is after my_midpoint_node" );
 828                     __TBB_ASSERT( mid_key <= end_key, "my_midpoint_node is after my_end_node" );
 829                 }
 830 #endif // TBB_USE_ASSERT
 831             }
 832         }
 833     };
 834
 835     class range_type : public const_range_type {
 836     public:
 837         typedef typename concurrent_unordered_base::iterator iterator;
 838         //! Split range.
 839         range_type( range_type &r, split ) : const_range_type( r, split() ) {}
 840         //! Init range with container and grainsize specified
 841         range_type( const concurrent_unordered_base &a_table ) : const_range_type(a_table) {}
 842
 843         iterator begin() const { return solist_t::get_iterator( const_range_type::begin() ); }
 844         iterator end() const { return solist_t::get_iterator( const_range_type::end() ); }
 845     };
 846
 847     range_type range() {
 848         return range_type( *this );
 849     }
 850
 851     const_range_type range() const {
 852         return const_range_type( *this );
 853     }
 854
 855     // Modifiers
 856     std::pair<iterator, bool> insert(const value_type& value) {
 857         return internal_insert(value);
 858     }
 859
 860     iterator insert(const_iterator, const value_type& value) {
 861         // Ignore hint
 862         return insert(value).first;
 863     }
 864
 865     template<class Iterator>
 866     void insert(Iterator first, Iterator last) {
 867         for (Iterator it = first; it != last; ++it)
 868             insert(*it);
 869     }
 870
 871     iterator unsafe_erase(const_iterator where) {
 872         return internal_erase(where);
 873     }
 874
 875     iterator unsafe_erase(const_iterator first, const_iterator last) {
 876         while (first != last)
 877             unsafe_erase(first++);
 878         return my_solist.get_iterator(first);
 879     }
 880
 881     size_type unsafe_erase(const key_type& key) {
 882         pairii_t where = equal_range(key);
 883         size_type item_count = internal_distance(where.first, where.second);
 884         unsafe_erase(where.first, where.second);
 885         return item_count;
 886     }
 887
 888     void swap(concurrent_unordered_base& right) {
 889         if (this != &right) {
 890             std::swap(my_hash_compare, right.my_hash_compare); // TODO: check what ADL meant here
 891             my_solist.swap(right.my_solist);
 892             internal_swap_buckets(right);
 893             std::swap(my_number_of_buckets, right.my_number_of_buckets);
 894             std::swap(my_maximum_bucket_size, right.my_maximum_bucket_size);
 895         }
 896     }
 897
 898     // Observers
 899     void clear() {
 900         // Clear list
 901         my_solist.clear();
 902
 903         // Clear buckets
 904         internal_clear();
 905
 906         // Initialize bucket 0
 907         __TBB_ASSERT(my_buckets[0] == NULL, NULL);
 908         raw_iterator dummy_node = my_solist.raw_begin();
 909         set_bucket(0, dummy_node);
 910     }
 911
 912     // Lookup
 913     iterator find(const key_type& key) {
 914         return internal_find(key);
 915     }
 916
 917     const_iterator find(const key_type& key) const {
 918         return const_cast<self_type*>(this)->internal_find(key);
 919     }
 920
 921     size_type count(const key_type& key) const {
 922         if(allow_multimapping) {
 923             paircc_t answer = equal_range(key);
 924             size_type item_count = internal_distance(answer.first, answer.second);
 925             return item_count;
 926         } else {
 927             return const_cast<self_type*>(this)->internal_find(key) == end()?0:1;
 928         }
 929     }
 930
 931     std::pair<iterator, iterator> equal_range(const key_type& key) {
 932         return internal_equal_range(key);
 933     }
 934
 935     std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
 936         return const_cast<self_type*>(this)->internal_equal_range(key);
 937     }
 938
 939     // Bucket interface - for debugging
 940     size_type unsafe_bucket_count() const {
 941         return my_number_of_buckets;
 942     }
 943
 944     size_type unsafe_max_bucket_count() const {
 945         return segment_size(pointers_per_table-1);
 946     }
 947
 948     size_type unsafe_bucket_size(size_type bucket) {
 949         size_type item_count = 0;
 950         if (is_initialized(bucket)) {
 951             raw_iterator it = get_bucket(bucket);
 952             ++it;
 953             for (; it != my_solist.raw_end() && !it.get_node_ptr()->is_dummy(); ++it)
 954                 ++item_count;
 955         }
 956         return item_count;
 957     }
 958
 959     size_type unsafe_bucket(const key_type& key) const {
 960         sokey_t order_key = (sokey_t) my_hash_compare(key);
 961         size_type bucket = order_key % my_number_of_buckets;
 962         return bucket;
 963     }
 964
 965     // If the bucket is initialized, return a first non-dummy element in it
 966     local_iterator unsafe_begin(size_type bucket) {
 967         if (!is_initialized(bucket))
 968             return end();
 969
 970         raw_iterator it = get_bucket(bucket);
 971         return my_solist.first_real_iterator(it);
 972     }
 973
 974     // If the bucket is initialized, return a first non-dummy element in it
 975     const_local_iterator unsafe_begin(size_type bucket) const
 976     {
 977         if (!is_initialized(bucket))
 978             return end();
 979
 980         raw_const_iterator it = get_bucket(bucket);
 981         return my_solist.first_real_iterator(it);
 982     }
 983
 984     // @REVIEW: Takes O(n)
 985     // Returns the iterator after the last non-dummy element in the bucket
 986     local_iterator unsafe_end(size_type bucket)
 987     {
 988         if (!is_initialized(bucket))
 989             return end();
 990
 991         raw_iterator it = get_bucket(bucket);
 992
 993         // Find the end of the bucket, denoted by the dummy element
 994         do ++it;
 995         while(it != my_solist.raw_end() && !it.get_node_ptr()->is_dummy());
 996
 997         // Return the first real element past the end of the bucket
 998         return my_solist.first_real_iterator(it);
 999     }
1000
1001     // @REVIEW: Takes O(n)
1002     // Returns the iterator after the last non-dummy element in the bucket
1003     const_local_iterator unsafe_end(size_type bucket) const
1004     {
1005         if (!is_initialized(bucket))
1006             return end();
1007
1008         raw_const_iterator it = get_bucket(bucket);
1009
1010         // Find the end of the bucket, denoted by the dummy element
1011         do ++it;
1012         while(it != my_solist.raw_end() && !it.get_node_ptr()->is_dummy());
1013
1014         // Return the first real element past the end of the bucket
1015         return my_solist.first_real_iterator(it);
1016     }
1017
1018     const_local_iterator unsafe_cbegin(size_type bucket) const {
1019         return ((const self_type *) this)->begin();
1020     }
1021
1022     const_local_iterator unsafe_cend(size_type bucket) const {
1023         return ((const self_type *) this)->end();
1024     }
1025
1026     // Hash policy
1027     float load_factor() const {
1028         return (float) size() / (float) unsafe_bucket_count();
1029     }
1030
1031     float max_load_factor() const {
1032         return my_maximum_bucket_size;
1033     }
1034
1035     void max_load_factor(float newmax) {
1036         if (newmax != newmax || newmax < 0)
1037             tbb::internal::throw_exception(tbb::internal::eid_invalid_load_factor);
1038         my_maximum_bucket_size = newmax;
1039     }
1040
1041     // This function is a noop, because the underlying split-ordered list
1042     // is already sorted, so an increase in the bucket number will be
1043     // reflected next time this bucket is touched.
1044     void rehash(size_type buckets) {
1045         size_type current_buckets = my_number_of_buckets;
1046         if (current_buckets >= buckets)
1047             return;
1048         my_number_of_buckets = 1<<__TBB_Log2((uintptr_t)buckets*2-1); // round up to power of 2
1049     }
1050
1051 private:
1052
1053     // Initialize the hash and keep the first bucket open
1054     void internal_init() {
1055         // Allocate an array of segment pointers
1056         memset(my_buckets, 0, pointers_per_table * sizeof(void *));
1057
1058         // Initialize bucket 0
1059         raw_iterator dummy_node = my_solist.raw_begin();
1060         set_bucket(0, dummy_node);
1061     }
1062
1063     void internal_clear() {
1064         for (size_type index = 0; index < pointers_per_table; ++index) {
1065             if (my_buckets[index] != NULL) {
1066                 size_type sz = segment_size(index);
1067                 for (size_type index2 = 0; index2 < sz; ++index2)
1068                     my_allocator.destroy(&my_buckets[index][index2]);
1069                 my_allocator.deallocate(my_buckets[index], sz);
1070                 my_buckets[index] = 0;
1071             }
1072         }
1073     }
1074
1075     void internal_copy(const self_type& right) {
1076         clear();
1077
1078         my_maximum_bucket_size = right.my_maximum_bucket_size;
1079         my_number_of_buckets = right.my_number_of_buckets;
1080
1081         __TBB_TRY {
1082             insert(right.begin(), right.end());
1083             my_hash_compare = right.my_hash_compare;
1084         } __TBB_CATCH(...) {
1085             my_solist.clear();
1086             __TBB_RETHROW();
1087         }
1088     }
1089
1090     void internal_swap_buckets(concurrent_unordered_base& right)
1091     {
1092         // Swap all node segments
1093         for (size_type index = 0; index < pointers_per_table; ++index)
1094         {
1095             raw_iterator * iterator_pointer = my_buckets[index];
1096             my_buckets[index] = right.my_buckets[index];
1097             right.my_buckets[index] = iterator_pointer;
1098         }
1099     }
1100
1101     // Hash APIs
1102     size_type internal_distance(const_iterator first, const_iterator last) const
1103     {
1104         size_type num = 0;
1105
1106         for (const_iterator it = first; it != last; ++it)
1107             ++num;
1108
1109         return num;
1110     }
1111
1112     // Insert an element in the hash given its value
1113     std::pair<iterator, bool> internal_insert(const value_type& value)
1114     {
1115         sokey_t order_key = (sokey_t) my_hash_compare(get_key(value));
1116         size_type bucket = order_key % my_number_of_buckets;
1117
1118         // If bucket is empty, initialize it first
1119         if (!is_initialized(bucket))
1120             init_bucket(bucket);
1121
1122         size_type new_count;
1123         order_key = split_order_key_regular(order_key);
1124         raw_iterator it = get_bucket(bucket);
1125         raw_iterator last = my_solist.raw_end();
1126         raw_iterator where = it;
1127
1128         __TBB_ASSERT(where != last, "Invalid head node");
1129
1130         // First node is a dummy node
1131         ++where;
1132
1133         for (;;)
1134         {
1135             if (where == last || solist_t::get_order_key(where) > order_key)
1136             {
1137                 // Try to insert it in the right place
1138                 std::pair<iterator, bool> result = my_solist.try_insert(it, where, value, order_key, &new_count);
1139
1140                 if (result.second)
1141                 {
1142                     // Insertion succeeded, adjust the table size, if needed
1143                     adjust_table_size(new_count, my_number_of_buckets);
1144                     return result;
1145                 }
1146                 else
1147                 {
1148                     // Insertion failed: either the same node was inserted by another thread, or
1149                     // another element was inserted at exactly the same place as this node.
1150                     // Proceed with the search from the previous location where order key was
1151                     // known to be larger (note: this is legal only because there is no safe
1152                     // concurrent erase operation supported).
1153                     where = it;
1154                     ++where;
1155                     continue;
1156                 }
1157             }
1158             else if (!allow_multimapping && solist_t::get_order_key(where) == order_key && my_hash_compare(get_key(*where), get_key(value)) == 0)
1159             {
1160                 // Element already in the list, return it
1161                 return std::pair<iterator, bool>(my_solist.get_iterator(where), false);
1162             }
1163
1164             // Move the iterator forward
1165             it = where;
1166             ++where;
1167         }
1168     }
1169
1170     // Find the element in the split-ordered list
1171     iterator internal_find(const key_type& key)
1172     {
1173         sokey_t order_key = (sokey_t) my_hash_compare(key);
1174         size_type bucket = order_key % my_number_of_buckets;
1175
1176         // If bucket is empty, initialize it first
1177         if (!is_initialized(bucket))
1178             init_bucket(bucket);
1179
1180         order_key = split_order_key_regular(order_key);
1181         raw_iterator last = my_solist.raw_end();
1182
1183         for (raw_iterator it = get_bucket(bucket); it != last; ++it)
1184         {
1185             if (solist_t::get_order_key(it) > order_key)
1186             {
1187                 // If the order key is smaller than the current order key, the element
1188                 // is not in the hash.
1189                 return end();
1190             }
1191             else if (solist_t::get_order_key(it) == order_key)
1192             {
1193                 // The fact that order keys match does not mean that the element is found.
1194                 // Key function comparison has to be performed to check whether this is the
1195                 // right element. If not, keep searching while order key is the same.
1196                 if (!my_hash_compare(get_key(*it), key))
1197                     return my_solist.get_iterator(it);
1198             }
1199         }
1200
1201         return end();
1202     }
1203
1204     // Erase an element from the list. This is not a concurrency safe function.
1205     iterator internal_erase(const_iterator it)
1206     {
1207         key_type key = get_key(*it);
1208         sokey_t order_key = (sokey_t) my_hash_compare(key);
1209         size_type bucket = order_key % my_number_of_buckets;
1210
1211         // If bucket is empty, initialize it first
1212         if (!is_initialized(bucket))
1213             init_bucket(bucket);
1214
1215         order_key = split_order_key_regular(order_key);
1216
1217         raw_iterator previous = get_bucket(bucket);
1218         raw_iterator last = my_solist.raw_end();
1219         raw_iterator where = previous;
1220
1221         __TBB_ASSERT(where != last, "Invalid head node");
1222
1223         // First node is a dummy node
1224         ++where;
1225
1226         for (;;) {
1227             if (where == last)
1228                 return end();
1229             else if (my_solist.get_iterator(where) == it)
1230                 return my_solist.erase_node(previous, it);
1231
1232             // Move the iterator forward
1233             previous = where;
1234             ++where;
1235         }
1236     }
1237
1238     // Return the [begin, end) pair of iterators with the same key values.
1239     // This operation makes sense only if mapping is many-to-one.
1240     pairii_t internal_equal_range(const key_type& key)
1241     {
1242         sokey_t order_key = (sokey_t) my_hash_compare(key);
1243         size_type bucket = order_key % my_number_of_buckets;
1244
1245         // If bucket is empty, initialize it first
1246         if (!is_initialized(bucket))
1247             init_bucket(bucket);
1248
1249         order_key = split_order_key_regular(order_key);
1250         raw_iterator end_it = my_solist.raw_end();
1251
1252         for (raw_iterator it = get_bucket(bucket); it != end_it; ++it)
1253         {
1254             if (solist_t::get_order_key(it) > order_key)
1255             {
1256                 // There is no element with the given key
1257                 return pairii_t(end(), end());
1258             }
1259             else if (solist_t::get_order_key(it) == order_key && !my_hash_compare(get_key(*it), key))
1260             {
1261                 iterator first = my_solist.get_iterator(it);
1262                 iterator last = first;
1263                 do ++last; while( allow_multimapping && last != end() && !my_hash_compare(get_key(*last), key) );
1264                 return pairii_t(first, last);
1265             }
1266         }
1267
1268         return pairii_t(end(), end());
1269     }
1270
1271     // Bucket APIs
1272     void init_bucket(size_type bucket)
1273     {
1274         // Bucket 0 has no parent.
1275         __TBB_ASSERT( bucket != 0, "The first bucket must always be initialized");
1276
1277         size_type parent_bucket = get_parent(bucket);
1278
1279         // All parent_bucket buckets have to be initialized before this bucket is
1280         if (!is_initialized(parent_bucket))
1281             init_bucket(parent_bucket);
1282
1283         raw_iterator parent = get_bucket(parent_bucket);
1284
1285         // Create a dummy first node in this bucket
1286         raw_iterator dummy_node = my_solist.insert_dummy(parent, split_order_key_dummy(bucket));
1287         set_bucket(bucket, dummy_node);
1288     }
1289
1290     void adjust_table_size(size_type total_elements, size_type current_size)
1291     {
1292         // Grow the table by a factor of 2 if possible and needed
1293         if ( ((float) total_elements / (float) current_size) > my_maximum_bucket_size )
1294         {
1295             // Double the size of the hash only if size has not changed inbetween loads
1296             __TBB_CompareAndSwapW((uintptr_t*)&my_number_of_buckets, uintptr_t(2u*current_size), uintptr_t(current_size) );
1297             //Simple "my_number_of_buckets.compare_and_swap( current_size<<1, current_size );" does not work for VC8
1298             //due to overzealous compiler warnings in /Wp64 mode
1299         }
1300     }
1301
1302     size_type get_parent(size_type bucket) const
1303     {
1304         // Unsets bucket's most significant turned-on bit
1305         size_type msb = __TBB_Log2((uintptr_t)bucket);
1306         return bucket & ~(size_type(1) << msb);
1307     }
1308
1309
1310     // Dynamic sized array (segments)
1311     //! @return segment index of given index in the array
1312     static size_type segment_index_of( size_type index ) {
1313         return size_type( __TBB_Log2( uintptr_t(index|1) ) );
1314     }
1315
1316     //! @return the first array index of given segment
1317     static size_type segment_base( size_type k ) {
1318         return (size_type(1)<<k & ~size_type(1));
1319     }
1320
1321     //! @return segment size
1322     static size_type segment_size( size_type k ) {
1323         return k? size_type(1)<<k : 2;
1324     }
1325
1326     raw_iterator get_bucket(size_type bucket) const {
1327         size_type segment = segment_index_of(bucket);
1328         bucket -= segment_base(segment);
1329         __TBB_ASSERT( my_buckets[segment], "bucket must be in an allocated segment" );
1330         return my_buckets[segment][bucket];
1331     }
1332
1333     void set_bucket(size_type bucket, raw_iterator dummy_head) {
1334         size_type segment = segment_index_of(bucket);
1335         bucket -= segment_base(segment);
1336
1337         if (my_buckets[segment] == NULL) {
1338             size_type sz = segment_size(segment);
1339             raw_iterator * new_segment = my_allocator.allocate(sz);
1340             std::memset(new_segment, 0, sz*sizeof(raw_iterator));
1341
1342             if (__TBB_CompareAndSwapW((void *) &my_buckets[segment], (uintptr_t)new_segment, 0) != 0)
1343                 my_allocator.deallocate(new_segment, sz);
1344         }
1345
1346         my_buckets[segment][bucket] = dummy_head;
1347     }
1348
1349     bool is_initialized(size_type bucket) const {
1350         size_type segment = segment_index_of(bucket);
1351         bucket -= segment_base(segment);
1352
1353         if (my_buckets[segment] == NULL)
1354             return false;
1355
1356         raw_iterator it = my_buckets[segment][bucket];
1357         return (it.get_node_ptr() != NULL);
1358     }
1359
1360     // Utilities for keys
1361
1362     // A regular order key has its original hash value reversed and the last bit set
1363     sokey_t split_order_key_regular(sokey_t order_key) const {
1364         return __TBB_ReverseBits(order_key) | 0x1;
1365     }
1366
1367     // A dummy order key has its original hash value reversed and the last bit unset
1368     sokey_t split_order_key_dummy(sokey_t order_key) const {
1369         return __TBB_ReverseBits(order_key) & ~(0x1);
1370     }
1371
1372     // Shared variables
1373     atomic<size_type>                                             my_number_of_buckets;       // Current table size
1374     solist_t                                                      my_solist;                  // List where all the elements are kept
1375     typename allocator_type::template rebind<raw_iterator>::other my_allocator;               // Allocator object for segments
1376     float                                                         my_maximum_bucket_size;     // Maximum size of the bucket
1377     atomic<raw_iterator*>                                         my_buckets[pointers_per_table]; // The segment table
1378 };
1379 #if _MSC_VER
1380 #pragma warning(pop) // warning 4127 -- while (true) has a constant expression in it
1381 #endif
1382
1383 //! Hash multiplier
1384 static const size_t hash_multiplier = sizeof(size_t)==4? 2654435769U : 11400714819323198485ULL;
1385 } // namespace internal
1386 //! @endcond
1387 //! Hasher functions
1388 template<typename T>
1389 inline size_t tbb_hasher( const T& t ) {
1390     return static_cast<size_t>( t ) * internal::hash_multiplier;
1391 }
1392 template<typename P>
1393 inline size_t tbb_hasher( P* ptr ) {
1394     size_t const h = reinterpret_cast<size_t>( ptr );
1395     return (h >> 3) ^ h;
1396 }
1397 template<typename E, typename S, typename A>
1398 inline size_t tbb_hasher( const std::basic_string<E,S,A>& s ) {
1399     size_t h = 0;
1400     for( const E* c = s.c_str(); *c; ++c )
1401         h = static_cast<size_t>(*c) ^ (h * internal::hash_multiplier);
1402     return h;
1403 }
1404 template<typename F, typename S>
1405 inline size_t tbb_hasher( const std::pair<F,S>& p ) {
1406     return tbb_hasher(p.first) ^ tbb_hasher(p.second);
1407 }
1408 } // namespace interface5
1409 using interface5::tbb_hasher;
1410
1411
1412 // Template class for hash compare
1413 template<typename Key>
1414 class tbb_hash
1415 {
1416 public:
1417     tbb_hash() {}
1418
1419     size_t operator()(const Key& key) const
1420     {
1421         return tbb_hasher(key);
1422     }
1423 };
1424
1425 } // namespace tbb
1426 #endif// __TBB_concurrent_unordered_internal_H