3 #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H
4 #define __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H
6 #include <cds/details/binary_functor_wrapper.h>
7 #include <cds/gc/guarded_ptr.h>
8 #include <cds/container/details/guarded_ptr_cast.h>
10 namespace cds { namespace container {
12 /// Lock-free skip-list set
13 /** @ingroup cds_nonintrusive_set
14 \anchor cds_nonintrusive_SkipListSet_hp
16 The implementation of well-known probabilistic data structure called skip-list
17 invented by W.Pugh in his papers:
18 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
19 - [1990] W.Pugh A Skip List Cookbook
21 A skip-list is a probabilistic data structure that provides expected logarithmic
22 time search without the need of rebalance. The skip-list is a collection of sorted
23 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
24 Each list has a level, ranging from 0 to 32. The bottom-level list contains
25 all the nodes, and each higher-level list is a sublist of the lower-level lists.
26 Each node is created with a random top level (with a random height), and belongs
27 to all lists up to that level. The probability that a node has the height 1 is 1/2.
28 The probability that a node has the height N is 1/2 ** N (more precisely,
29 the distribution depends on an random generator provided, but our generators
32 The lock-free variant of skip-list is implemented according to book
33 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
34 chapter 14.4 "A Lock-Free Concurrent Skiplist"
37 - \p GC - Garbage collector used.
38 - \p T - type to be stored in the list.
39 - \p Traits - type traits. See skip_list::type_traits for explanation.
41 It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
43 Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
44 - opt::compare - key comparison functor. No default functor is provided.
45 If the option is not specified, the opt::less is used.
46 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
47 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
48 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
49 or opt::v::sequential_consistent (sequentially consisnent memory model).
50 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
51 user-provided one. See skip_list::random_level_generator option description for explanation.
52 Default is \p %skip_list::turbo_pascal.
53 - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
54 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
55 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
57 \warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
58 the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
59 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
60 when you try to create skip-list object.
62 \note There are several specializations of \p %SkipListSet for each \p GC. You should include:
63 - <tt><cds/container/skip_list_set_hp.h></tt> for \p gc::HP garbage collector
64 - <tt><cds/container/skip_list_set_dhp.h></tt> for \p gc::DHP garbage collector
65 - <tt><cds/container/skip_list_set_rcu.h></tt> for \ref cds_nonintrusive_SkipListSet_rcu "RCU type"
66 - <tt><cds/container/skip_list_set_nogc.h></tt> for \ref cds_nonintrusive_SkipListSet_nogc "non-deletable SkipListSet"
70 The class supports a forward iterator (\ref iterator and \ref const_iterator).
71 The iteration is ordered.
72 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
73 so, the element cannot be reclaimed while the iterator object is alive.
74 However, passing an iterator object between threads is dangerous.
76 \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
77 all elements in the set: any concurrent deletion can exclude the element
78 pointed by the iterator from the set, and your iteration can be terminated
79 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
81 Remember, each iterator object requires 2 additional hazard pointers, that may be
82 a limited resource for \p GC like \p gc::HP (for \p gc::PTB the count of
85 The iterator class supports the following minimalistic interface:
92 iterator( iterator const& s);
94 value_type * operator ->() const;
95 value_type& operator *() const;
98 iterator& operator ++();
101 iterator& operator = (const iterator& src);
103 bool operator ==(iterator const& i ) const;
104 bool operator !=(iterator const& i ) const;
107 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
113 #ifdef CDS_DOXYGEN_INVOKED
114 typename Traits = skip_list::type_traits
120 #ifdef CDS_DOXYGEN_INVOKED
121 protected intrusive::SkipListSet< GC, T, Traits >
123 protected details::make_skip_list_set< GC, T, Traits >::type
127 typedef details::make_skip_list_set< GC, T, Traits > maker;
128 typedef typename maker::type base_class;
131 typedef typename base_class::gc gc ; ///< Garbage collector used
132 typedef T value_type ; ///< @anchor cds_containewr_SkipListSet_value_type Value type stored in the set
133 typedef Traits options ; ///< Options specified
135 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
136 typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
137 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
138 typedef typename maker::key_comparator key_comparator ; ///< key comparison functor
139 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
140 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
141 typedef typename options::stat stat ; ///< internal statistics type
145 typedef typename maker::node_type node_type;
146 typedef typename maker::node_allocator node_allocator;
148 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
153 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
157 unsigned int random_level()
159 return base_class::random_level();
169 /// Destructor destroys the set object
175 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
177 /// Const iterator type
178 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
180 /// Returns a forward iterator addressing the first element in a set
183 return iterator( base_class::begin() );
186 /// Returns a forward const iterator addressing the first element in a set
187 const_iterator begin() const
189 return const_iterator( base_class::begin() );
192 /// Returns a forward const iterator addressing the first element in a set
193 const_iterator cbegin() const
195 return const_iterator( base_class::cbegin() );
198 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
201 return iterator( base_class::end() );
204 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
205 const_iterator end() const
207 return const_iterator( base_class::end() );
210 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
211 const_iterator cend() const
213 return const_iterator( base_class::cend() );
219 The function creates a node with copy of \p val value
220 and then inserts the node created into the set.
222 The type \p Q should contain as minimum the complete key for the node.
223 The object of \ref value_type should be constructible from a value of type \p Q.
224 In trivial case, \p Q is equal to \ref value_type.
226 Returns \p true if \p val is inserted into the set, \p false otherwise.
228 template <typename Q>
229 bool insert( Q const& val )
231 scoped_node_ptr sp( node_allocator().New( random_level(), val ));
232 if ( base_class::insert( *sp.get() )) {
241 The function allows to split creating of new item into two part:
242 - create item with key only
243 - insert new item into the set
244 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
246 The functor signature is:
248 void func( value_type& val );
250 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
251 \p val no any other changes could be made on this set's item by concurrent threads.
252 The user-defined functor is called only if the inserting is success. It may be passed by reference
255 template <typename Q, typename Func>
256 bool insert( Q const& val, Func f )
258 scoped_node_ptr sp( node_allocator().New( random_level(), val ));
259 if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
266 /// Ensures that the item exists in the set
268 The operation performs inserting or changing data with lock-free manner.
270 If the \p val key not found in the set, then the new item created from \p val
271 is inserted into the set. Otherwise, the functor \p func is called with the item found.
272 The functor \p Func should be a function with signature:
274 void func( bool bNew, value_type& item, const Q& val );
279 void operator()( bool bNew, value_type& item, const Q& val );
284 - \p bNew - \p true if the item has been inserted, \p false otherwise
285 - \p item - item of the set
286 - \p val - argument \p key passed into the \p ensure function
288 The functor may change non-key fields of the \p item; however, \p func must guarantee
289 that during changing no any other modifications could be made on this item by concurrent threads.
291 You may pass \p func argument by reference using \p std::ref
293 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
294 \p second is true if new item has been added or \p false if the item with \p key
295 already is in the set.
297 template <typename Q, typename Func>
298 std::pair<bool, bool> ensure( const Q& val, Func func )
300 scoped_node_ptr sp( node_allocator().New( random_level(), val ));
301 std::pair<bool, bool> bRes = base_class::ensure( *sp,
302 [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); });
303 if ( bRes.first && bRes.second )
308 /// Inserts data of type \ref cds_containewr_SkipListSet_value_type "value_type" constructed with <tt>std::forward<Args>(args)...</tt>
310 Returns \p true if inserting successful, \p false otherwise.
312 template <typename... Args>
313 bool emplace( Args&&... args )
315 scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
316 if ( base_class::insert( *sp.get() )) {
323 /// Delete \p key from the set
324 /** \anchor cds_nonintrusive_SkipListSet_erase_val
326 The set item comparator should be able to compare the type \p value_type
329 Return \p true if key is found and deleted, \p false otherwise
331 template <typename Q>
332 bool erase( Q const& key )
334 return base_class::erase( key );
337 /// Deletes the item from the set using \p pred predicate for searching
339 The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_val "erase(Q const&)"
340 but \p pred is used for key comparing.
341 \p Less functor has the interface like \p std::less.
342 \p Less must imply the same element order as the comparator used for building the set.
344 template <typename Q, typename Less>
345 bool erase_with( Q const& key, Less pred )
347 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() );
350 /// Delete \p key from the set
351 /** \anchor cds_nonintrusive_SkipListSet_erase_func
353 The function searches an item with key \p key, calls \p f functor
354 and deletes the item. If \p key is not found, the functor is not called.
356 The functor \p Func interface:
359 void operator()(value_type const& val);
362 The functor may be passed by reference using <tt>boost:ref</tt>
364 Since the key of \p value_type is not explicitly specified,
365 template parameter \p Q defines the key type to search in the list.
366 The list item comparator should be able to compare the type \p T of list item
369 Return \p true if key is found and deleted, \p false otherwise
373 template <typename Q, typename Func>
374 bool erase( Q const& key, Func f )
376 return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
379 /// Deletes the item from the set using \p pred predicate for searching
381 The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_func "erase(Q const&, Func)"
382 but \p pred is used for key comparing.
383 \p Less functor has the interface like \p std::less.
384 \p Less must imply the same element order as the comparator used for building the set.
386 template <typename Q, typename Less, typename Func>
387 bool erase_with( Q const& key, Less pred, Func f )
389 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
390 [&f]( node_type const& node) { f( node.m_Value ); } );
393 /// Extracts the item from the set with specified \p key
394 /** \anchor cds_nonintrusive_SkipListSet_hp_extract
395 The function searches an item with key equal to \p key in the set,
396 unlinks it from the set, and returns it in \p result parameter.
397 If the item with key equal to \p key is not found the function returns \p false.
399 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
401 The item extracted is freed automatically by garbage collector \p GC
402 when returned \ref guarded_ptr object will be destroyed or released.
403 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
407 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
411 skip_list::guarded_ptr gp;
412 if ( theList.extract( gp, 5 ) ) {
416 // Destructor of gp releases internal HP guard and frees the pointer
420 template <typename Q>
421 bool extract( guarded_ptr& result, Q const& key )
423 return base_class::extract_( result.guard(), key, typename base_class::key_comparator() );
426 /// Extracts the item from the set with comparing functor \p pred
428 The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_extract "extract(Q const&)"
429 but \p pred predicate is used for key comparing.
431 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
433 \p pred must imply the same element order as the comparator used for building the set.
435 template <typename Q, typename Less>
436 bool extract_with( guarded_ptr& ptr, Q const& key, Less pred )
438 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
439 return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
442 /// Extracts an item with minimal key from the set
444 The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
445 If the skip-list is empty the function returns \p false.
447 The item extracted is freed automatically by garbage collector \p GC
448 when returned \ref guarded_ptr object will be destroyed or released.
449 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
453 typedef cds::continer::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
457 skip_list::guarded_ptr gp;
458 if ( theList.extract_min( gp )) {
462 // Destructor of gp releases internal HP guard and then frees the pointer
466 bool extract_min( guarded_ptr& result)
468 return base_class::extract_min_( result.guard() );
471 /// Extracts an item with maximal key from the set
473 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p result parameter.
474 If the skip-list is empty the function returns \p false.
476 The item found is freed by garbage collector \p GC automatically
477 when returned \ref guarded_ptr object will be destroyed or released.
478 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
482 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
486 skip_list::guarded_ptr gp;
487 if ( theList.extract_max( gp )) {
491 // Destructor of gp releases internal HP guard and then frees the pointer
495 bool extract_max( guarded_ptr& result )
497 return base_class::extract_max_( result.guard() );
500 /// Find the key \p val
501 /** \anchor cds_nonintrusive_SkipListSet_find_func
503 The function searches the item with key equal to \p val and calls the functor \p f for item found.
504 The interface of \p Func functor is:
507 void operator()( value_type& item, Q& val );
510 where \p item is the item found, \p val is the <tt>find</tt> function argument.
512 You may pass \p f argument by reference using \p std::ref
514 The functor may change non-key fields of \p item. Note that the functor is only guarantee
515 that \p item cannot be disposed during functor is executing.
516 The functor does not serialize simultaneous access to the set's \p item. If such access is
517 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
519 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
520 can modify both arguments.
522 Note the hash functor specified for class \p Traits template parameter
523 should accept a parameter of type \p Q that may be not the same as \p value_type.
525 The function returns \p true if \p val is found, \p false otherwise.
527 template <typename Q, typename Func>
528 bool find( Q& val, Func f )
530 return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
533 /// Finds the key \p val using \p pred predicate for searching
535 The function is an analog of \ref cds_nonintrusive_SkipListSet_find_func "find(Q&, Func)"
536 but \p pred is used for key comparing.
537 \p Less functor has the interface like \p std::less.
538 \p Less must imply the same element order as the comparator used for building the set.
540 template <typename Q, typename Less, typename Func>
541 bool find_with( Q& val, Less pred, Func f )
543 return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
544 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
547 /// Find the key \p val
548 /** \anchor cds_nonintrusive_SkipListSet_find_cfunc
550 The function searches the item with key equal to \p val and calls the functor \p f for item found.
551 The interface of \p Func functor is:
554 void operator()( value_type& item, Q const& val );
557 where \p item is the item found, \p val is the <tt>find</tt> function argument.
559 You may pass \p f argument by reference using \p std::ref
561 The functor may change non-key fields of \p item. Note that the functor is only guarantee
562 that \p item cannot be disposed during functor is executing.
563 The functor does not serialize simultaneous access to the set's \p item. If such access is
564 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
566 Note the hash functor specified for class \p Traits template parameter
567 should accept a parameter of type \p Q that may be not the same as \p value_type.
569 The function returns \p true if \p val is found, \p false otherwise.
571 template <typename Q, typename Func>
572 bool find( Q const& val, Func f )
574 return base_class::find( val, [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); });
577 /// Finds the key \p val using \p pred predicate for searching
579 The function is an analog of \ref cds_nonintrusive_SkipListSet_find_cfunc "find(Q const&, Func)"
580 but \p pred is used for key comparing.
581 \p Less functor has the interface like \p std::less.
582 \p Less must imply the same element order as the comparator used for building the set.
584 template <typename Q, typename Less, typename Func>
585 bool find_with( Q const& val, Less cmp, Func f )
587 return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
588 [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } );
591 /// Find the key \p val
592 /** \anchor cds_nonintrusive_SkipListSet_find_val
594 The function searches the item with key equal to \p val
595 and returns \p true if it is found, and \p false otherwise.
597 Note the hash functor specified for class \p Traits template parameter
598 should accept a parameter of type \p Q that may be not the same as \ref value_type.
600 template <typename Q>
601 bool find( Q const& val )
603 return base_class::find( val );
606 /// Finds the key \p val using \p pred predicate for searching
608 The function is an analog of \ref cds_nonintrusive_SkipListSet_find_val "find(Q const&)"
609 but \p pred is used for key comparing.
610 \p Less functor has the interface like \p std::less.
611 \p Less must imply the same element order as the comparator used for building the set.
613 template <typename Q, typename Less>
614 bool find_with( Q const& val, Less pred )
616 return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
619 /// Finds \p key and return the item found
620 /** \anchor cds_nonintrusive_SkipListSet_hp_get
621 The function searches the item with key equal to \p key
622 and assigns the item found to guarded pointer \p result.
623 The function returns \p true if \p key is found, and \p false otherwise.
624 If \p key is not found the \p result parameter is left unchanged.
626 It is safe when a concurrent thread erases the item returned in \p result guarded pointer.
627 In this case the item will be freed later by garbage collector \p GC automatically
628 when \p guarded_ptr object will be destroyed or released.
629 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
633 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
637 skip_list::guarded_ptr gp;
638 if ( theList.get( gp, 5 ) ) {
642 // Destructor of guarded_ptr releases internal HP guard
646 Note the compare functor specified for class \p Traits template parameter
647 should accept a parameter of type \p Q that can be not the same as \p value_type.
649 template <typename Q>
650 bool get( guarded_ptr& result, Q const& key )
652 return base_class::get_with_( result.guard(), key, typename base_class::key_comparator() );
655 /// Finds \p key and return the item found
657 The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get( guarded_ptr&, Q const&)"
658 but \p pred is used for comparing the keys.
660 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
662 \p pred must imply the same element order as the comparator used for building the set.
664 template <typename Q, typename Less>
665 bool get_with( guarded_ptr& result, Q const& key, Less pred )
667 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
668 return base_class::get_with_( result.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
671 /// Clears the set (non-atomic).
673 The function deletes all items from the set.
674 The function is not atomic, thus, in multi-threaded environment with parallel insertions
678 assert( set.empty() );
680 the assertion could be raised.
682 For each item the \ref disposer provided by \p Traits template parameter will be called.
689 /// Checks if the set is empty
692 return base_class::empty();
695 /// Returns item count in the set
697 The value returned depends on item counter type provided by \p Traits template parameter.
698 If it is atomicity::empty_item_counter this function always returns 0.
699 Therefore, the function is not suitable for checking the set emptiness, use \ref empty
700 member function for this purpose.
704 return base_class::size();
707 /// Returns const reference to internal statistics
708 stat const& statistics() const
710 return base_class::statistics();
715 }} // namespace cds::container
717 #endif // #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H