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::bit_reversal bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal
123 typedef typename traits::item_counter item_counter; ///< Item counter type
124 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
125 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
126 typedef typename traits::stat stat; ///< Internal statistics
128 // GC and OrderedList::gc must be the same
129 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
131 // atomicity::empty_item_counter is not allowed as a item counter
132 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
133 "cds::atomicity::empty_item_counter is not allowed as a item counter");
137 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
138 typedef split_list::node<list_node_type> node_type; ///< split-list node type
140 /// Split-list node traits
142 This traits is intended for converting between underlying ordered list node type \ref list_node_type
143 and split-list node type \ref node_type
145 typedef typename ordered_list_adapter::node_traits node_traits;
147 /// Bucket table implementation
148 typedef typename split_list::details::bucket_table_selector<
149 traits::dynamic_bucket_table
151 , typename ordered_list_adapter::aux_node
152 , opt::allocator< typename traits::allocator >
153 , opt::memory_model< memory_model >
154 , opt::free_list< typename traits::free_list >
155 >::type bucket_table;
157 typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
163 /// Ordered list wrapper to access protected members of OrderedList
164 class ordered_list_wrapper: public ordered_list
166 typedef ordered_list base_class;
167 typedef typename base_class::auxiliary_head bucket_head_type;
170 bool insert_at( aux_node_type * pHead, value_type& val )
172 assert( pHead != nullptr );
173 bucket_head_type h(pHead);
174 return base_class::insert_at( h, val );
177 template <typename Func>
178 bool insert_at( aux_node_type * pHead, value_type& val, Func f )
180 assert( pHead != nullptr );
181 bucket_head_type h(pHead);
182 return base_class::insert_at( h, val, f );
185 template <typename Func>
186 std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
188 assert( pHead != nullptr );
189 bucket_head_type h(pHead);
190 return base_class::update_at( h, val, func, bAllowInsert );
193 bool unlink_at( aux_node_type * pHead, value_type& val )
195 assert( pHead != nullptr );
196 bucket_head_type h(pHead);
197 return base_class::unlink_at( h, val );
200 template <typename Q, typename Compare, typename Func>
201 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
203 assert( pHead != nullptr );
204 bucket_head_type h(pHead);
205 return base_class::erase_at( h, val, cmp, f );
208 template <typename Q, typename Compare>
209 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
211 assert( pHead != nullptr );
212 bucket_head_type h(pHead);
213 return base_class::erase_at( h, val, cmp );
216 template <typename Q, typename Compare>
217 value_type * extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
219 assert( pHead != nullptr );
220 bucket_head_type h(pHead);
221 return base_class::extract_at( h, val, cmp );
224 template <typename Q, typename Compare, typename Func>
225 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
227 assert( pHead != nullptr );
228 bucket_head_type h(pHead);
229 return base_class::find_at( h, val, cmp, f );
232 template <typename Q, typename Compare>
233 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
235 assert( pHead != nullptr );
236 bucket_head_type h(pHead);
237 return base_class::find_at( h, val, cmp );
240 template <typename Q, typename Compare>
241 raw_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
243 assert( pHead != nullptr );
244 bucket_head_type h(pHead);
245 return base_class::get_at( h, val, cmp );
248 bool insert_aux_node( aux_node_type * pNode )
250 return base_class::insert_aux_node( pNode );
252 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
254 bucket_head_type h(pHead);
255 return base_class::insert_aux_node( h, pNode );
259 template <typename Less>
260 struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
262 typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
264 template <typename Q1, typename Q2>
265 int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
267 return base_wrapper::operator()( v1.val, v2 );
270 template <typename Q1, typename Q2>
271 int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
273 return base_wrapper::operator()( v1, v2.val );
279 /// Initialize split-ordered list of default capacity
281 The default capacity is defined in bucket table constructor.
282 See split_list::expandable_bucket_table, split_list::static_ducket_table
283 which selects by split_list::dynamic_bucket_table option.
286 : m_nBucketCountLog2(1)
287 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
292 /// Initialize split-ordered list
294 size_t nItemCount ///< estimate average of item count
295 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
297 : m_Buckets( nItemCount, nLoadFactor )
298 , m_nBucketCountLog2(1)
299 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
304 /// Destroys split-list
314 The function inserts \p val in the set if it does not contain
315 an item with key equal to \p val.
317 The function makes RCU lock internally.
319 Returns \p true if \p val is placed into the set, \p false otherwise.
321 bool insert( value_type& val )
323 size_t nHash = hash_value( val );
324 aux_node_type * pHead = get_bucket( nHash );
325 assert( pHead != nullptr );
327 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
329 if ( m_List.insert_at( pHead, val )) {
331 m_Stat.onInsertSuccess();
334 m_Stat.onInsertFailed();
340 This function is intended for derived non-intrusive containers.
342 The function allows to split creating of new item into two part:
343 - create item with key only
344 - insert new item into the set
345 - if inserting is success, calls \p f functor to initialize value-field of \p val.
347 The functor signature is:
349 void func( value_type& val );
351 where \p val is the item inserted.
353 The function makes RCU lock internally.
355 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
356 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
359 template <typename Func>
360 bool insert( value_type& val, Func f )
362 size_t nHash = hash_value( val );
363 aux_node_type * pHead = get_bucket( nHash );
364 assert( pHead != nullptr );
366 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
368 if ( m_List.insert_at( pHead, val, f )) {
370 m_Stat.onInsertSuccess();
373 m_Stat.onInsertFailed();
379 The operation performs inserting or changing data with lock-free manner.
381 If the item \p val is not found in the set, then \p val is inserted
382 iff \p bAllowInsert is \p true.
383 Otherwise, the functor \p func is called with item found.
384 The functor signature is:
386 void func( bool bNew, value_type& item, value_type& val );
389 - \p bNew - \p true if the item has been inserted, \p false otherwise
390 - \p item - item of the set
391 - \p val - argument \p val passed into the \p update() function
392 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
393 refers to the same stuff.
395 The functor may change non-key fields of the \p item.
397 The function applies RCU lock internally.
399 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
400 \p second is \p true if new item has been added or \p false if the item with \p key
401 already is in the list.
403 @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
404 \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
407 template <typename Func>
408 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
410 size_t nHash = hash_value( val );
411 aux_node_type * pHead = get_bucket( nHash );
412 assert( pHead != nullptr );
414 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
416 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
417 if ( bRet.first && bRet.second ) {
419 m_Stat.onUpdateNew();
422 m_Stat.onUpdateExist();
426 template <typename Func>
427 CDS_DEPRECATED("ensure() is deprecated, use update()")
428 std::pair<bool, bool> ensure( value_type& val, Func func )
430 return update( val, func, true );
434 /// Unlinks the item \p val from the set
436 The function searches the item \p val in the set and unlinks it from the set
437 if it is found and is equal to \p val.
439 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
440 and deletes the item found. \p unlink finds an item by key and deletes it
441 only if \p val is an item of that set, i.e. the pointer to item found
442 is equal to <tt> &val </tt>.
444 RCU \p synchronize method can be called, therefore, RCU should not be locked.
446 The function returns \p true if success and \p false otherwise.
448 bool unlink( value_type& val )
450 size_t nHash = hash_value( val );
451 aux_node_type * pHead = get_bucket( nHash );
452 assert( pHead != nullptr );
454 if ( m_List.unlink_at( pHead, val )) {
456 m_Stat.onEraseSuccess();
459 m_Stat.onEraseFailed();
463 /// Deletes the item from the set
464 /** \anchor cds_intrusive_SplitListSet_rcu_erase
465 The function searches an item with key equal to \p key in the set,
466 unlinks it from the set, and returns \p true.
467 If the item with key equal to \p key is not found the function return \p false.
469 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
470 and deletes the item found. \p unlink finds an item by key and deletes it
471 only if \p key is an item of that set, i.e. the pointer to item found
472 is equal to <tt> &key </tt>.
474 RCU \p synchronize method can be called, therefore, RCU should not be locked.
476 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
478 template <typename Q>
479 bool erase( Q const& key )
481 return erase_( key, key_comparator());
484 /// Deletes the item from the set using \p pred for searching
486 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
487 but \p cmp is used for key compare.
488 \p Less has the interface like \p std::less.
489 \p pred must imply the same element order as the comparator used for building the set.
491 template <typename Q, typename Less>
492 bool erase_with( Q const& key, Less pred )
495 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
498 /// Deletes the item from the set
499 /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
500 The function searches an item with key equal to \p key in the set,
501 call \p f functor with item found, unlinks it from the set, and returns \p true.
502 The \ref disposer specified by \p OrderedList class template parameter is called
503 by garbage collector \p GC asynchronously.
505 The \p Func interface is
508 void operator()( value_type const& item );
512 If the item with key equal to \p key is not found the function return \p false.
514 RCU \p synchronize method can be called, therefore, RCU should not be locked.
516 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
518 template <typename Q, typename Func>
519 bool erase( Q const& key, Func f )
521 return erase_( key, key_comparator(), f );
524 /// Deletes the item from the set using \p pred for searching
526 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
527 but \p cmp is used for key compare.
528 \p Less has the interface like \p std::less.
529 \p pred must imply the same element order as the comparator used for building the set.
531 template <typename Q, typename Less, typename Func>
532 bool erase_with( Q const& key, Less pred, Func f )
535 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
538 /// Extracts an item from the set
539 /** \anchor cds_intrusive_SplitListSet_rcu_extract
540 The function searches an item with key equal to \p key in the set,
541 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
542 If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
544 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
545 - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
546 - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
547 See ordered list implementation for details.
550 typedef cds::urcu::gc< general_buffered<> > rcu;
551 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
552 typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
554 rcu_splitlist_set theSet;
557 rcu_splitlist_set::exempt_ptr p;
559 // For MichaelList we should not lock RCU
561 // Now, you can apply extract function
562 // Note that you must not delete the item found inside the RCU lock
563 p = theList.extract( 10 );
565 // do something with p
569 // We may safely release p here
570 // release() passes the pointer to RCU reclamation cycle:
571 // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
575 template <typename Q>
576 exempt_ptr extract( Q const& key )
578 return exempt_ptr(extract_( key, key_comparator()));
581 /// Extracts an item from the set using \p pred for searching
583 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
584 \p Less functor has the interface like \p std::less.
585 \p pred must imply the same element order as the comparator used for building the set.
587 template <typename Q, typename Less>
588 exempt_ptr extract_with( Q const& key, Less pred )
590 return exempt_ptr( extract_with_( key, pred ));
593 /// Finds the key \p key
594 /** \anchor cds_intrusive_SplitListSet_rcu_find_func
595 The function searches the item with key equal to \p key and calls the functor \p f for item found.
596 The interface of \p Func functor is:
599 void operator()( value_type& item, Q& key );
602 where \p item is the item found, \p key is the <tt>find</tt> function argument.
604 The functor can change non-key fields of \p item. Note that the functor is only guarantee
605 that \p item cannot be disposed during functor is executing.
606 The functor does not serialize simultaneous access to the set \p item. If such access is
607 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
609 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
610 can modify both arguments.
612 Note the hash functor specified for class \p Traits template parameter
613 should accept a parameter of type \p Q that can be not the same as \p value_type.
615 The function applies RCU lock internally.
617 The function returns \p true if \p key is found, \p false otherwise.
619 template <typename Q, typename Func>
620 bool find( Q& key, Func f )
622 return find_( key, key_comparator(), f );
625 template <typename Q, typename Func>
626 bool find( Q const& key, Func f )
628 return find_( key, key_comparator(), f );
632 /// Finds the key \p key with \p pred predicate for comparing
634 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
635 but \p cmp is used for key compare.
636 \p Less has the interface like \p std::less.
637 \p cmp must imply the same element order as the comparator used for building the set.
639 template <typename Q, typename Less, typename Func>
640 bool find_with( Q& key, Less pred, Func f )
643 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
646 template <typename Q, typename Less, typename Func>
647 bool find_with( Q const& key, Less pred, Func f )
650 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
654 /// Checks whether the set contains \p key
656 The function searches the item with key equal to \p key
657 and returns \p true if it is found, and \p false otherwise.
659 Note the hash functor specified for class \p Traits template parameter
660 should accept a parameter of type \p Q that can be not the same as \p value_type.
661 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
663 template <typename Q>
664 bool contains( Q const& key )
666 return find_value( key, key_comparator());
669 template <typename Q>
670 CDS_DEPRECATED("deprecated, use contains()")
671 bool find( Q const& key )
673 return contains( key );
677 /// Checks whether the set contains \p key using \p pred predicate for searching
679 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
680 \p Less functor has the interface like \p std::less.
681 \p Less must imply the same element order as the comparator used for building the list.
683 template <typename Q, typename Less>
684 bool contains( Q const& key, Less pred )
687 return find_value( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
690 template <typename Q, typename Less>
691 CDS_DEPRECATED("deprecated, use contains()")
692 bool find_with( Q const& key, Less pred )
694 return contains( key, pred );
698 /// Finds the key \p key and return the item found
699 /** \anchor cds_intrusive_SplitListSet_rcu_get
700 The function searches the item with key equal to \p key and returns the pointer to item found.
701 If \p key is not found it returns \p nullptr.
703 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
705 RCU should be locked before call of this function.
706 Returned item is valid only while RCU is locked:
708 typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
711 typename set_class::raw_ptr rp;
714 hash_set::rcu_lock lock;
716 rp = theSet.get( 5 );
721 // Unlock RCU by rcu_lock destructor
722 // rp can be retired by disposer at any time after RCU has been unlocked
726 template <typename Q>
727 raw_ptr get( Q const& key )
729 return get_( key, key_comparator());
732 /// Finds the key \p key and return the item found
734 The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
735 but \p pred is used for comparing the keys.
737 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
739 \p pred must imply the same element order as the comparator used for building the set.
741 template <typename Q, typename Less>
742 raw_ptr get_with( Q const& key, Less pred )
745 return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
749 /// Returns item count in the set
752 return m_ItemCounter;
755 /// Checks if the set is empty
757 Emptiness is checked by item counting: if item count is zero then the set is empty.
758 Thus, the correct item counting feature is an important part of split-list set implementation.
765 /// Clears the set (not atomic)
768 iterator it = begin();
769 while ( it != end()) {
777 /// Returns internal statistics
778 stat const& statistics() const
783 /// Returns internal statistics for \p OrderedList
784 typename OrderedList::stat const& list_statistics() const
786 return m_List.statistics();
791 template <bool IsConst>
793 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
795 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
796 typedef typename iterator_base_class::list_iterator list_iterator;
799 : iterator_base_class()
802 iterator_type( iterator_type const& src )
803 : iterator_base_class( src )
806 // This ctor should be protected...
807 iterator_type( list_iterator itCur, list_iterator itEnd )
808 : iterator_base_class( itCur, itEnd )
814 ///@name Forward iterators (thread-safe under RCU lock)
818 The forward iterator for a split-list has some features:
819 - it has no post-increment operator
820 - it depends on iterator of underlying \p OrderedList
822 You may safely use iterators in multi-threaded environment only under RCU lock.
823 Otherwise, a crash is possible if another thread deletes the element the iterator points to.
825 typedef iterator_type<false> iterator;
827 /// Const forward iterator
829 For iterator's features and requirements see \ref iterator
831 typedef iterator_type<true> const_iterator;
833 /// Returns a forward iterator addressing the first element in a split-list
835 For empty list \code begin() == end() \endcode
839 return iterator( m_List.begin(), m_List.end());
842 /// Returns an iterator that addresses the location succeeding the last element in a split-list
844 Do not use the value returned by <tt>end</tt> function to access any item.
846 The returned value can be used only to control reaching the end of the split-list.
847 For empty list \code begin() == end() \endcode
851 return iterator( m_List.end(), m_List.end());
854 /// Returns a forward const iterator addressing the first element in a split-list
855 const_iterator begin() const
859 /// Returns a forward const iterator addressing the first element in a split-list
860 const_iterator cbegin() const
862 return const_iterator( m_List.cbegin(), m_List.cend());
865 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
866 const_iterator end() const
870 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
871 const_iterator cend() const
873 return const_iterator( m_List.cend(), m_List.cend());
879 aux_node_type * alloc_aux_node( size_t nHash )
881 m_Stat.onHeadNodeAllocated();
882 aux_node_type* p = m_Buckets.alloc_aux_node();
888 void free_aux_node( aux_node_type * p )
890 m_Buckets.free_aux_node( p );
891 m_Stat.onHeadNodeFreed();
894 /// Calculates hash value of \p key
895 template <typename Q>
896 size_t hash_value( Q const& key ) const
898 return m_HashFunctor( key );
901 size_t bucket_no( size_t nHash ) const
903 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
906 static size_t parent_bucket( size_t nBucket )
908 assert( nBucket > 0 );
909 return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
912 aux_node_type * init_bucket( size_t const nBucket )
914 assert( nBucket > 0 );
915 size_t nParent = parent_bucket( nBucket );
917 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
918 if ( pParentBucket == nullptr ) {
919 pParentBucket = init_bucket( nParent );
920 m_Stat.onRecursiveInitBucket();
923 assert( pParentBucket != nullptr );
925 // Allocate an aux node for new bucket
926 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
929 for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
933 pBucket = alloc_aux_node( split_list::dummy_hash<bit_reversal>( nBucket ));
935 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
936 m_Buckets.bucket( nBucket, pBucket );
937 m_Stat.onNewBucket();
941 // Another thread set the bucket. Wait while it done
942 free_aux_node( pBucket );
943 m_Stat.onBucketInitContenton();
947 // There are no free buckets. It means that the bucket table is full
948 // Wait while another thread set the bucket or a free bucket will be available
949 m_Stat.onBucketsExhausted();
953 // Another thread set the bucket. Wait while it done
954 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
956 m_Stat.onBusyWaitBucketInit();
962 aux_node_type * get_bucket( size_t nHash )
964 size_t nBucket = bucket_no( nHash );
966 aux_node_type * pHead = m_Buckets.bucket( nBucket );
967 if ( pHead == nullptr )
968 pHead = init_bucket( nBucket );
970 assert( pHead->is_dummy());
977 // Initialize bucket 0
978 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash<bit_reversal>(0)*/ );
980 // insert_aux_node cannot return false for empty list
981 CDS_VERIFY( m_List.insert_aux_node( pNode ));
983 m_Buckets.bucket( 0, pNode );
986 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
988 return nBucketCount * nLoadFactor;
991 void inc_item_count()
993 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
994 if ( ++m_ItemCounter <= nMaxCount )
997 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
998 const size_t nBucketCount = static_cast<size_t>(1) << sz;
999 if ( nBucketCount < m_Buckets.capacity()) {
1000 // we may grow the bucket table
1001 const size_t nLoadFactor = m_Buckets.load_factor();
1002 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1003 return; // someone already have updated m_nBucketCountLog2, so stop here
1005 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1006 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1007 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1010 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1013 template <typename Q, typename Compare, typename Func>
1014 bool find_( Q& val, Compare cmp, Func f )
1016 size_t nHash = hash_value( val );
1017 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1018 aux_node_type * pHead = get_bucket( nHash );
1019 assert( pHead != nullptr );
1021 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
1022 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
1025 template <typename Q, typename Compare>
1026 bool find_value( Q const& val, Compare cmp )
1028 size_t nHash = hash_value( val );
1029 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1030 aux_node_type * pHead = get_bucket( nHash );
1031 assert( pHead != nullptr );
1033 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1036 template <typename Q, typename Compare>
1037 raw_ptr get_( Q const& val, Compare cmp )
1039 size_t nHash = hash_value( val );
1040 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1041 aux_node_type * pHead = get_bucket( nHash );
1042 assert( pHead != nullptr );
1044 raw_ptr p = m_List.get_at( pHead, sv, cmp );
1045 m_Stat.onFind( !!p );
1049 template <typename Q, typename Compare>
1050 value_type * extract_( Q const& val, Compare cmp )
1052 size_t nHash = hash_value( val );
1053 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1054 aux_node_type * pHead = get_bucket( nHash );
1055 assert( pHead != nullptr );
1057 value_type * pNode = m_List.extract_at( pHead, sv, cmp );
1060 m_Stat.onExtractSuccess();
1063 m_Stat.onExtractFailed();
1067 template <typename Q, typename Less>
1068 value_type * extract_with_( Q const& val, Less pred )
1071 return extract_( val, typename ordered_list_adapter::template make_compare_from_less<Less>());
1074 template <typename Q, typename Compare>
1075 bool erase_( const Q& val, Compare cmp )
1077 size_t nHash = hash_value( val );
1078 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1079 aux_node_type * pHead = get_bucket( nHash );
1080 assert( pHead != nullptr );
1082 if ( m_List.erase_at( pHead, sv, cmp )) {
1084 m_Stat.onEraseSuccess();
1087 m_Stat.onEraseFailed();
1091 template <typename Q, typename Compare, typename Func>
1092 bool erase_( Q const& val, Compare cmp, Func f )
1094 size_t nHash = hash_value( val );
1095 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1096 aux_node_type * pHead = get_bucket( nHash );
1097 assert( pHead != nullptr );
1099 if ( m_List.erase_at( pHead, sv, cmp, f )) {
1101 m_Stat.onEraseSuccess();
1104 m_Stat.onEraseFailed();
1111 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1113 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1114 padded_bucket_table m_Buckets; ///< bucket table
1116 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1117 padded_ordered_list m_List; ///< Ordered list containing split-list items
1119 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1120 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
1121 item_counter m_ItemCounter; ///< Item counter
1122 hash m_HashFunctor; ///< Hash functor
1123 stat m_Stat; ///< Internal statistics accumulator
1127 }} // namespace cds::intrusive
1129 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H