cds/intrusive/feldman_hashset_rcu.h

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