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/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         CDS_ATOMIC::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(CDS_ATOMIC::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(CDS_ATOMIC::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, CDS_ATOMIC::memory_order_seq_cst, CDS_ATOMIC::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 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 357             return m_List.find_at( pHead, sv, cmp,
 358                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ cds::unref(f)(item, val.val ); });
 359 #       else
 360             split_list::details::find_functor_wrapper<Func> ffw( f );
 361             return m_List.find_at( pHead, sv, cmp, cds::ref(ffw) );
 362 #       endif
 363         }
 364
 365         template <typename Q, typename Compare>
 366         bool find_value( Q const& val, Compare cmp )
 367         {
 368             size_t nHash = hash_value( val );
 369             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 370             dummy_node_type * pHead = get_bucket( nHash );
 371             assert( pHead != nullptr );
 372
 373             return m_List.find_at( pHead, sv, cmp );
 374         }
 375
 376         template <typename Q, typename Compare>
 377         value_type * get_( Q const& val, Compare cmp )
 378         {
 379             size_t nHash = hash_value( val );
 380             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 381             dummy_node_type * pHead = get_bucket( nHash );
 382             assert( pHead != nullptr );
 383
 384             return m_List.get_at( pHead, sv, cmp );
 385         }
 386
 387         template <typename Q, typename Compare>
 388         value_type * extract_( Q const& val, Compare cmp )
 389         {
 390             size_t nHash = hash_value( val );
 391             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 392             dummy_node_type * pHead = get_bucket( nHash );
 393             assert( pHead != nullptr );
 394
 395             value_type * pNode = m_List.extract_at( pHead, sv, cmp );
 396             if ( pNode )
 397                 --m_ItemCounter;
 398             return pNode;
 399         }
 400
 401         template <typename Q, typename Less>
 402         value_type * extract_with_( Q const& val, Less pred )
 403         {
 404             return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 405         }
 406
 407         template <typename Q, typename Compare>
 408         bool erase_( const Q& val, Compare cmp )
 409         {
 410             size_t nHash = hash_value( val );
 411             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 412             dummy_node_type * pHead = get_bucket( nHash );
 413             assert( pHead != nullptr );
 414
 415             if ( m_List.erase_at( pHead, sv, cmp ) ) {
 416                 --m_ItemCounter;
 417                 return true;
 418             }
 419             return false;
 420         }
 421
 422         template <typename Q, typename Compare, typename Func>
 423         bool erase_( Q const& val, Compare cmp, Func f )
 424         {
 425             size_t nHash = hash_value( val );
 426             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 427             dummy_node_type * pHead = get_bucket( nHash );
 428             assert( pHead != nullptr );
 429
 430             if ( m_List.erase_at( pHead, sv, cmp, f )) {
 431                 --m_ItemCounter;
 432                 return true;
 433             }
 434             return false;
 435         }
 436
 437         //@endcond
 438
 439     public:
 440         /// Initialize split-ordered list of default capacity
 441         /**
 442             The default capacity is defined in bucket table constructor.
 443             See split_list::expandable_bucket_table, split_list::static_ducket_table
 444             which selects by split_list::dynamic_bucket_table option.
 445         */
 446         SplitListSet()
 447             : m_nBucketCountLog2(1)
 448         {
 449             init();
 450         }
 451
 452         /// Initialize split-ordered list
 453         SplitListSet(
 454             size_t nItemCount           ///< estimate average of item count
 455             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 456             )
 457             : m_Buckets( nItemCount, nLoadFactor )
 458             , m_nBucketCountLog2(1)
 459         {
 460             init();
 461         }
 462
 463     public:
 464         /// Inserts new node
 465         /**
 466             The function inserts \p val in the set if it does not contain
 467             an item with key equal to \p val.
 468
 469             The function makes RCU lock internally.
 470
 471             Returns \p true if \p val is placed into the set, \p false otherwise.
 472         */
 473         bool insert( value_type& val )
 474         {
 475             size_t nHash = hash_value( val );
 476             dummy_node_type * pHead = get_bucket( nHash );
 477             assert( pHead != nullptr );
 478
 479             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 480
 481             if ( m_List.insert_at( pHead, val )) {
 482                 inc_item_count();
 483                 return true;
 484             }
 485             return false;
 486         }
 487
 488         /// Inserts new node
 489         /**
 490             This function is intended for derived non-intrusive containers.
 491
 492             The function allows to split creating of new item into two part:
 493             - create item with key only
 494             - insert new item into the set
 495             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 496
 497             The functor signature is:
 498             \code
 499                 void func( value_type& val );
 500             \endcode
 501             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 502             \p val no any other changes could be made on this set's item by concurrent threads.
 503             The user-defined functor is called only if the inserting is success and may be passed by reference
 504             using <tt>boost::ref</tt>
 505
 506             The function makes RCU lock internally.
 507         */
 508         template <typename Func>
 509         bool insert( value_type& val, Func f )
 510         {
 511             size_t nHash = hash_value( val );
 512             dummy_node_type * pHead = get_bucket( nHash );
 513             assert( pHead != nullptr );
 514
 515             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 516
 517             if ( m_List.insert_at( pHead, val, f )) {
 518                 inc_item_count();
 519                 return true;
 520             }
 521             return false;
 522         }
 523
 524         /// Ensures that the \p val exists in the set
 525         /**
 526             The operation performs inserting or changing data with lock-free manner.
 527
 528             If the item \p val is not found in the set, then \p val is inserted into the set.
 529             Otherwise, the functor \p func is called with item found.
 530             The functor signature is:
 531             \code
 532                 void func( bool bNew, value_type& item, value_type& val );
 533             \endcode
 534             with arguments:
 535             - \p bNew - \p true if the item has been inserted, \p false otherwise
 536             - \p item - item of the set
 537             - \p val - argument \p val passed into the \p ensure function
 538             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 539             refers to the same thing.
 540
 541             The functor can change non-key fields of the \p item; however, \p func must guarantee
 542             that during changing no any other modifications could be made on this item by concurrent threads.
 543
 544             You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 545
 546             The function makes RCU lock internally.
 547
 548             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 549             \p second is \p true if new item has been added or \p false if the item with \p key
 550             already is in the set.
 551         */
 552         template <typename Func>
 553         std::pair<bool, bool> ensure( value_type& val, Func func )
 554         {
 555             size_t nHash = hash_value( val );
 556             dummy_node_type * pHead = get_bucket( nHash );
 557             assert( pHead != nullptr );
 558
 559             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 560
 561             std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
 562             if ( bRet.first && bRet.second )
 563                 inc_item_count();
 564             return bRet;
 565         }
 566
 567         /// Unlinks the item \p val from the set
 568         /**
 569             The function searches the item \p val in the set and unlinks it from the set
 570             if it is found and is equal to \p val.
 571
 572             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 573             and deletes the item found. \p unlink finds an item by key and deletes it
 574             only if \p val is an item of that set, i.e. the pointer to item found
 575             is equal to <tt> &val </tt>.
 576
 577             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 578
 579             The function returns \p true if success and \p false otherwise.
 580         */
 581         bool unlink( value_type& val )
 582         {
 583             size_t nHash = hash_value( val );
 584             dummy_node_type * pHead = get_bucket( nHash );
 585             assert( pHead != nullptr );
 586
 587             if ( m_List.unlink_at( pHead, val ) ) {
 588                 --m_ItemCounter;
 589                 return true;
 590             }
 591             return false;
 592         }
 593
 594         /// Deletes the item from the set
 595         /** \anchor cds_intrusive_SplitListSet_rcu_erase
 596             The function searches an item with key equal to \p val in the set,
 597             unlinks it from the set, and returns \p true.
 598             If the item with key equal to \p val is not found the function return \p false.
 599
 600             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 601             and deletes the item found. \p unlink finds an item by key and deletes it
 602             only if \p val is an item of that set, i.e. the pointer to item found
 603             is equal to <tt> &val </tt>.
 604
 605             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 606
 607             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 608         */
 609         template <typename Q>
 610         bool erase( Q const& val )
 611         {
 612             return erase_( val, key_comparator() );
 613         }
 614
 615         /// Deletes the item from the set using \p pred for searching
 616         /**
 617             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
 618             but \p cmp is used for key compare.
 619             \p Less has the interface like \p std::less.
 620             \p pred must imply the same element order as the comparator used for building the set.
 621         */
 622         template <typename Q, typename Less>
 623         bool erase_with( Q const& val, Less pred )
 624         {
 625             return erase_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 626         }
 627
 628         /// Deletes the item from the set
 629         /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
 630             The function searches an item with key equal to \p val in the set,
 631             call \p f functor with item found, unlinks it from the set, and returns \p true.
 632             The \ref disposer specified by \p OrderedList class template parameter is called
 633             by garbage collector \p GC asynchronously.
 634
 635             The \p Func interface is
 636             \code
 637             struct functor {
 638                 void operator()( value_type const& item );
 639             };
 640             \endcode
 641             The functor can be passed by reference with <tt>boost:ref</tt>
 642
 643             If the item with key equal to \p val is not found the function return \p false.
 644
 645             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 646
 647             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 648         */
 649         template <typename Q, typename Func>
 650         bool erase( Q const& val, Func f )
 651         {
 652             return erase_( val, key_comparator(), f );
 653         }
 654
 655         /// Deletes the item from the set using \p pred for searching
 656         /**
 657             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
 658             but \p cmp is used for key compare.
 659             \p Less has the interface like \p std::less.
 660             \p pred must imply the same element order as the comparator used for building the set.
 661         */
 662         template <typename Q, typename Less, typename Func>
 663         bool erase_with( Q const& val, Less pred, Func f )
 664         {
 665             return erase_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 666         }
 667
 668         /// Extracts an item from the set
 669         /** \anchor cds_intrusive_SplitListSet_rcu_extract
 670             The function searches an item with key equal to \p val in the set,
 671             unlinks it, and returns pointer to an item found in \p dest argument.
 672             If the item with the key equal to \p val is not found the function returns \p false.
 673
 674             @note The function does NOT call RCU read-side lock or synchronization,
 675             and does NOT dispose the item found. It just excludes the item from the set
 676             and returns a pointer to item found.
 677             You should lock RCU before calling of the function, and you should synchronize RCU
 678             outside the RCU lock before reusing returned pointer.
 679
 680             \code
 681             typedef cds::urcu::gc< general_buffered<> > rcu;
 682             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 683             typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
 684
 685             rcu_splitlist_set theSet;
 686             // ...
 687
 688             rcu_splitlist_set::exempt_ptr p;
 689             {
 690                 // first, we should lock RCU
 691                 rcu_splitlist_set::rcu_lock lock;
 692
 693                 // Now, you can apply extract function
 694                 // Note that you must not delete the item found inside the RCU lock
 695                 if ( theList.extract( p, 10 )) {
 696                     // do something with p
 697                     ...
 698                 }
 699             }
 700
 701             // We may safely release p here
 702             // release() passes the pointer to RCU reclamation cycle:
 703             // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
 704             p.release();
 705             \endcode
 706         */
 707         template <typename Q>
 708         bool extract( exempt_ptr& dest, Q const& val )
 709         {
 710             value_type * pNode = extract_( val, key_comparator() );
 711             if ( pNode ) {
 712                 dest = pNode;
 713                 return true;
 714             }
 715             return false;
 716         }
 717
 718         /// Extracts an item from the set using \p pred for searching
 719         /**
 720             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
 721             but \p pred is used for key compare.
 722             \p Less functor has the interface like \p std::less.
 723             \p pred must imply the same element order as the comparator used for building the set.
 724         */
 725         template <typename Q, typename Less>
 726         bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
 727         {
 728             value_type * pNode = extract_with_( val, pred );
 729             if ( pNode ) {
 730                 dest = pNode;
 731                 return true;
 732             }
 733             return false;
 734         }
 735
 736         /// Finds the key \p val
 737         /** \anchor cds_intrusive_SplitListSet_rcu_find_func
 738             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 739             The interface of \p Func functor is:
 740             \code
 741             struct functor {
 742                 void operator()( value_type& item, Q& val );
 743             };
 744             \endcode
 745             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 746
 747             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 748
 749             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 750             that \p item cannot be disposed during functor is executing.
 751             The functor does not serialize simultaneous access to the set \p item. If such access is
 752             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 753
 754             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 755             can modify both arguments.
 756
 757             Note the hash functor specified for class \p Traits template parameter
 758             should accept a parameter of type \p Q that can be not the same as \p value_type.
 759
 760             The function applies RCU lock internally.
 761
 762             The function returns \p true if \p val is found, \p false otherwise.
 763         */
 764         template <typename Q, typename Func>
 765         bool find( Q& val, Func f )
 766         {
 767             return find_( val, key_comparator(), f );
 768         }
 769
 770         /// Finds the key \p val with \p pred predicate for comparing
 771         /**
 772             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
 773             but \p cmp is used for key compare.
 774             \p Less has the interface like \p std::less.
 775             \p cmp must imply the same element order as the comparator used for building the set.
 776         */
 777         template <typename Q, typename Less, typename Func>
 778         bool find_with( Q& val, Less pred, Func f )
 779         {
 780             return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 781         }
 782
 783         /// Finds the key \p val
 784         /** \anchor cds_intrusive_SplitListSet_rcu_find_cfunc
 785             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 786             The interface of \p Func functor is:
 787             \code
 788             struct functor {
 789                 void operator()( value_type& item, Q const& val );
 790             };
 791             \endcode
 792             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 793
 794             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 795
 796             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 797             that \p item cannot be disposed during functor is executing.
 798             The functor does not serialize simultaneous access to the set \p item. If such access is
 799             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 800
 801             Note the hash functor specified for class \p Traits template parameter
 802             should accept a parameter of type \p Q that can be not the same as \p value_type.
 803
 804             The function applies RCU lock internally.
 805
 806             The function returns \p true if \p val is found, \p false otherwise.
 807         */
 808         template <typename Q, typename Func>
 809         bool find( Q const& val, Func f )
 810         {
 811             return find_( val, key_comparator(), f );
 812         }
 813
 814         /// Finds the key \p val with \p pred predicate for comparing
 815         /**
 816             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_cfunc "find(Q const&, Func)"
 817             but \p cmp is used for key compare.
 818             \p Less has the interface like \p std::less.
 819             \p pred must imply the same element order as the comparator used for building the set.
 820         */
 821         template <typename Q, typename Less, typename Func>
 822         bool find_with( Q const& val, Less pred, Func f )
 823         {
 824             return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 825         }
 826
 827         /// Finds the key \p val
 828         /** \anchor cds_intrusive_SplitListSet_rcu_find_val
 829             The function searches the item with key equal to \p val
 830             and returns \p true if \p val found or \p false otherwise.
 831         */
 832         template <typename Q>
 833         bool find( Q const& val )
 834         {
 835             return find_value( val, key_comparator() );
 836         }
 837
 838         /// Finds the key \p val with \p pred predicate for comparing
 839         /**
 840             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_val "find(Q const&)"
 841             but \p cmp is used for key compare.
 842             \p Less has the interface like \p std::less.
 843             \p pred must imply the same element order as the comparator used for building the set.
 844         */
 845         template <typename Q, typename Less>
 846         bool find_with( Q const& val, Less pred )
 847         {
 848             return find_value( val, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 849         }
 850
 851         /// Finds the key \p val and return the item found
 852         /** \anchor cds_intrusive_SplitListSet_rcu_get
 853             The function searches the item with key equal to \p val and returns the pointer to item found.
 854             If \p val is not found it returns \p NULL.
 855
 856             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 857
 858             RCU should be locked before call of this function.
 859             Returned item is valid only while RCU is locked:
 860             \code
 861             cds::intrusive::SplitListSet< your_template_parameters > theSet;
 862             // ...
 863             {
 864                 // Lock RCU
 865                 hash_set::rcu_lock lock;
 866
 867                 foo * pVal = theSet.get( 5 );
 868                 if ( pVal ) {
 869                     // Deal with pVal
 870                     //...
 871                 }
 872                 // Unlock RCU by rcu_lock destructor
 873                 // pVal can be retired by disposer at any time after RCU has been unlocked
 874             }
 875             \endcode
 876         */
 877         template <typename Q>
 878         value_type * get( Q const& val )
 879         {
 880             return get_( val, key_comparator() );
 881         }
 882
 883         /// Finds the key \p val and return the item found
 884         /**
 885             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
 886             but \p pred is used for comparing the keys.
 887
 888             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 889             in any order.
 890             \p pred must imply the same element order as the comparator used for building the set.
 891         */
 892         template <typename Q, typename Less>
 893         value_type * get_with( Q const& val, Less pred )
 894         {
 895             return get_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 896         }
 897
 898
 899         /// Returns item count in the set
 900         size_t size() const
 901         {
 902             return m_ItemCounter;
 903         }
 904
 905         /// Checks if the set is empty
 906         /**
 907             Emptiness is checked by item counting: if item count is zero then the set is empty.
 908             Thus, the correct item counting feature is an important part of split-list set implementation.
 909         */
 910         bool empty() const
 911         {
 912             return size() == 0;
 913         }
 914
 915         /// Clears the set (non-atomic)
 916         /**
 917             The function unlink all items from the set.
 918             The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
 919         */
 920         void clear()
 921         {
 922             iterator it = begin();
 923             while ( it != end() ) {
 924                 iterator i(it);
 925                 ++i;
 926                 unlink( *it );
 927                 it = i;
 928             }
 929         }
 930
 931     protected:
 932         //@cond
 933         template <bool IsConst>
 934         class iterator_type
 935             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 936         {
 937             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 938             typedef typename iterator_base_class::list_iterator list_iterator;
 939         public:
 940             iterator_type()
 941                 : iterator_base_class()
 942             {}
 943
 944             iterator_type( iterator_type const& src )
 945                 : iterator_base_class( src )
 946             {}
 947
 948             // This ctor should be protected...
 949             iterator_type( list_iterator itCur, list_iterator itEnd )
 950                 : iterator_base_class( itCur, itEnd )
 951             {}
 952         };
 953         //@endcond
 954     public:
 955         /// Forward iterator
 956         /**
 957             The forward iterator for a split-list has some features:
 958             - it has no post-increment operator
 959             - it depends on iterator of underlying \p OrderedList
 960             - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
 961             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 962               deleting operations it is no guarantee that you iterate all item in the split-list.
 963
 964             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 965             for debug purpose only.
 966         */
 967         typedef iterator_type<false>    iterator;
 968         /// Const forward iterator
 969         /**
 970             For iterator's features and requirements see \ref iterator
 971         */
 972         typedef iterator_type<true>     const_iterator;
 973
 974         /// Returns a forward iterator addressing the first element in a split-list
 975         /**
 976             For empty list \code begin() == end() \endcode
 977         */
 978         iterator begin()
 979         {
 980             return iterator( m_List.begin(), m_List.end() );
 981         }
 982
 983         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 984         /**
 985             Do not use the value returned by <tt>end</tt> function to access any item.
 986
 987             The returned value can be used only to control reaching the end of the split-list.
 988             For empty list \code begin() == end() \endcode
 989         */
 990         iterator end()
 991         {
 992             return iterator( m_List.end(), m_List.end() );
 993         }
 994
 995         /// Returns a forward const iterator addressing the first element in a split-list
 996         const_iterator begin() const
 997         {
 998             return const_iterator( m_List.begin(), m_List.end() );
 999         }
1000
1001         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1002         const_iterator end() const
1003         {
1004             return const_iterator( m_List.end(), m_List.end() );
1005         }
1006
1007     };
1008
1009 }}  // namespace cds::intrusive
1010
1011 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_RCU_H