2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
36 #include <cds/intrusive/details/split_list_base.h>
37 #include <cds/details/binary_functor_wrapper.h>
38 #include <cds/details/type_padding.h>
40 namespace cds { namespace intrusive {
42 /// Split-ordered list RCU specialization
43 /** @ingroup cds_intrusive_map
44 \anchor cds_intrusive_SplitListSet_rcu
46 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
47 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
48 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
50 The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
51 recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
52 without moving an item on resizing, see \ref cds_SplitList_algo_desc "short algo description".
56 Template parameters are:
57 - \p RCU - one of \ref cds_urcu_gc "RCU type"
58 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
59 The intrusive ordered list implementation specifies the type \p T stored in the hash-set,
60 the comparing functor for the type \p T and other features specific for the ordered list.
61 - \p Traits - set traits, default isd \p split_list::traits.
62 Instead of defining \p Traits struct you can use option-based syntax provided by \p split_list::make_traits metafunction.
64 @note About required features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
67 Before including <tt><cds/intrusive/split_list_rcu.h></tt> you should include appropriate RCU header file,
68 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
69 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" and
70 MichaelList-based split-list you should include:
72 #include <cds/urcu/general_buffered.h>
73 #include <cds/intrusive/michael_list_rcu.h>
74 #include <cds/intrusive/split_list_rcu.h>
76 // Declare Michael's list for type Foo and default traits:
77 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
79 // Declare split-list based on rcu_michael_list
80 typedef cds::intrusive::SplitListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, rcu_michael_list > rcu_split_list;
87 # ifdef CDS_DOXYGEN_INVOKED
88 class Traits = split_list::traits
93 class SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
96 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
97 typedef Traits traits; ///< Traits template parameters
99 /// Hash functor for \ref value_type and all its derivatives that you use
100 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
104 typedef split_list::details::rebind_list_traits<OrderedList, traits> ordered_list_adapter;
108 # ifdef CDS_DOXYGEN_INVOKED
109 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
111 typedef typename ordered_list_adapter::result ordered_list;
113 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
114 typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
115 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
116 typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock
117 typedef typename ordered_list::exempt_ptr exempt_ptr; ///< pointer to extracted node
118 typedef typename ordered_list::raw_ptr raw_ptr; ///< pointer to the node for \p get() function
119 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
120 static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
122 typedef typename traits::item_counter item_counter; ///< Item counter type
123 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
124 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
125 typedef typename traits::stat stat; ///< Internal statistics
127 // GC and OrderedList::gc must be the same
128 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
130 // atomicity::empty_item_counter is not allowed as a item counter
131 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
132 "cds::atomicity::empty_item_counter is not allowed as a item counter");
136 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
137 typedef split_list::node<list_node_type> node_type; ///< split-list node type
139 /// Split-list node traits
141 This traits is intended for converting between underlying ordered list node type \ref list_node_type
142 and split-list node type \ref node_type
144 typedef typename ordered_list_adapter::node_traits node_traits;
146 /// Bucket table implementation
147 typedef typename split_list::details::bucket_table_selector<
148 traits::dynamic_bucket_table
150 , typename ordered_list_adapter::aux_node
151 , opt::allocator< typename traits::allocator >
152 , opt::memory_model< memory_model >
153 , opt::free_list< typename traits::free_list >
154 >::type bucket_table;
156 typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
162 /// Ordered list wrapper to access protected members of OrderedList
163 class ordered_list_wrapper: public ordered_list
165 typedef ordered_list base_class;
166 typedef typename base_class::auxiliary_head bucket_head_type;
169 bool insert_at( aux_node_type * pHead, value_type& val )
171 assert( pHead != nullptr );
172 bucket_head_type h(pHead);
173 return base_class::insert_at( h, val );
176 template <typename Func>
177 bool insert_at( aux_node_type * pHead, value_type& val, Func f )
179 assert( pHead != nullptr );
180 bucket_head_type h(pHead);
181 return base_class::insert_at( h, val, f );
184 template <typename Func>
185 std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
187 assert( pHead != nullptr );
188 bucket_head_type h(pHead);
189 return base_class::update_at( h, val, func, bAllowInsert );
192 bool unlink_at( aux_node_type * pHead, value_type& val )
194 assert( pHead != nullptr );
195 bucket_head_type h(pHead);
196 return base_class::unlink_at( h, val );
199 template <typename Q, typename Compare, typename Func>
200 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
202 assert( pHead != nullptr );
203 bucket_head_type h(pHead);
204 return base_class::erase_at( h, val, cmp, f );
207 template <typename Q, typename Compare>
208 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
210 assert( pHead != nullptr );
211 bucket_head_type h(pHead);
212 return base_class::erase_at( h, val, cmp );
215 template <typename Q, typename Compare>
216 value_type * extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
218 assert( pHead != nullptr );
219 bucket_head_type h(pHead);
220 return base_class::extract_at( h, val, cmp );
223 template <typename Q, typename Compare, typename Func>
224 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
226 assert( pHead != nullptr );
227 bucket_head_type h(pHead);
228 return base_class::find_at( h, val, cmp, f );
231 template <typename Q, typename Compare>
232 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
234 assert( pHead != nullptr );
235 bucket_head_type h(pHead);
236 return base_class::find_at( h, val, cmp );
239 template <typename Q, typename Compare>
240 raw_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
242 assert( pHead != nullptr );
243 bucket_head_type h(pHead);
244 return base_class::get_at( h, val, cmp );
247 bool insert_aux_node( aux_node_type * pNode )
249 return base_class::insert_aux_node( pNode );
251 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
253 bucket_head_type h(pHead);
254 return base_class::insert_aux_node( h, pNode );
258 template <typename Less>
259 struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
261 typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
263 template <typename Q1, typename Q2>
264 int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
266 return base_wrapper::operator()( v1.val, v2 );
269 template <typename Q1, typename Q2>
270 int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
272 return base_wrapper::operator()( v1, v2.val );
278 /// Initialize split-ordered list of default capacity
280 The default capacity is defined in bucket table constructor.
281 See split_list::expandable_bucket_table, split_list::static_ducket_table
282 which selects by split_list::dynamic_bucket_table option.
285 : m_nBucketCountLog2(1)
286 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
291 /// Initialize split-ordered list
293 size_t nItemCount ///< estimate average of item count
294 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
296 : m_Buckets( nItemCount, nLoadFactor )
297 , m_nBucketCountLog2(1)
298 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
303 /// Destroys split-list
313 The function inserts \p val in the set if it does not contain
314 an item with key equal to \p val.
316 The function makes RCU lock internally.
318 Returns \p true if \p val is placed into the set, \p false otherwise.
320 bool insert( value_type& val )
322 size_t nHash = hash_value( val );
323 aux_node_type * pHead = get_bucket( nHash );
324 assert( pHead != nullptr );
326 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
328 if ( m_List.insert_at( pHead, val )) {
330 m_Stat.onInsertSuccess();
333 m_Stat.onInsertFailed();
339 This function is intended for derived non-intrusive containers.
341 The function allows to split creating of new item into two part:
342 - create item with key only
343 - insert new item into the set
344 - if inserting is success, calls \p f functor to initialize value-field of \p val.
346 The functor signature is:
348 void func( value_type& val );
350 where \p val is the item inserted.
352 The function makes RCU lock internally.
354 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
355 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
358 template <typename Func>
359 bool insert( value_type& val, Func f )
361 size_t nHash = hash_value( val );
362 aux_node_type * pHead = get_bucket( nHash );
363 assert( pHead != nullptr );
365 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
367 if ( m_List.insert_at( pHead, val, f )) {
369 m_Stat.onInsertSuccess();
372 m_Stat.onInsertFailed();
378 The operation performs inserting or changing data with lock-free manner.
380 If the item \p val is not found in the set, then \p val is inserted
381 iff \p bAllowInsert is \p true.
382 Otherwise, the functor \p func is called with item found.
383 The functor signature is:
385 void func( bool bNew, value_type& item, value_type& val );
388 - \p bNew - \p true if the item has been inserted, \p false otherwise
389 - \p item - item of the set
390 - \p val - argument \p val passed into the \p update() function
391 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
392 refers to the same stuff.
394 The functor may change non-key fields of the \p item.
396 The function applies RCU lock internally.
398 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
399 \p second is \p true if new item has been added or \p false if the item with \p key
400 already is in the list.
402 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
403 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
406 template <typename Func>
407 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
409 size_t nHash = hash_value( val );
410 aux_node_type * pHead = get_bucket( nHash );
411 assert( pHead != nullptr );
413 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
415 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
416 if ( bRet.first && bRet.second ) {
418 m_Stat.onUpdateNew();
421 m_Stat.onUpdateExist();
425 template <typename Func>
426 CDS_DEPRECATED("ensure() is deprecated, use update()")
427 std::pair<bool, bool> ensure( value_type& val, Func func )
429 return update( val, func, true );
433 /// Unlinks the item \p val from the set
435 The function searches the item \p val in the set and unlinks it from the set
436 if it is found and is equal to \p val.
438 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
439 and deletes the item found. \p unlink finds an item by key and deletes it
440 only if \p val is an item of that set, i.e. the pointer to item found
441 is equal to <tt> &val </tt>.
443 RCU \p synchronize method can be called, therefore, RCU should not be locked.
445 The function returns \p true if success and \p false otherwise.
447 bool unlink( value_type& val )
449 size_t nHash = hash_value( val );
450 aux_node_type * pHead = get_bucket( nHash );
451 assert( pHead != nullptr );
453 if ( m_List.unlink_at( pHead, val )) {
455 m_Stat.onEraseSuccess();
458 m_Stat.onEraseFailed();
462 /// Deletes the item from the set
463 /** \anchor cds_intrusive_SplitListSet_rcu_erase
464 The function searches an item with key equal to \p key in the set,
465 unlinks it from the set, and returns \p true.
466 If the item with key equal to \p key is not found the function return \p false.
468 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
469 and deletes the item found. \p unlink finds an item by key and deletes it
470 only if \p key is an item of that set, i.e. the pointer to item found
471 is equal to <tt> &key </tt>.
473 RCU \p synchronize method can be called, therefore, RCU should not be locked.
475 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
477 template <typename Q>
478 bool erase( Q const& key )
480 return erase_( key, key_comparator());
483 /// Deletes the item from the set using \p pred for searching
485 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
486 but \p cmp is used for key compare.
487 \p Less has the interface like \p std::less.
488 \p pred must imply the same element order as the comparator used for building the set.
490 template <typename Q, typename Less>
491 bool erase_with( Q const& key, Less pred )
494 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
497 /// Deletes the item from the set
498 /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
499 The function searches an item with key equal to \p key in the set,
500 call \p f functor with item found, unlinks it from the set, and returns \p true.
501 The \ref disposer specified by \p OrderedList class template parameter is called
502 by garbage collector \p GC asynchronously.
504 The \p Func interface is
507 void operator()( value_type const& item );
511 If the item with key equal to \p key is not found the function return \p false.
513 RCU \p synchronize method can be called, therefore, RCU should not be locked.
515 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
517 template <typename Q, typename Func>
518 bool erase( Q const& key, Func f )
520 return erase_( key, key_comparator(), f );
523 /// Deletes the item from the set using \p pred for searching
525 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
526 but \p cmp is used for key compare.
527 \p Less has the interface like \p std::less.
528 \p pred must imply the same element order as the comparator used for building the set.
530 template <typename Q, typename Less, typename Func>
531 bool erase_with( Q const& key, Less pred, Func f )
534 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
537 /// Extracts an item from the set
538 /** \anchor cds_intrusive_SplitListSet_rcu_extract
539 The function searches an item with key equal to \p key in the set,
540 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
541 If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
543 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
544 - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
545 - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
546 See ordered list implementation for details.
549 typedef cds::urcu::gc< general_buffered<> > rcu;
550 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
551 typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
553 rcu_splitlist_set theSet;
556 rcu_splitlist_set::exempt_ptr p;
558 // For MichaelList we should not lock RCU
560 // Now, you can apply extract function
561 // Note that you must not delete the item found inside the RCU lock
562 p = theList.extract( 10 );
564 // do something with p
568 // We may safely release p here
569 // release() passes the pointer to RCU reclamation cycle:
570 // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
574 template <typename Q>
575 exempt_ptr extract( Q const& key )
577 return exempt_ptr(extract_( key, key_comparator()));
580 /// Extracts an item from the set using \p pred for searching
582 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
583 \p Less functor has the interface like \p std::less.
584 \p pred must imply the same element order as the comparator used for building the set.
586 template <typename Q, typename Less>
587 exempt_ptr extract_with( Q const& key, Less pred )
589 return exempt_ptr( extract_with_( key, pred ));
592 /// Finds the key \p key
593 /** \anchor cds_intrusive_SplitListSet_rcu_find_func
594 The function searches the item with key equal to \p key and calls the functor \p f for item found.
595 The interface of \p Func functor is:
598 void operator()( value_type& item, Q& key );
601 where \p item is the item found, \p key is the <tt>find</tt> function argument.
603 The functor can change non-key fields of \p item. Note that the functor is only guarantee
604 that \p item cannot be disposed during functor is executing.
605 The functor does not serialize simultaneous access to the set \p item. If such access is
606 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
608 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
609 can modify both arguments.
611 Note the hash functor specified for class \p Traits template parameter
612 should accept a parameter of type \p Q that can be not the same as \p value_type.
614 The function applies RCU lock internally.
616 The function returns \p true if \p key is found, \p false otherwise.
618 template <typename Q, typename Func>
619 bool find( Q& key, Func f )
621 return find_( key, key_comparator(), f );
624 template <typename Q, typename Func>
625 bool find( Q const& key, Func f )
627 return find_( key, key_comparator(), f );
631 /// Finds the key \p key with \p pred predicate for comparing
633 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
634 but \p cmp is used for key compare.
635 \p Less has the interface like \p std::less.
636 \p cmp must imply the same element order as the comparator used for building the set.
638 template <typename Q, typename Less, typename Func>
639 bool find_with( Q& key, Less pred, Func f )
642 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
645 template <typename Q, typename Less, typename Func>
646 bool find_with( Q const& key, Less pred, Func f )
649 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
653 /// Checks whether the set contains \p key
655 The function searches the item with key equal to \p key
656 and returns \p true if it is found, and \p false otherwise.
658 Note the hash functor specified for class \p Traits template parameter
659 should accept a parameter of type \p Q that can be not the same as \p value_type.
660 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
662 template <typename Q>
663 bool contains( Q const& key )
665 return find_value( key, key_comparator());
668 template <typename Q>
669 CDS_DEPRECATED("deprecated, use contains()")
670 bool find( Q const& key )
672 return contains( key );
676 /// Checks whether the set contains \p key using \p pred predicate for searching
678 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
679 \p Less functor has the interface like \p std::less.
680 \p Less must imply the same element order as the comparator used for building the list.
682 template <typename Q, typename Less>
683 bool contains( Q const& key, Less pred )
686 return find_value( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
689 template <typename Q, typename Less>
690 CDS_DEPRECATED("deprecated, use contains()")
691 bool find_with( Q const& key, Less pred )
693 return contains( key, pred );
697 /// Finds the key \p key and return the item found
698 /** \anchor cds_intrusive_SplitListSet_rcu_get
699 The function searches the item with key equal to \p key and returns the pointer to item found.
700 If \p key is not found it returns \p nullptr.
702 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
704 RCU should be locked before call of this function.
705 Returned item is valid only while RCU is locked:
707 typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
710 typename set_class::raw_ptr rp;
713 hash_set::rcu_lock lock;
715 rp = theSet.get( 5 );
720 // Unlock RCU by rcu_lock destructor
721 // rp can be retired by disposer at any time after RCU has been unlocked
725 template <typename Q>
726 raw_ptr get( Q const& key )
728 return get_( key, key_comparator());
731 /// Finds the key \p key and return the item found
733 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
734 but \p pred is used for comparing the keys.
736 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
738 \p pred must imply the same element order as the comparator used for building the set.
740 template <typename Q, typename Less>
741 raw_ptr get_with( Q const& key, Less pred )
744 return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
748 /// Returns item count in the set
751 return m_ItemCounter;
754 /// Checks if the set is empty
756 Emptiness is checked by item counting: if item count is zero then the set is empty.
757 Thus, the correct item counting feature is an important part of split-list set implementation.
764 /// Clears the set (not atomic)
767 iterator it = begin();
768 while ( it != end()) {
776 /// Returns internal statistics
777 stat const& statistics() const
782 /// Returns internal statistics for \p OrderedList
783 typename OrderedList::stat const& list_statistics() const
785 return m_List.statistics();
790 template <bool IsConst>
792 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
794 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
795 typedef typename iterator_base_class::list_iterator list_iterator;
798 : iterator_base_class()
801 iterator_type( iterator_type const& src )
802 : iterator_base_class( src )
805 // This ctor should be protected...
806 iterator_type( list_iterator itCur, list_iterator itEnd )
807 : iterator_base_class( itCur, itEnd )
813 ///@name Forward iterators (thread-safe under RCU lock)
817 The forward iterator for a split-list has some features:
818 - it has no post-increment operator
819 - it depends on iterator of underlying \p OrderedList
821 You may safely use iterators in multi-threaded environment only under RCU lock.
822 Otherwise, a crash is possible if another thread deletes the element the iterator points to.
824 typedef iterator_type<false> iterator;
826 /// Const forward iterator
828 For iterator's features and requirements see \ref iterator
830 typedef iterator_type<true> const_iterator;
832 /// Returns a forward iterator addressing the first element in a split-list
834 For empty list \code begin() == end() \endcode
838 return iterator( m_List.begin(), m_List.end());
841 /// Returns an iterator that addresses the location succeeding the last element in a split-list
843 Do not use the value returned by <tt>end</tt> function to access any item.
845 The returned value can be used only to control reaching the end of the split-list.
846 For empty list \code begin() == end() \endcode
850 return iterator( m_List.end(), m_List.end());
853 /// Returns a forward const iterator addressing the first element in a split-list
854 const_iterator begin() const
858 /// Returns a forward const iterator addressing the first element in a split-list
859 const_iterator cbegin() const
861 return const_iterator( m_List.cbegin(), m_List.cend());
864 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
865 const_iterator end() const
869 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
870 const_iterator cend() const
872 return const_iterator( m_List.cend(), m_List.cend());
878 aux_node_type * alloc_aux_node( size_t nHash )
880 m_Stat.onHeadNodeAllocated();
881 aux_node_type* p = m_Buckets.alloc_aux_node();
887 void free_aux_node( aux_node_type * p )
889 m_Buckets.free_aux_node( p );
890 m_Stat.onHeadNodeFreed();
893 /// Calculates hash value of \p key
894 template <typename Q>
895 size_t hash_value( Q const& key ) const
897 return m_HashFunctor( key );
900 size_t bucket_no( size_t nHash ) const
902 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
905 static size_t parent_bucket( size_t nBucket )
907 assert( nBucket > 0 );
908 return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
911 aux_node_type * init_bucket( size_t const nBucket )
913 assert( nBucket > 0 );
914 size_t nParent = parent_bucket( nBucket );
916 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
917 if ( pParentBucket == nullptr ) {
918 pParentBucket = init_bucket( nParent );
919 m_Stat.onRecursiveInitBucket();
922 assert( pParentBucket != nullptr );
924 // Allocate an aux node for new bucket
925 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
928 for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
932 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
934 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
935 m_Buckets.bucket( nBucket, pBucket );
936 m_Stat.onNewBucket();
940 // Another thread set the bucket. Wait while it done
941 free_aux_node( pBucket );
942 m_Stat.onBucketInitContenton();
946 // There are no free buckets. It means that the bucket table is full
947 // Wait while another thread set the bucket or a free bucket will be available
948 m_Stat.onBucketsExhausted();
952 // Another thread set the bucket. Wait while it done
953 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
955 m_Stat.onBusyWaitBucketInit();
961 aux_node_type * get_bucket( size_t nHash )
963 size_t nBucket = bucket_no( nHash );
965 aux_node_type * pHead = m_Buckets.bucket( nBucket );
966 if ( pHead == nullptr )
967 pHead = init_bucket( nBucket );
969 assert( pHead->is_dummy());
976 // Initialize bucket 0
977 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
979 // insert_aux_node cannot return false for empty list
980 CDS_VERIFY( m_List.insert_aux_node( pNode ));
982 m_Buckets.bucket( 0, pNode );
985 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
987 return nBucketCount * nLoadFactor;
990 void inc_item_count()
992 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
993 if ( ++m_ItemCounter <= nMaxCount )
996 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
997 const size_t nBucketCount = static_cast<size_t>(1) << sz;
998 if ( nBucketCount < m_Buckets.capacity()) {
999 // we may grow the bucket table
1000 const size_t nLoadFactor = m_Buckets.load_factor();
1001 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1002 return; // someone already have updated m_nBucketCountLog2, so stop here
1004 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1005 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1006 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1009 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1012 template <typename Q, typename Compare, typename Func>
1013 bool find_( Q& val, Compare cmp, Func f )
1015 size_t nHash = hash_value( val );
1016 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
1017 aux_node_type * pHead = get_bucket( nHash );
1018 assert( pHead != nullptr );
1020 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
1021 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
1024 template <typename Q, typename Compare>
1025 bool find_value( Q const& val, Compare cmp )
1027 size_t nHash = hash_value( val );
1028 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1029 aux_node_type * pHead = get_bucket( nHash );
1030 assert( pHead != nullptr );
1032 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1035 template <typename Q, typename Compare>
1036 raw_ptr get_( Q const& val, Compare cmp )
1038 size_t nHash = hash_value( val );
1039 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1040 aux_node_type * pHead = get_bucket( nHash );
1041 assert( pHead != nullptr );
1043 raw_ptr p = m_List.get_at( pHead, sv, cmp );
1044 m_Stat.onFind( !!p );
1048 template <typename Q, typename Compare>
1049 value_type * extract_( Q const& val, Compare cmp )
1051 size_t nHash = hash_value( val );
1052 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1053 aux_node_type * pHead = get_bucket( nHash );
1054 assert( pHead != nullptr );
1056 value_type * pNode = m_List.extract_at( pHead, sv, cmp );
1059 m_Stat.onExtractSuccess();
1062 m_Stat.onExtractFailed();
1066 template <typename Q, typename Less>
1067 value_type * extract_with_( Q const& val, Less pred )
1070 return extract_( val, typename ordered_list_adapter::template make_compare_from_less<Less>());
1073 template <typename Q, typename Compare>
1074 bool erase_( const Q& val, Compare cmp )
1076 size_t nHash = hash_value( val );
1077 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1078 aux_node_type * pHead = get_bucket( nHash );
1079 assert( pHead != nullptr );
1081 if ( m_List.erase_at( pHead, sv, cmp )) {
1083 m_Stat.onEraseSuccess();
1086 m_Stat.onEraseFailed();
1090 template <typename Q, typename Compare, typename Func>
1091 bool erase_( Q const& val, Compare cmp, Func f )
1093 size_t nHash = hash_value( val );
1094 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1095 aux_node_type * pHead = get_bucket( nHash );
1096 assert( pHead != nullptr );
1098 if ( m_List.erase_at( pHead, sv, cmp, f )) {
1100 m_Stat.onEraseSuccess();
1103 m_Stat.onEraseFailed();
1110 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1112 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1113 padded_bucket_table m_Buckets; ///< bucket table
1115 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1116 padded_ordered_list m_List; ///< Ordered list containing split-list items
1118 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1119 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
1120 item_counter m_ItemCounter; ///< Item counter
1121 hash m_HashFunctor; ///< Hash functor
1122 stat m_Stat; ///< Internal statistics accumulator
1126 }} // namespace cds::intrusive
1128 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H