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             The functor can be passed by reference with <tt>boost:ref</tt>
 667
 668             If the item with key equal to \p key is not found the function return \p false.
 669
 670             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 671
 672             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 673         */
 674         template <typename Q, typename Func>
 675         bool erase( Q const& key, Func f )
 676         {
 677             return erase_( key, key_comparator(), f );
 678         }
 679
 680         /// Deletes the item from the set using \p pred for searching
 681         /**
 682             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
 683             but \p cmp is used for key compare.
 684             \p Less has the interface like \p std::less.
 685             \p pred must imply the same element order as the comparator used for building the set.
 686         */
 687         template <typename Q, typename Less, typename Func>
 688         bool erase_with( Q const& key, Less pred, Func f )
 689         {
 690             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 691         }
 692
 693         /// Extracts an item from the set
 694         /** \anchor cds_intrusive_SplitListSet_rcu_extract
 695             The function searches an item with key equal to \p key in the set,
 696             unlinks it, and returns pointer to an item found in \p dest argument.
 697             If the item with the key equal to \p key is not found the function returns \p false.
 698
 699             @note The function does NOT call RCU read-side lock or synchronization,
 700             and does NOT dispose the item found. It just excludes the item from the set
 701             and returns a pointer to item found.
 702             You should lock RCU before calling of the function, and you should synchronize RCU
 703             outside the RCU lock before reusing returned pointer.
 704
 705             \code
 706             typedef cds::urcu::gc< general_buffered<> > rcu;
 707             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 708             typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
 709
 710             rcu_splitlist_set theSet;
 711             // ...
 712
 713             rcu_splitlist_set::exempt_ptr p;
 714             {
 715                 // first, we should lock RCU
 716                 rcu_splitlist_set::rcu_lock lock;
 717
 718                 // Now, you can apply extract function
 719                 // Note that you must not delete the item found inside the RCU lock
 720                 if ( theList.extract( p, 10 )) {
 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         bool extract( exempt_ptr& dest, Q const& key )
 734         {
 735             value_type * pNode = extract_( key, key_comparator() );
 736             if ( pNode ) {
 737                 dest = pNode;
 738                 return true;
 739             }
 740             return false;
 741         }
 742
 743         /// Extracts an item from the set using \p pred for searching
 744         /**
 745             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
 746             but \p pred is used for key compare.
 747             \p Less functor has the interface like \p std::less.
 748             \p pred must imply the same element order as the comparator used for building the set.
 749         */
 750         template <typename Q, typename Less>
 751         bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
 752         {
 753             value_type * pNode = extract_with_( key, pred );
 754             if ( pNode ) {
 755                 dest = pNode;
 756                 return true;
 757             }
 758             return false;
 759         }
 760
 761         /// Finds the key \p key
 762         /** \anchor cds_intrusive_SplitListSet_rcu_find_func
 763             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 764             The interface of \p Func functor is:
 765             \code
 766             struct functor {
 767                 void operator()( value_type& item, Q& key );
 768             };
 769             \endcode
 770             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 771
 772             You can pass \p f argument by value or by reference using \p std::ref.
 773
 774             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 775             that \p item cannot be disposed during functor is executing.
 776             The functor does not serialize simultaneous access to the set \p item. If such access is
 777             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 778
 779             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 780             can modify both arguments.
 781
 782             Note the hash functor specified for class \p Traits template parameter
 783             should accept a parameter of type \p Q that can be not the same as \p value_type.
 784
 785             The function applies RCU lock internally.
 786
 787             The function returns \p true if \p key is found, \p false otherwise.
 788         */
 789         template <typename Q, typename Func>
 790         bool find( Q& key, Func f )
 791         {
 792             return find_( key, key_comparator(), f );
 793         }
 794
 795         /// Finds the key \p key with \p pred predicate for comparing
 796         /**
 797             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
 798             but \p cmp is used for key compare.
 799             \p Less has the interface like \p std::less.
 800             \p cmp must imply the same element order as the comparator used for building the set.
 801         */
 802         template <typename Q, typename Less, typename Func>
 803         bool find_with( Q& key, Less pred, Func f )
 804         {
 805             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 806         }
 807
 808
 809         /// Finds the key \p key
 810         /** \anchor cds_intrusive_SplitListSet_rcu_find_val
 811             The function searches the item with key equal to \p key
 812             and returns \p true if \p key found or \p false otherwise.
 813         */
 814         template <typename Q>
 815         bool find( Q const& key )
 816         {
 817             return find_value( key, key_comparator() );
 818         }
 819
 820         /// Finds the key \p key with \p pred predicate for comparing
 821         /**
 822             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_val "find(Q const&)"
 823             but \p cmp is used for key compare.
 824             \p Less has the interface like \p std::less.
 825             \p pred must imply the same element order as the comparator used for building the set.
 826         */
 827         template <typename Q, typename Less>
 828         bool find_with( Q const& key, Less pred )
 829         {
 830             return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 831         }
 832
 833         /// Finds the key \p key and return the item found
 834         /** \anchor cds_intrusive_SplitListSet_rcu_get
 835             The function searches the item with key equal to \p key and returns the pointer to item found.
 836             If \p key is not found it returns \p nullptr.
 837
 838             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 839
 840             RCU should be locked before call of this function.
 841             Returned item is valid only while RCU is locked:
 842             \code
 843             cds::intrusive::SplitListSet< your_template_parameters > theSet;
 844             // ...
 845             {
 846                 // Lock RCU
 847                 hash_set::rcu_lock lock;
 848
 849                 foo * pVal = theSet.get( 5 );
 850                 if ( pVal ) {
 851                     // Deal with pVal
 852                     //...
 853                 }
 854                 // Unlock RCU by rcu_lock destructor
 855                 // pVal can be retired by disposer at any time after RCU has been unlocked
 856             }
 857             \endcode
 858         */
 859         template <typename Q>
 860         value_type * get( Q const& key )
 861         {
 862             return get_( key, key_comparator() );
 863         }
 864
 865         /// Finds the key \p key and return the item found
 866         /**
 867             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
 868             but \p pred is used for comparing the keys.
 869
 870             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 871             in any order.
 872             \p pred must imply the same element order as the comparator used for building the set.
 873         */
 874         template <typename Q, typename Less>
 875         value_type * get_with( Q const& key, Less pred )
 876         {
 877             return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 878         }
 879
 880
 881         /// Returns item count in the set
 882         size_t size() const
 883         {
 884             return m_ItemCounter;
 885         }
 886
 887         /// Checks if the set is empty
 888         /**
 889             Emptiness is checked by item counting: if item count is zero then the set is empty.
 890             Thus, the correct item counting feature is an important part of split-list set implementation.
 891         */
 892         bool empty() const
 893         {
 894             return size() == 0;
 895         }
 896
 897         /// Clears the set (not atomic)
 898         void clear()
 899         {
 900             iterator it = begin();
 901             while ( it != end() ) {
 902                 iterator i(it);
 903                 ++i;
 904                 unlink( *it );
 905                 it = i;
 906             }
 907         }
 908
 909         /// Returns internal statistics
 910         stat const& statistics() const
 911         {
 912             return m_Stat;
 913         }
 914
 915     protected:
 916         //@cond
 917         template <bool IsConst>
 918         class iterator_type
 919             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 920         {
 921             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 922             typedef typename iterator_base_class::list_iterator list_iterator;
 923         public:
 924             iterator_type()
 925                 : iterator_base_class()
 926             {}
 927
 928             iterator_type( iterator_type const& src )
 929                 : iterator_base_class( src )
 930             {}
 931
 932             // This ctor should be protected...
 933             iterator_type( list_iterator itCur, list_iterator itEnd )
 934                 : iterator_base_class( itCur, itEnd )
 935             {}
 936         };
 937         //@endcond
 938     public:
 939         /// Forward iterator
 940         /**
 941             The forward iterator for a split-list has some features:
 942             - it has no post-increment operator
 943             - it depends on iterator of underlying \p OrderedList
 944             - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
 945             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 946               deleting operations it is no guarantee that you iterate all item in the split-list.
 947
 948             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 949             for debug purpose only.
 950         */
 951         typedef iterator_type<false>    iterator;
 952         /// Const forward iterator
 953         /**
 954             For iterator's features and requirements see \ref iterator
 955         */
 956         typedef iterator_type<true>     const_iterator;
 957
 958         /// Returns a forward iterator addressing the first element in a split-list
 959         /**
 960             For empty list \code begin() == end() \endcode
 961         */
 962         iterator begin()
 963         {
 964             return iterator( m_List.begin(), m_List.end() );
 965         }
 966
 967         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 968         /**
 969             Do not use the value returned by <tt>end</tt> function to access any item.
 970
 971             The returned value can be used only to control reaching the end of the split-list.
 972             For empty list \code begin() == end() \endcode
 973         */
 974         iterator end()
 975         {
 976             return iterator( m_List.end(), m_List.end() );
 977         }
 978
 979         /// Returns a forward const iterator addressing the first element in a split-list
 980         const_iterator begin() const
 981         {
 982             return cbegin();
 983         }
 984         /// Returns a forward const iterator addressing the first element in a split-list
 985         const_iterator cbegin() const
 986         {
 987             return const_iterator( m_List.cbegin(), m_List.cend() );
 988         }
 989
 990         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 991         const_iterator end() const
 992         {
 993             return cend();
 994         }
 995         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 996         const_iterator cend() const
 997         {
 998             return const_iterator( m_List.cend(), m_List.cend() );
 999         }
1000
1001     };
1002
1003 }}  // namespace cds::intrusive
1004
1005 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_RCU_H