3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
6 #include <cds/intrusive/details/split_list_base.h>
7 #include <cds/details/binary_functor_wrapper.h>
9 namespace cds { namespace intrusive {
11 /// Split-ordered list RCU specialization
12 /** @ingroup cds_intrusive_map
13 \anchor cds_intrusive_SplitListSet_rcu
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 moving an item on resizing, see \ref cds_SplitList_algo_desc "short algo description".
25 Template parameters are:
26 - \p RCU - one of \ref cds_urcu_gc "RCU type"
27 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
28 The intrusive ordered list implementation specifies the type \p T stored in the hash-set,
29 the comparing functor for the type \p T and other features specific for the ordered list.
30 - \p Traits - set traits, default isd \p split_list::traits.
31 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
33 @note About reqired features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
36 Before including <tt><cds/intrusive/split_list_rcu.h></tt> you should include appropriate RCU header file,
37 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
38 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" and
39 MichaelList-based split-list you should include:
41 #include <cds/urcu/general_buffered.h>
42 #include <cds/intrusive/michael_list_rcu.h>
43 #include <cds/intrusive/split_list_rcu.h>
45 // Declare Michael's list for type Foo and default traits:
46 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
48 // Declare split-list based on rcu_michael_list
49 typedef cds::intrusive::SplitListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, rcu_michael_list > rcu_split_list;
56 # ifdef CDS_DOXYGEN_INVOKED
57 class Traits = split_list::traits
62 class SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
65 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
66 typedef Traits traits; ///< Traits template parameters
68 /// Hash functor for \ref value_type and all its derivatives that you use
69 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
72 typedef cds::intrusive::split_list::implementation_tag implementation_tag;
77 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
81 # ifdef CDS_DOXYGEN_INVOKED
82 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
84 typedef typename wrapped_ordered_list::result ordered_list;
86 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
87 typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
88 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
89 typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock
90 typedef typename ordered_list::exempt_ptr exempt_ptr; ///< pointer to extracted node
91 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
92 static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
94 typedef typename traits::item_counter item_counter; ///< Item counter type
95 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
96 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
97 typedef typename traits::stat stat; ///< Internal statistics
100 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
101 typedef split_list::node<list_node_type> node_type; ///< split-list node type
102 typedef node_type dummy_node_type; ///< dummy node type
104 /// Split-list node traits
106 This traits is intended for converting between underlying ordered list node type \ref list_node_type
107 and split-list node type \ref node_type
109 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
112 /// Bucket table implementation
113 typedef typename split_list::details::bucket_table_selector<
114 traits::dynamic_bucket_table
117 , opt::allocator< typename traits::allocator >
118 , opt::memory_model< memory_model >
119 >::type bucket_table;
125 /// Ordered list wrapper to access protected members of OrderedList
126 class ordered_list_wrapper: public ordered_list
128 typedef ordered_list base_class;
129 typedef typename base_class::auxiliary_head bucket_head_type;
132 bool insert_at( dummy_node_type * pHead, value_type& val )
134 assert( pHead != nullptr );
135 bucket_head_type h(pHead);
136 return base_class::insert_at( h, val );
139 template <typename Func>
140 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
142 assert( pHead != nullptr );
143 bucket_head_type h(pHead);
144 return base_class::insert_at( h, val, f );
147 template <typename Func>
148 std::pair<bool, bool> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
150 assert( pHead != nullptr );
151 bucket_head_type h(pHead);
152 return base_class::ensure_at( h, val, func );
155 bool unlink_at( dummy_node_type * pHead, value_type& val )
157 assert( pHead != nullptr );
158 bucket_head_type h(pHead);
159 return base_class::unlink_at( h, val );
162 template <typename Q, typename Compare, typename Func>
163 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
165 assert( pHead != nullptr );
166 bucket_head_type h(pHead);
167 return base_class::erase_at( h, val, cmp, f );
170 template <typename Q, typename Compare>
171 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
173 assert( pHead != nullptr );
174 bucket_head_type h(pHead);
175 return base_class::erase_at( h, val, cmp );
178 template <typename Q, typename Compare>
179 value_type * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
181 assert( pHead != nullptr );
182 bucket_head_type h(pHead);
183 return base_class::extract_at( h, val, cmp );
186 template <typename Q, typename Compare, typename Func>
187 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f ) const
189 assert( pHead != nullptr );
190 bucket_head_type h(pHead);
191 return base_class::find_at( h, val, cmp, f );
194 template <typename Q, typename Compare>
195 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp ) const
197 assert( pHead != nullptr );
198 bucket_head_type h(pHead);
199 return base_class::find_at( h, val, cmp );
202 template <typename Q, typename Compare>
203 value_type * get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp ) const
205 assert( pHead != nullptr );
206 bucket_head_type h(pHead);
207 return base_class::get_at( h, val, cmp );
210 bool insert_aux_node( dummy_node_type * pNode )
212 return base_class::insert_aux_node( pNode );
214 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
216 bucket_head_type h(pHead);
217 return base_class::insert_aux_node( h, pNode );
221 template <typename Less>
222 struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
224 typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
226 template <typename Q1, typename Q2>
227 int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
229 return base_wrapper::operator()( v1.val, v2 );
232 template <typename Q1, typename Q2>
233 int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
235 return base_wrapper::operator()( v1, v2.val );
241 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
242 bucket_table m_Buckets; ///< bucket table
243 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
244 item_counter m_ItemCounter; ///< Item counter
245 hash m_HashFunctor; ///< Hash functor
246 stat m_Stat; ///< Internal stattistics accumulator
250 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
252 dummy_node_type * alloc_dummy_node( size_t nHash )
254 m_Stat.onHeadNodeAllocated();
255 return dummy_node_allocator().New( nHash );
257 void free_dummy_node( dummy_node_type * p )
259 dummy_node_allocator().Delete( p );
260 m_Stat.onHeadNodeFreed();
263 /// Calculates hash value of \p key
264 template <typename Q>
265 size_t hash_value( Q const& key ) const
267 return m_HashFunctor( key );
270 size_t bucket_no( size_t nHash ) const
272 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
275 static size_t parent_bucket( size_t nBucket )
277 assert( nBucket > 0 );
278 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
281 dummy_node_type * init_bucket( size_t nBucket )
283 assert( nBucket > 0 );
284 size_t nParent = parent_bucket( nBucket );
286 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
287 if ( pParentBucket == nullptr ) {
288 pParentBucket = init_bucket( nParent );
289 m_Stat.onRecursiveInitBucket();
292 assert( pParentBucket != nullptr );
294 // Allocate a dummy node for new bucket
296 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
297 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
298 m_Buckets.bucket( nBucket, pBucket );
299 m_Stat.onNewBucket();
302 free_dummy_node( pBucket );
305 // Another thread set the bucket. Wait while it done
307 // In this point, we must wait while nBucket is empty.
308 // The compiler can decide that waiting loop can be "optimized" (stripped)
309 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
311 m_Stat.onBucketInitContenton();
314 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
316 return const_cast<dummy_node_type *>( p );
318 m_Stat.onBusyWaitBucketInit();
322 dummy_node_type * get_bucket( size_t nHash )
324 size_t nBucket = bucket_no( nHash );
326 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
327 if ( pHead == nullptr )
328 pHead = init_bucket( nBucket );
330 assert( pHead->is_dummy() );
337 // GC and OrderedList::gc must be the same
338 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
340 // atomicity::empty_item_counter is not allowed as a item counter
341 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
342 "cds::atomicity::empty_item_counter is not allowed as a item counter");
344 // Initialize bucket 0
345 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
347 // insert_aux_node cannot return false for empty list
348 CDS_VERIFY( m_List.insert_aux_node( pNode ));
350 m_Buckets.bucket( 0, pNode );
353 void inc_item_count()
355 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
356 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
358 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
362 template <typename Q, typename Compare, typename Func>
363 bool find_( Q& val, Compare cmp, Func f )
365 size_t nHash = hash_value( val );
366 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
367 dummy_node_type * pHead = get_bucket( nHash );
368 assert( pHead != nullptr );
370 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
371 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
374 template <typename Q, typename Compare>
375 bool find_value( Q const& val, Compare cmp )
377 size_t nHash = hash_value( val );
378 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
379 dummy_node_type * pHead = get_bucket( nHash );
380 assert( pHead != nullptr );
382 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
385 template <typename Q, typename Compare>
386 value_type * get_( Q const& val, Compare cmp )
388 size_t nHash = hash_value( val );
389 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
390 dummy_node_type * pHead = get_bucket( nHash );
391 assert( pHead != nullptr );
393 value_type * p = m_List.get_at( pHead, sv, cmp );
394 m_Stat.onFind( p != nullptr );
398 template <typename Q, typename Compare>
399 value_type * extract_( Q const& val, Compare cmp )
401 size_t nHash = hash_value( val );
402 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
403 dummy_node_type * pHead = get_bucket( nHash );
404 assert( pHead != nullptr );
406 value_type * pNode = m_List.extract_at( pHead, sv, cmp );
409 m_Stat.onExtractSuccess();
412 m_Stat.onExtractFailed();
416 template <typename Q, typename Less>
417 value_type * extract_with_( Q const& val, Less pred )
420 return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
423 template <typename Q, typename Compare>
424 bool erase_( const Q& val, Compare cmp )
426 size_t nHash = hash_value( val );
427 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
428 dummy_node_type * pHead = get_bucket( nHash );
429 assert( pHead != nullptr );
431 if ( m_List.erase_at( pHead, sv, cmp ) ) {
433 m_Stat.onEraseSuccess();
436 m_Stat.onEraseFailed();
440 template <typename Q, typename Compare, typename Func>
441 bool erase_( Q const& val, Compare cmp, Func f )
443 size_t nHash = hash_value( val );
444 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
445 dummy_node_type * pHead = get_bucket( nHash );
446 assert( pHead != nullptr );
448 if ( m_List.erase_at( pHead, sv, cmp, f )) {
450 m_Stat.onEraseSuccess();
453 m_Stat.onEraseFailed();
460 /// Initialize split-ordered list of default capacity
462 The default capacity is defined in bucket table constructor.
463 See split_list::expandable_bucket_table, split_list::static_ducket_table
464 which selects by split_list::dynamic_bucket_table option.
467 : m_nBucketCountLog2(1)
472 /// Initialize split-ordered list
474 size_t nItemCount ///< estimate average of item count
475 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
477 : m_Buckets( nItemCount, nLoadFactor )
478 , m_nBucketCountLog2(1)
486 The function inserts \p val in the set if it does not contain
487 an item with key equal to \p val.
489 The function makes RCU lock internally.
491 Returns \p true if \p val is placed into the set, \p false otherwise.
493 bool insert( value_type& val )
495 size_t nHash = hash_value( val );
496 dummy_node_type * pHead = get_bucket( nHash );
497 assert( pHead != nullptr );
499 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
501 if ( m_List.insert_at( pHead, val )) {
503 m_Stat.onInsertSuccess();
506 m_Stat.onInsertFailed();
512 This function is intended for derived non-intrusive containers.
514 The function allows to split creating of new item into two part:
515 - create item with key only
516 - insert new item into the set
517 - if inserting is success, calls \p f functor to initialize value-field of \p val.
519 The functor signature is:
521 void func( value_type& val );
523 where \p val is the item inserted.
525 The function makes RCU lock internally.
527 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
528 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
531 template <typename Func>
532 bool insert( value_type& val, Func f )
534 size_t nHash = hash_value( val );
535 dummy_node_type * pHead = get_bucket( nHash );
536 assert( pHead != nullptr );
538 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
540 if ( m_List.insert_at( pHead, val, f )) {
542 m_Stat.onInsertSuccess();
545 m_Stat.onInsertFailed();
549 /// Ensures that the \p val exists in the set
551 The operation performs inserting or changing data with lock-free manner.
553 If the item \p val is not found in the set, then \p val is inserted into the set.
554 Otherwise, the functor \p func is called with item found.
555 The functor signature is:
557 void func( bool bNew, value_type& item, value_type& val );
560 - \p bNew - \p true if the item has been inserted, \p false otherwise
561 - \p item - item of the set
562 - \p val - argument \p val passed into the \p ensure function
563 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
564 refers to the same thing.
566 The function makes RCU lock internally.
568 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
569 \p second is \p true if new item has been added or \p false if the item with \p key
570 already is in the set.
572 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
573 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
576 template <typename Func>
577 std::pair<bool, bool> ensure( value_type& val, Func func )
579 size_t nHash = hash_value( val );
580 dummy_node_type * pHead = get_bucket( nHash );
581 assert( pHead != nullptr );
583 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
585 std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
586 if ( bRet.first && bRet.second ) {
588 m_Stat.onEnsureNew();
591 m_Stat.onEnsureExist();
595 /// Unlinks the item \p val from the set
597 The function searches the item \p val in the set and unlinks it from the set
598 if it is found and is equal to \p val.
600 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
601 and deletes the item found. \p unlink finds an item by key and deletes it
602 only if \p val is an item of that set, i.e. the pointer to item found
603 is equal to <tt> &val </tt>.
605 RCU \p synchronize method can be called, therefore, RCU should not be locked.
607 The function returns \p true if success and \p false otherwise.
609 bool unlink( value_type& val )
611 size_t nHash = hash_value( val );
612 dummy_node_type * pHead = get_bucket( nHash );
613 assert( pHead != nullptr );
615 if ( m_List.unlink_at( pHead, val ) ) {
617 m_Stat.onEraseSuccess();
620 m_Stat.onEraseFailed();
624 /// Deletes the item from the set
625 /** \anchor cds_intrusive_SplitListSet_rcu_erase
626 The function searches an item with key equal to \p key in the set,
627 unlinks it from the set, and returns \p true.
628 If the item with key equal to \p key is not found the function return \p false.
630 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
631 and deletes the item found. \p unlink finds an item by key and deletes it
632 only if \p key is an item of that set, i.e. the pointer to item found
633 is equal to <tt> &key </tt>.
635 RCU \p synchronize method can be called, therefore, RCU should not be locked.
637 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
639 template <typename Q>
640 bool erase( Q const& key )
642 return erase_( key, key_comparator() );
645 /// Deletes the item from the set using \p pred for searching
647 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
648 but \p cmp is used for key compare.
649 \p Less has the interface like \p std::less.
650 \p pred must imply the same element order as the comparator used for building the set.
652 template <typename Q, typename Less>
653 bool erase_with( Q const& key, Less pred )
656 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
659 /// Deletes the item from the set
660 /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
661 The function searches an item with key equal to \p key in the set,
662 call \p f functor with item found, unlinks it from the set, and returns \p true.
663 The \ref disposer specified by \p OrderedList class template parameter is called
664 by garbage collector \p GC asynchronously.
666 The \p Func interface is
669 void operator()( value_type const& item );
673 If the item with key equal to \p key is not found the function return \p false.
675 RCU \p synchronize method can be called, therefore, RCU should not be locked.
677 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
679 template <typename Q, typename Func>
680 bool erase( Q const& key, Func f )
682 return erase_( key, key_comparator(), f );
685 /// Deletes the item from the set using \p pred for searching
687 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
688 but \p cmp is used for key compare.
689 \p Less has the interface like \p std::less.
690 \p pred must imply the same element order as the comparator used for building the set.
692 template <typename Q, typename Less, typename Func>
693 bool erase_with( Q const& key, Less pred, Func f )
696 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
699 /// Extracts an item from the set
700 /** \anchor cds_intrusive_SplitListSet_rcu_extract
701 The function searches an item with key equal to \p key in the set,
702 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
703 If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
705 @note The function does NOT call RCU read-side lock or synchronization,
706 and does NOT dispose the item found. It just excludes the item from the set
707 and returns a pointer to item found.
708 You should lock RCU before calling of the function, and you should synchronize RCU
709 outside the RCU lock before reusing returned pointer.
712 typedef cds::urcu::gc< general_buffered<> > rcu;
713 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
714 typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
716 rcu_splitlist_set theSet;
719 rcu_splitlist_set::exempt_ptr p;
721 // first, we should lock RCU
722 rcu_splitlist_set::rcu_lock lock;
724 // Now, you can apply extract function
725 // Note that you must not delete the item found inside the RCU lock
726 p = theList.extract( 10 );
728 // do something with p
733 // We may safely release p here
734 // release() passes the pointer to RCU reclamation cycle:
735 // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
739 template <typename Q>
740 exempt_ptr extract( Q const& key )
742 return exempt_ptr(extract_( key, key_comparator() ));
745 /// Extracts an item from the set using \p pred for searching
747 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
748 \p Less functor has the interface like \p std::less.
749 \p pred must imply the same element order as the comparator used for building the set.
751 template <typename Q, typename Less>
752 exempt_ptr extract_with( Q const& key, Less pred )
754 return exempt_ptr( extract_with_( key, pred ));
757 /// Finds the key \p key
758 /** \anchor cds_intrusive_SplitListSet_rcu_find_func
759 The function searches the item with key equal to \p key and calls the functor \p f for item found.
760 The interface of \p Func functor is:
763 void operator()( value_type& item, Q& key );
766 where \p item is the item found, \p key is the <tt>find</tt> function argument.
768 The functor can change non-key fields of \p item. Note that the functor is only guarantee
769 that \p item cannot be disposed during functor is executing.
770 The functor does not serialize simultaneous access to the set \p item. If such access is
771 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
773 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
774 can modify both arguments.
776 Note the hash functor specified for class \p Traits template parameter
777 should accept a parameter of type \p Q that can be not the same as \p value_type.
779 The function applies RCU lock internally.
781 The function returns \p true if \p key is found, \p false otherwise.
783 template <typename Q, typename Func>
784 bool find( Q& key, Func f )
786 return find_( key, key_comparator(), f );
789 template <typename Q, typename Func>
790 bool find( Q const& key, Func f )
792 return find_( key, key_comparator(), f );
796 /// Finds the key \p key with \p pred predicate for comparing
798 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
799 but \p cmp is used for key compare.
800 \p Less has the interface like \p std::less.
801 \p cmp must imply the same element order as the comparator used for building the set.
803 template <typename Q, typename Less, typename Func>
804 bool find_with( Q& key, Less pred, Func f )
807 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
810 template <typename Q, typename Less, typename Func>
811 bool find_with( Q const& key, Less pred, Func f )
814 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
818 /// Finds the key \p key
819 /** \anchor cds_intrusive_SplitListSet_rcu_find_val
820 The function searches the item with key equal to \p key
821 and returns \p true if \p key found or \p false otherwise.
823 template <typename Q>
824 bool find( Q const& key )
826 return find_value( key, key_comparator() );
829 /// Finds the key \p key with \p pred predicate for comparing
831 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_val "find(Q const&)"
832 but \p cmp is used for key compare.
833 \p Less has the interface like \p std::less.
834 \p pred must imply the same element order as the comparator used for building the set.
836 template <typename Q, typename Less>
837 bool find_with( Q const& key, Less pred )
840 return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
843 /// Finds the key \p key and return the item found
844 /** \anchor cds_intrusive_SplitListSet_rcu_get
845 The function searches the item with key equal to \p key and returns the pointer to item found.
846 If \p key is not found it returns \p nullptr.
848 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
850 RCU should be locked before call of this function.
851 Returned item is valid only while RCU is locked:
853 cds::intrusive::SplitListSet< your_template_parameters > theSet;
857 hash_set::rcu_lock lock;
859 foo * pVal = theSet.get( 5 );
864 // Unlock RCU by rcu_lock destructor
865 // pVal can be retired by disposer at any time after RCU has been unlocked
869 template <typename Q>
870 value_type * get( Q const& key )
872 return get_( key, key_comparator() );
875 /// Finds the key \p key and return the item found
877 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
878 but \p pred is used for comparing the keys.
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 value_type * get_with( Q const& key, Less pred )
888 return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
892 /// Returns item count in the set
895 return m_ItemCounter;
898 /// Checks if the set is empty
900 Emptiness is checked by item counting: if item count is zero then the set is empty.
901 Thus, the correct item counting feature is an important part of split-list set implementation.
908 /// Clears the set (not atomic)
911 iterator it = begin();
912 while ( it != end() ) {
920 /// Returns internal statistics
921 stat const& statistics() const
928 template <bool IsConst>
930 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
932 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
933 typedef typename iterator_base_class::list_iterator list_iterator;
936 : iterator_base_class()
939 iterator_type( iterator_type const& src )
940 : iterator_base_class( src )
943 // This ctor should be protected...
944 iterator_type( list_iterator itCur, list_iterator itEnd )
945 : iterator_base_class( itCur, itEnd )
952 The forward iterator for a split-list has some features:
953 - it has no post-increment operator
954 - it depends on iterator of underlying \p OrderedList
955 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
956 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
957 deleting operations it is no guarantee that you iterate all item in the split-list.
959 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
960 for debug purpose only.
962 typedef iterator_type<false> iterator;
963 /// Const forward iterator
965 For iterator's features and requirements see \ref iterator
967 typedef iterator_type<true> const_iterator;
969 /// Returns a forward iterator addressing the first element in a split-list
971 For empty list \code begin() == end() \endcode
975 return iterator( m_List.begin(), m_List.end() );
978 /// Returns an iterator that addresses the location succeeding the last element in a split-list
980 Do not use the value returned by <tt>end</tt> function to access any item.
982 The returned value can be used only to control reaching the end of the split-list.
983 For empty list \code begin() == end() \endcode
987 return iterator( m_List.end(), m_List.end() );
990 /// Returns a forward const iterator addressing the first element in a split-list
991 const_iterator begin() const
995 /// Returns a forward const iterator addressing the first element in a split-list
996 const_iterator cbegin() const
998 return const_iterator( m_List.cbegin(), m_List.cend() );
1001 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1002 const_iterator end() const
1006 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1007 const_iterator cend() const
1009 return const_iterator( m_List.cend(), m_List.cend() );
1014 }} // namespace cds::intrusive
1016 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H