cds/intrusive/feldman_hashset_rcu.h

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