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::item_counter item_counter; ///< Item counter type
277 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
278 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
279 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
280 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
282 /// Count of hazard pointer required
283 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
287 typedef split_list::node<typename ordered_list_adapter::ordered_list_node_type> node_type; ///< split-list node type
288 typedef typename ordered_list_adapter::node_traits node_traits;
290 /// Bucket table implementation
291 typedef typename split_list::details::bucket_table_selector<
292 traits::dynamic_bucket_table
294 , typename ordered_list_adapter::aux_node
295 , opt::allocator< typename traits::allocator >
296 , opt::memory_model< memory_model >
297 , opt::free_list< typename traits::free_list >
298 >::type bucket_table;
300 typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
305 /// Ordered list wrapper to access protected members
306 class ordered_list_wrapper: public ordered_list
308 typedef ordered_list base_class;
309 typedef typename base_class::auxiliary_head bucket_head_type;
312 bool insert_at( aux_node_type* pHead, value_type& val )
314 assert( pHead != nullptr );
315 bucket_head_type h(pHead);
316 return base_class::insert_at( h, val );
319 template <typename Func>
320 bool insert_at( aux_node_type * pHead, value_type& val, Func f )
322 assert( pHead != nullptr );
323 bucket_head_type h(pHead);
324 return base_class::insert_at( h, val, f );
327 template <typename Func>
328 std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
330 assert( pHead != nullptr );
331 bucket_head_type h(pHead);
332 return base_class::update_at( h, val, func, bAllowInsert );
335 template <typename Q>
336 typename std::enable_if<
337 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
338 std::pair<bool, bool>
340 upsert_at( aux_node_type * pHead, Q& val, bool bAllowInsert )
342 assert( pHead != nullptr );
343 bucket_head_type h( pHead );
344 return base_class::upsert_at( h, val, bAllowInsert );
347 bool unlink_at( aux_node_type * pHead, value_type& val )
349 assert( pHead != nullptr );
350 bucket_head_type h(pHead);
351 return base_class::unlink_at( h, val );
354 template <typename Q, typename Compare, typename Func>
355 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
357 assert( pHead != nullptr );
358 bucket_head_type h(pHead);
359 return base_class::erase_at( h, val, cmp, f );
362 template <typename Q, typename Compare>
363 bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
365 assert( pHead != nullptr );
366 bucket_head_type h(pHead);
367 return base_class::erase_at( h, val, cmp );
370 template <typename Q, typename Compare>
371 guarded_ptr extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
373 assert( pHead != nullptr );
374 bucket_head_type h(pHead);
375 return base_class::extract_at( h, val, cmp );
378 template <typename Q, typename Compare, typename Func>
379 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
381 assert( pHead != nullptr );
382 bucket_head_type h(pHead);
383 return base_class::find_at( h, val, cmp, f );
386 template <typename Q, typename Compare>
387 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
389 assert( pHead != nullptr );
390 bucket_head_type h(pHead);
391 return base_class::find_at( h, val, cmp );
394 template <typename Q, typename Compare>
395 typename std::enable_if<
396 std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value,
397 typename base_class::iterator
399 find_iterator_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
401 assert( pHead != nullptr );
402 bucket_head_type h( pHead );
403 return base_class::find_iterator_at( h, val, cmp );
406 template <typename Q, typename Compare>
407 guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
409 assert( pHead != nullptr );
410 bucket_head_type h(pHead);
411 return base_class::get_at( h, val, cmp );
414 bool insert_aux_node( aux_node_type * pNode )
416 return base_class::insert_aux_node( pNode );
418 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
420 bucket_head_type h(pHead);
421 return base_class::insert_aux_node( h, pNode );
424 template <typename Predicate>
425 void destroy( Predicate pred )
427 base_class::destroy( pred );
434 template <bool IsConst>
436 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
438 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
439 typedef typename iterator_base_class::list_iterator list_iterator;
442 : iterator_base_class()
445 iterator_type( iterator_type const& src )
446 : iterator_base_class( src )
449 // This ctor should be protected...
450 iterator_type( list_iterator itCur, list_iterator itEnd )
451 : iterator_base_class( itCur, itEnd )
457 ///@name Forward iterators
461 The forward iterator is based on \p OrderedList forward iterator and has some features:
462 - it has no post-increment operator
463 - it iterates items in unordered fashion
464 - iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
466 Iterator thread safety depends on type of \p OrderedList:
467 - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
468 because that item is guarded by hazard pointer.
469 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
470 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
471 Use this iterator on the concurrent container for debugging purpose only.
472 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
474 typedef iterator_type<false> iterator;
476 /// Const forward iterator
478 For iterator's features and requirements see \ref iterator
480 typedef iterator_type<true> const_iterator;
482 /// Returns a forward iterator addressing the first element in a split-list
484 For empty list \code begin() == end() \endcode
488 return iterator( m_List.begin(), m_List.end());
491 /// Returns an iterator that addresses the location succeeding the last element in a split-list
493 Do not use the value returned by <tt>end</tt> function to access any item.
495 The returned value can be used only to control reaching the end of the split-list.
496 For empty list \code begin() == end() \endcode
500 return iterator( m_List.end(), m_List.end());
503 /// Returns a forward const iterator addressing the first element in a split-list
504 const_iterator begin() const
508 /// Returns a forward const iterator addressing the first element in a split-list
509 const_iterator cbegin() const
511 return const_iterator( m_List.cbegin(), m_List.cend());
514 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
515 const_iterator end() const
519 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
520 const_iterator cend() const
522 return const_iterator( m_List.cend(), m_List.cend());
527 /// Initialize split-ordered list of default capacity
529 The default capacity is defined in bucket table constructor.
530 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
531 which selects by \p split_list::dynamic_bucket_table option.
534 : m_nBucketCountLog2(1)
535 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
540 /// Initialize split-ordered list
542 size_t nItemCount ///< estimate average of item count
543 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
545 : m_Buckets( nItemCount, nLoadFactor )
546 , m_nBucketCountLog2(1)
547 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
552 /// Destroys split-list set
555 // list contains aux node that cannot be retired
556 // all aux nodes will be destroyed by bucket table dtor
558 []( node_type * pNode ) -> bool {
559 return !pNode->is_dummy();
568 The function inserts \p val in the set if it does not contain
569 an item with key equal to \p val.
571 Returns \p true if \p val is placed into the set, \p false otherwise.
573 bool insert( value_type& val )
575 size_t nHash = hash_value( val );
576 aux_node_type * pHead = get_bucket( nHash );
577 assert( pHead != nullptr );
579 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
581 if ( m_List.insert_at( pHead, val )) {
583 m_Stat.onInsertSuccess();
586 m_Stat.onInsertFailed();
592 This function is intended for derived non-intrusive containers.
594 The function allows to split creating of new item into two part:
595 - create item with key only
596 - insert new item into the set
597 - if inserting is success, calls \p f functor to initialize value-field of \p val.
599 The functor signature is:
601 void func( value_type& val );
603 where \p val is the item inserted.
604 The user-defined functor is called only if the inserting is success.
606 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
607 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
610 template <typename Func>
611 bool insert( value_type& val, Func f )
613 size_t nHash = hash_value( val );
614 aux_node_type * pHead = get_bucket( nHash );
615 assert( pHead != nullptr );
617 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
619 if ( m_List.insert_at( pHead, val, f )) {
621 m_Stat.onInsertSuccess();
624 m_Stat.onInsertFailed();
630 The operation performs inserting or changing data with lock-free manner.
632 If the item \p val is not found in the set, then \p val is inserted
633 iff \p bAllowInsert is \p true.
634 Otherwise, the functor \p func is called with item found.
636 The functor signature depends of the type of \p OrderedList:
638 <b>for \p MichaelList, \p LazyList</b>
641 void operator()( bool bNew, value_type& item, value_type& val );
645 - \p bNew - \p true if the item has been inserted, \p false otherwise
646 - \p item - item of the set
647 - \p val - argument \p val passed into the \p %update() function
648 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
649 refers to the same thing.
651 The functor may change non-key fields of the \p item.
652 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
653 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
656 <b>for \p IterableList</b>
658 void func( value_type& val, value_type * old );
661 - \p val - argument \p val passed into the \p %update() function
662 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
664 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
665 \p second is \p true if new item has been added or \p false if the item with \p val
666 already is in the list.
668 template <typename Func>
669 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
671 size_t nHash = hash_value( val );
672 aux_node_type * pHead = get_bucket( nHash );
673 assert( pHead != nullptr );
675 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
677 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
678 if ( bRet.first && bRet.second ) {
680 m_Stat.onUpdateNew();
683 m_Stat.onUpdateExist();
687 template <typename Func>
688 CDS_DEPRECATED("ensure() is deprecated, use update()")
689 std::pair<bool, bool> ensure( value_type& val, Func func )
691 return update( val, func, true );
695 /// Inserts or updates the node (only for \p IterableList)
697 The operation performs inserting or changing data with lock-free manner.
699 If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
700 Otherwise, the current element is changed to \p val, the old element will be retired later
701 by call \p Traits::disposer.
703 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
704 \p second is \p true if \p val has been added or \p false if the item with that key
707 #ifdef CDS_DOXYGEN_INVOKED
708 std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
710 template <typename Q>
711 typename std::enable_if<
712 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
713 std::pair<bool, bool>
715 upsert( Q& val, bool bAllowInsert = true )
718 size_t nHash = hash_value( val );
719 aux_node_type * pHead = get_bucket( nHash );
720 assert( pHead != nullptr );
722 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
724 std::pair<bool, bool> bRet = m_List.upsert_at( pHead, val, bAllowInsert );
725 if ( bRet.first && bRet.second ) {
727 m_Stat.onUpdateNew();
730 m_Stat.onUpdateExist();
734 /// Unlinks the item \p val from the set
736 The function searches the item \p val in the set and unlinks it from the set
737 if it is found and is equal to \p val.
739 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
740 and deletes the item found. \p unlink finds an item by key and deletes it
741 only if \p val is an item of that set, i.e. the pointer to item found
742 is equal to <tt> &val </tt>.
744 The function returns \p true if success and \p false otherwise.
746 bool unlink( value_type& val )
748 size_t nHash = hash_value( val );
749 aux_node_type * pHead = get_bucket( nHash );
750 assert( pHead != nullptr );
752 if ( m_List.unlink_at( pHead, val )) {
754 m_Stat.onEraseSuccess();
757 m_Stat.onEraseFailed();
761 /// Deletes the item from the set
762 /** \anchor cds_intrusive_SplitListSet_hp_erase
763 The function searches an item with key equal to \p key in the set,
764 unlinks it from the set, and returns \p true.
765 If the item with key equal to \p key is not found the function return \p false.
767 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
768 and deletes the item found. \p unlink finds an item by key and deletes it
769 only if \p key is an item of that set, i.e. the pointer to item found
770 is equal to <tt> &key </tt>.
772 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
774 template <typename Q>
775 bool erase( Q const& key )
777 return erase_( key, key_comparator());
780 /// Deletes the item from the set with comparing functor \p pred
783 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
784 but \p pred predicate is used for key comparing.
785 \p Less has the interface like \p std::less.
786 \p pred must imply the same element order as the comparator used for building the set.
788 template <typename Q, typename Less>
789 bool erase_with( const Q& key, Less pred )
792 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
795 /// Deletes the item from the set
796 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
797 The function searches an item with key equal to \p key in the set,
798 call \p f functor with item found, unlinks it from the set, and returns \p true.
799 The \ref disposer specified by \p OrderedList class template parameter is called
800 by garbage collector \p GC asynchronously.
802 The \p Func interface is
805 void operator()( value_type const& item );
809 If the item with key equal to \p key is not found the function return \p false.
811 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
813 template <typename Q, typename Func>
814 bool erase( Q const& key, Func f )
816 return erase_( key, key_comparator(), f );
819 /// Deletes the item from the set with comparing functor \p pred
821 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
822 but \p pred predicate is used for key comparing.
823 \p Less has the interface like \p std::less.
824 \p pred must imply the same element order as the comparator used for building the set.
826 template <typename Q, typename Less, typename Func>
827 bool erase_with( Q const& key, Less pred, Func f )
830 return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
833 /// Extracts the item with specified \p key
834 /** \anchor cds_intrusive_SplitListSet_hp_extract
835 The function searches an item with key equal to \p key,
836 unlinks it from the set, and returns it as \p guarded_ptr.
837 If \p key is not found the function returns an empty guarded pointer.
839 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
841 The \p disposer specified in \p OrderedList class' template parameter is called automatically
842 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
843 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
847 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
848 splitlist_set theSet;
851 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
856 // Destructor of gp releases internal HP guard
860 template <typename Q>
861 guarded_ptr extract( Q const& key )
863 return extract_( key );
866 /// Extracts the item using compare functor \p pred
868 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
869 but \p pred predicate is used for key comparing.
871 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
873 \p pred must imply the same element order as the comparator used for building the set.
875 template <typename Q, typename Less>
876 guarded_ptr extract_with( Q const& key, Less pred )
878 return extract_with_( key, pred );
881 /// Finds the key \p key
882 /** \anchor cds_intrusive_SplitListSet_hp_find_func
883 The function searches the item with key equal to \p key and calls the functor \p f for item found.
884 The interface of \p Func functor is:
887 void operator()( value_type& item, Q& key );
890 where \p item is the item found, \p key is the <tt>find</tt> function argument.
892 The functor can change non-key fields of \p item. Note that the functor is only guarantee
893 that \p item cannot be disposed during functor is executing.
894 The functor does not serialize simultaneous access to the set \p item. If such access is
895 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
897 Note the hash functor specified for class \p Traits template parameter
898 should accept a parameter of type \p Q that can be not the same as \p value_type.
900 The function returns \p true if \p key is found, \p false otherwise.
902 template <typename Q, typename Func>
903 bool find( Q& key, Func f )
905 return find_( key, key_comparator(), f );
908 template <typename Q, typename Func>
909 bool find( Q const& key, Func f )
911 return find_( key, key_comparator(), f );
915 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
917 If \p key is not found the function returns \p end().
919 @note This function is supported only for the set based on \p IterableList
921 template <typename Q>
922 #ifdef CDS_DOXYGEN_INVOKED
925 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
929 return find_iterator_( key, key_comparator());
932 template <typename Q>
933 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
936 return find_iterator_( key, key_comparator());
941 /// Finds the key \p key with \p pred predicate for comparing
943 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
944 but \p cmp is used for key compare.
945 \p Less has the interface like \p std::less.
946 \p cmp must imply the same element order as the comparator used for building the set.
948 template <typename Q, typename Less, typename Func>
949 bool find_with( Q& key, Less pred, Func f )
952 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
955 template <typename Q, typename Less, typename Func>
956 bool find_with( Q const& key, Less pred, Func f )
959 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
963 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
965 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
966 \p Less functor has the interface like \p std::less.
967 \p pred must imply the same element order as the comparator used for building the set.
969 If \p key is not found the function returns \p end().
971 @note This function is supported only for the set based on \p IterableList
973 template <typename Q, typename Less>
974 #ifdef CDS_DOXYGEN_INVOKED
977 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
979 find_with( Q& key, Less pred )
982 return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
985 template <typename Q, typename Less>
986 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
987 find_with( Q const& key, Less pred )
990 return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
995 /// Checks whether the set contains \p key
997 The function searches the item with key equal to \p key
998 and returns \p true if it is found, and \p false otherwise.
1000 Note the hash functor specified for class \p Traits template parameter
1001 should accept a parameter of type \p Q that can be not the same as \p value_type.
1002 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
1004 template <typename Q>
1005 bool contains( Q const& key )
1007 return find_( key, key_comparator());
1010 /// Checks whether the set contains \p key using \p pred predicate for searching
1012 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
1013 \p Less functor has the interface like \p std::less.
1014 \p Less must imply the same element order as the comparator used for building the set.
1016 template <typename Q, typename Less>
1017 bool contains( Q const& key, Less pred )
1020 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1023 /// Finds the key \p key and return the item found
1024 /** \anchor cds_intrusive_SplitListSet_hp_get
1025 The function searches the item with key equal to \p key
1026 and returns the item found as \p guarded_ptr.
1027 If \p key is not found the function returns an empty guarded pointer.
1029 The \p disposer specified in \p OrderedList class' template parameter is called
1030 by garbage collector \p GC automatically when returned \p guarded_ptr object
1031 will be destroyed or released.
1032 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1036 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
1037 splitlist_set theSet;
1040 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1045 // Destructor of guarded_ptr releases internal HP guard
1049 Note the compare functor specified for \p OrderedList template parameter
1050 should accept a parameter of type \p Q that can be not the same as \p value_type.
1052 template <typename Q>
1053 guarded_ptr get( Q const& key )
1058 /// Finds the key \p key and return the item found
1060 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1061 but \p pred is used for comparing the keys.
1063 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1065 \p pred must imply the same element order as the comparator used for building the set.
1067 template <typename Q, typename Less>
1068 guarded_ptr get_with( Q const& key, Less pred )
1070 return get_with_( key, pred );
1073 /// Returns item count in the set
1076 return m_ItemCounter;
1079 /// Checks if the set is empty
1081 Emptiness is checked by item counting: if item count is zero then the set is empty.
1082 Thus, the correct item counting feature is an important part of split-list set implementation.
1089 /// Clears the set (non-atomic)
1091 The function unlink all items from the set.
1092 The function is not atomic. After call the split-list can be non-empty.
1094 For each item the \p disposer is called after unlinking.
1098 iterator it = begin();
1099 while ( it != end()) {
1107 /// Returns internal statistics
1108 stat const& statistics() const
1113 /// Returns internal statistics for \p OrderedList
1114 typename OrderedList::stat const& list_statistics() const
1116 return m_List.statistics();
1121 aux_node_type * alloc_aux_node( size_t nHash )
1123 m_Stat.onHeadNodeAllocated();
1124 aux_node_type* p = m_Buckets.alloc_aux_node();
1130 void free_aux_node( aux_node_type * p )
1132 m_Buckets.free_aux_node( p );
1133 m_Stat.onHeadNodeFreed();
1136 /// Calculates hash value of \p key
1137 template <typename Q>
1138 size_t hash_value( Q const& key ) const
1140 return m_HashFunctor( key );
1143 size_t bucket_no( size_t nHash ) const
1145 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
1148 static size_t parent_bucket( size_t nBucket )
1150 assert( nBucket > 0 );
1151 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
1154 aux_node_type * init_bucket( size_t const nBucket )
1156 assert( nBucket > 0 );
1157 size_t nParent = parent_bucket( nBucket );
1159 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
1160 if ( pParentBucket == nullptr ) {
1161 pParentBucket = init_bucket( nParent );
1162 m_Stat.onRecursiveInitBucket();
1165 assert( pParentBucket != nullptr );
1167 // Allocate an aux node for new bucket
1168 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
1171 for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
1175 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
1177 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
1178 m_Buckets.bucket( nBucket, pBucket );
1179 m_Stat.onNewBucket();
1183 // Another thread set the bucket. Wait while it done
1184 free_aux_node( pBucket );
1185 m_Stat.onBucketInitContenton();
1189 // There are no free buckets. It means that the bucket table is full
1190 // Wait while another thread set the bucket or a free bucket will be available
1191 m_Stat.onBucketsExhausted();
1195 // Another thread set the bucket. Wait while it done
1196 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
1198 m_Stat.onBusyWaitBucketInit();
1204 aux_node_type * get_bucket( size_t nHash )
1206 size_t nBucket = bucket_no( nHash );
1208 aux_node_type * pHead = m_Buckets.bucket( nBucket );
1209 if ( pHead == nullptr )
1210 pHead = init_bucket( nBucket );
1212 assert( pHead->is_dummy());
1219 // GC and OrderedList::gc must be the same
1220 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
1222 // atomicity::empty_item_counter is not allowed as a item counter
1223 static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
1224 "cds::atomicity::empty_item_counter is not allowed as a item counter");
1226 // Initialize bucket 0
1227 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
1228 assert( pNode != nullptr );
1230 // insert_aux_node cannot return false for empty list
1231 CDS_VERIFY( m_List.insert_aux_node( pNode ));
1233 m_Buckets.bucket( 0, pNode );
1236 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
1238 return nBucketCount * nLoadFactor;
1241 void inc_item_count()
1243 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
1244 if ( ++m_ItemCounter <= nMaxCount )
1247 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
1248 const size_t nBucketCount = static_cast<size_t>(1) << sz;
1249 if ( nBucketCount < m_Buckets.capacity()) {
1250 // we may grow the bucket table
1251 const size_t nLoadFactor = m_Buckets.load_factor();
1252 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1253 return; // someone already have updated m_nBucketCountLog2, so stop here
1255 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1256 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1257 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1260 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1263 template <typename Q, typename Compare, typename Func>
1264 bool find_( Q& val, Compare cmp, Func f )
1266 size_t nHash = hash_value( val );
1267 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
1268 aux_node_type * pHead = get_bucket( nHash );
1269 assert( pHead != nullptr );
1271 return m_Stat.onFind(
1272 m_List.find_at( pHead, sv, cmp,
1273 [&f]( value_type& item, split_list::details::search_value_type<Q>& val ) { f( item, val.val ); } )
1277 template <typename Q, typename Compare>
1278 bool find_( Q const& val, Compare cmp )
1280 size_t nHash = hash_value( val );
1281 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1282 aux_node_type * pHead = get_bucket( nHash );
1283 assert( pHead != nullptr );
1285 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1288 template <typename Q, typename Compare>
1289 iterator find_iterator_( Q const& val, Compare cmp )
1291 size_t nHash = hash_value( val );
1292 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1293 aux_node_type * pHead = get_bucket( nHash );
1294 assert( pHead != nullptr );
1296 return iterator( m_List.find_iterator_at( pHead, sv, cmp ), m_List.end());
1299 template <typename Q, typename Compare>
1300 guarded_ptr get_( Q const& val, Compare cmp )
1302 size_t nHash = hash_value( val );
1303 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1304 aux_node_type * pHead = get_bucket( nHash );
1305 assert( pHead != nullptr );
1307 guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
1308 m_Stat.onFind( !gp.empty());
1312 template <typename Q>
1313 guarded_ptr get_( Q const& key )
1315 return get_( key, key_comparator());
1318 template <typename Q, typename Less>
1319 guarded_ptr get_with_( Q const& key, Less )
1321 return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1324 template <typename Q, typename Compare, typename Func>
1325 bool erase_( Q const& val, Compare cmp, Func f )
1327 size_t nHash = hash_value( val );
1328 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1329 aux_node_type * pHead = get_bucket( nHash );
1330 assert( pHead != nullptr );
1332 if ( m_List.erase_at( pHead, sv, cmp, f )) {
1334 m_Stat.onEraseSuccess();
1337 m_Stat.onEraseFailed();
1341 template <typename Q, typename Compare>
1342 bool erase_( Q const& val, Compare cmp )
1344 size_t nHash = hash_value( val );
1345 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1346 aux_node_type * pHead = get_bucket( nHash );
1347 assert( pHead != nullptr );
1349 if ( m_List.erase_at( pHead, sv, cmp )) {
1351 m_Stat.onEraseSuccess();
1354 m_Stat.onEraseFailed();
1358 template <typename Q, typename Compare>
1359 guarded_ptr extract_( Q const& val, Compare cmp )
1361 size_t nHash = hash_value( val );
1362 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1363 aux_node_type * pHead = get_bucket( nHash );
1364 assert( pHead != nullptr );
1366 guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
1369 m_Stat.onExtractSuccess();
1372 m_Stat.onExtractFailed();
1376 template <typename Q>
1377 guarded_ptr extract_( Q const& key )
1379 return extract_( key, key_comparator());
1382 template <typename Q, typename Less>
1383 guarded_ptr extract_with_( Q const& key, Less )
1385 return extract_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1391 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1393 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1394 padded_bucket_table m_Buckets; ///< bucket table
1396 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1397 padded_ordered_list m_List; ///< Ordered list containing split-list items
1399 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1400 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
1401 item_counter m_ItemCounter; ///< Item counter
1402 hash m_HashFunctor; ///< Hash functor
1403 stat m_Stat; ///< Internal statistics
1407 }} // namespace cds::intrusive
1409 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H