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