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             RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
 900             because erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
 901             while your thread is iterating.
 902
 903             A typical example is:
 904             \code
 905             struct foo {
 906                 uint32_t    hash;
 907                 // ... other fields
 908                 uint32_t    payload; // only for example
 909             };
 910             struct set_traits: cds::intrusive::feldman_hashset::traits
 911             {
 912                 struct hash_accessor {
 913                     uint32_t operator()( foo const& src ) const
 914                     {
 915                         retur src.hash;
 916                     }
 917                 };
 918             };
 919
 920             typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
 921             typedef cds::intrusive::FeldmanHashSet< rcu, foo, set_traits > set_type;
 922
 923             set_type s;
 924
 925             // ...
 926
 927             // iterate over the set
 928             {
 929                 // lock the RCU.
 930                 typename set_type::rcu_lock l; // scoped RCU lock
 931
 932                 // traverse the set
 933                 for ( auto i = s.begin(); i != s.end(); ++i ) {
 934                     // deal with i. Remember, erasing is prohibited here!
 935                     i->payload++;
 936                 }
 937             } // at this point RCU lock is released
 938             \endcode
 939
 940             Each iterator object supports the common interface:
 941             - dereference operators:
 942                 @code
 943                 value_type [const] * operator ->() noexcept
 944                 value_type [const] & operator *() noexcept
 945                 @endcode
 946             - pre-increment and pre-decrement. Post-operators is not supported
 947             - equality operators <tt>==</tt> and <tt>!=</tt>.
 948                 Iterators are equal iff they point to the same cell of the same array node.
 949                 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
 950                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 951
 952             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 953             in an array node that is being splitted.
 954         */
 955         ///@{
 956
 957         /// Returns an iterator to the beginning of the set
 958         iterator begin()
 959         {
 960             return iterator(*this, head(), size_t(0) - 1);
 961         }
 962
 963         /// Returns an const iterator to the beginning of the set
 964         const_iterator begin() const
 965         {
 966             return const_iterator(*this, head(), size_t(0) - 1);
 967         }
 968
 969         /// Returns an const iterator to the beginning of the set
 970         const_iterator cbegin()
 971         {
 972             return const_iterator(*this, head(), size_t(0) - 1);
 973         }
 974
 975         /// 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.
 976         iterator end()
 977         {
 978             return iterator(*this, head(), head_size(), false);
 979         }
 980
 981         /// 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.
 982         const_iterator end() const
 983         {
 984             return const_iterator(*this, head(), head_size(), false);
 985         }
 986
 987         /// 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.
 988         const_iterator cend()
 989         {
 990             return const_iterator(*this, head(), head_size(), false);
 991         }
 992
 993         /// Returns a reverse iterator to the first element of the reversed set
 994         reverse_iterator rbegin()
 995         {
 996             return reverse_iterator(*this, head(), head_size());
 997         }
 998
 999         /// Returns a const reverse iterator to the first element of the reversed set
1000         const_reverse_iterator rbegin() const
1001         {
1002             return const_reverse_iterator(*this, head(), head_size());
1003         }
1004
1005         /// Returns a const reverse iterator to the first element of the reversed set
1006         const_reverse_iterator crbegin()
1007         {
1008             return const_reverse_iterator(*this, head(), head_size());
1009         }
1010
1011         /// Returns a reverse iterator to the element following the last element of the reversed set
1012         /**
1013         It corresponds to the element preceding the first element of the non-reversed container.
1014         This element acts as a placeholder, attempting to access it results in undefined behavior.
1015         */
1016         reverse_iterator rend()
1017         {
1018             return reverse_iterator(*this, head(), size_t(0) - 1, false);
1019         }
1020
1021         /// Returns a const reverse iterator to the element following the last element of the reversed set
1022         /**
1023         It corresponds to the element preceding the first element of the non-reversed container.
1024         This element acts as a placeholder, attempting to access it results in undefined behavior.
1025         */
1026         const_reverse_iterator rend() const
1027         {
1028             return const_reverse_iterator(*this, head(), size_t(0) - 1, false);
1029         }
1030
1031         /// Returns a const reverse iterator to the element following the last element of the reversed set
1032         /**
1033         It corresponds to the element preceding the first element of the non-reversed container.
1034         This element acts as a placeholder, attempting to access it results in undefined behavior.
1035         */
1036         const_reverse_iterator crend()
1037         {
1038             return const_reverse_iterator(*this, head(), size_t(0) - 1, false);
1039         }
1040         ///@}
1041
1042     protected:
1043         //@cond
1044         template <typename Func>
1045         std::pair<bool, bool> do_update(value_type& val, Func f, bool bInsert = true)
1046         {
1047             hash_type const& hash = hash_accessor()(val);
1048             traverse_data pos( hash, *this );
1049             hash_comparator cmp;
1050             value_type * pOld;
1051
1052             while ( true ) {
1053                 rcu_lock rcuLock;
1054
1055                 node_ptr slot = base_class::traverse( pos );
1056                 assert(slot.bits() == 0);
1057
1058                 pOld = nullptr;
1059                 if ( pos.pArr->nodes[pos.nSlot].load(memory_model::memory_order_acquire) == slot) {
1060                     if ( slot.ptr()) {
1061                         if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
1062                             // the item with that hash value already exists
1063                             // Replace it with val
1064                             if ( slot.ptr() == &val ) {
1065                                 stats().onUpdateExisting();
1066                                 return std::make_pair(true, false);
1067                             }
1068
1069                             if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1070                                 // slot can be disposed
1071                                 f( val, slot.ptr());
1072                                 pOld = slot.ptr();
1073                                 stats().onUpdateExisting();
1074                                 goto update_existing_done;
1075                             }
1076
1077                             stats().onUpdateRetry();
1078                         }
1079                         else {
1080                             if ( bInsert ) {
1081                                 // the slot must be expanded
1082                                 base_class::expand_slot( pos, slot );
1083                             }
1084                             else {
1085                                 stats().onUpdateFailed();
1086                                 return std::make_pair(false, false);
1087                             }
1088                         }
1089                     }
1090                     else {
1091                         // the slot is empty, try to insert data node
1092                         if (bInsert) {
1093                             node_ptr pNull;
1094                             if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1095                             {
1096                                 // the new data node has been inserted
1097                                 f(val, nullptr);
1098                                 ++m_ItemCounter;
1099                                 stats().onUpdateNew();
1100                                 stats().height( pos.nHeight );
1101                                 return std::make_pair(true, true);
1102                             }
1103                         }
1104                         else {
1105                             stats().onUpdateFailed();
1106                             return std::make_pair(false, false);
1107                         }
1108
1109                         // insert failed - slot has been changed by another thread
1110                         // retry updating
1111                         stats().onUpdateRetry();
1112                     }
1113                 }
1114                 else
1115                     stats().onSlotChanged();
1116             } // while
1117
1118             // update success
1119             // retire_ptr must be called only outside of RCU lock
1120         update_existing_done:
1121             if (pOld)
1122                 gc::template retire_ptr<disposer>(pOld);
1123             return std::make_pair(true, false);
1124         }
1125
1126         template <typename Predicate>
1127         value_type * do_erase( hash_type const& hash, Predicate pred)
1128         {
1129             assert(gc::is_locked());
1130             traverse_data pos( hash, *this );
1131             hash_comparator cmp;
1132
1133             while ( true ) {
1134                 node_ptr slot = base_class::traverse( pos );
1135                 assert( slot.bits() == 0 );
1136
1137                 if ( pos.pArr->nodes[pos.nSlot].load( memory_model::memory_order_acquire ) == slot ) {
1138                     if ( slot.ptr()) {
1139                         if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 && pred( *slot.ptr())) {
1140                             // item found - replace it with nullptr
1141                             if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1142                                 --m_ItemCounter;
1143                                 stats().onEraseSuccess();
1144
1145                                 return slot.ptr();
1146                             }
1147                             stats().onEraseRetry();
1148                             continue;
1149                         }
1150                         stats().onEraseFailed();
1151                         return nullptr;
1152                     }
1153                     else {
1154                         // the slot is empty
1155                         stats().onEraseFailed();
1156                         return nullptr;
1157                     }
1158                 }
1159                 else
1160                     stats().onSlotChanged();
1161             }
1162         }
1163
1164         value_type * search(hash_type const& hash )
1165         {
1166             assert( gc::is_locked());
1167             traverse_data pos( hash, *this );
1168             hash_comparator cmp;
1169
1170             while ( true ) {
1171                 node_ptr slot = base_class::traverse( pos );
1172                 assert( slot.bits() == 0 );
1173
1174                 if ( pos.pArr->nodes[pos.nSlot].load( memory_model::memory_order_acquire ) != slot ) {
1175                     // slot value has been changed - retry
1176                     stats().onSlotChanged();
1177                     continue;
1178                 }
1179                 else if ( slot.ptr() && cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
1180                     // item found
1181                     stats().onFindSuccess();
1182                     return slot.ptr();
1183                 }
1184                 stats().onFindFailed();
1185                 return nullptr;
1186             }
1187         }
1188
1189         //@endcond
1190
1191     private:
1192         //@cond
1193         void clear_array(array_node * pArrNode, size_t nSize)
1194         {
1195             back_off bkoff;
1196
1197
1198             for (atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr) {
1199                 while (true) {
1200                     node_ptr slot = pArr->load(memory_model::memory_order_acquire);
1201                     if (slot.bits() == base_class::flag_array_node ) {
1202                         // array node, go down the tree
1203                         assert(slot.ptr() != nullptr);
1204                         clear_array(to_array(slot.ptr()), array_node_size());
1205                         break;
1206                     }
1207                     else if (slot.bits() == base_class::flag_array_converting ) {
1208                         // the slot is converting to array node right now
1209                         while ((slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1210                             bkoff();
1211                             stats().onSlotConverting();
1212                         }
1213                         bkoff.reset();
1214
1215                         assert(slot.ptr() != nullptr);
1216                         assert(slot.bits() == base_class::flag_array_node );
1217                         clear_array(to_array(slot.ptr()), array_node_size());
1218                         break;
1219                     }
1220                     else {
1221                         // data node
1222                         if (pArr->compare_exchange_strong(slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1223                             if (slot.ptr()) {
1224                                 gc::template retire_ptr<disposer>(slot.ptr());
1225                                 --m_ItemCounter;
1226                                 stats().onEraseSuccess();
1227                             }
1228                             break;
1229                         }
1230                     }
1231                 }
1232             }
1233         }
1234         //@endcond
1235     };
1236
1237 }} // namespace cds::intrusive
1238
1239 #endif  // #ifndef CDSLIB_INTRUSIVE_FELDMAN_HASHSET_RCU_H