cds/intrusive/impl/feldman_hashset.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
   4 #define CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
   5
   6 #include <functional>   // std::ref
   7 #include <iterator>     // std::iterator_traits
   8
   9 #include <cds/intrusive/details/feldman_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_FeldmanHashSet_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 %FeldmanHashSet 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 %FeldmanHashSet is a multi-level array which has a structure similar to a tree:
  38         @image html feldman_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 %FeldmanHashSet 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 %FeldmanHashSet:
  59         - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
  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 %FeldmanHashSet.
  64         - \p %FeldmanHashSet 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 %FeldmanHashSet does not maintain the key,
  66           it maintains its fixed-size hash value.
  67
  68         The set supports @ref cds_intrusive_FeldmanHashSet_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 feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
  74             \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_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 %FeldmanHashSet for each \p GC. You should include:
  78         - <tt><cds/intrusive/feldman_hashset_hp.h></tt> for \p gc::HP garbage collector
  79         - <tt><cds/intrusive/feldman_hashset_dhp.h></tt> for \p gc::DHP garbage collector
  80         - <tt><cds/intrusive/feldman_hashset_rcu.h></tt> for \ref cds_intrusive_FeldmanHashSet_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 = feldman_hashset::traits
  88 #else
  89        ,typename Traits
  90 #endif
  91     >
  92     class FeldmanHashSet
  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 feldman_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             feldman_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 feldman_hashset::details::hash_splitter< hash_type > hash_splitter;
 164         //@endcond
 165
 166     protected:
 167         //@cond
 168         class iterator_base
 169         {
 170             friend class FeldmanHashSet;
 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             FeldmanHashSet 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( FeldmanHashSet 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( FeldmanHashSet 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 FeldmanHashSet;
 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( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 458                 : iterator_base( set, pNode, idx, false )
 459             {}
 460
 461             bidirectional_iterator( FeldmanHashSet& 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 FeldmanHashSet;
 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( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 534                 : iterator_base( set, pNode, idx, false )
 535             {}
 536
 537             reverse_bidirectional_iterator( FeldmanHashSet& 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_FeldmanHashSet_iterators "bidirectional iterator" type
 548         typedef implementation_defined const_iterator;      ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
 549         typedef implementation_defined reverse_iterator;    ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
 550         typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_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         feldman_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         FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
 579             : m_Metrics( feldman_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         ~FeldmanHashSet()
 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::FeldmanHashSet< 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::FeldmanHashSet< 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_FeldmanHashSet_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             new ( pNode->nodes ) atomic_node_ptr[ nSize ];
1084             return pNode;
1085         }
1086
1087         static void free_array_node( array_node * parr )
1088         {
1089             cxx_array_node_allocator().Delete( parr );
1090         }
1091
1092         void destroy_tree()
1093         {
1094             // The function is not thread-safe. For use in dtor only
1095             // Remove data node
1096             clear();
1097
1098             // Destroy all array nodes
1099             destroy_array_nodes( m_Head, head_size());
1100         }
1101
1102         void destroy_array_nodes( array_node * pArr, size_t nSize )
1103         {
1104             for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
1105                 node_ptr slot = p->load( memory_model::memory_order_acquire );
1106                 if ( slot.bits() == flag_array_node ) {
1107                     destroy_array_nodes(to_array(slot.ptr()), array_node_size());
1108                     free_array_node( to_array(slot.ptr()));
1109                     p->store(node_ptr(), memory_model::memory_order_relaxed );
1110                 }
1111             }
1112         }
1113
1114         void clear_array( array_node * pArrNode, size_t nSize )
1115         {
1116             back_off bkoff;
1117
1118
1119             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1120                 while ( true ) {
1121                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1122                     if ( slot.bits() == flag_array_node ) {
1123                         // array node, go down the tree
1124                         assert( slot.ptr() != nullptr );
1125                         clear_array( to_array( slot.ptr()), array_node_size() );
1126                         break;
1127                     }
1128                     else if ( slot.bits() == flag_array_converting ) {
1129                         // the slot is converting to array node right now
1130                         while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting ) {
1131                             bkoff();
1132                             m_Stat.onSlotConverting();
1133                         }
1134                         bkoff.reset();
1135
1136                         assert( slot.ptr() != nullptr );
1137                         assert(slot.bits() == flag_array_node );
1138                         clear_array( to_array( slot.ptr()), array_node_size() );
1139                         break;
1140                     }
1141                     else {
1142                         // data node
1143                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1144                             if ( slot.ptr() ) {
1145                                 gc::template retire<disposer>( slot.ptr() );
1146                                 --m_ItemCounter;
1147                                 m_Stat.onEraseSuccess();
1148                             }
1149                             break;
1150                         }
1151                     }
1152                 }
1153             }
1154         }
1155
1156         union converter {
1157             value_type * pData;
1158             array_node * pArr;
1159
1160             converter( value_type * p )
1161                 : pData( p )
1162             {}
1163
1164             converter( array_node * p )
1165                 : pArr( p )
1166             {}
1167         };
1168
1169         static array_node * to_array( value_type * p )
1170         {
1171             return converter( p ).pArr;
1172         }
1173         static value_type * to_node( array_node * p )
1174         {
1175             return converter( p ).pData;
1176         }
1177
1178         bool expand_slot( array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset )
1179         {
1180             assert( current.bits() == 0 );
1181             assert( current.ptr() );
1182
1183             size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut( m_Metrics.array_node_size_log );
1184             array_node * pArr = alloc_array_node( pParent, idxParent );
1185
1186             node_ptr cur(current.ptr());
1187             atomic_node_ptr& slot = pParent->nodes[idxParent];
1188             if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
1189             {
1190                 m_Stat.onExpandNodeFailed();
1191                 free_array_node( pArr );
1192                 return false;
1193             }
1194
1195             pArr->nodes[idx].store( current, memory_model::memory_order_release );
1196
1197             cur = cur | flag_array_converting;
1198             CDS_VERIFY(
1199                 slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
1200             );
1201
1202             m_Stat.onExpandNodeSuccess();
1203             m_Stat.onArrayNodeCreated();
1204             return true;
1205         }
1206         //@endcond
1207
1208     protected:
1209         //@cond
1210         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1211         {
1212             hash_splitter splitter( hash );
1213             hash_comparator cmp;
1214             back_off bkoff;
1215
1216             array_node * pArr = m_Head;
1217             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1218             assert( nSlot < m_Metrics.head_node_size );
1219
1220             while ( true ) {
1221                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1222                 if ( slot.bits() == flag_array_node ) {
1223                     // array node, go down the tree
1224                     assert( slot.ptr() != nullptr );
1225                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1226                     assert( nSlot < m_Metrics.array_node_size );
1227                     pArr = to_array( slot.ptr() );
1228                 }
1229                 else if ( slot.bits() == flag_array_converting ) {
1230                     // the slot is converting to array node right now
1231                     bkoff();
1232                     m_Stat.onSlotConverting();
1233                 }
1234                 else {
1235                     // data node
1236                     assert(slot.bits() == 0 );
1237
1238                     // protect data node by hazard pointer
1239                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1240                         // slot value has been changed - retry
1241                         m_Stat.onSlotChanged();
1242                     }
1243                     else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1244                         // item found
1245                         m_Stat.onFindSuccess();
1246                         return slot.ptr();
1247                     }
1248                     m_Stat.onFindFailed();
1249                     return nullptr;
1250                 }
1251             } // while
1252         }
1253
1254         template <typename Predicate>
1255         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1256         {
1257             hash_splitter splitter( hash );
1258             hash_comparator cmp;
1259             back_off bkoff;
1260
1261             array_node * pArr = m_Head;
1262             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1263             assert( nSlot < m_Metrics.head_node_size );
1264
1265             while ( true ) {
1266                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1267                 if ( slot.bits() == flag_array_node ) {
1268                     // array node, go down the tree
1269                     assert( slot.ptr() != nullptr );
1270                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1271                     assert( nSlot < m_Metrics.array_node_size );
1272                     pArr = to_array( slot.ptr() );
1273                 }
1274                 else if ( slot.bits() == flag_array_converting ) {
1275                     // the slot is converting to array node right now
1276                     bkoff();
1277                     m_Stat.onSlotConverting();
1278                 }
1279                 else {
1280                     // data node
1281                     assert(slot.bits() == 0 );
1282
1283                     // protect data node by hazard pointer
1284                     if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1285                         // slot value has been changed - retry
1286                         m_Stat.onSlotChanged();
1287                     }
1288                     else if ( slot.ptr() ) {
1289                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
1290                             // item found - replace it with nullptr
1291                             if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1292                                 // slot is guarded by HP
1293                                 gc::template retire<disposer>( slot.ptr() );
1294                                 --m_ItemCounter;
1295                                 m_Stat.onEraseSuccess();
1296
1297                                 return slot.ptr();
1298                             }
1299                             m_Stat.onEraseRetry();
1300                             continue;
1301                         }
1302                         m_Stat.onEraseFailed();
1303                         return nullptr;
1304                     }
1305                     else {
1306                         // the slot is empty
1307                         m_Stat.onEraseFailed();
1308                         return nullptr;
1309                     }
1310                 }
1311             } // while
1312         }
1313
1314         bool do_erase_at( iterator_base const& iter )
1315         {
1316             if ( iter.m_set != this )
1317                 return false;
1318             if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
1319                 return false;
1320             if ( iter.m_idx >= array_node_size() )
1321                 return false;
1322
1323             for (;;) {
1324                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1325                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
1326                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1327                         // the item is guarded by iterator, so we may retire it safely
1328                         gc::template retire<disposer>( slot.ptr() );
1329                         --m_ItemCounter;
1330                         m_Stat.onEraseSuccess();
1331                         return true;
1332                     }
1333                 }
1334                 else
1335                     return false;
1336             }
1337         }
1338
1339         template <typename Func>
1340         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1341         {
1342             hash_type const& hash = hash_accessor()( val );
1343             hash_splitter splitter( hash );
1344             hash_comparator cmp;
1345             typename gc::template GuardArray<2> guards;
1346             back_off bkoff;
1347
1348             array_node * pArr = m_Head;
1349             size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1350             assert( nSlot < m_Metrics.head_node_size );
1351             size_t nOffset = m_Metrics.head_node_size_log;
1352             size_t nHeight = 1;
1353
1354             guards.assign( 1, &val );
1355
1356             while ( true ) {
1357                 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1358                 if ( slot.bits() == flag_array_node ) {
1359                     // array node, go down the tree
1360                     assert( slot.ptr() != nullptr );
1361                     nSlot = splitter.cut( m_Metrics.array_node_size_log );
1362                     assert( nSlot < m_Metrics.array_node_size );
1363                     pArr = to_array( slot.ptr() );
1364                     nOffset += m_Metrics.array_node_size_log;
1365                     ++nHeight;
1366                 }
1367                 else if ( slot.bits() == flag_array_converting ) {
1368                     // the slot is converting to array node right now
1369                     bkoff();
1370                     m_Stat.onSlotConverting();
1371                 }
1372                 else {
1373                     // data node
1374                     assert(slot.bits() == 0 );
1375
1376                     // protect data node by hazard pointer
1377                     if ( guards.protect( 0, pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1378                         // slot value has been changed - retry
1379                         m_Stat.onSlotChanged();
1380                     }
1381                     else if ( slot.ptr() ) {
1382                         if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1383                             // the item with that hash value already exists
1384                             // Replace it with val
1385                             if ( slot.ptr() == &val ) {
1386                                 m_Stat.onUpdateExisting();
1387                                 return std::make_pair( true, false );
1388                             }
1389
1390                             if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1391                                 // slot can be disposed
1392                                 f( val, slot.ptr() );
1393                                 gc::template retire<disposer>( slot.ptr() );
1394                                 m_Stat.onUpdateExisting();
1395                                 return std::make_pair( true, false );
1396                             }
1397
1398                             m_Stat.onUpdateRetry();
1399                             continue;
1400                         }
1401
1402                         // the slot must be expanded
1403                         expand_slot( pArr, nSlot, slot, nOffset );
1404                     }
1405                     else {
1406                         // the slot is empty, try to insert data node
1407                         if ( bInsert ) {
1408                             node_ptr pNull;
1409                             if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1410                             {
1411                                 // the new data node has been inserted
1412                                 f( val, nullptr );
1413                                 ++m_ItemCounter;
1414                                 m_Stat.onUpdateNew();
1415                                 m_Stat.height( nHeight );
1416                                 return std::make_pair( true, true );
1417                             }
1418                         }
1419                         else {
1420                             m_Stat.onUpdateFailed();
1421                             return std::make_pair( false, false );
1422                         }
1423
1424                         // insert failed - slot has been changed by another thread
1425                         // retry updating
1426                         m_Stat.onUpdateRetry();
1427                     }
1428                 }
1429             } // while
1430         }
1431         //@endcond
1432     };
1433 }} // namespace cds::intrusive
1434
1435 /*
1436 namespace std {
1437
1438     template <class GC, typename T, typename Traits>
1439     struct iterator_traits< typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::iterator >
1440     {
1441         typedef typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::iterator iterator_class;
1442
1443         // difference_type is not applicable for that iterator
1444         // typedef ??? difference_type
1445         typedef T value_type;
1446         typedef typename iterator_class::value_ptr pointer;
1447         typedef typename iterator_class::value_ref reference;
1448         typedef bidirectional_iterator_tag iterator_category;
1449     };
1450
1451     template <class GC, typename T, typename Traits>
1452     struct iterator_traits< typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::const_iterator >
1453     {
1454         typedef typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::const_iterator iterator_class;
1455
1456         // difference_type is not applicable for that iterator
1457         // typedef ??? difference_type
1458         typedef T value_type;
1459         typedef typename iterator_class::value_ptr pointer;
1460         typedef typename iterator_class::value_ref reference;
1461         typedef bidirectional_iterator_tag iterator_category;
1462     };
1463
1464 } // namespace std
1465 */
1466
1467 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H