cds/intrusive/split_list_rcu.h

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