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_CONTAINER_IMPL_SKIP_LIST_SET_H
32 #define CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H
34 #include <cds/details/binary_functor_wrapper.h>
35 #include <cds/container/details/guarded_ptr_cast.h>
37 namespace cds { namespace container {
39 /// Lock-free skip-list set
40 /** @ingroup cds_nonintrusive_set
41 \anchor cds_nonintrusive_SkipListSet_hp
43 The implementation of well-known probabilistic data structure called skip-list
44 invented by W.Pugh in his papers:
45 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
46 - [1990] W.Pugh A Skip List Cookbook
48 A skip-list is a probabilistic data structure that provides expected logarithmic
49 time search without the need of rebalance. The skip-list is a collection of sorted
50 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
51 Each list has a level, ranging from 0 to 32. The bottom-level list contains
52 all the nodes, and each higher-level list is a sublist of the lower-level lists.
53 Each node is created with a random top level (with a random height), and belongs
54 to all lists up to that level. The probability that a node has the height 1 is 1/2.
55 The probability that a node has the height N is 1/2 ** N (more precisely,
56 the distribution depends on an random generator provided, but our generators
59 The lock-free variant of skip-list is implemented according to book
60 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
61 chapter 14.4 "A Lock-Free Concurrent Skiplist"
64 - \p GC - Garbage collector used.
65 - \p T - type to be stored in the list.
66 - \p Traits - set traits, default is \p skip_list::traits.
67 It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
68 istead of \p Traits template argument.
70 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
71 the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
72 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
73 when you try to create skip-list object.
75 @note There are several specializations of \p %SkipListSet for each \p GC. You should include:
76 - <tt><cds/container/skip_list_set_hp.h></tt> for \p gc::HP garbage collector
77 - <tt><cds/container/skip_list_set_dhp.h></tt> for \p gc::DHP garbage collector
78 - <tt><cds/container/skip_list_set_rcu.h></tt> for \ref cds_nonintrusive_SkipListSet_rcu "RCU type"
79 - <tt><cds/container/skip_list_set_nogc.h></tt> for \ref cds_nonintrusive_SkipListSet_nogc "non-deletable SkipListSet"
83 The class supports a forward iterator (\ref iterator and \ref const_iterator).
84 The iteration is ordered.
85 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
86 so, the element cannot be reclaimed while the iterator object is alive.
87 However, passing an iterator object between threads is dangerous.
89 \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
90 all elements in the set: any concurrent deletion can exclude the element
91 pointed by the iterator from the set, and your iteration can be terminated
92 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
94 Remember, each iterator object requires 2 additional hazard pointers, that may be
95 a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of
98 The iterator class supports the following minimalistic interface:
105 iterator( iterator const& s);
107 value_type * operator ->() const;
108 value_type& operator *() const;
111 iterator& operator ++();
114 iterator& operator = (const iterator& src);
116 bool operator ==(iterator const& i ) const;
117 bool operator !=(iterator const& i ) const;
120 Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
125 #ifdef CDS_DOXYGEN_INVOKED
126 typename Traits = skip_list::traits
132 #ifdef CDS_DOXYGEN_INVOKED
133 protected intrusive::SkipListSet< GC, T, Traits >
135 protected details::make_skip_list_set< GC, T, Traits >::type
139 typedef details::make_skip_list_set< GC, T, Traits > maker;
140 typedef typename maker::type base_class;
143 typedef GC gc; ///< Garbage collector used
144 typedef T value_type; ///< @anchor cds_containewr_SkipListSet_value_type Value type to be stored in the set
145 typedef Traits traits; ///< Options specified
147 typedef typename base_class::back_off back_off; ///< Back-off strategy
148 typedef typename traits::allocator allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
149 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
150 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
151 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
152 typedef typename traits::random_level_generator random_level_generator; ///< random level generator
153 typedef typename traits::stat stat; ///< internal statistics type
155 static size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the skip-list
159 typedef typename maker::node_type node_type;
160 typedef typename maker::node_allocator node_allocator;
162 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
167 typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
171 unsigned int random_level()
173 return base_class::random_level();
183 /// Destructor destroys the set object
188 ///@name Forward iterators (only for debugging purpose)
192 The forward iterator has some features:
193 - it has no post-increment operator
194 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
195 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
196 may be thrown if the limit of guard count per thread is exceeded.
197 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
198 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
199 deleting operations there is no guarantee that you iterate all item in the list.
200 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
202 @warning Use this iterator on the concurrent container for debugging purpose only.
204 The iterator interface:
208 // Default constructor
212 iterator( iterator const& src );
214 // Dereference operator
215 value_type * operator ->() const;
217 // Dereference operator
218 value_type& operator *() const;
220 // Preincrement operator
221 iterator& operator ++();
223 // Assignment operator
224 iterator& operator = (iterator const& src);
226 // Equality operators
227 bool operator ==(iterator const& i ) const;
228 bool operator !=(iterator const& i ) const;
232 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
234 /// Const iterator type
235 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
237 /// Returns a forward iterator addressing the first element in a set
240 return iterator( base_class::begin() );
243 /// Returns a forward const iterator addressing the first element in a set
244 const_iterator begin() const
246 return const_iterator( base_class::begin() );
249 /// Returns a forward const iterator addressing the first element in a set
250 const_iterator cbegin() const
252 return const_iterator( base_class::cbegin() );
255 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
258 return iterator( base_class::end() );
261 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
262 const_iterator end() const
264 return const_iterator( base_class::end() );
267 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
268 const_iterator cend() const
270 return const_iterator( base_class::cend() );
277 The function creates a node with copy of \p val value
278 and then inserts the node created into the set.
280 The type \p Q should contain as minimum the complete key for the node.
281 The object of \ref value_type should be constructible from a value of type \p Q.
282 In trivial case, \p Q is equal to \ref value_type.
284 Returns \p true if \p val is inserted into the set, \p false otherwise.
286 template <typename Q>
287 bool insert( Q const& val )
289 scoped_node_ptr sp( node_allocator().New( random_level(), val ));
290 if ( base_class::insert( *sp.get() )) {
299 The function allows to split creating of new item into two part:
300 - create item with key only
301 - insert new item into the set
302 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
304 The functor signature is:
306 void func( value_type& val );
308 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
309 \p val no any other changes could be made on this set's item by concurrent threads.
310 The user-defined functor is called only if the inserting is success.
312 template <typename Q, typename Func>
313 bool insert( Q const& val, Func f )
315 scoped_node_ptr sp( node_allocator().New( random_level(), val ));
316 if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
325 The operation performs inserting or changing data with lock-free manner.
327 If the \p val key not found in the set, then the new item created from \p val
328 will be inserted into the set iff \p bInsert is \p true.
329 Otherwise, if \p val is found, the functor \p func will be called with the item found.
331 The functor \p Func signature:
334 void operator()( bool bNew, value_type& item, const Q& val );
338 - \p bNew - \p true if the item has been inserted, \p false otherwise
339 - \p item - item of the set
340 - \p val - argument \p key passed into the \p %update() function
342 The functor may change non-key fields of the \p item; however, \p func must guarantee
343 that during changing no any other modifications could be made on this item by concurrent threads.
345 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
346 i.e. the item has been inserted or updated,
347 \p second is \p true if new item has been added or \p false if the item with key equal to \p val
350 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
352 template <typename Q, typename Func>
353 std::pair<bool, bool> update( const Q& val, Func func, bool bInsert = true )
355 scoped_node_ptr sp( node_allocator().New( random_level(), val ));
356 std::pair<bool, bool> bRes = base_class::update( *sp,
357 [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); },
359 if ( bRes.first && bRes.second )
364 template <typename Q, typename Func>
365 CDS_DEPRECATED("ensure() is deprecated, use update()")
366 std::pair<bool, bool> ensure( const Q& val, Func func )
368 return update( val, func, true );
372 /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
374 Returns \p true if inserting successful, \p false otherwise.
376 template <typename... Args>
377 bool emplace( Args&&... args )
379 scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
380 if ( base_class::insert( *sp.get() )) {
387 /// Delete \p key from the set
388 /** \anchor cds_nonintrusive_SkipListSet_erase_val
390 The set item comparator should be able to compare the type \p value_type
393 Return \p true if key is found and deleted, \p false otherwise
395 template <typename Q>
396 bool erase( Q const& key )
398 return base_class::erase( key );
401 /// Deletes the item from the set using \p pred predicate for searching
403 The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_val "erase(Q const&)"
404 but \p pred is used for key comparing.
405 \p Less functor has the interface like \p std::less.
406 \p Less must imply the same element order as the comparator used for building the set.
408 template <typename Q, typename Less>
409 bool erase_with( Q const& key, Less pred )
412 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() );
415 /// Delete \p key from the set
416 /** \anchor cds_nonintrusive_SkipListSet_erase_func
418 The function searches an item with key \p key, calls \p f functor
419 and deletes the item. If \p key is not found, the functor is not called.
421 The functor \p Func interface:
424 void operator()(value_type const& val);
428 Since the key of \p value_type is not explicitly specified,
429 template parameter \p Q defines the key type to search in the list.
430 The list item comparator should be able to compare the type \p T of list item
433 Return \p true if key is found and deleted, \p false otherwise
435 template <typename Q, typename Func>
436 bool erase( Q const& key, Func f )
438 return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
441 /// Deletes the item from the set using \p pred predicate for searching
443 The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_func "erase(Q const&, Func)"
444 but \p pred is used for key comparing.
445 \p Less functor has the interface like \p std::less.
446 \p Less must imply the same element order as the comparator used for building the set.
448 template <typename Q, typename Less, typename Func>
449 bool erase_with( Q const& key, Less pred, Func f )
452 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
453 [&f]( node_type const& node) { f( node.m_Value ); } );
456 /// Extracts the item from the set with specified \p key
457 /** \anchor cds_nonintrusive_SkipListSet_hp_extract
458 The function searches an item with key equal to \p key in the set,
459 unlinks it from the set, and returns it as \p guarded_ptr.
460 If \p key is not found the function returns an empty guarded pointer.
462 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
464 The item extracted is freed automatically by garbage collector \p GC
465 when returned \p guarded_ptr object will be destroyed or released.
466 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
470 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
474 skip_list::guarded_ptr gp(theList.extract( 5 ))
479 // Destructor of gp releases internal HP guard and frees the pointer
483 template <typename Q>
484 guarded_ptr extract( Q const& key )
487 base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
491 /// Extracts the item from the set with comparing functor \p pred
493 The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_extract "extract(Q const&)"
494 but \p pred predicate is used for key comparing.
496 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
498 \p pred must imply the same element order as the comparator used for building the set.
500 template <typename Q, typename Less>
501 guarded_ptr extract_with( Q const& key, Less pred )
504 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
506 base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
510 /// Extracts an item with minimal key from the set
512 The function searches an item with minimal key, unlinks it, and returns pointer to the item found as \p guarded_ptr.
513 If the skip-list is empty the function returns an empty guarded pointer.
515 The item extracted is freed automatically by garbage collector \p GC
516 when returned \p guarded_ptr object will be destroyed or released.
517 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
521 typedef cds::continer::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
525 skip_list::guarded_ptr gp( theList.extract_min());
530 // Destructor of gp releases internal HP guard and then frees the pointer
534 guarded_ptr extract_min()
537 base_class::extract_min_( gp.guard() );
541 /// Extracts an item with maximal key from the set
543 The function searches an item with maximal key, unlinks it, and returns the pointer to item found as \p guarded_ptr.
544 If the skip-list is empty the function returns an empty guarded pointer.
546 The item found is freed by garbage collector \p GC automatically
547 when returned \p guarded_ptr object will be destroyed or released.
548 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
552 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
556 skip_list::guarded_ptr gp( theList.extract_max());
561 // Destructor of gp releases internal HP guard and then frees the pointer
565 guarded_ptr extract_max()
568 base_class::extract_max_( gp.guard() );
573 /** \anchor cds_nonintrusive_SkipListSet_find_func
575 The function searches the item with key equal to \p key and calls the functor \p f for item found.
576 The interface of \p Func functor is:
579 void operator()( value_type& item, Q& key );
582 where \p item is the item found, \p key is the <tt>find</tt> function argument.
584 The functor may change non-key fields of \p item. Note that the functor is only guarantee
585 that \p item cannot be disposed during functor is executing.
586 The functor does not serialize simultaneous access to the set's \p item. If such access is
587 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
589 Note the hash functor specified for class \p Traits template parameter
590 should accept a parameter of type \p Q that may be not the same as \p value_type.
592 The function returns \p true if \p key is found, \p false otherwise.
594 template <typename Q, typename Func>
595 bool find( Q& key, Func f )
597 return base_class::find( key, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
600 template <typename Q, typename Func>
601 bool find( Q const& key, Func f )
603 return base_class::find( key, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
607 /// Finds \p key using \p pred predicate for searching
609 The function is an analog of \ref cds_nonintrusive_SkipListSet_find_func "find(Q&, Func)"
610 but \p pred is used for key comparing.
611 \p Less functor has the interface like \p std::less.
612 \p Less must imply the same element order as the comparator used for building the set.
614 template <typename Q, typename Less, typename Func>
615 bool find_with( Q& key, Less pred, Func f )
618 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
619 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
622 template <typename Q, typename Less, typename Func>
623 bool find_with( Q const& key, Less pred, Func f )
626 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
627 [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } );
631 /// Checks whether the set contains \p key
633 The function searches the item with key equal to \p key
634 and returns \p true if it is found, and \p false otherwise.
636 template <typename Q>
637 bool contains( Q const& key )
639 return base_class::contains( key );
642 template <typename Q>
643 CDS_DEPRECATED("deprecated, use contains()")
644 bool find( Q const& key )
646 return contains( key );
650 /// Checks whether the set contains \p key using \p pred predicate for searching
652 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
653 \p Less functor has the interface like \p std::less.
654 \p Less must imply the same element order as the comparator used for building the set.
656 template <typename Q, typename Less>
657 bool contains( Q const& key, Less pred )
660 return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
663 template <typename Q, typename Less>
664 CDS_DEPRECATED("deprecated, use contains()")
665 bool find_with( Q const& key, Less pred )
667 return contains( key, pred );
671 /// Finds \p key and return the item found
672 /** \anchor cds_nonintrusive_SkipListSet_hp_get
673 The function searches the item with key equal to \p key
674 and returns a guarded pointer to the item found.
675 If \p key is not found the function returns an empty guarded pointer.
677 It is safe when a concurrent thread erases the item returned in \p result guarded pointer.
678 In this case the item will be freed later by garbage collector \p GC automatically
679 when \p guarded_ptr object will be destroyed or released.
680 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
684 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
688 skip_list::guarded_ptr gp( theList.get( 5 ));
689 if ( theList.get( 5 )) {
693 // Destructor of guarded_ptr releases internal HP guard
697 Note the compare functor specified for class \p Traits template parameter
698 should accept a parameter of type \p Q that can be not the same as \p value_type.
700 template <typename Q>
701 guarded_ptr get( Q const& key )
704 base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
708 /// Finds \p key and return the item found
710 The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get(Q const&)"
711 but \p pred is used for comparing the keys.
713 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
715 \p pred must imply the same element order as the comparator used for building the set.
717 template <typename Q, typename Less>
718 guarded_ptr get_with( Q const& key, Less pred )
721 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
723 base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
727 /// Clears the set (not atomic).
729 The function deletes all items from the set.
730 The function is not atomic, thus, in multi-threaded environment with parallel insertions
734 assert( set.empty() );
736 the assertion could be raised.
738 For each item the \ref disposer provided by \p Traits template parameter will be called.
745 /// Checks if the set is empty
748 return base_class::empty();
751 /// Returns item count in the set
753 The value returned depends on item counter type provided by \p Traits template parameter.
754 If it is \p atomicity::empty_item_counter this function always returns 0.
755 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
756 member function for this purpose.
760 return base_class::size();
763 /// Returns const reference to internal statistics
764 stat const& statistics() const
766 return base_class::statistics();
770 }} // namespace cds::container
772 #endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H