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
252 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
253 typedef split_list::node<list_node_type> node_type; ///< split-list node type
254 typedef node_type dummy_node_type; ///< dummy node type
256 /// Split-list node traits
258 This traits is intended for converting between underlying ordered list node type \p list_node_type
259 and split-list node type \p node_type
261 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
264 /// Bucket table implementation
265 typedef typename split_list::details::bucket_table_selector<
266 traits::dynamic_bucket_table
269 , opt::allocator< typename traits::allocator >
270 , opt::memory_model< memory_model >
271 >::type bucket_table;
276 /// Ordered list wrapper to access protected members
277 class ordered_list_wrapper: public ordered_list
279 typedef ordered_list base_class;
280 typedef typename base_class::auxiliary_head bucket_head_type;
283 bool insert_at( dummy_node_type * pHead, value_type& val )
285 assert( pHead != nullptr );
286 bucket_head_type h(pHead);
287 return base_class::insert_at( h, val );
290 template <typename Func>
291 bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
293 assert( pHead != nullptr );
294 bucket_head_type h(pHead);
295 return base_class::insert_at( h, val, f );
298 template <typename Func>
299 std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
301 assert( pHead != nullptr );
302 bucket_head_type h(pHead);
303 return base_class::update_at( h, val, func, bAllowInsert );
306 bool unlink_at( dummy_node_type * pHead, value_type& val )
308 assert( pHead != nullptr );
309 bucket_head_type h(pHead);
310 return base_class::unlink_at( h, val );
313 template <typename Q, typename Compare, typename Func>
314 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
316 assert( pHead != nullptr );
317 bucket_head_type h(pHead);
318 return base_class::erase_at( h, val, cmp, f );
321 template <typename Q, typename Compare>
322 bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
324 assert( pHead != nullptr );
325 bucket_head_type h(pHead);
326 return base_class::erase_at( h, val, cmp );
329 template <typename Q, typename Compare>
330 bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
332 assert( pHead != nullptr );
333 bucket_head_type h(pHead);
334 return base_class::extract_at( h, guard, val, cmp );
337 template <typename Q, typename Compare, typename Func>
338 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
340 assert( pHead != nullptr );
341 bucket_head_type h(pHead);
342 return base_class::find_at( h, val, cmp, f );
345 template <typename Q, typename Compare>
346 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
348 assert( pHead != nullptr );
349 bucket_head_type h(pHead);
350 return base_class::find_at( h, val, cmp );
353 template <typename Q, typename Compare>
354 bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
356 assert( pHead != nullptr );
357 bucket_head_type h(pHead);
358 return base_class::get_at( h, guard, val, cmp );
361 bool insert_aux_node( dummy_node_type * pNode )
363 return base_class::insert_aux_node( pNode );
365 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
367 bucket_head_type h(pHead);
368 return base_class::insert_aux_node( h, pNode );
374 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
375 bucket_table m_Buckets; ///< bucket table
376 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
377 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
378 item_counter m_ItemCounter; ///< Item counter
379 hash m_HashFunctor; ///< Hash functor
380 stat m_Stat; ///< Internal statistics
384 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
386 dummy_node_type * alloc_dummy_node( size_t nHash )
388 m_Stat.onHeadNodeAllocated();
389 return dummy_node_allocator().New( nHash );
391 void free_dummy_node( dummy_node_type * p )
393 dummy_node_allocator().Delete( p );
394 m_Stat.onHeadNodeFreed();
397 /// Calculates hash value of \p key
398 template <typename Q>
399 size_t hash_value( Q const& key ) const
401 return m_HashFunctor( key );
404 size_t bucket_no( size_t nHash ) const
406 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
409 static size_t parent_bucket( size_t nBucket )
411 assert( nBucket > 0 );
412 return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
415 dummy_node_type * init_bucket( size_t nBucket )
417 assert( nBucket > 0 );
418 size_t nParent = parent_bucket( nBucket );
420 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
421 if ( pParentBucket == nullptr ) {
422 pParentBucket = init_bucket( nParent );
423 m_Stat.onRecursiveInitBucket();
426 assert( pParentBucket != nullptr );
428 // Allocate a dummy node for new bucket
430 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ));
431 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
432 m_Buckets.bucket( nBucket, pBucket );
433 m_Stat.onNewBucket();
436 free_dummy_node( pBucket );
439 // Another thread set the bucket. Wait while it done
441 // In this point, we must wait while nBucket is empty.
442 // The compiler can decide that waiting loop can be "optimized" (stripped)
443 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
444 m_Stat.onBucketInitContenton();
447 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
449 return const_cast<dummy_node_type *>( p );
451 m_Stat.onBusyWaitBucketInit();
455 dummy_node_type * get_bucket( size_t nHash )
457 size_t nBucket = bucket_no( nHash );
459 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
460 if ( pHead == nullptr )
461 pHead = init_bucket( nBucket );
463 assert( pHead->is_dummy());
470 // GC and OrderedList::gc must be the same
471 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
473 // atomicity::empty_item_counter is not allowed as a item counter
474 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
475 "cds::atomicity::empty_item_counter is not allowed as a item counter");
477 // Initialize bucket 0
478 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
480 // insert_aux_node cannot return false for empty list
481 CDS_VERIFY( m_List.insert_aux_node( pNode ));
483 m_Buckets.bucket( 0, pNode );
486 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
488 return nBucketCount * nLoadFactor;
491 void inc_item_count()
493 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
494 if ( ++m_ItemCounter <= nMaxCount )
497 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
498 const size_t nBucketCount = static_cast<size_t>(1) << sz;
499 if ( nBucketCount < m_Buckets.capacity()) {
500 // we may grow the bucket table
501 const size_t nLoadFactor = m_Buckets.load_factor();
502 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
503 return; // someone already have updated m_nBucketCountLog2, so stop here
505 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
506 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
507 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
510 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
513 template <typename Q, typename Compare, typename Func>
514 bool find_( Q& val, Compare cmp, Func f )
516 size_t nHash = hash_value( val );
517 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
518 dummy_node_type * pHead = get_bucket( nHash );
519 assert( pHead != nullptr );
521 return m_Stat.onFind(
522 m_List.find_at( pHead, sv, cmp,
523 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
527 template <typename Q, typename Compare>
528 bool find_( Q const& val, Compare cmp )
530 size_t nHash = hash_value( val );
531 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
532 dummy_node_type * pHead = get_bucket( nHash );
533 assert( pHead != nullptr );
535 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
538 template <typename Q, typename Compare>
539 bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
541 size_t nHash = hash_value( val );
542 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
543 dummy_node_type * pHead = get_bucket( nHash );
544 assert( pHead != nullptr );
546 return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
549 template <typename Q>
550 bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
552 return get_( guard, key, key_comparator());
555 template <typename Q, typename Less>
556 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
558 return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
561 template <typename Q, typename Compare, typename Func>
562 bool erase_( Q const& val, Compare cmp, Func f )
564 size_t nHash = hash_value( val );
565 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
566 dummy_node_type * pHead = get_bucket( nHash );
567 assert( pHead != nullptr );
569 if ( m_List.erase_at( pHead, sv, cmp, f )) {
571 m_Stat.onEraseSuccess();
574 m_Stat.onEraseFailed();
578 template <typename Q, typename Compare>
579 bool erase_( Q const& val, Compare cmp )
581 size_t nHash = hash_value( val );
582 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
583 dummy_node_type * pHead = get_bucket( nHash );
584 assert( pHead != nullptr );
586 if ( m_List.erase_at( pHead, sv, cmp )) {
588 m_Stat.onEraseSuccess();
591 m_Stat.onEraseFailed();
595 template <typename Q, typename Compare>
596 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
598 size_t nHash = hash_value( val );
599 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
600 dummy_node_type * pHead = get_bucket( nHash );
601 assert( pHead != nullptr );
603 if ( m_List.extract_at( pHead, guard, sv, cmp )) {
605 m_Stat.onExtractSuccess();
608 m_Stat.onExtractFailed();
612 template <typename Q>
613 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
615 return extract_( guard, key, key_comparator());
618 template <typename Q, typename Less>
619 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
621 return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
626 /// Initialize split-ordered list of default capacity
628 The default capacity is defined in bucket table constructor.
629 See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
630 which selects by \p split_list::dynamic_bucket_table option.
633 : m_nBucketCountLog2(1)
634 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
639 /// Initialize split-ordered list
641 size_t nItemCount ///< estimate average of item count
642 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
644 : m_Buckets( nItemCount, nLoadFactor )
645 , m_nBucketCountLog2(1)
646 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
654 The function inserts \p val in the set if it does not contain
655 an item with key equal to \p val.
657 Returns \p true if \p val is placed into the set, \p false otherwise.
659 bool insert( value_type& val )
661 size_t nHash = hash_value( val );
662 dummy_node_type * pHead = get_bucket( nHash );
663 assert( pHead != nullptr );
665 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
667 if ( m_List.insert_at( pHead, val )) {
669 m_Stat.onInsertSuccess();
672 m_Stat.onInsertFailed();
678 This function is intended for derived non-intrusive containers.
680 The function allows to split creating of new item into two part:
681 - create item with key only
682 - insert new item into the set
683 - if inserting is success, calls \p f functor to initialize value-field of \p val.
685 The functor signature is:
687 void func( value_type& val );
689 where \p val is the item inserted.
690 The user-defined functor is called only if the inserting is success.
692 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
693 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
696 template <typename Func>
697 bool insert( value_type& val, Func f )
699 size_t nHash = hash_value( val );
700 dummy_node_type * pHead = get_bucket( nHash );
701 assert( pHead != nullptr );
703 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
705 if ( m_List.insert_at( pHead, val, f )) {
707 m_Stat.onInsertSuccess();
710 m_Stat.onInsertFailed();
716 The operation performs inserting or changing data with lock-free manner.
718 If the item \p val is not found in the set, then \p val is inserted
719 iff \p bAllowInsert is \p true.
720 Otherwise, the functor \p func is called with item found.
721 The functor signature is:
723 void func( bool bNew, value_type& item, value_type& val );
726 - \p bNew - \p true if the item has been inserted, \p false otherwise
727 - \p item - item of the set
728 - \p val - argument \p val passed into the \p update() function
729 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
730 refers to the same thing.
732 The functor may change non-key fields of the \p item.
734 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
735 \p second is \p true if new item has been added or \p false if the item with \p val
736 already is in the list.
738 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
739 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
742 template <typename Func>
743 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
745 size_t nHash = hash_value( val );
746 dummy_node_type * pHead = get_bucket( nHash );
747 assert( pHead != nullptr );
749 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
751 std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
752 if ( bRet.first && bRet.second ) {
754 m_Stat.onEnsureNew();
757 m_Stat.onEnsureExist();
761 template <typename Func>
762 CDS_DEPRECATED("ensure() is deprecated, use update()")
763 std::pair<bool, bool> ensure( value_type& val, Func func )
765 return update( val, func, true );
769 /// Unlinks the item \p val from the set
771 The function searches the item \p val in the set and unlinks it from the set
772 if it is found and is equal to \p val.
774 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
775 and deletes the item found. \p unlink finds an item by key and deletes it
776 only if \p val is an item of that set, i.e. the pointer to item found
777 is equal to <tt> &val </tt>.
779 The function returns \p true if success and \p false otherwise.
781 bool unlink( value_type& val )
783 size_t nHash = hash_value( val );
784 dummy_node_type * pHead = get_bucket( nHash );
785 assert( pHead != nullptr );
787 if ( m_List.unlink_at( pHead, val )) {
789 m_Stat.onEraseSuccess();
792 m_Stat.onEraseFailed();
796 /// Deletes the item from the set
797 /** \anchor cds_intrusive_SplitListSet_hp_erase
798 The function searches an item with key equal to \p key in the set,
799 unlinks it from the set, and returns \p true.
800 If the item with key equal to \p key is not found the function return \p false.
802 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
803 and deletes the item found. \p unlink finds an item by key and deletes it
804 only if \p key is an item of that set, i.e. the pointer to item found
805 is equal to <tt> &key </tt>.
807 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
809 template <typename Q>
810 bool erase( Q const& key )
812 return erase_( key, key_comparator());
815 /// Deletes the item from the set with comparing functor \p pred
818 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
819 but \p pred predicate is used for key comparing.
820 \p Less has the interface like \p std::less.
821 \p pred must imply the same element order as the comparator used for building the set.
823 template <typename Q, typename Less>
824 bool erase_with( const Q& key, Less pred )
827 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
830 /// Deletes the item from the set
831 /** \anchor cds_intrusive_SplitListSet_hp_erase_func
832 The function searches an item with key equal to \p key in the set,
833 call \p f functor with item found, unlinks it from the set, and returns \p true.
834 The \ref disposer specified by \p OrderedList class template parameter is called
835 by garbage collector \p GC asynchronously.
837 The \p Func interface is
840 void operator()( value_type const& item );
844 If the item with key equal to \p key is not found the function return \p false.
846 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
848 template <typename Q, typename Func>
849 bool erase( Q const& key, Func f )
851 return erase_( key, key_comparator(), f );
854 /// Deletes the item from the set with comparing functor \p pred
856 The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
857 but \p pred predicate is used for key comparing.
858 \p Less has the interface like \p std::less.
859 \p pred must imply the same element order as the comparator used for building the set.
861 template <typename Q, typename Less, typename Func>
862 bool erase_with( Q const& key, Less pred, Func f )
865 return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
868 /// Extracts the item with specified \p key
869 /** \anchor cds_intrusive_SplitListSet_hp_extract
870 The function searches an item with key equal to \p key,
871 unlinks it from the set, and returns it as \p guarded_ptr.
872 If \p key is not found the function returns an empty guarded pointer.
874 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
876 The \p disposer specified in \p OrderedList class' template parameter is called automatically
877 by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
878 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
882 typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
883 splitlist_set theSet;
886 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
891 // Destructor of gp releases internal HP guard
895 template <typename Q>
896 guarded_ptr extract( Q const& key )
899 extract_( gp.guard(), key );
903 /// Extracts the item using compare functor \p pred
905 The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
906 but \p pred predicate is used for key comparing.
908 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
910 \p pred must imply the same element order as the comparator used for building the set.
912 template <typename Q, typename Less>
913 guarded_ptr extract_with( Q const& key, Less pred )
916 extract_with_( gp.guard(), key, pred );
920 /// Finds the key \p key
921 /** \anchor cds_intrusive_SplitListSet_hp_find_func
922 The function searches the item with key equal to \p key and calls the functor \p f for item found.
923 The interface of \p Func functor is:
926 void operator()( value_type& item, Q& key );
929 where \p item is the item found, \p key is the <tt>find</tt> function argument.
931 The functor can change non-key fields of \p item. Note that the functor is only guarantee
932 that \p item cannot be disposed during functor is executing.
933 The functor does not serialize simultaneous access to the set \p item. If such access is
934 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
936 Note the hash functor specified for class \p Traits template parameter
937 should accept a parameter of type \p Q that can be not the same as \p value_type.
939 The function returns \p true if \p key is found, \p false otherwise.
941 template <typename Q, typename Func>
942 bool find( Q& key, Func f )
944 return find_( key, key_comparator(), f );
947 template <typename Q, typename Func>
948 bool find( Q const& key, Func f )
950 return find_( key, key_comparator(), f );
954 /// Finds the key \p key with \p pred predicate for comparing
956 The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
957 but \p cmp is used for key compare.
958 \p Less has the interface like \p std::less.
959 \p cmp must imply the same element order as the comparator used for building the set.
961 template <typename Q, typename Less, typename Func>
962 bool find_with( Q& key, Less pred, Func f )
965 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
968 template <typename Q, typename Less, typename Func>
969 bool find_with( Q const& key, Less pred, Func f )
972 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
976 /// Checks whether the set contains \p key
978 The function searches the item with key equal to \p key
979 and returns \p true if it is found, and \p false otherwise.
981 Note the hash functor specified for class \p Traits template parameter
982 should accept a parameter of type \p Q that can be not the same as \p value_type.
983 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
985 template <typename Q>
986 bool contains( Q const& key )
988 return find_( key, key_comparator());
991 template <typename Q>
992 CDS_DEPRECATED("deprecated, use contains()")
993 bool find( Q const& key )
995 return contains( key );
999 /// Checks whether the set contains \p key using \p pred predicate for searching
1001 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
1002 \p Less functor has the interface like \p std::less.
1003 \p Less must imply the same element order as the comparator used for building the set.
1005 template <typename Q, typename Less>
1006 bool contains( Q const& key, Less pred )
1009 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
1012 template <typename Q, typename Less>
1013 CDS_DEPRECATED("deprecated, use contains()")
1014 bool find_with( Q const& key, Less pred )
1016 return contains( key, pred );
1020 /// Finds the key \p key and return the item found
1021 /** \anchor cds_intrusive_SplitListSet_hp_get
1022 The function searches the item with key equal to \p key
1023 and returns the item found as \p guarded_ptr.
1024 If \p key is not found the function returns an empty guarded pointer.
1026 The \p disposer specified in \p OrderedList class' template parameter is called
1027 by garbage collector \p GC automatically when returned \p guarded_ptr object
1028 will be destroyed or released.
1029 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1033 typedef cds::intrusive::SplitListSet< your_template_params > splitlist_set;
1034 splitlist_set theSet;
1037 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1042 // Destructor of guarded_ptr releases internal HP guard
1046 Note the compare functor specified for \p OrderedList template parameter
1047 should accept a parameter of type \p Q that can be not the same as \p value_type.
1049 template <typename Q>
1050 guarded_ptr get( Q const& key )
1053 get_( gp.guard(), key );
1057 /// Finds the key \p key and return the item found
1059 The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1060 but \p pred is used for comparing the keys.
1062 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1064 \p pred must imply the same element order as the comparator used for building the set.
1066 template <typename Q, typename Less>
1067 guarded_ptr get_with( Q const& key, Less pred )
1070 get_with_( gp.guard(), key, pred );
1074 /// Returns item count in the set
1077 return m_ItemCounter;
1080 /// Checks if the set is empty
1082 Emptiness is checked by item counting: if item count is zero then the set is empty.
1083 Thus, the correct item counting feature is an important part of split-list set implementation.
1090 /// Clears the set (non-atomic)
1092 The function unlink all items from the set.
1093 The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1095 For each item the \p disposer is called after unlinking.
1099 iterator it = begin();
1100 while ( it != end()) {
1108 /// Returns internal statistics
1109 stat const& statistics() const
1116 template <bool IsConst>
1118 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1120 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1121 typedef typename iterator_base_class::list_iterator list_iterator;
1124 : iterator_base_class()
1127 iterator_type( iterator_type const& src )
1128 : iterator_base_class( src )
1131 // This ctor should be protected...
1132 iterator_type( list_iterator itCur, list_iterator itEnd )
1133 : iterator_base_class( itCur, itEnd )
1138 ///@name Forward iterators (only for debugging purpose)
1140 /// Forward iterator
1142 The forward iterator for a split-list has some features:
1143 - it has no post-increment operator
1144 - it depends on iterator of underlying \p OrderedList
1145 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1146 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1147 deleting operations it is no guarantee that you iterate all item in the set.
1148 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
1150 @warning Use this iterator on the concurrent container for debugging purpose only.
1152 typedef iterator_type<false> iterator;
1154 /// Const forward iterator
1156 For iterator's features and requirements see \ref iterator
1158 typedef iterator_type<true> const_iterator;
1160 /// Returns a forward iterator addressing the first element in a split-list
1162 For empty list \code begin() == end() \endcode
1166 return iterator( m_List.begin(), m_List.end());
1169 /// Returns an iterator that addresses the location succeeding the last element in a split-list
1171 Do not use the value returned by <tt>end</tt> function to access any item.
1173 The returned value can be used only to control reaching the end of the split-list.
1174 For empty list \code begin() == end() \endcode
1178 return iterator( m_List.end(), m_List.end());
1181 /// Returns a forward const iterator addressing the first element in a split-list
1182 const_iterator begin() const
1186 /// Returns a forward const iterator addressing the first element in a split-list
1187 const_iterator cbegin() const
1189 return const_iterator( m_List.cbegin(), m_List.cend());
1192 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1193 const_iterator end() const
1197 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1198 const_iterator cend() const
1200 return const_iterator( m_List.cend(), m_List.cend());
1205 }} // namespace cds::intrusive
1207 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H