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