cds/intrusive/split_list_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
   4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
   5
   6 #include <limits>
   7
   8 #include <cds/intrusive/details/split_list_base.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10
  11 namespace cds { namespace intrusive {
  12
  13     /// Split-ordered list RCU specialization
  14     /** @ingroup cds_intrusive_map
  15         \anchor cds_intrusive_SplitListSet_rcu
  16
  17         Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
  18         - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
  19         - [2008] Nir Shavit "The Art of Multiprocessor Programming"
  20
  21         The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
  22         recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
  23         without moving an item on resizing, see \ref cds_SplitList_algo_desc "short algo description".
  24
  25         <b>Implementation</b>
  26
  27         Template parameters are:
  28         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  29         - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
  30             The intrusive ordered list implementation specifies the type \p T stored in the hash-set,
  31             the comparing functor for the type \p T and other features specific for the ordered list.
  32         - \p Traits - set traits, default isd \p split_list::traits.
  33             Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
  34
  35         @note About reqired features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
  36
  37         \par How to use
  38         Before including <tt><cds/intrusive/split_list_rcu.h></tt> you should include appropriate RCU header file,
  39         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  40         For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" and
  41         MichaelList-based split-list you should include:
  42         \code
  43         #include <cds/urcu/general_buffered.h>
  44         #include <cds/intrusive/michael_list_rcu.h>
  45         #include <cds/intrusive/split_list_rcu.h>
  46
  47         // Declare Michael's list for type Foo and default traits:
  48         typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
  49
  50         // Declare split-list based on rcu_michael_list
  51         typedef cds::intrusive::SplitListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, rcu_michael_list > rcu_split_list;
  52         \endcode
  53
  54     */
  55     template <
  56         class RCU,
  57         class OrderedList,
  58 #   ifdef CDS_DOXYGEN_INVOKED
  59         class Traits = split_list::traits
  60 #   else
  61         class Traits
  62 #   endif
  63     >
  64     class SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
  65     {
  66     public:
  67         typedef cds::urcu::gc< RCU > gc;   ///< RCU garbage collector
  68         typedef Traits           traits;   ///< Traits template parameters
  69
  70         /// Hash functor for \ref value_type and all its derivatives that you use
  71         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
  72
  73     protected:
  74         //@cond
  75         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
  76         //@endcond
  77
  78     public:
  79 #   ifdef CDS_DOXYGEN_INVOKED
  80         typedef OrderedList         ordered_list;   ///< type of ordered list used as base for split-list
  81 #   else
  82         typedef typename wrapped_ordered_list::result    ordered_list;
  83 #   endif
  84         typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the split-list
  85         typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
  86         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
  87         typedef typename ordered_list::rcu_lock       rcu_lock;       ///< RCU scoped lock
  88         typedef typename ordered_list::exempt_ptr     exempt_ptr;     ///< pointer to extracted node
  89         typedef typename ordered_list::raw_ptr        raw_ptr;        ///< pointer to the node for \p get() function
  90         /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
  91         static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
  92
  93         typedef typename traits::item_counter item_counter; ///< Item counter type
  94         typedef typename traits::back_off     back_off;     ///< back-off strategy for spinning
  95         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
  96         typedef typename traits::stat         stat;         ///< Internal statistics
  97
  98     protected:
  99         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
 100         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
 101         typedef node_type                           dummy_node_type; ///< dummy node type
 102
 103         /// Split-list node traits
 104         /**
 105             This traits is intended for converting between underlying ordered list node type \ref list_node_type
 106             and split-list node type \ref node_type
 107         */
 108         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 109
 110         //@cond
 111         /// Bucket table implementation
 112         typedef typename split_list::details::bucket_table_selector<
 113             traits::dynamic_bucket_table
 114             , gc
 115             , dummy_node_type
 116             , opt::allocator< typename traits::allocator >
 117             , opt::memory_model< memory_model >
 118         >::type bucket_table;
 119
 120         //@endcond
 121
 122     protected:
 123         //@cond
 124         /// Ordered list wrapper to access protected members of OrderedList
 125         class ordered_list_wrapper: public ordered_list
 126         {
 127             typedef ordered_list base_class;
 128             typedef typename base_class::auxiliary_head       bucket_head_type;
 129
 130         public:
 131             bool insert_at( dummy_node_type * pHead, value_type& val )
 132             {
 133                 assert( pHead != nullptr );
 134                 bucket_head_type h(pHead);
 135                 return base_class::insert_at( h, val );
 136             }
 137
 138             template <typename Func>
 139             bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
 140             {
 141                 assert( pHead != nullptr );
 142                 bucket_head_type h(pHead);
 143                 return base_class::insert_at( h, val, f );
 144             }
 145
 146             template <typename Func>
 147             std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 148             {
 149                 assert( pHead != nullptr );
 150                 bucket_head_type h(pHead);
 151                 return base_class::update_at( h, val, func, bAllowInsert );
 152             }
 153
 154             bool unlink_at( dummy_node_type * pHead, value_type& val )
 155             {
 156                 assert( pHead != nullptr );
 157                 bucket_head_type h(pHead);
 158                 return base_class::unlink_at( h, val );
 159             }
 160
 161             template <typename Q, typename Compare, typename Func>
 162             bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
 163             {
 164                 assert( pHead != nullptr );
 165                 bucket_head_type h(pHead);
 166                 return base_class::erase_at( h, val, cmp, f );
 167             }
 168
 169             template <typename Q, typename Compare>
 170             bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 171             {
 172                 assert( pHead != nullptr );
 173                 bucket_head_type h(pHead);
 174                 return base_class::erase_at( h, val, cmp );
 175             }
 176
 177             template <typename Q, typename Compare>
 178             value_type * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
 179             {
 180                 assert( pHead != nullptr );
 181                 bucket_head_type h(pHead);
 182                 return base_class::extract_at( h, val, cmp );
 183             }
 184
 185             template <typename Q, typename Compare, typename Func>
 186             bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 187             {
 188                 assert( pHead != nullptr );
 189                 bucket_head_type h(pHead);
 190                 return base_class::find_at( h, val, cmp, f );
 191             }
 192
 193             template <typename Q, typename Compare>
 194             bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
 195             {
 196                 assert( pHead != nullptr );
 197                 bucket_head_type h(pHead);
 198                 return base_class::find_at( h, val, cmp );
 199             }
 200
 201             template <typename Q, typename Compare>
 202             raw_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
 203             {
 204                 assert( pHead != nullptr );
 205                 bucket_head_type h(pHead);
 206                 return base_class::get_at( h, val, cmp );
 207             }
 208
 209             bool insert_aux_node( dummy_node_type * pNode )
 210             {
 211                 return base_class::insert_aux_node( pNode );
 212             }
 213             bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
 214             {
 215                 bucket_head_type h(pHead);
 216                 return base_class::insert_aux_node( h, pNode );
 217             }
 218         };
 219
 220         template <typename Less>
 221         struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
 222         {
 223             typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
 224
 225             template <typename Q1, typename Q2>
 226             int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
 227             {
 228                 return base_wrapper::operator()( v1.val, v2 );
 229             }
 230
 231             template <typename Q1, typename Q2>
 232             int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
 233             {
 234                 return base_wrapper::operator()( v1, v2.val );
 235             }
 236         };
 237         //@endcond
 238
 239     protected:
 240         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
 241         bucket_table            m_Buckets;          ///< bucket table
 242         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 243         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 244         item_counter            m_ItemCounter;      ///< Item counter
 245         hash                    m_HashFunctor;      ///< Hash functor
 246         stat                    m_Stat;             ///< Internal stattistics accumulator
 247
 248     protected:
 249         //@cond
 250         typedef cds::details::Allocator< dummy_node_type, typename traits::allocator >   dummy_node_allocator;
 251
 252         dummy_node_type * alloc_dummy_node( size_t nHash )
 253         {
 254             m_Stat.onHeadNodeAllocated();
 255             return dummy_node_allocator().New( nHash );
 256         }
 257         void free_dummy_node( dummy_node_type * p )
 258         {
 259             dummy_node_allocator().Delete( p );
 260             m_Stat.onHeadNodeFreed();
 261         }
 262
 263         /// Calculates hash value of \p key
 264         template <typename Q>
 265         size_t hash_value( Q const& key ) const
 266         {
 267             return m_HashFunctor( key );
 268         }
 269
 270         size_t bucket_no( size_t nHash ) const
 271         {
 272             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 273         }
 274
 275         static size_t parent_bucket( size_t nBucket )
 276         {
 277             assert( nBucket > 0 );
 278             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
 279         }
 280
 281         dummy_node_type * init_bucket( size_t nBucket )
 282         {
 283             assert( nBucket > 0 );
 284             size_t nParent = parent_bucket( nBucket );
 285
 286             dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
 287             if ( pParentBucket == nullptr ) {
 288                 pParentBucket = init_bucket( nParent );
 289                 m_Stat.onRecursiveInitBucket();
 290             }
 291
 292             assert( pParentBucket != nullptr );
 293
 294             // Allocate a dummy node for new bucket
 295             {
 296                 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
 297                 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 298                     m_Buckets.bucket( nBucket, pBucket );
 299                     m_Stat.onNewBucket();
 300                     return pBucket;
 301                 }
 302                 free_dummy_node( pBucket );
 303             }
 304
 305             // Another thread set the bucket. Wait while it done
 306
 307             // In this point, we must wait while nBucket is empty.
 308             // The compiler can decide that waiting loop can be "optimized" (stripped)
 309             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
 310             //
 311             m_Stat.onBucketInitContenton();
 312             back_off bkoff;
 313             while ( true ) {
 314                 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
 315                 if ( p != nullptr )
 316                     return const_cast<dummy_node_type *>( p );
 317                 bkoff();
 318                 m_Stat.onBusyWaitBucketInit();
 319             }
 320         }
 321
 322         dummy_node_type * get_bucket( size_t nHash )
 323         {
 324             size_t nBucket = bucket_no( nHash );
 325
 326             dummy_node_type * pHead = m_Buckets.bucket( nBucket );
 327             if ( pHead == nullptr )
 328                 pHead = init_bucket( nBucket );
 329
 330             assert( pHead->is_dummy() );
 331
 332             return pHead;
 333         }
 334
 335         void init()
 336         {
 337             // GC and OrderedList::gc must be the same
 338             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 339
 340             // atomicity::empty_item_counter is not allowed as a item counter
 341             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 342                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 343
 344             // Initialize bucket 0
 345             dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
 346
 347             // insert_aux_node cannot return false for empty list
 348             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 349
 350             m_Buckets.bucket( 0, pNode );
 351         }
 352
 353         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 354         {
 355             return nBucketCount * nLoadFactor;
 356         }
 357
 358         void inc_item_count()
 359         {
 360             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 361             if ( ++m_ItemCounter <= nMaxCount )
 362                 return;
 363
 364             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 365             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 366             if ( nBucketCount < m_Buckets.capacity() ) {
 367                 // we may grow the bucket table
 368                 const size_t nLoadFactor = m_Buckets.load_factor();
 369                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 370                     return; // someone already have updated m_nBucketCountLog2, so stop here
 371
 372                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 373                                                          memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 374                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 375             }
 376             else
 377                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
 378         }
 379
 380         template <typename Q, typename Compare, typename Func>
 381         bool find_( Q& val, Compare cmp, Func f )
 382         {
 383             size_t nHash = hash_value( val );
 384             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 385             dummy_node_type * pHead = get_bucket( nHash );
 386             assert( pHead != nullptr );
 387
 388             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 389                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 390         }
 391
 392         template <typename Q, typename Compare>
 393         bool find_value( Q const& val, Compare cmp )
 394         {
 395             size_t nHash = hash_value( val );
 396             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 397             dummy_node_type * pHead = get_bucket( nHash );
 398             assert( pHead != nullptr );
 399
 400             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
 401         }
 402
 403         template <typename Q, typename Compare>
 404         raw_ptr get_( Q const& val, Compare cmp )
 405         {
 406             size_t nHash = hash_value( val );
 407             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 408             dummy_node_type * pHead = get_bucket( nHash );
 409             assert( pHead != nullptr );
 410
 411             raw_ptr p = m_List.get_at( pHead, sv, cmp );
 412             m_Stat.onFind( !!p );
 413             return p;
 414         }
 415
 416         template <typename Q, typename Compare>
 417         value_type * extract_( Q const& val, Compare cmp )
 418         {
 419             size_t nHash = hash_value( val );
 420             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 421             dummy_node_type * pHead = get_bucket( nHash );
 422             assert( pHead != nullptr );
 423
 424             value_type * pNode = m_List.extract_at( pHead, sv, cmp );
 425             if ( pNode ) {
 426                 --m_ItemCounter;
 427                 m_Stat.onExtractSuccess();
 428             }
 429             else
 430                 m_Stat.onExtractFailed();
 431             return pNode;
 432         }
 433
 434         template <typename Q, typename Less>
 435         value_type * extract_with_( Q const& val, Less pred )
 436         {
 437             CDS_UNUSED( pred );
 438             return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 439         }
 440
 441         template <typename Q, typename Compare>
 442         bool erase_( const Q& val, Compare cmp )
 443         {
 444             size_t nHash = hash_value( val );
 445             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 446             dummy_node_type * pHead = get_bucket( nHash );
 447             assert( pHead != nullptr );
 448
 449             if ( m_List.erase_at( pHead, sv, cmp ) ) {
 450                 --m_ItemCounter;
 451                 m_Stat.onEraseSuccess();
 452                 return true;
 453             }
 454             m_Stat.onEraseFailed();
 455             return false;
 456         }
 457
 458         template <typename Q, typename Compare, typename Func>
 459         bool erase_( Q const& val, Compare cmp, Func f )
 460         {
 461             size_t nHash = hash_value( val );
 462             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 463             dummy_node_type * pHead = get_bucket( nHash );
 464             assert( pHead != nullptr );
 465
 466             if ( m_List.erase_at( pHead, sv, cmp, f )) {
 467                 --m_ItemCounter;
 468                 m_Stat.onEraseSuccess();
 469                 return true;
 470             }
 471             m_Stat.onEraseFailed();
 472             return false;
 473         }
 474
 475         //@endcond
 476
 477     public:
 478         /// Initialize split-ordered list of default capacity
 479         /**
 480             The default capacity is defined in bucket table constructor.
 481             See split_list::expandable_bucket_table, split_list::static_ducket_table
 482             which selects by split_list::dynamic_bucket_table option.
 483         */
 484         SplitListSet()
 485             : m_nBucketCountLog2(1)
 486             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 487         {
 488             init();
 489         }
 490
 491         /// Initialize split-ordered list
 492         SplitListSet(
 493             size_t nItemCount           ///< estimate average of item count
 494             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 495             )
 496             : m_Buckets( nItemCount, nLoadFactor )
 497             , m_nBucketCountLog2(1)
 498             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 499         {
 500             init();
 501         }
 502
 503     public:
 504         /// Inserts new node
 505         /**
 506             The function inserts \p val in the set if it does not contain
 507             an item with key equal to \p val.
 508
 509             The function makes RCU lock internally.
 510
 511             Returns \p true if \p val is placed into the set, \p false otherwise.
 512         */
 513         bool insert( value_type& val )
 514         {
 515             size_t nHash = hash_value( val );
 516             dummy_node_type * pHead = get_bucket( nHash );
 517             assert( pHead != nullptr );
 518
 519             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 520
 521             if ( m_List.insert_at( pHead, val )) {
 522                 inc_item_count();
 523                 m_Stat.onInsertSuccess();
 524                 return true;
 525             }
 526             m_Stat.onInsertFailed();
 527             return false;
 528         }
 529
 530         /// Inserts new node
 531         /**
 532             This function is intended for derived non-intrusive containers.
 533
 534             The function allows to split creating of new item into two part:
 535             - create item with key only
 536             - insert new item into the set
 537             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 538
 539             The functor signature is:
 540             \code
 541                 void func( value_type& val );
 542             \endcode
 543             where \p val is the item inserted.
 544
 545             The function makes RCU lock internally.
 546
 547             @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 548             \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
 549             synchronization.
 550             */
 551         template <typename Func>
 552         bool insert( value_type& val, Func f )
 553         {
 554             size_t nHash = hash_value( val );
 555             dummy_node_type * pHead = get_bucket( nHash );
 556             assert( pHead != nullptr );
 557
 558             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 559
 560             if ( m_List.insert_at( pHead, val, f )) {
 561                 inc_item_count();
 562                 m_Stat.onInsertSuccess();
 563                 return true;
 564             }
 565             m_Stat.onInsertFailed();
 566             return false;
 567         }
 568
 569         /// Updates the node
 570         /**
 571             The operation performs inserting or changing data with lock-free manner.
 572
 573             If the item \p val is not found in the set, then \p val is inserted
 574             iff \p bAllowInsert is \p true.
 575             Otherwise, the functor \p func is called with item found.
 576             The functor signature is:
 577             \code
 578                 void func( bool bNew, value_type& item, value_type& val );
 579             \endcode
 580             with arguments:
 581             - \p bNew - \p true if the item has been inserted, \p false otherwise
 582             - \p item - item of the set
 583             - \p val - argument \p val passed into the \p update() function
 584             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 585             refers to the same stuff.
 586
 587             The functor may change non-key fields of the \p item.
 588
 589             The function applies RCU lock internally.
 590
 591             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 592             \p second is \p true if new item has been added or \p false if the item with \p key
 593             already is in the list.
 594
 595             @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 596             \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
 597             synchronization.
 598         */
 599         template <typename Func>
 600         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 601         {
 602             size_t nHash = hash_value( val );
 603             dummy_node_type * pHead = get_bucket( nHash );
 604             assert( pHead != nullptr );
 605
 606             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 607
 608             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
 609             if ( bRet.first && bRet.second ) {
 610                 inc_item_count();
 611                 m_Stat.onEnsureNew();
 612             }
 613             else
 614                 m_Stat.onEnsureExist();
 615             return bRet;
 616         }
 617         //@cond
 618         template <typename Func>
 619         CDS_DEPRECATED("ensure() is deprecated, use update()")
 620         std::pair<bool, bool> ensure( value_type& val, Func func )
 621         {
 622             return update( val, func, true );
 623         }
 624         //@endcond
 625
 626         /// Unlinks the item \p val from the set
 627         /**
 628             The function searches the item \p val in the set and unlinks it from the set
 629             if it is found and is equal to \p val.
 630
 631             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 632             and deletes the item found. \p unlink finds an item by key and deletes it
 633             only if \p val is an item of that set, i.e. the pointer to item found
 634             is equal to <tt> &val </tt>.
 635
 636             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 637
 638             The function returns \p true if success and \p false otherwise.
 639         */
 640         bool unlink( value_type& val )
 641         {
 642             size_t nHash = hash_value( val );
 643             dummy_node_type * pHead = get_bucket( nHash );
 644             assert( pHead != nullptr );
 645
 646             if ( m_List.unlink_at( pHead, val ) ) {
 647                 --m_ItemCounter;
 648                 m_Stat.onEraseSuccess();
 649                 return true;
 650             }
 651             m_Stat.onEraseFailed();
 652             return false;
 653         }
 654
 655         /// Deletes the item from the set
 656         /** \anchor cds_intrusive_SplitListSet_rcu_erase
 657             The function searches an item with key equal to \p key in the set,
 658             unlinks it from the set, and returns \p true.
 659             If the item with key equal to \p key is not found the function return \p false.
 660
 661             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 662             and deletes the item found. \p unlink finds an item by key and deletes it
 663             only if \p key is an item of that set, i.e. the pointer to item found
 664             is equal to <tt> &key </tt>.
 665
 666             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 667
 668             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 669         */
 670         template <typename Q>
 671         bool erase( Q const& key )
 672         {
 673             return erase_( key, key_comparator() );
 674         }
 675
 676         /// Deletes the item from the set using \p pred for searching
 677         /**
 678             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
 679             but \p cmp is used for key compare.
 680             \p Less has the interface like \p std::less.
 681             \p pred must imply the same element order as the comparator used for building the set.
 682         */
 683         template <typename Q, typename Less>
 684         bool erase_with( Q const& key, Less pred )
 685         {
 686             CDS_UNUSED( pred );
 687             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 688         }
 689
 690         /// Deletes the item from the set
 691         /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
 692             The function searches an item with key equal to \p key in the set,
 693             call \p f functor with item found, unlinks it from the set, and returns \p true.
 694             The \ref disposer specified by \p OrderedList class template parameter is called
 695             by garbage collector \p GC asynchronously.
 696
 697             The \p Func interface is
 698             \code
 699             struct functor {
 700                 void operator()( value_type const& item );
 701             };
 702             \endcode
 703
 704             If the item with key equal to \p key is not found the function return \p false.
 705
 706             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 707
 708             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 709         */
 710         template <typename Q, typename Func>
 711         bool erase( Q const& key, Func f )
 712         {
 713             return erase_( key, key_comparator(), f );
 714         }
 715
 716         /// Deletes the item from the set using \p pred for searching
 717         /**
 718             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
 719             but \p cmp is used for key compare.
 720             \p Less has the interface like \p std::less.
 721             \p pred must imply the same element order as the comparator used for building the set.
 722         */
 723         template <typename Q, typename Less, typename Func>
 724         bool erase_with( Q const& key, Less pred, Func f )
 725         {
 726             CDS_UNUSED( pred );
 727             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 728         }
 729
 730         /// Extracts an item from the set
 731         /** \anchor cds_intrusive_SplitListSet_rcu_extract
 732             The function searches an item with key equal to \p key in the set,
 733             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 734             If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
 735
 736             Depends on \p bucket_type you should or should not lock RCU before calling of this function:
 737             - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
 738             - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
 739             See ordered list implementation for details.
 740
 741             \code
 742             typedef cds::urcu::gc< general_buffered<> > rcu;
 743             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 744             typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
 745
 746             rcu_splitlist_set theSet;
 747             // ...
 748
 749             rcu_splitlist_set::exempt_ptr p;
 750
 751             // For MichaelList we should not lock RCU
 752
 753             // Now, you can apply extract function
 754             // Note that you must not delete the item found inside the RCU lock
 755             p = theList.extract( 10 );
 756             if ( p ) {
 757                 // do something with p
 758                 ...
 759             }
 760
 761             // We may safely release p here
 762             // release() passes the pointer to RCU reclamation cycle:
 763             // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
 764             p.release();
 765             \endcode
 766         */
 767         template <typename Q>
 768         exempt_ptr extract( Q const& key )
 769         {
 770             return exempt_ptr(extract_( key, key_comparator() ));
 771         }
 772
 773         /// Extracts an item from the set using \p pred for searching
 774         /**
 775             The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
 776             \p Less functor has the interface like \p std::less.
 777             \p pred must imply the same element order as the comparator used for building the set.
 778         */
 779         template <typename Q, typename Less>
 780         exempt_ptr extract_with( Q const& key, Less pred )
 781         {
 782             return exempt_ptr( extract_with_( key, pred ));
 783         }
 784
 785         /// Finds the key \p key
 786         /** \anchor cds_intrusive_SplitListSet_rcu_find_func
 787             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 788             The interface of \p Func functor is:
 789             \code
 790             struct functor {
 791                 void operator()( value_type& item, Q& key );
 792             };
 793             \endcode
 794             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 795
 796             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 797             that \p item cannot be disposed during functor is executing.
 798             The functor does not serialize simultaneous access to the set \p item. If such access is
 799             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 800
 801             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 802             can modify both arguments.
 803
 804             Note the hash functor specified for class \p Traits template parameter
 805             should accept a parameter of type \p Q that can be not the same as \p value_type.
 806
 807             The function applies RCU lock internally.
 808
 809             The function returns \p true if \p key is found, \p false otherwise.
 810         */
 811         template <typename Q, typename Func>
 812         bool find( Q& key, Func f )
 813         {
 814             return find_( key, key_comparator(), f );
 815         }
 816         //@cond
 817         template <typename Q, typename Func>
 818         bool find( Q const& key, Func f )
 819         {
 820             return find_( key, key_comparator(), f );
 821         }
 822         //@endcond
 823
 824         /// Finds the key \p key with \p pred predicate for comparing
 825         /**
 826             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
 827             but \p cmp is used for key compare.
 828             \p Less has the interface like \p std::less.
 829             \p cmp must imply the same element order as the comparator used for building the set.
 830         */
 831         template <typename Q, typename Less, typename Func>
 832         bool find_with( Q& key, Less pred, Func f )
 833         {
 834             CDS_UNUSED( pred );
 835             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 836         }
 837         //@cond
 838         template <typename Q, typename Less, typename Func>
 839         bool find_with( Q const& key, Less pred, Func f )
 840         {
 841             CDS_UNUSED( pred );
 842             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 843         }
 844         //@endcond
 845
 846         /// Checks whether the set contains \p key
 847         /**
 848             The function searches the item with key equal to \p key
 849             and returns \p true if it is found, and \p false otherwise.
 850
 851             Note the hash functor specified for class \p Traits template parameter
 852             should accept a parameter of type \p Q that can be not the same as \p value_type.
 853             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 854         */
 855         template <typename Q>
 856         bool contains( Q const& key )
 857         {
 858             return find_value( key, key_comparator() );
 859         }
 860         //@cond
 861         template <typename Q>
 862         CDS_DEPRECATED("deprecated, use contains()")
 863         bool find( Q const& key )
 864         {
 865             return contains( key );
 866         }
 867         //@endcond
 868
 869         /// Checks whether the set contains \p key using \p pred predicate for searching
 870         /**
 871             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 872             \p Less functor has the interface like \p std::less.
 873             \p Less must imply the same element order as the comparator used for building the list.
 874         */
 875         template <typename Q, typename Less>
 876         bool contains( Q const& key, Less pred )
 877         {
 878             CDS_UNUSED( pred );
 879             return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 880         }
 881         //@cond
 882         template <typename Q, typename Less>
 883         CDS_DEPRECATED("deprecated, use contains()")
 884         bool find_with( Q const& key, Less pred )
 885         {
 886             return contains( key, pred );
 887         }
 888         //@endcond
 889
 890         /// Finds the key \p key and return the item found
 891         /** \anchor cds_intrusive_SplitListSet_rcu_get
 892             The function searches the item with key equal to \p key and returns the pointer to item found.
 893             If \p key is not found it returns \p nullptr.
 894
 895             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 896
 897             RCU should be locked before call of this function.
 898             Returned item is valid only while RCU is locked:
 899             \code
 900             typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
 901             set_class theSet;
 902             // ...
 903             typename set_class::raw_ptr rp;
 904             {
 905                 // Lock RCU
 906                 hash_set::rcu_lock lock;
 907
 908                 rp = theSet.get( 5 );
 909                 if ( rp ) {
 910                     // Deal with rp
 911                     //...
 912                 }
 913                 // Unlock RCU by rcu_lock destructor
 914                 // rp can be retired by disposer at any time after RCU has been unlocked
 915             }
 916             \endcode
 917         */
 918         template <typename Q>
 919         raw_ptr get( Q const& key )
 920         {
 921             return get_( key, key_comparator() );
 922         }
 923
 924         /// Finds the key \p key and return the item found
 925         /**
 926             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
 927             but \p pred is used for comparing the keys.
 928
 929             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 930             in any order.
 931             \p pred must imply the same element order as the comparator used for building the set.
 932         */
 933         template <typename Q, typename Less>
 934         raw_ptr get_with( Q const& key, Less pred )
 935         {
 936             CDS_UNUSED( pred );
 937             return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 938         }
 939
 940
 941         /// Returns item count in the set
 942         size_t size() const
 943         {
 944             return m_ItemCounter;
 945         }
 946
 947         /// Checks if the set is empty
 948         /**
 949             Emptiness is checked by item counting: if item count is zero then the set is empty.
 950             Thus, the correct item counting feature is an important part of split-list set implementation.
 951         */
 952         bool empty() const
 953         {
 954             return size() == 0;
 955         }
 956
 957         /// Clears the set (not atomic)
 958         void clear()
 959         {
 960             iterator it = begin();
 961             while ( it != end() ) {
 962                 iterator i(it);
 963                 ++i;
 964                 unlink( *it );
 965                 it = i;
 966             }
 967         }
 968
 969         /// Returns internal statistics
 970         stat const& statistics() const
 971         {
 972             return m_Stat;
 973         }
 974
 975     protected:
 976         //@cond
 977         template <bool IsConst>
 978         class iterator_type
 979             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 980         {
 981             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 982             typedef typename iterator_base_class::list_iterator list_iterator;
 983         public:
 984             iterator_type()
 985                 : iterator_base_class()
 986             {}
 987
 988             iterator_type( iterator_type const& src )
 989                 : iterator_base_class( src )
 990             {}
 991
 992             // This ctor should be protected...
 993             iterator_type( list_iterator itCur, list_iterator itEnd )
 994                 : iterator_base_class( itCur, itEnd )
 995             {}
 996         };
 997         //@endcond
 998
 999     public:
1000         /// Forward iterator
1001         /**
1002             The forward iterator for a split-list has some features:
1003             - it has no post-increment operator
1004             - it depends on iterator of underlying \p OrderedList
1005             - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1006             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1007               deleting operations it is no guarantee that you iterate all item in the split-list.
1008
1009             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1010             for debug purpose only.
1011         */
1012         typedef iterator_type<false>    iterator;
1013         /// Const forward iterator
1014         /**
1015             For iterator's features and requirements see \ref iterator
1016         */
1017         typedef iterator_type<true>     const_iterator;
1018
1019         /// Returns a forward iterator addressing the first element in a split-list
1020         /**
1021             For empty list \code begin() == end() \endcode
1022         */
1023         iterator begin()
1024         {
1025             return iterator( m_List.begin(), m_List.end() );
1026         }
1027
1028         /// Returns an iterator that addresses the location succeeding the last element in a split-list
1029         /**
1030             Do not use the value returned by <tt>end</tt> function to access any item.
1031
1032             The returned value can be used only to control reaching the end of the split-list.
1033             For empty list \code begin() == end() \endcode
1034         */
1035         iterator end()
1036         {
1037             return iterator( m_List.end(), m_List.end() );
1038         }
1039
1040         /// Returns a forward const iterator addressing the first element in a split-list
1041         const_iterator begin() const
1042         {
1043             return cbegin();
1044         }
1045         /// Returns a forward const iterator addressing the first element in a split-list
1046         const_iterator cbegin() const
1047         {
1048             return const_iterator( m_List.cbegin(), m_List.cend() );
1049         }
1050
1051         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1052         const_iterator end() const
1053         {
1054             return cend();
1055         }
1056         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1057         const_iterator cend() const
1058         {
1059             return const_iterator( m_List.cend(), m_List.cend() );
1060         }
1061
1062     };
1063
1064 }}  // namespace cds::intrusive
1065
1066 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H