3 #ifndef __CDS_INTRUSIVE_SPLIT_LIST_H
4 #define __CDS_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
200 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
204 # ifdef CDS_DOXYGEN_INVOKED
205 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
207 typedef typename wrapped_ordered_list::result ordered_list;
209 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
210 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
211 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
213 /// Hash functor for \p %value_type and all its derivatives that you use
214 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
216 typedef typename traits::item_counter item_counter; ///< Item counter type
217 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
218 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
219 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
220 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
223 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
224 typedef split_list::node<list_node_type> node_type; ///< split-list node type
225 typedef node_type dummy_node_type; ///< dummy node type
227 /// Split-list node traits
229 This traits is intended for converting between underlying ordered list node type \p list_node_type
230 and split-list node type \p node_type
232 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
235 /// Bucket table implementation
236 typedef typename split_list::details::bucket_table_selector<
237 traits::dynamic_bucket_table
240 , opt::allocator< typename traits::allocator >
241 , opt::memory_model< memory_model >
242 >::type bucket_table;
247 /// Ordered list wrapper to access protected members
248 class ordered_list_wrapper: public ordered_list
250 typedef ordered_list base_class;
251 typedef typename base_class::auxiliary_head bucket_head_type;
254 bool insert_at( dummy_node_type * pHead, value_type& val )
256 assert( pHead != nullptr );
257 bucket_head_type h(pHead);
258 return base_class::insert_at( h, val );
261 template <typename Func>
262 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
264 assert( pHead != nullptr );
265 bucket_head_type h(pHead);
266 return base_class::insert_at( h, val, f );
269 template <typename Func>
270 std::pair<bool, bool> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
272 assert( pHead != nullptr );
273 bucket_head_type h(pHead);
274 return base_class::ensure_at( h, val, func );
277 bool unlink_at( dummy_node_type * pHead, value_type& val )
279 assert( pHead != nullptr );
280 bucket_head_type h(pHead);
281 return base_class::unlink_at( h, val );
284 template <typename Q, typename Compare, typename Func>
285 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
287 assert( pHead != nullptr );
288 bucket_head_type h(pHead);
289 return base_class::erase_at( h, val, cmp, f );
292 template <typename Q, typename Compare>
293 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
295 assert( pHead != nullptr );
296 bucket_head_type h(pHead);
297 return base_class::erase_at( h, val, cmp );
300 template <typename Q, typename Compare>
301 bool extract_at( dummy_node_type * pHead, typename gc::Guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
303 assert( pHead != nullptr );
304 bucket_head_type h(pHead);
305 return base_class::extract_at( h, guard, val, cmp );
308 template <typename Q, typename Compare, typename Func>
309 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
311 assert( pHead != nullptr );
312 bucket_head_type h(pHead);
313 return base_class::find_at( h, val, cmp, f );
316 template <typename Q, typename Compare>
317 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
319 assert( pHead != nullptr );
320 bucket_head_type h(pHead);
321 return base_class::find_at( h, val, cmp );
324 template <typename Q, typename Compare>
325 bool get_at( dummy_node_type * pHead, typename gc::Guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
327 assert( pHead != nullptr );
328 bucket_head_type h(pHead);
329 return base_class::get_at( h, guard, val, cmp );
332 bool insert_aux_node( dummy_node_type * pNode )
334 return base_class::insert_aux_node( pNode );
336 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
338 bucket_head_type h(pHead);
339 return base_class::insert_aux_node( h, pNode );
345 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
346 bucket_table m_Buckets; ///< bucket table
347 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
348 item_counter m_ItemCounter; ///< Item counter
349 hash m_HashFunctor; ///< Hash functor
350 stat m_Stat; ///< Internal statistics
354 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
356 dummy_node_type * alloc_dummy_node( size_t nHash )
358 m_Stat.onHeadNodeAllocated();
359 return dummy_node_allocator().New( nHash );
361 void free_dummy_node( dummy_node_type * p )
363 dummy_node_allocator().Delete( p );
364 m_Stat.onHeadNodeFreed();
367 /// Calculates hash value of \p key
368 template <typename Q>
369 size_t hash_value( Q const& key ) const
371 return m_HashFunctor( key );
374 size_t bucket_no( size_t nHash ) const
376 return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
379 static size_t parent_bucket( size_t nBucket )
381 assert( nBucket > 0 );
382 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
385 dummy_node_type * init_bucket( size_t nBucket )
387 assert( nBucket > 0 );
388 size_t nParent = parent_bucket( nBucket );
390 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
391 if ( pParentBucket == nullptr ) {
392 pParentBucket = init_bucket( nParent );
393 m_Stat.onRecursiveInitBucket();
396 assert( pParentBucket != nullptr );
398 // Allocate a dummy node for new bucket
400 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
401 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
402 m_Buckets.bucket( nBucket, pBucket );
403 m_Stat.onNewBucket();
406 free_dummy_node( pBucket );
409 // Another thread set the bucket. Wait while it done
411 // In this point, we must wait while nBucket is empty.
412 // The compiler can decide that waiting loop can be "optimized" (stripped)
413 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
415 m_Stat.onBucketInitContenton();
418 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
420 return const_cast<dummy_node_type *>( p );
422 m_Stat.onBusyWaitBucketInit();
426 dummy_node_type * get_bucket( size_t nHash )
428 size_t nBucket = bucket_no( nHash );
430 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
431 if ( pHead == nullptr )
432 pHead = init_bucket( nBucket );
434 assert( pHead->is_dummy() );
441 // GC and OrderedList::gc must be the same
442 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
444 // atomicity::empty_item_counter is not allowed as a item counter
445 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
446 "cds::atomicity::empty_item_counter is not allowed as a item counter");
448 // Initialize bucket 0
449 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
451 // insert_aux_node cannot return false for empty list
452 CDS_VERIFY( m_List.insert_aux_node( pNode ));
454 m_Buckets.bucket( 0, pNode );
457 void inc_item_count()
459 size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
460 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
462 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
466 template <typename Q, typename Compare, typename Func>
467 bool find_( Q& val, Compare cmp, Func f )
469 size_t nHash = hash_value( val );
470 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
471 dummy_node_type * pHead = get_bucket( nHash );
472 assert( pHead != nullptr );
474 return m_Stat.onFind(
475 m_List.find_at( pHead, sv, cmp,
476 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
480 template <typename Q, typename Compare>
481 bool find_( Q const& val, Compare cmp )
483 size_t nHash = hash_value( val );
484 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
485 dummy_node_type * pHead = get_bucket( nHash );
486 assert( pHead != nullptr );
488 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
491 template <typename Q, typename Compare>
492 bool get_( typename gc::Guard& guard, Q const& val, Compare cmp )
494 size_t nHash = hash_value( val );
495 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
496 dummy_node_type * pHead = get_bucket( nHash );
497 assert( pHead != nullptr );
499 return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
502 template <typename Q>
503 bool get_( typename gc::Guard& guard, Q const& key)
505 return get_( guard, key, key_comparator());
508 template <typename Q, typename Less>
509 bool get_with_( typename gc::Guard& guard, Q const& key, Less )
511 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
514 template <typename Q, typename Compare, typename Func>
515 bool erase_( Q const& val, Compare cmp, Func f )
517 size_t nHash = hash_value( val );
518 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
519 dummy_node_type * pHead = get_bucket( nHash );
520 assert( pHead != nullptr );
522 if ( m_List.erase_at( pHead, sv, cmp, f )) {
524 m_Stat.onEraseSuccess();
527 m_Stat.onEraseFailed();
531 template <typename Q, typename Compare>
532 bool erase_( Q const& val, Compare cmp )
534 size_t nHash = hash_value( val );
535 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
536 dummy_node_type * pHead = get_bucket( nHash );
537 assert( pHead != nullptr );
539 if ( m_List.erase_at( pHead, sv, cmp ) ) {
541 m_Stat.onEraseSuccess();
544 m_Stat.onEraseFailed();
548 template <typename Q, typename Compare>
549 bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
551 size_t nHash = hash_value( val );
552 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
553 dummy_node_type * pHead = get_bucket( nHash );
554 assert( pHead != nullptr );
556 if ( m_List.extract_at( pHead, guard, sv, cmp ) ) {
558 m_Stat.onExtractSuccess();
561 m_Stat.onExtractFailed();
565 template <typename Q>
566 bool extract_( typename gc::Guard& guard, Q const& key)
568 return extract_( guard, key, key_comparator());
571 template <typename Q, typename Less>
572 bool extract_with_( typename gc::Guard& guard, Q const& key, Less )
574 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
580 /// Initialize split-ordered list of default capacity
582 The default capacity is defined in bucket table constructor.
583 See \p split_list::expandable_bucket_table, \p split_list::static_ducket_table
584 which selects by \p split_list::dynamic_bucket_table option.
587 : m_nBucketCountLog2(1)
592 /// Initialize split-ordered list
594 size_t nItemCount ///< estimate average of item count
595 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
597 : m_Buckets( nItemCount, nLoadFactor )
598 , m_nBucketCountLog2(1)
606 The function inserts \p val in the set if it does not contain
607 an item with key equal to \p val.
609 Returns \p true if \p val is placed into the set, \p false otherwise.
611 bool insert( value_type& val )
613 size_t nHash = hash_value( val );
614 dummy_node_type * pHead = get_bucket( nHash );
615 assert( pHead != nullptr );
617 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
619 if ( m_List.insert_at( pHead, val )) {
621 m_Stat.onInsertSuccess();
624 m_Stat.onInsertFailed();
630 This function is intended for derived non-intrusive containers.
632 The function allows to split creating of new item into two part:
633 - create item with key only
634 - insert new item into the set
635 - if inserting is success, calls \p f functor to initialize value-field of \p val.
637 The functor signature is:
639 void func( value_type& val );
641 where \p val is the item inserted.
642 The user-defined functor is called only if the inserting is success.
644 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
645 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
648 template <typename Func>
649 bool insert( value_type& val, Func f )
651 size_t nHash = hash_value( val );
652 dummy_node_type * pHead = get_bucket( nHash );
653 assert( pHead != nullptr );
655 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
657 if ( m_List.insert_at( pHead, val, f )) {
659 m_Stat.onInsertSuccess();
662 m_Stat.onInsertFailed();
666 /// Ensures that the \p val exists in the set
668 The operation performs inserting or changing data with lock-free manner.
670 If the item \p val is not found in the set, then \p val is inserted into the set.
671 Otherwise, the functor \p func is called with item found.
672 The functor signature is:
674 void func( bool bNew, value_type& item, value_type& val );
677 - \p bNew - \p true if the item has been inserted, \p false otherwise
678 - \p item - item of the set
679 - \p val - argument \p val passed into the \p ensure function
680 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
681 refers to the same thing.
683 The functor can change non-key fields of the \p item.
685 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
686 \p second is \p true if new item has been added or \p false if the item with \p key
687 already is in the set.
689 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
690 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
693 template <typename Func>
694 std::pair<bool, bool> ensure( value_type& val, Func func )
696 size_t nHash = hash_value( val );
697 dummy_node_type * pHead = get_bucket( nHash );
698 assert( pHead != nullptr );
700 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
702 std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
703 if ( bRet.first && bRet.second ) {
705 m_Stat.onEnsureNew();
708 m_Stat.onEnsureExist();
712 /// Unlinks the item \p val from the set
714 The function searches the item \p val in the set and unlinks it from the set
715 if it is found and is equal to \p val.
717 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
718 and deletes the item found. \p unlink finds an item by key and deletes it
719 only if \p val is an item of that set, i.e. the pointer to item found
720 is equal to <tt> &val </tt>.
722 The function returns \p true if success and \p false otherwise.
724 bool unlink( value_type& val )
726 size_t nHash = hash_value( val );
727 dummy_node_type * pHead = get_bucket( nHash );
728 assert( pHead != nullptr );
730 if ( m_List.unlink_at( pHead, val ) ) {
732 m_Stat.onEraseSuccess();
735 m_Stat.onEraseFailed();
739 /// Deletes the item from the set
740 /** \anchor cds_intrusive_SplitListSet_hp_erase
741 The function searches an item with key equal to \p key in the set,
742 unlinks it from the set, and returns \p true.
743 If the item with key equal to \p key is not found the function return \p false.
745 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
746 and deletes the item found. \p unlink finds an item by key and deletes it
747 only if \p key is an item of that set, i.e. the pointer to item found
748 is equal to <tt> &key </tt>.
750 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
752 template <typename Q>
753 bool erase( Q const& key )
755 return erase_( key, key_comparator() );
758 /// Deletes the item from the set with comparing functor \p pred
761 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
762 but \p pred predicate is used for key comparing.
763 \p Less has the interface like \p std::less.
764 \p pred must imply the same element order as the comparator used for building the set.
766 template <typename Q, typename Less>
767 bool erase_with( const Q& key, Less pred )
770 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
773 /// Deletes the item from the set
774 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
775 The function searches an item with key equal to \p key in the set,
776 call \p f functor with item found, unlinks it from the set, and returns \p true.
777 The \ref disposer specified by \p OrderedList class template parameter is called
778 by garbage collector \p GC asynchronously.
780 The \p Func interface is
783 void operator()( value_type const& item );
787 If the item with key equal to \p key is not found the function return \p false.
789 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
791 template <typename Q, typename Func>
792 bool erase( Q const& key, Func f )
794 return erase_( key, key_comparator(), f );
797 /// Deletes the item from the set with comparing functor \p pred
799 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
800 but \p pred predicate is used for key comparing.
801 \p Less has the interface like \p std::less.
802 \p pred must imply the same element order as the comparator used for building the set.
804 template <typename Q, typename Less, typename Func>
805 bool erase_with( Q const& key, Less pred, Func f )
808 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
811 /// Extracts the item with specified \p key
812 /** \anchor cds_intrusive_SplitListSet_hp_extract
813 The function searches an item with key equal to \p key,
814 unlinks it from the set, and returns it in \p dest parameter.
815 If the item with key equal to \p key is not found the function returns \p false.
817 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
819 The \ref disposer specified in \p OrderedList class' template parameter is called automatically
820 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
821 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
825 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
826 splitlist_set theSet;
829 splitlist_set::guarded_ptr gp;
830 theSet.extract( gp, 5 );
834 // Destructor of gp releases internal HP guard
838 template <typename Q>
839 bool extract( guarded_ptr& dest, Q const& key )
841 return extract_( dest.guard(), key );
844 /// Extracts the item using compare functor \p pred
846 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(guarded_ptr&, Q const&)"
847 but \p pred predicate is used for key comparing.
849 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
851 \p pred must imply the same element order as the comparator used for building the set.
853 template <typename Q, typename Less>
854 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
856 return extract_with_( dest.guard(), key, pred );
859 /// Finds the key \p key
860 /** \anchor cds_intrusive_SplitListSet_hp_find_func
861 The function searches the item with key equal to \p key and calls the functor \p f for item found.
862 The interface of \p Func functor is:
865 void operator()( value_type& item, Q& key );
868 where \p item is the item found, \p key is the <tt>find</tt> function argument.
870 The functor can change non-key fields of \p item. Note that the functor is only guarantee
871 that \p item cannot be disposed during functor is executing.
872 The functor does not serialize simultaneous access to the set \p item. If such access is
873 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
875 Note the hash functor specified for class \p Traits template parameter
876 should accept a parameter of type \p Q that can be not the same as \p value_type.
878 The function returns \p true if \p key is found, \p false otherwise.
880 template <typename Q, typename Func>
881 bool find( Q& key, Func f )
883 return find_( key, key_comparator(), f );
886 template <typename Q, typename Func>
887 bool find( Q const& key, Func f )
889 return find_( key, key_comparator(), f );
893 /// Finds the key \p key with \p pred predicate for comparing
895 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
896 but \p cmp is used for key compare.
897 \p Less has the interface like \p std::less.
898 \p cmp must imply the same element order as the comparator used for building the set.
900 template <typename Q, typename Less, typename Func>
901 bool find_with( Q& key, Less pred, Func f )
904 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
907 template <typename Q, typename Less, typename Func>
908 bool find_with( Q const& key, Less pred, Func f )
911 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
915 /// Finds the key \p key
916 /** \anchor cds_intrusive_SplitListSet_hp_find_val
917 The function searches the item with key equal to \p key
918 and returns \p true if it is found, and \p false otherwise.
920 Note the hash functor specified for class \p Traits template parameter
921 should accept a parameter of type \p Q that can be not the same as \p value_type.
922 Otherwise, you may use \p find_with functions with explicit predicate for key comparing.
924 template <typename Q>
925 bool find( Q const& key )
927 return find_( key, key_comparator() );
930 /// Finds the key \p key with \p pred predicate for comparing
932 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_val "find(Q const&)"
933 but \p cmp is used for key compare.
934 \p Less has the interface like \p std::less.
935 \p cmp must imply the same element order as the comparator used for building the set.
937 template <typename Q, typename Less>
938 bool find_with( Q const& key, Less pred )
941 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
944 /// Finds the key \p key and return the item found
945 /** \anchor cds_intrusive_SplitListSet_hp_get
946 The function searches the item with key equal to \p key
947 and assigns the item found to guarded pointer \p ptr.
948 The function returns \p true if \p key is found, and \p false otherwise.
949 If \p key is not found the \p ptr parameter is not changed.
951 The \ref disposer specified in \p OrderedList class' template parameter is called
952 by garbage collector \p GC automatically when returned \ref guarded_ptr object
953 will be destroyed or released.
954 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
958 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
959 splitlist_set theSet;
962 splitlist_set::guarded_ptr gp;
963 if ( theSet.get( gp, 5 )) {
967 // Destructor of guarded_ptr releases internal HP guard
971 Note the compare functor specified for \p OrderedList template parameter
972 should accept a parameter of type \p Q that can be not the same as \p value_type.
974 template <typename Q>
975 bool get( guarded_ptr& ptr, Q const& key )
977 return get_( ptr.guard(), key );
980 /// Finds the key \p key and return the item found
982 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
983 but \p pred is used for comparing the keys.
985 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
987 \p pred must imply the same element order as the comparator used for building the set.
989 template <typename Q, typename Less>
990 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
992 return get_with_( ptr.guard(), key, pred );
995 /// Returns item count in the set
998 return m_ItemCounter;
1001 /// Checks if the set is empty
1003 Emptiness is checked by item counting: if item count is zero then the set is empty.
1004 Thus, the correct item counting feature is an important part of split-list set implementation.
1011 /// Clears the set (non-atomic)
1013 The function unlink all items from the set.
1014 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1016 For each item the \p disposer is called after unlinking.
1020 iterator it = begin();
1021 while ( it != end() ) {
1029 /// Returns internal statistics
1030 stat const& statistics() const
1037 template <bool IsConst>
1039 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1041 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1042 typedef typename iterator_base_class::list_iterator list_iterator;
1045 : iterator_base_class()
1048 iterator_type( iterator_type const& src )
1049 : iterator_base_class( src )
1052 // This ctor should be protected...
1053 iterator_type( list_iterator itCur, list_iterator itEnd )
1054 : iterator_base_class( itCur, itEnd )
1059 /// Forward iterator
1061 The forward iterator for a split-list has some features:
1062 - it has no post-increment operator
1063 - it depends on iterator of underlying \p OrderedList
1064 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1065 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1066 deleting operations it is no guarantee that you iterate all item in the split-list.
1068 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1069 for debug purpose only.
1071 typedef iterator_type<false> iterator;
1072 /// Const forward iterator
1074 For iterator's features and requirements see \ref iterator
1076 typedef iterator_type<true> const_iterator;
1078 /// Returns a forward iterator addressing the first element in a split-list
1080 For empty list \code begin() == end() \endcode
1084 return iterator( m_List.begin(), m_List.end() );
1087 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1089 Do not use the value returned by <tt>end</tt> function to access any item.
1091 The returned value can be used only to control reaching the end of the split-list.
1092 For empty list \code begin() == end() \endcode
1096 return iterator( m_List.end(), m_List.end() );
1099 /// Returns a forward const iterator addressing the first element in a split-list
1100 const_iterator begin() const
1104 /// Returns a forward const iterator addressing the first element in a split-list
1105 const_iterator cbegin() const
1107 return const_iterator( m_List.cbegin(), m_List.cend() );
1110 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1111 const_iterator end() const
1115 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1116 const_iterator cend() const
1118 return const_iterator( m_List.cend(), m_List.cend() );
1123 }} // namespace cds::intrusive
1125 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_H