2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_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 successful,
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 )
486 return base_class::extract_( key, typename base_class::key_comparator());
489 /// Extracts the item from the set with comparing functor \p pred
491 The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_extract "extract(Q const&)"
492 but \p pred predicate is used for key comparing.
494 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
496 \p pred must imply the same element order as the comparator used for building the set.
498 template <typename Q, typename Less>
499 guarded_ptr extract_with( Q const& key, Less pred )
502 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
503 return base_class::extract_( key, cds::opt::details::make_comparator_from_less<wrapped_less>());
506 /// Extracts an item with minimal key from the set
508 The function searches an item with minimal key, unlinks it, and returns pointer to the item found as \p guarded_ptr.
509 If the skip-list is empty the function returns an empty guarded pointer.
511 The item extracted is freed automatically by garbage collector \p GC
512 when returned \p guarded_ptr object will be destroyed or released.
513 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
517 typedef cds::continer::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
521 skip_list::guarded_ptr gp( theList.extract_min());
526 // Destructor of gp releases internal HP guard and then frees the pointer
530 guarded_ptr extract_min()
532 return base_class::extract_min_();
535 /// Extracts an item with maximal key from the set
537 The function searches an item with maximal key, unlinks it, and returns the pointer to item found as \p guarded_ptr.
538 If the skip-list is empty the function returns an empty guarded pointer.
540 The item found is freed by garbage collector \p GC automatically
541 when returned \p guarded_ptr object will be destroyed or released.
542 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
546 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
550 skip_list::guarded_ptr gp( theList.extract_max());
555 // Destructor of gp releases internal HP guard and then frees the pointer
559 guarded_ptr extract_max()
561 return base_class::extract_max_();
565 /** \anchor cds_nonintrusive_SkipListSet_find_func
567 The function searches the item with key equal to \p key and calls the functor \p f for item found.
568 The interface of \p Func functor is:
571 void operator()( value_type& item, Q& key );
574 where \p item is the item found, \p key is the <tt>find</tt> function argument.
576 The functor may change non-key fields of \p item. Note that the functor is only guarantee
577 that \p item cannot be disposed during functor is executing.
578 The functor does not serialize simultaneous access to the set's \p item. If such access is
579 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
581 Note the hash functor specified for class \p Traits template parameter
582 should accept a parameter of type \p Q that may be not the same as \p value_type.
584 The function returns \p true if \p key is found, \p false otherwise.
586 template <typename Q, typename Func>
587 bool find( Q& key, Func f )
589 return base_class::find( key, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
592 template <typename Q, typename Func>
593 bool find( Q const& key, Func f )
595 return base_class::find( key, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
599 /// Finds \p key using \p pred predicate for searching
601 The function is an analog of \ref cds_nonintrusive_SkipListSet_find_func "find(Q&, Func)"
602 but \p pred is used for key comparing.
603 \p Less functor has the interface like \p std::less.
604 \p Less must imply the same element order as the comparator used for building the set.
606 template <typename Q, typename Less, typename Func>
607 bool find_with( Q& key, Less pred, Func f )
610 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
611 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
614 template <typename Q, typename Less, typename Func>
615 bool find_with( Q const& 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 const& v ) { f( node.m_Value, v ); } );
623 /// Checks whether the set contains \p key
625 The function searches the item with key equal to \p key
626 and returns \p true if it is found, and \p false otherwise.
628 template <typename Q>
629 bool contains( Q const& key )
631 return base_class::contains( key );
634 template <typename Q>
635 CDS_DEPRECATED("deprecated, use contains()")
636 bool find( Q const& key )
638 return contains( key );
642 /// Checks whether the set contains \p key using \p pred predicate for searching
644 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
645 \p Less functor has the interface like \p std::less.
646 \p Less must imply the same element order as the comparator used for building the set.
648 template <typename Q, typename Less>
649 bool contains( Q const& key, Less pred )
652 return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
655 template <typename Q, typename Less>
656 CDS_DEPRECATED("deprecated, use contains()")
657 bool find_with( Q const& key, Less pred )
659 return contains( key, pred );
663 /// Finds \p key and return the item found
664 /** \anchor cds_nonintrusive_SkipListSet_hp_get
665 The function searches the item with key equal to \p key
666 and returns a guarded pointer to the item found.
667 If \p key is not found the function returns an empty guarded pointer.
669 It is safe when a concurrent thread erases the item returned in \p result guarded pointer.
670 In this case the item will be freed later by garbage collector \p GC automatically
671 when \p guarded_ptr object will be destroyed or released.
672 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
676 typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
680 skip_list::guarded_ptr gp( theList.get( 5 ));
681 if ( theList.get( 5 )) {
685 // Destructor of guarded_ptr releases internal HP guard
689 Note the compare functor specified for class \p Traits template parameter
690 should accept a parameter of type \p Q that can be not the same as \p value_type.
692 template <typename Q>
693 guarded_ptr get( Q const& key )
695 return base_class::get_with_( key, typename base_class::key_comparator());
698 /// Finds \p key and return the item found
700 The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get(Q const&)"
701 but \p pred is used for comparing the keys.
703 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
705 \p pred must imply the same element order as the comparator used for building the set.
707 template <typename Q, typename Less>
708 guarded_ptr get_with( Q const& key, Less pred )
711 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
712 return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >());
715 /// Clears the set (not atomic).
717 The function deletes all items from the set.
718 The function is not atomic, thus, in multi-threaded environment with parallel insertions
722 assert( set.empty());
724 the assertion could be raised.
726 For each item the \ref disposer provided by \p Traits template parameter will be called.
733 /// Checks if the set is empty
736 return base_class::empty();
739 /// Returns item count in the set
741 The value returned depends on item counter type provided by \p Traits template parameter.
742 If it is \p atomicity::empty_item_counter this function always returns 0.
743 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
744 member function for this purpose.
748 return base_class::size();
751 /// Returns const reference to internal statistics
752 stat const& statistics() const
754 return base_class::statistics();
758 }} // namespace cds::container
760 #endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H