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 whitch 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 map 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 defined as \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             hash_type const& hash = hash_accessor()( val );
 619             hash_splitter splitter( hash );
 620             hash_comparator cmp;
 621             typename gc::Guard guard;
 622             back_off bkoff;
 623
 624             array_node * pArr = m_Head;
 625             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
 626             assert( nSlot < m_Metrics.head_node_size );
 627             size_t nOffset = m_Metrics.head_node_size_log;
 628
 629             while ( true ) {
 630                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
 631                 if ( slot.bits() == flag_array_node ) {
 632                     // array node, go down the tree
 633                     assert( slot.ptr() != nullptr );
 634                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
 635                     assert( nSlot < m_Metrics.array_node_size );
 636                     pArr = to_array( slot.ptr() );
 637                     nOffset += m_Metrics.array_node_size_log;
 638                 }
 639                 else if ( slot.bits() == flag_array_converting ) {
 640                     // the slot is converting to array node right now
 641                     bkoff();
 642                     m_Stat.onSlotConverting();
 643                 }
 644                 else {
 645                     // data node
 646                     assert(slot.bits() == 0 );
 647
 648                     // protect data node by hazard pointer
 649                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
 650                         // slot value has been changed - retry
 651                         m_Stat.onSlotChanged();
 652                     }
 653                     else if ( slot.ptr() ) {
 654                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
 655                             // the item with that hash value already exists
 656                             // Replace it with val
 657                             if ( slot.ptr() == &val ) {
 658                                 m_Stat.onUpdateExisting();
 659                                 return std::make_pair( true, false );
 660                             }
 661
 662                             if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 663                                 // slot can be disposed
 664                                 gc::template retire<disposer>( slot.ptr() );
 665                                 m_Stat.onUpdateExisting();
 666                                 return std::make_pair( true, false );
 667                             }
 668
 669                             m_Stat.onUpdateRetry();
 670                             continue;
 671                         }
 672
 673                         // the slot must be expanded
 674                         expand_slot( pArr, nSlot, slot, nOffset );
 675                     }
 676                     else {
 677                         // the slot is empty, try to insert data node
 678                         if ( bInsert ) {
 679                             node_ptr pNull;
 680                             if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 681                             {
 682                                 // the new data node has been inserted
 683                                 ++m_ItemCounter;
 684                                 m_Stat.onUpdateNew();
 685                                 return std::make_pair( true, true );
 686                             }
 687                         }
 688                         else {
 689                             m_Stat.onUpdateFailed();
 690                             return std::make_pair( false, false );
 691                         }
 692
 693                         // insert failed - slot has been changed by another thread
 694                         // retry updating
 695                         m_Stat.onUpdateRetry();
 696                     }
 697                 }
 698             } // while
 699         }
 700
 701         /// Unlinks the item \p val from the set
 702         /**
 703             The function searches the item \p val in the set and unlink it
 704             if it is found and its address is equal to <tt>&val</tt>.
 705
 706             The function returns \p true if success and \p false otherwise.
 707         */
 708         bool unlink( value_type const& val )
 709         {
 710             typename gc::Guard guard;
 711             auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
 712             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 713
 714             // p is guarded by HP
 715             if ( p ) {
 716                 gc::template retire<disposer>( p );
 717                 --m_ItemCounter;
 718                 m_Stat.onEraseSuccess();
 719                 return true;
 720             }
 721             return false;
 722         }
 723
 724         /// Deletes the item from the set
 725         /**
 726             The function searches \p hash in the set,
 727             unlinks the item found, and returns \p true.
 728             If that item is not found the function returns \p false.
 729
 730             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 731
 732         */
 733         bool erase( hash_type const& hash )
 734         {
 735             return erase(hash, [](value_type const&) {} );
 736         }
 737
 738         /// Deletes the item from the set
 739         /**
 740             The function searches \p hash in the set,
 741             call \p f functor with item found, and unlinks it from the set.
 742             The \ref disposer specified in \p Traits is called
 743             by garbage collector \p GC asynchronously.
 744
 745             The \p Func interface is
 746             \code
 747             struct functor {
 748                 void operator()( value_type& item );
 749             };
 750             \endcode
 751
 752             If \p hash is not found the function returns \p false.
 753         */
 754         template <typename Func>
 755         bool erase( hash_type const& hash, Func f )
 756         {
 757             typename gc::Guard guard;
 758             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 759
 760             // p is guarded by HP
 761             if ( p ) {
 762                 gc::template retire<disposer>( p );
 763                 --m_ItemCounter;
 764                 f( *p );
 765                 m_Stat.onEraseSuccess();
 766                 return true;
 767             }
 768             return false;
 769         }
 770
 771         /// Deletes the item pointed by iterator \p it
 772         /**
 773             Returns \p true if the operation is successful, \p false otherwise.
 774
 775             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 776         */
 777         bool erase_at( iterator const& it )
 778         {
 779             if ( it.m_set != this )
 780                 return false;
 781             if ( it.m_pNode == m_Head && it.m_idx >= head_size())
 782                 return false;
 783             if ( it.m_idx >= array_node_size() )
 784                 return false;
 785
 786             for (;;) {
 787                 node_ptr slot = it.m_pNode->nodes[it.m_idx].load( memory_model::memory_order_acquire );
 788                 if ( slot.bits() == 0 && slot.ptr() == it.pointer() ) {
 789                     if ( it.m_pNode->nodes[it.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
 790                         // the item is guarded by iterator, so we may retire it safely
 791                         gc::template retire<disposer>( slot.ptr() );
 792                         --m_ItemCounter;
 793                         m_Stat.onEraseSuccess();
 794                         return true;
 795                     }
 796                 }
 797                 else
 798                     return false;
 799             }
 800         }
 801
 802         /// Extracts the item with specified \p hash
 803         /**
 804             The function searches \p hash in the set,
 805             unlinks it from the set, and returns an guarded pointer to the item extracted.
 806             If \p hash is not found the function returns an empty guarded pointer.
 807
 808             The \p disposer specified in \p Traits class' template parameter is called automatically
 809             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 810             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 811
 812             Usage:
 813             \code
 814             typedef cds::intrusive::MultiLevelHashSet< your_template_args > my_set;
 815             my_set theSet;
 816             // ...
 817             {
 818                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 819                 if ( gp ) {
 820                     // Deal with gp
 821                     // ...
 822                 }
 823                 // Destructor of gp releases internal HP guard
 824             }
 825             \endcode
 826         */
 827         guarded_ptr extract( hash_type const& hash )
 828         {
 829             guarded_ptr gp;
 830             {
 831                 typename gc::Guard guard;
 832                 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 833
 834                 // p is guarded by HP
 835                 if ( p ) {
 836                     gc::template retire<disposer>( p );
 837                     --m_ItemCounter;
 838                     m_Stat.onEraseSuccess();
 839                     gp.reset( p );
 840                 }
 841             }
 842             return gp;
 843         }
 844
 845         /// Finds an item by it's \p hash
 846         /**
 847             The function searches the item by \p hash and calls the functor \p f for item found.
 848             The interface of \p Func functor is:
 849             \code
 850             struct functor {
 851                 void operator()( value_type& item );
 852             };
 853             \endcode
 854             where \p item is the item found.
 855
 856             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 857             that \p item cannot be disposed during the functor is executing.
 858             The functor does not serialize simultaneous access to the set's \p item. If such access is
 859             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 860
 861             The function returns \p true if \p hash is found, \p false otherwise.
 862         */
 863         template <typename Func>
 864         bool find( hash_type const& hash, Func f )
 865         {
 866             typename gc::Guard guard;
 867             value_type * p = search( hash, guard );
 868
 869             // p is guarded by HP
 870             if ( p ) {
 871                 f( *p );
 872                 return true;
 873             }
 874             return false;
 875         }
 876
 877         /// Checks whether the set contains \p hash
 878         /**
 879             The function searches the item by its \p hash
 880             and returns \p true if it is found, or \p false otherwise.
 881         */
 882         bool contains( hash_type const& hash )
 883         {
 884             return find( hash, [](value_type&) {} );
 885         }
 886
 887         /// Finds an item by it's \p hash and returns the item found
 888         /**
 889             The function searches the item by its \p hash
 890             and returns the guarded pointer to the item found.
 891             If \p hash is not found the function returns an empty \p guarded_ptr.
 892
 893             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 894
 895             Usage:
 896             \code
 897             typedef cds::intrusive::MultiLevelHashSet< your_template_params >  my_set;
 898             my_set theSet;
 899             // ...
 900             {
 901                 my_set::guarded_ptr gp( theSet.get( 5 ));
 902                 if ( theSet.get( 5 )) {
 903                     // Deal with gp
 904                     //...
 905                 }
 906                 // Destructor of guarded_ptr releases internal HP guard
 907             }
 908             \endcode
 909         */
 910         guarded_ptr get( hash_type const& hash )
 911         {
 912             guarded_ptr gp;
 913             {
 914                 typename gc::Guard guard;
 915                 gp.reset( search( hash, guard ));
 916             }
 917             return gp;
 918         }
 919
 920         /// Clears the set (non-atomic)
 921         /**
 922             The function unlink all data node from the set.
 923             The function is not atomic but is thread-safe.
 924             After \p %clear() the set may not be empty because another threads may insert items.
 925
 926             For each item the \p disposer is called after unlinking.
 927         */
 928         void clear()
 929         {
 930             clear_array( m_Head, head_size() );
 931         }
 932
 933         /// Checks if the set is empty
 934         /**
 935             Emptiness is checked by item counting: if item count is zero then the set is empty.
 936             Thus, the correct item counting feature is an important part of the set implementation.
 937         */
 938         bool empty() const
 939         {
 940             return size() == 0;
 941         }
 942
 943         /// Returns item count in the set
 944         size_t size() const
 945         {
 946             return m_ItemCounter;
 947         }
 948
 949         /// Returns const reference to internal statistics
 950         stat const& statistics() const
 951         {
 952             return m_Stat;
 953         }
 954
 955         /// Returns the size of head node
 956         size_t head_size() const
 957         {
 958             return m_Metrics.head_node_size;
 959         }
 960
 961         /// Returns the size of the array node
 962         size_t array_node_size() const
 963         {
 964             return m_Metrics.array_node_size;
 965         }
 966
 967     public:
 968     ///@name Thread-safe iterators
 969         /** @anchor cds_intrusive_MultilevelHashSet_iterators
 970             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.\r
 971             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:\r
 972             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.\r
 973 \r
 974             @note Since the iterator object contains hazard pointer that is a thread-local resource,\r
 975             the iterator should not be passed to another thread.\r
 976 \r
 977             Each iterator object supports the common interface:\r
 978             - dereference operators:\r
 979                 @code\r
 980                 value_type [const] * operator ->() noexcept\r
 981                 value_type [const] & operator *() noexcept\r
 982                 @endcode\r
 983             - pre-increment and pre-decrement. Post-operators is not supported\r
 984             - equality operators <tt>==</tt> and <tt>!=</tt>.\r
 985                 Iterators are equal iff they point to the same cell of the same array node.
 986                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 987                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 988             - helper member function \p release() that clears internal hazard pointer.\r
 989                 After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 990         */
 991     ///@{
 992
 993         /// Returns an iterator to the beginning of the set
 994         iterator begin()
 995         {
 996             return iterator( *this, m_Head, size_t(0) - 1 );
 997         }
 998
 999         /// Returns an const iterator to the beginning of the set
1000         const_iterator begin() const
1001         {
1002             return const_iterator( *this, m_Head, size_t(0) - 1 );
1003         }
1004
1005         /// Returns an const iterator to the beginning of the set
1006         const_iterator cbegin()
1007         {
1008             return const_iterator( *this, m_Head, size_t(0) - 1 );
1009         }
1010
1011         /// 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.
1012         iterator end()
1013         {
1014             return iterator( *this, m_Head, head_size() - 1 );
1015         }
1016
1017         /// 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.
1018         const_iterator end() const
1019         {
1020             return const_iterator( *this, m_Head, head_size() - 1 );
1021         }
1022
1023         /// 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.
1024         const_iterator cend()
1025         {
1026             return const_iterator( *this, m_Head, head_size() - 1 );
1027         }
1028
1029         /// Returns a reverse iterator to the first element of the reversed set
1030         reverse_iterator rbegin()
1031         {
1032             return reverse_iterator( *this, m_Head, head_size() );
1033         }
1034
1035         /// Returns a const reverse iterator to the first element of the reversed set
1036         const_reverse_iterator rbegin() const
1037         {
1038             return const_reverse_iterator( *this, m_Head, head_size() );
1039         }
1040
1041         /// Returns a const reverse iterator to the first element of the reversed set
1042         const_reverse_iterator crbegin()
1043         {
1044             return const_reverse_iterator( *this, m_Head, head_size() );
1045         }
1046
1047         /// Returns a reverse iterator to the element following the last element of the reversed set
1048         /**
1049             It corresponds to the element preceding the first element of the non-reversed container.
1050             This element acts as a placeholder, attempting to access it results in undefined behavior.
1051         */
1052         reverse_iterator rend()
1053         {
1054             return reverse_iterator( *this, m_Head, 0 );
1055         }
1056
1057         /// Returns a const reverse iterator to the element following the last element of the reversed set
1058         /**
1059             It corresponds to the element preceding the first element of the non-reversed container.
1060             This element acts as a placeholder, attempting to access it results in undefined behavior.
1061         */
1062         const_reverse_iterator rend() const
1063         {
1064             return const_reverse_iterator( *this, m_Head, 0 );
1065         }
1066
1067         /// Returns a const reverse iterator to the element following the last element of the reversed set
1068         /**
1069             It corresponds to the element preceding the first element of the non-reversed container.
1070             This element acts as a placeholder, attempting to access it results in undefined behavior.
1071         */
1072         const_reverse_iterator crend()
1073         {
1074             return const_reverse_iterator( *this, m_Head, 0 );
1075         }
1076     ///@}
1077
1078     private:
1079         //@cond
1080         static metrics make_metrics( size_t head_bits, size_t array_bits )
1081         {
1082             size_t const hash_bits = sizeof( hash_type ) * 8;
1083
1084             if ( array_bits < 2 )
1085                 array_bits = 2;
1086             if ( head_bits < 4 )
1087                 head_bits = 4;
1088             if ( head_bits > hash_bits )
1089                 head_bits = hash_bits;
1090             if ( (hash_bits - head_bits) % array_bits != 0 )
1091                 head_bits += (hash_bits - head_bits) % array_bits;
1092
1093             assert( (hash_bits - head_bits) % array_bits == 0 );
1094
1095             metrics m;
1096             m.head_node_size_log = head_bits;
1097             m.head_node_size = size_t(1) << head_bits;
1098             m.array_node_size_log = array_bits;
1099             m.array_node_size = size_t(1) << array_bits;
1100             return m;
1101         }
1102
1103         array_node * alloc_head_node() const
1104         {
1105             return alloc_array_node( head_size(), nullptr, 0 );
1106         }
1107
1108         array_node * alloc_array_node( array_node * pParent, size_t idxParent ) const
1109         {
1110             return alloc_array_node( array_node_size(), pParent, idxParent );
1111         }
1112
1113         static array_node * alloc_array_node( size_t nSize, array_node * pParent, size_t idxParent )
1114         {
1115             array_node * pNode = cxx_array_node_allocator().NewBlock( sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent );
1116             for ( atomic_node_ptr * p = pNode->nodes, *pEnd = pNode->nodes + nSize; p < pEnd; ++p )
1117                 p->store( node_ptr(), memory_model::memory_order_release );
1118             return pNode;
1119         }
1120
1121         static void free_array_node( array_node * parr )
1122         {
1123             cxx_array_node_allocator().Delete( parr );
1124         }
1125
1126         void destroy_tree()
1127         {
1128             // The function is not thread-safe. For use in dtor only
1129             // Remove data node
1130             clear();
1131
1132             // Destroy all array nodes
1133             destroy_array_nodes( m_Head, head_size());
1134         }
1135
1136         void destroy_array_nodes( array_node * pArr, size_t nSize )
1137         {
1138             for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
1139                 node_ptr slot = p->load( memory_model::memory_order_acquire );
1140                 if ( slot.bits() == flag_array_node ) {
1141                     destroy_array_nodes(to_array(slot.ptr()), array_node_size());
1142                     free_array_node( to_array(slot.ptr()));
1143                     p->store(node_ptr(), memory_model::memory_order_relaxed );
1144                 }
1145             }
1146         }
1147
1148         void clear_array( array_node * pArrNode, size_t nSize )
1149         {
1150             back_off bkoff;
1151
1152
1153             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1154                 while ( true ) {
1155                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1156                     if ( slot.bits() == flag_array_node ) {
1157                         // array node, go down the tree
1158                         assert( slot.ptr() != nullptr );
1159                         clear_array( to_array( slot.ptr()), array_node_size() );
1160                         break;
1161                     }
1162                     else if ( slot.bits() == flag_array_converting ) {
1163                         // the slot is converting to array node right now
1164                         while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting ) {
1165                             bkoff();
1166                             m_Stat.onSlotConverting();
1167                         }
1168                         bkoff.reset();
1169
1170                         assert( slot.ptr() != nullptr );
1171                         assert(slot.bits() == flag_array_node );
1172                         clear_array( to_array( slot.ptr()), array_node_size() );
1173                         break;
1174                     }
1175                     else {
1176                         // data node
1177                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1178                             if ( slot.ptr() ) {
1179                                 gc::template retire<disposer>( slot.ptr() );
1180                                 --m_ItemCounter;
1181                                 m_Stat.onEraseSuccess();
1182                             }
1183                             break;
1184                         }
1185                     }
1186                 }
1187             }
1188         }
1189
1190         union converter {
1191             value_type * pData;
1192             array_node * pArr;
1193
1194             converter( value_type * p )
1195                 : pData( p )
1196             {}
1197
1198             converter( array_node * p )
1199                 : pArr( p )
1200             {}
1201         };
1202
1203         static array_node * to_array( value_type * p )
1204         {
1205             return converter( p ).pArr;
1206         }
1207         static value_type * to_node( array_node * p )
1208         {
1209             return converter( p ).pData;
1210         }
1211
1212         bool expand_slot( array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset )
1213         {
1214             assert( current.bits() == 0 );
1215             assert( current.ptr() );
1216
1217             size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut( m_Metrics.array_node_size_log );
1218             array_node * pArr = alloc_array_node( pParent, idxParent );
1219
1220             node_ptr cur(current.ptr());
1221             atomic_node_ptr& slot = pParent->nodes[idxParent];
1222             if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
1223             {
1224                 m_Stat.onExpandNodeFailed();
1225                 free_array_node( pArr );
1226                 return false;
1227             }
1228
1229             pArr->nodes[idx].store( current, memory_model::memory_order_release );
1230
1231             cur = cur | flag_array_converting;
1232             CDS_VERIFY(
1233                 slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
1234             );
1235
1236             m_Stat.onArrayNodeCreated();
1237             return true;
1238         }
1239
1240         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1241         {
1242             hash_splitter splitter( hash );
1243             hash_comparator cmp;
1244             back_off bkoff;
1245
1246             array_node * pArr = m_Head;
1247             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1248             assert( nSlot < m_Metrics.head_node_size );
1249
1250             while ( true ) {
1251                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1252                 if ( slot.bits() == flag_array_node ) {
1253                     // array node, go down the tree
1254                     assert( slot.ptr() != nullptr );
1255                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1256                     assert( nSlot < m_Metrics.array_node_size );
1257                     pArr = to_array( slot.ptr() );
1258                 }
1259                 else if ( slot.bits() == flag_array_converting ) {
1260                     // the slot is converting to array node right now
1261                     bkoff();
1262                     m_Stat.onSlotConverting();
1263                 }
1264                 else {
1265                     // data node
1266                     assert(slot.bits() == 0 );
1267
1268                     // protect data node by hazard pointer
1269                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1270                         // slot value has been changed - retry
1271                         m_Stat.onSlotChanged();
1272                     }
1273                     else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1274                         // item found
1275                         m_Stat.onFindSuccess();
1276                         return slot.ptr();
1277                     }
1278                     m_Stat.onFindFailed();
1279                     return nullptr;
1280                 }
1281             } // while
1282         }
1283
1284         template <typename Predicate>
1285         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1286         {
1287             hash_splitter splitter( hash );
1288             hash_comparator cmp;
1289             back_off bkoff;
1290
1291             array_node * pArr = m_Head;
1292             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1293             assert( nSlot < m_Metrics.head_node_size );
1294
1295             while ( true ) {
1296                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1297                 if ( slot.bits() == flag_array_node ) {
1298                     // array node, go down the tree
1299                     assert( slot.ptr() != nullptr );
1300                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1301                     assert( nSlot < m_Metrics.array_node_size );
1302                     pArr = to_array( slot.ptr() );
1303                 }
1304                 else if ( slot.bits() == flag_array_converting ) {
1305                     // the slot is converting to array node right now
1306                     bkoff();
1307                     m_Stat.onSlotConverting();
1308                 }
1309                 else {
1310                     // data node
1311                     assert(slot.bits() == 0 );
1312
1313                     // protect data node by hazard pointer
1314                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1315                         // slot value has been changed - retry
1316                         m_Stat.onSlotChanged();
1317                     }
1318                     else if ( slot.ptr() ) {
1319                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
1320                             // item found - replace it with nullptr
1321                             if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed))
1322                                 return slot.ptr();
1323                             m_Stat.onEraseRetry();
1324                             continue;
1325                         }
1326                         m_Stat.onEraseFailed();
1327                         return nullptr;
1328                     }
1329                     else {
1330                         // the slot is empty
1331                         m_Stat.onEraseFailed();
1332                         return nullptr;
1333                     }
1334                 }
1335             } // while
1336         }
1337
1338         //@endcond
1339     };
1340 }} // namespace cds::intrusive
1341
1342 /*
1343 //@cond
1344 namespace std {
1345
1346     template <class GC, typename T, typename Traits>
1347     struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator >
1348     {
1349         typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator iterator_class;
1350
1351         // difference_type is not applicable for that iterator
1352         // typedef ??? difference_type
1353         typedef T value_type;
1354         typedef typename iterator_class::value_ptr pointer;
1355         typedef typename iterator_class::value_ref reference;
1356         typedef bidirectional_iterator_tag iterator_category;
1357     };
1358
1359     template <class GC, typename T, typename Traits>
1360     struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator >
1361     {
1362         typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator iterator_class;
1363
1364         // difference_type is not applicable for that iterator
1365         // typedef ??? difference_type
1366         typedef T value_type;
1367         typedef typename iterator_class::value_ptr pointer;
1368         typedef typename iterator_class::value_ref reference;
1369         typedef bidirectional_iterator_tag iterator_category;
1370     };
1371
1372 } // namespace std
1373 //@endcond
1374 */
1375
1376 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H