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