3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H
4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
7 #include <cds/intrusive/details/split_list_base.h>
9 namespace cds { namespace intrusive {
11 /// Split-ordered list
12 /** @ingroup cds_intrusive_map
13 \anchor cds_intrusive_SplitListSet_hp
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"
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 item moving on resizing.
23 \anchor cds_SplitList_algo_desc
24 <b>Short description</b>
25 [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
27 The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
28 the places in the list where a sublist of
\93correct
\94 items can be found. A bucket is initialized upon first
29 access by assigning it to a new
\93dummy
\94 node (dashed contour) in the list, preceding all items that should be
30 in that bucket. A newly created bucket splits an older bucket
\92s chain, reducing the access cost to its items. The
31 table uses a modulo 2**i hash (there are known techniques for
\93pre-hashing
\94 before a modulo 2**i hash
32 to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
34 Unlike moving an item, the operation of directing a bucket pointer can be done
35 in a single CAS operation, and since items are not moved, they are never
\93lost
\94.
36 However, to make this approach work, one must be able to keep the items in the
37 list sorted in such a way that any bucket
\92s sublist can be
\93split
\94 by directing a new
38 bucket pointer within it. This operation must be recursively repeatable, as every
39 split bucket may be split again and again as the hash table grows. To achieve this
40 goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
41 in a given bucket adjacent in the list throughout the repeated splitting process.
43 Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
44 simple binary reversal: reversing the bits of the hash key so that the new key
\92s
45 most significant bits (MSB) are those that were originally its least significant.
46 The split-order keys of regular nodes are exactly the bit-reverse image of the original
47 keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
48 4</tt> bucket, which can be recursively split in two by inserting a new node between
51 To insert (respectively delete or search for) an item in the hash table, hash its
52 key to the appropriate bucket using recursive split-ordering, follow the pointer to
53 the appropriate location in the sorted items list, and traverse the list until the key
\92s
54 proper location in the split-ordering (respectively until the key or a key indicating
55 the item is not in the list is found). Because of the combinatorial structure induced
56 by the split-ordering, this will require traversal of no more than an expected constant number of items.
58 The design is modular: to implement the ordered items list, you can use one of several
59 non-blocking list-based set algorithms: MichaelList, LazyList.
63 Template parameters are:
64 - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
65 - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
66 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
67 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
69 - \p Traits - split-list traits, default is \p split_list::traits.
70 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
72 There are several specialization of the split-list class for different \p GC:
73 - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
74 \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
75 - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
76 \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
78 \anchor cds_SplitList_hash_functor
81 Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
82 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
83 the hash values of these keys must be equal too.
84 The hash functor \p Traits::hash should accept parameters of both type:
88 std::string key_ ; // key field
94 size_t operator()( const std::string& s ) const
96 return std::hash( s );
99 size_t operator()( const Foo& f ) const
101 return (*this)( f.key_ );
108 First, you should choose ordered list type to use in your split-list set:
110 // For gc::HP-based MichaelList implementation
111 #include <cds/intrusive/michael_list_hp.h>
113 // cds::intrusive::SplitListSet declaration
114 #include <cds/intrusive/split_list.h>
117 // Note you should declare your struct based on cds::intrusive::split_list::node
118 // which is a wrapper for ordered-list node struct.
119 // In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
120 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
122 std::string key_ ; // key field
123 unsigned val_ ; // value field
124 // ... other value fields
127 // Declare comparator for the item
130 int operator()( const Foo& f1, const Foo& f2 ) const
132 return f1.key_.compare( f2.key_ );
136 // Declare base ordered-list type for split-list
137 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
138 typename cds::intrusive::michael_list::make_traits<
140 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
141 // item comparator option
142 ,cds::opt::compare< FooCmp >
147 Second, you should declare split-list set container:
150 // Declare hash functor
151 // Note, the hash functor accepts parameter type Foo and std::string
153 size_t operator()( const Foo& f ) const
155 return cds::opt::v::hash<std::string>()( f.key_ );
157 size_t operator()( const std::string& s ) const
159 return cds::opt::v::hash<std::string>()( s );
163 // Split-list set typedef
164 typedef cds::intrusive::SplitListSet<
167 ,typename cds::intrusive::split_list::make_traits<
168 cds::opt::hash< FooHash >
173 Now, you can use \p Foo_set in your application.
179 fooSet.insert( *foo );
187 # ifdef CDS_DOXYGEN_INVOKED
188 class Traits = split_list::traits
196 typedef GC gc; ///< Garbage collector
197 typedef Traits traits; ///< Set traits
201 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
205 # ifdef CDS_DOXYGEN_INVOKED
206 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
208 typedef typename wrapped_ordered_list::result ordered_list;
210 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
211 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
212 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
214 /// Hash functor for \p %value_type and all its derivatives that you use
215 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
217 typedef typename traits::item_counter item_counter; ///< Item counter type
218 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
219 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
220 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
221 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
224 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
225 typedef split_list::node<list_node_type> node_type; ///< split-list node type
226 typedef node_type dummy_node_type; ///< dummy node type
228 /// Split-list node traits
230 This traits is intended for converting between underlying ordered list node type \p list_node_type
231 and split-list node type \p node_type
233 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
236 /// Bucket table implementation
237 typedef typename split_list::details::bucket_table_selector<
238 traits::dynamic_bucket_table
241 , opt::allocator< typename traits::allocator >
242 , opt::memory_model< memory_model >
243 >::type bucket_table;
248 /// Ordered list wrapper to access protected members
249 class ordered_list_wrapper: public ordered_list
251 typedef ordered_list base_class;
252 typedef typename base_class::auxiliary_head bucket_head_type;
255 bool insert_at( dummy_node_type * pHead, value_type& val )
257 assert( pHead != nullptr );
258 bucket_head_type h(pHead);
259 return base_class::insert_at( h, val );
262 template <typename Func>
263 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
265 assert( pHead != nullptr );
266 bucket_head_type h(pHead);
267 return base_class::insert_at( h, val, f );
270 template <typename Func>
271 std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
273 assert( pHead != nullptr );
274 bucket_head_type h(pHead);
275 return base_class::update_at( h, val, func, bAllowInsert );
278 bool unlink_at( dummy_node_type * pHead, value_type& val )
280 assert( pHead != nullptr );
281 bucket_head_type h(pHead);
282 return base_class::unlink_at( h, val );
285 template <typename Q, typename Compare, typename Func>
286 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
288 assert( pHead != nullptr );
289 bucket_head_type h(pHead);
290 return base_class::erase_at( h, val, cmp, f );
293 template <typename Q, typename Compare>
294 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
296 assert( pHead != nullptr );
297 bucket_head_type h(pHead);
298 return base_class::erase_at( h, val, cmp );
301 template <typename Q, typename Compare>
302 bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
304 assert( pHead != nullptr );
305 bucket_head_type h(pHead);
306 return base_class::extract_at( h, guard, val, cmp );
309 template <typename Q, typename Compare, typename Func>
310 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
312 assert( pHead != nullptr );
313 bucket_head_type h(pHead);
314 return base_class::find_at( h, val, cmp, f );
317 template <typename Q, typename Compare>
318 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
320 assert( pHead != nullptr );
321 bucket_head_type h(pHead);
322 return base_class::find_at( h, val, cmp );
325 template <typename Q, typename Compare>
326 bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
328 assert( pHead != nullptr );
329 bucket_head_type h(pHead);
330 return base_class::get_at( h, guard, val, cmp );
333 bool insert_aux_node( dummy_node_type * pNode )
335 return base_class::insert_aux_node( pNode );
337 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
339 bucket_head_type h(pHead);
340 return base_class::insert_aux_node( h, pNode );
346 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
347 bucket_table m_Buckets; ///< bucket table
348 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
349 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
350 item_counter m_ItemCounter; ///< Item counter
351 hash m_HashFunctor; ///< Hash functor
352 stat m_Stat; ///< Internal statistics
356 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
358 dummy_node_type * alloc_dummy_node( size_t nHash )
360 m_Stat.onHeadNodeAllocated();
361 return dummy_node_allocator().New( nHash );
363 void free_dummy_node( dummy_node_type * p )
365 dummy_node_allocator().Delete( p );
366 m_Stat.onHeadNodeFreed();
369 /// Calculates hash value of \p key
370 template <typename Q>
371 size_t hash_value( Q const& key ) const
373 return m_HashFunctor( key );
376 size_t bucket_no( size_t nHash ) const
378 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
381 static size_t parent_bucket( size_t nBucket )
383 assert( nBucket > 0 );
384 return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
387 dummy_node_type * init_bucket( size_t nBucket )
389 assert( nBucket > 0 );
390 size_t nParent = parent_bucket( nBucket );
392 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
393 if ( pParentBucket == nullptr ) {
394 pParentBucket = init_bucket( nParent );
395 m_Stat.onRecursiveInitBucket();
398 assert( pParentBucket != nullptr );
400 // Allocate a dummy node for new bucket
402 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ));
403 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
404 m_Buckets.bucket( nBucket, pBucket );
405 m_Stat.onNewBucket();
408 free_dummy_node( pBucket );
411 // Another thread set the bucket. Wait while it done
413 // In this point, we must wait while nBucket is empty.
414 // The compiler can decide that waiting loop can be "optimized" (stripped)
415 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
416 m_Stat.onBucketInitContenton();
419 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
421 return const_cast<dummy_node_type *>( p );
423 m_Stat.onBusyWaitBucketInit();
427 dummy_node_type * get_bucket( size_t nHash )
429 size_t nBucket = bucket_no( nHash );
431 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
432 if ( pHead == nullptr )
433 pHead = init_bucket( nBucket );
435 assert( pHead->is_dummy());
442 // GC and OrderedList::gc must be the same
443 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
445 // atomicity::empty_item_counter is not allowed as a item counter
446 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
447 "cds::atomicity::empty_item_counter is not allowed as a item counter");
449 // Initialize bucket 0
450 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
452 // insert_aux_node cannot return false for empty list
453 CDS_VERIFY( m_List.insert_aux_node( pNode ));
455 m_Buckets.bucket( 0, pNode );
458 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
460 return nBucketCount * nLoadFactor;
463 void inc_item_count()
465 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
466 if ( ++m_ItemCounter <= nMaxCount )
469 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
470 const size_t nBucketCount = static_cast<size_t>(1) << sz;
471 if ( nBucketCount < m_Buckets.capacity()) {
472 // we may grow the bucket table
473 const size_t nLoadFactor = m_Buckets.load_factor();
474 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
475 return; // someone already have updated m_nBucketCountLog2, so stop here
477 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
478 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
479 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
482 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
485 template <typename Q, typename Compare, typename Func>
486 bool find_( Q& val, Compare cmp, Func f )
488 size_t nHash = hash_value( val );
489 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
490 dummy_node_type * pHead = get_bucket( nHash );
491 assert( pHead != nullptr );
493 return m_Stat.onFind(
494 m_List.find_at( pHead, sv, cmp,
495 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
499 template <typename Q, typename Compare>
500 bool find_( Q const& val, Compare cmp )
502 size_t nHash = hash_value( val );
503 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
504 dummy_node_type * pHead = get_bucket( nHash );
505 assert( pHead != nullptr );
507 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
510 template <typename Q, typename Compare>
511 bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
513 size_t nHash = hash_value( val );
514 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
515 dummy_node_type * pHead = get_bucket( nHash );
516 assert( pHead != nullptr );
518 return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
521 template <typename Q>
522 bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
524 return get_( guard, key, key_comparator());
527 template <typename Q, typename Less>
528 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
530 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
533 template <typename Q, typename Compare, typename Func>
534 bool erase_( Q const& val, Compare cmp, Func f )
536 size_t nHash = hash_value( val );
537 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
538 dummy_node_type * pHead = get_bucket( nHash );
539 assert( pHead != nullptr );
541 if ( m_List.erase_at( pHead, sv, cmp, f )) {
543 m_Stat.onEraseSuccess();
546 m_Stat.onEraseFailed();
550 template <typename Q, typename Compare>
551 bool erase_( Q const& val, Compare cmp )
553 size_t nHash = hash_value( val );
554 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
555 dummy_node_type * pHead = get_bucket( nHash );
556 assert( pHead != nullptr );
558 if ( m_List.erase_at( pHead, sv, cmp )) {
560 m_Stat.onEraseSuccess();
563 m_Stat.onEraseFailed();
567 template <typename Q, typename Compare>
568 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
570 size_t nHash = hash_value( val );
571 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
572 dummy_node_type * pHead = get_bucket( nHash );
573 assert( pHead != nullptr );
575 if ( m_List.extract_at( pHead, guard, sv, cmp )) {
577 m_Stat.onExtractSuccess();
580 m_Stat.onExtractFailed();
584 template <typename Q>
585 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
587 return extract_( guard, key, key_comparator());
590 template <typename Q, typename Less>
591 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
593 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
598 /// Initialize split-ordered list of default capacity
600 The default capacity is defined in bucket table constructor.
601 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
602 which selects by \p split_list::dynamic_bucket_table option.
605 : m_nBucketCountLog2(1)
606 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
611 /// Initialize split-ordered list
613 size_t nItemCount ///< estimate average of item count
614 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
616 : m_Buckets( nItemCount, nLoadFactor )
617 , m_nBucketCountLog2(1)
618 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
626 The function inserts \p val in the set if it does not contain
627 an item with key equal to \p val.
629 Returns \p true if \p val is placed into the set, \p false otherwise.
631 bool insert( value_type& val )
633 size_t nHash = hash_value( val );
634 dummy_node_type * pHead = get_bucket( nHash );
635 assert( pHead != nullptr );
637 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
639 if ( m_List.insert_at( pHead, val )) {
641 m_Stat.onInsertSuccess();
644 m_Stat.onInsertFailed();
650 This function is intended for derived non-intrusive containers.
652 The function allows to split creating of new item into two part:
653 - create item with key only
654 - insert new item into the set
655 - if inserting is success, calls \p f functor to initialize value-field of \p val.
657 The functor signature is:
659 void func( value_type& val );
661 where \p val is the item inserted.
662 The user-defined functor is called only if the inserting is success.
664 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
665 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
668 template <typename Func>
669 bool insert( value_type& val, Func f )
671 size_t nHash = hash_value( val );
672 dummy_node_type * pHead = get_bucket( nHash );
673 assert( pHead != nullptr );
675 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
677 if ( m_List.insert_at( pHead, val, f )) {
679 m_Stat.onInsertSuccess();
682 m_Stat.onInsertFailed();
688 The operation performs inserting or changing data with lock-free manner.
690 If the item \p val is not found in the set, then \p val is inserted
691 iff \p bAllowInsert is \p true.
692 Otherwise, the functor \p func is called with item found.
693 The functor signature is:
695 void func( bool bNew, value_type& item, value_type& val );
698 - \p bNew - \p true if the item has been inserted, \p false otherwise
699 - \p item - item of the set
700 - \p val - argument \p val passed into the \p update() function
701 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
702 refers to the same thing.
704 The functor may change non-key fields of the \p item.
706 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
707 \p second is \p true if new item has been added or \p false if the item with \p val
708 already is in the list.
710 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
711 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
714 template <typename Func>
715 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
717 size_t nHash = hash_value( val );
718 dummy_node_type * pHead = get_bucket( nHash );
719 assert( pHead != nullptr );
721 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
723 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
724 if ( bRet.first && bRet.second ) {
726 m_Stat.onEnsureNew();
729 m_Stat.onEnsureExist();
733 template <typename Func>
734 CDS_DEPRECATED("ensure() is deprecated, use update()")
735 std::pair<bool, bool> ensure( value_type& val, Func func )
737 return update( val, func, true );
741 /// Unlinks the item \p val from the set
743 The function searches the item \p val in the set and unlinks it from the set
744 if it is found and is equal to \p val.
746 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
747 and deletes the item found. \p unlink finds an item by key and deletes it
748 only if \p val is an item of that set, i.e. the pointer to item found
749 is equal to <tt> &val </tt>.
751 The function returns \p true if success and \p false otherwise.
753 bool unlink( value_type& val )
755 size_t nHash = hash_value( val );
756 dummy_node_type * pHead = get_bucket( nHash );
757 assert( pHead != nullptr );
759 if ( m_List.unlink_at( pHead, val )) {
761 m_Stat.onEraseSuccess();
764 m_Stat.onEraseFailed();
768 /// Deletes the item from the set
769 /** \anchor cds_intrusive_SplitListSet_hp_erase
770 The function searches an item with key equal to \p key in the set,
771 unlinks it from the set, and returns \p true.
772 If the item with key equal to \p key is not found the function return \p false.
774 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
775 and deletes the item found. \p unlink finds an item by key and deletes it
776 only if \p key is an item of that set, i.e. the pointer to item found
777 is equal to <tt> &key </tt>.
779 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
781 template <typename Q>
782 bool erase( Q const& key )
784 return erase_( key, key_comparator());
787 /// Deletes the item from the set with comparing functor \p pred
790 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
791 but \p pred predicate is used for key comparing.
792 \p Less has the interface like \p std::less.
793 \p pred must imply the same element order as the comparator used for building the set.
795 template <typename Q, typename Less>
796 bool erase_with( const Q& key, Less pred )
799 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
802 /// Deletes the item from the set
803 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
804 The function searches an item with key equal to \p key in the set,
805 call \p f functor with item found, unlinks it from the set, and returns \p true.
806 The \ref disposer specified by \p OrderedList class template parameter is called
807 by garbage collector \p GC asynchronously.
809 The \p Func interface is
812 void operator()( value_type const& item );
816 If the item with key equal to \p key is not found the function return \p false.
818 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
820 template <typename Q, typename Func>
821 bool erase( Q const& key, Func f )
823 return erase_( key, key_comparator(), f );
826 /// Deletes the item from the set with comparing functor \p pred
828 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
829 but \p pred predicate is used for key comparing.
830 \p Less has the interface like \p std::less.
831 \p pred must imply the same element order as the comparator used for building the set.
833 template <typename Q, typename Less, typename Func>
834 bool erase_with( Q const& key, Less pred, Func f )
837 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
840 /// Extracts the item with specified \p key
841 /** \anchor cds_intrusive_SplitListSet_hp_extract
842 The function searches an item with key equal to \p key,
843 unlinks it from the set, and returns it as \p guarded_ptr.
844 If \p key is not found the function returns an empty guarded pointer.
846 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
848 The \p disposer specified in \p OrderedList class' template parameter is called automatically
849 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
850 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
854 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
855 splitlist_set theSet;
858 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
863 // Destructor of gp releases internal HP guard
867 template <typename Q>
868 guarded_ptr extract( Q const& key )
871 extract_( gp.guard(), key );
875 /// Extracts the item using compare functor \p pred
877 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
878 but \p pred predicate is used for key comparing.
880 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
882 \p pred must imply the same element order as the comparator used for building the set.
884 template <typename Q, typename Less>
885 guarded_ptr extract_with( Q const& key, Less pred )
888 extract_with_( gp.guard(), key, pred );
892 /// Finds the key \p key
893 /** \anchor cds_intrusive_SplitListSet_hp_find_func
894 The function searches the item with key equal to \p key and calls the functor \p f for item found.
895 The interface of \p Func functor is:
898 void operator()( value_type& item, Q& key );
901 where \p item is the item found, \p key is the <tt>find</tt> function argument.
903 The functor can change non-key fields of \p item. Note that the functor is only guarantee
904 that \p item cannot be disposed during functor is executing.
905 The functor does not serialize simultaneous access to the set \p item. If such access is
906 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
908 Note the hash functor specified for class \p Traits template parameter
909 should accept a parameter of type \p Q that can be not the same as \p value_type.
911 The function returns \p true if \p key is found, \p false otherwise.
913 template <typename Q, typename Func>
914 bool find( Q& key, Func f )
916 return find_( key, key_comparator(), f );
919 template <typename Q, typename Func>
920 bool find( Q const& key, Func f )
922 return find_( key, key_comparator(), f );
926 /// Finds the key \p key with \p pred predicate for comparing
928 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
929 but \p cmp is used for key compare.
930 \p Less has the interface like \p std::less.
931 \p cmp must imply the same element order as the comparator used for building the set.
933 template <typename Q, typename Less, typename Func>
934 bool find_with( Q& key, Less pred, Func f )
937 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
940 template <typename Q, typename Less, typename Func>
941 bool find_with( Q const& key, Less pred, Func f )
944 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
948 /// Checks whether the set contains \p key
950 The function searches the item with key equal to \p key
951 and returns \p true if it is found, and \p false otherwise.
953 Note the hash functor specified for class \p Traits template parameter
954 should accept a parameter of type \p Q that can be not the same as \p value_type.
955 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
957 template <typename Q>
958 bool contains( Q const& key )
960 return find_( key, key_comparator());
963 template <typename Q>
964 CDS_DEPRECATED("deprecated, use contains()")
965 bool find( Q const& key )
967 return contains( key );
971 /// Checks whether the set contains \p key using \p pred predicate for searching
973 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
974 \p Less functor has the interface like \p std::less.
975 \p Less must imply the same element order as the comparator used for building the set.
977 template <typename Q, typename Less>
978 bool contains( Q const& key, Less pred )
981 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
984 template <typename Q, typename Less>
985 CDS_DEPRECATED("deprecated, use contains()")
986 bool find_with( Q const& key, Less pred )
988 return contains( key, pred );
992 /// Finds the key \p key and return the item found
993 /** \anchor cds_intrusive_SplitListSet_hp_get
994 The function searches the item with key equal to \p key
995 and returns the item found as \p guarded_ptr.
996 If \p key is not found the function returns an empty guarded pointer.
998 The \p disposer specified in \p OrderedList class' template parameter is called
999 by garbage collector \p GC automatically when returned \p guarded_ptr object
1000 will be destroyed or released.
1001 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1005 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
1006 splitlist_set theSet;
1009 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1014 // Destructor of guarded_ptr releases internal HP guard
1018 Note the compare functor specified for \p OrderedList template parameter
1019 should accept a parameter of type \p Q that can be not the same as \p value_type.
1021 template <typename Q>
1022 guarded_ptr get( Q const& key )
1025 get_( gp.guard(), key );
1029 /// Finds the key \p key and return the item found
1031 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1032 but \p pred is used for comparing the keys.
1034 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1036 \p pred must imply the same element order as the comparator used for building the set.
1038 template <typename Q, typename Less>
1039 guarded_ptr get_with( Q const& key, Less pred )
1042 get_with_( gp.guard(), key, pred );
1046 /// Returns item count in the set
1049 return m_ItemCounter;
1052 /// Checks if the set is empty
1054 Emptiness is checked by item counting: if item count is zero then the set is empty.
1055 Thus, the correct item counting feature is an important part of split-list set implementation.
1062 /// Clears the set (non-atomic)
1064 The function unlink all items from the set.
1065 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1067 For each item the \p disposer is called after unlinking.
1071 iterator it = begin();
1072 while ( it != end()) {
1080 /// Returns internal statistics
1081 stat const& statistics() const
1088 template <bool IsConst>
1090 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1092 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1093 typedef typename iterator_base_class::list_iterator list_iterator;
1096 : iterator_base_class()
1099 iterator_type( iterator_type const& src )
1100 : iterator_base_class( src )
1103 // This ctor should be protected...
1104 iterator_type( list_iterator itCur, list_iterator itEnd )
1105 : iterator_base_class( itCur, itEnd )
1110 /// Forward iterator
1112 The forward iterator for a split-list has some features:
1113 - it has no post-increment operator
1114 - it depends on iterator of underlying \p OrderedList
1115 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1116 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1117 deleting operations it is no guarantee that you iterate all item in the split-list.
1119 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1120 for debug purpose only.
1122 typedef iterator_type<false> iterator;
1123 /// Const forward iterator
1125 For iterator's features and requirements see \ref iterator
1127 typedef iterator_type<true> const_iterator;
1129 /// Returns a forward iterator addressing the first element in a split-list
1131 For empty list \code begin() == end() \endcode
1135 return iterator( m_List.begin(), m_List.end());
1138 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1140 Do not use the value returned by <tt>end</tt> function to access any item.
1142 The returned value can be used only to control reaching the end of the split-list.
1143 For empty list \code begin() == end() \endcode
1147 return iterator( m_List.end(), m_List.end());
1150 /// Returns a forward const iterator addressing the first element in a split-list
1151 const_iterator begin() const
1155 /// Returns a forward const iterator addressing the first element in a split-list
1156 const_iterator cbegin() const
1158 return const_iterator( m_List.cbegin(), m_List.cend());
1161 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1162 const_iterator end() const
1166 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1167 const_iterator cend() const
1169 return const_iterator( m_List.cend(), m_List.cend());
1174 }} // namespace cds::intrusive
1176 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H