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>
13 namespace cds { namespace intrusive {
16 namespace skip_list { namespace details {
18 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
22 typedef NodeTraits node_traits;
23 typedef BackOff back_off;
24 typedef typename node_traits::node_type node_type;
25 typedef typename node_traits::value_type value_type;
26 static CDS_CONSTEXPR bool const c_isConst = IsConst;
28 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type value_ref;
31 typedef typename node_type::marked_ptr marked_ptr;
32 typedef typename node_type::atomic_marked_ptr atomic_marked_ptr;
34 typename gc::Guard m_guard;
38 static value_type * gc_protect( marked_ptr p )
40 return node_traits::to_value_ptr( p.ptr() );
50 if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
51 // Current node is marked as deleted. So, its next pointer can point to anything
52 // In this case we interrupt our iteration and returns end() iterator.
57 marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
58 node_type * pp = p.ptr();
60 // p is marked as deleted. Spin waiting for physical removal
64 else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits() ) {
65 // p is marked as deleted. Spin waiting for physical removal
75 public: // for internal use only!!!
76 iterator( node_type& refHead )
82 marked_ptr p = m_guard.protect( refHead[0], gc_protect );
89 node_type * pp = p.ptr();
90 // Logically deleted node is marked from highest level
91 if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
105 iterator( iterator const& s)
106 : m_pNode( s.m_pNode )
108 m_guard.assign( node_traits::to_value_ptr(m_pNode) );
111 value_type * operator ->() const
113 assert( m_pNode != nullptr );
114 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
116 return node_traits::to_value_ptr( m_pNode );
119 value_ref operator *() const
121 assert( m_pNode != nullptr );
122 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
124 return *node_traits::to_value_ptr( m_pNode );
128 iterator& operator ++()
134 iterator& operator =(const iterator& src)
136 m_pNode = src.m_pNode;
137 m_guard.copy( src.m_guard );
141 template <typename Bkoff, bool C>
142 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
144 return m_pNode == i.m_pNode;
146 template <typename Bkoff, bool C>
147 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
149 return !( *this == i );
152 }} // namespace skip_list::details
155 /// Lock-free skip-list set
156 /** @ingroup cds_intrusive_map
157 @anchor cds_intrusive_SkipListSet_hp
159 The implementation of well-known probabilistic data structure called skip-list
160 invented by W.Pugh in his papers:
161 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
162 - [1990] W.Pugh A Skip List Cookbook
164 A skip-list is a probabilistic data structure that provides expected logarithmic
165 time search without the need of rebalance. The skip-list is a collection of sorted
166 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
167 Each list has a level, ranging from 0 to 32. The bottom-level list contains
168 all the nodes, and each higher-level list is a sublist of the lower-level lists.
169 Each node is created with a random top level (with a random height), and belongs
170 to all lists up to that level. The probability that a node has the height 1 is 1/2.
171 The probability that a node has the height N is 1/2 ** N (more precisely,
172 the distribution depends on an random generator provided, but our generators
175 The lock-free variant of skip-list is implemented according to book
176 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
177 chapter 14.4 "A Lock-Free Concurrent Skiplist".
179 <b>Template arguments</b>:
180 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T, see \p skip_list::node.
181 - \p T - type to be stored in the list. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
182 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
183 - \p Traits - skip-list traits, default is \p skip_list::traits.
184 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
187 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
188 the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
189 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
190 when you try to create skip-list object.
192 There are several specializations of \p %SkipListSet for each \p GC. You should include:
193 - <tt><cds/intrusive/skip_list_hp.h></tt> for \p gc::HP garbage collector
194 - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
195 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for append-only set
196 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
200 The class supports a forward iterator (\ref iterator and \ref const_iterator).
201 The iteration is ordered.
202 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
203 so, the element cannot be reclaimed while the iterator object is alive.
204 However, passing an iterator object between threads is dangerous.
206 @warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
207 all elements in the set: any concurrent deletion can exclude the element
208 pointed by the iterator from the set, and your iteration can be terminated
209 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
211 Remember, each iterator object requires 2 additional hazard pointers, that may be
212 a limited resource for \p GC like as \p gc::HP (for \p gc::DHP the count of
213 guards is unlimited).
215 The iterator class supports the following minimalistic interface:
222 iterator( iterator const& s);
224 value_type * operator ->() const;
225 value_type& operator *() const;
228 iterator& operator ++();
231 iterator& operator = (const iterator& src);
233 bool operator ==(iterator const& i ) const;
234 bool operator !=(iterator const& i ) const;
237 Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
241 You should incorporate \p skip_list::node into your struct \p T and provide
242 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
243 define a struct based on \p skip_list::traits.
245 Example for \p gc::HP and base hook:
247 // Include GC-related skip-list specialization
248 #include <cds/intrusive/skip_list_hp.h>
250 // Data stored in skip list
251 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
260 // my_data compare functor
262 int operator()( const my_data& d1, const my_data& d2 )
264 return d1.strKey.compare( d2.strKey );
267 int operator()( const my_data& d, const std::string& s )
269 return d.strKey.compare(s);
272 int operator()( const std::string& s, const my_data& d )
274 return s.compare( d.strKey );
279 // Declare your traits
280 struct my_traits: public cds::intrusive::skip_list::traits
282 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
283 typedef my_data_cmp compare;
286 // Declare skip-list set type
287 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
290 Equivalent option-based code:
292 // GC-related specialization
293 #include <cds/intrusive/skip_list_hp.h>
302 // Declare option-based skip-list set
303 typedef cds::intrusive::SkipListSet< cds::gc::HP
305 , typename cds::intrusive::skip_list::make_traits<
306 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
307 ,cds::intrusive::opt::compare< my_data_cmp >
316 #ifdef CDS_DOXYGEN_INVOKED
317 ,typename Traits = skip_list::traits
325 typedef GC gc; ///< Garbage collector
326 typedef T value_type; ///< type of value stored in the skip-list
327 typedef Traits traits; ///< Traits template parameter
329 typedef typename traits::hook hook; ///< hook type
330 typedef typename hook::node_type node_type; ///< node type
332 # ifdef CDS_DOXYGEN_INVOKED
333 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
335 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
338 typedef typename traits::disposer disposer; ///< item disposer
339 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
341 typedef typename traits::item_counter item_counter; ///< Item counting policy
342 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
343 typedef typename traits::random_level_generator random_level_generator; ///< random level generator
344 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
345 typedef typename traits::back_off back_off; ///< Back-off strategy
346 typedef typename traits::stat stat; ///< internal statistics type
349 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
351 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
353 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
354 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
356 static unsigned int const c_nMaxHeight = std::conditional<
357 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
358 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
359 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
363 static unsigned int const c_nMinHeight = 5;
367 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
368 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
372 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
374 typedef typename std::conditional<
375 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
376 ,intrusive_node_builder
377 ,typename traits::internal_node_builder
378 >::type node_builder;
380 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
382 // c_nMaxHeight * 2 - pPred/pSucc guards
383 // + 1 - for erase, unlink
385 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
387 node_type * pPrev[ c_nMaxHeight ];
388 node_type * pSucc[ c_nMaxHeight ];
390 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
391 node_type * pCur; // guarded by guards; needed only for \p ensure()
396 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
398 item_counter m_ItemCounter; ///< item counter
399 random_level_generator m_RandomLevelGen; ///< random level generator instance
400 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
401 mutable stat m_Stat; ///< internal statistics
405 unsigned int random_level()
407 // Random generator produces a number from range [0..31]
408 // We need a number from range [1..32]
409 return m_RandomLevelGen() + 1;
412 template <typename Q>
413 node_type * build_node( Q v )
415 return node_builder::make_tower( v, m_RandomLevelGen );
418 static value_type * gc_protect( marked_node_ptr p )
420 return node_traits::to_value_ptr( p.ptr() );
423 static void dispose_node( value_type * pVal )
425 assert( pVal != nullptr );
426 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
430 template <typename Q, typename Compare >
431 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
434 marked_node_ptr pSucc;
435 marked_node_ptr pCur;
437 // Hazard pointer array:
438 // pPred: [nLevel * 2]
439 // pSucc: [nLevel * 2 + 1]
442 pPred = m_Head.head();
445 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
446 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
448 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
450 // pCur.bits() means that pPred is logically deleted
454 if ( pCur.ptr() == nullptr ) {
455 // end of the list at level nLevel - goto next level
459 // pSucc contains deletion mark for pCur
460 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
462 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
465 if ( pSucc.bits() ) {
466 // pCur is marked, i.e. logically deleted.
467 marked_node_ptr p( pCur.ptr() );
468 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
469 memory_model::memory_order_release, atomics::memory_order_relaxed ))
472 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
473 m_Stat.onEraseWhileFind();
479 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
482 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
484 else if ( nCmp == 0 && bStopIfFound )
492 pos.pPrev[ nLevel ] = pPred;
493 pos.pSucc[ nLevel ] = pCur.ptr();
500 pos.pCur = pCur.ptr();
501 return pCur.ptr() && nCmp == 0;
504 bool find_min_position( position& pos )
507 marked_node_ptr pSucc;
508 marked_node_ptr pCur;
510 // Hazard pointer array:
511 // pPred: [nLevel * 2]
512 // pSucc: [nLevel * 2 + 1]
515 pPred = m_Head.head();
517 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
518 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
519 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
521 // pCur.bits() means that pPred is logically deleted
522 // head cannot be deleted
523 assert( pCur.bits() == 0 );
527 // pSucc contains deletion mark for pCur
528 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
530 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
533 if ( pSucc.bits() ) {
534 // pCur is marked, i.e. logically deleted.
535 marked_node_ptr p( pCur.ptr() );
536 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
537 memory_model::memory_order_release, atomics::memory_order_relaxed ))
540 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
547 pos.pPrev[ nLevel ] = pPred;
548 pos.pSucc[ nLevel ] = pCur.ptr();
551 return (pos.pCur = pCur.ptr()) != nullptr;
554 bool find_max_position( position& pos )
557 marked_node_ptr pSucc;
558 marked_node_ptr pCur;
560 // Hazard pointer array:
561 // pPred: [nLevel * 2]
562 // pSucc: [nLevel * 2 + 1]
565 pPred = m_Head.head();
567 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
568 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
570 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
572 // pCur.bits() means that pPred is logically deleted
576 if ( pCur.ptr() == nullptr ) {
577 // end of the list at level nLevel - goto next level
581 // pSucc contains deletion mark for pCur
582 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
584 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
587 if ( pSucc.bits() ) {
588 // pCur is marked, i.e. logically deleted.
589 marked_node_ptr p( pCur.ptr() );
590 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
591 memory_model::memory_order_release, atomics::memory_order_relaxed ))
594 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
603 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
604 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
609 pos.pPrev[ nLevel ] = pPred;
610 pos.pSucc[ nLevel ] = pCur.ptr();
613 return (pos.pCur = pCur.ptr()) != nullptr;
616 template <typename Func>
617 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
619 unsigned int nHeight = pNode->height();
621 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
622 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
625 marked_node_ptr p( pos.pSucc[0] );
626 pNode->next( 0 ).store( p, memory_model::memory_order_release );
627 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
633 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
636 marked_node_ptr q( pos.pSucc[ nLevel ]);
637 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
638 // pNode has been marked as removed while we are inserting it
641 m_Stat.onLogicDeleteWhileInsert();
645 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
648 // Renew insert position
649 m_Stat.onRenewInsertPosition();
650 if ( !find_position( val, pos, key_comparator(), false )) {
651 // The node has been deleted while we are inserting it
652 m_Stat.onNotFoundWhileInsert();
660 template <typename Func>
661 bool try_remove_at( node_type * pDel, position& pos, Func f )
663 assert( pDel != nullptr );
665 marked_node_ptr pSucc;
666 typename gc::Guard gSucc;
668 // logical deletion (marking)
669 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
671 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
672 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
673 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
681 pSucc = gSucc.protect( pDel->next(0), gc_protect );
682 marked_node_ptr p( pSucc.ptr() );
683 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
684 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
686 f( *node_traits::to_value_ptr( pDel ));
691 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
692 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
693 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
694 memory_model::memory_order_release, atomics::memory_order_relaxed) )
697 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
698 m_Stat.onSlowErase();
703 // Fast erasing success
704 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
705 m_Stat.onFastErase();
716 enum finsd_fastpath_result {
718 find_fastpath_not_found,
721 template <typename Q, typename Compare, typename Func>
722 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
725 typename gc::template GuardArray<2> guards;
726 marked_node_ptr pCur;
727 marked_node_ptr pNull;
731 pPred = m_Head.head();
732 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
733 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
737 while ( pCur != pNull ) {
739 unsigned int nAttempt = 0;
740 while ( pCur.bits() && nAttempt++ < 16 ) {
742 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
747 // Maybe, we are on deleted node sequence
748 // Abort searching, try slow-path
749 return find_fastpath_abort;
754 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
758 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
760 else if ( nCmp == 0 ) {
762 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
763 return find_fastpath_found;
765 else // pCur > val - go down
771 return find_fastpath_not_found;
774 template <typename Q, typename Compare, typename Func>
775 bool find_slowpath( Q& val, Compare cmp, Func f )
778 if ( find_position( val, pos, cmp, true )) {
779 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
781 f( *node_traits::to_value_ptr( pos.pCur ), val );
788 template <typename Q, typename Compare, typename Func>
789 bool find_with_( Q& val, Compare cmp, Func f )
791 switch ( find_fastpath( val, cmp, f )) {
792 case find_fastpath_found:
793 m_Stat.onFindFastSuccess();
795 case find_fastpath_not_found:
796 m_Stat.onFindFastFailed();
802 if ( find_slowpath( val, cmp, f )) {
803 m_Stat.onFindSlowSuccess();
807 m_Stat.onFindSlowFailed();
811 template <typename Q, typename Compare>
812 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
814 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
817 template <typename Q, typename Compare, typename Func>
818 bool erase_( Q const& val, Compare cmp, Func f )
822 if ( !find_position( val, pos, cmp, false ) ) {
823 m_Stat.onEraseFailed();
827 node_type * pDel = pos.pCur;
828 typename gc::Guard gDel;
829 gDel.assign( node_traits::to_value_ptr(pDel) );
830 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
832 unsigned int nHeight = pDel->height();
833 if ( try_remove_at( pDel, pos, f )) {
835 m_Stat.onRemoveNode( nHeight );
836 m_Stat.onEraseSuccess();
840 m_Stat.onEraseFailed();
844 template <typename Q, typename Compare>
845 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
850 if ( !find_position( val, pos, cmp, false ) ) {
851 m_Stat.onExtractFailed();
856 node_type * pDel = pos.pCur;
857 guard.set( node_traits::to_value_ptr(pDel));
858 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
860 unsigned int nHeight = pDel->height();
861 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
863 m_Stat.onRemoveNode( nHeight );
864 m_Stat.onExtractSuccess();
867 m_Stat.onExtractRetry();
871 bool extract_min_( typename guarded_ptr::native_guard& gDel )
876 if ( !find_min_position( pos ) ) {
878 m_Stat.onExtractMinFailed();
883 node_type * pDel = pos.pCur;
885 unsigned int nHeight = pDel->height();
886 gDel.set( node_traits::to_value_ptr(pDel) );
888 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
890 m_Stat.onRemoveNode( nHeight );
891 m_Stat.onExtractMinSuccess();
895 m_Stat.onExtractMinRetry();
899 bool extract_max_( typename guarded_ptr::native_guard& gDel )
904 if ( !find_max_position( pos ) ) {
906 m_Stat.onExtractMaxFailed();
911 node_type * pDel = pos.pCur;
913 unsigned int nHeight = pDel->height();
914 gDel.set( node_traits::to_value_ptr(pDel) );
916 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
918 m_Stat.onRemoveNode( nHeight );
919 m_Stat.onExtractMaxSuccess();
923 m_Stat.onExtractMaxRetry();
927 void increase_height( unsigned int nHeight )
929 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
930 if ( nCur < nHeight )
931 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
936 /// Default constructor
938 The constructor checks whether the count of guards is enough
939 for skip-list and may raise an exception if not.
942 : m_Head( c_nMaxHeight )
943 , m_nHeight( c_nMinHeight )
945 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
947 gc::check_available_guards( c_nHazardPtrCount );
949 // Barrier for head node
950 atomics::atomic_thread_fence( memory_model::memory_order_release );
953 /// Clears and destructs the skip-list
961 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
963 /// Const iterator type
964 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
966 /// Returns a forward iterator addressing the first element in a set
969 return iterator( *m_Head.head() );
972 /// Returns a forward const iterator addressing the first element in a set
973 const_iterator begin() const
975 return const_iterator( *m_Head.head() );
977 /// Returns a forward const iterator addressing the first element in a set
978 const_iterator cbegin() const
980 return const_iterator( *m_Head.head() );
983 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
989 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
990 const_iterator end() const
992 return const_iterator();
994 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
995 const_iterator cend() const
997 return const_iterator();
1001 /// Inserts new node
1003 The function inserts \p val in the set if it does not contain
1004 an item with key equal to \p val.
1006 Returns \p true if \p val is placed into the set, \p false otherwise.
1008 bool insert( value_type& val )
1010 return insert( val, []( value_type& ) {} );
1013 /// Inserts new node
1015 This function is intended for derived non-intrusive containers.
1017 The function allows to split creating of new item into two part:
1018 - create item with key only
1019 - insert new item into the set
1020 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1022 The functor signature is:
1024 void func( value_type& val );
1026 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1027 \p val no any other changes could be made on this set's item by concurrent threads.
1028 The user-defined functor is called only if the inserting is success.
1030 template <typename Func>
1031 bool insert( value_type& val, Func f )
1033 typename gc::Guard gNew;
1034 gNew.assign( &val );
1036 node_type * pNode = node_traits::to_node_ptr( val );
1037 scoped_node_ptr scp( pNode );
1038 unsigned int nHeight = pNode->height();
1039 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1040 bool bTowerMade = false;
1045 bool bFound = find_position( val, pos, key_comparator(), true );
1047 // scoped_node_ptr deletes the node tower if we create it
1051 m_Stat.onInsertFailed();
1056 build_node( pNode );
1057 nHeight = pNode->height();
1062 if ( !insert_at_position( val, pNode, pos, f )) {
1063 m_Stat.onInsertRetry();
1067 increase_height( nHeight );
1069 m_Stat.onAddNode( nHeight );
1070 m_Stat.onInsertSuccess();
1076 /// Ensures that the \p val exists in the set
1078 The operation performs inserting or changing data with lock-free manner.
1080 If the item \p val is not found in the set, then \p val is inserted into the set.
1081 Otherwise, the functor \p func is called with item found.
1082 The functor signature is:
1084 void func( bool bNew, value_type& item, value_type& val );
1087 - \p bNew - \p true if the item has been inserted, \p false otherwise
1088 - \p item - item of the set
1089 - \p val - argument \p val passed into the \p ensure function
1090 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1091 refer to the same thing.
1093 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1094 \p second is \p true if new item has been added or \p false if the item with \p key
1095 already is in the set.
1097 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1099 template <typename Func>
1100 std::pair<bool, bool> ensure( value_type& val, Func func )
1102 typename gc::Guard gNew;
1103 gNew.assign( &val );
1105 node_type * pNode = node_traits::to_node_ptr( val );
1106 scoped_node_ptr scp( pNode );
1107 unsigned int nHeight = pNode->height();
1108 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1109 bool bTowerMade = false;
1114 bool bFound = find_position( val, pos, key_comparator(), true );
1116 // scoped_node_ptr deletes the node tower if we create it before
1120 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1121 m_Stat.onEnsureExist();
1122 return std::make_pair( true, false );
1126 build_node( pNode );
1127 nHeight = pNode->height();
1132 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1133 m_Stat.onInsertRetry();
1137 increase_height( nHeight );
1140 m_Stat.onAddNode( nHeight );
1141 m_Stat.onEnsureNew();
1142 return std::make_pair( true, true );
1146 /// Unlinks the item \p val from the set
1148 The function searches the item \p val in the set and unlink it from the set
1149 if it is found and is equal to \p val.
1151 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1152 and deletes the item found. \p %unlink() finds an item by key and deletes it
1153 only if \p val is an item of that set, i.e. the pointer to item found
1154 is equal to <tt> &val </tt>.
1156 The \p disposer specified in \p Traits class template parameter is called
1157 by garbage collector \p GC asynchronously.
1159 The function returns \p true if success and \p false otherwise.
1161 bool unlink( value_type& val )
1165 if ( !find_position( val, pos, key_comparator(), false ) ) {
1166 m_Stat.onUnlinkFailed();
1170 node_type * pDel = pos.pCur;
1171 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1173 unsigned int nHeight = pDel->height();
1174 typename gc::Guard gDel;
1175 gDel.assign( node_traits::to_value_ptr(pDel) );
1177 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1179 m_Stat.onRemoveNode( nHeight );
1180 m_Stat.onUnlinkSuccess();
1184 m_Stat.onUnlinkFailed();
1188 /// Extracts the item from the set with specified \p key
1189 /** \anchor cds_intrusive_SkipListSet_hp_extract
1190 The function searches an item with key equal to \p key in the set,
1191 unlinks it from the set, and returns it as \p guarded_ptr object.
1192 If \p key is not found the function returns an empty guarded pointer.
1194 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1196 The \p disposer specified in \p Traits class template parameter is called automatically
1197 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1198 will be destroyed or released.
1199 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1203 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1207 skip_list::guarded_ptr gp(theList.extract( 5 ));
1212 // Destructor of gp releases internal HP guard
1216 template <typename Q>
1217 guarded_ptr extract( Q const& key )
1220 extract_( gp.guard(), key, key_comparator() );
1224 /// Extracts the item from the set with comparing functor \p pred
1226 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1227 but \p pred predicate is used for key comparing.
1229 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1231 \p pred must imply the same element order as the comparator used for building the set.
1233 template <typename Q, typename Less>
1234 guarded_ptr extract_with( Q const& key, Less pred )
1238 extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1242 /// Extracts an item with minimal key from the list
1244 The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
1245 If the skip-list is empty the function returns an empty guarded pointer.
1247 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1248 It means that the function gets leftmost item and tries to unlink it.
1249 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1250 So, the function returns the item with minimum key at the moment of list traversing.
1252 The \p disposer specified in \p Traits class template parameter is called
1253 by garbage collector \p GC automatically when returned \p guarded_ptr object
1254 will be destroyed or released.
1255 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1259 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1263 skip_list::guarded_ptr gp(theList.extract_min());
1268 // Destructor of gp releases internal HP guard
1272 guarded_ptr extract_min()
1275 extract_min_( gp.guard() );
1279 /// Extracts an item with maximal key from the list
1281 The function searches an item with maximal key, unlinks it, and returns the pointer to item
1282 as \p guarded_ptr object.
1283 If the skip-list is empty the function returns an empty \p guarded_ptr.
1285 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1286 It means that the function gets rightmost item and tries to unlink it.
1287 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1288 So, the function returns the item with maximum key at the moment of list traversing.
1290 The \p disposer specified in \p Traits class template parameter is called
1291 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1292 will be destroyed or released.
1293 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1297 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1301 skip_list::guarded_ptr gp( theList.extract_max( gp ));
1306 // Destructor of gp releases internal HP guard
1310 guarded_ptr extract_max()
1313 extract_max_( gp.guard() );
1317 /// Deletes the item from the set
1318 /** \anchor cds_intrusive_SkipListSet_hp_erase
1319 The function searches an item with key equal to \p key in the set,
1320 unlinks it from the set, and returns \p true.
1321 If the item with key equal to \p key is not found the function return \p false.
1323 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1325 template <typename Q>
1326 bool erase( Q const& key )
1328 return erase_( key, key_comparator(), [](value_type const&) {} );
1331 /// Deletes the item from the set with comparing functor \p pred
1333 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1334 but \p pred predicate is used for key comparing.
1336 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1338 \p pred must imply the same element order as the comparator used for building the set.
1340 template <typename Q, typename Less>
1341 bool erase_with( Q const& key, Less pred )
1344 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1347 /// Deletes the item from the set
1348 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1349 The function searches an item with key equal to \p key in the set,
1350 call \p f functor with item found, unlinks it from the set, and returns \p true.
1351 The \ref disposer specified in \p Traits class template parameter is called
1352 by garbage collector \p GC asynchronously.
1354 The \p Func interface is
1357 void operator()( value_type const& item );
1361 If the item with key equal to \p key is not found the function return \p false.
1363 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1365 template <typename Q, typename Func>
1366 bool erase( Q const& key, Func f )
1368 return erase_( key, key_comparator(), f );
1371 /// Deletes the item from the set with comparing functor \p pred
1373 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1374 but \p pred predicate is used for key comparing.
1376 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1378 \p pred must imply the same element order as the comparator used for building the set.
1380 template <typename Q, typename Less, typename Func>
1381 bool erase_with( Q const& key, Less pred, Func f )
1384 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1388 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1389 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1390 The interface of \p Func functor is:
1393 void operator()( value_type& item, Q& key );
1396 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1398 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1399 that \p item cannot be disposed during functor is executing.
1400 The functor does not serialize simultaneous access to the set \p item. If such access is
1401 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1403 Note the compare functor specified for class \p Traits template parameter
1404 should accept a parameter of type \p Q that can be not the same as \p value_type.
1406 The function returns \p true if \p key is found, \p false otherwise.
1408 template <typename Q, typename Func>
1409 bool find( Q& key, Func f )
1411 return find_with_( key, key_comparator(), f );
1414 template <typename Q, typename Func>
1415 bool find( Q const& key, Func f )
1417 return find_with_( key, key_comparator(), f );
1421 /// Finds the key \p key with \p pred predicate for comparing
1423 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1424 but \p pred is used for key compare.
1426 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1428 \p pred must imply the same element order as the comparator used for building the set.
1430 template <typename Q, typename Less, typename Func>
1431 bool find_with( Q& key, Less pred, Func f )
1434 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1437 template <typename Q, typename Less, typename Func>
1438 bool find_with( Q const& key, Less pred, Func f )
1441 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1446 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1447 The function searches the item with key equal to \p key
1448 and returns \p true if it is found, and \p false otherwise.
1450 Note the compare functor specified for class \p Traits template parameter
1451 should accept a parameter of type \p Q that can be not the same as \p value_type.
1453 template <typename Q>
1454 bool find( Q const& key )
1456 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1459 /// Finds \p key with comparing functor \p pred
1461 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1462 but \p pred is used for comparing the keys.
1463 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1465 \p pred must imply the same element order as the comparator used for building the set.
1467 template <typename Q, typename Less>
1468 bool find_with( Q const& key, Less pred )
1471 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1474 /// Finds \p key and return the item found
1475 /** \anchor cds_intrusive_SkipListSet_hp_get
1476 The function searches the item with key equal to \p key
1477 and returns the pointer to the item found as \p guarded_ptr.
1478 If \p key is not found the function returns an empt guarded pointer.
1480 The \p disposer specified in \p Traits class template parameter is called
1481 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1482 will be destroyed or released.
1483 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1487 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1491 skip_list::guarded_ptr gp(theList.get( 5 ));
1496 // Destructor of guarded_ptr releases internal HP guard
1500 Note the compare functor specified for class \p Traits template parameter
1501 should accept a parameter of type \p Q that can be not the same as \p value_type.
1503 template <typename Q>
1504 guarded_ptr get( Q const& key )
1507 get_with_( gp.guard(), key, key_comparator() );
1511 /// Finds \p key and return the item found
1513 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1514 but \p pred is used for comparing the keys.
1516 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1518 \p pred must imply the same element order as the comparator used for building the set.
1520 template <typename Q, typename Less>
1521 guarded_ptr get_with( Q const& key, Less pred )
1525 get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1529 /// Returns item count in the set
1531 The value returned depends on item counter type provided by \p Traits template parameter.
1532 If it is \p atomicity::empty_item_counter this function always returns 0.
1533 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1538 return m_ItemCounter;
1541 /// Checks if the set is empty
1544 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1547 /// Clears the set (not atomic)
1549 The function unlink all items from the set.
1550 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1554 assert( set.empty() );
1556 the assertion could be raised.
1558 For each item the \ref disposer will be called after unlinking.
1563 while ( extract_min_( gp.guard() ));
1566 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1567 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1569 return c_nMaxHeight;
1572 /// Returns const reference to internal statistics
1573 stat const& statistics() const
1579 }} // namespace cds::intrusive
1582 #endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H