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> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
 152             {
 153                 assert( pHead != nullptr );
 154                 bucket_head_type h(pHead);
 155                 return base_class::ensure_at( h, val, func );
 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         /// Ensures that the \p val exists in the set
 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 into the set.
 578             Otherwise, the functor \p func is called with item found.
 579             The functor signature is:
 580             \code
 581                 void func( bool bNew, value_type& item, value_type& val );
 582             \endcode
 583             with arguments:
 584             - \p bNew - \p true if the item has been inserted, \p false otherwise
 585             - \p item - item of the set
 586             - \p val - argument \p val passed into the \p ensure function
 587             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 588             refers to the same thing.
 589
 590             The function makes RCU lock internally.
 591
 592             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 593             \p second is \p true if new item has been added or \p false if the item with \p key
 594             already is in the set.
 595
 596             @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 597             \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
 598             synchronization.
 599             */
 600         template <typename Func>
 601         std::pair<bool, bool> ensure( value_type& val, Func func )
 602         {
 603             size_t nHash = hash_value( val );
 604             dummy_node_type * pHead = get_bucket( nHash );
 605             assert( pHead != nullptr );
 606
 607             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 608
 609             std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
 610             if ( bRet.first && bRet.second ) {
 611                 inc_item_count();
 612                 m_Stat.onEnsureNew();
 613             }
 614             else
 615                 m_Stat.onEnsureExist();
 616             return bRet;
 617         }
 618
 619         /// Unlinks the item \p val from the set
 620         /**
 621             The function searches the item \p val in the set and unlinks it from the set
 622             if it is found and is equal to \p val.
 623
 624             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 625             and deletes the item found. \p unlink finds an item by key and deletes it
 626             only if \p val is an item of that set, i.e. the pointer to item found
 627             is equal to <tt> &val </tt>.
 628
 629             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 630
 631             The function returns \p true if success and \p false otherwise.
 632         */
 633         bool unlink( value_type& val )
 634         {
 635             size_t nHash = hash_value( val );
 636             dummy_node_type * pHead = get_bucket( nHash );
 637             assert( pHead != nullptr );
 638
 639             if ( m_List.unlink_at( pHead, val ) ) {
 640                 --m_ItemCounter;
 641                 m_Stat.onEraseSuccess();
 642                 return true;
 643             }
 644             m_Stat.onEraseFailed();
 645             return false;
 646         }
 647
 648         /// Deletes the item from the set
 649         /** \anchor cds_intrusive_SplitListSet_rcu_erase
 650             The function searches an item with key equal to \p key in the set,
 651             unlinks it from the set, and returns \p true.
 652             If the item with key equal to \p key is not found the function return \p false.
 653
 654             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 655             and deletes the item found. \p unlink finds an item by key and deletes it
 656             only if \p key is an item of that set, i.e. the pointer to item found
 657             is equal to <tt> &key </tt>.
 658
 659             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 660
 661             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 662         */
 663         template <typename Q>
 664         bool erase( Q const& key )
 665         {
 666             return erase_( key, key_comparator() );
 667         }
 668
 669         /// Deletes the item from the set using \p pred for searching
 670         /**
 671             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
 672             but \p cmp is used for key compare.
 673             \p Less has the interface like \p std::less.
 674             \p pred must imply the same element order as the comparator used for building the set.
 675         */
 676         template <typename Q, typename Less>
 677         bool erase_with( Q const& key, Less pred )
 678         {
 679             CDS_UNUSED( pred );
 680             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 681         }
 682
 683         /// Deletes the item from the set
 684         /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
 685             The function searches an item with key equal to \p key in the set,
 686             call \p f functor with item found, unlinks it from the set, and returns \p true.
 687             The \ref disposer specified by \p OrderedList class template parameter is called
 688             by garbage collector \p GC asynchronously.
 689
 690             The \p Func interface is
 691             \code
 692             struct functor {
 693                 void operator()( value_type const& item );
 694             };
 695             \endcode
 696
 697             If the item with key equal to \p key is not found the function return \p false.
 698
 699             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 700
 701             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 702         */
 703         template <typename Q, typename Func>
 704         bool erase( Q const& key, Func f )
 705         {
 706             return erase_( key, key_comparator(), f );
 707         }
 708
 709         /// Deletes the item from the set using \p pred for searching
 710         /**
 711             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
 712             but \p cmp is used for key compare.
 713             \p Less has the interface like \p std::less.
 714             \p pred must imply the same element order as the comparator used for building the set.
 715         */
 716         template <typename Q, typename Less, typename Func>
 717         bool erase_with( Q const& key, Less pred, Func f )
 718         {
 719             CDS_UNUSED( pred );
 720             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 721         }
 722
 723         /// Extracts an item from the set
 724         /** \anchor cds_intrusive_SplitListSet_rcu_extract
 725             The function searches an item with key equal to \p key in the set,
 726             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 727             If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
 728
 729             Depends on \p bucket_type you should or should not lock RCU before calling of this function:
 730             - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
 731             - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
 732             See ordered list implementation for details.
 733
 734             \code
 735             typedef cds::urcu::gc< general_buffered<> > rcu;
 736             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 737             typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
 738
 739             rcu_splitlist_set theSet;
 740             // ...
 741
 742             rcu_splitlist_set::exempt_ptr p;
 743
 744             // For MichaelList we should not lock RCU
 745
 746             // Now, you can apply extract function
 747             // Note that you must not delete the item found inside the RCU lock
 748             p = theList.extract( 10 );
 749             if ( p ) {
 750                 // do something with p
 751                 ...
 752             }
 753
 754             // We may safely release p here
 755             // release() passes the pointer to RCU reclamation cycle:
 756             // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
 757             p.release();
 758             \endcode
 759         */
 760         template <typename Q>
 761         exempt_ptr extract( Q const& key )
 762         {
 763             return exempt_ptr(extract_( key, key_comparator() ));
 764         }
 765
 766         /// Extracts an item from the set using \p pred for searching
 767         /**
 768             The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
 769             \p Less functor has the interface like \p std::less.
 770             \p pred must imply the same element order as the comparator used for building the set.
 771         */
 772         template <typename Q, typename Less>
 773         exempt_ptr extract_with( Q const& key, Less pred )
 774         {
 775             return exempt_ptr( extract_with_( key, pred ));
 776         }
 777
 778         /// Finds the key \p key
 779         /** \anchor cds_intrusive_SplitListSet_rcu_find_func
 780             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 781             The interface of \p Func functor is:
 782             \code
 783             struct functor {
 784                 void operator()( value_type& item, Q& key );
 785             };
 786             \endcode
 787             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 788
 789             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 790             that \p item cannot be disposed during functor is executing.
 791             The functor does not serialize simultaneous access to the set \p item. If such access is
 792             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 793
 794             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 795             can modify both arguments.
 796
 797             Note the hash functor specified for class \p Traits template parameter
 798             should accept a parameter of type \p Q that can be not the same as \p value_type.
 799
 800             The function applies RCU lock internally.
 801
 802             The function returns \p true if \p key is found, \p false otherwise.
 803         */
 804         template <typename Q, typename Func>
 805         bool find( Q& key, Func f )
 806         {
 807             return find_( key, key_comparator(), f );
 808         }
 809         //@cond
 810         template <typename Q, typename Func>
 811         bool find( Q const& key, Func f )
 812         {
 813             return find_( key, key_comparator(), f );
 814         }
 815         //@endcond
 816
 817         /// Finds the key \p key with \p pred predicate for comparing
 818         /**
 819             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
 820             but \p cmp is used for key compare.
 821             \p Less has the interface like \p std::less.
 822             \p cmp must imply the same element order as the comparator used for building the set.
 823         */
 824         template <typename Q, typename Less, typename Func>
 825         bool find_with( Q& key, Less pred, Func f )
 826         {
 827             CDS_UNUSED( pred );
 828             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 829         }
 830         //@cond
 831         template <typename Q, typename Less, typename Func>
 832         bool find_with( Q const& 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         //@endcond
 838
 839         /// Finds the key \p key
 840         /** \anchor cds_intrusive_SplitListSet_rcu_find_val
 841             The function searches the item with key equal to \p key
 842             and returns \p true if \p key found or \p false otherwise.
 843         */
 844         template <typename Q>
 845         bool find( Q const& key )
 846         {
 847             return find_value( key, key_comparator() );
 848         }
 849
 850         /// Finds the key \p key with \p pred predicate for comparing
 851         /**
 852             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_val "find(Q const&)"
 853             but \p cmp is used for key compare.
 854             \p Less has the interface like \p std::less.
 855             \p pred must imply the same element order as the comparator used for building the set.
 856         */
 857         template <typename Q, typename Less>
 858         bool find_with( Q const& key, Less pred )
 859         {
 860             CDS_UNUSED( pred );
 861             return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 862         }
 863
 864         /// Finds the key \p key and return the item found
 865         /** \anchor cds_intrusive_SplitListSet_rcu_get
 866             The function searches the item with key equal to \p key and returns the pointer to item found.
 867             If \p key is not found it returns \p nullptr.
 868
 869             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 870
 871             RCU should be locked before call of this function.
 872             Returned item is valid only while RCU is locked:
 873             \code
 874             typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
 875             set_class theSet;
 876             // ...
 877             typename set_class::raw_ptr rp;
 878             {
 879                 // Lock RCU
 880                 hash_set::rcu_lock lock;
 881
 882                 rp = theSet.get( 5 );
 883                 if ( rp ) {
 884                     // Deal with rp
 885                     //...
 886                 }
 887                 // Unlock RCU by rcu_lock destructor
 888                 // rp can be retired by disposer at any time after RCU has been unlocked
 889             }
 890             \endcode
 891         */
 892         template <typename Q>
 893         raw_ptr get( Q const& key )
 894         {
 895             return get_( key, key_comparator() );
 896         }
 897
 898         /// Finds the key \p key and return the item found
 899         /**
 900             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
 901             but \p pred is used for comparing the keys.
 902
 903             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 904             in any order.
 905             \p pred must imply the same element order as the comparator used for building the set.
 906         */
 907         template <typename Q, typename Less>
 908         raw_ptr get_with( Q const& key, Less pred )
 909         {
 910             CDS_UNUSED( pred );
 911             return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 912         }
 913
 914
 915         /// Returns item count in the set
 916         size_t size() const
 917         {
 918             return m_ItemCounter;
 919         }
 920
 921         /// Checks if the set is empty
 922         /**
 923             Emptiness is checked by item counting: if item count is zero then the set is empty.
 924             Thus, the correct item counting feature is an important part of split-list set implementation.
 925         */
 926         bool empty() const
 927         {
 928             return size() == 0;
 929         }
 930
 931         /// Clears the set (not atomic)
 932         void clear()
 933         {
 934             iterator it = begin();
 935             while ( it != end() ) {
 936                 iterator i(it);
 937                 ++i;
 938                 unlink( *it );
 939                 it = i;
 940             }
 941         }
 942
 943         /// Returns internal statistics
 944         stat const& statistics() const
 945         {
 946             return m_Stat;
 947         }
 948
 949     protected:
 950         //@cond
 951         template <bool IsConst>
 952         class iterator_type
 953             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 954         {
 955             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 956             typedef typename iterator_base_class::list_iterator list_iterator;
 957         public:
 958             iterator_type()
 959                 : iterator_base_class()
 960             {}
 961
 962             iterator_type( iterator_type const& src )
 963                 : iterator_base_class( src )
 964             {}
 965
 966             // This ctor should be protected...
 967             iterator_type( list_iterator itCur, list_iterator itEnd )
 968                 : iterator_base_class( itCur, itEnd )
 969             {}
 970         };
 971         //@endcond
 972     public:
 973         /// Forward iterator
 974         /**
 975             The forward iterator for a split-list has some features:
 976             - it has no post-increment operator
 977             - it depends on iterator of underlying \p OrderedList
 978             - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
 979             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 980               deleting operations it is no guarantee that you iterate all item in the split-list.
 981
 982             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 983             for debug purpose only.
 984         */
 985         typedef iterator_type<false>    iterator;
 986         /// Const forward iterator
 987         /**
 988             For iterator's features and requirements see \ref iterator
 989         */
 990         typedef iterator_type<true>     const_iterator;
 991
 992         /// Returns a forward iterator addressing the first element in a split-list
 993         /**
 994             For empty list \code begin() == end() \endcode
 995         */
 996         iterator begin()
 997         {
 998             return iterator( m_List.begin(), m_List.end() );
 999         }
1000
1001         /// Returns an iterator that addresses the location succeeding the last element in a split-list
1002         /**
1003             Do not use the value returned by <tt>end</tt> function to access any item.
1004
1005             The returned value can be used only to control reaching the end of the split-list.
1006             For empty list \code begin() == end() \endcode
1007         */
1008         iterator end()
1009         {
1010             return iterator( m_List.end(), m_List.end() );
1011         }
1012
1013         /// Returns a forward const iterator addressing the first element in a split-list
1014         const_iterator begin() const
1015         {
1016             return cbegin();
1017         }
1018         /// Returns a forward const iterator addressing the first element in a split-list
1019         const_iterator cbegin() const
1020         {
1021             return const_iterator( m_List.cbegin(), m_List.cend() );
1022         }
1023
1024         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1025         const_iterator end() const
1026         {
1027             return cend();
1028         }
1029         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1030         const_iterator cend() const
1031         {
1032             return const_iterator( m_List.cend(), m_List.cend() );
1033         }
1034
1035     };
1036
1037 }}  // namespace cds::intrusive
1038
1039 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H