2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H
32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
35 #include <cds/intrusive/details/split_list_base.h>
37 namespace cds { namespace intrusive {
39 /// Split-ordered list
40 /** @ingroup cds_intrusive_map
41 \anchor cds_intrusive_SplitListSet_hp
43 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
44 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
45 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
47 The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
48 recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
49 without item moving on resizing.
51 \anchor cds_SplitList_algo_desc
52 <b>Short description</b>
53 [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
55 The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
56 the places in the list where a sublist of 'correct' items can be found. A bucket is initialized upon first
57 access by assigning it to a new 'dummy' node (dashed contour) in the list, preceding all items that should be
58 in that bucket. A newly created bucket splits an older bucket's chain, reducing the access cost to its items. The
59 table uses a modulo 2**i hash (there are known techniques for 'pre-hashing' before a modulo 2**i hash
60 to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
62 Unlike moving an item, the operation of directing a bucket pointer can be done
63 in a single CAS operation, and since items are not moved, they are never 'lost'.
64 However, to make this approach work, one must be able to keep the items in the
65 list sorted in such a way that any bucket's sublist can be 'split' by directing a new
66 bucket pointer within it. This operation must be recursively repeatable, as every
67 split bucket may be split again and again as the hash table grows. To achieve this
68 goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
69 in a given bucket adjacent in the list throughout the repeated splitting process.
71 Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
72 simple binary reversal: reversing the bits of the hash key so that the new key's
73 most significant bits (MSB) are those that were originally its least significant.
74 The split-order keys of regular nodes are exactly the bit-reverse image of the original
75 keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
76 4</tt> bucket, which can be recursively split in two by inserting a new node between
79 To insert (respectively delete or search for) an item in the hash table, hash its
80 key to the appropriate bucket using recursive split-ordering, follow the pointer to
81 the appropriate location in the sorted items list, and traverse the list until the key's
82 proper location in the split-ordering (respectively until the key or a key indicating
83 the item is not in the list is found). Because of the combinatorial structure induced
84 by the split-ordering, this will require traversal of no more than an expected constant number of items.
86 The design is modular: to implement the ordered items list, you can use one of several
87 non-blocking list-based set algorithms: MichaelList, LazyList.
91 Template parameters are:
92 - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
93 - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
94 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
95 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
97 - \p Traits - split-list traits, default is \p split_list::traits.
98 Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
100 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 First, you should choose ordered list type to use in your split-list set:
138 // For gc::HP-based MichaelList implementation
139 #include <cds/intrusive/michael_list_hp.h>
141 // cds::intrusive::SplitListSet declaration
142 #include <cds/intrusive/split_list.h>
145 // Note you should declare your struct based on cds::intrusive::split_list::node
146 // which is a wrapper for ordered-list node struct.
147 // In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
148 struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
150 std::string key_ ; // key field
151 unsigned val_ ; // value field
152 // ... other value fields
155 // Declare comparator for the item
158 int operator()( const Foo& f1, const Foo& f2 ) const
160 return f1.key_.compare( f2.key_ );
164 // Declare base ordered-list type for split-list
165 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
166 typename cds::intrusive::michael_list::make_traits<
168 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
169 // item comparator option
170 ,cds::opt::compare< FooCmp >
175 Second, you should declare split-list set container:
178 // Declare hash functor
179 // Note, the hash functor accepts parameter type Foo and std::string
181 size_t operator()( const Foo& f ) const
183 return cds::opt::v::hash<std::string>()( f.key_ );
185 size_t operator()( const std::string& s ) const
187 return cds::opt::v::hash<std::string>()( s );
191 // Split-list set typedef
192 typedef cds::intrusive::SplitListSet<
195 ,typename cds::intrusive::split_list::make_traits<
196 cds::opt::hash< FooHash >
201 Now, you can use \p Foo_set in your application.
207 fooSet.insert( *foo );
215 # ifdef CDS_DOXYGEN_INVOKED
216 class Traits = split_list::traits
224 typedef GC gc; ///< Garbage collector
225 typedef Traits traits; ///< Set traits
229 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
233 # ifdef CDS_DOXYGEN_INVOKED
234 typedef OrderedList ordered_list; ///< type of ordered list used as a base for split-list
236 typedef typename wrapped_ordered_list::result ordered_list;
238 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
239 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
240 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
242 /// Hash functor for \p %value_type and all its derivatives that you use
243 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
245 typedef typename traits::item_counter item_counter; ///< Item counter type
246 typedef typename traits::back_off back_off; ///< back-off strategy for spinning
247 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
248 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
249 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
251 /// Count of hazard pointer required
252 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
255 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
256 typedef split_list::node<list_node_type> node_type; ///< split-list node type
257 typedef node_type dummy_node_type; ///< dummy node type
259 /// Split-list node traits
261 This traits is intended for converting between underlying ordered list node type \p list_node_type
262 and split-list node type \p node_type
264 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
267 /// Bucket table implementation
268 typedef typename split_list::details::bucket_table_selector<
269 traits::dynamic_bucket_table
272 , opt::allocator< typename traits::allocator >
273 , opt::memory_model< memory_model >
274 >::type bucket_table;
279 /// Ordered list wrapper to access protected members
280 class ordered_list_wrapper: public ordered_list
282 typedef ordered_list base_class;
283 typedef typename base_class::auxiliary_head bucket_head_type;
286 bool insert_at( dummy_node_type * pHead, value_type& val )
288 assert( pHead != nullptr );
289 bucket_head_type h(pHead);
290 return base_class::insert_at( h, val );
293 template <typename Func>
294 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
296 assert( pHead != nullptr );
297 bucket_head_type h(pHead);
298 return base_class::insert_at( h, val, f );
301 template <typename Func>
302 std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
304 assert( pHead != nullptr );
305 bucket_head_type h(pHead);
306 return base_class::update_at( h, val, func, bAllowInsert );
309 bool unlink_at( dummy_node_type * pHead, value_type& val )
311 assert( pHead != nullptr );
312 bucket_head_type h(pHead);
313 return base_class::unlink_at( h, val );
316 template <typename Q, typename Compare, typename Func>
317 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
319 assert( pHead != nullptr );
320 bucket_head_type h(pHead);
321 return base_class::erase_at( h, val, cmp, f );
324 template <typename Q, typename Compare>
325 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
327 assert( pHead != nullptr );
328 bucket_head_type h(pHead);
329 return base_class::erase_at( h, val, cmp );
332 template <typename Q, typename Compare>
333 bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
335 assert( pHead != nullptr );
336 bucket_head_type h(pHead);
337 return base_class::extract_at( h, guard, val, cmp );
340 template <typename Q, typename Compare, typename Func>
341 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
343 assert( pHead != nullptr );
344 bucket_head_type h(pHead);
345 return base_class::find_at( h, val, cmp, f );
348 template <typename Q, typename Compare>
349 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
351 assert( pHead != nullptr );
352 bucket_head_type h(pHead);
353 return base_class::find_at( h, val, cmp );
356 template <typename Q, typename Compare>
357 bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
359 assert( pHead != nullptr );
360 bucket_head_type h(pHead);
361 return base_class::get_at( h, guard, val, cmp );
364 bool insert_aux_node( dummy_node_type * pNode )
366 return base_class::insert_aux_node( pNode );
368 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
370 bucket_head_type h(pHead);
371 return base_class::insert_aux_node( h, pNode );
377 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
378 bucket_table m_Buckets; ///< bucket table
379 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
380 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
381 item_counter m_ItemCounter; ///< Item counter
382 hash m_HashFunctor; ///< Hash functor
383 stat m_Stat; ///< Internal statistics
387 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
389 dummy_node_type * alloc_dummy_node( size_t nHash )
391 m_Stat.onHeadNodeAllocated();
392 return dummy_node_allocator().New( nHash );
394 void free_dummy_node( dummy_node_type * p )
396 dummy_node_allocator().Delete( p );
397 m_Stat.onHeadNodeFreed();
400 /// Calculates hash value of \p key
401 template <typename Q>
402 size_t hash_value( Q const& key ) const
404 return m_HashFunctor( key );
407 size_t bucket_no( size_t nHash ) const
409 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
412 static size_t parent_bucket( size_t nBucket )
414 assert( nBucket > 0 );
415 return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
418 dummy_node_type * init_bucket( size_t nBucket )
420 assert( nBucket > 0 );
421 size_t nParent = parent_bucket( nBucket );
423 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
424 if ( pParentBucket == nullptr ) {
425 pParentBucket = init_bucket( nParent );
426 m_Stat.onRecursiveInitBucket();
429 assert( pParentBucket != nullptr );
431 // Allocate a dummy node for new bucket
433 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ));
434 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
435 m_Buckets.bucket( nBucket, pBucket );
436 m_Stat.onNewBucket();
439 free_dummy_node( pBucket );
442 // Another thread set the bucket. Wait while it done
444 // In this point, we must wait while nBucket is empty.
445 // The compiler can decide that waiting loop can be "optimized" (stripped)
446 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
447 m_Stat.onBucketInitContenton();
450 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
452 return const_cast<dummy_node_type *>( p );
454 m_Stat.onBusyWaitBucketInit();
458 dummy_node_type * get_bucket( size_t nHash )
460 size_t nBucket = bucket_no( nHash );
462 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
463 if ( pHead == nullptr )
464 pHead = init_bucket( nBucket );
466 assert( pHead->is_dummy());
473 // GC and OrderedList::gc must be the same
474 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
476 // atomicity::empty_item_counter is not allowed as a item counter
477 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
478 "cds::atomicity::empty_item_counter is not allowed as a item counter");
480 // Initialize bucket 0
481 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
483 // insert_aux_node cannot return false for empty list
484 CDS_VERIFY( m_List.insert_aux_node( pNode ));
486 m_Buckets.bucket( 0, pNode );
489 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
491 return nBucketCount * nLoadFactor;
494 void inc_item_count()
496 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
497 if ( ++m_ItemCounter <= nMaxCount )
500 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
501 const size_t nBucketCount = static_cast<size_t>(1) << sz;
502 if ( nBucketCount < m_Buckets.capacity()) {
503 // we may grow the bucket table
504 const size_t nLoadFactor = m_Buckets.load_factor();
505 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
506 return; // someone already have updated m_nBucketCountLog2, so stop here
508 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
509 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
510 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
513 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
516 template <typename Q, typename Compare, typename Func>
517 bool find_( Q& val, Compare cmp, Func f )
519 size_t nHash = hash_value( val );
520 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
521 dummy_node_type * pHead = get_bucket( nHash );
522 assert( pHead != nullptr );
524 return m_Stat.onFind(
525 m_List.find_at( pHead, sv, cmp,
526 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
530 template <typename Q, typename Compare>
531 bool find_( Q const& val, Compare cmp )
533 size_t nHash = hash_value( val );
534 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
535 dummy_node_type * pHead = get_bucket( nHash );
536 assert( pHead != nullptr );
538 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
541 template <typename Q, typename Compare>
542 bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
544 size_t nHash = hash_value( val );
545 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
546 dummy_node_type * pHead = get_bucket( nHash );
547 assert( pHead != nullptr );
549 return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
552 template <typename Q>
553 bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
555 return get_( guard, key, key_comparator());
558 template <typename Q, typename Less>
559 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
561 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
564 template <typename Q, typename Compare, typename Func>
565 bool erase_( Q const& val, Compare cmp, Func f )
567 size_t nHash = hash_value( val );
568 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
569 dummy_node_type * pHead = get_bucket( nHash );
570 assert( pHead != nullptr );
572 if ( m_List.erase_at( pHead, sv, cmp, f )) {
574 m_Stat.onEraseSuccess();
577 m_Stat.onEraseFailed();
581 template <typename Q, typename Compare>
582 bool erase_( Q const& val, Compare cmp )
584 size_t nHash = hash_value( val );
585 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
586 dummy_node_type * pHead = get_bucket( nHash );
587 assert( pHead != nullptr );
589 if ( m_List.erase_at( pHead, sv, cmp )) {
591 m_Stat.onEraseSuccess();
594 m_Stat.onEraseFailed();
598 template <typename Q, typename Compare>
599 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
601 size_t nHash = hash_value( val );
602 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
603 dummy_node_type * pHead = get_bucket( nHash );
604 assert( pHead != nullptr );
606 if ( m_List.extract_at( pHead, guard, sv, cmp )) {
608 m_Stat.onExtractSuccess();
611 m_Stat.onExtractFailed();
615 template <typename Q>
616 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
618 return extract_( guard, key, key_comparator());
621 template <typename Q, typename Less>
622 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
624 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
629 /// Initialize split-ordered list of default capacity
631 The default capacity is defined in bucket table constructor.
632 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
633 which selects by \p split_list::dynamic_bucket_table option.
636 : m_nBucketCountLog2(1)
637 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
642 /// Initialize split-ordered list
644 size_t nItemCount ///< estimate average of item count
645 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
647 : m_Buckets( nItemCount, nLoadFactor )
648 , m_nBucketCountLog2(1)
649 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
657 The function inserts \p val in the set if it does not contain
658 an item with key equal to \p val.
660 Returns \p true if \p val is placed into the set, \p false otherwise.
662 bool insert( value_type& val )
664 size_t nHash = hash_value( val );
665 dummy_node_type * pHead = get_bucket( nHash );
666 assert( pHead != nullptr );
668 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
670 if ( m_List.insert_at( pHead, val )) {
672 m_Stat.onInsertSuccess();
675 m_Stat.onInsertFailed();
681 This function is intended for derived non-intrusive containers.
683 The function allows to split creating of new item into two part:
684 - create item with key only
685 - insert new item into the set
686 - if inserting is success, calls \p f functor to initialize value-field of \p val.
688 The functor signature is:
690 void func( value_type& val );
692 where \p val is the item inserted.
693 The user-defined functor is called only if the inserting is success.
695 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
696 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
699 template <typename Func>
700 bool insert( value_type& val, Func f )
702 size_t nHash = hash_value( val );
703 dummy_node_type * pHead = get_bucket( nHash );
704 assert( pHead != nullptr );
706 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
708 if ( m_List.insert_at( pHead, val, f )) {
710 m_Stat.onInsertSuccess();
713 m_Stat.onInsertFailed();
719 The operation performs inserting or changing data with lock-free manner.
721 If the item \p val is not found in the set, then \p val is inserted
722 iff \p bAllowInsert is \p true.
723 Otherwise, the functor \p func is called with item found.
724 The functor signature is:
726 void func( bool bNew, value_type& item, value_type& val );
729 - \p bNew - \p true if the item has been inserted, \p false otherwise
730 - \p item - item of the set
731 - \p val - argument \p val passed into the \p update() function
732 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
733 refers to the same thing.
735 The functor may change non-key fields of the \p item.
737 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
738 \p second is \p true if new item has been added or \p false if the item with \p val
739 already is in the list.
741 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
742 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
745 template <typename Func>
746 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
748 size_t nHash = hash_value( val );
749 dummy_node_type * pHead = get_bucket( nHash );
750 assert( pHead != nullptr );
752 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
754 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
755 if ( bRet.first && bRet.second ) {
757 m_Stat.onEnsureNew();
760 m_Stat.onEnsureExist();
764 template <typename Func>
765 CDS_DEPRECATED("ensure() is deprecated, use update()")
766 std::pair<bool, bool> ensure( value_type& val, Func func )
768 return update( val, func, true );
772 /// Unlinks the item \p val from the set
774 The function searches the item \p val in the set and unlinks it from the set
775 if it is found and is equal to \p val.
777 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
778 and deletes the item found. \p unlink finds an item by key and deletes it
779 only if \p val is an item of that set, i.e. the pointer to item found
780 is equal to <tt> &val </tt>.
782 The function returns \p true if success and \p false otherwise.
784 bool unlink( value_type& val )
786 size_t nHash = hash_value( val );
787 dummy_node_type * pHead = get_bucket( nHash );
788 assert( pHead != nullptr );
790 if ( m_List.unlink_at( pHead, val )) {
792 m_Stat.onEraseSuccess();
795 m_Stat.onEraseFailed();
799 /// Deletes the item from the set
800 /** \anchor cds_intrusive_SplitListSet_hp_erase
801 The function searches an item with key equal to \p key in the set,
802 unlinks it from the set, and returns \p true.
803 If the item with key equal to \p key is not found the function return \p false.
805 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
806 and deletes the item found. \p unlink finds an item by key and deletes it
807 only if \p key is an item of that set, i.e. the pointer to item found
808 is equal to <tt> &key </tt>.
810 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
812 template <typename Q>
813 bool erase( Q const& key )
815 return erase_( key, key_comparator());
818 /// Deletes the item from the set with comparing functor \p pred
821 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
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>
827 bool erase_with( const Q& key, Less pred )
830 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
833 /// Deletes the item from the set
834 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
835 The function searches an item with key equal to \p key in the set,
836 call \p f functor with item found, unlinks it from the set, and returns \p true.
837 The \ref disposer specified by \p OrderedList class template parameter is called
838 by garbage collector \p GC asynchronously.
840 The \p Func interface is
843 void operator()( value_type const& item );
847 If the item with key equal to \p key is not found the function return \p false.
849 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
851 template <typename Q, typename Func>
852 bool erase( Q const& key, Func f )
854 return erase_( key, key_comparator(), f );
857 /// Deletes the item from the set with comparing functor \p pred
859 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
860 but \p pred predicate is used for key comparing.
861 \p Less has the interface like \p std::less.
862 \p pred must imply the same element order as the comparator used for building the set.
864 template <typename Q, typename Less, typename Func>
865 bool erase_with( Q const& key, Less pred, Func f )
868 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
871 /// Extracts the item with specified \p key
872 /** \anchor cds_intrusive_SplitListSet_hp_extract
873 The function searches an item with key equal to \p key,
874 unlinks it from the set, and returns it as \p guarded_ptr.
875 If \p key is not found the function returns an empty guarded pointer.
877 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
879 The \p disposer specified in \p OrderedList class' template parameter is called automatically
880 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
881 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
885 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
886 splitlist_set theSet;
889 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
894 // Destructor of gp releases internal HP guard
898 template <typename Q>
899 guarded_ptr extract( Q const& key )
902 extract_( gp.guard(), key );
906 /// Extracts the item using compare functor \p pred
908 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
909 but \p pred predicate is used for key comparing.
911 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
913 \p pred must imply the same element order as the comparator used for building the set.
915 template <typename Q, typename Less>
916 guarded_ptr extract_with( Q const& key, Less pred )
919 extract_with_( gp.guard(), 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 the key \p key with \p pred predicate for comparing
959 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
960 but \p cmp is used for key compare.
961 \p Less has the interface like \p std::less.
962 \p cmp must imply the same element order as the comparator used for building the set.
964 template <typename Q, typename Less, typename Func>
965 bool find_with( Q& key, Less pred, Func f )
968 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
971 template <typename Q, typename Less, typename Func>
972 bool find_with( Q const& key, Less pred, Func f )
975 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
979 /// Checks whether the set contains \p key
981 The function searches the item with key equal to \p key
982 and returns \p true if it is found, and \p false otherwise.
984 Note the hash functor specified for class \p Traits template parameter
985 should accept a parameter of type \p Q that can be not the same as \p value_type.
986 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
988 template <typename Q>
989 bool contains( Q const& key )
991 return find_( key, key_comparator());
994 template <typename Q>
995 CDS_DEPRECATED("deprecated, use contains()")
996 bool find( Q const& key )
998 return contains( key );
1002 /// Checks whether the set contains \p key using \p pred predicate for searching
1004 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
1005 \p Less functor has the interface like \p std::less.
1006 \p Less must imply the same element order as the comparator used for building the set.
1008 template <typename Q, typename Less>
1009 bool contains( Q const& key, Less pred )
1012 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
1015 template <typename Q, typename Less>
1016 CDS_DEPRECATED("deprecated, use contains()")
1017 bool find_with( Q const& key, Less pred )
1019 return contains( key, pred );
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 )
1056 get_( gp.guard(), key );
1060 /// Finds the key \p key and return the item found
1062 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1063 but \p pred is used for comparing the keys.
1065 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1067 \p pred must imply the same element order as the comparator used for building the set.
1069 template <typename Q, typename Less>
1070 guarded_ptr get_with( Q const& key, Less pred )
1073 get_with_( gp.guard(), key, pred );
1077 /// Returns item count in the set
1080 return m_ItemCounter;
1083 /// Checks if the set is empty
1085 Emptiness is checked by item counting: if item count is zero then the set is empty.
1086 Thus, the correct item counting feature is an important part of split-list set implementation.
1093 /// Clears the set (non-atomic)
1095 The function unlink all items from the set.
1096 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1098 For each item the \p disposer is called after unlinking.
1102 iterator it = begin();
1103 while ( it != end()) {
1111 /// Returns internal statistics
1112 stat const& statistics() const
1119 template <bool IsConst>
1121 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1123 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1124 typedef typename iterator_base_class::list_iterator list_iterator;
1127 : iterator_base_class()
1130 iterator_type( iterator_type const& src )
1131 : iterator_base_class( src )
1134 // This ctor should be protected...
1135 iterator_type( list_iterator itCur, list_iterator itEnd )
1136 : iterator_base_class( itCur, itEnd )
1141 ///@name Forward iterators (only for debugging purpose)
1143 /// Forward iterator
1145 The forward iterator for a split-list has some features:
1146 - it has no post-increment operator
1147 - it depends on iterator of underlying \p OrderedList
1148 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1149 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1150 deleting operations it is no guarantee that you iterate all item in the set.
1151 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
1153 @warning Use this iterator on the concurrent container for debugging purpose only.
1155 typedef iterator_type<false> iterator;
1157 /// Const forward iterator
1159 For iterator's features and requirements see \ref iterator
1161 typedef iterator_type<true> const_iterator;
1163 /// Returns a forward iterator addressing the first element in a split-list
1165 For empty list \code begin() == end() \endcode
1169 return iterator( m_List.begin(), m_List.end());
1172 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1174 Do not use the value returned by <tt>end</tt> function to access any item.
1176 The returned value can be used only to control reaching the end of the split-list.
1177 For empty list \code begin() == end() \endcode
1181 return iterator( m_List.end(), m_List.end());
1184 /// Returns a forward const iterator addressing the first element in a split-list
1185 const_iterator begin() const
1189 /// Returns a forward const iterator addressing the first element in a split-list
1190 const_iterator cbegin() const
1192 return const_iterator( m_List.cbegin(), m_List.cend());
1195 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1196 const_iterator end() const
1200 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1201 const_iterator cend() const
1203 return const_iterator( m_List.cend(), m_List.cend());
1208 }} // namespace cds::intrusive
1210 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H