cds/intrusive/impl/multilevel_hashset.h

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