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
200 typedef cds::intrusive::split_list::implementation_tag implementation_tag;
205 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
209 # ifdef CDS_DOXYGEN_INVOKED
210 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
212 typedef typename wrapped_ordered_list::result ordered_list;
214 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
215 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
216 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
218 /// Hash functor for \p %value_type and all its derivatives that you use
219 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
221 typedef typename traits::item_counter item_counter; ///< Item counter type
222 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
223 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
224 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
225 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
228 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
229 typedef split_list::node<list_node_type> node_type; ///< split-list node type
230 typedef node_type dummy_node_type; ///< dummy node type
232 /// Split-list node traits
234 This traits is intended for converting between underlying ordered list node type \p list_node_type
235 and split-list node type \p node_type
237 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
240 /// Bucket table implementation
241 typedef typename split_list::details::bucket_table_selector<
242 traits::dynamic_bucket_table
245 , opt::allocator< typename traits::allocator >
246 , opt::memory_model< memory_model >
247 >::type bucket_table;
252 /// Ordered list wrapper to access protected members
253 class ordered_list_wrapper: public ordered_list
255 typedef ordered_list base_class;
256 typedef typename base_class::auxiliary_head bucket_head_type;
259 bool insert_at( dummy_node_type * pHead, value_type& val )
261 assert( pHead != nullptr );
262 bucket_head_type h(pHead);
263 return base_class::insert_at( h, val );
266 template <typename Func>
267 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
269 assert( pHead != nullptr );
270 bucket_head_type h(pHead);
271 return base_class::insert_at( h, val, f );
274 template <typename Func>
275 std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
277 assert( pHead != nullptr );
278 bucket_head_type h(pHead);
279 return base_class::update_at( h, val, func, bAllowInsert );
282 bool unlink_at( dummy_node_type * pHead, value_type& val )
284 assert( pHead != nullptr );
285 bucket_head_type h(pHead);
286 return base_class::unlink_at( h, val );
289 template <typename Q, typename Compare, typename Func>
290 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
292 assert( pHead != nullptr );
293 bucket_head_type h(pHead);
294 return base_class::erase_at( h, val, cmp, f );
297 template <typename Q, typename Compare>
298 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
300 assert( pHead != nullptr );
301 bucket_head_type h(pHead);
302 return base_class::erase_at( h, val, cmp );
305 template <typename Q, typename Compare>
306 bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
308 assert( pHead != nullptr );
309 bucket_head_type h(pHead);
310 return base_class::extract_at( h, guard, val, cmp );
313 template <typename Q, typename Compare, typename Func>
314 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
316 assert( pHead != nullptr );
317 bucket_head_type h(pHead);
318 return base_class::find_at( h, val, cmp, f );
321 template <typename Q, typename Compare>
322 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
324 assert( pHead != nullptr );
325 bucket_head_type h(pHead);
326 return base_class::find_at( h, val, cmp );
329 template <typename Q, typename Compare>
330 bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
332 assert( pHead != nullptr );
333 bucket_head_type h(pHead);
334 return base_class::get_at( h, guard, val, cmp );
337 bool insert_aux_node( dummy_node_type * pNode )
339 return base_class::insert_aux_node( pNode );
341 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
343 bucket_head_type h(pHead);
344 return base_class::insert_aux_node( h, pNode );
350 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
351 bucket_table m_Buckets; ///< bucket table
352 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
353 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
354 item_counter m_ItemCounter; ///< Item counter
355 hash m_HashFunctor; ///< Hash functor
356 stat m_Stat; ///< Internal statistics
360 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
362 dummy_node_type * alloc_dummy_node( size_t nHash )
364 m_Stat.onHeadNodeAllocated();
365 return dummy_node_allocator().New( nHash );
367 void free_dummy_node( dummy_node_type * p )
369 dummy_node_allocator().Delete( p );
370 m_Stat.onHeadNodeFreed();
373 /// Calculates hash value of \p key
374 template <typename Q>
375 size_t hash_value( Q const& key ) const
377 return m_HashFunctor( key );
380 size_t bucket_no( size_t nHash ) const
382 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
385 static size_t parent_bucket( size_t nBucket )
387 assert( nBucket > 0 );
388 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
391 dummy_node_type * init_bucket( size_t nBucket )
393 assert( nBucket > 0 );
394 size_t nParent = parent_bucket( nBucket );
396 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
397 if ( pParentBucket == nullptr ) {
398 pParentBucket = init_bucket( nParent );
399 m_Stat.onRecursiveInitBucket();
402 assert( pParentBucket != nullptr );
404 // Allocate a dummy node for new bucket
406 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
407 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
408 m_Buckets.bucket( nBucket, pBucket );
409 m_Stat.onNewBucket();
412 free_dummy_node( pBucket );
415 // Another thread set the bucket. Wait while it done
417 // In this point, we must wait while nBucket is empty.
418 // The compiler can decide that waiting loop can be "optimized" (stripped)
419 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
420 m_Stat.onBucketInitContenton();
423 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
425 return const_cast<dummy_node_type *>( p );
427 m_Stat.onBusyWaitBucketInit();
431 dummy_node_type * get_bucket( size_t nHash )
433 size_t nBucket = bucket_no( nHash );
435 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
436 if ( pHead == nullptr )
437 pHead = init_bucket( nBucket );
439 assert( pHead->is_dummy() );
446 // GC and OrderedList::gc must be the same
447 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
449 // atomicity::empty_item_counter is not allowed as a item counter
450 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
451 "cds::atomicity::empty_item_counter is not allowed as a item counter");
453 // Initialize bucket 0
454 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
456 // insert_aux_node cannot return false for empty list
457 CDS_VERIFY( m_List.insert_aux_node( pNode ));
459 m_Buckets.bucket( 0, pNode );
462 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
464 return nBucketCount * nLoadFactor;
467 void inc_item_count()
469 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
470 if ( ++m_ItemCounter <= nMaxCount )
473 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
474 const size_t nBucketCount = static_cast<size_t>(1) << sz;
475 if ( nBucketCount < m_Buckets.capacity() ) {
476 // we may grow the bucket table
477 const size_t nLoadFactor = m_Buckets.load_factor();
478 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
479 return; // someone already have updated m_nBucketCountLog2, so stop here
481 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
482 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
483 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
486 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
489 template <typename Q, typename Compare, typename Func>
490 bool find_( Q& val, Compare cmp, Func f )
492 size_t nHash = hash_value( val );
493 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
494 dummy_node_type * pHead = get_bucket( nHash );
495 assert( pHead != nullptr );
497 return m_Stat.onFind(
498 m_List.find_at( pHead, sv, cmp,
499 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
503 template <typename Q, typename Compare>
504 bool find_( Q const& val, Compare cmp )
506 size_t nHash = hash_value( val );
507 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
508 dummy_node_type * pHead = get_bucket( nHash );
509 assert( pHead != nullptr );
511 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
514 template <typename Q, typename Compare>
515 bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
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 return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
525 template <typename Q>
526 bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
528 return get_( guard, key, key_comparator());
531 template <typename Q, typename Less>
532 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
534 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
537 template <typename Q, typename Compare, typename Func>
538 bool erase_( Q const& val, Compare cmp, Func f )
540 size_t nHash = hash_value( val );
541 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
542 dummy_node_type * pHead = get_bucket( nHash );
543 assert( pHead != nullptr );
545 if ( m_List.erase_at( pHead, sv, cmp, f )) {
547 m_Stat.onEraseSuccess();
550 m_Stat.onEraseFailed();
554 template <typename Q, typename Compare>
555 bool erase_( Q const& val, Compare cmp )
557 size_t nHash = hash_value( val );
558 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
559 dummy_node_type * pHead = get_bucket( nHash );
560 assert( pHead != nullptr );
562 if ( m_List.erase_at( pHead, sv, cmp ) ) {
564 m_Stat.onEraseSuccess();
567 m_Stat.onEraseFailed();
571 template <typename Q, typename Compare>
572 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
574 size_t nHash = hash_value( val );
575 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
576 dummy_node_type * pHead = get_bucket( nHash );
577 assert( pHead != nullptr );
579 if ( m_List.extract_at( pHead, guard, sv, cmp ) ) {
581 m_Stat.onExtractSuccess();
584 m_Stat.onExtractFailed();
588 template <typename Q>
589 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
591 return extract_( guard, key, key_comparator());
594 template <typename Q, typename Less>
595 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
597 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
602 /// Initialize split-ordered list of default capacity
604 The default capacity is defined in bucket table constructor.
605 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
606 which selects by \p split_list::dynamic_bucket_table option.
609 : m_nBucketCountLog2(1)
610 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
615 /// Initialize split-ordered list
617 size_t nItemCount ///< estimate average of item count
618 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
620 : m_Buckets( nItemCount, nLoadFactor )
621 , m_nBucketCountLog2(1)
622 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
630 The function inserts \p val in the set if it does not contain
631 an item with key equal to \p val.
633 Returns \p true if \p val is placed into the set, \p false otherwise.
635 bool insert( value_type& val )
637 size_t nHash = hash_value( val );
638 dummy_node_type * pHead = get_bucket( nHash );
639 assert( pHead != nullptr );
641 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
643 if ( m_List.insert_at( pHead, val )) {
645 m_Stat.onInsertSuccess();
648 m_Stat.onInsertFailed();
654 This function is intended for derived non-intrusive containers.
656 The function allows to split creating of new item into two part:
657 - create item with key only
658 - insert new item into the set
659 - if inserting is success, calls \p f functor to initialize value-field of \p val.
661 The functor signature is:
663 void func( value_type& val );
665 where \p val is the item inserted.
666 The user-defined functor is called only if the inserting is success.
668 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
669 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
672 template <typename Func>
673 bool insert( value_type& val, Func f )
675 size_t nHash = hash_value( val );
676 dummy_node_type * pHead = get_bucket( nHash );
677 assert( pHead != nullptr );
679 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
681 if ( m_List.insert_at( pHead, val, f )) {
683 m_Stat.onInsertSuccess();
686 m_Stat.onInsertFailed();
692 The operation performs inserting or changing data with lock-free manner.
694 If the item \p val is not found in the set, then \p val is inserted
695 iff \p bAllowInsert is \p true.
696 Otherwise, the functor \p func is called with item found.
697 The functor signature is:
699 void func( bool bNew, value_type& item, value_type& val );
702 - \p bNew - \p true if the item has been inserted, \p false otherwise
703 - \p item - item of the set
704 - \p val - argument \p val passed into the \p update() function
705 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
706 refers to the same thing.
708 The functor may change non-key fields of the \p item.
710 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
711 \p second is \p true if new item has been added or \p false if the item with \p key
712 already is in the list.
714 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
715 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
718 template <typename Func>
719 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
721 size_t nHash = hash_value( val );
722 dummy_node_type * pHead = get_bucket( nHash );
723 assert( pHead != nullptr );
725 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
727 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
728 if ( bRet.first && bRet.second ) {
730 m_Stat.onEnsureNew();
733 m_Stat.onEnsureExist();
737 // Deprecated, use update()
738 template <typename Func>
739 std::pair<bool, bool> ensure( value_type& val, Func func )
741 return update( val, func, true );
745 /// Unlinks the item \p val from the set
747 The function searches the item \p val in the set and unlinks it from the set
748 if it is found and is equal to \p val.
750 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
751 and deletes the item found. \p unlink finds an item by key and deletes it
752 only if \p val is an item of that set, i.e. the pointer to item found
753 is equal to <tt> &val </tt>.
755 The function returns \p true if success and \p false otherwise.
757 bool unlink( value_type& val )
759 size_t nHash = hash_value( val );
760 dummy_node_type * pHead = get_bucket( nHash );
761 assert( pHead != nullptr );
763 if ( m_List.unlink_at( pHead, val ) ) {
765 m_Stat.onEraseSuccess();
768 m_Stat.onEraseFailed();
772 /// Deletes the item from the set
773 /** \anchor cds_intrusive_SplitListSet_hp_erase
774 The function searches an item with key equal to \p key in the set,
775 unlinks it from the set, and returns \p true.
776 If the item with key equal to \p key is not found the function return \p false.
778 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
779 and deletes the item found. \p unlink finds an item by key and deletes it
780 only if \p key is an item of that set, i.e. the pointer to item found
781 is equal to <tt> &key </tt>.
783 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
785 template <typename Q>
786 bool erase( Q const& key )
788 return erase_( key, key_comparator() );
791 /// Deletes the item from the set with comparing functor \p pred
794 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
795 but \p pred predicate is used for key comparing.
796 \p Less has the interface like \p std::less.
797 \p pred must imply the same element order as the comparator used for building the set.
799 template <typename Q, typename Less>
800 bool erase_with( const Q& key, Less pred )
803 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
806 /// Deletes the item from the set
807 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
808 The function searches an item with key equal to \p key in the set,
809 call \p f functor with item found, unlinks it from the set, and returns \p true.
810 The \ref disposer specified by \p OrderedList class template parameter is called
811 by garbage collector \p GC asynchronously.
813 The \p Func interface is
816 void operator()( value_type const& item );
820 If the item with key equal to \p key is not found the function return \p false.
822 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
824 template <typename Q, typename Func>
825 bool erase( Q const& key, Func f )
827 return erase_( key, key_comparator(), f );
830 /// Deletes the item from the set with comparing functor \p pred
832 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
833 but \p pred predicate is used for key comparing.
834 \p Less has the interface like \p std::less.
835 \p pred must imply the same element order as the comparator used for building the set.
837 template <typename Q, typename Less, typename Func>
838 bool erase_with( Q const& key, Less pred, Func f )
841 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
844 /// Extracts the item with specified \p key
845 /** \anchor cds_intrusive_SplitListSet_hp_extract
846 The function searches an item with key equal to \p key,
847 unlinks it from the set, and returns it as \p guarded_ptr.
848 If \p key is not found the function returns an empty guarded pointer.
850 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
852 The \p disposer specified in \p OrderedList class' template parameter is called automatically
853 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
854 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
858 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
859 splitlist_set theSet;
862 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
867 // Destructor of gp releases internal HP guard
871 template <typename Q>
872 guarded_ptr extract( Q const& key )
875 extract_( gp.guard(), key );
879 /// Extracts the item using compare functor \p pred
881 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
882 but \p pred predicate is used for key comparing.
884 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
886 \p pred must imply the same element order as the comparator used for building the set.
888 template <typename Q, typename Less>
889 guarded_ptr extract_with( Q const& key, Less pred )
892 extract_with_( gp.guard(), key, pred );
896 /// Finds the key \p key
897 /** \anchor cds_intrusive_SplitListSet_hp_find_func
898 The function searches the item with key equal to \p key and calls the functor \p f for item found.
899 The interface of \p Func functor is:
902 void operator()( value_type& item, Q& key );
905 where \p item is the item found, \p key is the <tt>find</tt> function argument.
907 The functor can change non-key fields of \p item. Note that the functor is only guarantee
908 that \p item cannot be disposed during functor is executing.
909 The functor does not serialize simultaneous access to the set \p item. If such access is
910 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
912 Note the hash functor specified for class \p Traits template parameter
913 should accept a parameter of type \p Q that can be not the same as \p value_type.
915 The function returns \p true if \p key is found, \p false otherwise.
917 template <typename Q, typename Func>
918 bool find( Q& key, Func f )
920 return find_( key, key_comparator(), f );
923 template <typename Q, typename Func>
924 bool find( Q const& key, Func f )
926 return find_( key, key_comparator(), f );
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_func "find(Q&, Func)"
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, typename Func>
938 bool find_with( Q& key, Less pred, Func f )
941 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
944 template <typename Q, typename Less, typename Func>
945 bool find_with( Q const& key, Less pred, Func f )
948 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
952 /// Checks whether the set contains \p key
954 The function searches the item with key equal to \p key
955 and returns \p true if it is found, and \p false otherwise.
957 Note the hash functor specified for class \p Traits template parameter
958 should accept a parameter of type \p Q that can be not the same as \p value_type.
959 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
961 template <typename Q>
962 bool contains( Q const& key )
964 return find_( key, key_comparator() );
967 // Deprecated, use contains()
968 template <typename Q>
969 bool find( Q const& key )
971 return contains( key );
975 /// Checks whether the set contains \p key using \p pred predicate for searching
977 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
978 \p Less functor has the interface like \p std::less.
979 \p Less must imply the same element order as the comparator used for building the set.
981 template <typename Q, typename Less>
982 bool contains( Q const& key, Less pred )
985 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
988 // Deprecated, use contains()
989 template <typename Q, typename Less>
990 bool find_with( Q const& key, Less pred )
992 return contains( key, pred );
996 /// Finds the key \p key and return the item found
997 /** \anchor cds_intrusive_SplitListSet_hp_get
998 The function searches the item with key equal to \p key
999 and returns the item found as \p guarded_ptr.
1000 If \p key is not found the function returns an empty guarded pointer.
1002 The \p disposer specified in \p OrderedList class' template parameter is called
1003 by garbage collector \p GC automatically when returned \p guarded_ptr object
1004 will be destroyed or released.
1005 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1009 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
1010 splitlist_set theSet;
1013 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1018 // Destructor of guarded_ptr releases internal HP guard
1022 Note the compare functor specified for \p OrderedList template parameter
1023 should accept a parameter of type \p Q that can be not the same as \p value_type.
1025 template <typename Q>
1026 guarded_ptr get( Q const& key )
1029 get_( gp.guard(), key );
1033 /// Finds the key \p key and return the item found
1035 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1036 but \p pred is used for comparing the keys.
1038 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1040 \p pred must imply the same element order as the comparator used for building the set.
1042 template <typename Q, typename Less>
1043 guarded_ptr get_with( Q const& key, Less pred )
1046 get_with_( gp.guard(), key, pred );
1050 /// Returns item count in the set
1053 return m_ItemCounter;
1056 /// Checks if the set is empty
1058 Emptiness is checked by item counting: if item count is zero then the set is empty.
1059 Thus, the correct item counting feature is an important part of split-list set implementation.
1066 /// Clears the set (non-atomic)
1068 The function unlink all items from the set.
1069 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1071 For each item the \p disposer is called after unlinking.
1075 iterator it = begin();
1076 while ( it != end() ) {
1084 /// Returns internal statistics
1085 stat const& statistics() const
1092 template <bool IsConst>
1094 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1096 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1097 typedef typename iterator_base_class::list_iterator list_iterator;
1100 : iterator_base_class()
1103 iterator_type( iterator_type const& src )
1104 : iterator_base_class( src )
1107 // This ctor should be protected...
1108 iterator_type( list_iterator itCur, list_iterator itEnd )
1109 : iterator_base_class( itCur, itEnd )
1114 /// Forward iterator
1116 The forward iterator for a split-list has some features:
1117 - it has no post-increment operator
1118 - it depends on iterator of underlying \p OrderedList
1119 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1120 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1121 deleting operations it is no guarantee that you iterate all item in the split-list.
1123 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1124 for debug purpose only.
1126 typedef iterator_type<false> iterator;
1127 /// Const forward iterator
1129 For iterator's features and requirements see \ref iterator
1131 typedef iterator_type<true> const_iterator;
1133 /// Returns a forward iterator addressing the first element in a split-list
1135 For empty list \code begin() == end() \endcode
1139 return iterator( m_List.begin(), m_List.end() );
1142 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1144 Do not use the value returned by <tt>end</tt> function to access any item.
1146 The returned value can be used only to control reaching the end of the split-list.
1147 For empty list \code begin() == end() \endcode
1151 return iterator( m_List.end(), m_List.end() );
1154 /// Returns a forward const iterator addressing the first element in a split-list
1155 const_iterator begin() const
1159 /// Returns a forward const iterator addressing the first element in a split-list
1160 const_iterator cbegin() const
1162 return const_iterator( m_List.cbegin(), m_List.cend() );
1165 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1166 const_iterator end() const
1170 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1171 const_iterator cend() const
1173 return const_iterator( m_List.cend(), m_List.cend() );
1178 }} // namespace cds::intrusive
1180 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H