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_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 comparison
96 functor for the type \p T and other features specific for the ordered list.
97 - \p Traits - split-list traits, default is \p split_list::traits.
98 Instead of defining \p Traits struct you can use option-based syntax provided by \p split_list::make_traits metafunction.
100 There are several specialization of the split-list class for different \p GC:
101 - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
102 \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
103 - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
104 \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
106 \anchor cds_SplitList_hash_functor
109 Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
110 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
111 the hash values of these keys must be equal too.
112 The hash functor \p Traits::hash should accept parameters of both type:
116 std::string key_ ; // key field
122 size_t operator()( const std::string& s ) const
124 return std::hash( s );
127 size_t operator()( const Foo& f ) const
129 return (*this)( f.key_ );
136 Split-list based on \p IterableList differs from split-list based on \p MichaelList or \p LazyList
137 because \p %IterableList stores data "as is" - it cannot use any hook.
139 Suppose, your split-list contains values of type \p Foo.
140 For \p %MichaelList and \p %LazyList, \p Foo declaration should be based on ordered-list node:
143 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
145 // ... field declarations
150 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::lazy_list::node< cds::gc::HP > >
152 // ... field declarations
156 For \p %IterableList, \p Foo should be based on \p void:
158 struct Foo: public cds::intrusive::split_list::node<void>
160 // ... field declarations
164 Everything else is the same.
165 Consider split-list based on \p MichaelList.
167 First, you should choose ordered list type to use in your split-list set:
169 // For gc::HP-based MichaelList implementation
170 #include <cds/intrusive/michael_list_hp.h>
172 // cds::intrusive::SplitListSet declaration
173 #include <cds/intrusive/split_list.h>
176 // Note you should declare your struct based on cds::intrusive::split_list::node
177 // which is a wrapper for ordered-list node struct.
178 // In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
179 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
181 std::string key_ ; // key field
182 unsigned val_ ; // value field
183 // ... other value fields
186 // Declare comparator for the item
189 int operator()( const Foo& f1, const Foo& f2 ) const
191 return f1.key_.compare( f2.key_ );
195 // Declare base ordered-list type for split-list
196 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
197 typename cds::intrusive::michael_list::make_traits<
199 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
200 // item comparator option
201 ,cds::opt::compare< FooCmp >
206 Second, you should declare split-list set container:
209 // Declare hash functor
210 // Note, the hash functor accepts parameter type Foo and std::string
212 size_t operator()( const Foo& f ) const
214 return cds::opt::v::hash<std::string>()( f.key_ );
216 size_t operator()( const std::string& s ) const
218 return cds::opt::v::hash<std::string>()( s );
222 // Split-list set typedef
223 typedef cds::intrusive::SplitListSet<
226 ,typename cds::intrusive::split_list::make_traits<
227 cds::opt::hash< FooHash >
232 Now, you can use \p Foo_set in your application.
238 fooSet.insert( *foo );
246 # ifdef CDS_DOXYGEN_INVOKED
247 class Traits = split_list::traits
255 typedef GC gc; ///< Garbage collector
256 typedef Traits traits; ///< Set traits
260 typedef split_list::details::rebind_list_traits<OrderedList, traits> ordered_list_adapter;
264 # ifdef CDS_DOXYGEN_INVOKED
265 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
267 typedef typename ordered_list_adapter::result ordered_list;
269 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
270 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
271 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
273 /// Hash functor for \p %value_type and all its derivatives you use
274 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
276 typedef typename traits::bit_reversal bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal
277 typedef typename traits::item_counter item_counter; ///< Item counter type
278 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
279 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
280 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
281 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
283 /// Count of hazard pointer required
284 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
288 typedef split_list::node<typename ordered_list_adapter::ordered_list_node_type> node_type; ///< split-list node type
289 typedef typename ordered_list_adapter::node_traits node_traits;
291 /// Bucket table implementation
292 typedef typename split_list::details::bucket_table_selector<
293 traits::dynamic_bucket_table
295 , typename ordered_list_adapter::aux_node
296 , opt::allocator< typename traits::allocator >
297 , opt::memory_model< memory_model >
298 , opt::free_list< typename traits::free_list >
299 >::type bucket_table;
301 typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
306 /// Ordered list wrapper to access protected members
307 class ordered_list_wrapper: public ordered_list
309 typedef ordered_list base_class;
310 typedef typename base_class::auxiliary_head bucket_head_type;
313 bool insert_at( aux_node_type* pHead, value_type& val )
315 assert( pHead != nullptr );
316 bucket_head_type h(pHead);
317 return base_class::insert_at( h, val );
320 template <typename Func>
321 bool insert_at( aux_node_type * pHead, value_type& val, Func f )
323 assert( pHead != nullptr );
324 bucket_head_type h(pHead);
325 return base_class::insert_at( h, val, f );
328 template <typename Func>
329 std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
331 assert( pHead != nullptr );
332 bucket_head_type h(pHead);
333 return base_class::update_at( h, val, func, bAllowInsert );
336 template <typename Q>
337 typename std::enable_if<
338 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
339 std::pair<bool, bool>
341 upsert_at( aux_node_type * pHead, Q& val, bool bAllowInsert )
343 assert( pHead != nullptr );
344 bucket_head_type h( pHead );
345 return base_class::upsert_at( h, val, bAllowInsert );
348 bool unlink_at( aux_node_type * pHead, value_type& val )
350 assert( pHead != nullptr );
351 bucket_head_type h(pHead);
352 return base_class::unlink_at( h, val );
355 template <typename Iterator>
356 typename std::enable_if<
357 std::is_same< Iterator, typename ordered_list::iterator>::value && is_iterable_list< ordered_list >::value,
360 erase_at( Iterator iter )
362 return base_class::erase_at( iter );
365 template <typename Q, typename Compare, typename Func>
366 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
368 assert( pHead != nullptr );
369 bucket_head_type h(pHead);
370 return base_class::erase_at( h, val, cmp, f );
373 template <typename Q, typename Compare>
374 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
376 assert( pHead != nullptr );
377 bucket_head_type h(pHead);
378 return base_class::erase_at( h, val, cmp );
381 template <typename Q, typename Compare>
382 guarded_ptr extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
384 assert( pHead != nullptr );
385 bucket_head_type h(pHead);
386 return base_class::extract_at( h, val, cmp );
389 template <typename Q, typename Compare, typename Func>
390 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
392 assert( pHead != nullptr );
393 bucket_head_type h(pHead);
394 return base_class::find_at( h, val, cmp, f );
397 template <typename Q, typename Compare>
398 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
400 assert( pHead != nullptr );
401 bucket_head_type h(pHead);
402 return base_class::find_at( h, val, cmp );
405 template <typename Q, typename Compare>
406 typename std::enable_if<
407 std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value,
408 typename base_class::iterator
410 find_iterator_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
412 assert( pHead != nullptr );
413 bucket_head_type h( pHead );
414 return base_class::find_iterator_at( h, val, cmp );
417 template <typename Q, typename Compare>
418 guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
420 assert( pHead != nullptr );
421 bucket_head_type h(pHead);
422 return base_class::get_at( h, val, cmp );
425 bool insert_aux_node( aux_node_type * pNode )
427 return base_class::insert_aux_node( pNode );
429 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
431 bucket_head_type h(pHead);
432 return base_class::insert_aux_node( h, pNode );
435 template <typename Predicate>
436 void destroy( Predicate pred )
438 base_class::destroy( pred );
445 template <bool IsConst>
447 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
449 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
450 typedef typename iterator_base_class::list_iterator list_iterator;
452 friend class SplitListSet;
456 : iterator_base_class()
459 iterator_type( iterator_type const& src )
460 : iterator_base_class( src )
463 // This ctor should be protected...
464 iterator_type( list_iterator itCur, list_iterator itEnd )
465 : iterator_base_class( itCur, itEnd )
471 ///@name Forward iterators
475 The forward iterator is based on \p OrderedList forward iterator and has some features:
476 - it has no post-increment operator
477 - it iterates items in unordered fashion
478 - iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
480 Iterator thread safety depends on type of \p OrderedList:
481 - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
482 because that item is guarded by hazard pointer.
483 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
484 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
485 Use this iterator on the concurrent container for debugging purpose only.
486 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
488 typedef iterator_type<false> iterator;
490 /// Const forward iterator
492 For iterator's features and requirements see \ref iterator
494 typedef iterator_type<true> const_iterator;
496 /// Returns a forward iterator addressing the first element in a split-list
498 For empty list \code begin() == end() \endcode
502 return iterator( m_List.begin(), m_List.end());
505 /// Returns an iterator that addresses the location succeeding the last element in a split-list
507 Do not use the value returned by <tt>end</tt> function to access any item.
509 The returned value can be used only to control reaching the end of the split-list.
510 For empty list \code begin() == end() \endcode
514 return iterator( m_List.end(), m_List.end());
517 /// Returns a forward const iterator addressing the first element in a split-list
518 const_iterator begin() const
522 /// Returns a forward const iterator addressing the first element in a split-list
523 const_iterator cbegin() const
525 return const_iterator( m_List.cbegin(), m_List.cend());
528 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
529 const_iterator end() const
533 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
534 const_iterator cend() const
536 return const_iterator( m_List.cend(), m_List.cend());
541 /// Initialize split-ordered list of default capacity
543 The default capacity is defined in bucket table constructor.
544 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
545 which selects by \p split_list::dynamic_bucket_table option.
548 : m_nBucketCountLog2(1)
549 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
554 /// Initialize split-ordered list
556 size_t nItemCount ///< estimate average of item count
557 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
559 : m_Buckets( nItemCount, nLoadFactor )
560 , m_nBucketCountLog2(1)
561 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
566 /// Destroys split-list set
569 // list contains aux node that cannot be retired
570 // all aux nodes will be destroyed by bucket table dtor
572 []( node_type * pNode ) -> bool {
573 return !pNode->is_dummy();
582 The function inserts \p val in the set if it does not contain
583 an item with key equal to \p val.
585 Returns \p true if \p val is placed into the set, \p false otherwise.
587 bool insert( value_type& val )
589 size_t nHash = hash_value( val );
590 aux_node_type * pHead = get_bucket( nHash );
591 assert( pHead != nullptr );
593 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
595 if ( m_List.insert_at( pHead, val )) {
597 m_Stat.onInsertSuccess();
600 m_Stat.onInsertFailed();
606 This function is intended for derived non-intrusive containers.
608 The function allows to split creating of new item into two part:
609 - create item with key only
610 - insert new item into the set
611 - if inserting is success, calls \p f functor to initialize value-field of \p val.
613 The functor signature is:
615 void func( value_type& val );
617 where \p val is the item inserted.
618 The user-defined functor is called only if the inserting is success.
620 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
621 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
624 template <typename Func>
625 bool insert( value_type& val, Func f )
627 size_t nHash = hash_value( val );
628 aux_node_type * pHead = get_bucket( nHash );
629 assert( pHead != nullptr );
631 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
633 if ( m_List.insert_at( pHead, val, f )) {
635 m_Stat.onInsertSuccess();
638 m_Stat.onInsertFailed();
644 The operation performs inserting or changing data with lock-free manner.
646 If the item \p val is not found in the set, then \p val is inserted
647 iff \p bAllowInsert is \p true.
648 Otherwise, the functor \p func is called with item found.
650 The functor signature depends of the type of \p OrderedList:
652 <b>for \p MichaelList, \p LazyList</b>
655 void operator()( bool bNew, value_type& item, value_type& val );
659 - \p bNew - \p true if the item has been inserted, \p false otherwise
660 - \p item - item of the set
661 - \p val - argument \p val passed into the \p %update() function
662 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
663 refers to the same thing.
665 The functor may change non-key fields of the \p item.
666 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
667 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
670 <b>for \p IterableList</b>
672 void func( value_type& val, value_type * old );
675 - \p val - argument \p val passed into the \p %update() function
676 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
678 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
679 \p second is \p true if new item has been added or \p false if the item with \p val
680 already is in the list.
682 template <typename Func>
683 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
685 size_t nHash = hash_value( val );
686 aux_node_type * pHead = get_bucket( nHash );
687 assert( pHead != nullptr );
689 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
691 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
692 if ( bRet.first && bRet.second ) {
694 m_Stat.onUpdateNew();
697 m_Stat.onUpdateExist();
701 template <typename Func>
702 CDS_DEPRECATED("ensure() is deprecated, use update()")
703 std::pair<bool, bool> ensure( value_type& val, Func func )
705 return update( val, func, true );
709 /// Inserts or updates the node (only for \p IterableList)
711 The operation performs inserting or changing data with lock-free manner.
713 If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
714 Otherwise, the current element is changed to \p val, the old element will be retired later
715 by call \p Traits::disposer.
717 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
718 \p second is \p true if \p val has been added or \p false if the item with that key
721 #ifdef CDS_DOXYGEN_INVOKED
722 std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
724 template <typename Q>
725 typename std::enable_if<
726 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
727 std::pair<bool, bool>
729 upsert( Q& val, bool bAllowInsert = true )
732 size_t nHash = hash_value( val );
733 aux_node_type * pHead = get_bucket( nHash );
734 assert( pHead != nullptr );
736 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
738 std::pair<bool, bool> bRet = m_List.upsert_at( pHead, val, bAllowInsert );
739 if ( bRet.first && bRet.second ) {
741 m_Stat.onUpdateNew();
744 m_Stat.onUpdateExist();
748 /// Unlinks the item \p val from the set
750 The function searches the item \p val in the set and unlinks it from the set
751 if it is found and is equal to \p val.
753 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
754 and deletes the item found. \p unlink finds an item by key and deletes it
755 only if \p val is an item of that set, i.e. the pointer to item found
756 is equal to <tt> &val </tt>.
758 The function returns \p true if success and \p false otherwise.
760 bool unlink( value_type& val )
762 size_t nHash = hash_value( val );
763 aux_node_type * pHead = get_bucket( nHash );
764 assert( pHead != nullptr );
766 if ( m_List.unlink_at( pHead, val )) {
768 m_Stat.onEraseSuccess();
771 m_Stat.onEraseFailed();
775 /// Deletes the item from the set
776 /** \anchor cds_intrusive_SplitListSet_hp_erase
777 The function searches an item with key equal to \p key in the set,
778 unlinks it from the set, and returns \p true.
779 If the item with key equal to \p key is not found the function return \p false.
781 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
782 and deletes the item found. \p unlink finds an item by key and deletes it
783 only if \p key is an item of that set, i.e. the pointer to item found
784 is equal to <tt> &key </tt>.
786 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
788 template <typename Q>
789 bool erase( Q const& key )
791 return erase_( key, key_comparator());
794 /// Deletes the item from the set with comparing functor \p pred
797 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
798 but \p pred predicate is used for key comparing.
799 \p Less has the interface like \p std::less.
800 \p pred must imply the same element order as the comparator used for building the set.
802 template <typename Q, typename Less>
803 bool erase_with( const Q& key, Less pred )
806 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
809 /// Deletes the item from the set
810 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
811 The function searches an item with key equal to \p key in the set,
812 call \p f functor with item found, unlinks it from the set, and returns \p true.
813 The \ref disposer specified by \p OrderedList class template parameter is called
814 by garbage collector \p GC asynchronously.
816 The \p Func interface is
819 void operator()( value_type const& item );
823 If the item with key equal to \p key is not found the function return \p false.
825 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
827 template <typename Q, typename Func>
828 bool erase( Q const& key, Func f )
830 return erase_( key, key_comparator(), f );
833 /// Deletes the item from the set with comparing functor \p pred
835 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
836 but \p pred predicate is used for key comparing.
837 \p Less has the interface like \p std::less.
838 \p pred must imply the same element order as the comparator used for building the set.
840 template <typename Q, typename Less, typename Func>
841 bool erase_with( Q const& key, Less pred, Func f )
844 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
847 /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
849 Returns \p true if the operation is successful, \p false otherwise.
850 The function can return \p false if the node the iterator points to has already been deleted
853 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
855 @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList.
857 #ifdef CDS_DOXYGEN_INVOKED
858 bool erase_at( iterator const& iter )
860 template <typename Iterator>
861 typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
862 erase_at( Iterator const& iter )
865 assert( iter != end());
867 if ( m_List.erase_at( iter.underlying_iterator())) {
869 m_Stat.onEraseSuccess();
875 /// Extracts the item with specified \p key
876 /** \anchor cds_intrusive_SplitListSet_hp_extract
877 The function searches an item with key equal to \p key,
878 unlinks it from the set, and returns it as \p guarded_ptr.
879 If \p key is not found the function returns an empty guarded pointer.
881 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
883 The \p disposer specified in \p OrderedList class' template parameter is called automatically
884 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
885 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
889 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
890 splitlist_set theSet;
893 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
898 // Destructor of gp releases internal HP guard
902 template <typename Q>
903 guarded_ptr extract( Q const& key )
905 return extract_( key );
908 /// Extracts the item using compare functor \p pred
910 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
911 but \p pred predicate is used for key comparing.
913 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
915 \p pred must imply the same element order as the comparator used for building the set.
917 template <typename Q, typename Less>
918 guarded_ptr extract_with( Q const& key, Less pred )
920 return extract_with_( key, pred );
923 /// Finds the key \p key
924 /** \anchor cds_intrusive_SplitListSet_hp_find_func
925 The function searches the item with key equal to \p key and calls the functor \p f for item found.
926 The interface of \p Func functor is:
929 void operator()( value_type& item, Q& key );
932 where \p item is the item found, \p key is the <tt>find</tt> function argument.
934 The functor can change non-key fields of \p item. Note that the functor is only guarantee
935 that \p item cannot be disposed during functor is executing.
936 The functor does not serialize simultaneous access to the set \p item. If such access is
937 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
939 Note the hash functor specified for class \p Traits template parameter
940 should accept a parameter of type \p Q that can be not the same as \p value_type.
942 The function returns \p true if \p key is found, \p false otherwise.
944 template <typename Q, typename Func>
945 bool find( Q& key, Func f )
947 return find_( key, key_comparator(), f );
950 template <typename Q, typename Func>
951 bool find( Q const& key, Func f )
953 return find_( key, key_comparator(), f );
957 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
959 If \p key is not found the function returns \p end().
961 @note This function is supported only for the set based on \p IterableList
963 template <typename Q>
964 #ifdef CDS_DOXYGEN_INVOKED
967 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
971 return find_iterator_( key, key_comparator());
974 template <typename Q>
975 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
978 return find_iterator_( key, key_comparator());
983 /// Finds the key \p key with \p pred predicate for comparing
985 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
986 but \p cmp is used for key compare.
987 \p Less has the interface like \p std::less.
988 \p cmp must imply the same element order as the comparator used for building the set.
990 template <typename Q, typename Less, typename Func>
991 bool find_with( Q& key, Less pred, Func f )
994 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
997 template <typename Q, typename Less, typename Func>
998 bool find_with( Q const& key, Less pred, Func f )
1001 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
1005 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
1007 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
1008 \p Less functor has the interface like \p std::less.
1009 \p pred must imply the same element order as the comparator used for building the set.
1011 If \p key is not found the function returns \p end().
1013 @note This function is supported only for the set based on \p IterableList
1015 template <typename Q, typename Less>
1016 #ifdef CDS_DOXYGEN_INVOKED
1019 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
1021 find_with( Q& key, Less pred )
1024 return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1027 template <typename Q, typename Less>
1028 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
1029 find_with( Q const& key, Less pred )
1032 return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1037 /// Checks whether the set contains \p key
1039 The function searches the item with key equal to \p key
1040 and returns \p true if it is found, and \p false otherwise.
1042 Note the hash functor specified for class \p Traits template parameter
1043 should accept a parameter of type \p Q that can be not the same as \p value_type.
1044 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
1046 template <typename Q>
1047 bool contains( Q const& key )
1049 return find_( key, key_comparator());
1052 /// Checks whether the set contains \p key using \p pred predicate for searching
1054 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
1055 \p Less functor has the interface like \p std::less.
1056 \p Less must imply the same element order as the comparator used for building the set.
1058 template <typename Q, typename Less>
1059 bool contains( Q const& key, Less pred )
1062 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1065 /// Finds the key \p key and return the item found
1066 /** \anchor cds_intrusive_SplitListSet_hp_get
1067 The function searches the item with key equal to \p key
1068 and returns the item found as \p guarded_ptr.
1069 If \p key is not found the function returns an empty guarded pointer.
1071 The \p disposer specified in \p OrderedList class' template parameter is called
1072 by garbage collector \p GC automatically when returned \p guarded_ptr object
1073 will be destroyed or released.
1074 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1078 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
1079 splitlist_set theSet;
1082 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1087 // Destructor of guarded_ptr releases internal HP guard
1091 Note the compare functor specified for \p OrderedList template parameter
1092 should accept a parameter of type \p Q that can be not the same as \p value_type.
1094 template <typename Q>
1095 guarded_ptr get( Q const& key )
1100 /// Finds the key \p key and return the item found
1102 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1103 but \p pred is used for comparing the keys.
1105 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1107 \p pred must imply the same element order as the comparator used for building the set.
1109 template <typename Q, typename Less>
1110 guarded_ptr get_with( Q const& key, Less pred )
1112 return get_with_( key, pred );
1115 /// Returns item count in the set
1118 return m_ItemCounter;
1121 /// Checks if the set is empty
1123 Emptiness is checked by item counting: if item count is zero then the set is empty.
1124 Thus, the correct item counting feature is an important part of split-list set implementation.
1131 /// Clears the set (non-atomic)
1133 The function unlink all items from the set.
1134 The function is not atomic. After call the split-list can be non-empty.
1136 For each item the \p disposer is called after unlinking.
1140 iterator it = begin();
1141 while ( it != end()) {
1149 /// Returns internal statistics
1150 stat const& statistics() const
1155 /// Returns internal statistics for \p OrderedList
1156 typename OrderedList::stat const& list_statistics() const
1158 return m_List.statistics();
1163 aux_node_type * alloc_aux_node( size_t nHash )
1165 m_Stat.onHeadNodeAllocated();
1166 aux_node_type* p = m_Buckets.alloc_aux_node();
1168 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
1169 // p->m_nHash is read-only data member
1171 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
1173 cds_assert( !p->m_busy.load( atomics::memory_order_acquire ));
1174 p->m_busy.store( true, atomics::memory_order_release );
1180 void free_aux_node( aux_node_type * p )
1183 cds_assert( p->m_busy.load( atomics::memory_order_acquire ));
1184 p->m_busy.store( false, atomics::memory_order_release );
1187 m_Buckets.free_aux_node( p );
1188 m_Stat.onHeadNodeFreed();
1191 /// Calculates hash value of \p key
1192 template <typename Q>
1193 size_t hash_value( Q const& key ) const
1195 return m_HashFunctor( key );
1198 size_t bucket_no( size_t nHash ) const
1200 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
1203 static size_t parent_bucket( size_t nBucket )
1205 assert( nBucket > 0 );
1206 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
1209 aux_node_type * init_bucket( size_t const nBucket )
1211 assert( nBucket > 0 );
1212 size_t nParent = parent_bucket( nBucket );
1214 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
1215 if ( pParentBucket == nullptr ) {
1216 pParentBucket = init_bucket( nParent );
1217 m_Stat.onRecursiveInitBucket();
1220 assert( pParentBucket != nullptr );
1222 // Allocate an aux node for new bucket
1223 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
1226 for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
1230 pBucket = alloc_aux_node( split_list::dummy_hash<bit_reversal>( nBucket ));
1232 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
1233 m_Buckets.bucket( nBucket, pBucket );
1234 m_Stat.onNewBucket();
1238 // Another thread set the bucket. Wait while it done
1239 free_aux_node( pBucket );
1240 m_Stat.onBucketInitContenton();
1244 // There are no free buckets. It means that the bucket table is full
1245 // Wait while another thread set the bucket or a free bucket will be available
1246 m_Stat.onBucketsExhausted();
1250 // Another thread set the bucket. Wait while it done
1251 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
1253 m_Stat.onBusyWaitBucketInit();
1259 aux_node_type * get_bucket( size_t nHash )
1261 size_t nBucket = bucket_no( nHash );
1263 aux_node_type * pHead = m_Buckets.bucket( nBucket );
1264 if ( pHead == nullptr )
1265 pHead = init_bucket( nBucket );
1267 assert( pHead->is_dummy());
1274 // GC and OrderedList::gc must be the same
1275 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
1277 // atomicity::empty_item_counter is not allowed as a item counter
1278 static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
1279 "cds::atomicity::empty_item_counter is not allowed as a item counter");
1281 // Initialize bucket 0
1282 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash<bit_reversal>(0)*/ );
1283 assert( pNode != nullptr );
1285 // insert_aux_node cannot return false for empty list
1286 CDS_VERIFY( m_List.insert_aux_node( pNode ));
1288 m_Buckets.bucket( 0, pNode );
1291 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
1293 return nBucketCount * nLoadFactor;
1296 void inc_item_count()
1298 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
1299 if ( ++m_ItemCounter <= nMaxCount )
1302 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
1303 const size_t nBucketCount = static_cast<size_t>(1) << sz;
1304 if ( nBucketCount < m_Buckets.capacity()) {
1305 // we may grow the bucket table
1306 const size_t nLoadFactor = m_Buckets.load_factor();
1307 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1308 return; // someone already have updated m_nBucketCountLog2, so stop here
1310 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1311 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1312 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1315 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1318 template <typename Q, typename Compare, typename Func>
1319 bool find_( Q& val, Compare cmp, Func f )
1321 size_t nHash = hash_value( val );
1322 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1323 aux_node_type * pHead = get_bucket( nHash );
1324 assert( pHead != nullptr );
1326 return m_Stat.onFind(
1327 m_List.find_at( pHead, sv, cmp,
1328 [&f]( value_type& item, split_list::details::search_value_type<Q>& val ) { f( item, val.val ); } )
1332 template <typename Q, typename Compare>
1333 bool find_( Q const& val, Compare cmp )
1335 size_t nHash = hash_value( val );
1336 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1337 aux_node_type * pHead = get_bucket( nHash );
1338 assert( pHead != nullptr );
1340 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1343 template <typename Q, typename Compare>
1344 iterator find_iterator_( Q const& val, Compare cmp )
1346 size_t nHash = hash_value( val );
1347 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1348 aux_node_type * pHead = get_bucket( nHash );
1349 assert( pHead != nullptr );
1351 return iterator( m_List.find_iterator_at( pHead, sv, cmp ), m_List.end());
1354 template <typename Q, typename Compare>
1355 guarded_ptr get_( Q const& val, Compare cmp )
1357 size_t nHash = hash_value( val );
1358 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1359 aux_node_type * pHead = get_bucket( nHash );
1360 assert( pHead != nullptr );
1362 guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
1363 m_Stat.onFind( !gp.empty());
1367 template <typename Q>
1368 guarded_ptr get_( Q const& key )
1370 return get_( key, key_comparator());
1373 template <typename Q, typename Less>
1374 guarded_ptr get_with_( Q const& key, Less )
1376 return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1379 template <typename Q, typename Compare, typename Func>
1380 bool erase_( Q const& val, Compare cmp, Func f )
1382 size_t nHash = hash_value( val );
1383 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1384 aux_node_type * pHead = get_bucket( nHash );
1385 assert( pHead != nullptr );
1387 if ( m_List.erase_at( pHead, sv, cmp, f )) {
1389 m_Stat.onEraseSuccess();
1392 m_Stat.onEraseFailed();
1396 template <typename Q, typename Compare>
1397 bool erase_( Q const& val, Compare cmp )
1399 size_t nHash = hash_value( val );
1400 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1401 aux_node_type * pHead = get_bucket( nHash );
1402 assert( pHead != nullptr );
1404 if ( m_List.erase_at( pHead, sv, cmp )) {
1406 m_Stat.onEraseSuccess();
1409 m_Stat.onEraseFailed();
1413 template <typename Q, typename Compare>
1414 guarded_ptr extract_( Q const& val, Compare cmp )
1416 size_t nHash = hash_value( val );
1417 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1418 aux_node_type * pHead = get_bucket( nHash );
1419 assert( pHead != nullptr );
1421 guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
1424 m_Stat.onExtractSuccess();
1427 m_Stat.onExtractFailed();
1431 template <typename Q>
1432 guarded_ptr extract_( Q const& key )
1434 return extract_( key, key_comparator());
1437 template <typename Q, typename Less>
1438 guarded_ptr extract_with_( Q const& key, Less )
1440 return extract_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1446 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1448 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1449 padded_bucket_table m_Buckets; ///< bucket table
1451 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1452 padded_ordered_list m_List; ///< Ordered list containing split-list items
1454 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1455 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
1456 hash m_HashFunctor; ///< Hash functor
1457 item_counter m_ItemCounter; ///< Item counter
1458 stat m_Stat; ///< Internal statistics
1462 }} // namespace cds::intrusive
1464 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H