3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
8 #include <cds/intrusive/details/split_list_base.h>
9 #include <cds/details/binary_functor_wrapper.h>
11 namespace cds { namespace intrusive {
13 /// Split-ordered list RCU specialization
14 /** @ingroup cds_intrusive_map
15 \anchor cds_intrusive_SplitListSet_rcu
17 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
18 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
19 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
21 The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
22 recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
23 without moving an item on resizing, see \ref cds_SplitList_algo_desc "short algo description".
27 Template parameters are:
28 - \p RCU - one of \ref cds_urcu_gc "RCU type"
29 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
30 The intrusive ordered list implementation specifies the type \p T stored in the hash-set,
31 the comparing functor for the type \p T and other features specific for the ordered list.
32 - \p Traits - set traits, default isd \p split_list::traits.
33 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
35 @note About required features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
38 Before including <tt><cds/intrusive/split_list_rcu.h></tt> you should include appropriate RCU header file,
39 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
40 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" and
41 MichaelList-based split-list you should include:
43 #include <cds/urcu/general_buffered.h>
44 #include <cds/intrusive/michael_list_rcu.h>
45 #include <cds/intrusive/split_list_rcu.h>
47 // Declare Michael's list for type Foo and default traits:
48 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
50 // Declare split-list based on rcu_michael_list
51 typedef cds::intrusive::SplitListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, rcu_michael_list > rcu_split_list;
58 # ifdef CDS_DOXYGEN_INVOKED
59 class Traits = split_list::traits
64 class SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
67 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
68 typedef Traits traits; ///< Traits template parameters
70 /// Hash functor for \ref value_type and all its derivatives that you use
71 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
75 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
79 # ifdef CDS_DOXYGEN_INVOKED
80 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
82 typedef typename wrapped_ordered_list::result ordered_list;
84 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
85 typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
86 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
87 typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock
88 typedef typename ordered_list::exempt_ptr exempt_ptr; ///< pointer to extracted node
89 typedef typename ordered_list::raw_ptr raw_ptr; ///< pointer to the node for \p get() function
90 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
91 static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
93 typedef typename traits::item_counter item_counter; ///< Item counter type
94 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
95 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
96 typedef typename traits::stat stat; ///< Internal statistics
99 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
100 typedef split_list::node<list_node_type> node_type; ///< split-list node type
101 typedef node_type dummy_node_type; ///< dummy node type
103 /// Split-list node traits
105 This traits is intended for converting between underlying ordered list node type \ref list_node_type
106 and split-list node type \ref node_type
108 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
111 /// Bucket table implementation
112 typedef typename split_list::details::bucket_table_selector<
113 traits::dynamic_bucket_table
116 , opt::allocator< typename traits::allocator >
117 , opt::memory_model< memory_model >
118 >::type bucket_table;
124 /// Ordered list wrapper to access protected members of OrderedList
125 class ordered_list_wrapper: public ordered_list
127 typedef ordered_list base_class;
128 typedef typename base_class::auxiliary_head bucket_head_type;
131 bool insert_at( dummy_node_type * pHead, value_type& val )
133 assert( pHead != nullptr );
134 bucket_head_type h(pHead);
135 return base_class::insert_at( h, val );
138 template <typename Func>
139 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
141 assert( pHead != nullptr );
142 bucket_head_type h(pHead);
143 return base_class::insert_at( h, val, f );
146 template <typename Func>
147 std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
149 assert( pHead != nullptr );
150 bucket_head_type h(pHead);
151 return base_class::update_at( h, val, func, bAllowInsert );
154 bool unlink_at( dummy_node_type * pHead, value_type& val )
156 assert( pHead != nullptr );
157 bucket_head_type h(pHead);
158 return base_class::unlink_at( h, val );
161 template <typename Q, typename Compare, typename Func>
162 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
164 assert( pHead != nullptr );
165 bucket_head_type h(pHead);
166 return base_class::erase_at( h, val, cmp, f );
169 template <typename Q, typename Compare>
170 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
172 assert( pHead != nullptr );
173 bucket_head_type h(pHead);
174 return base_class::erase_at( h, val, cmp );
177 template <typename Q, typename Compare>
178 value_type * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
180 assert( pHead != nullptr );
181 bucket_head_type h(pHead);
182 return base_class::extract_at( h, val, cmp );
185 template <typename Q, typename Compare, typename Func>
186 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
188 assert( pHead != nullptr );
189 bucket_head_type h(pHead);
190 return base_class::find_at( h, val, cmp, f );
193 template <typename Q, typename Compare>
194 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
196 assert( pHead != nullptr );
197 bucket_head_type h(pHead);
198 return base_class::find_at( h, val, cmp );
201 template <typename Q, typename Compare>
202 raw_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
204 assert( pHead != nullptr );
205 bucket_head_type h(pHead);
206 return base_class::get_at( h, val, cmp );
209 bool insert_aux_node( dummy_node_type * pNode )
211 return base_class::insert_aux_node( pNode );
213 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
215 bucket_head_type h(pHead);
216 return base_class::insert_aux_node( h, pNode );
220 template <typename Less>
221 struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
223 typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
225 template <typename Q1, typename Q2>
226 int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
228 return base_wrapper::operator()( v1.val, v2 );
231 template <typename Q1, typename Q2>
232 int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
234 return base_wrapper::operator()( v1, v2.val );
240 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
241 bucket_table m_Buckets; ///< bucket table
242 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
243 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
244 item_counter m_ItemCounter; ///< Item counter
245 hash m_HashFunctor; ///< Hash functor
246 stat m_Stat; ///< Internal statistics 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 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
355 return nBucketCount * nLoadFactor;
358 void inc_item_count()
360 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
361 if ( ++m_ItemCounter <= nMaxCount )
364 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
365 const size_t nBucketCount = static_cast<size_t>(1) << sz;
366 if ( nBucketCount < m_Buckets.capacity() ) {
367 // we may grow the bucket table
368 const size_t nLoadFactor = m_Buckets.load_factor();
369 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
370 return; // someone already have updated m_nBucketCountLog2, so stop here
372 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
373 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
374 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
377 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
380 template <typename Q, typename Compare, typename Func>
381 bool find_( Q& val, Compare cmp, Func f )
383 size_t nHash = hash_value( val );
384 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
385 dummy_node_type * pHead = get_bucket( nHash );
386 assert( pHead != nullptr );
388 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
389 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
392 template <typename Q, typename Compare>
393 bool find_value( Q const& val, Compare cmp )
395 size_t nHash = hash_value( val );
396 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
397 dummy_node_type * pHead = get_bucket( nHash );
398 assert( pHead != nullptr );
400 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
403 template <typename Q, typename Compare>
404 raw_ptr get_( Q const& val, Compare cmp )
406 size_t nHash = hash_value( val );
407 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
408 dummy_node_type * pHead = get_bucket( nHash );
409 assert( pHead != nullptr );
411 raw_ptr p = m_List.get_at( pHead, sv, cmp );
412 m_Stat.onFind( !!p );
416 template <typename Q, typename Compare>
417 value_type * extract_( Q const& val, Compare cmp )
419 size_t nHash = hash_value( val );
420 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
421 dummy_node_type * pHead = get_bucket( nHash );
422 assert( pHead != nullptr );
424 value_type * pNode = m_List.extract_at( pHead, sv, cmp );
427 m_Stat.onExtractSuccess();
430 m_Stat.onExtractFailed();
434 template <typename Q, typename Less>
435 value_type * extract_with_( Q const& val, Less pred )
438 return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
441 template <typename Q, typename Compare>
442 bool erase_( const Q& val, Compare cmp )
444 size_t nHash = hash_value( val );
445 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
446 dummy_node_type * pHead = get_bucket( nHash );
447 assert( pHead != nullptr );
449 if ( m_List.erase_at( pHead, sv, cmp ) ) {
451 m_Stat.onEraseSuccess();
454 m_Stat.onEraseFailed();
458 template <typename Q, typename Compare, typename Func>
459 bool erase_( Q const& val, Compare cmp, Func f )
461 size_t nHash = hash_value( val );
462 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
463 dummy_node_type * pHead = get_bucket( nHash );
464 assert( pHead != nullptr );
466 if ( m_List.erase_at( pHead, sv, cmp, f )) {
468 m_Stat.onEraseSuccess();
471 m_Stat.onEraseFailed();
478 /// Initialize split-ordered list of default capacity
480 The default capacity is defined in bucket table constructor.
481 See split_list::expandable_bucket_table, split_list::static_ducket_table
482 which selects by split_list::dynamic_bucket_table option.
485 : m_nBucketCountLog2(1)
486 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
491 /// Initialize split-ordered list
493 size_t nItemCount ///< estimate average of item count
494 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
496 : m_Buckets( nItemCount, nLoadFactor )
497 , m_nBucketCountLog2(1)
498 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
506 The function inserts \p val in the set if it does not contain
507 an item with key equal to \p val.
509 The function makes RCU lock internally.
511 Returns \p true if \p val is placed into the set, \p false otherwise.
513 bool insert( value_type& val )
515 size_t nHash = hash_value( val );
516 dummy_node_type * pHead = get_bucket( nHash );
517 assert( pHead != nullptr );
519 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
521 if ( m_List.insert_at( pHead, val )) {
523 m_Stat.onInsertSuccess();
526 m_Stat.onInsertFailed();
532 This function is intended for derived non-intrusive containers.
534 The function allows to split creating of new item into two part:
535 - create item with key only
536 - insert new item into the set
537 - if inserting is success, calls \p f functor to initialize value-field of \p val.
539 The functor signature is:
541 void func( value_type& val );
543 where \p val is the item inserted.
545 The function makes RCU lock internally.
547 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
548 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
551 template <typename Func>
552 bool insert( value_type& val, Func f )
554 size_t nHash = hash_value( val );
555 dummy_node_type * pHead = get_bucket( nHash );
556 assert( pHead != nullptr );
558 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
560 if ( m_List.insert_at( pHead, val, f )) {
562 m_Stat.onInsertSuccess();
565 m_Stat.onInsertFailed();
571 The operation performs inserting or changing data with lock-free manner.
573 If the item \p val is not found in the set, then \p val is inserted
574 iff \p bAllowInsert is \p true.
575 Otherwise, the functor \p func is called with item found.
576 The functor signature is:
578 void func( bool bNew, value_type& item, value_type& val );
581 - \p bNew - \p true if the item has been inserted, \p false otherwise
582 - \p item - item of the set
583 - \p val - argument \p val passed into the \p update() function
584 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
585 refers to the same stuff.
587 The functor may change non-key fields of the \p item.
589 The function applies RCU lock internally.
591 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
592 \p second is \p true if new item has been added or \p false if the item with \p key
593 already is in the list.
595 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
596 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
599 template <typename Func>
600 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
602 size_t nHash = hash_value( val );
603 dummy_node_type * pHead = get_bucket( nHash );
604 assert( pHead != nullptr );
606 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
608 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
609 if ( bRet.first && bRet.second ) {
611 m_Stat.onEnsureNew();
614 m_Stat.onEnsureExist();
618 template <typename Func>
619 CDS_DEPRECATED("ensure() is deprecated, use update()")
620 std::pair<bool, bool> ensure( value_type& val, Func func )
622 return update( val, func, true );
626 /// Unlinks the item \p val from the set
628 The function searches the item \p val in the set and unlinks it from the set
629 if it is found and is equal to \p val.
631 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
632 and deletes the item found. \p unlink finds an item by key and deletes it
633 only if \p val is an item of that set, i.e. the pointer to item found
634 is equal to <tt> &val </tt>.
636 RCU \p synchronize method can be called, therefore, RCU should not be locked.
638 The function returns \p true if success and \p false otherwise.
640 bool unlink( value_type& val )
642 size_t nHash = hash_value( val );
643 dummy_node_type * pHead = get_bucket( nHash );
644 assert( pHead != nullptr );
646 if ( m_List.unlink_at( pHead, val ) ) {
648 m_Stat.onEraseSuccess();
651 m_Stat.onEraseFailed();
655 /// Deletes the item from the set
656 /** \anchor cds_intrusive_SplitListSet_rcu_erase
657 The function searches an item with key equal to \p key in the set,
658 unlinks it from the set, and returns \p true.
659 If the item with key equal to \p key is not found the function return \p false.
661 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
662 and deletes the item found. \p unlink finds an item by key and deletes it
663 only if \p key is an item of that set, i.e. the pointer to item found
664 is equal to <tt> &key </tt>.
666 RCU \p synchronize method can be called, therefore, RCU should not be locked.
668 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
670 template <typename Q>
671 bool erase( Q const& key )
673 return erase_( key, key_comparator() );
676 /// Deletes the item from the set using \p pred for searching
678 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
679 but \p cmp is used for key compare.
680 \p Less has the interface like \p std::less.
681 \p pred must imply the same element order as the comparator used for building the set.
683 template <typename Q, typename Less>
684 bool erase_with( Q const& key, Less pred )
687 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
690 /// Deletes the item from the set
691 /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
692 The function searches an item with key equal to \p key in the set,
693 call \p f functor with item found, unlinks it from the set, and returns \p true.
694 The \ref disposer specified by \p OrderedList class template parameter is called
695 by garbage collector \p GC asynchronously.
697 The \p Func interface is
700 void operator()( value_type const& item );
704 If the item with key equal to \p key is not found the function return \p false.
706 RCU \p synchronize method can be called, therefore, RCU should not be locked.
708 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
710 template <typename Q, typename Func>
711 bool erase( Q const& key, Func f )
713 return erase_( key, key_comparator(), f );
716 /// Deletes the item from the set using \p pred for searching
718 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
719 but \p cmp is used for key compare.
720 \p Less has the interface like \p std::less.
721 \p pred must imply the same element order as the comparator used for building the set.
723 template <typename Q, typename Less, typename Func>
724 bool erase_with( Q const& key, Less pred, Func f )
727 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
730 /// Extracts an item from the set
731 /** \anchor cds_intrusive_SplitListSet_rcu_extract
732 The function searches an item with key equal to \p key in the set,
733 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
734 If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
736 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
737 - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
738 - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
739 See ordered list implementation for details.
742 typedef cds::urcu::gc< general_buffered<> > rcu;
743 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
744 typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
746 rcu_splitlist_set theSet;
749 rcu_splitlist_set::exempt_ptr p;
751 // For MichaelList we should not lock RCU
753 // Now, you can apply extract function
754 // Note that you must not delete the item found inside the RCU lock
755 p = theList.extract( 10 );
757 // do something with p
761 // We may safely release p here
762 // release() passes the pointer to RCU reclamation cycle:
763 // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
767 template <typename Q>
768 exempt_ptr extract( Q const& key )
770 return exempt_ptr(extract_( key, key_comparator() ));
773 /// Extracts an item from the set using \p pred for searching
775 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
776 \p Less functor has the interface like \p std::less.
777 \p pred must imply the same element order as the comparator used for building the set.
779 template <typename Q, typename Less>
780 exempt_ptr extract_with( Q const& key, Less pred )
782 return exempt_ptr( extract_with_( key, pred ));
785 /// Finds the key \p key
786 /** \anchor cds_intrusive_SplitListSet_rcu_find_func
787 The function searches the item with key equal to \p key and calls the functor \p f for item found.
788 The interface of \p Func functor is:
791 void operator()( value_type& item, Q& key );
794 where \p item is the item found, \p key is the <tt>find</tt> function argument.
796 The functor can change non-key fields of \p item. Note that the functor is only guarantee
797 that \p item cannot be disposed during functor is executing.
798 The functor does not serialize simultaneous access to the set \p item. If such access is
799 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
801 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
802 can modify both arguments.
804 Note the hash functor specified for class \p Traits template parameter
805 should accept a parameter of type \p Q that can be not the same as \p value_type.
807 The function applies RCU lock internally.
809 The function returns \p true if \p key is found, \p false otherwise.
811 template <typename Q, typename Func>
812 bool find( Q& key, Func f )
814 return find_( key, key_comparator(), f );
817 template <typename Q, typename Func>
818 bool find( Q const& key, Func f )
820 return find_( key, key_comparator(), f );
824 /// Finds the key \p key with \p pred predicate for comparing
826 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
827 but \p cmp is used for key compare.
828 \p Less has the interface like \p std::less.
829 \p cmp must imply the same element order as the comparator used for building the set.
831 template <typename Q, typename Less, typename Func>
832 bool find_with( Q& key, Less pred, Func f )
835 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
838 template <typename Q, typename Less, typename Func>
839 bool find_with( Q const& key, Less pred, Func f )
842 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
846 /// Checks whether the set contains \p key
848 The function searches the item with key equal to \p key
849 and returns \p true if it is found, and \p false otherwise.
851 Note the hash functor specified for class \p Traits template parameter
852 should accept a parameter of type \p Q that can be not the same as \p value_type.
853 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
855 template <typename Q>
856 bool contains( Q const& key )
858 return find_value( key, key_comparator() );
861 template <typename Q>
862 CDS_DEPRECATED("deprecated, use contains()")
863 bool find( Q const& key )
865 return contains( key );
869 /// Checks whether the set contains \p key using \p pred predicate for searching
871 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
872 \p Less functor has the interface like \p std::less.
873 \p Less must imply the same element order as the comparator used for building the list.
875 template <typename Q, typename Less>
876 bool contains( Q const& key, Less pred )
879 return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
882 template <typename Q, typename Less>
883 CDS_DEPRECATED("deprecated, use contains()")
884 bool find_with( Q const& key, Less pred )
886 return contains( key, pred );
890 /// Finds the key \p key and return the item found
891 /** \anchor cds_intrusive_SplitListSet_rcu_get
892 The function searches the item with key equal to \p key and returns the pointer to item found.
893 If \p key is not found it returns \p nullptr.
895 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
897 RCU should be locked before call of this function.
898 Returned item is valid only while RCU is locked:
900 typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
903 typename set_class::raw_ptr rp;
906 hash_set::rcu_lock lock;
908 rp = theSet.get( 5 );
913 // Unlock RCU by rcu_lock destructor
914 // rp can be retired by disposer at any time after RCU has been unlocked
918 template <typename Q>
919 raw_ptr get( Q const& key )
921 return get_( key, key_comparator() );
924 /// Finds the key \p key and return the item found
926 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
927 but \p pred is used for comparing the keys.
929 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
931 \p pred must imply the same element order as the comparator used for building the set.
933 template <typename Q, typename Less>
934 raw_ptr get_with( Q const& key, Less pred )
937 return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
941 /// Returns item count in the set
944 return m_ItemCounter;
947 /// Checks if the set is empty
949 Emptiness is checked by item counting: if item count is zero then the set is empty.
950 Thus, the correct item counting feature is an important part of split-list set implementation.
957 /// Clears the set (not atomic)
960 iterator it = begin();
961 while ( it != end() ) {
969 /// Returns internal statistics
970 stat const& statistics() const
977 template <bool IsConst>
979 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
981 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
982 typedef typename iterator_base_class::list_iterator list_iterator;
985 : iterator_base_class()
988 iterator_type( iterator_type const& src )
989 : iterator_base_class( src )
992 // This ctor should be protected...
993 iterator_type( list_iterator itCur, list_iterator itEnd )
994 : iterator_base_class( itCur, itEnd )
1000 /// Forward iterator
1002 The forward iterator for a split-list has some features:
1003 - it has no post-increment operator
1004 - it depends on iterator of underlying \p OrderedList
1005 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1006 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1007 deleting operations it is no guarantee that you iterate all item in the split-list.
1009 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1010 for debug purpose only.
1012 typedef iterator_type<false> iterator;
1013 /// Const forward iterator
1015 For iterator's features and requirements see \ref iterator
1017 typedef iterator_type<true> const_iterator;
1019 /// Returns a forward iterator addressing the first element in a split-list
1021 For empty list \code begin() == end() \endcode
1025 return iterator( m_List.begin(), m_List.end() );
1028 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1030 Do not use the value returned by <tt>end</tt> function to access any item.
1032 The returned value can be used only to control reaching the end of the split-list.
1033 For empty list \code begin() == end() \endcode
1037 return iterator( m_List.end(), m_List.end() );
1040 /// Returns a forward const iterator addressing the first element in a split-list
1041 const_iterator begin() const
1045 /// Returns a forward const iterator addressing the first element in a split-list
1046 const_iterator cbegin() const
1048 return const_iterator( m_List.cbegin(), m_List.cend() );
1051 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1052 const_iterator end() const
1056 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1057 const_iterator cend() const
1059 return const_iterator( m_List.cend(), m_List.cend() );
1064 }} // namespace cds::intrusive
1066 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H