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