cds/intrusive/impl/multilevel_hashset.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
   4 #define CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
   5
   6 #include <functional>   // std::ref
   7 #include <iterator>     // std::iterator_traits
   8
   9 #include <cds/intrusive/details/multilevel_hashset_base.h>
  10 #include <cds/details/allocator.h>
  11
  12 namespace cds { namespace intrusive {
  13     /// Intrusive hash set based on multi-level array
  14     /** @ingroup cds_intrusive_map
  15         @anchor cds_intrusive_MultilevelHashSet_hp
  16
  17         Source:
  18         - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
  19                  Wait-free Extensible Hash Maps"
  20
  21         [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
  22         a global resize, the process of redistributing the elements in a hash map that occurs when adding new
  23         buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
  24         threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
  25         and redistributing the elements. \p %MultilevelHashSet implementation avoids global resizes through new array
  26         allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
  27         which facilitates concurrent operations.
  28
  29         The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
  30         which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
  31         It is important to note that the perfect hash function required by our hash map is trivial to realize as
  32         any hash function that permutes the bits of the key is suitable. This is possible because of our approach
  33         to the hash function; we require that it produces hash values that are equal in size to that of the key.
  34         We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
  35         are not provided for in the standard semantics of a hash map.
  36
  37         \p %MultiLevelHashSet is a multi-level array which has a structure similar to a tree:
  38         @image html multilevel_hashset.png
  39         The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node.
  40         A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated\r
  41         with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.\r
  42         A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)\r
  43         of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;\r
  44         any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds\r
  45         an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark\r
  46         on the second-least significant bit.\r
  47 \r
  48         \p %MultiLevelHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array\r
  49         called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;\r
  50         a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.\r
  51         The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.\r
  52         We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which\r
  53         we need to operate; this is initially one, because of \p head.\r
  54 \r
  55         That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit\r
  56         string</b> and rehash incrementally.\r
  57 \r
  58         @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:\r
  59         - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.\r
  60           Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,\r
  61           <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a> \r
  62           or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which\r
  63           converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.\r
  64         - \p %MultiLevelHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,\r
  65           have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashSet does not maintain the key,\r
  66           it maintains its fixed-size hash value.\r
  67 \r
  68         The set supports @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional thread-safe iterators".\r
  69 \r
  70         Template parameters:\r
  71         - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"\r
  72         - \p T - a value type to be stored in the set\r
  73         - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.\r
  74             \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor" \r
  75             to hash value of \p T. The set algorithm does not calculate that hash value.\r
  76 \r
  77         There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include:
  78         - <tt><cds/intrusive/multilevel_hashset_hp.h></tt> for \p gc::HP garbage collector
  79         - <tt><cds/intrusive/multilevel_hashset_dhp.h></tt> for \p gc::DHP garbage collector
  80         - <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization
  81             has a slightly different interface.
  82     */
  83     template <
  84         class GC
  85         ,typename T
  86 #ifdef CDS_DOXYGEN_INVOKED
  87        ,typename Traits = multilevel_hashset::traits
  88 #else
  89        ,typename Traits
  90 #endif
  91     >
  92     class MultiLevelHashSet
  93     {
  94     public:
  95         typedef GC      gc;         ///< Garbage collector
  96         typedef T       value_type; ///< type of value stored in the set
  97         typedef Traits  traits;     ///< Traits template parameter, see \p multilevel_hashset::traits
  98
  99         typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
 100         static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified" );
 101
 102         /// Hash type deduced from \p hash_accessor return type
 103         typedef typename std::decay<
 104             typename std::remove_reference<
 105                 decltype( hash_accessor()( std::declval<T>()) )
 106             >::type
 107         >::type hash_type;
 108         //typedef typename std::result_of< hash_accessor( std::declval<T>()) >::type hash_type;
 109         static_assert( !std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value" );
 110
 111         typedef typename traits::disposer disposer; ///< data node disposer
 112
 113 #   ifdef CDS_DOXYGEN_INVOKED
 114         typedef implementation_defined hash_comparator  ;    ///< hash compare functor based on opt::compare and opt::less option setter
 115 #   else
 116         typedef typename cds::opt::details::make_comparator_from<
 117             hash_type,
 118             traits,
 119             multilevel_hashset::bitwise_compare< hash_type >
 120         >::type hash_comparator;
 121 #   endif
 122
 123         typedef typename traits::item_counter   item_counter;   ///< Item counter type
 124         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
 125         typedef typename traits::memory_model   memory_model;   ///< Memory model
 126         typedef typename traits::back_off       back_off;       ///< Backoff strategy
 127         typedef typename traits::stat           stat;           ///< Internal statistics type
 128
 129         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 130
 131         /// Count of hazard pointers required
 132         static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 1;
 133
 134         /// Node marked poiter
 135         typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
 136         /// Array node element
 137         typedef atomics::atomic< node_ptr > atomic_node_ptr;
 138
 139     protected:
 140         //@cond
 141         enum node_flags {
 142             flag_array_converting = 1,   ///< the cell is converting from data node to an array node
 143             flag_array_node = 2          ///< the cell is a pointer to an array node
 144         };
 145
 146         struct array_node {
 147             array_node * const  pParent;    ///< parent array node
 148             size_t const        idxParent;  ///< index in parent array node
 149             atomic_node_ptr     nodes[1];   ///< node array
 150
 151             array_node( array_node * parent, size_t idx )
 152                 : pParent( parent )
 153                 , idxParent( idx )
 154             {}
 155
 156             array_node() = delete;
 157             array_node( array_node const&) = delete;
 158             array_node( array_node&& ) = delete;
 159         };
 160
 161         typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
 162
 163         typedef multilevel_hashset::details::hash_splitter< hash_type > hash_splitter;
 164
 165         struct metrics {
 166             size_t  head_node_size;     // power-of-two
 167             size_t  head_node_size_log; // log2( head_node_size )
 168             size_t  array_node_size;    // power-of-two
 169             size_t  array_node_size_log;// log2( array_node_size )
 170         };
 171         //@endcond
 172
 173     protected:
 174         //@cond
 175         /// Bidirectional iterator class
 176         template <bool IsConst>
 177         class bidirectional_iterator
 178         {
 179             friend class MultiLevelHashSet;
 180
 181             array_node *        m_pNode;    ///< current array node
 182             size_t              m_idx;      ///< current position in m_pNode
 183             typename gc::Guard  m_guard;    ///< HP guard
 184             MultiLevelHashSet const*  m_set;    ///< Hash set
 185
 186         public:
 187             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 188             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 189
 190         public:
 191             bidirectional_iterator() CDS_NOEXCEPT
 192                 : m_pNode( nullptr )
 193                 , m_idx( 0 )
 194                 , m_set( nullptr )
 195             {}
 196
 197             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 198                 : m_pNode( rhs.m_pNode )
 199                 , m_idx( rhs.m_idx )
 200                 , m_set( rhs.m_set )
 201             {
 202                 m_guard.copy( rhs.m_guard );
 203             }
 204
 205             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
 206             {
 207                 m_pNode = rhs.m_pNode;
 208                 m_idx = rhs.m_idx;
 209                 m_set = rhs.m_set;
 210                 m_guard.copy( rhs.m_guard );
 211                 return *this;
 212             }
 213
 214             bidirectional_iterator& operator++()
 215             {
 216                 forward();
 217                 return *this;
 218             }
 219
 220             bidirectional_iterator& operator--()
 221             {
 222                 backward();
 223                 return *this;
 224             }
 225
 226             value_ptr operator ->() const CDS_NOEXCEPT
 227             {
 228                 return pointer();
 229             }
 230
 231             value_ref operator *() const CDS_NOEXCEPT
 232             {
 233                 value_ptr p = pointer();
 234                 assert( p );
 235                 return *p;
 236             }
 237
 238             void release()
 239             {
 240                 m_guard.clear();
 241             }
 242
 243             template <bool IsConst2>
 244             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const
 245             {
 246                 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
 247             }
 248
 249             template <bool IsConst2>
 250             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const
 251             {
 252                 return !( *this == rhs );
 253             }
 254
 255         protected:
 256             bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
 257                 : m_pNode( pNode )
 258                 , m_idx( idx )
 259                 , m_set( &set )
 260             {}
 261
 262             bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
 263                 : m_pNode( pNode )
 264                 , m_idx( idx )
 265                 , m_set( &set )
 266             {
 267                 forward();
 268             }
 269
 270             value_ptr pointer() const CDS_NOEXCEPT
 271             {
 272                 return m_guard.template get<value_type>();
 273             }
 274
 275             void forward()
 276             {
 277                 assert( m_set != nullptr );
 278                 assert( m_pNode != nullptr );
 279
 280                 size_t const arrayNodeSize = m_set->array_node_size();
 281                 size_t const headSize = m_set->head_size();
 282                 array_node * pNode = m_pNode;
 283                 size_t idx = m_idx + 1;
 284                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 285
 286                 for ( ;; ) {
 287                     if ( idx < nodeSize ) {
 288                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 289                         if ( slot.bits() == flag_array_node ) {
 290                             // array node, go down the tree
 291                             assert( slot.ptr() != nullptr );
 292                             pNode = to_array( slot.ptr() );
 293                             idx = 0;
 294                             nodeSize = arrayNodeSize;
 295                         }
 296                         else if ( slot.bits() == flag_array_converting ) {
 297                             // the slot is converting to array node right now - skip the node
 298                             ++idx;
 299                         }
 300                         else {
 301                             if ( slot.ptr()) {
 302                                 // data node
 303                                 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
 304                                     m_pNode = pNode;
 305                                     m_idx = idx;
 306                                     return;
 307                                 }
 308                             }
 309                             ++idx;
 310                         }
 311                     }
 312                     else {
 313                         // up to parent node
 314                         if ( pNode->pParent ) {
 315                             idx = pNode->idxParent + 1;
 316                             pNode = pNode->pParent;
 317                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 318                         }
 319                         else {
 320                             // end()
 321                             assert( pNode == m_set->m_Head );
 322                             assert( idx == headSize );
 323                             m_pNode = pNode;
 324                             m_idx = idx;
 325                             return;
 326                         }
 327                     }
 328                 }
 329             }
 330
 331             void backward()
 332             {
 333                 assert( m_set != nullptr );
 334                 assert( m_pNode != nullptr );
 335
 336                 size_t const arrayNodeSize = m_set->array_node_size();
 337                 size_t const headSize = m_set->head_size();
 338                 size_t const endIdx = size_t(0) - 1;
 339
 340                 array_node * pNode = m_pNode;
 341                 size_t idx = m_idx - 1;
 342                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 343
 344                 for ( ;; ) {
 345                     if ( idx != endIdx ) {
 346                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 347                         if ( slot.bits() == flag_array_node ) {
 348                             // array node, go down the tree
 349                             assert( slot.ptr() != nullptr );
 350                             pNode = to_array( slot.ptr() );
 351                             nodeSize = arrayNodeSize;
 352                             idx = nodeSize - 1;
 353                         }
 354                         else if ( slot.bits() == flag_array_converting ) {
 355                             // the slot is converting to array node right now - skip the node
 356                             --idx;
 357                         }
 358                         else {
 359                             if ( slot.ptr()) {
 360                                 // data node
 361                                 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
 362                                     m_pNode = pNode;
 363                                     m_idx = idx;
 364                                     return;
 365                                 }
 366                             }
 367                             --idx;
 368                         }
 369                     }
 370                     else {
 371                         // up to parent node
 372                         if ( pNode->pParent ) {
 373                             idx = pNode->idxParent - 1;
 374                             pNode = pNode->pParent;
 375                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 376                         }
 377                         else {
 378                             // rend()
 379                             assert( pNode == m_set->m_Head );
 380                             assert( idx == endIdx );
 381                             m_pNode = pNode;
 382                             m_idx = idx;
 383                             return;
 384                         }
 385                     }
 386                 }
 387             }
 388         };
 389
 390         /// Reverse bidirectional iterator
 391         template <bool IsConst>
 392         class reverse_bidirectional_iterator : protected bidirectional_iterator<IsConst>
 393         {
 394             typedef bidirectional_iterator<IsConst> base_class;
 395             friend class MultiLevelHashSet;
 396
 397         public:
 398             typedef typename base_class::value_ptr value_ptr;
 399             typedef typename base_class::value_ref value_ref;
 400
 401         public:
 402             reverse_bidirectional_iterator() CDS_NOEXCEPT
 403                 : base_class()
 404             {}
 405
 406             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 407                 : base_class( rhs )
 408             {}
 409
 410             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 411             {
 412                 base_class::operator=( rhs );
 413                 return *this;
 414             }
 415
 416             reverse_bidirectional_iterator& operator++()
 417             {
 418                 base_class::backward();
 419                 return *this;
 420             }
 421
 422             reverse_bidirectional_iterator& operator--()
 423             {
 424                 base_class::forward();
 425                 return *this;
 426             }
 427
 428             value_ptr operator ->() const CDS_NOEXCEPT
 429             {
 430                 return base_class::operator->();
 431             }
 432
 433             value_ref operator *() const CDS_NOEXCEPT
 434             {
 435                 return base_class::operator*();
 436             }
 437
 438             void release()
 439             {
 440                 base_class::release();
 441             }
 442
 443             template <bool IsConst2>
 444             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
 445             {
 446                 return base_class::operator==( rhs );
 447             }
 448
 449             template <bool IsConst2>
 450             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
 451             {
 452                 return !( *this == rhs );
 453             }
 454
 455         private:
 456             reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
 457                 : base_class( set, pNode, idx, false )
 458             {
 459                 base_class::backward();
 460             }
 461         };
 462         //@endcond
 463
 464     public:
 465         typedef bidirectional_iterator<false>   iterator;       ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
 466         typedef bidirectional_iterator<true>    const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
 467         typedef reverse_bidirectional_iterator<false>   reverse_iterator;       ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
 468         typedef reverse_bidirectional_iterator<true>    const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
 469
 470     private:
 471         //@cond
 472         metrics const     m_Metrics;     ///< Metrics
 473         array_node *      m_Head;        ///< Head array
 474         item_counter      m_ItemCounter; ///< Item counter
 475         stat              m_Stat;        ///< Internal statistics
 476         //@endcond
 477
 478     public:
 479         /// Creates empty set
 480         /**
 481             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 482             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 483
 484             Equation for \p head_bits and \p array_bits:
 485             \code
 486             sizeof(hash_type) * 8 == head_bits + N * array_bits
 487             \endcode
 488             where \p N is multi-level array depth.
 489         */
 490         MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
 491             : m_Metrics(make_metrics( head_bits, array_bits ))
 492             , m_Head( alloc_head_node())
 493         {}
 494
 495         /// Destructs the set and frees all data
 496         ~MultiLevelHashSet()
 497         {
 498             destroy_tree();
 499             free_array_node( m_Head );
 500         }
 501
 502         /// Inserts new node
 503         /**
 504             The function inserts \p val in the set if it does not contain
 505             an item with that hash.
 506
 507             Returns \p true if \p val is placed into the set, \p false otherwise.
 508         */
 509         bool insert( value_type& val )
 510         {
 511             return insert( val, [](value_type&) {} );
 512         }
 513
 514         /// Inserts new node
 515         /**
 516             This function is intended for derived non-intrusive containers.
 517
 518             The function allows to split creating of new item into two part:
 519             - create item with key only
 520             - insert new item into the set
 521             - if inserting is success, calls \p f functor to initialize \p val.
 522
 523             The functor signature is:
 524             \code
 525                 void func( value_type& val );
 526             \endcode
 527             where \p val is the item inserted.
 528
 529             The user-defined functor is called only if the inserting is success.
 530
 531             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
 532         */
 533         template <typename Func>
 534         bool insert( value_type& val, Func f )
 535         {
 536             hash_type const& hash = hash_accessor()( val );
 537             hash_splitter splitter( hash );
 538             hash_comparator cmp;
 539             typename gc::Guard guard;
 540             back_off bkoff;
 541
 542             size_t nOffset = m_Metrics.head_node_size_log;
 543             array_node * pArr = m_Head;
 544             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
 545             assert( nSlot < m_Metrics.head_node_size );
 546
 547             while ( true ) {
 548                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
 549                 if ( slot.bits() == flag_array_node ) {
 550                     // array node, go down the tree
 551                     assert( slot.ptr() != nullptr );
 552                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
 553                     assert( nSlot < m_Metrics.array_node_size );
 554                     pArr = to_array( slot.ptr() );
 555                     nOffset += m_Metrics.array_node_size_log;
 556                 }
 557                 else if ( slot.bits() == flag_array_converting ) {
 558                     // the slot is converting to array node right now
 559                     bkoff();
 560                     m_Stat.onSlotConverting();
 561                 }
 562                 else {
 563                     // data node
 564                     assert(slot.bits() == 0 );
 565
 566                     // protect data node by hazard pointer
 567                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
 568                         // slot value has been changed - retry
 569                         m_Stat.onSlotChanged();
 570                     }
 571                     else if ( slot.ptr() ) {
 572                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
 573                             // the item with that hash value already exists
 574                             m_Stat.onInsertFailed();
 575                             return false;
 576                         }
 577
 578                         // the slot must be expanded
 579                         expand_slot( pArr, nSlot, slot, nOffset );
 580                     }
 581                     else {
 582                         // the slot is empty, try to insert data node
 583                         node_ptr pNull;
 584                         if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 585                         {
 586                             // the new data node has been inserted
 587                             f( val );
 588                             ++m_ItemCounter;
 589                             m_Stat.onInsertSuccess();
 590                             return true;
 591                         }
 592
 593                         // insert failed - slot has been changed by another thread
 594                         // retry inserting
 595                         m_Stat.onInsertRetry();
 596                     }
 597                 }
 598             } // while
 599         }
 600
 601         /// Updates the node
 602         /**
 603             Performs inserting or updating the item with hash value equal to \p val.
 604             - If hash value is found then existing item is replaced with \p val, old item is disposed
 605               with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
 606               The function returns <tt> std::pair<true, false> </tt>
 607             - If hash value is not found and \p bInsert is \p true then \p val is inserted,
 608               the function returns <tt> std::pair<true, true> </tt>
 609             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
 610               the function returns <tt> std::pair<false, false> </tt>
 611
 612             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
 613             (i.e. the item has been inserted or updated),
 614             \p second is \p true if new item has been added or \p false if the set contains that hash.
 615         */
 616         std::pair<bool, bool> update( value_type& val, bool bInsert = true )
 617         {
 618             return do_update(val, [](bool, value_type&) {}, bInsert );
 619         }
 620
 621         /// Unlinks the item \p val from the set
 622         /**
 623             The function searches the item \p val in the set and unlink it
 624             if it is found and its address is equal to <tt>&val</tt>.
 625
 626             The function returns \p true if success and \p false otherwise.
 627         */
 628         bool unlink( value_type const& val )
 629         {
 630             typename gc::Guard guard;
 631             auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
 632             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 633
 634             // p is guarded by HP
 635             if ( p ) {
 636                 gc::template retire<disposer>( p );
 637                 --m_ItemCounter;
 638                 m_Stat.onEraseSuccess();
 639                 return true;
 640             }
 641             return false;
 642         }
 643
 644         /// Deletes the item from the set
 645         /**
 646             The function searches \p hash in the set,
 647             unlinks the item found, and returns \p true.
 648             If that item is not found the function returns \p false.
 649
 650             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 651         */
 652         bool erase( hash_type const& hash )
 653         {
 654             return erase(hash, [](value_type const&) {} );
 655         }
 656
 657         /// Deletes the item from the set
 658         /**
 659             The function searches \p hash in the set,
 660             call \p f functor with item found, and unlinks it from the set.
 661             The \ref disposer specified in \p Traits is called
 662             by garbage collector \p GC asynchronously.
 663
 664             The \p Func interface is
 665             \code
 666             struct functor {
 667                 void operator()( value_type& item );
 668             };
 669             \endcode
 670
 671             If \p hash is not found the function returns \p false.
 672         */
 673         template <typename Func>
 674         bool erase( hash_type const& hash, Func f )
 675         {
 676             typename gc::Guard guard;
 677             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 678
 679             // p is guarded by HP
 680             if ( p ) {
 681                 gc::template retire<disposer>( p );
 682                 --m_ItemCounter;
 683                 f( *p );
 684                 m_Stat.onEraseSuccess();
 685                 return true;
 686             }
 687             return false;
 688         }
 689
 690         /// Deletes the item pointed by iterator \p iter
 691         /**
 692             Returns \p true if the operation is successful, \p false otherwise.
 693
 694             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 695         */
 696         bool erase_at( iterator const& iter )
 697         {
 698             if ( iter.m_set != this )
 699                 return false;
 700             if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
 701                 return false;
 702             if ( iter.m_idx >= array_node_size() )
 703                 return false;
 704
 705             for (;;) {
 706                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
 707                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
 708                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
 709                         // the item is guarded by iterator, so we may retire it safely
 710                         gc::template retire<disposer>( slot.ptr() );
 711                         --m_ItemCounter;
 712                         m_Stat.onEraseSuccess();
 713                         return true;
 714                     }
 715                 }
 716                 else
 717                     return false;
 718             }
 719         }
 720
 721         /// Extracts the item with specified \p hash
 722         /**
 723             The function searches \p hash in the set,
 724             unlinks it from the set, and returns an guarded pointer to the item extracted.
 725             If \p hash is not found the function returns an empty guarded pointer.
 726
 727             The \p disposer specified in \p Traits class' template parameter is called automatically
 728             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 729             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 730
 731             Usage:
 732             \code
 733             typedef cds::intrusive::MultiLevelHashSet< your_template_args > my_set;
 734             my_set theSet;
 735             // ...
 736             {
 737                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 738                 if ( gp ) {
 739                     // Deal with gp
 740                     // ...
 741                 }
 742                 // Destructor of gp releases internal HP guard
 743             }
 744             \endcode
 745         */
 746         guarded_ptr extract( hash_type const& hash )
 747         {
 748             guarded_ptr gp;
 749             {
 750                 typename gc::Guard guard;
 751                 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 752
 753                 // p is guarded by HP
 754                 if ( p ) {
 755                     gc::template retire<disposer>( p );
 756                     --m_ItemCounter;
 757                     m_Stat.onEraseSuccess();
 758                     gp.reset( p );
 759                 }
 760             }
 761             return gp;
 762         }
 763
 764         /// Finds an item by it's \p hash
 765         /**
 766             The function searches the item by \p hash and calls the functor \p f for item found.
 767             The interface of \p Func functor is:
 768             \code
 769             struct functor {
 770                 void operator()( value_type& item );
 771             };
 772             \endcode
 773             where \p item is the item found.
 774
 775             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 776             that \p item cannot be disposed during the functor is executing.
 777             The functor does not serialize simultaneous access to the set's \p item. If such access is
 778             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 779
 780             The function returns \p true if \p hash is found, \p false otherwise.
 781         */
 782         template <typename Func>
 783         bool find( hash_type const& hash, Func f )
 784         {
 785             typename gc::Guard guard;
 786             value_type * p = search( hash, guard );
 787
 788             // p is guarded by HP
 789             if ( p ) {
 790                 f( *p );
 791                 return true;
 792             }
 793             return false;
 794         }
 795
 796         /// Checks whether the set contains \p hash
 797         /**
 798             The function searches the item by its \p hash
 799             and returns \p true if it is found, or \p false otherwise.
 800         */
 801         bool contains( hash_type const& hash )
 802         {
 803             return find( hash, [](value_type&) {} );
 804         }
 805
 806         /// Finds an item by it's \p hash and returns the item found
 807         /**
 808             The function searches the item by its \p hash
 809             and returns the guarded pointer to the item found.
 810             If \p hash is not found the function returns an empty \p guarded_ptr.
 811
 812             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 813
 814             Usage:
 815             \code
 816             typedef cds::intrusive::MultiLevelHashSet< your_template_params >  my_set;
 817             my_set theSet;
 818             // ...
 819             {
 820                 my_set::guarded_ptr gp( theSet.get( 5 ));
 821                 if ( theSet.get( 5 )) {
 822                     // Deal with gp
 823                     //...
 824                 }
 825                 // Destructor of guarded_ptr releases internal HP guard
 826             }
 827             \endcode
 828         */
 829         guarded_ptr get( hash_type const& hash )
 830         {
 831             guarded_ptr gp;
 832             {
 833                 typename gc::Guard guard;
 834                 gp.reset( search( hash, guard ));
 835             }
 836             return gp;
 837         }
 838
 839         /// Clears the set (non-atomic)
 840         /**
 841             The function unlink all data node from the set.
 842             The function is not atomic but is thread-safe.
 843             After \p %clear() the set may not be empty because another threads may insert items.
 844
 845             For each item the \p disposer is called after unlinking.
 846         */
 847         void clear()
 848         {
 849             clear_array( m_Head, head_size() );
 850         }
 851
 852         /// Checks if the set is empty
 853         /**
 854             Emptiness is checked by item counting: if item count is zero then the set is empty.
 855             Thus, the correct item counting feature is an important part of the set implementation.
 856         */
 857         bool empty() const
 858         {
 859             return size() == 0;
 860         }
 861
 862         /// Returns item count in the set
 863         size_t size() const
 864         {
 865             return m_ItemCounter;
 866         }
 867
 868         /// Returns const reference to internal statistics
 869         stat const& statistics() const
 870         {
 871             return m_Stat;
 872         }
 873
 874         /// Returns the size of head node
 875         size_t head_size() const
 876         {
 877             return m_Metrics.head_node_size;
 878         }
 879
 880         /// Returns the size of the array node
 881         size_t array_node_size() const
 882         {
 883             return m_Metrics.array_node_size;
 884         }
 885
 886     public:
 887     ///@name Thread-safe iterators
 888         /** @anchor cds_intrusive_MultilevelHashSet_iterators
 889             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.\r
 890             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:\r
 891             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.\r
 892 \r
 893             @note Since the iterator object contains hazard pointer that is a thread-local resource,\r
 894             the iterator should not be passed to another thread.\r
 895 \r
 896             Each iterator object supports the common interface:\r
 897             - dereference operators:\r
 898                 @code\r
 899                 value_type [const] * operator ->() noexcept\r
 900                 value_type [const] & operator *() noexcept\r
 901                 @endcode\r
 902             - pre-increment and pre-decrement. Post-operators is not supported\r
 903             - equality operators <tt>==</tt> and <tt>!=</tt>.\r
 904                 Iterators are equal iff they point to the same cell of the same array node.
 905                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 906                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 907             - helper member function \p release() that clears internal hazard pointer.\r
 908                 After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 909         */
 910     ///@{
 911
 912         /// Returns an iterator to the beginning of the set
 913         iterator begin()
 914         {
 915             return iterator( *this, m_Head, size_t(0) - 1 );
 916         }
 917
 918         /// Returns an const iterator to the beginning of the set
 919         const_iterator begin() const
 920         {
 921             return const_iterator( *this, m_Head, size_t(0) - 1 );
 922         }
 923
 924         /// Returns an const iterator to the beginning of the set
 925         const_iterator cbegin()
 926         {
 927             return const_iterator( *this, m_Head, size_t(0) - 1 );
 928         }
 929
 930         /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 931         iterator end()
 932         {
 933             return iterator( *this, m_Head, head_size() - 1 );
 934         }
 935
 936         /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 937         const_iterator end() const
 938         {
 939             return const_iterator( *this, m_Head, head_size() - 1 );
 940         }
 941
 942         /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 943         const_iterator cend()
 944         {
 945             return const_iterator( *this, m_Head, head_size() - 1 );
 946         }
 947
 948         /// Returns a reverse iterator to the first element of the reversed set
 949         reverse_iterator rbegin()
 950         {
 951             return reverse_iterator( *this, m_Head, head_size() );
 952         }
 953
 954         /// Returns a const reverse iterator to the first element of the reversed set
 955         const_reverse_iterator rbegin() const
 956         {
 957             return const_reverse_iterator( *this, m_Head, head_size() );
 958         }
 959
 960         /// Returns a const reverse iterator to the first element of the reversed set
 961         const_reverse_iterator crbegin()
 962         {
 963             return const_reverse_iterator( *this, m_Head, head_size() );
 964         }
 965
 966         /// Returns a reverse iterator to the element following the last element of the reversed set
 967         /**
 968             It corresponds to the element preceding the first element of the non-reversed container.
 969             This element acts as a placeholder, attempting to access it results in undefined behavior.
 970         */
 971         reverse_iterator rend()
 972         {
 973             return reverse_iterator( *this, m_Head, 0 );
 974         }
 975
 976         /// Returns a const reverse iterator to the element following the last element of the reversed set
 977         /**
 978             It corresponds to the element preceding the first element of the non-reversed container.
 979             This element acts as a placeholder, attempting to access it results in undefined behavior.
 980         */
 981         const_reverse_iterator rend() const
 982         {
 983             return const_reverse_iterator( *this, m_Head, 0 );
 984         }
 985
 986         /// Returns a const reverse iterator to the element following the last element of the reversed set
 987         /**
 988             It corresponds to the element preceding the first element of the non-reversed container.
 989             This element acts as a placeholder, attempting to access it results in undefined behavior.
 990         */
 991         const_reverse_iterator crend()
 992         {
 993             return const_reverse_iterator( *this, m_Head, 0 );
 994         }
 995     ///@}
 996
 997     private:
 998         //@cond
 999         static metrics make_metrics( size_t head_bits, size_t array_bits )
1000         {
1001             size_t const hash_bits = sizeof( hash_type ) * 8;
1002
1003             if ( array_bits < 2 )
1004                 array_bits = 2;
1005             if ( head_bits < 4 )
1006                 head_bits = 4;
1007             if ( head_bits > hash_bits )
1008                 head_bits = hash_bits;
1009             if ( (hash_bits - head_bits) % array_bits != 0 )
1010                 head_bits += (hash_bits - head_bits) % array_bits;
1011
1012             assert( (hash_bits - head_bits) % array_bits == 0 );
1013
1014             metrics m;
1015             m.head_node_size_log = head_bits;
1016             m.head_node_size = size_t(1) << head_bits;
1017             m.array_node_size_log = array_bits;
1018             m.array_node_size = size_t(1) << array_bits;
1019             return m;
1020         }
1021
1022         array_node * alloc_head_node() const
1023         {
1024             return alloc_array_node( head_size(), nullptr, 0 );
1025         }
1026
1027         array_node * alloc_array_node( array_node * pParent, size_t idxParent ) const
1028         {
1029             return alloc_array_node( array_node_size(), pParent, idxParent );
1030         }
1031
1032         static array_node * alloc_array_node( size_t nSize, array_node * pParent, size_t idxParent )
1033         {
1034             array_node * pNode = cxx_array_node_allocator().NewBlock( sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent );
1035             for ( atomic_node_ptr * p = pNode->nodes, *pEnd = pNode->nodes + nSize; p < pEnd; ++p )
1036                 p->store( node_ptr(), memory_model::memory_order_release );
1037             return pNode;
1038         }
1039
1040         static void free_array_node( array_node * parr )
1041         {
1042             cxx_array_node_allocator().Delete( parr );
1043         }
1044
1045         void destroy_tree()
1046         {
1047             // The function is not thread-safe. For use in dtor only
1048             // Remove data node
1049             clear();
1050
1051             // Destroy all array nodes
1052             destroy_array_nodes( m_Head, head_size());
1053         }
1054
1055         void destroy_array_nodes( array_node * pArr, size_t nSize )
1056         {
1057             for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
1058                 node_ptr slot = p->load( memory_model::memory_order_acquire );
1059                 if ( slot.bits() == flag_array_node ) {
1060                     destroy_array_nodes(to_array(slot.ptr()), array_node_size());
1061                     free_array_node( to_array(slot.ptr()));
1062                     p->store(node_ptr(), memory_model::memory_order_relaxed );
1063                 }
1064             }
1065         }
1066
1067         void clear_array( array_node * pArrNode, size_t nSize )
1068         {
1069             back_off bkoff;
1070
1071
1072             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1073                 while ( true ) {
1074                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1075                     if ( slot.bits() == flag_array_node ) {
1076                         // array node, go down the tree
1077                         assert( slot.ptr() != nullptr );
1078                         clear_array( to_array( slot.ptr()), array_node_size() );
1079                         break;
1080                     }
1081                     else if ( slot.bits() == flag_array_converting ) {
1082                         // the slot is converting to array node right now
1083                         while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting ) {
1084                             bkoff();
1085                             m_Stat.onSlotConverting();
1086                         }
1087                         bkoff.reset();
1088
1089                         assert( slot.ptr() != nullptr );
1090                         assert(slot.bits() == flag_array_node );
1091                         clear_array( to_array( slot.ptr()), array_node_size() );
1092                         break;
1093                     }
1094                     else {
1095                         // data node
1096                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1097                             if ( slot.ptr() ) {
1098                                 gc::template retire<disposer>( slot.ptr() );
1099                                 --m_ItemCounter;
1100                                 m_Stat.onEraseSuccess();
1101                             }
1102                             break;
1103                         }
1104                     }
1105                 }
1106             }
1107         }
1108
1109         union converter {
1110             value_type * pData;
1111             array_node * pArr;
1112
1113             converter( value_type * p )
1114                 : pData( p )
1115             {}
1116
1117             converter( array_node * p )
1118                 : pArr( p )
1119             {}
1120         };
1121
1122         static array_node * to_array( value_type * p )
1123         {
1124             return converter( p ).pArr;
1125         }
1126         static value_type * to_node( array_node * p )
1127         {
1128             return converter( p ).pData;
1129         }
1130
1131         bool expand_slot( array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset )
1132         {
1133             assert( current.bits() == 0 );
1134             assert( current.ptr() );
1135
1136             size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut( m_Metrics.array_node_size_log );
1137             array_node * pArr = alloc_array_node( pParent, idxParent );
1138
1139             node_ptr cur(current.ptr());
1140             atomic_node_ptr& slot = pParent->nodes[idxParent];
1141             if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
1142             {
1143                 m_Stat.onExpandNodeFailed();
1144                 free_array_node( pArr );
1145                 return false;
1146             }
1147
1148             pArr->nodes[idx].store( current, memory_model::memory_order_release );
1149
1150             cur = cur | flag_array_converting;
1151             CDS_VERIFY(
1152                 slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
1153             );
1154
1155             m_Stat.onArrayNodeCreated();
1156             return true;
1157         }
1158         //@endcond
1159
1160     protected:
1161         //@cond
1162         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1163         {
1164             hash_splitter splitter( hash );
1165             hash_comparator cmp;
1166             back_off bkoff;
1167
1168             array_node * pArr = m_Head;
1169             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1170             assert( nSlot < m_Metrics.head_node_size );
1171
1172             while ( true ) {
1173                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1174                 if ( slot.bits() == flag_array_node ) {
1175                     // array node, go down the tree
1176                     assert( slot.ptr() != nullptr );
1177                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1178                     assert( nSlot < m_Metrics.array_node_size );
1179                     pArr = to_array( slot.ptr() );
1180                 }
1181                 else if ( slot.bits() == flag_array_converting ) {
1182                     // the slot is converting to array node right now
1183                     bkoff();
1184                     m_Stat.onSlotConverting();
1185                 }
1186                 else {
1187                     // data node
1188                     assert(slot.bits() == 0 );
1189
1190                     // protect data node by hazard pointer
1191                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1192                         // slot value has been changed - retry
1193                         m_Stat.onSlotChanged();
1194                     }
1195                     else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1196                         // item found
1197                         m_Stat.onFindSuccess();
1198                         return slot.ptr();
1199                     }
1200                     m_Stat.onFindFailed();
1201                     return nullptr;
1202                 }
1203             } // while
1204         }
1205
1206         template <typename Predicate>
1207         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1208         {
1209             hash_splitter splitter( hash );
1210             hash_comparator cmp;
1211             back_off bkoff;
1212
1213             array_node * pArr = m_Head;
1214             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1215             assert( nSlot < m_Metrics.head_node_size );
1216
1217             while ( true ) {
1218                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1219                 if ( slot.bits() == flag_array_node ) {
1220                     // array node, go down the tree
1221                     assert( slot.ptr() != nullptr );
1222                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1223                     assert( nSlot < m_Metrics.array_node_size );
1224                     pArr = to_array( slot.ptr() );
1225                 }
1226                 else if ( slot.bits() == flag_array_converting ) {
1227                     // the slot is converting to array node right now
1228                     bkoff();
1229                     m_Stat.onSlotConverting();
1230                 }
1231                 else {
1232                     // data node
1233                     assert(slot.bits() == 0 );
1234
1235                     // protect data node by hazard pointer
1236                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1237                         // slot value has been changed - retry
1238                         m_Stat.onSlotChanged();
1239                     }
1240                     else if ( slot.ptr() ) {
1241                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
1242                             // item found - replace it with nullptr
1243                             if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed))
1244                                 return slot.ptr();
1245                             m_Stat.onEraseRetry();
1246                             continue;
1247                         }
1248                         m_Stat.onEraseFailed();
1249                         return nullptr;
1250                     }
1251                     else {
1252                         // the slot is empty
1253                         m_Stat.onEraseFailed();
1254                         return nullptr;
1255                     }
1256                 }
1257             } // while
1258         }
1259
1260         template <typename Func>
1261         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1262         {
1263             hash_type const& hash = hash_accessor()( val );
1264             hash_splitter splitter( hash );
1265             hash_comparator cmp;
1266             typename gc::Guard guard;
1267             back_off bkoff;
1268
1269             array_node * pArr = m_Head;
1270             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1271             assert( nSlot < m_Metrics.head_node_size );
1272             size_t nOffset = m_Metrics.head_node_size_log;
1273
1274             while ( true ) {
1275                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1276                 if ( slot.bits() == flag_array_node ) {
1277                     // array node, go down the tree
1278                     assert( slot.ptr() != nullptr );
1279                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1280                     assert( nSlot < m_Metrics.array_node_size );
1281                     pArr = to_array( slot.ptr() );
1282                     nOffset += m_Metrics.array_node_size_log;
1283                 }
1284                 else if ( slot.bits() == flag_array_converting ) {
1285                     // the slot is converting to array node right now
1286                     bkoff();
1287                     m_Stat.onSlotConverting();
1288                 }
1289                 else {
1290                     // data node
1291                     assert(slot.bits() == 0 );
1292
1293                     // protect data node by hazard pointer
1294                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1295                         // slot value has been changed - retry
1296                         m_Stat.onSlotChanged();
1297                     }
1298                     else if ( slot.ptr() ) {
1299                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1300                             // the item with that hash value already exists
1301                             // Replace it with val
1302                             if ( slot.ptr() == &val ) {
1303                                 m_Stat.onUpdateExisting();
1304                                 return std::make_pair( true, false );
1305                             }
1306
1307                             if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1308                                 // slot can be disposed
1309                                 f( false, val );
1310                                 gc::template retire<disposer>( slot.ptr() );
1311                                 m_Stat.onUpdateExisting();
1312                                 return std::make_pair( true, false );
1313                             }
1314
1315                             m_Stat.onUpdateRetry();
1316                             continue;
1317                         }
1318
1319                         // the slot must be expanded
1320                         expand_slot( pArr, nSlot, slot, nOffset );
1321                     }
1322                     else {
1323                         // the slot is empty, try to insert data node
1324                         if ( bInsert ) {
1325                             node_ptr pNull;
1326                             if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1327                             {
1328                                 // the new data node has been inserted
1329                                 f( true, val );
1330                                 ++m_ItemCounter;
1331                                 m_Stat.onUpdateNew();
1332                                 return std::make_pair( true, true );
1333                             }
1334                         }
1335                         else {
1336                             m_Stat.onUpdateFailed();
1337                             return std::make_pair( false, false );
1338                         }
1339
1340                         // insert failed - slot has been changed by another thread
1341                         // retry updating
1342                         m_Stat.onUpdateRetry();
1343                     }
1344                 }
1345             } // while
1346         }
1347         //@endcond
1348     };
1349 }} // namespace cds::intrusive
1350
1351 /*
1352 namespace std {
1353
1354     template <class GC, typename T, typename Traits>
1355     struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator >
1356     {
1357         typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator iterator_class;
1358
1359         // difference_type is not applicable for that iterator
1360         // typedef ??? difference_type
1361         typedef T value_type;
1362         typedef typename iterator_class::value_ptr pointer;
1363         typedef typename iterator_class::value_ref reference;
1364         typedef bidirectional_iterator_tag iterator_category;
1365     };
1366
1367     template <class GC, typename T, typename Traits>
1368     struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator >
1369     {
1370         typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator iterator_class;
1371
1372         // difference_type is not applicable for that iterator
1373         // typedef ??? difference_type
1374         typedef T value_type;
1375         typedef typename iterator_class::value_ptr pointer;
1376         typedef typename iterator_class::value_ref reference;
1377         typedef bidirectional_iterator_tag iterator_category;
1378     };
1379
1380 } // namespace std
1381 */
1382
1383 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H