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