3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
4 #define __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
8 #include <cds/intrusive/skip_list_base.h>
9 #include <cds/opt/compare.h>
11 #include <cds/details/binary_functor_wrapper.h>
12 #include <cds/gc/guarded_ptr.h>
14 namespace cds { namespace intrusive {
17 namespace skip_list { namespace details {
19 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
23 typedef NodeTraits node_traits;
24 typedef BackOff back_off;
25 typedef typename node_traits::node_type node_type;
26 typedef typename node_traits::value_type value_type;
27 static bool const c_isConst = IsConst;
29 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
32 typedef typename node_type::marked_ptr marked_ptr;
33 typedef typename node_type::atomic_marked_ptr atomic_marked_ptr;
35 typename gc::Guard m_guard;
39 static value_type * gc_protect( marked_ptr p )
41 return node_traits::to_value_ptr( p.ptr() );
51 if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
52 // Current node is marked as deleted. So, its next pointer can point to anything
53 // In this case we interrupt our iteration and returns end() iterator.
58 marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
59 node_type * pp = p.ptr();
61 // p is marked as deleted. Spin waiting for physical removal
65 else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits() ) {
66 // p is marked as deleted. Spin waiting for physical removal
76 public: // for internal use only!!!
77 iterator( node_type& refHead )
83 marked_ptr p = m_guard.protect( refHead[0], gc_protect );
90 node_type * pp = p.ptr();
91 // Logically deleted node is marked from highest level
92 if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
106 iterator( iterator const& s)
107 : m_pNode( s.m_pNode )
109 m_guard.assign( node_traits::to_value_ptr(m_pNode) );
112 value_type * operator ->() const
114 assert( m_pNode != nullptr );
115 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
117 return node_traits::to_value_ptr( m_pNode );
120 value_ref operator *() const
122 assert( m_pNode != nullptr );
123 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
125 return *node_traits::to_value_ptr( m_pNode );
129 iterator& operator ++()
135 iterator& operator = (const iterator& src)
137 m_pNode = src.m_pNode;
138 m_guard.copy( src.m_guard );
142 template <typename Bkoff, bool C>
143 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
145 return m_pNode == i.m_pNode;
147 template <typename Bkoff, bool C>
148 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
150 return !( *this == i );
153 }} // namespace skip_list::details
156 /// Lock-free skip-list set
157 /** @ingroup cds_intrusive_map
158 @anchor cds_intrusive_SkipListSet_hp
160 The implementation of well-known probabilistic data structure called skip-list
161 invented by W.Pugh in his papers:
162 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
163 - [1990] W.Pugh A Skip List Cookbook
165 A skip-list is a probabilistic data structure that provides expected logarithmic
166 time search without the need of rebalance. The skip-list is a collection of sorted
167 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
168 Each list has a level, ranging from 0 to 32. The bottom-level list contains
169 all the nodes, and each higher-level list is a sublist of the lower-level lists.
170 Each node is created with a random top level (with a random height), and belongs
171 to all lists up to that level. The probability that a node has the height 1 is 1/2.
172 The probability that a node has the height N is 1/2 ** N (more precisely,
173 the distribution depends on an random generator provided, but our generators
176 The lock-free variant of skip-list is implemented according to book
177 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
178 chapter 14.4 "A Lock-Free Concurrent Skiplist".
179 \note The algorithm described in this book cannot be directly adapted for C++ (roughly speaking,
180 the algo contains a lot of bugs). The \b libcds implementation applies the approach discovered
181 by M.Michael in his \ref cds_intrusive_MichaelList_hp "lock-free linked list".
183 <b>Template arguments</b>:
184 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see skip_list::node).
185 - \p T - type to be stored in the list. The type must be based on skip_list::node (for skip_list::base_hook)
186 or it must have a member of type skip_list::node (for skip_list::member_hook).
187 - \p Traits - type traits. See skip_list::type_traits for explanation.
189 It is possible to declare option-based list with cds::intrusive::skip_list::make_traits metafunction istead of \p Traits template
191 Template argument list \p Options of cds::intrusive::skip_list::make_traits metafunction are:
192 - opt::hook - hook used. Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
193 If the option is not specified, <tt>skip_list::base_hook<></tt> and gc::HP is used.
194 - opt::compare - key comparison functor. No default functor is provided.
195 If the option is not specified, the opt::less is used.
196 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
197 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
198 of GC schema the disposer may be called asynchronously.
199 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
200 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
201 or opt::v::sequential_consistent (sequentially consisnent memory model).
202 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
203 user-provided one. See skip_list::random_level_generator option description for explanation.
204 Default is \p %skip_list::turbo_pascal.
205 - opt::allocator - although the skip-list is an intrusive container,
206 an allocator should be provided to maintain variable randomly-calculated height of the node
207 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
208 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
209 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
210 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
212 \warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
213 the guard count is limited (like as gc::HP, gc::HRC). Those GCs should be explicitly initialized with
214 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
215 when you try to create skip-list object.
217 \note There are several specializations of \p %SkipListSet for each \p GC. You should include:
218 - <tt><cds/intrusive/skip_list_hp.h></tt> for gc::HP garbage collector
219 - <tt><cds/intrusive/skip_list_hrc.h></tt> for gc::HRC garbage collector
220 - <tt><cds/intrusive/skip_list_ptb.h></tt> for gc::PTB garbage collector
221 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for persistent set
222 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
226 The class supports a forward iterator (\ref iterator and \ref const_iterator).
227 The iteration is ordered.
228 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
229 so, the element cannot be reclaimed while the iterator object is alive.
230 However, passing an iterator object between threads is dangerous.
232 \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
233 all elements in the set: any concurrent deletion can exclude the element
234 pointed by the iterator from the set, and your iteration can be terminated
235 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
237 Remember, each iterator object requires 2 additional hazard pointers, that may be
238 a limited resource for \p GC like as gc::HP and gc::HRC (for gc::PTB the count of
239 guards is unlimited).
241 The iterator class supports the following minimalistic interface:
248 iterator( iterator const& s);
250 value_type * operator ->() const;
251 value_type& operator *() const;
254 iterator& operator ++();
257 iterator& operator = (const iterator& src);
259 bool operator ==(iterator const& i ) const;
260 bool operator !=(iterator const& i ) const;
263 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
267 You should incorporate skip_list::node into your struct \p T and provide
268 appropriate skip_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
269 define a struct based on skip_list::type_traits.
271 Example for gc::HP and base hook:
273 // Include GC-related skip-list specialization
274 #include <cds/intrusive/skip_list_hp.h>
276 // Data stored in skip list
277 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
286 // my_data compare functor
288 int operator()( const my_data& d1, const my_data& d2 )
290 return d1.strKey.compare( d2.strKey );
293 int operator()( const my_data& d, const std::string& s )
295 return d.strKey.compare(s);
298 int operator()( const std::string& s, const my_data& d )
300 return s.compare( d.strKey );
305 // Declare type_traits
306 struct my_traits: public cds::intrusive::skip_list::type_traits
308 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
309 typedef my_data_cmp compare;
312 // Declare skip-list set type
313 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
316 Equivalent option-based code:
318 // GC-related specialization
319 #include <cds/intrusive/skip_list_hp.h>
328 // Declare option-based skip-list set
329 typedef cds::intrusive::SkipListSet< cds::gc::HP
331 , typename cds::intrusive::skip_list::make_traits<
332 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
333 ,cds::intrusive::opt::compare< my_data_cmp >
342 #ifdef CDS_DOXYGEN_INVOKED
343 ,typename Traits = skip_list::type_traits
351 typedef T value_type ; ///< type of value stored in the skip-list
352 typedef Traits options ; ///< Traits template parameter
354 typedef typename options::hook hook ; ///< hook type
355 typedef typename hook::node_type node_type ; ///< node type
357 # ifdef CDS_DOXYGEN_INVOKED
358 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
360 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
363 typedef typename options::disposer disposer ; ///< disposer used
364 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
366 typedef GC gc ; ///< Garbage collector
367 typedef typename options::item_counter item_counter ; ///< Item counting policy used
368 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
369 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
370 typedef typename options::allocator allocator_type ; ///< allocator for maintaining array of next pointers of the node
371 typedef typename options::back_off back_off ; ///< Back-off strategy
372 typedef typename options::stat stat ; ///< internal statistics type
375 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
377 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
379 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
380 but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
382 static unsigned int const c_nMaxHeight = std::conditional<
383 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
384 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
385 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
389 static unsigned int const c_nMinHeight = 5;
393 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic marked node pointer
394 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
398 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
400 typedef typename std::conditional<
401 std::is_same< typename options::internal_node_builder, cds::opt::none >::value
402 ,intrusive_node_builder
403 ,typename options::internal_node_builder
404 >::type node_builder;
406 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
408 // c_nMaxHeight * 2 - pPred/pSucc guards
409 // + 1 - for erase, unlink
411 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
413 node_type * pPrev[ c_nMaxHeight ];
414 node_type * pSucc[ c_nMaxHeight ];
416 typename gc::template GuardArray< c_nMaxHeight * 2 > guards ; ///< Guards array for pPrev/pSucc
418 node_type * pCur ; // guarded by guards; needed only for *ensure* function
423 skip_list::details::head_node< node_type > m_Head ; ///< head tower (max height)
425 item_counter m_ItemCounter ; ///< item counter
426 random_level_generator m_RandomLevelGen ; ///< random level generator instance
427 atomics::atomic<unsigned int> m_nHeight ; ///< estimated high level
428 mutable stat m_Stat ; ///< internal statistics
432 unsigned int random_level()
434 // Random generator produces a number from range [0..31]
435 // We need a number from range [1..32]
436 return m_RandomLevelGen() + 1;
439 template <typename Q>
440 node_type * build_node( Q v )
442 return node_builder::make_tower( v, m_RandomLevelGen );
445 static value_type * gc_protect( marked_node_ptr p )
447 return node_traits::to_value_ptr( p.ptr() );
450 static void dispose_node( value_type * pVal )
452 assert( pVal != nullptr );
453 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
457 template <typename Q, typename Compare >
458 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
461 marked_node_ptr pSucc;
462 marked_node_ptr pCur;
464 // Hazard pointer array:
465 // pPred: [nLevel * 2]
466 // pSucc: [nLevel * 2 + 1]
469 pPred = m_Head.head();
472 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
473 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
475 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
477 // pCur.bits() means that pPred is logically deleted
481 if ( pCur.ptr() == nullptr ) {
482 // end of the list at level nLevel - goto next level
486 // pSucc contains deletion mark for pCur
487 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
489 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
492 if ( pSucc.bits() ) {
493 // pCur is marked, i.e. logically deleted.
494 marked_node_ptr p( pCur.ptr() );
495 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
496 memory_model::memory_order_release, atomics::memory_order_relaxed ))
499 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
500 m_Stat.onEraseWhileFind();
506 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
509 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
511 else if ( nCmp == 0 && bStopIfFound )
519 pos.pPrev[ nLevel ] = pPred;
520 pos.pSucc[ nLevel ] = pCur.ptr();
527 pos.pCur = pCur.ptr();
528 return pCur.ptr() && nCmp == 0;
531 bool find_min_position( position& pos )
534 marked_node_ptr pSucc;
535 marked_node_ptr pCur;
537 // Hazard pointer array:
538 // pPred: [nLevel * 2]
539 // pSucc: [nLevel * 2 + 1]
542 pPred = m_Head.head();
544 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
545 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
546 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
548 // pCur.bits() means that pPred is logically deleted
549 // head cannot be deleted
550 assert( pCur.bits() == 0 );
554 // pSucc contains deletion mark for pCur
555 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
557 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
560 if ( pSucc.bits() ) {
561 // pCur is marked, i.e. logically deleted.
562 marked_node_ptr p( pCur.ptr() );
563 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
564 memory_model::memory_order_release, atomics::memory_order_relaxed ))
567 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
574 pos.pPrev[ nLevel ] = pPred;
575 pos.pSucc[ nLevel ] = pCur.ptr();
578 return (pos.pCur = pCur.ptr()) != nullptr;
581 bool find_max_position( position& pos )
584 marked_node_ptr pSucc;
585 marked_node_ptr pCur;
587 // Hazard pointer array:
588 // pPred: [nLevel * 2]
589 // pSucc: [nLevel * 2 + 1]
592 pPred = m_Head.head();
594 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
595 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
597 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
599 // pCur.bits() means that pPred is logically deleted
603 if ( pCur.ptr() == nullptr ) {
604 // end of the list at level nLevel - goto next level
608 // pSucc contains deletion mark for pCur
609 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
611 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
614 if ( pSucc.bits() ) {
615 // pCur is marked, i.e. logically deleted.
616 marked_node_ptr p( pCur.ptr() );
617 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
618 memory_model::memory_order_release, atomics::memory_order_relaxed ))
621 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
630 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
631 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
636 pos.pPrev[ nLevel ] = pPred;
637 pos.pSucc[ nLevel ] = pCur.ptr();
640 return (pos.pCur = pCur.ptr()) != nullptr;
643 template <typename Func>
644 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
646 unsigned int nHeight = pNode->height();
648 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
649 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
652 marked_node_ptr p( pos.pSucc[0] );
653 pNode->next( 0 ).store( p, memory_model::memory_order_release );
654 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
657 cds::unref( f )( val );
660 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
663 marked_node_ptr q( pos.pSucc[ nLevel ]);
664 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
665 // pNode has been marked as removed while we are inserting it
668 m_Stat.onLogicDeleteWhileInsert();
672 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
675 // Renew insert position
676 m_Stat.onRenewInsertPosition();
677 if ( !find_position( val, pos, key_comparator(), false )) {
678 // The node has been deleted while we are inserting it
679 m_Stat.onNotFoundWhileInsert();
687 template <typename Func>
688 bool try_remove_at( node_type * pDel, position& pos, Func f )
690 assert( pDel != nullptr );
692 marked_node_ptr pSucc;
693 typename gc::Guard gSucc;
695 // logical deletion (marking)
696 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
698 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
699 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
700 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
708 pSucc = gSucc.protect( pDel->next(0), gc_protect );
709 marked_node_ptr p( pSucc.ptr() );
710 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
711 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
713 cds::unref(f)( *node_traits::to_value_ptr( pDel ));
718 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
719 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
720 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
721 memory_model::memory_order_release, atomics::memory_order_relaxed) )
724 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
725 m_Stat.onSlowErase();
730 // Fast erasing success
731 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
732 m_Stat.onFastErase();
743 enum finsd_fastpath_result {
745 find_fastpath_not_found,
748 template <typename Q, typename Compare, typename Func>
749 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
752 typename gc::template GuardArray<2> guards;
753 marked_node_ptr pCur;
754 marked_node_ptr pNull;
758 pPred = m_Head.head();
759 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
760 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
764 while ( pCur != pNull ) {
766 unsigned int nAttempt = 0;
767 while ( pCur.bits() && nAttempt++ < 16 ) {
769 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
774 // Maybe, we are on deleted node sequence
775 // Abort searching, try slow-path
776 return find_fastpath_abort;
781 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
785 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
787 else if ( nCmp == 0 ) {
789 cds::unref(f)( *node_traits::to_value_ptr( pCur.ptr() ), val );
790 return find_fastpath_found;
792 else // pCur > val - go down
798 return find_fastpath_not_found;
801 template <typename Q, typename Compare, typename Func>
802 bool find_slowpath( Q& val, Compare cmp, Func f )
805 if ( find_position( val, pos, cmp, true )) {
806 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
808 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
815 template <typename Q, typename Compare, typename Func>
816 bool find_with_( Q& val, Compare cmp, Func f )
818 switch ( find_fastpath( val, cmp, f )) {
819 case find_fastpath_found:
820 m_Stat.onFindFastSuccess();
822 case find_fastpath_not_found:
823 m_Stat.onFindFastFailed();
829 if ( find_slowpath( val, cmp, f )) {
830 m_Stat.onFindSlowSuccess();
834 m_Stat.onFindSlowFailed();
838 template <typename Q, typename Compare>
839 bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp )
841 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } );
844 template <typename Q, typename Compare, typename Func>
845 bool erase_( Q const& val, Compare cmp, Func f )
849 if ( !find_position( val, pos, cmp, false ) ) {
850 m_Stat.onEraseFailed();
854 node_type * pDel = pos.pCur;
855 typename gc::Guard gDel;
856 gDel.assign( node_traits::to_value_ptr(pDel) );
857 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
859 unsigned int nHeight = pDel->height();
860 if ( try_remove_at( pDel, pos, f )) {
862 m_Stat.onRemoveNode( nHeight );
863 m_Stat.onEraseSuccess();
867 m_Stat.onEraseFailed();
871 template <typename Q, typename Compare>
872 bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
877 if ( !find_position( val, pos, cmp, false ) ) {
878 m_Stat.onExtractFailed();
882 node_type * pDel = pos.pCur;
883 guard.assign( node_traits::to_value_ptr(pDel));
884 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
886 unsigned int nHeight = pDel->height();
887 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
889 m_Stat.onRemoveNode( nHeight );
890 m_Stat.onExtractSuccess();
894 m_Stat.onExtractRetry();
898 bool extract_min_( typename gc::Guard& gDel )
903 if ( !find_min_position( pos ) ) {
905 m_Stat.onExtractMinFailed();
909 node_type * pDel = pos.pCur;
911 unsigned int nHeight = pDel->height();
912 gDel.assign( node_traits::to_value_ptr(pDel) );
914 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
916 m_Stat.onRemoveNode( nHeight );
917 m_Stat.onExtractMinSuccess();
921 m_Stat.onExtractMinRetry();
925 bool extract_max_( typename gc::Guard& gDel )
930 if ( !find_max_position( pos ) ) {
932 m_Stat.onExtractMaxFailed();
936 node_type * pDel = pos.pCur;
938 unsigned int nHeight = pDel->height();
939 gDel.assign( node_traits::to_value_ptr(pDel) );
941 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
943 m_Stat.onRemoveNode( nHeight );
944 m_Stat.onExtractMaxSuccess();
948 m_Stat.onExtractMaxRetry();
952 void increase_height( unsigned int nHeight )
954 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
955 if ( nCur < nHeight )
956 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
961 /// Default constructor
963 The constructor checks whether the count of guards is enough
964 for skip-list and may raise an exception if not.
967 : m_Head( c_nMaxHeight )
968 , m_nHeight( c_nMinHeight )
970 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
972 gc::check_available_guards( c_nHazardPtrCount );
974 // Barrier for head node
975 atomics::atomic_thread_fence( memory_model::memory_order_release );
978 /// Clears and destructs the skip-list
986 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
988 /// Const iterator type
989 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
991 /// Returns a forward iterator addressing the first element in a set
994 return iterator( *m_Head.head() );
997 /// Returns a forward const iterator addressing the first element in a set
999 const_iterator begin() const
1001 return const_iterator( *m_Head.head() );
1003 const_iterator cbegin()
1005 return const_iterator( *m_Head.head() );
1009 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1015 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1017 const_iterator end() const
1019 return const_iterator();
1021 const_iterator cend()
1023 return const_iterator();
1028 /// Inserts new node
1030 The function inserts \p val in the set if it does not contain
1031 an item with key equal to \p val.
1033 Returns \p true if \p val is placed into the set, \p false otherwise.
1035 bool insert( value_type& val )
1037 return insert( val, []( value_type& ) {} );
1040 /// Inserts new node
1042 This function is intended for derived non-intrusive containers.
1044 The function allows to split creating of new item into two part:
1045 - create item with key only
1046 - insert new item into the set
1047 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1049 The functor signature is:
1051 void func( value_type& val );
1053 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1054 \p val no any other changes could be made on this set's item by concurrent threads.
1055 The user-defined functor is called only if the inserting is success and may be passed by reference
1056 using <tt>boost::ref</tt>
1058 template <typename Func>
1059 bool insert( value_type& val, Func f )
1061 typename gc::Guard gNew;
1062 gNew.assign( &val );
1064 node_type * pNode = node_traits::to_node_ptr( val );
1065 scoped_node_ptr scp( pNode );
1066 unsigned int nHeight = pNode->height();
1067 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1068 bool bTowerMade = false;
1073 bool bFound = find_position( val, pos, key_comparator(), true );
1075 // scoped_node_ptr deletes the node tower if we create it
1079 m_Stat.onInsertFailed();
1084 build_node( pNode );
1085 nHeight = pNode->height();
1090 if ( !insert_at_position( val, pNode, pos, f )) {
1091 m_Stat.onInsertRetry();
1095 increase_height( nHeight );
1097 m_Stat.onAddNode( nHeight );
1098 m_Stat.onInsertSuccess();
1104 /// Ensures that the \p val exists in the set
1106 The operation performs inserting or changing data with lock-free manner.
1108 If the item \p val is not found in the set, then \p val is inserted into the set.
1109 Otherwise, the functor \p func is called with item found.
1110 The functor signature is:
1112 void func( bool bNew, value_type& item, value_type& val );
1115 - \p bNew - \p true if the item has been inserted, \p false otherwise
1116 - \p item - item of the set
1117 - \p val - argument \p val passed into the \p ensure function
1118 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1119 refer to the same thing.
1121 The functor can change non-key fields of the \p item; however, \p func must guarantee
1122 that during changing no any other modifications could be made on this item by concurrent threads.
1124 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1126 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1127 \p second is \p true if new item has been added or \p false if the item with \p key
1128 already is in the set.
1130 template <typename Func>
1131 std::pair<bool, bool> ensure( value_type& val, Func func )
1133 typename gc::Guard gNew;
1134 gNew.assign( &val );
1136 node_type * pNode = node_traits::to_node_ptr( val );
1137 scoped_node_ptr scp( pNode );
1138 unsigned int nHeight = pNode->height();
1139 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1140 bool bTowerMade = false;
1145 bool bFound = find_position( val, pos, key_comparator(), true );
1147 // scoped_node_ptr deletes the node tower if we create it before
1151 cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
1152 m_Stat.onEnsureExist();
1153 return std::make_pair( true, false );
1157 build_node( pNode );
1158 nHeight = pNode->height();
1163 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); })) {
1164 m_Stat.onInsertRetry();
1168 increase_height( nHeight );
1171 m_Stat.onAddNode( nHeight );
1172 m_Stat.onEnsureNew();
1173 return std::make_pair( true, true );
1177 /// Unlinks the item \p val from the set
1179 The function searches the item \p val in the set and unlink it from the set
1180 if it is found and is equal to \p val.
1182 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
1183 and deletes the item found. \p unlink finds an item by key and deletes it
1184 only if \p val is an item of that set, i.e. the pointer to item found
1185 is equal to <tt> &val </tt>.
1187 The \ref disposer specified in \p Traits class template parameter is called
1188 by garbage collector \p GC asynchronously.
1190 The function returns \p true if success and \p false otherwise.
1192 bool unlink( value_type& val )
1196 if ( !find_position( val, pos, key_comparator(), false ) ) {
1197 m_Stat.onUnlinkFailed();
1201 node_type * pDel = pos.pCur;
1202 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1204 unsigned int nHeight = pDel->height();
1205 typename gc::Guard gDel;
1206 gDel.assign( node_traits::to_value_ptr(pDel) );
1208 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1210 m_Stat.onRemoveNode( nHeight );
1211 m_Stat.onUnlinkSuccess();
1215 m_Stat.onUnlinkFailed();
1219 /// Extracts the item from the set with specified \p key
1220 /** \anchor cds_intrusive_SkipListSet_hp_extract
1221 The function searches an item with key equal to \p key in the set,
1222 unlinks it from the set, and returns it in \p dest parameter.
1223 If the item with key equal to \p key is not found the function returns \p false.
1225 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1227 The \ref disposer specified in \p Traits class template parameter is called automatically
1228 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
1229 will be destroyed or released.
1230 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1234 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1238 skip_list::guarded_ptr gp;
1239 theList.extract( gp, 5 );
1243 // Destructor of gp releases internal HP guard
1247 template <typename Q>
1248 bool extract( guarded_ptr& dest, Q const& key )
1250 return extract_( dest.guard(), key, key_comparator() );
1253 /// Extracts the item from the set with comparing functor \p pred
1255 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1256 but \p pred predicate is used for key comparing.
1258 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1260 \p pred must imply the same element order as the comparator used for building the set.
1262 template <typename Q, typename Less>
1263 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
1265 return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1268 /// Extracts an item with minimal key from the list
1270 The function searches an item with minimal key, unlinks it, and returns the item found in \p dest parameter.
1271 If the skip-list is empty the function returns \p false.
1273 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1274 It means that the function gets leftmost item and tries to unlink it.
1275 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1276 So, the function returns the item with minimum key at the moment of list traversing.
1278 The \ref disposer specified in \p Traits class template parameter is called
1279 by garbage collector \p GC automatically when returned \ref guarded_ptr object
1280 will be destroyed or released.
1281 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1285 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1289 skip_list::guarded_ptr gp;
1290 if ( theList.extract_min( gp )) {
1294 // Destructor of gp releases internal HP guard
1298 bool extract_min( guarded_ptr& dest)
1300 return extract_min_( dest.guard() );
1303 /// Extracts an item with maximal key from the list
1305 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p dest parameter.
1306 If the skip-list is empty the function returns empty \p guarded_ptr.
1308 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1309 It means that the function gets rightmost item and tries to unlink it.
1310 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1311 So, the function returns the item with maximum key at the moment of list traversing.
1313 The \ref disposer specified in \p Traits class template parameter is called
1314 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1315 will be destroyed or released.
1316 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1320 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1324 skip_list::guarded_ptr gp;
1325 if ( theList.extract_max( gp )) {
1329 // Destructor of gp releases internal HP guard
1333 bool extract_max( guarded_ptr& dest )
1335 return extract_max_( dest.guard() );
1338 /// Deletes the item from the set
1339 /** \anchor cds_intrusive_SkipListSet_hp_erase
1340 The function searches an item with key equal to \p val in the set,
1341 unlinks it from the set, and returns \p true.
1342 If the item with key equal to \p val is not found the function return \p false.
1344 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1346 template <typename Q>
1347 bool erase( Q const& val )
1349 return erase_( val, key_comparator(), [](value_type const&) {} );
1352 /// Deletes the item from the set with comparing functor \p pred
1354 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1355 but \p pred predicate is used for key comparing.
1357 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1359 \p pred must imply the same element order as the comparator used for building the set.
1361 template <typename Q, typename Less>
1362 bool erase_with( Q const& val, Less pred )
1364 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1367 /// Deletes the item from the set
1368 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1369 The function searches an item with key equal to \p val in the set,
1370 call \p f functor with item found, unlinks it from the set, and returns \p true.
1371 The \ref disposer specified in \p Traits class template parameter is called
1372 by garbage collector \p GC asynchronously.
1374 The \p Func interface is
1377 void operator()( value_type const& item );
1380 The functor can be passed by reference with <tt>boost:ref</tt>
1382 If the item with key equal to \p val is not found the function return \p false.
1384 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1386 template <typename Q, typename Func>
1387 bool erase( Q const& val, Func f )
1389 return erase_( val, key_comparator(), f );
1392 /// Deletes the item from the set with comparing functor \p pred
1394 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1395 but \p pred predicate is used for key comparing.
1397 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1399 \p pred must imply the same element order as the comparator used for building the set.
1401 template <typename Q, typename Less, typename Func>
1402 bool erase_with( Q const& val, Less pred, Func f )
1404 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1407 /// Finds the key \p val
1408 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1409 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1410 The interface of \p Func functor is:
1413 void operator()( value_type& item, Q& val );
1416 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1418 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1420 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1421 that \p item cannot be disposed during functor is executing.
1422 The functor does not serialize simultaneous access to the set \p item. If such access is
1423 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1425 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1426 can modify both arguments.
1428 Note the compare functor specified for class \p Traits template parameter
1429 should accept a parameter of type \p Q that can be not the same as \p value_type.
1431 The function returns \p true if \p val is found, \p false otherwise.
1433 template <typename Q, typename Func>
1434 bool find( Q& val, Func f )
1436 return find_with_( val, key_comparator(), f );
1439 /// Finds the key \p val with \p pred predicate for comparing
1441 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1442 but \p pred is used for key compare.
1444 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1446 \p pred must imply the same element order as the comparator used for building the set.
1448 template <typename Q, typename Less, typename Func>
1449 bool find_with( Q& val, Less pred, Func f )
1451 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1454 /// Finds the key \p val
1455 /** \anchor cds_intrusive_SkipListSet_hp_find_cfunc
1456 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1457 The interface of \p Func functor is:
1460 void operator()( value_type& item, Q const& val );
1463 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1465 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1467 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1468 that \p item cannot be disposed during functor is executing.
1469 The functor does not serialize simultaneous access to the set \p item. If such access is
1470 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1472 Note the compare functor specified for class \p Traits template parameter
1473 should accept a parameter of type \p Q that can be not the same as \p value_type.
1475 The function returns \p true if \p val is found, \p false otherwise.
1477 template <typename Q, typename Func>
1478 bool find( Q const& val, Func f )
1480 return find_with_( val, key_comparator(), f );
1483 /// Finds the key \p val with \p pred predicate for comparing
1485 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_cfunc "find(Q const&, Func)"
1486 but \p pred is used for key compare.
1487 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1489 \p pred must imply the same element order as the comparator used for building the set.
1491 template <typename Q, typename Less, typename Func>
1492 bool find_with( Q const& val, Less pred, Func f )
1494 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1497 /// Finds the key \p val
1498 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1499 The function searches the item with key equal to \p val
1500 and returns \p true if it is found, and \p false otherwise.
1502 Note the compare functor specified for class \p Traits template parameter
1503 should accept a parameter of type \p Q that can be not the same as \p value_type.
1505 template <typename Q>
1506 bool find( Q const & val )
1508 return find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
1511 /// Finds the key \p val with comparing functor \p pred
1513 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1514 but \p pred is used for comparing the keys.
1515 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1517 \p pred must imply the same element order as the comparator used for building the set.
1519 template <typename Q, typename Less>
1520 bool find_with( Q const& val, Less pred )
1522 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1525 /// Finds the key \p val and return the item found
1526 /** \anchor cds_intrusive_SkipListSet_hp_get
1527 The function searches the item with key equal to \p val
1528 and assigns the item found to guarded pointer \p ptr.
1529 The function returns \p true if \p val is found, and \p false otherwise.
1530 If \p val is not found the \p ptr parameter is not changed.
1532 The \ref disposer specified in \p Traits class template parameter is called
1533 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1534 will be destroyed or released.
1535 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1539 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1543 skip_list::guarded_ptr gp;
1544 if ( theList.get( gp, 5 )) {
1548 // Destructor of guarded_ptr releases internal HP guard
1552 Note the compare functor specified for class \p Traits template parameter
1553 should accept a parameter of type \p Q that can be not the same as \p value_type.
1555 template <typename Q>
1556 bool get( guarded_ptr& ptr, Q const& val )
1558 return get_with_( ptr.guard(), val, key_comparator() );
1561 /// Finds the key \p val and return the item found
1563 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1564 but \p pred is used for comparing the keys.
1566 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1568 \p pred must imply the same element order as the comparator used for building the set.
1570 template <typename Q, typename Less>
1571 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
1573 return get_with_( ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
1576 /// Returns item count in the set
1578 The value returned depends on item counter type provided by \p Traits template parameter.
1579 If it is atomicity::empty_item_counter this function always returns 0.
1580 Therefore, the function is not suitable for checking the set emptiness, use \ref empty
1581 member function for this purpose.
1585 return m_ItemCounter;
1588 /// Checks if the set is empty
1591 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1594 /// Clears the set (non-atomic)
1596 The function unlink all items from the set.
1597 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1601 assert( set.empty() );
1603 the assertion could be raised.
1605 For each item the \ref disposer will be called after unlinking.
1610 while ( extract_min( gp ));
1613 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1614 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1616 return c_nMaxHeight;
1619 /// Returns const reference to internal statistics
1620 stat const& statistics() const
1627 }} // namespace cds::intrusive
1630 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H