3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H
4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
6 #include <cds/intrusive/details/split_list_base.h>
8 namespace cds { namespace intrusive {
10 /// Split-ordered list
11 /** @ingroup cds_intrusive_map
12 \anchor cds_intrusive_SplitListSet_hp
14 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
15 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
16 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
18 The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
19 recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
20 without item moving on resizing.
22 \anchor cds_SplitList_algo_desc
23 <b>Short description</b>
24 [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
26 The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
27 the places in the list where a sublist of
\93correct
\94 items can be found. A bucket is initialized upon first
28 access by assigning it to a new
\93dummy
\94 node (dashed contour) in the list, preceding all items that should be
29 in that bucket. A newly created bucket splits an older bucket
\92s chain, reducing the access cost to its items. The
30 table uses a modulo 2**i hash (there are known techniques for
\93pre-hashing
\94 before a modulo 2**i hash
31 to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
33 Unlike moving an item, the operation of directing a bucket pointer can be done
34 in a single CAS operation, and since items are not moved, they are never
\93lost
\94.
35 However, to make this approach work, one must be able to keep the items in the
36 list sorted in such a way that any bucket
\92s sublist can be
\93split
\94 by directing a new
37 bucket pointer within it. This operation must be recursively repeatable, as every
38 split bucket may be split again and again as the hash table grows. To achieve this
39 goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
40 in a given bucket adjacent in the list throughout the repeated splitting process.
42 Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
43 simple binary reversal: reversing the bits of the hash key so that the new key
\92s
44 most significant bits (MSB) are those that were originally its least significant.
45 The split-order keys of regular nodes are exactly the bit-reverse image of the original
46 keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
47 4</tt> bucket, which can be recursively split in two by inserting a new node between
50 To insert (respectively delete or search for) an item in the hash table, hash its
51 key to the appropriate bucket using recursive split-ordering, follow the pointer to
52 the appropriate location in the sorted items list, and traverse the list until the key
\92s
53 proper location in the split-ordering (respectively until the key or a key indicating
54 the item is not in the list is found). Because of the combinatorial structure induced
55 by the split-ordering, this will require traversal of no more than an expected constant number of items.
57 The design is modular: to implement the ordered items list, you can use one of several
58 non-blocking list-based set algorithms: MichaelList, LazyList.
62 Template parameters are:
63 - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
64 - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
65 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
66 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
68 - \p Traits - split-list traits, default is \p split_list::traits.
69 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
71 There are several specialization of the split-list class for different \p GC:
72 - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
73 \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
74 - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
75 \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
77 \anchor cds_SplitList_hash_functor
80 Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
81 It is expected that type \p Q contains full key of \p value_type, and for equal keys of type \p Q and \p value_type
82 the hash values of these keys must be equal too.
83 The hash functor \p Traits::hash should accept parameters of both type:
87 std::string key_ ; // key field
93 size_t operator()( const std::string& s ) const
95 return std::hash( s );
98 size_t operator()( const Foo& f ) const
100 return (*this)( f.key_ );
107 First, you should choose ordered list type to use in your split-list set:
109 // For gc::HP-based MichaelList implementation
110 #include <cds/intrusive/michael_list_hp.h>
112 // cds::intrusive::SplitListSet declaration
113 #include <cds/intrusive/split_list.h>
116 // Note you should declare your struct based on cds::intrusive::split_list::node
117 // which is a wrapper for ordered-list node struct.
118 // In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
119 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
121 std::string key_ ; // key field
122 unsigned val_ ; // value field
123 // ... other value fields
126 // Declare comparator for the item
129 int operator()( const Foo& f1, const Foo& f2 ) const
131 return f1.key_.compare( f2.key_ );
135 // Declare base ordered-list type for split-list
136 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
137 typename cds::intrusive::michael_list::make_traits<
139 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
140 // item comparator option
141 ,cds::opt::compare< FooCmp >
146 Second, you should declare split-list set container:
149 // Declare hash functor
150 // Note, the hash functor accepts parameter type Foo and std::string
152 size_t operator()( const Foo& f ) const
154 return cds::opt::v::hash<std::string>()( f.key_ );
156 size_t operator()( const std::string& s ) const
158 return cds::opt::v::hash<std::string>()( s );
162 // Split-list set typedef
163 typedef cds::intrusive::SplitListSet<
166 ,typename cds::intrusive::split_list::make_traits<
167 cds::opt::hash< FooHash >
172 Now, you can use \p Foo_set in your application.
178 fooSet.insert( *foo );
186 # ifdef CDS_DOXYGEN_INVOKED
187 class Traits = split_list::traits
195 typedef GC gc; ///< Garbage collector
196 typedef Traits traits; ///< Set traits
199 typedef cds::intrusive::split_list::implementation_tag implementation_tag;
204 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
208 # ifdef CDS_DOXYGEN_INVOKED
209 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
211 typedef typename wrapped_ordered_list::result ordered_list;
213 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
214 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
215 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
217 /// Hash functor for \p %value_type and all its derivatives that you use
218 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
220 typedef typename traits::item_counter item_counter; ///< Item counter type
221 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
222 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
223 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
224 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
227 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
228 typedef split_list::node<list_node_type> node_type; ///< split-list node type
229 typedef node_type dummy_node_type; ///< dummy node type
231 /// Split-list node traits
233 This traits is intended for converting between underlying ordered list node type \p list_node_type
234 and split-list node type \p node_type
236 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
239 /// Bucket table implementation
240 typedef typename split_list::details::bucket_table_selector<
241 traits::dynamic_bucket_table
244 , opt::allocator< typename traits::allocator >
245 , opt::memory_model< memory_model >
246 >::type bucket_table;
251 /// Ordered list wrapper to access protected members
252 class ordered_list_wrapper: public ordered_list
254 typedef ordered_list base_class;
255 typedef typename base_class::auxiliary_head bucket_head_type;
258 bool insert_at( dummy_node_type * pHead, value_type& val )
260 assert( pHead != nullptr );
261 bucket_head_type h(pHead);
262 return base_class::insert_at( h, val );
265 template <typename Func>
266 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
268 assert( pHead != nullptr );
269 bucket_head_type h(pHead);
270 return base_class::insert_at( h, val, f );
273 template <typename Func>
274 std::pair<bool, bool> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
276 assert( pHead != nullptr );
277 bucket_head_type h(pHead);
278 return base_class::ensure_at( h, val, func );
281 bool unlink_at( dummy_node_type * pHead, value_type& val )
283 assert( pHead != nullptr );
284 bucket_head_type h(pHead);
285 return base_class::unlink_at( h, val );
288 template <typename Q, typename Compare, typename Func>
289 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
291 assert( pHead != nullptr );
292 bucket_head_type h(pHead);
293 return base_class::erase_at( h, val, cmp, f );
296 template <typename Q, typename Compare>
297 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
299 assert( pHead != nullptr );
300 bucket_head_type h(pHead);
301 return base_class::erase_at( h, val, cmp );
304 template <typename Q, typename Compare>
305 bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
307 assert( pHead != nullptr );
308 bucket_head_type h(pHead);
309 return base_class::extract_at( h, guard, val, cmp );
312 template <typename Q, typename Compare, typename Func>
313 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
315 assert( pHead != nullptr );
316 bucket_head_type h(pHead);
317 return base_class::find_at( h, val, cmp, f );
320 template <typename Q, typename Compare>
321 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
323 assert( pHead != nullptr );
324 bucket_head_type h(pHead);
325 return base_class::find_at( h, val, cmp );
328 template <typename Q, typename Compare>
329 bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
331 assert( pHead != nullptr );
332 bucket_head_type h(pHead);
333 return base_class::get_at( h, guard, val, cmp );
336 bool insert_aux_node( dummy_node_type * pNode )
338 return base_class::insert_aux_node( pNode );
340 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
342 bucket_head_type h(pHead);
343 return base_class::insert_aux_node( h, pNode );
349 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
350 bucket_table m_Buckets; ///< bucket table
351 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
352 item_counter m_ItemCounter; ///< Item counter
353 hash m_HashFunctor; ///< Hash functor
354 stat m_Stat; ///< Internal statistics
358 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
360 dummy_node_type * alloc_dummy_node( size_t nHash )
362 m_Stat.onHeadNodeAllocated();
363 return dummy_node_allocator().New( nHash );
365 void free_dummy_node( dummy_node_type * p )
367 dummy_node_allocator().Delete( p );
368 m_Stat.onHeadNodeFreed();
371 /// Calculates hash value of \p key
372 template <typename Q>
373 size_t hash_value( Q const& key ) const
375 return m_HashFunctor( key );
378 size_t bucket_no( size_t nHash ) const
380 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
383 static size_t parent_bucket( size_t nBucket )
385 assert( nBucket > 0 );
386 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
389 dummy_node_type * init_bucket( size_t nBucket )
391 assert( nBucket > 0 );
392 size_t nParent = parent_bucket( nBucket );
394 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
395 if ( pParentBucket == nullptr ) {
396 pParentBucket = init_bucket( nParent );
397 m_Stat.onRecursiveInitBucket();
400 assert( pParentBucket != nullptr );
402 // Allocate a dummy node for new bucket
404 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
405 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
406 m_Buckets.bucket( nBucket, pBucket );
407 m_Stat.onNewBucket();
410 free_dummy_node( pBucket );
413 // Another thread set the bucket. Wait while it done
415 // In this point, we must wait while nBucket is empty.
416 // The compiler can decide that waiting loop can be "optimized" (stripped)
417 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
418 m_Stat.onBucketInitContenton();
421 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
423 return const_cast<dummy_node_type *>( p );
425 m_Stat.onBusyWaitBucketInit();
429 dummy_node_type * get_bucket( size_t nHash )
431 size_t nBucket = bucket_no( nHash );
433 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
434 if ( pHead == nullptr )
435 pHead = init_bucket( nBucket );
437 assert( pHead->is_dummy() );
444 // GC and OrderedList::gc must be the same
445 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
447 // atomicity::empty_item_counter is not allowed as a item counter
448 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
449 "cds::atomicity::empty_item_counter is not allowed as a item counter");
451 // Initialize bucket 0
452 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
454 // insert_aux_node cannot return false for empty list
455 CDS_VERIFY( m_List.insert_aux_node( pNode ));
457 m_Buckets.bucket( 0, pNode );
460 void inc_item_count()
462 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
463 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
465 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
469 template <typename Q, typename Compare, typename Func>
470 bool find_( Q& val, Compare cmp, Func f )
472 size_t nHash = hash_value( val );
473 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
474 dummy_node_type * pHead = get_bucket( nHash );
475 assert( pHead != nullptr );
477 return m_Stat.onFind(
478 m_List.find_at( pHead, sv, cmp,
479 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
483 template <typename Q, typename Compare>
484 bool find_( Q const& val, Compare cmp )
486 size_t nHash = hash_value( val );
487 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
488 dummy_node_type * pHead = get_bucket( nHash );
489 assert( pHead != nullptr );
491 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
494 template <typename Q, typename Compare>
495 bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
497 size_t nHash = hash_value( val );
498 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
499 dummy_node_type * pHead = get_bucket( nHash );
500 assert( pHead != nullptr );
502 return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
505 template <typename Q>
506 bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
508 return get_( guard, key, key_comparator());
511 template <typename Q, typename Less>
512 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
514 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
517 template <typename Q, typename Compare, typename Func>
518 bool erase_( Q const& val, Compare cmp, Func f )
520 size_t nHash = hash_value( val );
521 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
522 dummy_node_type * pHead = get_bucket( nHash );
523 assert( pHead != nullptr );
525 if ( m_List.erase_at( pHead, sv, cmp, f )) {
527 m_Stat.onEraseSuccess();
530 m_Stat.onEraseFailed();
534 template <typename Q, typename Compare>
535 bool erase_( Q const& val, Compare cmp )
537 size_t nHash = hash_value( val );
538 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
539 dummy_node_type * pHead = get_bucket( nHash );
540 assert( pHead != nullptr );
542 if ( m_List.erase_at( pHead, sv, cmp ) ) {
544 m_Stat.onEraseSuccess();
547 m_Stat.onEraseFailed();
551 template <typename Q, typename Compare>
552 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
554 size_t nHash = hash_value( val );
555 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
556 dummy_node_type * pHead = get_bucket( nHash );
557 assert( pHead != nullptr );
559 if ( m_List.extract_at( pHead, guard, sv, cmp ) ) {
561 m_Stat.onExtractSuccess();
564 m_Stat.onExtractFailed();
568 template <typename Q>
569 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
571 return extract_( guard, key, key_comparator());
574 template <typename Q, typename Less>
575 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
577 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
582 /// Initialize split-ordered list of default capacity
584 The default capacity is defined in bucket table constructor.
585 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
586 which selects by \p split_list::dynamic_bucket_table option.
589 : m_nBucketCountLog2(1)
594 /// Initialize split-ordered list
596 size_t nItemCount ///< estimate average of item count
597 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
599 : m_Buckets( nItemCount, nLoadFactor )
600 , m_nBucketCountLog2(1)
608 The function inserts \p val in the set if it does not contain
609 an item with key equal to \p val.
611 Returns \p true if \p val is placed into the set, \p false otherwise.
613 bool insert( value_type& val )
615 size_t nHash = hash_value( val );
616 dummy_node_type * pHead = get_bucket( nHash );
617 assert( pHead != nullptr );
619 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
621 if ( m_List.insert_at( pHead, val )) {
623 m_Stat.onInsertSuccess();
626 m_Stat.onInsertFailed();
632 This function is intended for derived non-intrusive containers.
634 The function allows to split creating of new item into two part:
635 - create item with key only
636 - insert new item into the set
637 - if inserting is success, calls \p f functor to initialize value-field of \p val.
639 The functor signature is:
641 void func( value_type& val );
643 where \p val is the item inserted.
644 The user-defined functor is called only if the inserting is success.
646 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
647 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
650 template <typename Func>
651 bool insert( value_type& val, Func f )
653 size_t nHash = hash_value( val );
654 dummy_node_type * pHead = get_bucket( nHash );
655 assert( pHead != nullptr );
657 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
659 if ( m_List.insert_at( pHead, val, f )) {
661 m_Stat.onInsertSuccess();
664 m_Stat.onInsertFailed();
668 /// Ensures that the \p val exists in the set
670 The operation performs inserting or changing data with lock-free manner.
672 If the item \p val is not found in the set, then \p val is inserted into the set.
673 Otherwise, the functor \p func is called with item found.
674 The functor signature is:
676 void func( bool bNew, value_type& item, value_type& val );
679 - \p bNew - \p true if the item has been inserted, \p false otherwise
680 - \p item - item of the set
681 - \p val - argument \p val passed into the \p ensure function
682 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
683 refers to the same thing.
685 The functor can change non-key fields of the \p item.
687 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
688 \p second is \p true if new item has been added or \p false if the item with \p key
689 already is in the set.
691 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
692 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
695 template <typename Func>
696 std::pair<bool, bool> ensure( value_type& val, Func func )
698 size_t nHash = hash_value( val );
699 dummy_node_type * pHead = get_bucket( nHash );
700 assert( pHead != nullptr );
702 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
704 std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
705 if ( bRet.first && bRet.second ) {
707 m_Stat.onEnsureNew();
710 m_Stat.onEnsureExist();
714 /// Unlinks the item \p val from the set
716 The function searches the item \p val in the set and unlinks it from the set
717 if it is found and is equal to \p val.
719 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
720 and deletes the item found. \p unlink finds an item by key and deletes it
721 only if \p val is an item of that set, i.e. the pointer to item found
722 is equal to <tt> &val </tt>.
724 The function returns \p true if success and \p false otherwise.
726 bool unlink( value_type& val )
728 size_t nHash = hash_value( val );
729 dummy_node_type * pHead = get_bucket( nHash );
730 assert( pHead != nullptr );
732 if ( m_List.unlink_at( pHead, val ) ) {
734 m_Stat.onEraseSuccess();
737 m_Stat.onEraseFailed();
741 /// Deletes the item from the set
742 /** \anchor cds_intrusive_SplitListSet_hp_erase
743 The function searches an item with key equal to \p key in the set,
744 unlinks it from the set, and returns \p true.
745 If the item with key equal to \p key is not found the function return \p false.
747 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
748 and deletes the item found. \p unlink finds an item by key and deletes it
749 only if \p key is an item of that set, i.e. the pointer to item found
750 is equal to <tt> &key </tt>.
752 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
754 template <typename Q>
755 bool erase( Q const& key )
757 return erase_( key, key_comparator() );
760 /// Deletes the item from the set with comparing functor \p pred
763 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
764 but \p pred predicate is used for key comparing.
765 \p Less has the interface like \p std::less.
766 \p pred must imply the same element order as the comparator used for building the set.
768 template <typename Q, typename Less>
769 bool erase_with( const Q& key, Less pred )
772 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
775 /// Deletes the item from the set
776 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
777 The function searches an item with key equal to \p key in the set,
778 call \p f functor with item found, unlinks it from the set, and returns \p true.
779 The \ref disposer specified by \p OrderedList class template parameter is called
780 by garbage collector \p GC asynchronously.
782 The \p Func interface is
785 void operator()( value_type const& item );
789 If the item with key equal to \p key is not found the function return \p false.
791 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
793 template <typename Q, typename Func>
794 bool erase( Q const& key, Func f )
796 return erase_( key, key_comparator(), f );
799 /// Deletes the item from the set with comparing functor \p pred
801 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
802 but \p pred predicate is used for key comparing.
803 \p Less has the interface like \p std::less.
804 \p pred must imply the same element order as the comparator used for building the set.
806 template <typename Q, typename Less, typename Func>
807 bool erase_with( Q const& key, Less pred, Func f )
810 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
813 /// Extracts the item with specified \p key
814 /** \anchor cds_intrusive_SplitListSet_hp_extract
815 The function searches an item with key equal to \p key,
816 unlinks it from the set, and returns it as \p guarded_ptr.
817 If \p key is not found the function returns an empty guarded pointer.
819 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
821 The \p disposer specified in \p OrderedList class' template parameter is called automatically
822 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
823 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
827 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
828 splitlist_set theSet;
831 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
836 // Destructor of gp releases internal HP guard
840 template <typename Q>
841 guarded_ptr extract( Q const& key )
844 extract_( gp.guard(), key );
848 /// Extracts the item using compare functor \p pred
850 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
851 but \p pred predicate is used for key comparing.
853 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
855 \p pred must imply the same element order as the comparator used for building the set.
857 template <typename Q, typename Less>
858 guarded_ptr extract_with( Q const& key, Less pred )
861 extract_with_( gp.guard(), key, pred );
865 /// Finds the key \p key
866 /** \anchor cds_intrusive_SplitListSet_hp_find_func
867 The function searches the item with key equal to \p key and calls the functor \p f for item found.
868 The interface of \p Func functor is:
871 void operator()( value_type& item, Q& key );
874 where \p item is the item found, \p key is the <tt>find</tt> function argument.
876 The functor can change non-key fields of \p item. Note that the functor is only guarantee
877 that \p item cannot be disposed during functor is executing.
878 The functor does not serialize simultaneous access to the set \p item. If such access is
879 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
881 Note the hash functor specified for class \p Traits template parameter
882 should accept a parameter of type \p Q that can be not the same as \p value_type.
884 The function returns \p true if \p key is found, \p false otherwise.
886 template <typename Q, typename Func>
887 bool find( Q& key, Func f )
889 return find_( key, key_comparator(), f );
892 template <typename Q, typename Func>
893 bool find( Q const& key, Func f )
895 return find_( key, key_comparator(), f );
899 /// Finds the key \p key with \p pred predicate for comparing
901 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
902 but \p cmp is used for key compare.
903 \p Less has the interface like \p std::less.
904 \p cmp must imply the same element order as the comparator used for building the set.
906 template <typename Q, typename Less, typename Func>
907 bool find_with( Q& key, Less pred, Func f )
910 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
913 template <typename Q, typename Less, typename Func>
914 bool find_with( Q const& key, Less pred, Func f )
917 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
921 /// Finds the key \p key
922 /** \anchor cds_intrusive_SplitListSet_hp_find_val
923 The function searches the item with key equal to \p key
924 and returns \p true if it is found, and \p false otherwise.
926 Note the hash functor specified for class \p Traits template parameter
927 should accept a parameter of type \p Q that can be not the same as \p value_type.
928 Otherwise, you may use \p find_with functions with explicit predicate for key comparing.
930 template <typename Q>
931 bool find( Q const& key )
933 return find_( key, key_comparator() );
936 /// Finds the key \p key with \p pred predicate for comparing
938 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_val "find(Q const&)"
939 but \p cmp is used for key compare.
940 \p Less has the interface like \p std::less.
941 \p cmp must imply the same element order as the comparator used for building the set.
943 template <typename Q, typename Less>
944 bool find_with( Q const& key, Less pred )
947 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
950 /// Finds the key \p key and return the item found
951 /** \anchor cds_intrusive_SplitListSet_hp_get
952 The function searches the item with key equal to \p key
953 and returns the item found as \p guarded_ptr.
954 If \p key is not found the function returns an empty guarded pointer.
956 The \p disposer specified in \p OrderedList class' template parameter is called
957 by garbage collector \p GC automatically when returned \p guarded_ptr object
958 will be destroyed or released.
959 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
963 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
964 splitlist_set theSet;
967 splitlist_set::guarded_ptr gp = theSet.get( 5 );
972 // Destructor of guarded_ptr releases internal HP guard
976 Note the compare functor specified for \p OrderedList template parameter
977 should accept a parameter of type \p Q that can be not the same as \p value_type.
979 template <typename Q>
980 guarded_ptr get( Q const& key )
983 get_( gp.guard(), key );
987 /// Finds the key \p key and return the item found
989 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
990 but \p pred is used for comparing the keys.
992 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
994 \p pred must imply the same element order as the comparator used for building the set.
996 template <typename Q, typename Less>
997 guarded_ptr get_with( Q const& key, Less pred )
1000 get_with_( gp.guard(), key, pred );
1004 /// Returns item count in the set
1007 return m_ItemCounter;
1010 /// Checks if the set is empty
1012 Emptiness is checked by item counting: if item count is zero then the set is empty.
1013 Thus, the correct item counting feature is an important part of split-list set implementation.
1020 /// Clears the set (non-atomic)
1022 The function unlink all items from the set.
1023 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1025 For each item the \p disposer is called after unlinking.
1029 iterator it = begin();
1030 while ( it != end() ) {
1038 /// Returns internal statistics
1039 stat const& statistics() const
1046 template <bool IsConst>
1048 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1050 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1051 typedef typename iterator_base_class::list_iterator list_iterator;
1054 : iterator_base_class()
1057 iterator_type( iterator_type const& src )
1058 : iterator_base_class( src )
1061 // This ctor should be protected...
1062 iterator_type( list_iterator itCur, list_iterator itEnd )
1063 : iterator_base_class( itCur, itEnd )
1068 /// Forward iterator
1070 The forward iterator for a split-list has some features:
1071 - it has no post-increment operator
1072 - it depends on iterator of underlying \p OrderedList
1073 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1074 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1075 deleting operations it is no guarantee that you iterate all item in the split-list.
1077 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1078 for debug purpose only.
1080 typedef iterator_type<false> iterator;
1081 /// Const forward iterator
1083 For iterator's features and requirements see \ref iterator
1085 typedef iterator_type<true> const_iterator;
1087 /// Returns a forward iterator addressing the first element in a split-list
1089 For empty list \code begin() == end() \endcode
1093 return iterator( m_List.begin(), m_List.end() );
1096 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1098 Do not use the value returned by <tt>end</tt> function to access any item.
1100 The returned value can be used only to control reaching the end of the split-list.
1101 For empty list \code begin() == end() \endcode
1105 return iterator( m_List.end(), m_List.end() );
1108 /// Returns a forward const iterator addressing the first element in a split-list
1109 const_iterator begin() const
1113 /// Returns a forward const iterator addressing the first element in a split-list
1114 const_iterator cbegin() const
1116 return const_iterator( m_List.cbegin(), m_List.cend() );
1119 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1120 const_iterator end() const
1124 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1125 const_iterator cend() const
1127 return const_iterator( m_List.cend(), m_List.cend() );
1132 }} // namespace cds::intrusive
1134 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H