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>
36 #include <cds/details/type_padding.h>
38 namespace cds { namespace intrusive {
40 /// Split-ordered list
41 /** @ingroup cds_intrusive_map
42 \anchor cds_intrusive_SplitListSet_hp
44 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
45 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
46 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
48 The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
49 recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
50 without item moving on resizing.
52 \anchor cds_SplitList_algo_desc
53 <b>Short description</b>
54 [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
56 The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
57 the places in the list where a sublist of 'correct' items can be found. A bucket is initialized upon first
58 access by assigning it to a new 'dummy' node (dashed contour) in the list, preceding all items that should be
59 in that bucket. A newly created bucket splits an older bucket's chain, reducing the access cost to its items. The
60 table uses a modulo 2**i hash (there are known techniques for 'pre-hashing' before a modulo 2**i hash
61 to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
63 Unlike moving an item, the operation of directing a bucket pointer can be done
64 in a single CAS operation, and since items are not moved, they are never 'lost'.
65 However, to make this approach work, one must be able to keep the items in the
66 list sorted in such a way that any bucket's sublist can be 'split' by directing a new
67 bucket pointer within it. This operation must be recursively repeatable, as every
68 split bucket may be split again and again as the hash table grows. To achieve this
69 goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
70 in a given bucket adjacent in the list throughout the repeated splitting process.
72 Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
73 simple binary reversal: reversing the bits of the hash key so that the new key's
74 most significant bits (MSB) are those that were originally its least significant.
75 The split-order keys of regular nodes are exactly the bit-reverse image of the original
76 keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
77 4</tt> bucket, which can be recursively split in two by inserting a new node between
80 To insert (respectively delete or search for) an item in the hash table, hash its
81 key to the appropriate bucket using recursive split-ordering, follow the pointer to
82 the appropriate location in the sorted items list, and traverse the list until the key's
83 proper location in the split-ordering (respectively until the key or a key indicating
84 the item is not in the list is found). Because of the combinatorial structure induced
85 by the split-ordering, this will require traversal of no more than an expected constant number of items.
87 The design is modular: to implement the ordered items list, you can use one of several
88 non-blocking list-based set algorithms: MichaelList, LazyList.
92 Template parameters are:
93 - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
94 - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
95 The intrusive ordered list implementation specifies the type \p T stored in the split-list set, the reclamation
96 schema \p GC used by split-list set, the comparison functor for the type \p T and other features specific for
98 - \p Traits - split-list traits, default is \p split_list::traits.
99 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
101 @warning \p IterableList is not supported as \p OrderedList template parameter.
103 There are several specialization of the split-list class for different \p GC:
104 - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
105 \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
106 - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
107 \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
109 \anchor cds_SplitList_hash_functor
112 Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
113 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
114 the hash values of these keys must be equal too.
115 The hash functor \p Traits::hash should accept parameters of both type:
119 std::string key_ ; // key field
125 size_t operator()( const std::string& s ) const
127 return std::hash( s );
130 size_t operator()( const Foo& f ) const
132 return (*this)( f.key_ );
139 First, you should choose ordered list type to use in your split-list set:
141 // For gc::HP-based MichaelList implementation
142 #include <cds/intrusive/michael_list_hp.h>
144 // cds::intrusive::SplitListSet declaration
145 #include <cds/intrusive/split_list.h>
148 // Note you should declare your struct based on cds::intrusive::split_list::node
149 // which is a wrapper for ordered-list node struct.
150 // In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
151 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
153 std::string key_ ; // key field
154 unsigned val_ ; // value field
155 // ... other value fields
158 // Declare comparator for the item
161 int operator()( const Foo& f1, const Foo& f2 ) const
163 return f1.key_.compare( f2.key_ );
167 // Declare base ordered-list type for split-list
168 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
169 typename cds::intrusive::michael_list::make_traits<
171 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
172 // item comparator option
173 ,cds::opt::compare< FooCmp >
178 Second, you should declare split-list set container:
181 // Declare hash functor
182 // Note, the hash functor accepts parameter type Foo and std::string
184 size_t operator()( const Foo& f ) const
186 return cds::opt::v::hash<std::string>()( f.key_ );
188 size_t operator()( const std::string& s ) const
190 return cds::opt::v::hash<std::string>()( s );
194 // Split-list set typedef
195 typedef cds::intrusive::SplitListSet<
198 ,typename cds::intrusive::split_list::make_traits<
199 cds::opt::hash< FooHash >
204 Now, you can use \p Foo_set in your application.
210 fooSet.insert( *foo );
218 # ifdef CDS_DOXYGEN_INVOKED
219 class Traits = split_list::traits
227 typedef GC gc; ///< Garbage collector
228 typedef Traits traits; ///< Set traits
232 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
236 # ifdef CDS_DOXYGEN_INVOKED
237 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
239 typedef typename wrapped_ordered_list::result ordered_list;
241 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
242 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
243 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
245 /// Hash functor for \p %value_type and all its derivatives that you use
246 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
248 typedef typename traits::item_counter item_counter; ///< Item counter type
249 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
250 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
251 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
252 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
254 /// Count of hazard pointer required
255 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
259 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
260 typedef split_list::node<list_node_type> node_type; ///< split-list 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 , opt::free_list< typename traits::free_list >
277 >::type bucket_table;
279 typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
284 /// Ordered list wrapper to access protected members
285 class ordered_list_wrapper: public ordered_list
287 typedef ordered_list base_class;
288 typedef typename base_class::auxiliary_head bucket_head_type;
291 bool insert_at( aux_node_type* pHead, value_type& val )
293 assert( pHead != nullptr );
294 bucket_head_type h(pHead);
295 return base_class::insert_at( h, val );
298 template <typename Func>
299 bool insert_at( aux_node_type * pHead, value_type& val, Func f )
301 assert( pHead != nullptr );
302 bucket_head_type h(pHead);
303 return base_class::insert_at( h, val, f );
306 template <typename Func>
307 std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
309 assert( pHead != nullptr );
310 bucket_head_type h(pHead);
311 return base_class::update_at( h, val, func, bAllowInsert );
314 bool unlink_at( aux_node_type * pHead, value_type& val )
316 assert( pHead != nullptr );
317 bucket_head_type h(pHead);
318 return base_class::unlink_at( h, val );
321 template <typename Q, typename Compare, typename Func>
322 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
324 assert( pHead != nullptr );
325 bucket_head_type h(pHead);
326 return base_class::erase_at( h, val, cmp, f );
329 template <typename Q, typename Compare>
330 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
332 assert( pHead != nullptr );
333 bucket_head_type h(pHead);
334 return base_class::erase_at( h, val, cmp );
337 template <typename Q, typename Compare>
338 guarded_ptr extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
340 assert( pHead != nullptr );
341 bucket_head_type h(pHead);
342 return base_class::extract_at( h, val, cmp );
345 template <typename Q, typename Compare, typename Func>
346 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
348 assert( pHead != nullptr );
349 bucket_head_type h(pHead);
350 return base_class::find_at( h, val, cmp, f );
353 template <typename Q, typename Compare>
354 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
356 assert( pHead != nullptr );
357 bucket_head_type h(pHead);
358 return base_class::find_at( h, val, cmp );
361 template <typename Q, typename Compare>
362 guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
364 assert( pHead != nullptr );
365 bucket_head_type h(pHead);
366 return base_class::get_at( h, val, cmp );
369 bool insert_aux_node( aux_node_type * pNode )
371 return base_class::insert_aux_node( pNode );
373 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
375 bucket_head_type h(pHead);
376 return base_class::insert_aux_node( h, pNode );
382 /// Initialize split-ordered list of default capacity
384 The default capacity is defined in bucket table constructor.
385 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
386 which selects by \p split_list::dynamic_bucket_table option.
389 : m_nBucketCountLog2(1)
390 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
395 /// Initialize split-ordered list
397 size_t nItemCount ///< estimate average of item count
398 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
400 : m_Buckets( nItemCount, nLoadFactor )
401 , m_nBucketCountLog2(1)
402 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
407 /// Destroys split-list set
410 // list contains aux node that cannot be retired
411 // all aux nodes will be destroyed by bucket table dtor
419 The function inserts \p val in the set if it does not contain
420 an item with key equal to \p val.
422 Returns \p true if \p val is placed into the set, \p false otherwise.
424 bool insert( value_type& val )
426 size_t nHash = hash_value( val );
427 aux_node_type * pHead = get_bucket( nHash );
428 assert( pHead != nullptr );
430 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
432 if ( m_List.insert_at( pHead, val )) {
434 m_Stat.onInsertSuccess();
437 m_Stat.onInsertFailed();
443 This function is intended for derived non-intrusive containers.
445 The function allows to split creating of new item into two part:
446 - create item with key only
447 - insert new item into the set
448 - if inserting is success, calls \p f functor to initialize value-field of \p val.
450 The functor signature is:
452 void func( value_type& val );
454 where \p val is the item inserted.
455 The user-defined functor is called only if the inserting is success.
457 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
458 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
461 template <typename Func>
462 bool insert( value_type& val, Func f )
464 size_t nHash = hash_value( val );
465 aux_node_type * pHead = get_bucket( nHash );
466 assert( pHead != nullptr );
468 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
470 if ( m_List.insert_at( pHead, val, f )) {
472 m_Stat.onInsertSuccess();
475 m_Stat.onInsertFailed();
481 The operation performs inserting or changing data with lock-free manner.
483 If the item \p val is not found in the set, then \p val is inserted
484 iff \p bAllowInsert is \p true.
485 Otherwise, the functor \p func is called with item found.
486 The functor signature is:
488 void func( bool bNew, value_type& item, value_type& val );
491 - \p bNew - \p true if the item has been inserted, \p false otherwise
492 - \p item - item of the set
493 - \p val - argument \p val passed into the \p update() function
494 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
495 refers to the same thing.
497 The functor may change non-key fields of the \p item.
499 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
500 \p second is \p true if new item has been added or \p false if the item with \p val
501 already is in the list.
503 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
504 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
507 template <typename Func>
508 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
510 size_t nHash = hash_value( val );
511 aux_node_type * pHead = get_bucket( nHash );
512 assert( pHead != nullptr );
514 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
516 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
517 if ( bRet.first && bRet.second ) {
519 m_Stat.onUpdateNew();
522 m_Stat.onUpdateExist();
526 template <typename Func>
527 CDS_DEPRECATED("ensure() is deprecated, use update()")
528 std::pair<bool, bool> ensure( value_type& val, Func func )
530 return update( val, func, true );
534 /// Unlinks the item \p val from the set
536 The function searches the item \p val in the set and unlinks it from the set
537 if it is found and is equal to \p val.
539 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
540 and deletes the item found. \p unlink finds an item by key and deletes it
541 only if \p val is an item of that set, i.e. the pointer to item found
542 is equal to <tt> &val </tt>.
544 The function returns \p true if success and \p false otherwise.
546 bool unlink( value_type& val )
548 size_t nHash = hash_value( val );
549 aux_node_type * pHead = get_bucket( nHash );
550 assert( pHead != nullptr );
552 if ( m_List.unlink_at( pHead, val )) {
554 m_Stat.onEraseSuccess();
557 m_Stat.onEraseFailed();
561 /// Deletes the item from the set
562 /** \anchor cds_intrusive_SplitListSet_hp_erase
563 The function searches an item with key equal to \p key in the set,
564 unlinks it from the set, and returns \p true.
565 If the item with key equal to \p key is not found the function return \p false.
567 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
568 and deletes the item found. \p unlink finds an item by key and deletes it
569 only if \p key is an item of that set, i.e. the pointer to item found
570 is equal to <tt> &key </tt>.
572 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
574 template <typename Q>
575 bool erase( Q const& key )
577 return erase_( key, key_comparator());
580 /// Deletes the item from the set with comparing functor \p pred
583 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
584 but \p pred predicate is used for key comparing.
585 \p Less has the interface like \p std::less.
586 \p pred must imply the same element order as the comparator used for building the set.
588 template <typename Q, typename Less>
589 bool erase_with( const Q& key, Less pred )
592 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
595 /// Deletes the item from the set
596 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
597 The function searches an item with key equal to \p key in the set,
598 call \p f functor with item found, unlinks it from the set, and returns \p true.
599 The \ref disposer specified by \p OrderedList class template parameter is called
600 by garbage collector \p GC asynchronously.
602 The \p Func interface is
605 void operator()( value_type const& item );
609 If the item with key equal to \p key is not found the function return \p false.
611 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
613 template <typename Q, typename Func>
614 bool erase( Q const& key, Func f )
616 return erase_( key, key_comparator(), f );
619 /// Deletes the item from the set with comparing functor \p pred
621 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
622 but \p pred predicate is used for key comparing.
623 \p Less has the interface like \p std::less.
624 \p pred must imply the same element order as the comparator used for building the set.
626 template <typename Q, typename Less, typename Func>
627 bool erase_with( Q const& key, Less pred, Func f )
630 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
633 /// Extracts the item with specified \p key
634 /** \anchor cds_intrusive_SplitListSet_hp_extract
635 The function searches an item with key equal to \p key,
636 unlinks it from the set, and returns it as \p guarded_ptr.
637 If \p key is not found the function returns an empty guarded pointer.
639 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
641 The \p disposer specified in \p OrderedList class' template parameter is called automatically
642 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
643 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
647 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
648 splitlist_set theSet;
651 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
656 // Destructor of gp releases internal HP guard
660 template <typename Q>
661 guarded_ptr extract( Q const& key )
663 return extract_( key );
666 /// Extracts the item using compare functor \p pred
668 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
669 but \p pred predicate is used for key comparing.
671 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
673 \p pred must imply the same element order as the comparator used for building the set.
675 template <typename Q, typename Less>
676 guarded_ptr extract_with( Q const& key, Less pred )
678 return extract_with_( key, pred );
681 /// Finds the key \p key
682 /** \anchor cds_intrusive_SplitListSet_hp_find_func
683 The function searches the item with key equal to \p key and calls the functor \p f for item found.
684 The interface of \p Func functor is:
687 void operator()( value_type& item, Q& key );
690 where \p item is the item found, \p key is the <tt>find</tt> function argument.
692 The functor can change non-key fields of \p item. Note that the functor is only guarantee
693 that \p item cannot be disposed during functor is executing.
694 The functor does not serialize simultaneous access to the set \p item. If such access is
695 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
697 Note the hash functor specified for class \p Traits template parameter
698 should accept a parameter of type \p Q that can be not the same as \p value_type.
700 The function returns \p true if \p key is found, \p false otherwise.
702 template <typename Q, typename Func>
703 bool find( Q& key, Func f )
705 return find_( key, key_comparator(), f );
708 template <typename Q, typename Func>
709 bool find( Q const& key, Func f )
711 return find_( key, key_comparator(), f );
715 /// Finds the key \p key with \p pred predicate for comparing
717 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
718 but \p cmp is used for key compare.
719 \p Less has the interface like \p std::less.
720 \p cmp must imply the same element order as the comparator used for building the set.
722 template <typename Q, typename Less, typename Func>
723 bool find_with( Q& key, Less pred, Func f )
726 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
729 template <typename Q, typename Less, typename Func>
730 bool find_with( Q const& key, Less pred, Func f )
733 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
737 /// Checks whether the set contains \p key
739 The function searches the item with key equal to \p key
740 and returns \p true if it is found, and \p false otherwise.
742 Note the hash functor specified for class \p Traits template parameter
743 should accept a parameter of type \p Q that can be not the same as \p value_type.
744 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
746 template <typename Q>
747 bool contains( Q const& key )
749 return find_( key, key_comparator());
752 template <typename Q>
753 CDS_DEPRECATED("deprecated, use contains()")
754 bool find( Q const& key )
756 return contains( key );
760 /// Checks whether the set contains \p key using \p pred predicate for searching
762 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
763 \p Less functor has the interface like \p std::less.
764 \p Less must imply the same element order as the comparator used for building the set.
766 template <typename Q, typename Less>
767 bool contains( Q const& key, Less pred )
770 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
773 template <typename Q, typename Less>
774 CDS_DEPRECATED("deprecated, use contains()")
775 bool find_with( Q const& key, Less pred )
777 return contains( key, pred );
781 /// Finds the key \p key and return the item found
782 /** \anchor cds_intrusive_SplitListSet_hp_get
783 The function searches the item with key equal to \p key
784 and returns the item found as \p guarded_ptr.
785 If \p key is not found the function returns an empty guarded pointer.
787 The \p disposer specified in \p OrderedList class' template parameter is called
788 by garbage collector \p GC automatically when returned \p guarded_ptr object
789 will be destroyed or released.
790 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
794 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
795 splitlist_set theSet;
798 splitlist_set::guarded_ptr gp = theSet.get( 5 );
803 // Destructor of guarded_ptr releases internal HP guard
807 Note the compare functor specified for \p OrderedList template parameter
808 should accept a parameter of type \p Q that can be not the same as \p value_type.
810 template <typename Q>
811 guarded_ptr get( Q const& key )
816 /// Finds the key \p key and return the item found
818 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
819 but \p pred is used for comparing the keys.
821 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
823 \p pred must imply the same element order as the comparator used for building the set.
825 template <typename Q, typename Less>
826 guarded_ptr get_with( Q const& key, Less pred )
828 return get_with_( key, pred );
831 /// Returns item count in the set
834 return m_ItemCounter;
837 /// Checks if the set is empty
839 Emptiness is checked by item counting: if item count is zero then the set is empty.
840 Thus, the correct item counting feature is an important part of split-list set implementation.
847 /// Clears the set (non-atomic)
849 The function unlink all items from the set.
850 The function is not atomic. After call the split-list can be non-empty.
852 For each item the \p disposer is called after unlinking.
856 iterator it = begin();
857 while ( it != end()) {
865 /// Returns internal statistics
866 stat const& statistics() const
873 template <bool IsConst>
875 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
877 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
878 typedef typename iterator_base_class::list_iterator list_iterator;
881 : iterator_base_class()
884 iterator_type( iterator_type const& src )
885 : iterator_base_class( src )
888 // This ctor should be protected...
889 iterator_type( list_iterator itCur, list_iterator itEnd )
890 : iterator_base_class( itCur, itEnd )
895 ///@name Forward iterators (only for debugging purpose)
899 The forward iterator for a split-list has some features:
900 - it has no post-increment operator
901 - it depends on iterator of underlying \p OrderedList
902 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
903 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
904 deleting operations it is no guarantee that you iterate all item in the set.
905 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
907 @warning Use this iterator on the concurrent container for debugging purpose only.
909 typedef iterator_type<false> iterator;
911 /// Const forward iterator
913 For iterator's features and requirements see \ref iterator
915 typedef iterator_type<true> const_iterator;
917 /// Returns a forward iterator addressing the first element in a split-list
919 For empty list \code begin() == end() \endcode
923 return iterator( m_List.begin(), m_List.end());
926 /// Returns an iterator that addresses the location succeeding the last element in a split-list
928 Do not use the value returned by <tt>end</tt> function to access any item.
930 The returned value can be used only to control reaching the end of the split-list.
931 For empty list \code begin() == end() \endcode
935 return iterator( m_List.end(), m_List.end());
938 /// Returns a forward const iterator addressing the first element in a split-list
939 const_iterator begin() const
943 /// Returns a forward const iterator addressing the first element in a split-list
944 const_iterator cbegin() const
946 return const_iterator( m_List.cbegin(), m_List.cend());
949 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
950 const_iterator end() const
954 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
955 const_iterator cend() const
957 return const_iterator( m_List.cend(), m_List.cend());
963 aux_node_type * alloc_aux_node( size_t nHash )
965 m_Stat.onHeadNodeAllocated();
966 aux_node_type* p = m_Buckets.alloc_aux_node();
972 void free_aux_node( aux_node_type * p )
974 m_Buckets.free_aux_node( p );
975 m_Stat.onHeadNodeFreed();
978 /// Calculates hash value of \p key
979 template <typename Q>
980 size_t hash_value( Q const& key ) const
982 return m_HashFunctor( key );
985 size_t bucket_no( size_t nHash ) const
987 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
990 static size_t parent_bucket( size_t nBucket )
992 assert( nBucket > 0 );
993 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
996 aux_node_type * init_bucket( size_t nBucket )
998 assert( nBucket > 0 );
999 size_t nParent = parent_bucket( nBucket );
1001 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
1002 if ( pParentBucket == nullptr ) {
1003 pParentBucket = init_bucket( nParent );
1004 m_Stat.onRecursiveInitBucket();
1007 assert( pParentBucket != nullptr );
1009 // Allocate a dummy node for new bucket
1010 aux_node_type * pBucket;
1011 if ( ( pBucket = m_Buckets.bucket( nBucket )) == nullptr ) {
1012 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
1014 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
1015 m_Buckets.bucket( nBucket, pBucket );
1016 m_Stat.onNewBucket();
1020 // Another thread set the bucket. Wait while it done
1021 free_aux_node( pBucket );
1025 // There are no free buckets. It means that the bucket table is full
1026 // Wait while another thread set th bucket
1027 m_Stat.onBucketsExhausted();
1033 // Another thread set the bucket. Wait while it done
1035 // In this point, we must wait while nBucket is empty.
1036 // The compiler can decide that waiting loop can be "optimized" (stripped)
1037 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
1039 m_Stat.onBucketInitContenton();
1042 aux_node_type volatile * p = m_Buckets.bucket( nBucket );
1044 return const_cast<aux_node_type *>(p);
1046 m_Stat.onBusyWaitBucketInit();
1050 aux_node_type * get_bucket( size_t nHash )
1052 size_t nBucket = bucket_no( nHash );
1054 aux_node_type * pHead = m_Buckets.bucket( nBucket );
1055 if ( pHead == nullptr )
1056 pHead = init_bucket( nBucket );
1058 assert( pHead->is_dummy() );
1065 // GC and OrderedList::gc must be the same
1066 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
1068 // atomicity::empty_item_counter is not allowed as a item counter
1069 static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
1070 "cds::atomicity::empty_item_counter is not allowed as a item counter");
1072 // Initialize bucket 0
1073 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
1074 assert( pNode != nullptr );
1076 // insert_aux_node cannot return false for empty list
1077 CDS_VERIFY( m_List.insert_aux_node( pNode ) );
1079 m_Buckets.bucket( 0, pNode );
1082 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
1084 return nBucketCount * nLoadFactor;
1087 void inc_item_count()
1089 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
1090 if ( ++m_ItemCounter <= nMaxCount )
1093 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
1094 const size_t nBucketCount = static_cast<size_t>(1) << sz;
1095 if ( nBucketCount < m_Buckets.capacity() ) {
1096 // we may grow the bucket table
1097 const size_t nLoadFactor = m_Buckets.load_factor();
1098 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ) )
1099 return; // someone already have updated m_nBucketCountLog2, so stop here
1101 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1102 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1103 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1106 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1109 template <typename Q, typename Compare, typename Func>
1110 bool find_( Q& val, Compare cmp, Func f )
1112 size_t nHash = hash_value( val );
1113 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ) );
1114 aux_node_type * pHead = get_bucket( nHash );
1115 assert( pHead != nullptr );
1117 return m_Stat.onFind(
1118 m_List.find_at( pHead, sv, cmp,
1119 [&f]( value_type& item, split_list::details::search_value_type<Q>& val ) { f( item, val.val ); } )
1123 template <typename Q, typename Compare>
1124 bool find_( Q const& val, Compare cmp )
1126 size_t nHash = hash_value( val );
1127 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1128 aux_node_type * pHead = get_bucket( nHash );
1129 assert( pHead != nullptr );
1131 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ) );
1134 template <typename Q, typename Compare>
1135 guarded_ptr get_( Q const& val, Compare cmp )
1137 size_t nHash = hash_value( val );
1138 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1139 aux_node_type * pHead = get_bucket( nHash );
1140 assert( pHead != nullptr );
1142 guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
1143 m_Stat.onFind( !gp.empty() );
1147 template <typename Q>
1148 guarded_ptr get_( Q const& key )
1150 return get_( key, key_comparator() );
1153 template <typename Q, typename Less>
1154 guarded_ptr get_with_( Q const& key, Less )
1156 return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
1159 template <typename Q, typename Compare, typename Func>
1160 bool erase_( Q const& val, Compare cmp, Func f )
1162 size_t nHash = hash_value( val );
1163 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1164 aux_node_type * pHead = get_bucket( nHash );
1165 assert( pHead != nullptr );
1167 if ( m_List.erase_at( pHead, sv, cmp, f ) ) {
1169 m_Stat.onEraseSuccess();
1172 m_Stat.onEraseFailed();
1176 template <typename Q, typename Compare>
1177 bool erase_( Q const& val, Compare cmp )
1179 size_t nHash = hash_value( val );
1180 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1181 aux_node_type * pHead = get_bucket( nHash );
1182 assert( pHead != nullptr );
1184 if ( m_List.erase_at( pHead, sv, cmp ) ) {
1186 m_Stat.onEraseSuccess();
1189 m_Stat.onEraseFailed();
1193 template <typename Q, typename Compare>
1194 guarded_ptr extract_( Q const& val, Compare cmp )
1196 size_t nHash = hash_value( val );
1197 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ) );
1198 aux_node_type * pHead = get_bucket( nHash );
1199 assert( pHead != nullptr );
1201 guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
1204 m_Stat.onExtractSuccess();
1207 m_Stat.onExtractFailed();
1211 template <typename Q>
1212 guarded_ptr extract_( Q const& key )
1214 return extract_( key, key_comparator() );
1217 template <typename Q, typename Less>
1218 guarded_ptr extract_with_( Q const& key, Less )
1220 return extract_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
1226 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1228 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1229 padded_bucket_table m_Buckets; ///< bucket table
1231 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1232 padded_ordered_list m_List; ///< Ordered list containing split-list items
1234 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1235 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
1236 item_counter m_ItemCounter; ///< Item counter
1237 hash m_HashFunctor; ///< Hash functor
1238 stat m_Stat; ///< Internal statistics
1242 }} // namespace cds::intrusive
1244 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H