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