3 #ifndef __CDS_INTRUSIVE_SPLIT_LIST_H
4 #define __CDS_INTRUSIVE_SPLIT_LIST_H
6 #include <cds/intrusive/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 moving an item 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 used. Note the \p GC must be the same as the GC used for \p OrderedList
64 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, 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 - type traits. See split_list::type_traits for explanation.
69 Instead of defining \p Traits struct you may use option-based syntax with 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 <tt>Traits::hash</tt> 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 // It may be any ordered list type like MichaelList, LazyList
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 );
188 # ifdef CDS_DOXYGEN_INVOKED
189 class Traits = split_list::type_traits
197 typedef Traits options ; ///< Traits template parameters
198 typedef GC gc ; ///< Garbage collector
202 typedef split_list::details::rebind_list_options<OrderedList, options> wrapped_ordered_list;
206 # ifdef CDS_DOXYGEN_INVOKED
207 typedef OrderedList ordered_list ; ///< type of ordered list used as base for split-list
209 typedef typename wrapped_ordered_list::result ordered_list;
211 typedef typename ordered_list::value_type value_type ; ///< type of value stored in the split-list
212 typedef typename ordered_list::key_comparator key_comparator ; ///< key comparison functor
213 typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
215 /// Hash functor for \p %value_type and all its derivatives that you use
216 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
218 typedef typename options::item_counter item_counter ; ///< Item counter type
219 typedef typename options::back_off back_off ; ///< back-off strategy for spinning
220 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
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 \ref list_node_type
231 and split-list node type \ref 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 options::dynamic_bucket_table
241 , opt::allocator< typename options::allocator >
242 , opt::memory_model< memory_model >
243 >::type bucket_table;
249 /// Ordered list wrapper to access protected members
250 class ordered_list_wrapper: public ordered_list
252 typedef ordered_list base_class;
253 typedef typename base_class::auxiliary_head bucket_head_type;
256 bool insert_at( dummy_node_type * pHead, value_type& val )
258 assert( pHead != nullptr );
259 bucket_head_type h(pHead);
260 return base_class::insert_at( h, val );
263 template <typename Func>
264 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
266 assert( pHead != nullptr );
267 bucket_head_type h(pHead);
268 return base_class::insert_at( h, val, f );
271 template <typename Func>
272 std::pair<bool, bool> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
274 assert( pHead != nullptr );
275 bucket_head_type h(pHead);
276 return base_class::ensure_at( h, val, func );
279 bool unlink_at( dummy_node_type * pHead, value_type& val )
281 assert( pHead != nullptr );
282 bucket_head_type h(pHead);
283 return base_class::unlink_at( h, val );
286 template <typename Q, typename Compare, typename Func>
287 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
289 assert( pHead != nullptr );
290 bucket_head_type h(pHead);
291 return base_class::erase_at( h, val, cmp, f );
294 template <typename Q, typename Compare>
295 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
297 assert( pHead != nullptr );
298 bucket_head_type h(pHead);
299 return base_class::erase_at( h, val, cmp );
302 template <typename Q, typename Compare>
303 bool extract_at( dummy_node_type * pHead, typename gc::Guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
305 assert( pHead != nullptr );
306 bucket_head_type h(pHead);
307 return base_class::extract_at( h, guard, val, cmp );
310 template <typename Q, typename Compare, typename Func>
311 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
313 assert( pHead != nullptr );
314 bucket_head_type h(pHead);
315 return base_class::find_at( h, val, cmp, f );
318 template <typename Q, typename Compare>
319 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
321 assert( pHead != nullptr );
322 bucket_head_type h(pHead);
323 return base_class::find_at( h, val, cmp );
326 template <typename Q, typename Compare>
327 bool get_at( dummy_node_type * pHead, typename gc::Guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
329 assert( pHead != nullptr );
330 bucket_head_type h(pHead);
331 return base_class::get_at( h, guard, val, cmp );
334 bool insert_aux_node( dummy_node_type * pNode )
336 return base_class::insert_aux_node( pNode );
338 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
340 bucket_head_type h(pHead);
341 return base_class::insert_aux_node( h, pNode );
347 ordered_list_wrapper m_List ; ///< Ordered list containing split-list items
348 bucket_table m_Buckets ; ///< bucket table
349 atomics::atomic<size_t> m_nBucketCountLog2 ; ///< log2( current bucket count )
350 item_counter m_ItemCounter ; ///< Item counter
351 hash m_HashFunctor ; ///< Hash functor
355 typedef cds::details::Allocator< dummy_node_type, typename options::allocator > dummy_node_allocator;
356 static dummy_node_type * alloc_dummy_node( size_t nHash )
358 return dummy_node_allocator().New( nHash );
360 static void free_dummy_node( dummy_node_type * p )
362 dummy_node_allocator().Delete( p );
365 /// Calculates hash value of \p key
366 template <typename Q>
367 size_t hash_value( Q const& key ) const
369 return m_HashFunctor( key );
372 size_t bucket_no( size_t nHash ) const
374 return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
377 static size_t parent_bucket( size_t nBucket )
379 assert( nBucket > 0 );
380 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
383 dummy_node_type * init_bucket( size_t nBucket )
385 assert( nBucket > 0 );
386 size_t nParent = parent_bucket( nBucket );
388 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
389 if ( pParentBucket == nullptr ) {
390 pParentBucket = init_bucket( nParent );
393 assert( pParentBucket != nullptr );
395 // Allocate a dummy node for new bucket
397 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
398 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
399 m_Buckets.bucket( nBucket, pBucket );
402 free_dummy_node( pBucket );
405 // Another thread set the bucket. Wait while it done
407 // In this point, we must wait while nBucket is empty.
408 // The compiler can decide that waiting loop can be "optimized" (stripped)
409 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
413 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
415 return const_cast<dummy_node_type *>( p );
420 dummy_node_type * get_bucket( size_t nHash )
422 size_t nBucket = bucket_no( nHash );
424 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
425 if ( pHead == nullptr )
426 pHead = init_bucket( nBucket );
428 assert( pHead->is_dummy() );
435 // GC and OrderedList::gc must be the same
436 static_assert(( std::is_same<gc, typename ordered_list::gc>::value ), "GC and OrderedList::gc must be the same");
438 // atomicity::empty_item_counter is not allowed as a item counter
439 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
441 // Initialize bucket 0
442 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
444 // insert_aux_node cannot return false for empty list
445 CDS_VERIFY( m_List.insert_aux_node( pNode ));
447 m_Buckets.bucket( 0, pNode );
450 void inc_item_count()
452 size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
453 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
455 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
459 template <typename Q, typename Compare, typename Func>
460 bool find_( Q& val, Compare cmp, Func f )
462 size_t nHash = hash_value( val );
463 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
464 dummy_node_type * pHead = get_bucket( nHash );
465 assert( pHead != nullptr );
467 # ifdef CDS_CXX11_LAMBDA_SUPPORT
468 return m_List.find_at( pHead, sv, cmp,
469 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ cds::unref(f)(item, val.val ); });
471 split_list::details::find_functor_wrapper<Func> ffw( f );
472 return m_List.find_at( pHead, sv, cmp, cds::ref(ffw) );
476 template <typename Q, typename Compare>
477 bool find_( Q const& val, Compare cmp )
479 size_t nHash = hash_value( val );
480 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
481 dummy_node_type * pHead = get_bucket( nHash );
482 assert( pHead != nullptr );
484 return m_List.find_at( pHead, sv, cmp );
487 template <typename Q, typename Compare>
488 bool get_( typename gc::Guard& guard, Q const& val, Compare cmp )
490 size_t nHash = hash_value( val );
491 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
492 dummy_node_type * pHead = get_bucket( nHash );
493 assert( pHead != nullptr );
495 return m_List.get_at( pHead, guard, sv, cmp );
498 template <typename Q>
499 bool get_( typename gc::Guard& guard, Q const& key)
501 return get_( guard, key, key_comparator());
504 template <typename Q, typename Less>
505 bool get_with_( typename gc::Guard& guard, Q const& key, Less )
507 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
510 template <typename Q, typename Compare, typename Func>
511 bool erase_( Q const& val, Compare cmp, Func f )
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 if ( m_List.erase_at( pHead, sv, cmp, f )) {
525 template <typename Q, typename Compare>
526 bool erase_( Q const& val, Compare cmp )
528 size_t nHash = hash_value( val );
529 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
530 dummy_node_type * pHead = get_bucket( nHash );
531 assert( pHead != nullptr );
533 if ( m_List.erase_at( pHead, sv, cmp ) ) {
540 template <typename Q, typename Compare>
541 bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
543 size_t nHash = hash_value( val );
544 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
545 dummy_node_type * pHead = get_bucket( nHash );
546 assert( pHead != nullptr );
548 if ( m_List.extract_at( pHead, guard, sv, cmp ) ) {
555 template <typename Q>
556 bool extract_( typename gc::Guard& guard, Q const& key)
558 return extract_( guard, key, key_comparator());
561 template <typename Q, typename Less>
562 bool extract_with_( typename gc::Guard& guard, Q const& key, Less )
564 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
570 /// Initialize split-ordered list of default capacity
572 The default capacity is defined in bucket table constructor.
573 See split_list::expandable_bucket_table, split_list::static_ducket_table
574 which selects by split_list::dynamic_bucket_table option.
577 : m_nBucketCountLog2(1)
582 /// Initialize split-ordered list
584 size_t nItemCount ///< estimate average of item count
585 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
587 : m_Buckets( nItemCount, nLoadFactor )
588 , m_nBucketCountLog2(1)
596 The function inserts \p val in the set if it does not contain
597 an item with key equal to \p val.
599 Returns \p true if \p val is placed into the set, \p false otherwise.
601 bool insert( value_type& val )
603 size_t nHash = hash_value( val );
604 dummy_node_type * pHead = get_bucket( nHash );
605 assert( pHead != nullptr );
607 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
609 if ( m_List.insert_at( pHead, val )) {
618 This function is intended for derived non-intrusive containers.
620 The function allows to split creating of new item into two part:
621 - create item with key only
622 - insert new item into the set
623 - if inserting is success, calls \p f functor to initialize value-field of \p val.
625 The functor signature is:
627 void func( value_type& val );
629 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
630 \p val no any other changes could be made on this set's item by concurrent threads.
631 The user-defined functor is called only if the inserting is success and may be passed by reference
632 using <tt>boost::ref</tt>
634 template <typename Func>
635 bool insert( value_type& val, Func f )
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, f )) {
650 /// Ensures that the \p val exists in the set
652 The operation performs inserting or changing data with lock-free manner.
654 If the item \p val is not found in the set, then \p val is inserted into the set.
655 Otherwise, the functor \p func is called with item found.
656 The functor signature is:
658 void func( bool bNew, value_type& item, value_type& val );
661 - \p bNew - \p true if the item has been inserted, \p false otherwise
662 - \p item - item of the set
663 - \p val - argument \p val passed into the \p ensure function
664 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
665 refers to the same thing.
667 The functor can change non-key fields of the \p item; however, \p func must guarantee
668 that during changing no any other modifications could be made on this item by concurrent threads.
670 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
672 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
673 \p second is \p true if new item has been added or \p false if the item with \p key
674 already is in the set.
676 template <typename Func>
677 std::pair<bool, bool> ensure( value_type& val, Func func )
679 size_t nHash = hash_value( val );
680 dummy_node_type * pHead = get_bucket( nHash );
681 assert( pHead != nullptr );
683 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
685 std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
686 if ( bRet.first && bRet.second )
691 /// Unlinks the item \p val from the set
693 The function searches the item \p val in the set and unlinks it from the set
694 if it is found and is equal to \p val.
696 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
697 and deletes the item found. \p unlink finds an item by key and deletes it
698 only if \p val is an item of that set, i.e. the pointer to item found
699 is equal to <tt> &val </tt>.
701 The function returns \p true if success and \p false otherwise.
703 bool unlink( value_type& val )
705 size_t nHash = hash_value( val );
706 dummy_node_type * pHead = get_bucket( nHash );
707 assert( pHead != nullptr );
709 if ( m_List.unlink_at( pHead, val ) ) {
716 /// Deletes the item from the set
717 /** \anchor cds_intrusive_SplitListSet_hp_erase
718 The function searches an item with key equal to \p val in the set,
719 unlinks it from the set, and returns \p true.
720 If the item with key equal to \p val is not found the function return \p false.
722 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
723 and deletes the item found. \p unlink finds an item by key and deletes it
724 only if \p val is an item of that set, i.e. the pointer to item found
725 is equal to <tt> &val </tt>.
727 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
729 template <typename Q>
730 bool erase( Q const& val )
732 return erase_( val, key_comparator() );
735 /// Deletes the item from the set with comparing functor \p pred
737 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
738 but \p pred predicate is used for key comparing.
739 \p Less has the interface like \p std::less.
740 \p pred must imply the same element order as the comparator used for building the set.
742 template <typename Q, typename Less>
743 bool erase_with( const Q& val, Less pred )
745 return erase_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
748 /// Deletes the item from the set
749 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
750 The function searches an item with key equal to \p val in the set,
751 call \p f functor with item found, unlinks it from the set, and returns \p true.
752 The \ref disposer specified by \p OrderedList class template parameter is called
753 by garbage collector \p GC asynchronously.
755 The \p Func interface is
758 void operator()( value_type const& item );
761 The functor can be passed by reference with <tt>boost:ref</tt>
763 If the item with key equal to \p val is not found the function return \p false.
765 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
767 template <typename Q, typename Func>
768 bool erase( Q const& val, Func f )
770 return erase_( val, key_comparator(), f );
773 /// Deletes the item from the set with comparing functor \p pred
775 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
776 but \p pred predicate is used for key comparing.
777 \p Less has the interface like \p std::less.
778 \p pred must imply the same element order as the comparator used for building the set.
780 template <typename Q, typename Less, typename Func>
781 bool erase_with( Q const& val, Less pred, Func f )
783 return erase_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
786 /// Extracts the item with specified \p key
787 /** \anchor cds_intrusive_SplitListSet_hp_extract
788 The function searches an item with key equal to \p key,
789 unlinks it from the set, and returns it in \p dest parameter.
790 If the item with key equal to \p key is not found the function returns \p false.
792 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
794 The \ref disposer specified in \p OrderedList class' template parameter is called automatically
795 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
796 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
800 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
801 splitlist_set theSet;
804 splitlist_set::guarded_ptr gp;
805 theSet.extract( gp, 5 );
809 // Destructor of gp releases internal HP guard
813 template <typename Q>
814 bool extract( guarded_ptr& dest, Q const& key )
816 return extract_( dest.guard(), key );
819 /// Extracts the item using compare functor \p pred
821 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(guarded_ptr&, Q const&)"
822 but \p pred predicate is used for key comparing.
824 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
826 \p pred must imply the same element order as the comparator used for building the set.
828 template <typename Q, typename Less>
829 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
831 return extract_with_( dest.guard(), key, pred );
835 /// Finds the key \p val
836 /** \anchor cds_intrusive_SplitListSet_hp_find_func
837 The function searches the item with key equal to \p val and calls the functor \p f for item found.
838 The interface of \p Func functor is:
841 void operator()( value_type& item, Q& val );
844 where \p item is the item found, \p val is the <tt>find</tt> function argument.
846 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
848 The functor can change non-key fields of \p item. Note that the functor is only guarantee
849 that \p item cannot be disposed during functor is executing.
850 The functor does not serialize simultaneous access to the set \p item. If such access is
851 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
853 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
854 can modify both arguments.
856 Note the hash functor specified for class \p Traits template parameter
857 should accept a parameter of type \p Q that can be not the same as \p value_type.
859 The function returns \p true if \p val is found, \p false otherwise.
861 template <typename Q, typename Func>
862 bool find( Q& val, Func f )
864 return find_( val, key_comparator(), f );
867 /// Finds the key \p val with \p pred predicate for comparing
869 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
870 but \p cmp is used for key compare.
871 \p Less has the interface like \p std::less.
872 \p cmp must imply the same element order as the comparator used for building the set.
874 template <typename Q, typename Less, typename Func>
875 bool find_with( Q& val, Less pred, Func f )
877 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
880 /// Finds the key \p val
881 /** \anchor cds_intrusive_SplitListSet_hp_find_cfunc
882 The function searches the item with key equal to \p val and calls the functor \p f for item found.
883 The interface of \p Func functor is:
886 void operator()( value_type& item, Q const& val );
889 where \p item is the item found, \p val is the <tt>find</tt> function argument.
891 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
893 The functor can change non-key fields of \p item. Note that the functor is only guarantee
894 that \p item cannot be disposed during functor is executing.
895 The functor does not serialize simultaneous access to the set \p item. If such access is
896 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
898 Note the hash functor specified for class \p Traits template parameter
899 should accept a parameter of type \p Q that can be not the same as \p value_type.
901 The function returns \p true if \p val is found, \p false otherwise.
903 template <typename Q, typename Func>
904 bool find( Q const& val, Func f )
906 return find_( val, key_comparator(), f );
909 /// Finds the key \p val with \p pred predicate for comparing
911 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_cfunc "find(Q const&, Func)"
912 but \p cmp is used for key compare.
913 \p Less has the interface like \p std::less.
914 \p cmp must imply the same element order as the comparator used for building the set.
916 template <typename Q, typename Less, typename Func>
917 bool find_with( Q const& val, Less pred, Func f )
919 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
922 /// Finds the key \p val
923 /** \anchor cds_intrusive_SplitListSet_hp_find_val
924 The function searches the item with key equal to \p val
925 and returns \p true if it is found, and \p false otherwise.
927 Note the hash functor specified for class \p Traits template parameter
928 should accept a parameter of type \p Q that can be not the same as \p value_type.
929 Otherwise, you may use \p find_with functions with explicit predicate for key comparing.
931 template <typename Q>
932 bool find( Q const& val )
934 return find_( val, key_comparator() );
937 /// Finds the key \p val with \p pred predicate for comparing
939 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_val "find(Q const&)"
940 but \p cmp is used for key compare.
941 \p Less has the interface like \p std::less.
942 \p cmp must imply the same element order as the comparator used for building the set.
944 template <typename Q, typename Less>
945 bool find_with( Q const& val, Less pred )
947 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
950 /// Finds the key \p val and return the item found
951 /** \anchor cds_intrusive_SplitListSet_hp_get
952 The function searches the item with key equal to \p val
953 and assigns the item found to guarded pointer \p ptr.
954 The function returns \p true if \p val is found, and \p false otherwise.
955 If \p val is not found the \p ptr parameter is not changed.
957 The \ref disposer specified in \p OrderedList class' template parameter is called
958 by garbage collector \p GC automatically when returned \ref guarded_ptr object
959 will be destroyed or released.
960 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
964 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
965 splitlist_set theSet;
968 splitlist_set::guarded_ptr gp;
969 if ( theSet.get( gp, 5 )) {
973 // Destructor of guarded_ptr releases internal HP guard
977 Note the compare functor specified for \p OrderedList template parameter
978 should accept a parameter of type \p Q that can be not the same as \p value_type.
980 template <typename Q>
981 bool get( guarded_ptr& ptr, Q const& val )
983 return get_( ptr.guard(), val );
986 /// Finds the key \p val and return the item found
988 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
989 but \p pred is used for comparing the keys.
991 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
993 \p pred must imply the same element order as the comparator used for building the set.
995 template <typename Q, typename Less>
996 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
998 return get_with_( ptr.guard(), val, pred );
1001 /// Returns item count in the set
1004 return m_ItemCounter;
1007 /// Checks if the set is empty
1009 Emptiness is checked by item counting: if item count is zero then the set is empty.
1010 Thus, the correct item counting feature is an important part of split-list set implementation.
1017 /// Clears the set (non-atomic)
1019 The function unlink all items from the set.
1020 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1022 For each item the \p disposer is called after unlinking.
1026 iterator it = begin();
1027 while ( it != end() ) {
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
1102 return const_iterator( m_List.begin(), m_List.end() );
1105 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1106 const_iterator end() const
1108 return const_iterator( m_List.end(), m_List.end() );
1113 }} // namespace cds::intrusive
1115 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_H