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 cds::gc::guarded_ptr< gc, 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 gc::Guard& guard, Q const& val, Compare cmp )
814 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&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 gc::Guard& guard, Q const& val, Compare cmp )
850 if ( !find_position( val, pos, cmp, false ) ) {
851 m_Stat.onExtractFailed();
855 node_type * pDel = pos.pCur;
856 guard.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, [](value_type const&) {} )) {
862 m_Stat.onRemoveNode( nHeight );
863 m_Stat.onExtractSuccess();
867 m_Stat.onExtractRetry();
871 bool extract_min_( typename gc::Guard& gDel )
876 if ( !find_min_position( pos ) ) {
878 m_Stat.onExtractMinFailed();
882 node_type * pDel = pos.pCur;
884 unsigned int nHeight = pDel->height();
885 gDel.assign( node_traits::to_value_ptr(pDel) );
887 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
889 m_Stat.onRemoveNode( nHeight );
890 m_Stat.onExtractMinSuccess();
894 m_Stat.onExtractMinRetry();
898 bool extract_max_( typename gc::Guard& gDel )
903 if ( !find_max_position( pos ) ) {
905 m_Stat.onExtractMaxFailed();
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.onExtractMaxSuccess();
921 m_Stat.onExtractMaxRetry();
925 void increase_height( unsigned int nHeight )
927 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
928 if ( nCur < nHeight )
929 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
934 /// Default constructor
936 The constructor checks whether the count of guards is enough
937 for skip-list and may raise an exception if not.
940 : m_Head( c_nMaxHeight )
941 , m_nHeight( c_nMinHeight )
943 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
945 gc::check_available_guards( c_nHazardPtrCount );
947 // Barrier for head node
948 atomics::atomic_thread_fence( memory_model::memory_order_release );
951 /// Clears and destructs the skip-list
959 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
961 /// Const iterator type
962 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
964 /// Returns a forward iterator addressing the first element in a set
967 return iterator( *m_Head.head() );
970 /// Returns a forward const iterator addressing the first element in a set
971 const_iterator begin() const
973 return const_iterator( *m_Head.head() );
975 /// Returns a forward const iterator addressing the first element in a set
976 const_iterator cbegin() const
978 return const_iterator( *m_Head.head() );
981 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
987 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
988 const_iterator end() const
990 return const_iterator();
992 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
993 const_iterator cend() const
995 return const_iterator();
1001 The function inserts \p val in the set if it does not contain
1002 an item with key equal to \p val.
1004 Returns \p true if \p val is placed into the set, \p false otherwise.
1006 bool insert( value_type& val )
1008 return insert( val, []( value_type& ) {} );
1011 /// Inserts new node
1013 This function is intended for derived non-intrusive containers.
1015 The function allows to split creating of new item into two part:
1016 - create item with key only
1017 - insert new item into the set
1018 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1020 The functor signature is:
1022 void func( value_type& val );
1024 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1025 \p val no any other changes could be made on this set's item by concurrent threads.
1026 The user-defined functor is called only if the inserting is success.
1028 template <typename Func>
1029 bool insert( value_type& val, Func f )
1031 typename gc::Guard gNew;
1032 gNew.assign( &val );
1034 node_type * pNode = node_traits::to_node_ptr( val );
1035 scoped_node_ptr scp( pNode );
1036 unsigned int nHeight = pNode->height();
1037 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1038 bool bTowerMade = false;
1043 bool bFound = find_position( val, pos, key_comparator(), true );
1045 // scoped_node_ptr deletes the node tower if we create it
1049 m_Stat.onInsertFailed();
1054 build_node( pNode );
1055 nHeight = pNode->height();
1060 if ( !insert_at_position( val, pNode, pos, f )) {
1061 m_Stat.onInsertRetry();
1065 increase_height( nHeight );
1067 m_Stat.onAddNode( nHeight );
1068 m_Stat.onInsertSuccess();
1074 /// Ensures that the \p val exists in the set
1076 The operation performs inserting or changing data with lock-free manner.
1078 If the item \p val is not found in the set, then \p val is inserted into the set.
1079 Otherwise, the functor \p func is called with item found.
1080 The functor signature is:
1082 void func( bool bNew, value_type& item, value_type& val );
1085 - \p bNew - \p true if the item has been inserted, \p false otherwise
1086 - \p item - item of the set
1087 - \p val - argument \p val passed into the \p ensure function
1088 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1089 refer to the same thing.
1091 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1092 \p second is \p true if new item has been added or \p false if the item with \p key
1093 already is in the set.
1095 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1097 template <typename Func>
1098 std::pair<bool, bool> ensure( value_type& val, Func func )
1100 typename gc::Guard gNew;
1101 gNew.assign( &val );
1103 node_type * pNode = node_traits::to_node_ptr( val );
1104 scoped_node_ptr scp( pNode );
1105 unsigned int nHeight = pNode->height();
1106 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1107 bool bTowerMade = false;
1112 bool bFound = find_position( val, pos, key_comparator(), true );
1114 // scoped_node_ptr deletes the node tower if we create it before
1118 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1119 m_Stat.onEnsureExist();
1120 return std::make_pair( true, false );
1124 build_node( pNode );
1125 nHeight = pNode->height();
1130 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1131 m_Stat.onInsertRetry();
1135 increase_height( nHeight );
1138 m_Stat.onAddNode( nHeight );
1139 m_Stat.onEnsureNew();
1140 return std::make_pair( true, true );
1144 /// Unlinks the item \p val from the set
1146 The function searches the item \p val in the set and unlink it from the set
1147 if it is found and is equal to \p val.
1149 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1150 and deletes the item found. \p %unlink() finds an item by key and deletes it
1151 only if \p val is an item of that set, i.e. the pointer to item found
1152 is equal to <tt> &val </tt>.
1154 The \p disposer specified in \p Traits class template parameter is called
1155 by garbage collector \p GC asynchronously.
1157 The function returns \p true if success and \p false otherwise.
1159 bool unlink( value_type& val )
1163 if ( !find_position( val, pos, key_comparator(), false ) ) {
1164 m_Stat.onUnlinkFailed();
1168 node_type * pDel = pos.pCur;
1169 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1171 unsigned int nHeight = pDel->height();
1172 typename gc::Guard gDel;
1173 gDel.assign( node_traits::to_value_ptr(pDel) );
1175 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1177 m_Stat.onRemoveNode( nHeight );
1178 m_Stat.onUnlinkSuccess();
1182 m_Stat.onUnlinkFailed();
1186 /// Extracts the item from the set with specified \p key
1187 /** \anchor cds_intrusive_SkipListSet_hp_extract
1188 The function searches an item with key equal to \p key in the set,
1189 unlinks it from the set, and returns it in \p dest parameter.
1190 If the item with key equal to \p key is not found the function returns \p false.
1192 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1194 The \ref disposer specified in \p Traits class template parameter is called automatically
1195 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1196 will be destroyed or released.
1197 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1201 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1205 skip_list::guarded_ptr gp;
1206 theList.extract( gp, 5 );
1210 // Destructor of gp releases internal HP guard
1214 template <typename Q>
1215 bool extract( guarded_ptr& dest, Q const& key )
1217 return extract_( dest.guard(), key, key_comparator() );
1220 /// Extracts the item from the set with comparing functor \p pred
1222 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1223 but \p pred predicate is used for key comparing.
1225 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1227 \p pred must imply the same element order as the comparator used for building the set.
1229 template <typename Q, typename Less>
1230 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
1233 return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1236 /// Extracts an item with minimal key from the list
1238 The function searches an item with minimal key, unlinks it, and returns the item found in \p dest parameter.
1239 If the skip-list is empty the function returns \p false.
1241 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1242 It means that the function gets leftmost item and tries to unlink it.
1243 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1244 So, the function returns the item with minimum key at the moment of list traversing.
1246 The \p disposer specified in \p Traits class template parameter is called
1247 by garbage collector \p GC automatically when returned \p guarded_ptr object
1248 will be destroyed or released.
1249 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1253 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1257 skip_list::guarded_ptr gp;
1258 if ( theList.extract_min( gp )) {
1262 // Destructor of gp releases internal HP guard
1266 bool extract_min( guarded_ptr& dest)
1268 return extract_min_( dest.guard() );
1271 /// Extracts an item with maximal key from the list
1273 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p dest parameter.
1274 If the skip-list is empty the function returns empty \p guarded_ptr.
1276 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1277 It means that the function gets rightmost item and tries to unlink it.
1278 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1279 So, the function returns the item with maximum key at the moment of list traversing.
1281 The \p disposer specified in \p Traits class template parameter is called
1282 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1283 will be destroyed or released.
1284 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1288 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1292 skip_list::guarded_ptr gp;
1293 if ( theList.extract_max( gp )) {
1297 // Destructor of gp releases internal HP guard
1301 bool extract_max( guarded_ptr& dest )
1303 return extract_max_( dest.guard() );
1306 /// Deletes the item from the set
1307 /** \anchor cds_intrusive_SkipListSet_hp_erase
1308 The function searches an item with key equal to \p key in the set,
1309 unlinks it from the set, and returns \p true.
1310 If the item with key equal to \p key is not found the function return \p false.
1312 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1314 template <typename Q>
1315 bool erase( Q const& key )
1317 return erase_( key, key_comparator(), [](value_type const&) {} );
1320 /// Deletes the item from the set with comparing functor \p pred
1322 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1323 but \p pred predicate is used for key comparing.
1325 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1327 \p pred must imply the same element order as the comparator used for building the set.
1329 template <typename Q, typename Less>
1330 bool erase_with( Q const& key, Less pred )
1333 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1336 /// Deletes the item from the set
1337 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1338 The function searches an item with key equal to \p key in the set,
1339 call \p f functor with item found, unlinks it from the set, and returns \p true.
1340 The \ref disposer specified in \p Traits class template parameter is called
1341 by garbage collector \p GC asynchronously.
1343 The \p Func interface is
1346 void operator()( value_type const& item );
1350 If the item with key equal to \p key is not found the function return \p false.
1352 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1354 template <typename Q, typename Func>
1355 bool erase( Q const& key, Func f )
1357 return erase_( key, key_comparator(), f );
1360 /// Deletes the item from the set with comparing functor \p pred
1362 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1363 but \p pred predicate is used for key comparing.
1365 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1367 \p pred must imply the same element order as the comparator used for building the set.
1369 template <typename Q, typename Less, typename Func>
1370 bool erase_with( Q const& key, Less pred, Func f )
1373 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1377 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1378 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1379 The interface of \p Func functor is:
1382 void operator()( value_type& item, Q& key );
1385 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1387 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1388 that \p item cannot be disposed during functor is executing.
1389 The functor does not serialize simultaneous access to the set \p item. If such access is
1390 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1392 Note the compare functor specified for class \p Traits template parameter
1393 should accept a parameter of type \p Q that can be not the same as \p value_type.
1395 The function returns \p true if \p key is found, \p false otherwise.
1397 template <typename Q, typename Func>
1398 bool find( Q& key, Func f )
1400 return find_with_( key, key_comparator(), f );
1403 template <typename Q, typename Func>
1404 bool find( Q const& key, Func f )
1406 return find_with_( key, key_comparator(), f );
1410 /// Finds the key \p key with \p pred predicate for comparing
1412 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1413 but \p pred is used for key compare.
1415 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1417 \p pred must imply the same element order as the comparator used for building the set.
1419 template <typename Q, typename Less, typename Func>
1420 bool find_with( Q& key, Less pred, Func f )
1423 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1426 template <typename Q, typename Less, typename Func>
1427 bool find_with( Q const& key, Less pred, Func f )
1430 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1435 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1436 The function searches the item with key equal to \p key
1437 and returns \p true if it is found, and \p false otherwise.
1439 Note the compare functor specified for class \p Traits template parameter
1440 should accept a parameter of type \p Q that can be not the same as \p value_type.
1442 template <typename Q>
1443 bool find( Q const& key )
1445 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1448 /// Finds \p key with comparing functor \p pred
1450 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1451 but \p pred is used for comparing the keys.
1452 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1454 \p pred must imply the same element order as the comparator used for building the set.
1456 template <typename Q, typename Less>
1457 bool find_with( Q const& key, Less pred )
1460 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1463 /// Finds \p key and return the item found
1464 /** \anchor cds_intrusive_SkipListSet_hp_get
1465 The function searches the item with key equal to \p key
1466 and assigns the item found to guarded pointer \p ptr.
1467 The function returns \p true if \p key is found, and \p false otherwise.
1468 If \p key is not found the \p ptr parameter is not changed.
1470 The \ref disposer specified in \p Traits class template parameter is called
1471 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1472 will be destroyed or released.
1473 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1477 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1481 skip_list::guarded_ptr gp;
1482 if ( theList.get( gp, 5 )) {
1486 // Destructor of guarded_ptr releases internal HP guard
1490 Note the compare functor specified for class \p Traits template parameter
1491 should accept a parameter of type \p Q that can be not the same as \p value_type.
1493 template <typename Q>
1494 bool get( guarded_ptr& ptr, Q const& key )
1496 return get_with_( ptr.guard(), key, key_comparator() );
1499 /// Finds \p key and return the item found
1501 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1502 but \p pred is used for comparing the keys.
1504 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1506 \p pred must imply the same element order as the comparator used for building the set.
1508 template <typename Q, typename Less>
1509 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
1512 return get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1515 /// Returns item count in the set
1517 The value returned depends on item counter type provided by \p Traits template parameter.
1518 If it is \p atomicity::empty_item_counter this function always returns 0.
1519 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1524 return m_ItemCounter;
1527 /// Checks if the set is empty
1530 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1533 /// Clears the set (not atomic)
1535 The function unlink all items from the set.
1536 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1540 assert( set.empty() );
1542 the assertion could be raised.
1544 For each item the \ref disposer will be called after unlinking.
1549 while ( extract_min( gp ));
1552 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1553 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1555 return c_nMaxHeight;
1558 /// Returns const reference to internal statistics
1559 stat const& statistics() const
1565 }} // namespace cds::intrusive
1568 #endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H