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