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