3 #ifndef __CDS_INTRUSIVE_SPLIT_LIST_RCU_H
4 #define __CDS_INTRUSIVE_SPLIT_LIST_RCU_H
6 #include <cds/intrusive/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 - type traits. See split_list::type_traits for explanation.
31 Instead of defining \p Traits struct you may use option-based syntax with split_list::make_traits metafunction.
33 @note About features of hash functor needed for \p %SplitList 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::type_traits
62 class SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
65 typedef Traits options ; ///< Traits template parameters
66 typedef cds::urcu::gc< RCU > gc ; ///< RCU garbage collector
68 /// Hash functor for \ref value_type and all its derivatives that you use
69 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
73 typedef split_list::details::rebind_list_options<OrderedList, options> wrapped_ordered_list;
77 # ifdef CDS_DOXYGEN_INVOKED
78 typedef OrderedList ordered_list ; ///< type of ordered list used as base for split-list
80 typedef typename wrapped_ordered_list::result ordered_list;
82 typedef typename ordered_list::value_type value_type ; ///< type of value stored in the split-list
83 typedef typename ordered_list::key_comparator key_comparator ; ///< key compare functor
84 typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
85 typedef typename ordered_list::rcu_lock rcu_lock ; ///< RCU scoped lock
86 typedef typename ordered_list::exempt_ptr exempt_ptr ; ///< pointer to extracted node
87 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
88 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
90 typedef typename options::item_counter item_counter ; ///< Item counter type
91 typedef typename options::back_off back_off ; ///< back-off strategy for spinning
92 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
95 typedef typename ordered_list::node_type list_node_type ; ///< Node type as declared in ordered list
96 typedef split_list::node<list_node_type> node_type ; ///< split-list node type
97 typedef node_type dummy_node_type ; ///< dummy node type
99 /// Split-list node traits
101 This traits is intended for converting between underlying ordered list node type \ref list_node_type
102 and split-list node type \ref node_type
104 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
107 /// Bucket table implementation
108 typedef typename split_list::details::bucket_table_selector<
109 options::dynamic_bucket_table
112 , opt::allocator< typename options::allocator >
113 , opt::memory_model< memory_model >
114 >::type bucket_table;
120 /// Ordered list wrapper to access protected members of OrderedList
121 class ordered_list_wrapper: public ordered_list
123 typedef ordered_list base_class;
124 typedef typename base_class::auxiliary_head bucket_head_type;
127 bool insert_at( dummy_node_type * pHead, value_type& val )
129 assert( pHead != nullptr );
130 bucket_head_type h(pHead);
131 return base_class::insert_at( h, val );
134 template <typename Func>
135 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
137 assert( pHead != nullptr );
138 bucket_head_type h(pHead);
139 return base_class::insert_at( h, val, f );
142 template <typename Func>
143 std::pair<bool, bool> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
145 assert( pHead != nullptr );
146 bucket_head_type h(pHead);
147 return base_class::ensure_at( h, val, func );
150 bool unlink_at( dummy_node_type * pHead, value_type& val )
152 assert( pHead != nullptr );
153 bucket_head_type h(pHead);
154 return base_class::unlink_at( h, val );
157 template <typename Q, typename Compare, typename Func>
158 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
160 assert( pHead != nullptr );
161 bucket_head_type h(pHead);
162 return base_class::erase_at( h, val, cmp, f );
165 template <typename Q, typename Compare>
166 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
168 assert( pHead != nullptr );
169 bucket_head_type h(pHead);
170 return base_class::erase_at( h, val, cmp );
173 template <typename Q, typename Compare>
174 value_type * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
176 assert( pHead != nullptr );
177 bucket_head_type h(pHead);
178 return base_class::extract_at( h, val, cmp );
181 template <typename Q, typename Compare, typename Func>
182 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f ) const
184 assert( pHead != nullptr );
185 bucket_head_type h(pHead);
186 return base_class::find_at( h, val, cmp, f );
189 template <typename Q, typename Compare>
190 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp ) const
192 assert( pHead != nullptr );
193 bucket_head_type h(pHead);
194 return base_class::find_at( h, val, cmp );
197 template <typename Q, typename Compare>
198 value_type * get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp ) const
200 assert( pHead != nullptr );
201 bucket_head_type h(pHead);
202 return base_class::get_at( h, val, cmp );
205 bool insert_aux_node( dummy_node_type * pNode )
207 return base_class::insert_aux_node( pNode );
209 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
211 bucket_head_type h(pHead);
212 return base_class::insert_aux_node( h, pNode );
216 template <typename Less>
217 struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
219 typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
221 template <typename Q1, typename Q2>
222 int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
224 return base_wrapper::operator()( v1.val, v2 );
227 template <typename Q1, typename Q2>
228 int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
230 return base_wrapper::operator()( v1, v2.val );
236 ordered_list_wrapper m_List ; ///< Ordered list containing split-list items
237 bucket_table m_Buckets ; ///< bucket table
238 CDS_ATOMIC::atomic<size_t> m_nBucketCountLog2 ; ///< log2( current bucket count )
239 item_counter m_ItemCounter ; ///< Item counter
240 hash m_HashFunctor ; ///< Hash functor
244 typedef cds::details::Allocator< dummy_node_type, typename options::allocator > dummy_node_allocator;
245 static dummy_node_type * alloc_dummy_node( size_t nHash )
247 return dummy_node_allocator().New( nHash );
249 static void free_dummy_node( dummy_node_type * p )
251 dummy_node_allocator().Delete( p );
254 /// Calculates hash value of \p key
255 template <typename Q>
256 size_t hash_value( Q const& key ) const
258 return m_HashFunctor( key );
261 size_t bucket_no( size_t nHash ) const
263 return nHash & ( (1 << m_nBucketCountLog2.load(CDS_ATOMIC::memory_order_relaxed)) - 1 );
266 static size_t parent_bucket( size_t nBucket )
268 assert( nBucket > 0 );
269 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
272 dummy_node_type * init_bucket( size_t nBucket )
274 assert( nBucket > 0 );
275 size_t nParent = parent_bucket( nBucket );
277 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
278 if ( pParentBucket == nullptr ) {
279 pParentBucket = init_bucket( nParent );
282 assert( pParentBucket != nullptr );
284 // Allocate a dummy node for new bucket
286 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
287 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
288 m_Buckets.bucket( nBucket, pBucket );
291 free_dummy_node( pBucket );
294 // Another thread set the bucket. Wait while it done
296 // In this point, we must wait while nBucket is empty.
297 // The compiler can decide that waiting loop can be "optimized" (stripped)
298 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
302 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
304 return const_cast<dummy_node_type *>( p );
309 dummy_node_type * get_bucket( size_t nHash )
311 size_t nBucket = bucket_no( nHash );
313 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
314 if ( pHead == nullptr )
315 pHead = init_bucket( nBucket );
317 assert( pHead->is_dummy() );
324 // GC and OrderedList::gc must be the same
325 static_assert(( std::is_same<gc, typename ordered_list::gc>::value ), "GC and OrderedList::gc must be the same");
327 // atomicity::empty_item_counter is not allowed as a item counter
328 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
330 // Initialize bucket 0
331 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
333 // insert_aux_node cannot return false for empty list
334 CDS_VERIFY( m_List.insert_aux_node( pNode ));
336 m_Buckets.bucket( 0, pNode );
339 void inc_item_count()
341 size_t sz = m_nBucketCountLog2.load(CDS_ATOMIC::memory_order_relaxed);
342 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
344 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, CDS_ATOMIC::memory_order_seq_cst, CDS_ATOMIC::memory_order_relaxed );
348 template <typename Q, typename Compare, typename Func>
349 bool find_( Q& val, Compare cmp, Func f )
351 size_t nHash = hash_value( val );
352 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
353 dummy_node_type * pHead = get_bucket( nHash );
354 assert( pHead != nullptr );
356 # ifdef CDS_CXX11_LAMBDA_SUPPORT
357 return m_List.find_at( pHead, sv, cmp,
358 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ cds::unref(f)(item, val.val ); });
360 split_list::details::find_functor_wrapper<Func> ffw( f );
361 return m_List.find_at( pHead, sv, cmp, cds::ref(ffw) );
365 template <typename Q, typename Compare>
366 bool find_value( Q const& val, Compare cmp )
368 size_t nHash = hash_value( val );
369 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
370 dummy_node_type * pHead = get_bucket( nHash );
371 assert( pHead != nullptr );
373 return m_List.find_at( pHead, sv, cmp );
376 template <typename Q, typename Compare>
377 value_type * get_( Q const& val, Compare cmp )
379 size_t nHash = hash_value( val );
380 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
381 dummy_node_type * pHead = get_bucket( nHash );
382 assert( pHead != nullptr );
384 return m_List.get_at( pHead, sv, cmp );
387 template <typename Q, typename Compare>
388 value_type * extract_( Q const& val, Compare cmp )
390 size_t nHash = hash_value( val );
391 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
392 dummy_node_type * pHead = get_bucket( nHash );
393 assert( pHead != nullptr );
395 value_type * pNode = m_List.extract_at( pHead, sv, cmp );
401 template <typename Q, typename Less>
402 value_type * extract_with_( Q const& val, Less pred )
404 return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
407 template <typename Q, typename Compare>
408 bool erase_( const Q& val, Compare cmp )
410 size_t nHash = hash_value( val );
411 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
412 dummy_node_type * pHead = get_bucket( nHash );
413 assert( pHead != nullptr );
415 if ( m_List.erase_at( pHead, sv, cmp ) ) {
422 template <typename Q, typename Compare, typename Func>
423 bool erase_( Q const& val, Compare cmp, Func f )
425 size_t nHash = hash_value( val );
426 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
427 dummy_node_type * pHead = get_bucket( nHash );
428 assert( pHead != nullptr );
430 if ( m_List.erase_at( pHead, sv, cmp, f )) {
440 /// Initialize split-ordered list of default capacity
442 The default capacity is defined in bucket table constructor.
443 See split_list::expandable_bucket_table, split_list::static_ducket_table
444 which selects by split_list::dynamic_bucket_table option.
447 : m_nBucketCountLog2(1)
452 /// Initialize split-ordered list
454 size_t nItemCount ///< estimate average of item count
455 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
457 : m_Buckets( nItemCount, nLoadFactor )
458 , m_nBucketCountLog2(1)
466 The function inserts \p val in the set if it does not contain
467 an item with key equal to \p val.
469 The function makes RCU lock internally.
471 Returns \p true if \p val is placed into the set, \p false otherwise.
473 bool insert( value_type& val )
475 size_t nHash = hash_value( val );
476 dummy_node_type * pHead = get_bucket( nHash );
477 assert( pHead != nullptr );
479 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
481 if ( m_List.insert_at( pHead, val )) {
490 This function is intended for derived non-intrusive containers.
492 The function allows to split creating of new item into two part:
493 - create item with key only
494 - insert new item into the set
495 - if inserting is success, calls \p f functor to initialize value-field of \p val.
497 The functor signature is:
499 void func( value_type& val );
501 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
502 \p val no any other changes could be made on this set's item by concurrent threads.
503 The user-defined functor is called only if the inserting is success and may be passed by reference
504 using <tt>boost::ref</tt>
506 The function makes RCU lock internally.
508 template <typename Func>
509 bool insert( value_type& val, Func f )
511 size_t nHash = hash_value( val );
512 dummy_node_type * pHead = get_bucket( nHash );
513 assert( pHead != nullptr );
515 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
517 if ( m_List.insert_at( pHead, val, f )) {
524 /// Ensures that the \p val exists in the set
526 The operation performs inserting or changing data with lock-free manner.
528 If the item \p val is not found in the set, then \p val is inserted into the set.
529 Otherwise, the functor \p func is called with item found.
530 The functor signature is:
532 void func( bool bNew, value_type& item, value_type& val );
535 - \p bNew - \p true if the item has been inserted, \p false otherwise
536 - \p item - item of the set
537 - \p val - argument \p val passed into the \p ensure function
538 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
539 refers to the same thing.
541 The functor can change non-key fields of the \p item; however, \p func must guarantee
542 that during changing no any other modifications could be made on this item by concurrent threads.
544 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
546 The function makes RCU lock internally.
548 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
549 \p second is \p true if new item has been added or \p false if the item with \p key
550 already is in the set.
552 template <typename Func>
553 std::pair<bool, bool> ensure( value_type& val, Func func )
555 size_t nHash = hash_value( val );
556 dummy_node_type * pHead = get_bucket( nHash );
557 assert( pHead != nullptr );
559 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
561 std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
562 if ( bRet.first && bRet.second )
567 /// Unlinks the item \p val from the set
569 The function searches the item \p val in the set and unlinks it from the set
570 if it is found and is equal to \p val.
572 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
573 and deletes the item found. \p unlink finds an item by key and deletes it
574 only if \p val is an item of that set, i.e. the pointer to item found
575 is equal to <tt> &val </tt>.
577 RCU \p synchronize method can be called, therefore, RCU should not be locked.
579 The function returns \p true if success and \p false otherwise.
581 bool unlink( value_type& val )
583 size_t nHash = hash_value( val );
584 dummy_node_type * pHead = get_bucket( nHash );
585 assert( pHead != nullptr );
587 if ( m_List.unlink_at( pHead, val ) ) {
594 /// Deletes the item from the set
595 /** \anchor cds_intrusive_SplitListSet_rcu_erase
596 The function searches an item with key equal to \p val in the set,
597 unlinks it from the set, and returns \p true.
598 If the item with key equal to \p val is not found the function return \p false.
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 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
609 template <typename Q>
610 bool erase( Q const& val )
612 return erase_( val, key_comparator() );
615 /// Deletes the item from the set using \p pred for searching
617 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
618 but \p cmp is used for key compare.
619 \p Less has the interface like \p std::less.
620 \p pred must imply the same element order as the comparator used for building the set.
622 template <typename Q, typename Less>
623 bool erase_with( Q const& val, Less pred )
625 return erase_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
628 /// Deletes the item from the set
629 /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
630 The function searches an item with key equal to \p val in the set,
631 call \p f functor with item found, unlinks it from the set, and returns \p true.
632 The \ref disposer specified by \p OrderedList class template parameter is called
633 by garbage collector \p GC asynchronously.
635 The \p Func interface is
638 void operator()( value_type const& item );
641 The functor can be passed by reference with <tt>boost:ref</tt>
643 If the item with key equal to \p val is not found the function return \p false.
645 RCU \p synchronize method can be called, therefore, RCU should not be locked.
647 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
649 template <typename Q, typename Func>
650 bool erase( Q const& val, Func f )
652 return erase_( val, key_comparator(), f );
655 /// Deletes the item from the set using \p pred for searching
657 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
658 but \p cmp is used for key compare.
659 \p Less has the interface like \p std::less.
660 \p pred must imply the same element order as the comparator used for building the set.
662 template <typename Q, typename Less, typename Func>
663 bool erase_with( Q const& val, Less pred, Func f )
665 return erase_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
668 /// Extracts an item from the set
669 /** \anchor cds_intrusive_SplitListSet_rcu_extract
670 The function searches an item with key equal to \p val in the set,
671 unlinks it, and returns pointer to an item found in \p dest argument.
672 If the item with the key equal to \p val is not found the function returns \p false.
674 @note The function does NOT call RCU read-side lock or synchronization,
675 and does NOT dispose the item found. It just excludes the item from the set
676 and returns a pointer to item found.
677 You should lock RCU before calling of the function, and you should synchronize RCU
678 outside the RCU lock before reusing returned pointer.
681 typedef cds::urcu::gc< general_buffered<> > rcu;
682 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
683 typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
685 rcu_splitlist_set theSet;
688 rcu_splitlist_set::exempt_ptr p;
690 // first, we should lock RCU
691 rcu_splitlist_set::rcu_lock lock;
693 // Now, you can apply extract function
694 // Note that you must not delete the item found inside the RCU lock
695 if ( theList.extract( p, 10 )) {
696 // do something with p
701 // We may safely release p here
702 // release() passes the pointer to RCU reclamation cycle:
703 // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
707 template <typename Q>
708 bool extract( exempt_ptr& dest, Q const& val )
710 value_type * pNode = extract_( val, key_comparator() );
718 /// Extracts an item from the set using \p pred for searching
720 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
721 but \p pred is used for key compare.
722 \p Less functor has the interface like \p std::less.
723 \p pred must imply the same element order as the comparator used for building the set.
725 template <typename Q, typename Less>
726 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
728 value_type * pNode = extract_with_( val, pred );
736 /// Finds the key \p val
737 /** \anchor cds_intrusive_SplitListSet_rcu_find_func
738 The function searches the item with key equal to \p val and calls the functor \p f for item found.
739 The interface of \p Func functor is:
742 void operator()( value_type& item, Q& val );
745 where \p item is the item found, \p val is the <tt>find</tt> function argument.
747 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
749 The functor can change non-key fields of \p item. Note that the functor is only guarantee
750 that \p item cannot be disposed during functor is executing.
751 The functor does not serialize simultaneous access to the set \p item. If such access is
752 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
754 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
755 can modify both arguments.
757 Note the hash functor specified for class \p Traits template parameter
758 should accept a parameter of type \p Q that can be not the same as \p value_type.
760 The function applies RCU lock internally.
762 The function returns \p true if \p val is found, \p false otherwise.
764 template <typename Q, typename Func>
765 bool find( Q& val, Func f )
767 return find_( val, key_comparator(), f );
770 /// Finds the key \p val with \p pred predicate for comparing
772 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
773 but \p cmp is used for key compare.
774 \p Less has the interface like \p std::less.
775 \p cmp must imply the same element order as the comparator used for building the set.
777 template <typename Q, typename Less, typename Func>
778 bool find_with( Q& val, Less pred, Func f )
780 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
783 /// Finds the key \p val
784 /** \anchor cds_intrusive_SplitListSet_rcu_find_cfunc
785 The function searches the item with key equal to \p val and calls the functor \p f for item found.
786 The interface of \p Func functor is:
789 void operator()( value_type& item, Q const& val );
792 where \p item is the item found, \p val is the <tt>find</tt> function argument.
794 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
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 Note the hash functor specified for class \p Traits template parameter
802 should accept a parameter of type \p Q that can be not the same as \p value_type.
804 The function applies RCU lock internally.
806 The function returns \p true if \p val is found, \p false otherwise.
808 template <typename Q, typename Func>
809 bool find( Q const& val, Func f )
811 return find_( val, key_comparator(), f );
814 /// Finds the key \p val with \p pred predicate for comparing
816 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_cfunc "find(Q const&, Func)"
817 but \p cmp is used for key compare.
818 \p Less has the interface like \p std::less.
819 \p pred must imply the same element order as the comparator used for building the set.
821 template <typename Q, typename Less, typename Func>
822 bool find_with( Q const& val, Less pred, Func f )
824 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
827 /// Finds the key \p val
828 /** \anchor cds_intrusive_SplitListSet_rcu_find_val
829 The function searches the item with key equal to \p val
830 and returns \p true if \p val found or \p false otherwise.
832 template <typename Q>
833 bool find( Q const& val )
835 return find_value( val, key_comparator() );
838 /// Finds the key \p val with \p pred predicate for comparing
840 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_val "find(Q const&)"
841 but \p cmp is used for key compare.
842 \p Less has the interface like \p std::less.
843 \p pred must imply the same element order as the comparator used for building the set.
845 template <typename Q, typename Less>
846 bool find_with( Q const& val, Less pred )
848 return find_value( val, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
851 /// Finds the key \p val and return the item found
852 /** \anchor cds_intrusive_SplitListSet_rcu_get
853 The function searches the item with key equal to \p val and returns the pointer to item found.
854 If \p val is not found it returns \p NULL.
856 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
858 RCU should be locked before call of this function.
859 Returned item is valid only while RCU is locked:
861 cds::intrusive::SplitListSet< your_template_parameters > theSet;
865 hash_set::rcu_lock lock;
867 foo * pVal = theSet.get( 5 );
872 // Unlock RCU by rcu_lock destructor
873 // pVal can be retired by disposer at any time after RCU has been unlocked
877 template <typename Q>
878 value_type * get( Q const& val )
880 return get_( val, key_comparator() );
883 /// Finds the key \p val and return the item found
885 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
886 but \p pred is used for comparing the keys.
888 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
890 \p pred must imply the same element order as the comparator used for building the set.
892 template <typename Q, typename Less>
893 value_type * get_with( Q const& val, Less pred )
895 return get_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
899 /// Returns item count in the set
902 return m_ItemCounter;
905 /// Checks if the set is empty
907 Emptiness is checked by item counting: if item count is zero then the set is empty.
908 Thus, the correct item counting feature is an important part of split-list set implementation.
915 /// Clears the set (non-atomic)
917 The function unlink all items from the set.
918 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
922 iterator it = begin();
923 while ( it != end() ) {
933 template <bool IsConst>
935 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
937 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
938 typedef typename iterator_base_class::list_iterator list_iterator;
941 : iterator_base_class()
944 iterator_type( iterator_type const& src )
945 : iterator_base_class( src )
948 // This ctor should be protected...
949 iterator_type( list_iterator itCur, list_iterator itEnd )
950 : iterator_base_class( itCur, itEnd )
957 The forward iterator for a split-list has some features:
958 - it has no post-increment operator
959 - it depends on iterator of underlying \p OrderedList
960 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
961 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
962 deleting operations it is no guarantee that you iterate all item in the split-list.
964 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
965 for debug purpose only.
967 typedef iterator_type<false> iterator;
968 /// Const forward iterator
970 For iterator's features and requirements see \ref iterator
972 typedef iterator_type<true> const_iterator;
974 /// Returns a forward iterator addressing the first element in a split-list
976 For empty list \code begin() == end() \endcode
980 return iterator( m_List.begin(), m_List.end() );
983 /// Returns an iterator that addresses the location succeeding the last element in a split-list
985 Do not use the value returned by <tt>end</tt> function to access any item.
987 The returned value can be used only to control reaching the end of the split-list.
988 For empty list \code begin() == end() \endcode
992 return iterator( m_List.end(), m_List.end() );
995 /// Returns a forward const iterator addressing the first element in a split-list
996 const_iterator begin() const
998 return const_iterator( m_List.begin(), m_List.end() );
1001 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1002 const_iterator end() const
1004 return const_iterator( m_List.end(), m_List.end() );
1009 }} // namespace cds::intrusive
1011 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_RCU_H