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: protected feldman_hashset::multilevel_array<T, Traits>
  94     {
  95         typedef feldman_hashset::multilevel_array<T, Traits> base_class;
  96
  97     public:
  98         typedef GC      gc;         ///< Garbage collector
  99         typedef T       value_type; ///< type of value stored in the set
 100         typedef Traits  traits;     ///< Traits template parameter, see \p feldman_hashset::traits
 101
 102         typedef typename traits::hash_accessor hash_accessor;   ///< Hash accessor functor
 103         typedef typename base_class::hash_type hash_type;       ///< Hash type deduced from \p hash_accessor return type
 104         typedef typename traits::disposer disposer;             ///< data node disposer
 105         typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p traits::compare and \p traits::less options
 106
 107         typedef typename traits::item_counter   item_counter;   ///< Item counter type
 108         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
 109         typedef typename traits::memory_model   memory_model;   ///< Memory model
 110         typedef typename traits::back_off       back_off;       ///< Backoff strategy
 111         typedef typename traits::stat           stat;           ///< Internal statistics type
 112
 113         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 114
 115         /// Count of hazard pointers required
 116         static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
 117
 118     protected:
 119         //@cond
 120         typedef typename base_class::node_ptr node_ptr;
 121         typedef typename base_class::atomic_node_ptr atomic_node_ptr;
 122         typedef typename base_class::array_node array_node;
 123         typedef typename base_class::traverse_data traverse_data;
 124
 125         using base_class::to_array;
 126         using base_class::to_node;
 127         using base_class::stats;
 128         using base_class::head;
 129         using base_class::metrics;
 130         //@endcond
 131
 132     protected:
 133         //@cond
 134         class iterator_base
 135         {
 136             friend class FeldmanHashSet;
 137
 138         protected:
 139             array_node *        m_pNode;    ///< current array node
 140             size_t              m_idx;      ///< current position in m_pNode
 141             typename gc::Guard  m_guard;    ///< HP guard
 142             FeldmanHashSet const*  m_set;    ///< Hash set
 143
 144         public:
 145             iterator_base() CDS_NOEXCEPT
 146                 : m_pNode( nullptr )
 147                 , m_idx( 0 )
 148                 , m_set( nullptr )
 149             {}
 150
 151             iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
 152                 : m_pNode( rhs.m_pNode )
 153                 , m_idx( rhs.m_idx )
 154                 , m_set( rhs.m_set )
 155             {
 156                 m_guard.copy( rhs.m_guard );
 157             }
 158
 159             iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
 160             {
 161                 m_pNode = rhs.m_pNode;
 162                 m_idx = rhs.m_idx;
 163                 m_set = rhs.m_set;
 164                 m_guard.copy( rhs.m_guard );
 165                 return *this;
 166             }
 167
 168             iterator_base& operator++()
 169             {
 170                 forward();
 171                 return *this;
 172             }
 173
 174             iterator_base& operator--()
 175             {
 176                 backward();
 177                 return *this;
 178             }
 179
 180             void release()
 181             {
 182                 m_guard.clear();
 183             }
 184
 185             bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
 186             {
 187                 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
 188             }
 189
 190             bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
 191             {
 192                 return !( *this == rhs );
 193             }
 194
 195         protected:
 196             iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
 197                 : m_pNode( pNode )
 198                 , m_idx( idx )
 199                 , m_set( &set )
 200             {}
 201
 202             iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
 203                 : m_pNode( pNode )
 204                 , m_idx( idx )
 205                 , m_set( &set )
 206             {
 207                 forward();
 208             }
 209
 210             value_type * pointer() const CDS_NOEXCEPT
 211             {
 212                 return m_guard.template get<value_type>();
 213             }
 214
 215             void forward()
 216             {
 217                 assert( m_set != nullptr );
 218                 assert( m_pNode != nullptr );
 219
 220                 size_t const arrayNodeSize = m_set->array_node_size();
 221                 size_t const headSize = m_set->head_size();
 222                 array_node * pNode = m_pNode;
 223                 size_t idx = m_idx + 1;
 224                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 225
 226                 for ( ;; ) {
 227                     if ( idx < nodeSize ) {
 228                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 229                         if ( slot.bits() == base_class::flag_array_node ) {
 230                             // array node, go down the tree
 231                             assert( slot.ptr() != nullptr );
 232                             pNode = to_array( slot.ptr() );
 233                             idx = 0;
 234                             nodeSize = arrayNodeSize;
 235                         }
 236                         else if ( slot.bits() == base_class::flag_array_converting ) {
 237                             // the slot is converting to array node right now - skip the node
 238                             ++idx;
 239                         }
 240                         else {
 241                             if ( slot.ptr()) {
 242                                 // data node
 243                                 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
 244                                     m_pNode = pNode;
 245                                     m_idx = idx;
 246                                     return;
 247                                 }
 248                             }
 249                             ++idx;
 250                         }
 251                     }
 252                     else {
 253                         // up to parent node
 254                         if ( pNode->pParent ) {
 255                             idx = pNode->idxParent + 1;
 256                             pNode = pNode->pParent;
 257                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 258                         }
 259                         else {
 260                             // end()
 261                             assert( pNode == m_set->head() );
 262                             assert( idx == headSize );
 263                             m_pNode = pNode;
 264                             m_idx = idx;
 265                             return;
 266                         }
 267                     }
 268                 }
 269             }
 270
 271             void backward()
 272             {
 273                 assert( m_set != nullptr );
 274                 assert( m_pNode != nullptr );
 275
 276                 size_t const arrayNodeSize = m_set->array_node_size();
 277                 size_t const headSize = m_set->head_size();
 278                 size_t const endIdx = size_t(0) - 1;
 279
 280                 array_node * pNode = m_pNode;
 281                 size_t idx = m_idx - 1;
 282                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 283
 284                 for ( ;; ) {
 285                     if ( idx != endIdx ) {
 286                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 287                         if ( slot.bits() == base_class::flag_array_node ) {
 288                             // array node, go down the tree
 289                             assert( slot.ptr() != nullptr );
 290                             pNode = to_array( slot.ptr() );
 291                             nodeSize = arrayNodeSize;
 292                             idx = nodeSize - 1;
 293                         }
 294                         else if ( slot.bits() == base_class::flag_array_converting ) {
 295                             // the slot is converting to array node right now - skip the node
 296                             --idx;
 297                         }
 298                         else {
 299                             if ( slot.ptr()) {
 300                                 // data node
 301                                 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
 302                                     m_pNode = pNode;
 303                                     m_idx = idx;
 304                                     return;
 305                                 }
 306                             }
 307                             --idx;
 308                         }
 309                     }
 310                     else {
 311                         // up to parent node
 312                         if ( pNode->pParent ) {
 313                             idx = pNode->idxParent - 1;
 314                             pNode = pNode->pParent;
 315                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 316                         }
 317                         else {
 318                             // rend()
 319                             assert( pNode == m_set->head() );
 320                             assert( idx == endIdx );
 321                             m_pNode = pNode;
 322                             m_idx = idx;
 323                             return;
 324                         }
 325                     }
 326                 }
 327             }
 328         };
 329
 330         template <class Iterator>
 331         Iterator init_begin() const
 332         {
 333             return Iterator( *this, head(), size_t(0) - 1 );
 334         }
 335
 336         template <class Iterator>
 337         Iterator init_end() const
 338         {
 339             return Iterator( *this, head(), head_size(), false );
 340         }
 341
 342         template <class Iterator>
 343         Iterator init_rbegin() const
 344         {
 345             return Iterator( *this, head(), head_size() );
 346         }
 347
 348         template <class Iterator>
 349         Iterator init_rend() const
 350         {
 351             return Iterator( *this, head(), size_t(0) - 1, false );
 352         }
 353
 354         /// Bidirectional iterator class
 355         template <bool IsConst>
 356         class bidirectional_iterator: protected iterator_base
 357         {
 358             friend class FeldmanHashSet;
 359
 360         protected:
 361             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
 362
 363         public:
 364             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 365             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 366
 367         public:
 368             bidirectional_iterator() CDS_NOEXCEPT
 369             {}
 370
 371             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 372                 : iterator_base( rhs )
 373             {}
 374
 375             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
 376             {
 377                 iterator_base::operator=( rhs );
 378                 return *this;
 379             }
 380
 381             bidirectional_iterator& operator++()
 382             {
 383                 iterator_base::operator++();
 384                 return *this;
 385             }
 386
 387             bidirectional_iterator& operator--()
 388             {
 389                 iterator_base::operator--();
 390                 return *this;
 391             }
 392
 393             value_ptr operator ->() const CDS_NOEXCEPT
 394             {
 395                 return iterator_base::pointer();
 396             }
 397
 398             value_ref operator *() const CDS_NOEXCEPT
 399             {
 400                 value_ptr p = iterator_base::pointer();
 401                 assert( p );
 402                 return *p;
 403             }
 404
 405             void release()
 406             {
 407                 iterator_base::release();
 408             }
 409
 410             template <bool IsConst2>
 411             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 412             {
 413                 return iterator_base::operator==( rhs );
 414             }
 415
 416             template <bool IsConst2>
 417             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 418             {
 419                 return !( *this == rhs );
 420             }
 421
 422         protected:
 423             bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 424                 : iterator_base( set, pNode, idx, false )
 425             {}
 426
 427             bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
 428                 : iterator_base( set, pNode, idx )
 429             {}
 430         };
 431
 432         /// Reverse bidirectional iterator
 433         template <bool IsConst>
 434         class reverse_bidirectional_iterator : public iterator_base
 435         {
 436             friend class FeldmanHashSet;
 437
 438         public:
 439             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 440             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 441
 442         public:
 443             reverse_bidirectional_iterator() CDS_NOEXCEPT
 444                 : iterator_base()
 445             {}
 446
 447             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 448                 : iterator_base( rhs )
 449             {}
 450
 451             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 452             {
 453                 iterator_base::operator=( rhs );
 454                 return *this;
 455             }
 456
 457             reverse_bidirectional_iterator& operator++()
 458             {
 459                 iterator_base::operator--();
 460                 return *this;
 461             }
 462
 463             reverse_bidirectional_iterator& operator--()
 464             {
 465                 iterator_base::operator++();
 466                 return *this;
 467             }
 468
 469             value_ptr operator ->() const CDS_NOEXCEPT
 470             {
 471                 return iterator_base::pointer();
 472             }
 473
 474             value_ref operator *() const CDS_NOEXCEPT
 475             {
 476                 value_ptr p = iterator_base::pointer();
 477                 assert( p );
 478                 return *p;
 479             }
 480
 481             void release()
 482             {
 483                 iterator_base::release();
 484             }
 485
 486             template <bool IsConst2>
 487             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
 488             {
 489                 return iterator_base::operator==( rhs );
 490             }
 491
 492             template <bool IsConst2>
 493             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
 494             {
 495                 return !( *this == rhs );
 496             }
 497
 498         private:
 499             reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 500                 : iterator_base( set, pNode, idx, false )
 501             {}
 502
 503             reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
 504                 : iterator_base( set, pNode, idx, false )
 505             {
 506                 iterator_base::backward();
 507             }
 508         };
 509         //@endcond
 510
 511     public:
 512 #ifdef CDS_DOXYGEN_INVOKED
 513         typedef implementation_defined iterator;            ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
 514         typedef implementation_defined const_iterator;      ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
 515         typedef implementation_defined reverse_iterator;    ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
 516         typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
 517 #else
 518         typedef bidirectional_iterator<false>   iterator;
 519         typedef bidirectional_iterator<true>    const_iterator;
 520         typedef reverse_bidirectional_iterator<false>   reverse_iterator;
 521         typedef reverse_bidirectional_iterator<true>    const_reverse_iterator;
 522 #endif
 523
 524     private:
 525         //@cond
 526         item_counter      m_ItemCounter; ///< Item counter
 527         //@endcond
 528
 529     public:
 530         /// Creates empty set
 531         /**
 532             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 533             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 534
 535             Equation for \p head_bits and \p array_bits:
 536             \code
 537             sizeof(hash_type) * 8 == head_bits + N * array_bits
 538             \endcode
 539             where \p N is multi-level array depth.
 540         */
 541         FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
 542             : base_class( head_bits, array_bits )
 543         {}
 544
 545         /// Destructs the set and frees all data
 546         ~FeldmanHashSet()
 547         {
 548             clear();
 549         }
 550
 551         /// Inserts new node
 552         /**
 553             The function inserts \p val in the set if it does not contain
 554             an item with that hash.
 555
 556             Returns \p true if \p val is placed into the set, \p false otherwise.
 557         */
 558         bool insert( value_type& val )
 559         {
 560             return insert( val, [](value_type&) {} );
 561         }
 562
 563         /// Inserts new node
 564         /**
 565             This function is intended for derived non-intrusive containers.
 566
 567             The function allows to split creating of new item into two part:
 568             - create item with key only
 569             - insert new item into the set
 570             - if inserting is success, calls \p f functor to initialize \p val.
 571
 572             The functor signature is:
 573             \code
 574                 void func( value_type& val );
 575             \endcode
 576             where \p val is the item inserted.
 577
 578             The user-defined functor is called only if the inserting is success.
 579
 580             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
 581         */
 582         template <typename Func>
 583         bool insert( value_type& val, Func f )
 584         {
 585             hash_type const& hash = hash_accessor()(val);
 586             traverse_data pos( hash, *this );
 587             hash_comparator cmp;
 588             typename gc::Guard guard;
 589
 590             while (true) {
 591                 node_ptr slot = base_class::traverse( pos );
 592                 assert( slot.bits() == 0 );
 593
 594                 // protect data node by hazard pointer
 595                 if (guard.protect(pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
 596                     // slot value has been changed - retry
 597                     stats().onSlotChanged();
 598                 }
 599
 600                 if (slot.ptr()) {
 601                     if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
 602                         // the item with that hash value already exists
 603                         stats().onInsertFailed();
 604                         return false;
 605                     }
 606
 607                     // the slot must be expanded
 608                     base_class::expand_slot( pos, slot );
 609                 }
 610                 else {
 611                     // the slot is empty, try to insert data node
 612                     node_ptr pNull;
 613                     if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
 614                     {
 615                         // the new data node has been inserted
 616                         f(val);
 617                         ++m_ItemCounter;
 618                         stats().onInsertSuccess();
 619                         stats().height(pos.nHeight);
 620                         return true;
 621                     }
 622
 623                     // insert failed - slot has been changed by another thread
 624                     // retry inserting
 625                     stats().onInsertRetry();
 626                 }
 627             }
 628         }
 629
 630         /// Updates the node
 631         /**
 632             Performs inserting or updating the item with hash value equal to \p val.
 633             - If hash value is found then existing item is replaced with \p val, old item is disposed
 634               with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
 635               The function returns <tt> std::pair<true, false> </tt>
 636             - If hash value is not found and \p bInsert is \p true then \p val is inserted,
 637               the function returns <tt> std::pair<true, true> </tt>
 638             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
 639               the function returns <tt> std::pair<false, false> </tt>
 640
 641             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
 642             (i.e. the item has been inserted or updated),
 643             \p second is \p true if new item has been added or \p false if the set contains that hash.
 644         */
 645         std::pair<bool, bool> update( value_type& val, bool bInsert = true )
 646         {
 647             return do_update(val, [](value_type&, value_type *) {}, bInsert );
 648         }
 649
 650         /// Unlinks the item \p val from the set
 651         /**
 652             The function searches the item \p val in the set and unlink it
 653             if it is found and its address is equal to <tt>&val</tt>.
 654
 655             The function returns \p true if success and \p false otherwise.
 656         */
 657         bool unlink( value_type const& val )
 658         {
 659             typename gc::Guard guard;
 660             auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
 661             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 662             return p != nullptr;
 663         }
 664
 665         /// Deletes the item from the set
 666         /**
 667             The function searches \p hash in the set,
 668             unlinks the item found, and returns \p true.
 669             If that item is not found the function returns \p false.
 670
 671             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 672         */
 673         bool erase( hash_type const& hash )
 674         {
 675             return erase(hash, [](value_type const&) {} );
 676         }
 677
 678         /// Deletes the item from the set
 679         /**
 680             The function searches \p hash in the set,
 681             call \p f functor with item found, and unlinks it from the set.
 682             The \ref disposer specified in \p Traits is called
 683             by garbage collector \p GC asynchronously.
 684
 685             The \p Func interface is
 686             \code
 687             struct functor {
 688                 void operator()( value_type& item );
 689             };
 690             \endcode
 691
 692             If \p hash is not found the function returns \p false.
 693         */
 694         template <typename Func>
 695         bool erase( hash_type const& hash, Func f )
 696         {
 697             typename gc::Guard guard;
 698             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 699
 700             // p is guarded by HP
 701             if ( p ) {
 702                 f( *p );
 703                 return true;
 704             }
 705             return false;
 706         }
 707
 708         /// Deletes the item pointed by iterator \p iter
 709         /**
 710             Returns \p true if the operation is successful, \p false otherwise.
 711
 712             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 713         */
 714         bool erase_at( iterator const& iter )
 715         {
 716             return do_erase_at( iter );
 717         }
 718         //@cond
 719         bool erase_at( reverse_iterator const& iter )
 720         {
 721             return do_erase_at( iter );
 722         }
 723         //@endcond
 724
 725         /// Extracts the item with specified \p hash
 726         /**
 727             The function searches \p hash in the set,
 728             unlinks it from the set, and returns an guarded pointer to the item extracted.
 729             If \p hash is not found the function returns an empty guarded pointer.
 730
 731             The \p disposer specified in \p Traits class' template parameter is called automatically
 732             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 733             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 734
 735             Usage:
 736             \code
 737             typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
 738             my_set theSet;
 739             // ...
 740             {
 741                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 742                 if ( gp ) {
 743                     // Deal with gp
 744                     // ...
 745                 }
 746                 // Destructor of gp releases internal HP guard
 747             }
 748             \endcode
 749         */
 750         guarded_ptr extract( hash_type const& hash )
 751         {
 752             guarded_ptr gp;
 753             {
 754                 typename gc::Guard guard;
 755                 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
 756
 757                 // p is guarded by HP
 758                 if ( p )
 759                     gp.reset( p );
 760             }
 761             return gp;
 762         }
 763
 764         /// Finds an item by it's \p hash
 765         /**
 766             The function searches the item by \p hash and calls the functor \p f for item found.
 767             The interface of \p Func functor is:
 768             \code
 769             struct functor {
 770                 void operator()( value_type& item );
 771             };
 772             \endcode
 773             where \p item is the item found.
 774
 775             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 776             that \p item cannot be disposed during the functor is executing.
 777             The functor does not serialize simultaneous access to the set's \p item. If such access is
 778             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 779
 780             The function returns \p true if \p hash is found, \p false otherwise.
 781         */
 782         template <typename Func>
 783         bool find( hash_type const& hash, Func f )
 784         {
 785             typename gc::Guard guard;
 786             value_type * p = search( hash, guard );
 787
 788             // p is guarded by HP
 789             if ( p ) {
 790                 f( *p );
 791                 return true;
 792             }
 793             return false;
 794         }
 795
 796         /// Checks whether the set contains \p hash
 797         /**
 798             The function searches the item by its \p hash
 799             and returns \p true if it is found, or \p false otherwise.
 800         */
 801         bool contains( hash_type const& hash )
 802         {
 803             return find( hash, [](value_type&) {} );
 804         }
 805
 806         /// Finds an item by it's \p hash and returns the item found
 807         /**
 808             The function searches the item by its \p hash
 809             and returns the guarded pointer to the item found.
 810             If \p hash is not found the function returns an empty \p guarded_ptr.
 811
 812             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 813
 814             Usage:
 815             \code
 816             typedef cds::intrusive::FeldmanHashSet< your_template_params >  my_set;
 817             my_set theSet;
 818             // ...
 819             {
 820                 my_set::guarded_ptr gp( theSet.get( 5 ));
 821                 if ( theSet.get( 5 )) {
 822                     // Deal with gp
 823                     //...
 824                 }
 825                 // Destructor of guarded_ptr releases internal HP guard
 826             }
 827             \endcode
 828         */
 829         guarded_ptr get( hash_type const& hash )
 830         {
 831             guarded_ptr gp;
 832             {
 833                 typename gc::Guard guard;
 834                 gp.reset( search( hash, guard ));
 835             }
 836             return gp;
 837         }
 838
 839         /// Clears the set (non-atomic)
 840         /**
 841             The function unlink all data node from the set.
 842             The function is not atomic but is thread-safe.
 843             After \p %clear() the set may not be empty because another threads may insert items.
 844
 845             For each item the \p disposer is called after unlinking.
 846         */
 847         void clear()
 848         {
 849             clear_array( head(), head_size() );
 850         }
 851
 852         /// Checks if the set is empty
 853         /**
 854             Emptiness is checked by item counting: if item count is zero then the set is empty.
 855             Thus, the correct item counting feature is an important part of the set implementation.
 856         */
 857         bool empty() const
 858         {
 859             return size() == 0;
 860         }
 861
 862         /// Returns item count in the set
 863         size_t size() const
 864         {
 865             return m_ItemCounter;
 866         }
 867
 868         /// Returns const reference to internal statistics
 869         stat const& statistics() const
 870         {
 871             return stats();
 872         }
 873
 874         /// Returns the size of head node
 875         using base_class::head_size;
 876
 877         /// Returns the size of the array node
 878         using base_class::array_node_size;
 879
 880         /// Collects tree level statistics into \p stat
 881         /** @anchor cds_intrusive_FeldmanHashSet_hp_get_level_statistics
 882             The function traverses the set and collects staistics for each level of the tree
 883             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
 884             represents statistics for level \p i, level 0 is head array.
 885             The function is thread-safe and may be called in multi-threaded environment.
 886
 887             Result can be useful for estimating efficiency of hash functor you use.
 888         */
 889         void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
 890         {
 891             base_class::get_level_statistics( stat );
 892         }
 893
 894     public:
 895     ///@name Thread-safe iterators
 896         /** @anchor cds_intrusive_FeldmanHashSet_iterators
 897             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
 898             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
 899             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
 900
 901             @note Since the iterator object contains hazard pointer that is a thread-local resource,
 902             the iterator should not be passed to another thread.
 903
 904             Each iterator object supports the common interface:
 905             - dereference operators:
 906                 @code
 907                 value_type [const] * operator ->() noexcept
 908                 value_type [const] & operator *() noexcept
 909                 @endcode
 910             - pre-increment and pre-decrement. Post-operators is not supported
 911             - equality operators <tt>==</tt> and <tt>!=</tt>.
 912                 Iterators are equal iff they point to the same cell of the same array node.
 913                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 914                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 915             - helper member function \p release() that clears internal hazard pointer.
 916                 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 917
 918             During iteration you may safely erase any item from the set;
 919             @ref erase_at() function call doesn't invalidate any iterator.
 920             If some iterator points to the item to be erased, that item is not deleted immediately
 921             but only after that iterator will be advanced forward or backward.
 922
 923             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 924             in array node that is being splitted.
 925         */
 926     ///@{
 927
 928         /// Returns an iterator to the beginning of the set
 929         iterator begin()
 930         {
 931             return iterator( *this, head(), size_t(0) - 1 );
 932         }
 933
 934         /// Returns an const iterator to the beginning of the set
 935         const_iterator begin() const
 936         {
 937             return const_iterator( *this, head(), size_t(0) - 1 );
 938         }
 939
 940         /// Returns an const iterator to the beginning of the set
 941         const_iterator cbegin()
 942         {
 943             return const_iterator( *this, head(), size_t(0) - 1 );
 944         }
 945
 946         /// 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.
 947         iterator end()
 948         {
 949             return iterator( *this, head(), head_size(), false );
 950         }
 951
 952         /// 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.
 953         const_iterator end() const
 954         {
 955             return const_iterator( *this, head(), head_size(), false );
 956         }
 957
 958         /// 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.
 959         const_iterator cend()
 960         {
 961             return const_iterator( *this, head(), head_size(), false );
 962         }
 963
 964         /// Returns a reverse iterator to the first element of the reversed set
 965         reverse_iterator rbegin()
 966         {
 967             return reverse_iterator( *this, head(), head_size() );
 968         }
 969
 970         /// Returns a const reverse iterator to the first element of the reversed set
 971         const_reverse_iterator rbegin() const
 972         {
 973             return const_reverse_iterator( *this, head(), head_size() );
 974         }
 975
 976         /// Returns a const reverse iterator to the first element of the reversed set
 977         const_reverse_iterator crbegin()
 978         {
 979             return const_reverse_iterator( *this, head(), head_size() );
 980         }
 981
 982         /// Returns a reverse iterator to the element following the last element of the reversed set
 983         /**
 984             It corresponds to the element preceding the first element of the non-reversed container.
 985             This element acts as a placeholder, attempting to access it results in undefined behavior.
 986         */
 987         reverse_iterator rend()
 988         {
 989             return reverse_iterator( *this, head(), size_t(0) - 1, false );
 990         }
 991
 992         /// Returns a const reverse iterator to the element following the last element of the reversed set
 993         /**
 994             It corresponds to the element preceding the first element of the non-reversed container.
 995             This element acts as a placeholder, attempting to access it results in undefined behavior.
 996         */
 997         const_reverse_iterator rend() const
 998         {
 999             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1000         }
1001
1002         /// Returns a const reverse iterator to the element following the last element of the reversed set
1003         /**
1004             It corresponds to the element preceding the first element of the non-reversed container.
1005             This element acts as a placeholder, attempting to access it results in undefined behavior.
1006         */
1007         const_reverse_iterator crend()
1008         {
1009             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1010         }
1011     ///@}
1012
1013     private:
1014         //@cond
1015         void clear_array( array_node * pArrNode, size_t nSize )
1016         {
1017             back_off bkoff;
1018
1019             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1020                 while ( true ) {
1021                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1022                     if ( slot.bits() == base_class::flag_array_node ) {
1023                         // array node, go down the tree
1024                         assert( slot.ptr() != nullptr );
1025                         clear_array( to_array( slot.ptr()), array_node_size() );
1026                         break;
1027                     }
1028                     else if ( slot.bits() == base_class::flag_array_converting ) {
1029                         // the slot is converting to array node right now
1030                         while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1031                             bkoff();
1032                             stats().onSlotConverting();
1033                         }
1034                         bkoff.reset();
1035
1036                         assert( slot.ptr() != nullptr );
1037                         assert( slot.bits() == base_class::flag_array_node );
1038                         clear_array( to_array( slot.ptr()), array_node_size() );
1039                         break;
1040                     }
1041                     else {
1042                         // data node
1043                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1044                             if ( slot.ptr() ) {
1045                                 gc::template retire<disposer>( slot.ptr() );
1046                                 --m_ItemCounter;
1047                                 stats().onEraseSuccess();
1048                             }
1049                             break;
1050                         }
1051                     }
1052                 }
1053             }
1054         }
1055         //@endcond
1056
1057     protected:
1058         //@cond
1059         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1060         {
1061             traverse_data pos( hash, *this );
1062             hash_comparator cmp;
1063
1064             while (true) {
1065                 node_ptr slot = base_class::traverse( pos );
1066                 assert(slot.bits() == 0);
1067
1068                 // protect data node by hazard pointer
1069                 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1070                     // slot value has been changed - retry
1071                     stats().onSlotChanged();
1072                 }
1073                 else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1074                     // item found
1075                     stats().onFindSuccess();
1076                     return slot.ptr();
1077                 }
1078                 stats().onFindFailed();
1079                 return nullptr;
1080             }
1081         }
1082
1083         template <typename Predicate>
1084         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1085         {
1086             traverse_data pos( hash, *this );
1087             hash_comparator cmp;
1088             while (true) {
1089                 node_ptr slot = base_class::traverse( pos );
1090                 assert(slot.bits() == 0);
1091
1092                 // protect data node by hazard pointer
1093                 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1094                     // slot value has been changed - retry
1095                     stats().onSlotChanged();
1096                 }
1097                 else if (slot.ptr()) {
1098                     if (cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) {
1099                         // item found - replace it with nullptr
1100                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1101                             // slot is guarded by HP
1102                             gc::template retire<disposer>(slot.ptr());
1103                             --m_ItemCounter;
1104                             stats().onEraseSuccess();
1105
1106                             return slot.ptr();
1107                         }
1108                         stats().onEraseRetry();
1109                         continue;
1110                     }
1111                     stats().onEraseFailed();
1112                     return nullptr;
1113                 }
1114                 else {
1115                     // the slot is empty
1116                     stats().onEraseFailed();
1117                     return nullptr;
1118                 }
1119             }
1120         }
1121
1122         bool do_erase_at( iterator_base const& iter )
1123         {
1124             if ( iter.m_set != this )
1125                 return false;
1126             if ( iter.m_pNode == head() && iter.m_idx >= head_size())
1127                 return false;
1128             if ( iter.m_idx >= array_node_size() )
1129                 return false;
1130
1131             for (;;) {
1132                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1133                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
1134                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1135                         // the item is guarded by iterator, so we may retire it safely
1136                         gc::template retire<disposer>( slot.ptr() );
1137                         --m_ItemCounter;
1138                         stats().onEraseSuccess();
1139                         return true;
1140                     }
1141                 }
1142                 else
1143                     return false;
1144             }
1145         }
1146
1147         template <typename Func>
1148         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1149         {
1150             hash_type const& hash = hash_accessor()( val );
1151             traverse_data pos( hash, *this );
1152             hash_comparator cmp;
1153             typename gc::template GuardArray<2> guards;
1154
1155             while (true) {
1156                 node_ptr slot = base_class::traverse( pos );
1157                 assert(slot.bits() == 0);
1158
1159                 // protect data node by hazard pointer
1160                 if (guards.protect(0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1161                     // slot value has been changed - retry
1162                     stats().onSlotChanged();
1163                 }
1164                 else if (slot.ptr()) {
1165                     if (cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1166                         // the item with that hash value already exists
1167                         // Replace it with val
1168                         if (slot.ptr() == &val) {
1169                             stats().onUpdateExisting();
1170                             return std::make_pair(true, false);
1171                         }
1172
1173                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1174                             // slot can be disposed
1175                             f(val, slot.ptr());
1176                             gc::template retire<disposer>(slot.ptr());
1177                             stats().onUpdateExisting();
1178                             return std::make_pair(true, false);
1179                         }
1180
1181                         stats().onUpdateRetry();
1182                         continue;
1183                     }
1184
1185                     if ( bInsert ) {
1186                         // the slot must be expanded
1187                         base_class::expand_slot( pos, slot );
1188                     }
1189                     else {
1190                         stats().onUpdateFailed();
1191                         return std::make_pair(false, false);
1192                     }
1193                 }
1194                 else {
1195                     // the slot is empty, try to insert data node
1196                     if (bInsert) {
1197                         node_ptr pNull;
1198                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1199                         {
1200                             // the new data node has been inserted
1201                             f(val, nullptr);
1202                             ++m_ItemCounter;
1203                             stats().onUpdateNew();
1204                             stats().height( pos.nHeight );
1205                             return std::make_pair(true, true);
1206                         }
1207                     }
1208                     else {
1209                         stats().onUpdateFailed();
1210                         return std::make_pair(false, false);
1211                     }
1212
1213                     // insert failed - slot has been changed by another thread
1214                     // retry updating
1215                     stats().onUpdateRetry();
1216                 }
1217             } // while
1218         }
1219         //@endcond
1220     };
1221 }} // namespace cds::intrusive
1222
1223 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H