2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_H
32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
35 #include <cds/intrusive/details/split_list_base.h>
37 namespace cds { namespace intrusive {
39 /// Split-ordered list
40 /** @ingroup cds_intrusive_map
41 \anchor cds_intrusive_SplitListSet_hp
43 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
44 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
45 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
47 The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
48 recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
49 without item moving on resizing.
51 \anchor cds_SplitList_algo_desc
52 <b>Short description</b>
53 [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
55 The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
56 the places in the list where a sublist of 'correct' items can be found. A bucket is initialized upon first
57 access by assigning it to a new 'dummy' node (dashed contour) in the list, preceding all items that should be
58 in that bucket. A newly created bucket splits an older bucket's chain, reducing the access cost to its items. The
59 table uses a modulo 2**i hash (there are known techniques for 'pre-hashing' before a modulo 2**i hash
60 to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
62 Unlike moving an item, the operation of directing a bucket pointer can be done
63 in a single CAS operation, and since items are not moved, they are never 'lost'.
64 However, to make this approach work, one must be able to keep the items in the
65 list sorted in such a way that any bucket's sublist can be 'split' by directing a new
66 bucket pointer within it. This operation must be recursively repeatable, as every
67 split bucket may be split again and again as the hash table grows. To achieve this
68 goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
69 in a given bucket adjacent in the list throughout the repeated splitting process.
71 Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
72 simple binary reversal: reversing the bits of the hash key so that the new key's
73 most significant bits (MSB) are those that were originally its least significant.
74 The split-order keys of regular nodes are exactly the bit-reverse image of the original
75 keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
76 4</tt> bucket, which can be recursively split in two by inserting a new node between
79 To insert (respectively delete or search for) an item in the hash table, hash its
80 key to the appropriate bucket using recursive split-ordering, follow the pointer to
81 the appropriate location in the sorted items list, and traverse the list until the key's
82 proper location in the split-ordering (respectively until the key or a key indicating
83 the item is not in the list is found). Because of the combinatorial structure induced
84 by the split-ordering, this will require traversal of no more than an expected constant number of items.
86 The design is modular: to implement the ordered items list, you can use one of several
87 non-blocking list-based set algorithms: MichaelList, LazyList.
91 Template parameters are:
92 - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
93 - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
94 The intrusive ordered list implementation specifies the type \p T stored in the split-list set, the reclamation
95 schema \p GC used by split-list set, the comparison functor for the type \p T and other features specific for
97 - \p Traits - split-list traits, default is \p split_list::traits.
98 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
100 @warning \p IterableList is not supported as \p OrderedList template parameter.
102 There are several specialization of the split-list class for different \p GC:
103 - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
104 \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
105 - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
106 \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
108 \anchor cds_SplitList_hash_functor
111 Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
112 It is expected that type \p Q contains full key of \p value_type, and for equal keys of type \p Q and \p value_type
113 the hash values of these keys must be equal too.
114 The hash functor \p Traits::hash should accept parameters of both type:
118 std::string key_ ; // key field
124 size_t operator()( const std::string& s ) const
126 return std::hash( s );
129 size_t operator()( const Foo& f ) const
131 return (*this)( f.key_ );
138 First, you should choose ordered list type to use in your split-list set:
140 // For gc::HP-based MichaelList implementation
141 #include <cds/intrusive/michael_list_hp.h>
143 // cds::intrusive::SplitListSet declaration
144 #include <cds/intrusive/split_list.h>
147 // Note you should declare your struct based on cds::intrusive::split_list::node
148 // which is a wrapper for ordered-list node struct.
149 // In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
150 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
152 std::string key_ ; // key field
153 unsigned val_ ; // value field
154 // ... other value fields
157 // Declare comparator for the item
160 int operator()( const Foo& f1, const Foo& f2 ) const
162 return f1.key_.compare( f2.key_ );
166 // Declare base ordered-list type for split-list
167 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
168 typename cds::intrusive::michael_list::make_traits<
170 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
171 // item comparator option
172 ,cds::opt::compare< FooCmp >
177 Second, you should declare split-list set container:
180 // Declare hash functor
181 // Note, the hash functor accepts parameter type Foo and std::string
183 size_t operator()( const Foo& f ) const
185 return cds::opt::v::hash<std::string>()( f.key_ );
187 size_t operator()( const std::string& s ) const
189 return cds::opt::v::hash<std::string>()( s );
193 // Split-list set typedef
194 typedef cds::intrusive::SplitListSet<
197 ,typename cds::intrusive::split_list::make_traits<
198 cds::opt::hash< FooHash >
203 Now, you can use \p Foo_set in your application.
209 fooSet.insert( *foo );
217 # ifdef CDS_DOXYGEN_INVOKED
218 class Traits = split_list::traits
226 typedef GC gc; ///< Garbage collector
227 typedef Traits traits; ///< Set traits
231 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
235 # ifdef CDS_DOXYGEN_INVOKED
236 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
238 typedef typename wrapped_ordered_list::result ordered_list;
240 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
241 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
242 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
244 /// Hash functor for \p %value_type and all its derivatives that you use
245 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
247 typedef typename traits::item_counter item_counter; ///< Item counter type
248 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
249 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
250 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
251 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
253 /// Count of hazard pointer required
254 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
258 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
259 typedef split_list::node<list_node_type> node_type; ///< split-list node type
260 typedef node_type aux_node_type; ///< dummy node type
262 /// Split-list node traits
264 This traits is intended for converting between underlying ordered list node type \p list_node_type
265 and split-list node type \p node_type
267 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
269 /// Bucket table implementation
270 typedef typename split_list::details::bucket_table_selector<
271 traits::dynamic_bucket_table
274 , opt::allocator< typename traits::allocator >
275 , opt::memory_model< memory_model >
276 >::type bucket_table;
278 typedef cds::details::Allocator< aux_node_type, typename traits::allocator > aux_node_allocator;
283 /// Ordered list wrapper to access protected members
284 class ordered_list_wrapper: public ordered_list
286 typedef ordered_list base_class;
287 typedef typename base_class::auxiliary_head bucket_head_type;
290 bool insert_at( aux_node_type * pHead, value_type& val )
292 assert( pHead != nullptr );
293 bucket_head_type h(pHead);
294 return base_class::insert_at( h, val );
297 template <typename Func>
298 bool insert_at( aux_node_type * pHead, value_type& val, Func f )
300 assert( pHead != nullptr );
301 bucket_head_type h(pHead);
302 return base_class::insert_at( h, val, f );
305 template <typename Func>
306 std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
308 assert( pHead != nullptr );
309 bucket_head_type h(pHead);
310 return base_class::update_at( h, val, func, bAllowInsert );
313 bool unlink_at( aux_node_type * pHead, value_type& val )
315 assert( pHead != nullptr );
316 bucket_head_type h(pHead);
317 return base_class::unlink_at( h, val );
320 template <typename Q, typename Compare, typename Func>
321 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
323 assert( pHead != nullptr );
324 bucket_head_type h(pHead);
325 return base_class::erase_at( h, val, cmp, f );
328 template <typename Q, typename Compare>
329 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
331 assert( pHead != nullptr );
332 bucket_head_type h(pHead);
333 return base_class::erase_at( h, val, cmp );
336 template <typename Q, typename Compare>
337 guarded_ptr extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
339 assert( pHead != nullptr );
340 bucket_head_type h(pHead);
341 return base_class::extract_at( h, val, cmp );
344 template <typename Q, typename Compare, typename Func>
345 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
347 assert( pHead != nullptr );
348 bucket_head_type h(pHead);
349 return base_class::find_at( h, val, cmp, f );
352 template <typename Q, typename Compare>
353 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
355 assert( pHead != nullptr );
356 bucket_head_type h(pHead);
357 return base_class::find_at( h, val, cmp );
360 template <typename Q, typename Compare>
361 guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
363 assert( pHead != nullptr );
364 bucket_head_type h(pHead);
365 return base_class::get_at( h, val, cmp );
368 bool insert_aux_node( aux_node_type * pNode )
370 return base_class::insert_aux_node( pNode );
372 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
374 bucket_head_type h(pHead);
375 return base_class::insert_aux_node( h, pNode );
381 /// Initialize split-ordered list of default capacity
383 The default capacity is defined in bucket table constructor.
384 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
385 which selects by \p split_list::dynamic_bucket_table option.
388 : m_nBucketCountLog2(1)
389 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
394 /// Initialize split-ordered list
396 size_t nItemCount ///< estimate average of item count
397 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
399 : m_Buckets( nItemCount, nLoadFactor )
400 , m_nBucketCountLog2(1)
401 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
409 The function inserts \p val in the set if it does not contain
410 an item with key equal to \p val.
412 Returns \p true if \p val is placed into the set, \p false otherwise.
414 bool insert( value_type& val )
416 size_t nHash = hash_value( val );
417 aux_node_type * pHead = get_bucket( nHash );
418 assert( pHead != nullptr );
420 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
422 if ( m_List.insert_at( pHead, val )) {
424 m_Stat.onInsertSuccess();
427 m_Stat.onInsertFailed();
433 This function is intended for derived non-intrusive containers.
435 The function allows to split creating of new item into two part:
436 - create item with key only
437 - insert new item into the set
438 - if inserting is success, calls \p f functor to initialize value-field of \p val.
440 The functor signature is:
442 void func( value_type& val );
444 where \p val is the item inserted.
445 The user-defined functor is called only if the inserting is success.
447 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
448 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
451 template <typename Func>
452 bool insert( value_type& val, Func f )
454 size_t nHash = hash_value( val );
455 aux_node_type * pHead = get_bucket( nHash );
456 assert( pHead != nullptr );
458 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
460 if ( m_List.insert_at( pHead, val, f )) {
462 m_Stat.onInsertSuccess();
465 m_Stat.onInsertFailed();
471 The operation performs inserting or changing data with lock-free manner.
473 If the item \p val is not found in the set, then \p val is inserted
474 iff \p bAllowInsert is \p true.
475 Otherwise, the functor \p func is called with item found.
476 The functor signature is:
478 void func( bool bNew, value_type& item, value_type& val );
481 - \p bNew - \p true if the item has been inserted, \p false otherwise
482 - \p item - item of the set
483 - \p val - argument \p val passed into the \p update() function
484 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
485 refers to the same thing.
487 The functor may change non-key fields of the \p item.
489 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
490 \p second is \p true if new item has been added or \p false if the item with \p val
491 already is in the list.
493 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
494 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
497 template <typename Func>
498 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
500 size_t nHash = hash_value( val );
501 aux_node_type * pHead = get_bucket( nHash );
502 assert( pHead != nullptr );
504 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
506 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
507 if ( bRet.first && bRet.second ) {
509 m_Stat.onUpdateNew();
512 m_Stat.onUpdateExist();
516 template <typename Func>
517 CDS_DEPRECATED("ensure() is deprecated, use update()")
518 std::pair<bool, bool> ensure( value_type& val, Func func )
520 return update( val, func, true );
524 /// Unlinks the item \p val from the set
526 The function searches the item \p val in the set and unlinks it from the set
527 if it is found and is equal to \p val.
529 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
530 and deletes the item found. \p unlink finds an item by key and deletes it
531 only if \p val is an item of that set, i.e. the pointer to item found
532 is equal to <tt> &val </tt>.
534 The function returns \p true if success and \p false otherwise.
536 bool unlink( value_type& val )
538 size_t nHash = hash_value( val );
539 aux_node_type * pHead = get_bucket( nHash );
540 assert( pHead != nullptr );
542 if ( m_List.unlink_at( pHead, val )) {
544 m_Stat.onEraseSuccess();
547 m_Stat.onEraseFailed();
551 /// Deletes the item from the set
552 /** \anchor cds_intrusive_SplitListSet_hp_erase
553 The function searches an item with key equal to \p key in the set,
554 unlinks it from the set, and returns \p true.
555 If the item with key equal to \p key is not found the function return \p false.
557 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
558 and deletes the item found. \p unlink finds an item by key and deletes it
559 only if \p key is an item of that set, i.e. the pointer to item found
560 is equal to <tt> &key </tt>.
562 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
564 template <typename Q>
565 bool erase( Q const& key )
567 return erase_( key, key_comparator());
570 /// Deletes the item from the set with comparing functor \p pred
573 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
574 but \p pred predicate is used for key comparing.
575 \p Less has the interface like \p std::less.
576 \p pred must imply the same element order as the comparator used for building the set.
578 template <typename Q, typename Less>
579 bool erase_with( const Q& key, Less pred )
582 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
585 /// Deletes the item from the set
586 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
587 The function searches an item with key equal to \p key in the set,
588 call \p f functor with item found, unlinks it from the set, and returns \p true.
589 The \ref disposer specified by \p OrderedList class template parameter is called
590 by garbage collector \p GC asynchronously.
592 The \p Func interface is
595 void operator()( value_type const& item );
599 If the item with key equal to \p key is not found the function return \p false.
601 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
603 template <typename Q, typename Func>
604 bool erase( Q const& key, Func f )
606 return erase_( key, key_comparator(), f );
609 /// Deletes the item from the set with comparing functor \p pred
611 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
612 but \p pred predicate is used for key comparing.
613 \p Less has the interface like \p std::less.
614 \p pred must imply the same element order as the comparator used for building the set.
616 template <typename Q, typename Less, typename Func>
617 bool erase_with( Q const& key, Less pred, Func f )
620 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
623 /// Extracts the item with specified \p key
624 /** \anchor cds_intrusive_SplitListSet_hp_extract
625 The function searches an item with key equal to \p key,
626 unlinks it from the set, and returns it as \p guarded_ptr.
627 If \p key is not found the function returns an empty guarded pointer.
629 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
631 The \p disposer specified in \p OrderedList class' template parameter is called automatically
632 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
633 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
637 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
638 splitlist_set theSet;
641 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
646 // Destructor of gp releases internal HP guard
650 template <typename Q>
651 guarded_ptr extract( Q const& key )
653 return extract_( key );
656 /// Extracts the item using compare functor \p pred
658 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
659 but \p pred predicate is used for key comparing.
661 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
663 \p pred must imply the same element order as the comparator used for building the set.
665 template <typename Q, typename Less>
666 guarded_ptr extract_with( Q const& key, Less pred )
668 return extract_with_( key, pred );
671 /// Finds the key \p key
672 /** \anchor cds_intrusive_SplitListSet_hp_find_func
673 The function searches the item with key equal to \p key and calls the functor \p f for item found.
674 The interface of \p Func functor is:
677 void operator()( value_type& item, Q& key );
680 where \p item is the item found, \p key is the <tt>find</tt> function argument.
682 The functor can change non-key fields of \p item. Note that the functor is only guarantee
683 that \p item cannot be disposed during functor is executing.
684 The functor does not serialize simultaneous access to the set \p item. If such access is
685 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
687 Note the hash functor specified for class \p Traits template parameter
688 should accept a parameter of type \p Q that can be not the same as \p value_type.
690 The function returns \p true if \p key is found, \p false otherwise.
692 template <typename Q, typename Func>
693 bool find( Q& key, Func f )
695 return find_( key, key_comparator(), f );
698 template <typename Q, typename Func>
699 bool find( Q const& key, Func f )
701 return find_( key, key_comparator(), f );
705 /// Finds the key \p key with \p pred predicate for comparing
707 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
708 but \p cmp is used for key compare.
709 \p Less has the interface like \p std::less.
710 \p cmp must imply the same element order as the comparator used for building the set.
712 template <typename Q, typename Less, typename Func>
713 bool find_with( Q& key, Less pred, Func f )
716 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
719 template <typename Q, typename Less, typename Func>
720 bool find_with( Q const& key, Less pred, Func f )
723 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
727 /// Checks whether the set contains \p key
729 The function searches the item with key equal to \p key
730 and returns \p true if it is found, and \p false otherwise.
732 Note the hash functor specified for class \p Traits template parameter
733 should accept a parameter of type \p Q that can be not the same as \p value_type.
734 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
736 template <typename Q>
737 bool contains( Q const& key )
739 return find_( key, key_comparator());
742 template <typename Q>
743 CDS_DEPRECATED("deprecated, use contains()")
744 bool find( Q const& key )
746 return contains( key );
750 /// Checks whether the set contains \p key using \p pred predicate for searching
752 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
753 \p Less functor has the interface like \p std::less.
754 \p Less must imply the same element order as the comparator used for building the set.
756 template <typename Q, typename Less>
757 bool contains( Q const& key, Less pred )
760 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
763 template <typename Q, typename Less>
764 CDS_DEPRECATED("deprecated, use contains()")
765 bool find_with( Q const& key, Less pred )
767 return contains( key, pred );
771 /// Finds the key \p key and return the item found
772 /** \anchor cds_intrusive_SplitListSet_hp_get
773 The function searches the item with key equal to \p key
774 and returns the item found as \p guarded_ptr.
775 If \p key is not found the function returns an empty guarded pointer.
777 The \p disposer specified in \p OrderedList class' template parameter is called
778 by garbage collector \p GC automatically when returned \p guarded_ptr object
779 will be destroyed or released.
780 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
784 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
785 splitlist_set theSet;
788 splitlist_set::guarded_ptr gp = theSet.get( 5 );
793 // Destructor of guarded_ptr releases internal HP guard
797 Note the compare functor specified for \p OrderedList template parameter
798 should accept a parameter of type \p Q that can be not the same as \p value_type.
800 template <typename Q>
801 guarded_ptr get( Q const& key )
806 /// Finds the key \p key and return the item found
808 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
809 but \p pred is used for comparing the keys.
811 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
813 \p pred must imply the same element order as the comparator used for building the set.
815 template <typename Q, typename Less>
816 guarded_ptr get_with( Q const& key, Less pred )
818 return get_with_( key, pred );
821 /// Returns item count in the set
824 return m_ItemCounter;
827 /// Checks if the set is empty
829 Emptiness is checked by item counting: if item count is zero then the set is empty.
830 Thus, the correct item counting feature is an important part of split-list set implementation.
837 /// Clears the set (non-atomic)
839 The function unlink all items from the set.
840 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
842 For each item the \p disposer is called after unlinking.
846 iterator it = begin();
847 while ( it != end()) {
855 /// Returns internal statistics
856 stat const& statistics() const
863 template <bool IsConst>
865 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
867 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
868 typedef typename iterator_base_class::list_iterator list_iterator;
871 : iterator_base_class()
874 iterator_type( iterator_type const& src )
875 : iterator_base_class( src )
878 // This ctor should be protected...
879 iterator_type( list_iterator itCur, list_iterator itEnd )
880 : iterator_base_class( itCur, itEnd )
885 ///@name Forward iterators (only for debugging purpose)
889 The forward iterator for a split-list has some features:
890 - it has no post-increment operator
891 - it depends on iterator of underlying \p OrderedList
892 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
893 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
894 deleting operations it is no guarantee that you iterate all item in the set.
895 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
897 @warning Use this iterator on the concurrent container for debugging purpose only.
899 typedef iterator_type<false> iterator;
901 /// Const forward iterator
903 For iterator's features and requirements see \ref iterator
905 typedef iterator_type<true> const_iterator;
907 /// Returns a forward iterator addressing the first element in a split-list
909 For empty list \code begin() == end() \endcode
913 return iterator( m_List.begin(), m_List.end());
916 /// Returns an iterator that addresses the location succeeding the last element in a split-list
918 Do not use the value returned by <tt>end</tt> function to access any item.
920 The returned value can be used only to control reaching the end of the split-list.
921 For empty list \code begin() == end() \endcode
925 return iterator( m_List.end(), m_List.end());
928 /// Returns a forward const iterator addressing the first element in a split-list
929 const_iterator begin() const
933 /// Returns a forward const iterator addressing the first element in a split-list
934 const_iterator cbegin() const
936 return const_iterator( m_List.cbegin(), m_List.cend());
939 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
940 const_iterator end() const
944 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
945 const_iterator cend() const
947 return const_iterator( m_List.cend(), m_List.cend());
953 aux_node_type * alloc_aux_node( size_t nHash )
955 m_Stat.onHeadNodeAllocated();
956 return aux_node_allocator().New( nHash );
958 void free_aux_node( aux_node_type * p )
960 aux_node_allocator().Delete( p );
961 m_Stat.onHeadNodeFreed();
964 /// Calculates hash value of \p key
965 template <typename Q>
966 size_t hash_value( Q const& key ) const
968 return m_HashFunctor( key );
971 size_t bucket_no( size_t nHash ) const
973 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
976 static size_t parent_bucket( size_t nBucket )
978 assert( nBucket > 0 );
979 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
982 aux_node_type * init_bucket( size_t nBucket )
984 assert( nBucket > 0 );
985 size_t nParent = parent_bucket( nBucket );
987 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
988 if ( pParentBucket == nullptr ) {
989 pParentBucket = init_bucket( nParent );
990 m_Stat.onRecursiveInitBucket();
993 assert( pParentBucket != nullptr );
995 // Allocate a dummy node for new bucket
997 aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
998 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
999 m_Buckets.bucket( nBucket, pBucket );
1000 m_Stat.onNewBucket();
1003 free_aux_node( pBucket );
1006 // Another thread set the bucket. Wait while it done
1008 // In this point, we must wait while nBucket is empty.
1009 // The compiler can decide that waiting loop can be "optimized" (stripped)
1010 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
1011 m_Stat.onBucketInitContenton();
1014 aux_node_type volatile * p = m_Buckets.bucket( nBucket );
1016 return const_cast<aux_node_type *>(p);
1018 m_Stat.onBusyWaitBucketInit();
1022 aux_node_type * get_bucket( size_t nHash )
1024 size_t nBucket = bucket_no( nHash );
1026 aux_node_type * pHead = m_Buckets.bucket( nBucket );
1027 if ( pHead == nullptr )
1028 pHead = init_bucket( nBucket );
1030 assert( pHead->is_dummy() );
1037 // GC and OrderedList::gc must be the same
1038 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
1040 // atomicity::empty_item_counter is not allowed as a item counter
1041 static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
1042 "cds::atomicity::empty_item_counter is not allowed as a item counter");
1044 // Initialize bucket 0
1045 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
1047 // insert_aux_node cannot return false for empty list
1048 CDS_VERIFY( m_List.insert_aux_node( pNode ) );
1050 m_Buckets.bucket( 0, pNode );
1053 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
1055 return nBucketCount * nLoadFactor;
1058 void inc_item_count()
1060 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
1061 if ( ++m_ItemCounter <= nMaxCount )
1064 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
1065 const size_t nBucketCount = static_cast<size_t>(1) << sz;
1066 if ( nBucketCount < m_Buckets.capacity() ) {
1067 // we may grow the bucket table
1068 const size_t nLoadFactor = m_Buckets.load_factor();
1069 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ) )
1070 return; // someone already have updated m_nBucketCountLog2, so stop here
1072 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1073 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1074 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1077 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1080 template <typename Q, typename Compare, typename Func>
1081 bool find_( Q& val, Compare cmp, Func f )
1083 size_t nHash = hash_value( val );
1084 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ) );
1085 aux_node_type * pHead = get_bucket( nHash );
1086 assert( pHead != nullptr );
1088 return m_Stat.onFind(
1089 m_List.find_at( pHead, sv, cmp,
1090 [&f]( value_type& item, split_list::details::search_value_type<Q>& val ) { f( item, val.val ); } )
1094 template <typename Q, typename Compare>
1095 bool find_( Q const& val, Compare cmp )
1097 size_t nHash = hash_value( val );
1098 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1099 aux_node_type * pHead = get_bucket( nHash );
1100 assert( pHead != nullptr );
1102 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ) );
1105 template <typename Q, typename Compare>
1106 guarded_ptr get_( Q const& val, Compare cmp )
1108 size_t nHash = hash_value( val );
1109 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1110 aux_node_type * pHead = get_bucket( nHash );
1111 assert( pHead != nullptr );
1113 guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
1114 m_Stat.onFind( !gp.empty() );
1118 template <typename Q>
1119 guarded_ptr get_( Q const& key )
1121 return get_( key, key_comparator() );
1124 template <typename Q, typename Less>
1125 guarded_ptr get_with_( Q const& key, Less )
1127 return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
1130 template <typename Q, typename Compare, typename Func>
1131 bool erase_( Q const& val, Compare cmp, Func f )
1133 size_t nHash = hash_value( val );
1134 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1135 aux_node_type * pHead = get_bucket( nHash );
1136 assert( pHead != nullptr );
1138 if ( m_List.erase_at( pHead, sv, cmp, f ) ) {
1140 m_Stat.onEraseSuccess();
1143 m_Stat.onEraseFailed();
1147 template <typename Q, typename Compare>
1148 bool erase_( Q const& val, Compare cmp )
1150 size_t nHash = hash_value( val );
1151 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1152 aux_node_type * pHead = get_bucket( nHash );
1153 assert( pHead != nullptr );
1155 if ( m_List.erase_at( pHead, sv, cmp ) ) {
1157 m_Stat.onEraseSuccess();
1160 m_Stat.onEraseFailed();
1164 template <typename Q, typename Compare>
1165 guarded_ptr extract_( Q const& val, Compare cmp )
1167 size_t nHash = hash_value( val );
1168 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1169 aux_node_type * pHead = get_bucket( nHash );
1170 assert( pHead != nullptr );
1172 guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
1175 m_Stat.onExtractSuccess();
1178 m_Stat.onExtractFailed();
1182 template <typename Q>
1183 guarded_ptr extract_( Q const& key )
1185 return extract_( key, key_comparator() );
1188 template <typename Q, typename Less>
1189 guarded_ptr extract_with_( Q const& key, Less )
1191 return extract_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
1197 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
1198 bucket_table m_Buckets; ///< bucket table
1199 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1200 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
1201 item_counter m_ItemCounter; ///< Item counter
1202 hash m_HashFunctor; ///< Hash functor
1203 stat m_Stat; ///< Internal statistics
1207 }} // namespace cds::intrusive
1209 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H