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::template GuardArray<2> guards;
 591
 592             guards.assign( 1, &val );
 593             while ( true ) {
 594                 node_ptr slot = base_class::traverse( pos );
 595                 assert( slot.bits() == 0 );
 596
 597                 // protect data node by hazard pointer
 598                 if (guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
 599                     // slot value has been changed - retry
 600                     stats().onSlotChanged();
 601                 }
 602
 603                 if (slot.ptr()) {
 604                     if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
 605                         // the item with that hash value already exists
 606                         stats().onInsertFailed();
 607                         return false;
 608                     }
 609
 610                     // the slot must be expanded
 611                     base_class::expand_slot( pos, slot );
 612                 }
 613                 else {
 614                     // the slot is empty, try to insert data node
 615                     node_ptr pNull;
 616                     if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 617                     {
 618                         // the new data node has been inserted
 619                         f(val);
 620                         ++m_ItemCounter;
 621                         stats().onInsertSuccess();
 622                         stats().height(pos.nHeight);
 623                         return true;
 624                     }
 625
 626                     // insert failed - slot has been changed by another thread
 627                     // retry inserting
 628                     stats().onInsertRetry();
 629                 }
 630             }
 631         }
 632
 633         /// Updates the node
 634         /**
 635             Performs inserting or updating the item with hash value equal to \p val.
 636             - If hash value is found then existing item is replaced with \p val, old item is disposed
 637               with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
 638               The function returns <tt> std::pair<true, false> </tt>
 639             - If hash value is not found and \p bInsert is \p true then \p val is inserted,
 640               the function returns <tt> std::pair<true, true> </tt>
 641             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
 642               the function returns <tt> std::pair<false, false> </tt>
 643
 644             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
 645             (i.e. the item has been inserted or updated),
 646             \p second is \p true if new item has been added or \p false if the set contains that hash.
 647         */
 648         std::pair<bool, bool> update( value_type& val, bool bInsert = true )
 649         {
 650             return do_update(val, [](value_type&, value_type *) {}, bInsert );
 651         }
 652
 653         /// Unlinks the item \p val from the set
 654         /**
 655             The function searches the item \p val in the set and unlink it
 656             if it is found and its address is equal to <tt>&val</tt>.
 657
 658             The function returns \p true if success and \p false otherwise.
 659         */
 660         bool unlink( value_type const& val )
 661         {
 662             typename gc::Guard guard;
 663             auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
 664             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 665             return p != nullptr;
 666         }
 667
 668         /// Deletes the item from the set
 669         /**
 670             The function searches \p hash in the set,
 671             unlinks the item found, and returns \p true.
 672             If that item is not found the function returns \p false.
 673
 674             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 675         */
 676         bool erase( hash_type const& hash )
 677         {
 678             return erase(hash, [](value_type const&) {} );
 679         }
 680
 681         /// Deletes the item from the set
 682         /**
 683             The function searches \p hash in the set,
 684             call \p f functor with item found, and unlinks it from the set.
 685             The \ref disposer specified in \p Traits is called
 686             by garbage collector \p GC asynchronously.
 687
 688             The \p Func interface is
 689             \code
 690             struct functor {
 691                 void operator()( value_type& item );
 692             };
 693             \endcode
 694
 695             If \p hash is not found the function returns \p false.
 696         */
 697         template <typename Func>
 698         bool erase( hash_type const& hash, Func f )
 699         {
 700             typename gc::Guard guard;
 701             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 702
 703             // p is guarded by HP
 704             if ( p ) {
 705                 f( *p );
 706                 return true;
 707             }
 708             return false;
 709         }
 710
 711         /// Deletes the item pointed by iterator \p iter
 712         /**
 713             Returns \p true if the operation is successful, \p false otherwise.
 714
 715             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 716         */
 717         bool erase_at( iterator const& iter )
 718         {
 719             return do_erase_at( iter );
 720         }
 721         //@cond
 722         bool erase_at( reverse_iterator const& iter )
 723         {
 724             return do_erase_at( iter );
 725         }
 726         //@endcond
 727
 728         /// Extracts the item with specified \p hash
 729         /**
 730             The function searches \p hash in the set,
 731             unlinks it from the set, and returns an guarded pointer to the item extracted.
 732             If \p hash is not found the function returns an empty guarded pointer.
 733
 734             The \p disposer specified in \p Traits class' template parameter is called automatically
 735             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 736             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 737
 738             Usage:
 739             \code
 740             typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
 741             my_set theSet;
 742             // ...
 743             {
 744                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 745                 if ( gp ) {
 746                     // Deal with gp
 747                     // ...
 748                 }
 749                 // Destructor of gp releases internal HP guard
 750             }
 751             \endcode
 752         */
 753         guarded_ptr extract( hash_type const& hash )
 754         {
 755             guarded_ptr gp;
 756             {
 757                 typename gc::Guard guard;
 758                 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
 759
 760                 // p is guarded by HP
 761                 if ( p )
 762                     gp.reset( p );
 763             }
 764             return gp;
 765         }
 766
 767         /// Finds an item by it's \p hash
 768         /**
 769             The function searches the item by \p hash and calls the functor \p f for item found.
 770             The interface of \p Func functor is:
 771             \code
 772             struct functor {
 773                 void operator()( value_type& item );
 774             };
 775             \endcode
 776             where \p item is the item found.
 777
 778             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 779             that \p item cannot be disposed during the functor is executing.
 780             The functor does not serialize simultaneous access to the set's \p item. If such access is
 781             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 782
 783             The function returns \p true if \p hash is found, \p false otherwise.
 784         */
 785         template <typename Func>
 786         bool find( hash_type const& hash, Func f )
 787         {
 788             typename gc::Guard guard;
 789             value_type * p = search( hash, guard );
 790
 791             // p is guarded by HP
 792             if ( p ) {
 793                 f( *p );
 794                 return true;
 795             }
 796             return false;
 797         }
 798
 799         /// Checks whether the set contains \p hash
 800         /**
 801             The function searches the item by its \p hash
 802             and returns \p true if it is found, or \p false otherwise.
 803         */
 804         bool contains( hash_type const& hash )
 805         {
 806             return find( hash, [](value_type&) {} );
 807         }
 808
 809         /// Finds an item by it's \p hash and returns the item found
 810         /**
 811             The function searches the item by its \p hash
 812             and returns the guarded pointer to the item found.
 813             If \p hash is not found the function returns an empty \p guarded_ptr.
 814
 815             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 816
 817             Usage:
 818             \code
 819             typedef cds::intrusive::FeldmanHashSet< your_template_params >  my_set;
 820             my_set theSet;
 821             // ...
 822             {
 823                 my_set::guarded_ptr gp( theSet.get( 5 ));
 824                 if ( theSet.get( 5 )) {
 825                     // Deal with gp
 826                     //...
 827                 }
 828                 // Destructor of guarded_ptr releases internal HP guard
 829             }
 830             \endcode
 831         */
 832         guarded_ptr get( hash_type const& hash )
 833         {
 834             guarded_ptr gp;
 835             {
 836                 typename gc::Guard guard;
 837                 gp.reset( search( hash, guard ));
 838             }
 839             return gp;
 840         }
 841
 842         /// Clears the set (non-atomic)
 843         /**
 844             The function unlink all data node from the set.
 845             The function is not atomic but is thread-safe.
 846             After \p %clear() the set may not be empty because another threads may insert items.
 847
 848             For each item the \p disposer is called after unlinking.
 849         */
 850         void clear()
 851         {
 852             clear_array( head(), head_size());
 853         }
 854
 855         /// Checks if the set is empty
 856         /**
 857             Emptiness is checked by item counting: if item count is zero then the set is empty.
 858             Thus, the correct item counting feature is an important part of the set implementation.
 859         */
 860         bool empty() const
 861         {
 862             return size() == 0;
 863         }
 864
 865         /// Returns item count in the set
 866         size_t size() const
 867         {
 868             return m_ItemCounter;
 869         }
 870
 871         /// Returns const reference to internal statistics
 872         stat const& statistics() const
 873         {
 874             return stats();
 875         }
 876
 877         /// Returns the size of head node
 878         using base_class::head_size;
 879
 880         /// Returns the size of the array node
 881         using base_class::array_node_size;
 882
 883         /// Collects tree level statistics into \p stat
 884         /** @anchor cds_intrusive_FeldmanHashSet_hp_get_level_statistics
 885             The function traverses the set and collects staistics for each level of the tree
 886             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
 887             represents statistics for level \p i, level 0 is head array.
 888             The function is thread-safe and may be called in multi-threaded environment.
 889
 890             Result can be useful for estimating efficiency of hash functor you use.
 891         */
 892         void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
 893         {
 894             base_class::get_level_statistics( stat );
 895         }
 896
 897     public:
 898     ///@name Thread-safe iterators
 899         /** @anchor cds_intrusive_FeldmanHashSet_iterators
 900             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
 901             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
 902             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
 903
 904             @note Since the iterator object contains hazard pointer that is a thread-local resource,
 905             the iterator should not be passed to another thread.
 906
 907             Each iterator object supports the common interface:
 908             - dereference operators:
 909                 @code
 910                 value_type [const] * operator ->() noexcept
 911                 value_type [const] & operator *() noexcept
 912                 @endcode
 913             - pre-increment and pre-decrement. Post-operators is not supported
 914             - equality operators <tt>==</tt> and <tt>!=</tt>.
 915                 Iterators are equal iff they point to the same cell of the same array node.
 916                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 917                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 918             - helper member function \p release() that clears internal hazard pointer.
 919                 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 920
 921             During iteration you may safely erase any item from the set;
 922             @ref erase_at() function call doesn't invalidate any iterator.
 923             If some iterator points to the item to be erased, that item is not deleted immediately
 924             but only after that iterator will be advanced forward or backward.
 925
 926             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 927             in array node that is being splitted.
 928         */
 929     ///@{
 930
 931         /// Returns an iterator to the beginning of the set
 932         iterator begin()
 933         {
 934             return iterator( *this, head(), size_t(0) - 1 );
 935         }
 936
 937         /// Returns an const iterator to the beginning of the set
 938         const_iterator begin() const
 939         {
 940             return const_iterator( *this, head(), size_t(0) - 1 );
 941         }
 942
 943         /// Returns an const iterator to the beginning of the set
 944         const_iterator cbegin()
 945         {
 946             return const_iterator( *this, head(), size_t(0) - 1 );
 947         }
 948
 949         /// 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.
 950         iterator end()
 951         {
 952             return iterator( *this, head(), head_size(), false );
 953         }
 954
 955         /// 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.
 956         const_iterator end() const
 957         {
 958             return const_iterator( *this, head(), head_size(), false );
 959         }
 960
 961         /// 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.
 962         const_iterator cend()
 963         {
 964             return const_iterator( *this, head(), head_size(), false );
 965         }
 966
 967         /// Returns a reverse iterator to the first element of the reversed set
 968         reverse_iterator rbegin()
 969         {
 970             return reverse_iterator( *this, head(), head_size());
 971         }
 972
 973         /// Returns a const reverse iterator to the first element of the reversed set
 974         const_reverse_iterator rbegin() const
 975         {
 976             return const_reverse_iterator( *this, head(), head_size());
 977         }
 978
 979         /// Returns a const reverse iterator to the first element of the reversed set
 980         const_reverse_iterator crbegin()
 981         {
 982             return const_reverse_iterator( *this, head(), head_size());
 983         }
 984
 985         /// Returns a reverse iterator to the element following the last element of the reversed set
 986         /**
 987             It corresponds to the element preceding the first element of the non-reversed container.
 988             This element acts as a placeholder, attempting to access it results in undefined behavior.
 989         */
 990         reverse_iterator rend()
 991         {
 992             return reverse_iterator( *this, head(), size_t(0) - 1, false );
 993         }
 994
 995         /// Returns a const reverse iterator to the element following the last element of the reversed set
 996         /**
 997             It corresponds to the element preceding the first element of the non-reversed container.
 998             This element acts as a placeholder, attempting to access it results in undefined behavior.
 999         */
1000         const_reverse_iterator rend() const
1001         {
1002             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1003         }
1004
1005         /// Returns a const reverse iterator to the element following the last element of the reversed set
1006         /**
1007             It corresponds to the element preceding the first element of the non-reversed container.
1008             This element acts as a placeholder, attempting to access it results in undefined behavior.
1009         */
1010         const_reverse_iterator crend()
1011         {
1012             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1013         }
1014     ///@}
1015
1016     private:
1017         //@cond
1018         void clear_array( array_node * pArrNode, size_t nSize )
1019         {
1020             back_off bkoff;
1021
1022             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1023                 while ( true ) {
1024                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1025                     if ( slot.bits() == base_class::flag_array_node ) {
1026                         // array node, go down the tree
1027                         assert( slot.ptr() != nullptr );
1028                         clear_array( to_array( slot.ptr()), array_node_size());
1029                         break;
1030                     }
1031                     else if ( slot.bits() == base_class::flag_array_converting ) {
1032                         // the slot is converting to array node right now
1033                         while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1034                             bkoff();
1035                             stats().onSlotConverting();
1036                         }
1037                         bkoff.reset();
1038
1039                         assert( slot.ptr() != nullptr );
1040                         assert( slot.bits() == base_class::flag_array_node );
1041                         clear_array( to_array( slot.ptr()), array_node_size());
1042                         break;
1043                     }
1044                     else {
1045                         // data node
1046                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1047                             if ( slot.ptr()) {
1048                                 gc::template retire<disposer>( slot.ptr());
1049                                 --m_ItemCounter;
1050                                 stats().onEraseSuccess();
1051                             }
1052                             break;
1053                         }
1054                     }
1055                 }
1056             }
1057         }
1058         //@endcond
1059
1060     protected:
1061         //@cond
1062         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1063         {
1064             traverse_data pos( hash, *this );
1065             hash_comparator cmp;
1066
1067             while (true) {
1068                 node_ptr slot = base_class::traverse( pos );
1069                 assert(slot.bits() == 0);
1070
1071                 // protect data node by hazard pointer
1072                 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1073                     // slot value has been changed - retry
1074                     stats().onSlotChanged();
1075                     continue;
1076                 }
1077                 else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1078                     // item found
1079                     stats().onFindSuccess();
1080                     return slot.ptr();
1081                 }
1082                 stats().onFindFailed();
1083                 return nullptr;
1084             }
1085         }
1086
1087         template <typename Predicate>
1088         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1089         {
1090             traverse_data pos( hash, *this );
1091             hash_comparator cmp;
1092             while (true) {
1093                 node_ptr slot = base_class::traverse( pos );
1094                 assert(slot.bits() == 0);
1095
1096                 // protect data node by hazard pointer
1097                 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1098                     // slot value has been changed - retry
1099                     stats().onSlotChanged();
1100                 }
1101                 else if (slot.ptr()) {
1102                     if ( cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) {
1103                         // item found - replace it with nullptr
1104                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1105                             // slot is guarded by HP
1106                             gc::template retire<disposer>(slot.ptr());
1107                             --m_ItemCounter;
1108                             stats().onEraseSuccess();
1109
1110                             return slot.ptr();
1111                         }
1112                         stats().onEraseRetry();
1113                         continue;
1114                     }
1115                     stats().onEraseFailed();
1116                     return nullptr;
1117                 }
1118                 else {
1119                     // the slot is empty
1120                     stats().onEraseFailed();
1121                     return nullptr;
1122                 }
1123             }
1124         }
1125
1126         bool do_erase_at( iterator_base const& iter )
1127         {
1128             if ( iter.m_set != this )
1129                 return false;
1130             if ( iter.m_pNode == head() && iter.m_idx >= head_size())
1131                 return false;
1132             if ( iter.m_idx >= array_node_size())
1133                 return false;
1134
1135             for (;;) {
1136                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1137                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1138                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1139                         // the item is guarded by iterator, so we may retire it safely
1140                         gc::template retire<disposer>( slot.ptr());
1141                         --m_ItemCounter;
1142                         stats().onEraseSuccess();
1143                         return true;
1144                     }
1145                 }
1146                 else
1147                     return false;
1148             }
1149         }
1150
1151         template <typename Func>
1152         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1153         {
1154             hash_type const& hash = hash_accessor()( val );
1155             traverse_data pos( hash, *this );
1156             hash_comparator cmp;
1157             typename gc::template GuardArray<2> guards;
1158
1159             guards.assign( 1, &val );
1160             while (true) {
1161                 node_ptr slot = base_class::traverse( pos );
1162                 assert(slot.bits() == 0);
1163
1164                 // protect data node by hazard pointer
1165                 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1166                     // slot value has been changed - retry
1167                     stats().onSlotChanged();
1168                 }
1169                 else if ( slot.ptr()) {
1170                     if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
1171                         // the item with that hash value already exists
1172                         // Replace it with val
1173                         if ( slot.ptr() == &val ) {
1174                             stats().onUpdateExisting();
1175                             return std::make_pair(true, false);
1176                         }
1177
1178                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1179                             // slot can be disposed
1180                             f( val, slot.ptr());
1181                             gc::template retire<disposer>( slot.ptr());
1182                             stats().onUpdateExisting();
1183                             return std::make_pair(true, false);
1184                         }
1185
1186                         stats().onUpdateRetry();
1187                         continue;
1188                     }
1189
1190                     if ( bInsert ) {
1191                         // the slot must be expanded
1192                         base_class::expand_slot( pos, slot );
1193                     }
1194                     else {
1195                         stats().onUpdateFailed();
1196                         return std::make_pair(false, false);
1197                     }
1198                 }
1199                 else {
1200                     // the slot is empty, try to insert data node
1201                     if ( bInsert ) {
1202                         node_ptr pNull;
1203                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1204                         {
1205                             // the new data node has been inserted
1206                             f(val, nullptr);
1207                             ++m_ItemCounter;
1208                             stats().onUpdateNew();
1209                             stats().height( pos.nHeight );
1210                             return std::make_pair(true, true);
1211                         }
1212                     }
1213                     else {
1214                         stats().onUpdateFailed();
1215                         return std::make_pair(false, false);
1216                     }
1217
1218                     // insert failed - slot has been changed by another thread
1219                     // retry updating
1220                     stats().onUpdateRetry();
1221                 }
1222             } // while
1223         }
1224         //@endcond
1225     };
1226 }} // namespace cds::intrusive
1227
1228 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H