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_IMPL_SKIP_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
34 #include <type_traits>
36 #include <functional> // ref
37 #include <cds/intrusive/details/skip_list_base.h>
38 #include <cds/opt/compare.h>
39 #include <cds/details/binary_functor_wrapper.h>
41 namespace cds { namespace intrusive {
44 namespace skip_list { namespace details {
46 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
50 typedef NodeTraits node_traits;
51 typedef BackOff back_off;
52 typedef typename node_traits::node_type node_type;
53 typedef typename node_traits::value_type value_type;
54 static CDS_CONSTEXPR bool const c_isConst = IsConst;
56 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type value_ref;
59 typedef typename node_type::marked_ptr marked_ptr;
60 typedef typename node_type::atomic_marked_ptr atomic_marked_ptr;
62 typename gc::Guard m_guard;
66 static value_type * gc_protect( marked_ptr p )
68 return node_traits::to_value_ptr( p.ptr());
78 if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
79 // Current node is marked as deleted. So, its next pointer can point to anything
80 // In this case we interrupt our iteration and returns end() iterator.
85 marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
86 node_type * pp = p.ptr();
88 // p is marked as deleted. Spin waiting for physical removal
92 else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits()) {
93 // p is marked as deleted. Spin waiting for physical removal
103 public: // for internal use only!!!
104 iterator( node_type& refHead )
110 marked_ptr p = m_guard.protect( refHead[0], gc_protect );
117 node_type * pp = p.ptr();
118 // Logically deleted node is marked from highest level
119 if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
133 iterator( iterator const& s)
134 : m_pNode( s.m_pNode )
136 m_guard.assign( node_traits::to_value_ptr(m_pNode));
139 value_type * operator ->() const
141 assert( m_pNode != nullptr );
142 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
144 return node_traits::to_value_ptr( m_pNode );
147 value_ref operator *() const
149 assert( m_pNode != nullptr );
150 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
152 return *node_traits::to_value_ptr( m_pNode );
156 iterator& operator ++()
162 iterator& operator =(const iterator& src)
164 m_pNode = src.m_pNode;
165 m_guard.copy( src.m_guard );
169 template <typename Bkoff, bool C>
170 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
172 return m_pNode == i.m_pNode;
174 template <typename Bkoff, bool C>
175 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
177 return !( *this == i );
180 }} // namespace skip_list::details
183 /// Lock-free skip-list set
184 /** @ingroup cds_intrusive_map
185 @anchor cds_intrusive_SkipListSet_hp
187 The implementation of well-known probabilistic data structure called skip-list
188 invented by W.Pugh in his papers:
189 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
190 - [1990] W.Pugh A Skip List Cookbook
192 A skip-list is a probabilistic data structure that provides expected logarithmic
193 time search without the need of rebalance. The skip-list is a collection of sorted
194 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
195 Each list has a level, ranging from 0 to 32. The bottom-level list contains
196 all the nodes, and each higher-level list is a sublist of the lower-level lists.
197 Each node is created with a random top level (with a random height), and belongs
198 to all lists up to that level. The probability that a node has the height 1 is 1/2.
199 The probability that a node has the height N is 1/2 ** N (more precisely,
200 the distribution depends on an random generator provided, but our generators
203 The lock-free variant of skip-list is implemented according to book
204 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
205 chapter 14.4 "A Lock-Free Concurrent Skiplist".
207 <b>Template arguments</b>:
208 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T, see \p skip_list::node.
209 - \p T - type to be stored in the list. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
210 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
211 - \p Traits - skip-list traits, default is \p skip_list::traits.
212 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
215 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
216 the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
217 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
218 when you try to create skip-list object.
220 There are several specializations of \p %SkipListSet for each \p GC. You should include:
221 - <tt><cds/intrusive/skip_list_hp.h></tt> for \p gc::HP garbage collector
222 - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
223 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for append-only set
224 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
228 The class supports a forward iterator (\ref iterator and \ref const_iterator).
229 The iteration is ordered.
230 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
231 so, the element cannot be reclaimed while the iterator object is alive.
232 However, passing an iterator object between threads is dangerous.
234 @warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
235 all elements in the set: any concurrent deletion can exclude the element
236 pointed by the iterator from the set, and your iteration can be terminated
237 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
239 Remember, each iterator object requires 2 additional hazard pointers, that may be
240 a limited resource for \p GC like as \p gc::HP (for \p gc::DHP the count of
241 guards is unlimited).
243 The iterator class supports the following minimalistic interface:
250 iterator( iterator const& s);
252 value_type * operator ->() const;
253 value_type& operator *() const;
256 iterator& operator ++();
259 iterator& operator = (const iterator& src);
261 bool operator ==(iterator const& i ) const;
262 bool operator !=(iterator const& i ) const;
265 Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
269 You should incorporate \p skip_list::node into your struct \p T and provide
270 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
271 define a struct based on \p skip_list::traits.
273 Example for \p gc::HP and base hook:
275 // Include GC-related skip-list specialization
276 #include <cds/intrusive/skip_list_hp.h>
278 // Data stored in skip list
279 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
288 // my_data compare functor
290 int operator()( const my_data& d1, const my_data& d2 )
292 return d1.strKey.compare( d2.strKey );
295 int operator()( const my_data& d, const std::string& s )
297 return d.strKey.compare(s);
300 int operator()( const std::string& s, const my_data& d )
302 return s.compare( d.strKey );
307 // Declare your traits
308 struct my_traits: public cds::intrusive::skip_list::traits
310 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
311 typedef my_data_cmp compare;
314 // Declare skip-list set type
315 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
318 Equivalent option-based code:
320 // GC-related specialization
321 #include <cds/intrusive/skip_list_hp.h>
330 // Declare option-based skip-list set
331 typedef cds::intrusive::SkipListSet< cds::gc::HP
333 , typename cds::intrusive::skip_list::make_traits<
334 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
335 ,cds::intrusive::opt::compare< my_data_cmp >
344 #ifdef CDS_DOXYGEN_INVOKED
345 ,typename Traits = skip_list::traits
353 typedef GC gc; ///< Garbage collector
354 typedef T value_type; ///< type of value stored in the skip-list
355 typedef Traits traits; ///< Traits template parameter
357 typedef typename traits::hook hook; ///< hook type
358 typedef typename hook::node_type node_type; ///< node type
360 # ifdef CDS_DOXYGEN_INVOKED
361 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
363 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
366 typedef typename traits::disposer disposer; ///< item disposer
367 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
369 typedef typename traits::item_counter item_counter; ///< Item counting policy
370 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
371 typedef typename traits::random_level_generator random_level_generator; ///< random level generator
372 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
373 typedef typename traits::back_off back_off; ///< Back-off strategy
374 typedef typename traits::stat stat; ///< internal statistics type
377 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
379 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
381 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
382 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
384 static unsigned int const c_nMaxHeight = std::conditional<
385 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
386 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
387 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
391 static unsigned int const c_nMinHeight = 5;
394 // c_nMaxHeight * 2 - pPred/pSucc guards
395 // + 1 - for erase, unlink
397 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2; ///< Count of hazard pointer required for the skip-list
400 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
401 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
405 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
407 typedef typename std::conditional<
408 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
409 ,intrusive_node_builder
410 ,typename traits::internal_node_builder
411 >::type node_builder;
413 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
416 node_type * pPrev[ c_nMaxHeight ];
417 node_type * pSucc[ c_nMaxHeight ];
419 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
420 node_type * pCur; // guarded by one of guards
425 /// Default constructor
427 The constructor checks whether the count of guards is enough
428 for skip-list and may raise an exception if not.
431 : m_Head( c_nMaxHeight )
432 , m_nHeight( c_nMinHeight )
434 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
436 gc::check_available_guards( c_nHazardPtrCount );
438 // Barrier for head node
439 atomics::atomic_thread_fence( memory_model::memory_order_release );
442 /// Clears and destructs the skip-list
449 ///@name Forward iterators (only for debugging purpose)
453 The forward iterator has some features:
454 - it has no post-increment operator
455 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
456 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
457 may be thrown if the limit of guard count per thread is exceeded.
458 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
459 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
460 deleting operations there is no guarantee that you iterate all item in the list.
461 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
463 @warning Use this iterator on the concurrent container for debugging purpose only.
465 The iterator interface:
469 // Default constructor
473 iterator( iterator const& src );
475 // Dereference operator
476 value_type * operator ->() const;
478 // Dereference operator
479 value_type& operator *() const;
481 // Preincrement operator
482 iterator& operator ++();
484 // Assignment operator
485 iterator& operator = (iterator const& src);
487 // Equality operators
488 bool operator ==(iterator const& i ) const;
489 bool operator !=(iterator const& i ) const;
493 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
495 /// Const iterator type
496 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
498 /// Returns a forward iterator addressing the first element in a set
501 return iterator( *m_Head.head());
504 /// Returns a forward const iterator addressing the first element in a set
505 const_iterator begin() const
507 return const_iterator( *m_Head.head());
509 /// Returns a forward const iterator addressing the first element in a set
510 const_iterator cbegin() const
512 return const_iterator( *m_Head.head());
515 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
521 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
522 const_iterator end() const
524 return const_iterator();
526 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
527 const_iterator cend() const
529 return const_iterator();
536 The function inserts \p val in the set if it does not contain
537 an item with key equal to \p val.
539 Returns \p true if \p val is placed into the set, \p false otherwise.
541 bool insert( value_type& val )
543 return insert( val, []( value_type& ) {} );
548 This function is intended for derived non-intrusive containers.
550 The function allows to split creating of new item into two part:
551 - create item with key only
552 - insert new item into the set
553 - if inserting is success, calls \p f functor to initialize value-field of \p val.
555 The functor signature is:
557 void func( value_type& val );
559 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
560 \p val no any other changes could be made on this set's item by concurrent threads.
561 The user-defined functor is called only if the inserting is success.
563 template <typename Func>
564 bool insert( value_type& val, Func f )
566 typename gc::Guard gNew;
569 node_type * pNode = node_traits::to_node_ptr( val );
570 scoped_node_ptr scp( pNode );
571 unsigned int nHeight = pNode->height();
572 bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
573 bool bTowerMade = false;
578 if ( find_position( val, pos, key_comparator(), true )) {
579 // scoped_node_ptr deletes the node tower if we create it
583 m_Stat.onInsertFailed();
589 nHeight = pNode->height();
590 bTowerMade = pNode->has_tower();
594 if ( !insert_at_position( val, pNode, pos, f )) {
595 m_Stat.onInsertRetry();
599 increase_height( nHeight );
601 m_Stat.onAddNode( nHeight );
602 m_Stat.onInsertSuccess();
610 The operation performs inserting or changing data with lock-free manner.
612 If the item \p val is not found in the set, then \p val is inserted into the set
613 iff \p bInsert is \p true.
614 Otherwise, the functor \p func is called with item found.
615 The functor \p func signature is:
617 void func( bool bNew, value_type& item, value_type& val );
620 - \p bNew - \p true if the item has been inserted, \p false otherwise
621 - \p item - item of the set
622 - \p val - argument \p val passed into the \p %update() function
623 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
624 refer to the same thing.
626 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
627 i.e. the node has been inserted or updated,
628 \p second is \p true if new item has been added or \p false if the item with \p key
631 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
633 template <typename Func>
634 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
636 typename gc::Guard gNew;
639 node_type * pNode = node_traits::to_node_ptr( val );
640 scoped_node_ptr scp( pNode );
641 unsigned int nHeight = pNode->height();
642 bool bTowerOk = pNode->has_tower();
643 bool bTowerMade = false;
648 bool bFound = find_position( val, pos, key_comparator(), true );
650 // scoped_node_ptr deletes the node tower if we create it before
654 func( false, *node_traits::to_value_ptr(pos.pCur), val );
655 m_Stat.onUpdateExist();
656 return std::make_pair( true, false );
661 return std::make_pair( false, false );
666 nHeight = pNode->height();
667 bTowerMade = pNode->has_tower();
671 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
672 m_Stat.onInsertRetry();
676 increase_height( nHeight );
679 m_Stat.onAddNode( nHeight );
680 m_Stat.onUpdateNew();
681 return std::make_pair( true, true );
685 template <typename Func>
686 CDS_DEPRECATED("ensure() is deprecated, use update()")
687 std::pair<bool, bool> ensure( value_type& val, Func func )
689 return update( val, func, true );
693 /// Unlinks the item \p val from the set
695 The function searches the item \p val in the set and unlink it from the set
696 if it is found and is equal to \p val.
698 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
699 and deletes the item found. \p %unlink() finds an item by key and deletes it
700 only if \p val is an item of that set, i.e. the pointer to item found
701 is equal to <tt> &val </tt>.
703 The \p disposer specified in \p Traits class template parameter is called
704 by garbage collector \p GC asynchronously.
706 The function returns \p true if success and \p false otherwise.
708 bool unlink( value_type& val )
712 if ( !find_position( val, pos, key_comparator(), false )) {
713 m_Stat.onUnlinkFailed();
717 node_type * pDel = pos.pCur;
718 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
720 unsigned int nHeight = pDel->height();
721 typename gc::Guard gDel;
722 gDel.assign( node_traits::to_value_ptr(pDel));
724 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
726 m_Stat.onRemoveNode( nHeight );
727 m_Stat.onUnlinkSuccess();
731 m_Stat.onUnlinkFailed();
735 /// Extracts the item from the set with specified \p key
736 /** \anchor cds_intrusive_SkipListSet_hp_extract
737 The function searches an item with key equal to \p key in the set,
738 unlinks it from the set, and returns it as \p guarded_ptr object.
739 If \p key is not found the function returns an empty guarded pointer.
741 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
743 The \p disposer specified in \p Traits class template parameter is called automatically
744 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
745 will be destroyed or released.
746 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
750 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
754 skip_list::guarded_ptr gp(theList.extract( 5 ));
759 // Destructor of gp releases internal HP guard
763 template <typename Q>
764 guarded_ptr extract( Q const& key )
766 return extract_( key, key_comparator());
769 /// Extracts the item from the set with comparing functor \p pred
771 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
772 but \p pred predicate is used for key comparing.
774 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
776 \p pred must imply the same element order as the comparator used for building the set.
778 template <typename Q, typename Less>
779 guarded_ptr extract_with( Q const& key, Less pred )
782 return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
785 /// Extracts an item with minimal key from the list
787 The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
788 If the skip-list is empty the function returns an empty guarded pointer.
790 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
791 It means that the function gets leftmost item and tries to unlink it.
792 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
793 So, the function returns the item with minimum key at the moment of list traversing.
795 The \p disposer specified in \p Traits class template parameter is called
796 by garbage collector \p GC automatically when returned \p guarded_ptr object
797 will be destroyed or released.
798 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
802 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
806 skip_list::guarded_ptr gp(theList.extract_min());
811 // Destructor of gp releases internal HP guard
815 guarded_ptr extract_min()
817 return extract_min_();
820 /// Extracts an item with maximal key from the list
822 The function searches an item with maximal key, unlinks it, and returns the pointer to item
823 as \p guarded_ptr object.
824 If the skip-list is empty the function returns an empty \p guarded_ptr.
826 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
827 It means that the function gets rightmost item and tries to unlink it.
828 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
829 So, the function returns the item with maximum key at the moment of list traversing.
831 The \p disposer specified in \p Traits class template parameter is called
832 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
833 will be destroyed or released.
834 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
838 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
842 skip_list::guarded_ptr gp( theList.extract_max( gp ));
847 // Destructor of gp releases internal HP guard
851 guarded_ptr extract_max()
853 return extract_max_();
856 /// Deletes the item from the set
857 /** \anchor cds_intrusive_SkipListSet_hp_erase
858 The function searches an item with key equal to \p key in the set,
859 unlinks it from the set, and returns \p true.
860 If the item with key equal to \p key is not found the function return \p false.
862 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
864 template <typename Q>
865 bool erase( Q const& key )
867 return erase_( key, key_comparator(), [](value_type const&) {} );
870 /// Deletes the item from the set with comparing functor \p pred
872 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
873 but \p pred predicate is used for key comparing.
875 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
877 \p pred must imply the same element order as the comparator used for building the set.
879 template <typename Q, typename Less>
880 bool erase_with( Q const& key, Less pred )
883 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
886 /// Deletes the item from the set
887 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
888 The function searches an item with key equal to \p key in the set,
889 call \p f functor with item found, unlinks it from the set, and returns \p true.
890 The \ref disposer specified in \p Traits class template parameter is called
891 by garbage collector \p GC asynchronously.
893 The \p Func interface is
896 void operator()( value_type const& item );
900 If the item with key equal to \p key is not found the function return \p false.
902 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
904 template <typename Q, typename Func>
905 bool erase( Q const& key, Func f )
907 return erase_( key, key_comparator(), f );
910 /// Deletes the item from the set with comparing functor \p pred
912 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
913 but \p pred predicate is used for key comparing.
915 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
917 \p pred must imply the same element order as the comparator used for building the set.
919 template <typename Q, typename Less, typename Func>
920 bool erase_with( Q const& key, Less pred, Func f )
923 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
927 /** \anchor cds_intrusive_SkipListSet_hp_find_func
928 The function searches the item with key equal to \p key and calls the functor \p f for item found.
929 The interface of \p Func functor is:
932 void operator()( value_type& item, Q& key );
935 where \p item is the item found, \p key is the <tt>find</tt> function argument.
937 The functor can change non-key fields of \p item. Note that the functor is only guarantee
938 that \p item cannot be disposed during functor is executing.
939 The functor does not serialize simultaneous access to the set \p item. If such access is
940 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
942 Note the compare functor specified for class \p Traits template parameter
943 should accept a parameter of type \p Q that can be not the same as \p value_type.
945 The function returns \p true if \p key is found, \p false otherwise.
947 template <typename Q, typename Func>
948 bool find( Q& key, Func f )
950 return find_with_( key, key_comparator(), f );
953 template <typename Q, typename Func>
954 bool find( Q const& key, Func f )
956 return find_with_( key, key_comparator(), f );
960 /// Finds the key \p key with \p pred predicate for comparing
962 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
963 but \p pred is used for key compare.
965 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
967 \p pred must imply the same element order as the comparator used for building the set.
969 template <typename Q, typename Less, typename Func>
970 bool find_with( Q& key, Less pred, Func f )
973 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
976 template <typename Q, typename Less, typename Func>
977 bool find_with( Q const& key, Less pred, Func f )
980 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
984 /// Checks whether the set contains \p key
986 The function searches the item with key equal to \p key
987 and returns \p true if it is found, and \p false otherwise.
989 template <typename Q>
990 bool contains( Q const& key )
992 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
995 template <typename Q>
996 CDS_DEPRECATED("deprecated, use contains()")
997 bool find( Q const& key )
999 return contains( key );
1003 /// Checks whether the set contains \p key using \p pred predicate for searching
1005 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1006 \p Less functor has the interface like \p std::less.
1007 \p Less must imply the same element order as the comparator used for building the set.
1009 template <typename Q, typename Less>
1010 bool contains( Q const& key, Less pred )
1013 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1016 template <typename Q, typename Less>
1017 CDS_DEPRECATED("deprecated, use contains()")
1018 bool find_with( Q const& key, Less pred )
1020 return contains( key, pred );
1024 /// Finds \p key and return the item found
1025 /** \anchor cds_intrusive_SkipListSet_hp_get
1026 The function searches the item with key equal to \p key
1027 and returns the pointer to the item found as \p guarded_ptr.
1028 If \p key is not found the function returns an empt guarded pointer.
1030 The \p disposer specified in \p Traits class template parameter is called
1031 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1032 will be destroyed or released.
1033 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1037 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1041 skip_list::guarded_ptr gp(theList.get( 5 ));
1046 // Destructor of guarded_ptr releases internal HP guard
1050 Note the compare functor specified for class \p Traits template parameter
1051 should accept a parameter of type \p Q that can be not the same as \p value_type.
1053 template <typename Q>
1054 guarded_ptr get( Q const& key )
1056 return get_with_( key, key_comparator());
1059 /// Finds \p key and return the item found
1061 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1062 but \p pred is used for comparing the keys.
1064 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1066 \p pred must imply the same element order as the comparator used for building the set.
1068 template <typename Q, typename Less>
1069 guarded_ptr get_with( Q const& key, Less pred )
1072 return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
1075 /// Returns item count in the set
1077 The value returned depends on item counter type provided by \p Traits template parameter.
1078 If it is \p atomicity::empty_item_counter this function always returns 0.
1079 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1084 return m_ItemCounter;
1087 /// Checks if the set is empty
1090 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1093 /// Clears the set (not atomic)
1095 The function unlink all items from the set.
1096 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1100 assert( set.empty());
1102 the assertion could be raised.
1104 For each item the \ref disposer will be called after unlinking.
1108 while ( extract_min_());
1111 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1112 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1114 return c_nMaxHeight;
1117 /// Returns const reference to internal statistics
1118 stat const& statistics() const
1125 unsigned int random_level()
1127 // Random generator produces a number from range [0..31]
1128 // We need a number from range [1..32]
1129 return m_RandomLevelGen() + 1;
1132 template <typename Q>
1133 node_type * build_node( Q v )
1135 return node_builder::make_tower( v, m_RandomLevelGen );
1138 static value_type * gc_protect( marked_node_ptr p )
1140 return node_traits::to_value_ptr( p.ptr() );
1143 static void dispose_node( value_type * pVal )
1145 assert( pVal != nullptr );
1146 typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ) );
1150 void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur, marked_node_ptr pSucc )
1152 marked_node_ptr p( pCur.ptr() );
1153 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
1154 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1156 if ( pCur->level_unlinked() ) {
1157 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
1158 m_Stat.onEraseWhileFind();
1163 template <typename Q, typename Compare >
1164 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
1167 marked_node_ptr pSucc;
1168 marked_node_ptr pCur;
1170 // Hazard pointer array:
1171 // pPred: [nLevel * 2]
1172 // pSucc: [nLevel * 2 + 1]
1175 pPred = m_Head.head();
1178 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1179 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
1181 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1182 if ( pCur.bits() ) {
1183 // pCur.bits() means that pPred is logically deleted
1187 if ( pCur.ptr() == nullptr ) {
1188 // end of list at level nLevel - goto next level
1192 // pSucc contains deletion mark for pCur
1193 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1195 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
1198 if ( pSucc.bits() ) {
1199 // pCur is marked, i.e. logically deleted
1200 // try to help deleting pCur
1201 help_remove( nLevel, pPred, pCur, pSucc );
1205 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1208 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
1210 else if ( nCmp == 0 && bStopIfFound )
1218 pos.pPrev[nLevel] = pPred;
1219 pos.pSucc[nLevel] = pCur.ptr();
1226 pos.pCur = pCur.ptr();
1227 return pCur.ptr() && nCmp == 0;
1230 bool find_min_position( position& pos )
1233 marked_node_ptr pSucc;
1234 marked_node_ptr pCur;
1236 // Hazard pointer array:
1237 // pPred: [nLevel * 2]
1238 // pSucc: [nLevel * 2 + 1]
1241 pPred = m_Head.head();
1243 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1244 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
1245 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1247 // pCur.bits() means that pPred is logically deleted
1248 // head cannot be deleted
1249 assert( pCur.bits() == 0 );
1253 // pSucc contains deletion mark for pCur
1254 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1256 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
1259 if ( pSucc.bits() ) {
1260 // pCur is marked, i.e. logically deleted.
1261 // try to help deleting pCur
1262 help_remove( nLevel, pPred, pCur, pSucc );
1268 pos.pPrev[nLevel] = pPred;
1269 pos.pSucc[nLevel] = pCur.ptr();
1272 return ( pos.pCur = pCur.ptr() ) != nullptr;
1275 bool find_max_position( position& pos )
1278 marked_node_ptr pSucc;
1279 marked_node_ptr pCur;
1281 // Hazard pointer array:
1282 // pPred: [nLevel * 2]
1283 // pSucc: [nLevel * 2 + 1]
1286 pPred = m_Head.head();
1288 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1289 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
1291 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1292 if ( pCur.bits() ) {
1293 // pCur.bits() means that pPred is logically deleted
1297 if ( pCur.ptr() == nullptr ) {
1298 // end of the list at level nLevel - goto next level
1302 // pSucc contains deletion mark for pCur
1303 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1305 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
1308 if ( pSucc.bits() ) {
1309 // pCur is marked, i.e. logically deleted.
1310 // try to help deleting pCur
1311 help_remove( nLevel, pPred, pCur, pSucc );
1319 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );
1324 pos.pPrev[nLevel] = pPred;
1325 pos.pSucc[nLevel] = pCur.ptr();
1328 return ( pos.pCur = pCur.ptr() ) != nullptr;
1331 template <typename Func>
1332 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
1334 unsigned int const nHeight = pNode->height();
1336 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
1337 pNode->next( nLevel ).store( marked_node_ptr(), memory_model::memory_order_relaxed );
1339 // Insert at level 0
1341 marked_node_ptr p( pos.pSucc[0] );
1342 pNode->next( 0 ).store( p, memory_model::memory_order_relaxed );
1343 if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1349 // Insert at level 1..max
1350 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
1353 marked_node_ptr pSucc( pos.pSucc[nLevel] );
1356 // pNode->next must be null but can have a "logical deleted" flag if another thread is removing pNode right now
1357 if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc,
1358 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1360 // pNode has been marked as removed while we are inserting it
1362 assert( p.bits() != 0 );
1364 if ( pNode->level_unlinked( nHeight - nLevel )) {
1365 gc::retire( node_traits::to_value_ptr( pNode ), dispose_node );
1366 m_Stat.onEraseWhileInsert();
1369 m_Stat.onLogicDeleteWhileInsert();
1374 // Link pNode into the list at nLevel
1375 if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( pSucc, marked_node_ptr( pNode ),
1376 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1382 // Renew insert position
1383 m_Stat.onRenewInsertPosition();
1384 if ( !find_position( val, pos, key_comparator(), false )) {
1385 // The node has been deleted while we are inserting it
1386 m_Stat.onNotFoundWhileInsert();
1394 template <typename Func>
1395 bool try_remove_at( node_type * pDel, position& pos, Func f )
1397 assert( pDel != nullptr );
1399 marked_node_ptr pSucc;
1402 // logical deletion (marking)
1403 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
1404 pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
1405 if ( pSucc.bits() == 0 ) {
1407 while ( !( pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
1408 memory_model::memory_order_release, atomics::memory_order_acquire )
1409 || pSucc.bits() != 0 ))
1412 m_Stat.onMarkFailed();
1417 marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr());
1419 if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_acquire ))
1421 f( *node_traits::to_value_ptr( pDel ) );
1423 // Physical deletion
1426 unsigned nCount = 0;
1428 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
1430 pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
1431 if ( !pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
1432 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1434 // Maybe, another threads already helped us to delete the node?..
1436 if ( pDel->level_unlinked( nCount )) {
1437 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
1438 m_Stat.onFastEraseHelped();
1444 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
1445 m_Stat.onSlowErase();
1451 // Fast erasing success
1452 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
1453 m_Stat.onFastErase();
1456 else if ( p.bits() ) {
1457 // Another thread is deleting pDel right now
1460 m_Stat.onEraseRetry();
1465 enum finsd_fastpath_result {
1466 find_fastpath_found,
1467 find_fastpath_not_found,
1470 template <typename Q, typename Compare, typename Func>
1471 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
1474 marked_node_ptr pCur;
1475 marked_node_ptr pNull;
1478 // 0 - pPred on level N
1479 // 1 - pCur on level N
1480 typename gc::template GuardArray<2> guards;
1482 unsigned attempt = 0;
1485 pPred = m_Head.head();
1486 for ( int nLevel = static_cast<int>( m_nHeight.load( memory_model::memory_order_relaxed ) - 1 ); nLevel >= 0; --nLevel ) {
1487 pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
1488 if ( pCur == pNull )
1491 while ( pCur != pNull ) {
1492 if ( pCur.bits() ) {
1493 // pPred is being removed
1494 if ( ++attempt < 4 ) {
1499 return find_fastpath_abort;
1503 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1505 guards.copy( 0, 1 );
1507 pCur = guards.protect( 1, pCur->next( nLevel ), gc_protect );
1509 else if ( nCmp == 0 ) {
1511 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
1512 return find_fastpath_found;
1515 // pCur > val - go down
1522 return find_fastpath_not_found;
1525 template <typename Q, typename Compare, typename Func>
1526 bool find_slowpath( Q& val, Compare cmp, Func f )
1529 if ( find_position( val, pos, cmp, true ) ) {
1530 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
1532 f( *node_traits::to_value_ptr( pos.pCur ), val );
1539 template <typename Q, typename Compare, typename Func>
1540 bool find_with_( Q& val, Compare cmp, Func f )
1542 switch ( find_fastpath( val, cmp, f ) ) {
1543 case find_fastpath_found:
1544 m_Stat.onFindFastSuccess();
1546 case find_fastpath_not_found:
1547 m_Stat.onFindFastFailed();
1553 if ( find_slowpath( val, cmp, f ) ) {
1554 m_Stat.onFindSlowSuccess();
1558 m_Stat.onFindSlowFailed();
1562 template <typename Q, typename Compare>
1563 guarded_ptr get_with_( Q const& val, Compare cmp )
1566 if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ) )
1568 return guarded_ptr();
1571 template <typename Q, typename Compare, typename Func>
1572 bool erase_( Q const& val, Compare cmp, Func f )
1576 if ( !find_position( val, pos, cmp, false ) ) {
1577 m_Stat.onEraseFailed();
1581 node_type * pDel = pos.pCur;
1582 typename gc::Guard gDel;
1583 gDel.assign( node_traits::to_value_ptr( pDel ) );
1584 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1586 unsigned int nHeight = pDel->height();
1587 if ( try_remove_at( pDel, pos, f ) ) {
1589 m_Stat.onRemoveNode( nHeight );
1590 m_Stat.onEraseSuccess();
1594 m_Stat.onEraseFailed();
1598 template <typename Q, typename Compare>
1599 guarded_ptr extract_( Q const& val, Compare cmp )
1605 if ( !find_position( val, pos, cmp, false ) ) {
1606 m_Stat.onExtractFailed();
1607 return guarded_ptr();
1610 node_type * pDel = pos.pCur;
1611 gp.reset( node_traits::to_value_ptr( pDel ) );
1612 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1614 unsigned int nHeight = pDel->height();
1615 if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
1617 m_Stat.onRemoveNode( nHeight );
1618 m_Stat.onExtractSuccess();
1621 m_Stat.onExtractRetry();
1625 guarded_ptr extract_min_()
1631 if ( !find_min_position( pos ) ) {
1632 // The list is empty
1633 m_Stat.onExtractMinFailed();
1634 return guarded_ptr();
1637 node_type * pDel = pos.pCur;
1639 unsigned int nHeight = pDel->height();
1640 gp.reset( node_traits::to_value_ptr( pDel ) );
1642 if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
1644 m_Stat.onRemoveNode( nHeight );
1645 m_Stat.onExtractMinSuccess();
1649 m_Stat.onExtractMinRetry();
1653 guarded_ptr extract_max_()
1659 if ( !find_max_position( pos ) ) {
1660 // The list is empty
1661 m_Stat.onExtractMaxFailed();
1662 return guarded_ptr();
1665 node_type * pDel = pos.pCur;
1667 unsigned int nHeight = pDel->height();
1668 gp.reset( node_traits::to_value_ptr( pDel ) );
1670 if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
1672 m_Stat.onRemoveNode( nHeight );
1673 m_Stat.onExtractMaxSuccess();
1677 m_Stat.onExtractMaxRetry();
1681 void increase_height( unsigned int nHeight )
1683 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1684 if ( nCur < nHeight )
1685 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
1691 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
1693 item_counter m_ItemCounter; ///< item counter
1694 random_level_generator m_RandomLevelGen; ///< random level generator instance
1695 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
1696 mutable stat m_Stat; ///< internal statistics
1700 }} // namespace cds::intrusive
1703 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H