3 #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H
4 #define __CDS_INTRUSIVE_IMPL_SKIP_LIST_H
8 #include <functional> // ref
9 #include <cds/intrusive/details/skip_list_base.h>
10 #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 \p gc::HP). 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 \p gc::HP garbage collector
219 - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
220 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for persistent set
221 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
225 The class supports a forward iterator (\ref iterator and \ref const_iterator).
226 The iteration is ordered.
227 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
228 so, the element cannot be reclaimed while the iterator object is alive.
229 However, passing an iterator object between threads is dangerous.
231 \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
232 all elements in the set: any concurrent deletion can exclude the element
233 pointed by the iterator from the set, and your iteration can be terminated
234 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
236 Remember, each iterator object requires 2 additional hazard pointers, that may be
237 a limited resource for \p GC like as \p gc::HP (for \p gc::PTB the count of
238 guards is unlimited).
240 The iterator class supports the following minimalistic interface:
247 iterator( iterator const& s);
249 value_type * operator ->() const;
250 value_type& operator *() const;
253 iterator& operator ++();
256 iterator& operator = (const iterator& src);
258 bool operator ==(iterator const& i ) const;
259 bool operator !=(iterator const& i ) const;
262 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
266 You should incorporate skip_list::node into your struct \p T and provide
267 appropriate skip_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
268 define a struct based on skip_list::type_traits.
270 Example for gc::HP and base hook:
272 // Include GC-related skip-list specialization
273 #include <cds/intrusive/skip_list_hp.h>
275 // Data stored in skip list
276 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
285 // my_data compare functor
287 int operator()( const my_data& d1, const my_data& d2 )
289 return d1.strKey.compare( d2.strKey );
292 int operator()( const my_data& d, const std::string& s )
294 return d.strKey.compare(s);
297 int operator()( const std::string& s, const my_data& d )
299 return s.compare( d.strKey );
304 // Declare type_traits
305 struct my_traits: public cds::intrusive::skip_list::type_traits
307 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
308 typedef my_data_cmp compare;
311 // Declare skip-list set type
312 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
315 Equivalent option-based code:
317 // GC-related specialization
318 #include <cds/intrusive/skip_list_hp.h>
327 // Declare option-based skip-list set
328 typedef cds::intrusive::SkipListSet< cds::gc::HP
330 , typename cds::intrusive::skip_list::make_traits<
331 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
332 ,cds::intrusive::opt::compare< my_data_cmp >
341 #ifdef CDS_DOXYGEN_INVOKED
342 ,typename Traits = skip_list::type_traits
350 typedef T value_type ; ///< type of value stored in the skip-list
351 typedef Traits options ; ///< Traits template parameter
353 typedef typename options::hook hook ; ///< hook type
354 typedef typename hook::node_type node_type ; ///< node type
356 # ifdef CDS_DOXYGEN_INVOKED
357 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
359 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
362 typedef typename options::disposer disposer ; ///< disposer used
363 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
365 typedef GC gc ; ///< Garbage collector
366 typedef typename options::item_counter item_counter ; ///< Item counting policy used
367 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
368 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
369 typedef typename options::allocator allocator_type ; ///< allocator for maintaining array of next pointers of the node
370 typedef typename options::back_off back_off ; ///< Back-off strategy
371 typedef typename options::stat stat ; ///< internal statistics type
374 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
376 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
378 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
379 but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
381 static unsigned int const c_nMaxHeight = std::conditional<
382 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
383 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
384 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
388 static unsigned int const c_nMinHeight = 5;
392 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic marked node pointer
393 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
397 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
399 typedef typename std::conditional<
400 std::is_same< typename options::internal_node_builder, cds::opt::none >::value
401 ,intrusive_node_builder
402 ,typename options::internal_node_builder
403 >::type node_builder;
405 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
407 // c_nMaxHeight * 2 - pPred/pSucc guards
408 // + 1 - for erase, unlink
410 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
412 node_type * pPrev[ c_nMaxHeight ];
413 node_type * pSucc[ c_nMaxHeight ];
415 typename gc::template GuardArray< c_nMaxHeight * 2 > guards ; ///< Guards array for pPrev/pSucc
417 node_type * pCur ; // guarded by guards; needed only for *ensure* function
422 skip_list::details::head_node< node_type > m_Head ; ///< head tower (max height)
424 item_counter m_ItemCounter ; ///< item counter
425 random_level_generator m_RandomLevelGen ; ///< random level generator instance
426 atomics::atomic<unsigned int> m_nHeight ; ///< estimated high level
427 mutable stat m_Stat ; ///< internal statistics
431 unsigned int random_level()
433 // Random generator produces a number from range [0..31]
434 // We need a number from range [1..32]
435 return m_RandomLevelGen() + 1;
438 template <typename Q>
439 node_type * build_node( Q v )
441 return node_builder::make_tower( v, m_RandomLevelGen );
444 static value_type * gc_protect( marked_node_ptr p )
446 return node_traits::to_value_ptr( p.ptr() );
449 static void dispose_node( value_type * pVal )
451 assert( pVal != nullptr );
452 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
456 template <typename Q, typename Compare >
457 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
460 marked_node_ptr pSucc;
461 marked_node_ptr pCur;
463 // Hazard pointer array:
464 // pPred: [nLevel * 2]
465 // pSucc: [nLevel * 2 + 1]
468 pPred = m_Head.head();
471 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
472 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
474 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
476 // pCur.bits() means that pPred is logically deleted
480 if ( pCur.ptr() == nullptr ) {
481 // end of the list at level nLevel - goto next level
485 // pSucc contains deletion mark for pCur
486 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
488 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
491 if ( pSucc.bits() ) {
492 // pCur is marked, i.e. logically deleted.
493 marked_node_ptr p( pCur.ptr() );
494 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
495 memory_model::memory_order_release, atomics::memory_order_relaxed ))
498 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
499 m_Stat.onEraseWhileFind();
505 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
508 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
510 else if ( nCmp == 0 && bStopIfFound )
518 pos.pPrev[ nLevel ] = pPred;
519 pos.pSucc[ nLevel ] = pCur.ptr();
526 pos.pCur = pCur.ptr();
527 return pCur.ptr() && nCmp == 0;
530 bool find_min_position( position& pos )
533 marked_node_ptr pSucc;
534 marked_node_ptr pCur;
536 // Hazard pointer array:
537 // pPred: [nLevel * 2]
538 // pSucc: [nLevel * 2 + 1]
541 pPred = m_Head.head();
543 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
544 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
545 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
547 // pCur.bits() means that pPred is logically deleted
548 // head cannot be deleted
549 assert( pCur.bits() == 0 );
553 // pSucc contains deletion mark for pCur
554 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
556 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
559 if ( pSucc.bits() ) {
560 // pCur is marked, i.e. logically deleted.
561 marked_node_ptr p( pCur.ptr() );
562 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
563 memory_model::memory_order_release, atomics::memory_order_relaxed ))
566 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
573 pos.pPrev[ nLevel ] = pPred;
574 pos.pSucc[ nLevel ] = pCur.ptr();
577 return (pos.pCur = pCur.ptr()) != nullptr;
580 bool find_max_position( position& pos )
583 marked_node_ptr pSucc;
584 marked_node_ptr pCur;
586 // Hazard pointer array:
587 // pPred: [nLevel * 2]
588 // pSucc: [nLevel * 2 + 1]
591 pPred = m_Head.head();
593 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
594 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
596 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
598 // pCur.bits() means that pPred is logically deleted
602 if ( pCur.ptr() == nullptr ) {
603 // end of the list at level nLevel - goto next level
607 // pSucc contains deletion mark for pCur
608 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
610 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
613 if ( pSucc.bits() ) {
614 // pCur is marked, i.e. logically deleted.
615 marked_node_ptr p( pCur.ptr() );
616 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
617 memory_model::memory_order_release, atomics::memory_order_relaxed ))
620 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
629 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
630 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
635 pos.pPrev[ nLevel ] = pPred;
636 pos.pSucc[ nLevel ] = pCur.ptr();
639 return (pos.pCur = pCur.ptr()) != nullptr;
642 template <typename Func>
643 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
645 unsigned int nHeight = pNode->height();
647 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
648 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
651 marked_node_ptr p( pos.pSucc[0] );
652 pNode->next( 0 ).store( p, memory_model::memory_order_release );
653 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
659 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
662 marked_node_ptr q( pos.pSucc[ nLevel ]);
663 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
664 // pNode has been marked as removed while we are inserting it
667 m_Stat.onLogicDeleteWhileInsert();
671 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
674 // Renew insert position
675 m_Stat.onRenewInsertPosition();
676 if ( !find_position( val, pos, key_comparator(), false )) {
677 // The node has been deleted while we are inserting it
678 m_Stat.onNotFoundWhileInsert();
686 template <typename Func>
687 bool try_remove_at( node_type * pDel, position& pos, Func f )
689 assert( pDel != nullptr );
691 marked_node_ptr pSucc;
692 typename gc::Guard gSucc;
694 // logical deletion (marking)
695 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
697 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
698 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
699 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
707 pSucc = gSucc.protect( pDel->next(0), gc_protect );
708 marked_node_ptr p( pSucc.ptr() );
709 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
710 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
712 f( *node_traits::to_value_ptr( pDel ));
717 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
718 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
719 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
720 memory_model::memory_order_release, atomics::memory_order_relaxed) )
723 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
724 m_Stat.onSlowErase();
729 // Fast erasing success
730 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
731 m_Stat.onFastErase();
742 enum finsd_fastpath_result {
744 find_fastpath_not_found,
747 template <typename Q, typename Compare, typename Func>
748 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
751 typename gc::template GuardArray<2> guards;
752 marked_node_ptr pCur;
753 marked_node_ptr pNull;
757 pPred = m_Head.head();
758 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
759 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
763 while ( pCur != pNull ) {
765 unsigned int nAttempt = 0;
766 while ( pCur.bits() && nAttempt++ < 16 ) {
768 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
773 // Maybe, we are on deleted node sequence
774 // Abort searching, try slow-path
775 return find_fastpath_abort;
780 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
784 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
786 else if ( nCmp == 0 ) {
788 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
789 return find_fastpath_found;
791 else // pCur > val - go down
797 return find_fastpath_not_found;
800 template <typename Q, typename Compare, typename Func>
801 bool find_slowpath( Q& val, Compare cmp, Func f )
804 if ( find_position( val, pos, cmp, true )) {
805 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
807 f( *node_traits::to_value_ptr( pos.pCur ), val );
814 template <typename Q, typename Compare, typename Func>
815 bool find_with_( Q& val, Compare cmp, Func f )
817 switch ( find_fastpath( val, cmp, f )) {
818 case find_fastpath_found:
819 m_Stat.onFindFastSuccess();
821 case find_fastpath_not_found:
822 m_Stat.onFindFastFailed();
828 if ( find_slowpath( val, cmp, f )) {
829 m_Stat.onFindSlowSuccess();
833 m_Stat.onFindSlowFailed();
837 template <typename Q, typename Compare>
838 bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp )
840 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } );
843 template <typename Q, typename Compare, typename Func>
844 bool erase_( Q const& val, Compare cmp, Func f )
848 if ( !find_position( val, pos, cmp, false ) ) {
849 m_Stat.onEraseFailed();
853 node_type * pDel = pos.pCur;
854 typename gc::Guard gDel;
855 gDel.assign( node_traits::to_value_ptr(pDel) );
856 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
858 unsigned int nHeight = pDel->height();
859 if ( try_remove_at( pDel, pos, f )) {
861 m_Stat.onRemoveNode( nHeight );
862 m_Stat.onEraseSuccess();
866 m_Stat.onEraseFailed();
870 template <typename Q, typename Compare>
871 bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
876 if ( !find_position( val, pos, cmp, false ) ) {
877 m_Stat.onExtractFailed();
881 node_type * pDel = pos.pCur;
882 guard.assign( node_traits::to_value_ptr(pDel));
883 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
885 unsigned int nHeight = pDel->height();
886 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
888 m_Stat.onRemoveNode( nHeight );
889 m_Stat.onExtractSuccess();
893 m_Stat.onExtractRetry();
897 bool extract_min_( typename gc::Guard& gDel )
902 if ( !find_min_position( pos ) ) {
904 m_Stat.onExtractMinFailed();
908 node_type * pDel = pos.pCur;
910 unsigned int nHeight = pDel->height();
911 gDel.assign( node_traits::to_value_ptr(pDel) );
913 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
915 m_Stat.onRemoveNode( nHeight );
916 m_Stat.onExtractMinSuccess();
920 m_Stat.onExtractMinRetry();
924 bool extract_max_( typename gc::Guard& gDel )
929 if ( !find_max_position( pos ) ) {
931 m_Stat.onExtractMaxFailed();
935 node_type * pDel = pos.pCur;
937 unsigned int nHeight = pDel->height();
938 gDel.assign( node_traits::to_value_ptr(pDel) );
940 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
942 m_Stat.onRemoveNode( nHeight );
943 m_Stat.onExtractMaxSuccess();
947 m_Stat.onExtractMaxRetry();
951 void increase_height( unsigned int nHeight )
953 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
954 if ( nCur < nHeight )
955 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
960 /// Default constructor
962 The constructor checks whether the count of guards is enough
963 for skip-list and may raise an exception if not.
966 : m_Head( c_nMaxHeight )
967 , m_nHeight( c_nMinHeight )
969 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
971 gc::check_available_guards( c_nHazardPtrCount );
973 // Barrier for head node
974 atomics::atomic_thread_fence( memory_model::memory_order_release );
977 /// Clears and destructs the skip-list
985 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
987 /// Const iterator type
988 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
990 /// Returns a forward iterator addressing the first element in a set
993 return iterator( *m_Head.head() );
996 /// Returns a forward const iterator addressing the first element in a set
998 const_iterator begin() const
1000 return const_iterator( *m_Head.head() );
1002 const_iterator cbegin() const
1004 return const_iterator( *m_Head.head() );
1008 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1014 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1016 const_iterator end() const
1018 return const_iterator();
1020 const_iterator cend() const
1022 return const_iterator();
1027 /// Inserts new node
1029 The function inserts \p val in the set if it does not contain
1030 an item with key equal to \p val.
1032 Returns \p true if \p val is placed into the set, \p false otherwise.
1034 bool insert( value_type& val )
1036 return insert( val, []( value_type& ) {} );
1039 /// Inserts new node
1041 This function is intended for derived non-intrusive containers.
1043 The function allows to split creating of new item into two part:
1044 - create item with key only
1045 - insert new item into the set
1046 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1048 The functor signature is:
1050 void func( value_type& val );
1052 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1053 \p val no any other changes could be made on this set's item by concurrent threads.
1054 The user-defined functor is called only if the inserting is success and may be passed by reference
1057 template <typename Func>
1058 bool insert( value_type& val, Func f )
1060 typename gc::Guard gNew;
1061 gNew.assign( &val );
1063 node_type * pNode = node_traits::to_node_ptr( val );
1064 scoped_node_ptr scp( pNode );
1065 unsigned int nHeight = pNode->height();
1066 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1067 bool bTowerMade = false;
1072 bool bFound = find_position( val, pos, key_comparator(), true );
1074 // scoped_node_ptr deletes the node tower if we create it
1078 m_Stat.onInsertFailed();
1083 build_node( pNode );
1084 nHeight = pNode->height();
1089 if ( !insert_at_position( val, pNode, pos, f )) {
1090 m_Stat.onInsertRetry();
1094 increase_height( nHeight );
1096 m_Stat.onAddNode( nHeight );
1097 m_Stat.onInsertSuccess();
1103 /// Ensures that the \p val exists in the set
1105 The operation performs inserting or changing data with lock-free manner.
1107 If the item \p val is not found in the set, then \p val is inserted into the set.
1108 Otherwise, the functor \p func is called with item found.
1109 The functor signature is:
1111 void func( bool bNew, value_type& item, value_type& val );
1114 - \p bNew - \p true if the item has been inserted, \p false otherwise
1115 - \p item - item of the set
1116 - \p val - argument \p val passed into the \p ensure function
1117 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1118 refer to the same thing.
1120 The functor can change non-key fields of the \p item; however, \p func must guarantee
1121 that during changing no any other modifications could be made on this item by concurrent threads.
1123 You can pass \p func argument by value or by reference using \p std::ref.
1125 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1126 \p second is \p true if new item has been added or \p false if the item with \p key
1127 already is in the set.
1129 template <typename Func>
1130 std::pair<bool, bool> ensure( value_type& val, Func func )
1132 typename gc::Guard gNew;
1133 gNew.assign( &val );
1135 node_type * pNode = node_traits::to_node_ptr( val );
1136 scoped_node_ptr scp( pNode );
1137 unsigned int nHeight = pNode->height();
1138 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1139 bool bTowerMade = false;
1144 bool bFound = find_position( val, pos, key_comparator(), true );
1146 // scoped_node_ptr deletes the node tower if we create it before
1150 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1151 m_Stat.onEnsureExist();
1152 return std::make_pair( true, false );
1156 build_node( pNode );
1157 nHeight = pNode->height();
1162 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1163 m_Stat.onInsertRetry();
1167 increase_height( nHeight );
1170 m_Stat.onAddNode( nHeight );
1171 m_Stat.onEnsureNew();
1172 return std::make_pair( true, true );
1176 /// Unlinks the item \p val from the set
1178 The function searches the item \p val in the set and unlink it from the set
1179 if it is found and is equal to \p val.
1181 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
1182 and deletes the item found. \p unlink finds an item by key and deletes it
1183 only if \p val is an item of that set, i.e. the pointer to item found
1184 is equal to <tt> &val </tt>.
1186 The \ref disposer specified in \p Traits class template parameter is called
1187 by garbage collector \p GC asynchronously.
1189 The function returns \p true if success and \p false otherwise.
1191 bool unlink( value_type& val )
1195 if ( !find_position( val, pos, key_comparator(), false ) ) {
1196 m_Stat.onUnlinkFailed();
1200 node_type * pDel = pos.pCur;
1201 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1203 unsigned int nHeight = pDel->height();
1204 typename gc::Guard gDel;
1205 gDel.assign( node_traits::to_value_ptr(pDel) );
1207 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1209 m_Stat.onRemoveNode( nHeight );
1210 m_Stat.onUnlinkSuccess();
1214 m_Stat.onUnlinkFailed();
1218 /// Extracts the item from the set with specified \p key
1219 /** \anchor cds_intrusive_SkipListSet_hp_extract
1220 The function searches an item with key equal to \p key in the set,
1221 unlinks it from the set, and returns it in \p dest parameter.
1222 If the item with key equal to \p key is not found the function returns \p false.
1224 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1226 The \ref disposer specified in \p Traits class template parameter is called automatically
1227 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
1228 will be destroyed or released.
1229 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1233 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1237 skip_list::guarded_ptr gp;
1238 theList.extract( gp, 5 );
1242 // Destructor of gp releases internal HP guard
1246 template <typename Q>
1247 bool extract( guarded_ptr& dest, Q const& key )
1249 return extract_( dest.guard(), key, key_comparator() );
1252 /// Extracts the item from the set with comparing functor \p pred
1254 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1255 but \p pred predicate is used for key comparing.
1257 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1259 \p pred must imply the same element order as the comparator used for building the set.
1261 template <typename Q, typename Less>
1262 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
1264 return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1267 /// Extracts an item with minimal key from the list
1269 The function searches an item with minimal key, unlinks it, and returns the item found in \p dest parameter.
1270 If the skip-list is empty the function returns \p false.
1272 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1273 It means that the function gets leftmost item and tries to unlink it.
1274 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1275 So, the function returns the item with minimum key at the moment of list traversing.
1277 The \ref disposer specified in \p Traits class template parameter is called
1278 by garbage collector \p GC automatically when returned \ref guarded_ptr object
1279 will be destroyed or released.
1280 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1284 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1288 skip_list::guarded_ptr gp;
1289 if ( theList.extract_min( gp )) {
1293 // Destructor of gp releases internal HP guard
1297 bool extract_min( guarded_ptr& dest)
1299 return extract_min_( dest.guard() );
1302 /// Extracts an item with maximal key from the list
1304 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p dest parameter.
1305 If the skip-list is empty the function returns empty \p guarded_ptr.
1307 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1308 It means that the function gets rightmost item and tries to unlink it.
1309 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1310 So, the function returns the item with maximum key at the moment of list traversing.
1312 The \ref disposer specified in \p Traits class template parameter is called
1313 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1314 will be destroyed or released.
1315 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1319 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1323 skip_list::guarded_ptr gp;
1324 if ( theList.extract_max( gp )) {
1328 // Destructor of gp releases internal HP guard
1332 bool extract_max( guarded_ptr& dest )
1334 return extract_max_( dest.guard() );
1337 /// Deletes the item from the set
1338 /** \anchor cds_intrusive_SkipListSet_hp_erase
1339 The function searches an item with key equal to \p val in the set,
1340 unlinks it from the set, and returns \p true.
1341 If the item with key equal to \p val is not found the function return \p false.
1343 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1345 template <typename Q>
1346 bool erase( Q const& val )
1348 return erase_( val, key_comparator(), [](value_type const&) {} );
1351 /// Deletes the item from the set with comparing functor \p pred
1353 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1354 but \p pred predicate is used for key comparing.
1356 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1358 \p pred must imply the same element order as the comparator used for building the set.
1360 template <typename Q, typename Less>
1361 bool erase_with( Q const& val, Less pred )
1363 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1366 /// Deletes the item from the set
1367 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1368 The function searches an item with key equal to \p val in the set,
1369 call \p f functor with item found, unlinks it from the set, and returns \p true.
1370 The \ref disposer specified in \p Traits class template parameter is called
1371 by garbage collector \p GC asynchronously.
1373 The \p Func interface is
1376 void operator()( value_type const& item );
1379 The functor can be passed by reference with <tt>boost:ref</tt>
1381 If the item with key equal to \p val is not found the function return \p false.
1383 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1385 template <typename Q, typename Func>
1386 bool erase( Q const& val, Func f )
1388 return erase_( val, key_comparator(), f );
1391 /// Deletes the item from the set with comparing functor \p pred
1393 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1394 but \p pred predicate is used for key comparing.
1396 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1398 \p pred must imply the same element order as the comparator used for building the set.
1400 template <typename Q, typename Less, typename Func>
1401 bool erase_with( Q const& val, Less pred, Func f )
1403 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1406 /// Finds the key \p val
1407 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1408 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1409 The interface of \p Func functor is:
1412 void operator()( value_type& item, Q& val );
1415 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1417 You can pass \p f argument by value or by reference using \p std::ref.
1419 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1420 that \p item cannot be disposed during functor is executing.
1421 The functor does not serialize simultaneous access to the set \p item. If such access is
1422 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1424 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1425 can modify both arguments.
1427 Note the compare functor specified for class \p Traits template parameter
1428 should accept a parameter of type \p Q that can be not the same as \p value_type.
1430 The function returns \p true if \p val is found, \p false otherwise.
1432 template <typename Q, typename Func>
1433 bool find( Q& val, Func f )
1435 return find_with_( val, key_comparator(), f );
1438 /// Finds the key \p val with \p pred predicate for comparing
1440 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1441 but \p pred is used for key compare.
1443 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1445 \p pred must imply the same element order as the comparator used for building the set.
1447 template <typename Q, typename Less, typename Func>
1448 bool find_with( Q& val, Less pred, Func f )
1450 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1453 /// Finds the key \p val
1454 /** \anchor cds_intrusive_SkipListSet_hp_find_cfunc
1455 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1456 The interface of \p Func functor is:
1459 void operator()( value_type& item, Q const& val );
1462 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1464 You can pass \p f argument by value or by reference using \p std::ref.
1466 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1467 that \p item cannot be disposed during functor is executing.
1468 The functor does not serialize simultaneous access to the set \p item. If such access is
1469 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1471 Note the compare functor specified for class \p Traits template parameter
1472 should accept a parameter of type \p Q that can be not the same as \p value_type.
1474 The function returns \p true if \p val is found, \p false otherwise.
1476 template <typename Q, typename Func>
1477 bool find( Q const& val, Func f )
1479 return find_with_( val, key_comparator(), f );
1482 /// Finds the key \p val with \p pred predicate for comparing
1484 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_cfunc "find(Q const&, Func)"
1485 but \p pred is used for key compare.
1486 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1488 \p pred must imply the same element order as the comparator used for building the set.
1490 template <typename Q, typename Less, typename Func>
1491 bool find_with( Q const& val, Less pred, Func f )
1493 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1496 /// Finds the key \p val
1497 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1498 The function searches the item with key equal to \p val
1499 and returns \p true if it is found, and \p false otherwise.
1501 Note the compare functor specified for class \p Traits template parameter
1502 should accept a parameter of type \p Q that can be not the same as \p value_type.
1504 template <typename Q>
1505 bool find( Q const & val )
1507 return find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
1510 /// Finds the key \p val with comparing functor \p pred
1512 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1513 but \p pred is used for comparing the keys.
1514 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1516 \p pred must imply the same element order as the comparator used for building the set.
1518 template <typename Q, typename Less>
1519 bool find_with( Q const& val, Less pred )
1521 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1524 /// Finds the key \p val and return the item found
1525 /** \anchor cds_intrusive_SkipListSet_hp_get
1526 The function searches the item with key equal to \p val
1527 and assigns the item found to guarded pointer \p ptr.
1528 The function returns \p true if \p val is found, and \p false otherwise.
1529 If \p val is not found the \p ptr parameter is not changed.
1531 The \ref disposer specified in \p Traits class template parameter is called
1532 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1533 will be destroyed or released.
1534 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1538 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1542 skip_list::guarded_ptr gp;
1543 if ( theList.get( gp, 5 )) {
1547 // Destructor of guarded_ptr releases internal HP guard
1551 Note the compare functor specified for class \p Traits template parameter
1552 should accept a parameter of type \p Q that can be not the same as \p value_type.
1554 template <typename Q>
1555 bool get( guarded_ptr& ptr, Q const& val )
1557 return get_with_( ptr.guard(), val, key_comparator() );
1560 /// Finds the key \p val and return the item found
1562 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1563 but \p pred is used for comparing the keys.
1565 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1567 \p pred must imply the same element order as the comparator used for building the set.
1569 template <typename Q, typename Less>
1570 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
1572 return get_with_( ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
1575 /// Returns item count in the set
1577 The value returned depends on item counter type provided by \p Traits template parameter.
1578 If it is atomicity::empty_item_counter this function always returns 0.
1579 Therefore, the function is not suitable for checking the set emptiness, use \ref empty
1580 member function for this purpose.
1584 return m_ItemCounter;
1587 /// Checks if the set is empty
1590 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1593 /// Clears the set (non-atomic)
1595 The function unlink all items from the set.
1596 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1600 assert( set.empty() );
1602 the assertion could be raised.
1604 For each item the \ref disposer will be called after unlinking.
1609 while ( extract_min( gp ));
1612 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1613 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1615 return c_nMaxHeight;
1618 /// Returns const reference to internal statistics
1619 stat const& statistics() const
1626 }} // namespace cds::intrusive
1629 #endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H