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 CDS_CONSTEXPR 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".
180 <b>Template arguments</b>:
181 - \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.
182 - \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)
183 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
184 - \p Traits - skip-list traits, default is \p skip_list::traits.
185 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
188 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
189 the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
190 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
191 when you try to create skip-list object.
193 There are several specializations of \p %SkipListSet for each \p GC. You should include:
194 - <tt><cds/intrusive/skip_list_hp.h></tt> for \p gc::HP garbage collector
195 - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
196 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for append-only set
197 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
201 The class supports a forward iterator (\ref iterator and \ref const_iterator).
202 The iteration is ordered.
203 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
204 so, the element cannot be reclaimed while the iterator object is alive.
205 However, passing an iterator object between threads is dangerous.
207 @warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
208 all elements in the set: any concurrent deletion can exclude the element
209 pointed by the iterator from the set, and your iteration can be terminated
210 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
212 Remember, each iterator object requires 2 additional hazard pointers, that may be
213 a limited resource for \p GC like as \p gc::HP (for \p gc::DHP the count of
214 guards is unlimited).
216 The iterator class supports the following minimalistic interface:
223 iterator( iterator const& s);
225 value_type * operator ->() const;
226 value_type& operator *() const;
229 iterator& operator ++();
232 iterator& operator = (const iterator& src);
234 bool operator ==(iterator const& i ) const;
235 bool operator !=(iterator const& i ) const;
238 Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
242 You should incorporate \p skip_list::node into your struct \p T and provide
243 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
244 define a struct based on \p skip_list::traits.
246 Example for \p gc::HP and base hook:
248 // Include GC-related skip-list specialization
249 #include <cds/intrusive/skip_list_hp.h>
251 // Data stored in skip list
252 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
261 // my_data compare functor
263 int operator()( const my_data& d1, const my_data& d2 )
265 return d1.strKey.compare( d2.strKey );
268 int operator()( const my_data& d, const std::string& s )
270 return d.strKey.compare(s);
273 int operator()( const std::string& s, const my_data& d )
275 return s.compare( d.strKey );
280 // Declare your traits
281 struct my_traits: public cds::intrusive::skip_list::traits
283 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
284 typedef my_data_cmp compare;
287 // Declare skip-list set type
288 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
291 Equivalent option-based code:
293 // GC-related specialization
294 #include <cds/intrusive/skip_list_hp.h>
303 // Declare option-based skip-list set
304 typedef cds::intrusive::SkipListSet< cds::gc::HP
306 , typename cds::intrusive::skip_list::make_traits<
307 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
308 ,cds::intrusive::opt::compare< my_data_cmp >
317 #ifdef CDS_DOXYGEN_INVOKED
318 ,typename Traits = skip_list::traits
326 typedef GC gc; ///< Garbage collector
327 typedef T value_type; ///< type of value stored in the skip-list
328 typedef Traits traits; ///< Traits template parameter
330 typedef typename traits::hook hook; ///< hook type
331 typedef typename hook::node_type node_type; ///< node type
333 # ifdef CDS_DOXYGEN_INVOKED
334 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
336 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
339 typedef typename traits::disposer disposer; ///< item disposer
340 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
342 typedef typename traits::item_counter item_counter; ///< Item counting policy
343 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
344 typedef typename traits::random_level_generator random_level_generator; ///< random level generator
345 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
346 typedef typename traits::back_off back_off; ///< Back-off strategy
347 typedef typename traits::stat stat; ///< internal statistics type
350 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
352 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
354 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
355 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
357 static unsigned int const c_nMaxHeight = std::conditional<
358 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
359 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
360 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
364 static unsigned int const c_nMinHeight = 5;
368 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
369 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
373 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
375 typedef typename std::conditional<
376 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
377 ,intrusive_node_builder
378 ,typename traits::internal_node_builder
379 >::type node_builder;
381 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
383 // c_nMaxHeight * 2 - pPred/pSucc guards
384 // + 1 - for erase, unlink
386 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
388 node_type * pPrev[ c_nMaxHeight ];
389 node_type * pSucc[ c_nMaxHeight ];
391 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
392 node_type * pCur; // guarded by guards; needed only for \p ensure()
397 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
399 item_counter m_ItemCounter; ///< item counter
400 random_level_generator m_RandomLevelGen; ///< random level generator instance
401 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
402 mutable stat m_Stat; ///< internal statistics
406 unsigned int random_level()
408 // Random generator produces a number from range [0..31]
409 // We need a number from range [1..32]
410 return m_RandomLevelGen() + 1;
413 template <typename Q>
414 node_type * build_node( Q v )
416 return node_builder::make_tower( v, m_RandomLevelGen );
419 static value_type * gc_protect( marked_node_ptr p )
421 return node_traits::to_value_ptr( p.ptr() );
424 static void dispose_node( value_type * pVal )
426 assert( pVal != nullptr );
427 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
431 template <typename Q, typename Compare >
432 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
435 marked_node_ptr pSucc;
436 marked_node_ptr pCur;
438 // Hazard pointer array:
439 // pPred: [nLevel * 2]
440 // pSucc: [nLevel * 2 + 1]
443 pPred = m_Head.head();
446 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
447 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
449 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
451 // pCur.bits() means that pPred is logically deleted
455 if ( pCur.ptr() == nullptr ) {
456 // end of the list at level nLevel - goto next level
460 // pSucc contains deletion mark for pCur
461 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
463 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
466 if ( pSucc.bits() ) {
467 // pCur is marked, i.e. logically deleted.
468 marked_node_ptr p( pCur.ptr() );
469 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
470 memory_model::memory_order_release, atomics::memory_order_relaxed ))
473 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
474 m_Stat.onEraseWhileFind();
480 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
483 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
485 else if ( nCmp == 0 && bStopIfFound )
493 pos.pPrev[ nLevel ] = pPred;
494 pos.pSucc[ nLevel ] = pCur.ptr();
501 pos.pCur = pCur.ptr();
502 return pCur.ptr() && nCmp == 0;
505 bool find_min_position( position& pos )
508 marked_node_ptr pSucc;
509 marked_node_ptr pCur;
511 // Hazard pointer array:
512 // pPred: [nLevel * 2]
513 // pSucc: [nLevel * 2 + 1]
516 pPred = m_Head.head();
518 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
519 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
520 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
522 // pCur.bits() means that pPred is logically deleted
523 // head cannot be deleted
524 assert( pCur.bits() == 0 );
528 // pSucc contains deletion mark for pCur
529 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
531 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
534 if ( pSucc.bits() ) {
535 // pCur is marked, i.e. logically deleted.
536 marked_node_ptr p( pCur.ptr() );
537 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
538 memory_model::memory_order_release, atomics::memory_order_relaxed ))
541 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
548 pos.pPrev[ nLevel ] = pPred;
549 pos.pSucc[ nLevel ] = pCur.ptr();
552 return (pos.pCur = pCur.ptr()) != nullptr;
555 bool find_max_position( position& pos )
558 marked_node_ptr pSucc;
559 marked_node_ptr pCur;
561 // Hazard pointer array:
562 // pPred: [nLevel * 2]
563 // pSucc: [nLevel * 2 + 1]
566 pPred = m_Head.head();
568 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
569 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
571 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
573 // pCur.bits() means that pPred is logically deleted
577 if ( pCur.ptr() == nullptr ) {
578 // end of the list at level nLevel - goto next level
582 // pSucc contains deletion mark for pCur
583 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
585 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
588 if ( pSucc.bits() ) {
589 // pCur is marked, i.e. logically deleted.
590 marked_node_ptr p( pCur.ptr() );
591 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
592 memory_model::memory_order_release, atomics::memory_order_relaxed ))
595 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
604 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
605 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
610 pos.pPrev[ nLevel ] = pPred;
611 pos.pSucc[ nLevel ] = pCur.ptr();
614 return (pos.pCur = pCur.ptr()) != nullptr;
617 template <typename Func>
618 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
620 unsigned int nHeight = pNode->height();
622 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
623 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
626 marked_node_ptr p( pos.pSucc[0] );
627 pNode->next( 0 ).store( p, memory_model::memory_order_release );
628 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
634 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
637 marked_node_ptr q( pos.pSucc[ nLevel ]);
638 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
639 // pNode has been marked as removed while we are inserting it
642 m_Stat.onLogicDeleteWhileInsert();
646 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
649 // Renew insert position
650 m_Stat.onRenewInsertPosition();
651 if ( !find_position( val, pos, key_comparator(), false )) {
652 // The node has been deleted while we are inserting it
653 m_Stat.onNotFoundWhileInsert();
661 template <typename Func>
662 bool try_remove_at( node_type * pDel, position& pos, Func f )
664 assert( pDel != nullptr );
666 marked_node_ptr pSucc;
667 typename gc::Guard gSucc;
669 // logical deletion (marking)
670 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
672 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
673 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
674 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
682 pSucc = gSucc.protect( pDel->next(0), gc_protect );
683 marked_node_ptr p( pSucc.ptr() );
684 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
685 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
687 f( *node_traits::to_value_ptr( pDel ));
692 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
693 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
694 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
695 memory_model::memory_order_release, atomics::memory_order_relaxed) )
698 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
699 m_Stat.onSlowErase();
704 // Fast erasing success
705 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
706 m_Stat.onFastErase();
717 enum finsd_fastpath_result {
719 find_fastpath_not_found,
722 template <typename Q, typename Compare, typename Func>
723 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
726 typename gc::template GuardArray<2> guards;
727 marked_node_ptr pCur;
728 marked_node_ptr pNull;
732 pPred = m_Head.head();
733 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
734 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
738 while ( pCur != pNull ) {
740 unsigned int nAttempt = 0;
741 while ( pCur.bits() && nAttempt++ < 16 ) {
743 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
748 // Maybe, we are on deleted node sequence
749 // Abort searching, try slow-path
750 return find_fastpath_abort;
755 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
759 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
761 else if ( nCmp == 0 ) {
763 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
764 return find_fastpath_found;
766 else // pCur > val - go down
772 return find_fastpath_not_found;
775 template <typename Q, typename Compare, typename Func>
776 bool find_slowpath( Q& val, Compare cmp, Func f )
779 if ( find_position( val, pos, cmp, true )) {
780 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
782 f( *node_traits::to_value_ptr( pos.pCur ), val );
789 template <typename Q, typename Compare, typename Func>
790 bool find_with_( Q& val, Compare cmp, Func f )
792 switch ( find_fastpath( val, cmp, f )) {
793 case find_fastpath_found:
794 m_Stat.onFindFastSuccess();
796 case find_fastpath_not_found:
797 m_Stat.onFindFastFailed();
803 if ( find_slowpath( val, cmp, f )) {
804 m_Stat.onFindSlowSuccess();
808 m_Stat.onFindSlowFailed();
812 template <typename Q, typename Compare>
813 bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp )
815 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } );
818 template <typename Q, typename Compare, typename Func>
819 bool erase_( Q const& val, Compare cmp, Func f )
823 if ( !find_position( val, pos, cmp, false ) ) {
824 m_Stat.onEraseFailed();
828 node_type * pDel = pos.pCur;
829 typename gc::Guard gDel;
830 gDel.assign( node_traits::to_value_ptr(pDel) );
831 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
833 unsigned int nHeight = pDel->height();
834 if ( try_remove_at( pDel, pos, f )) {
836 m_Stat.onRemoveNode( nHeight );
837 m_Stat.onEraseSuccess();
841 m_Stat.onEraseFailed();
845 template <typename Q, typename Compare>
846 bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
851 if ( !find_position( val, pos, cmp, false ) ) {
852 m_Stat.onExtractFailed();
856 node_type * pDel = pos.pCur;
857 guard.assign( 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();
868 m_Stat.onExtractRetry();
872 bool extract_min_( typename gc::Guard& gDel )
877 if ( !find_min_position( pos ) ) {
879 m_Stat.onExtractMinFailed();
883 node_type * pDel = pos.pCur;
885 unsigned int nHeight = pDel->height();
886 gDel.assign( 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 gc::Guard& gDel )
904 if ( !find_max_position( pos ) ) {
906 m_Stat.onExtractMaxFailed();
910 node_type * pDel = pos.pCur;
912 unsigned int nHeight = pDel->height();
913 gDel.assign( node_traits::to_value_ptr(pDel) );
915 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
917 m_Stat.onRemoveNode( nHeight );
918 m_Stat.onExtractMaxSuccess();
922 m_Stat.onExtractMaxRetry();
926 void increase_height( unsigned int nHeight )
928 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
929 if ( nCur < nHeight )
930 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
935 /// Default constructor
937 The constructor checks whether the count of guards is enough
938 for skip-list and may raise an exception if not.
941 : m_Head( c_nMaxHeight )
942 , m_nHeight( c_nMinHeight )
944 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
946 gc::check_available_guards( c_nHazardPtrCount );
948 // Barrier for head node
949 atomics::atomic_thread_fence( memory_model::memory_order_release );
952 /// Clears and destructs the skip-list
960 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
962 /// Const iterator type
963 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
965 /// Returns a forward iterator addressing the first element in a set
968 return iterator( *m_Head.head() );
971 /// Returns a forward const iterator addressing the first element in a set
972 const_iterator begin() const
974 return const_iterator( *m_Head.head() );
976 /// Returns a forward const iterator addressing the first element in a set
977 const_iterator cbegin() const
979 return const_iterator( *m_Head.head() );
982 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
988 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
989 const_iterator end() const
991 return const_iterator();
993 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
994 const_iterator cend() const
996 return const_iterator();
1000 /// Inserts new node
1002 The function inserts \p val in the set if it does not contain
1003 an item with key equal to \p val.
1005 Returns \p true if \p val is placed into the set, \p false otherwise.
1007 bool insert( value_type& val )
1009 return insert( val, []( value_type& ) {} );
1012 /// Inserts new node
1014 This function is intended for derived non-intrusive containers.
1016 The function allows to split creating of new item into two part:
1017 - create item with key only
1018 - insert new item into the set
1019 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1021 The functor signature is:
1023 void func( value_type& val );
1025 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1026 \p val no any other changes could be made on this set's item by concurrent threads.
1027 The user-defined functor is called only if the inserting is success.
1029 template <typename Func>
1030 bool insert( value_type& val, Func f )
1032 typename gc::Guard gNew;
1033 gNew.assign( &val );
1035 node_type * pNode = node_traits::to_node_ptr( val );
1036 scoped_node_ptr scp( pNode );
1037 unsigned int nHeight = pNode->height();
1038 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1039 bool bTowerMade = false;
1044 bool bFound = find_position( val, pos, key_comparator(), true );
1046 // scoped_node_ptr deletes the node tower if we create it
1050 m_Stat.onInsertFailed();
1055 build_node( pNode );
1056 nHeight = pNode->height();
1061 if ( !insert_at_position( val, pNode, pos, f )) {
1062 m_Stat.onInsertRetry();
1066 increase_height( nHeight );
1068 m_Stat.onAddNode( nHeight );
1069 m_Stat.onInsertSuccess();
1075 /// Ensures that the \p val exists in the set
1077 The operation performs inserting or changing data with lock-free manner.
1079 If the item \p val is not found in the set, then \p val is inserted into the set.
1080 Otherwise, the functor \p func is called with item found.
1081 The functor signature is:
1083 void func( bool bNew, value_type& item, value_type& val );
1086 - \p bNew - \p true if the item has been inserted, \p false otherwise
1087 - \p item - item of the set
1088 - \p val - argument \p val passed into the \p ensure function
1089 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1090 refer to the same thing.
1092 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1093 \p second is \p true if new item has been added or \p false if the item with \p key
1094 already is in the set.
1096 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1098 template <typename Func>
1099 std::pair<bool, bool> ensure( value_type& val, Func func )
1101 typename gc::Guard gNew;
1102 gNew.assign( &val );
1104 node_type * pNode = node_traits::to_node_ptr( val );
1105 scoped_node_ptr scp( pNode );
1106 unsigned int nHeight = pNode->height();
1107 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1108 bool bTowerMade = false;
1113 bool bFound = find_position( val, pos, key_comparator(), true );
1115 // scoped_node_ptr deletes the node tower if we create it before
1119 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1120 m_Stat.onEnsureExist();
1121 return std::make_pair( true, false );
1125 build_node( pNode );
1126 nHeight = pNode->height();
1131 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1132 m_Stat.onInsertRetry();
1136 increase_height( nHeight );
1139 m_Stat.onAddNode( nHeight );
1140 m_Stat.onEnsureNew();
1141 return std::make_pair( true, true );
1145 /// Unlinks the item \p val from the set
1147 The function searches the item \p val in the set and unlink it from the set
1148 if it is found and is equal to \p val.
1150 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1151 and deletes the item found. \p %unlink() finds an item by key and deletes it
1152 only if \p val is an item of that set, i.e. the pointer to item found
1153 is equal to <tt> &val </tt>.
1155 The \p disposer specified in \p Traits class template parameter is called
1156 by garbage collector \p GC asynchronously.
1158 The function returns \p true if success and \p false otherwise.
1160 bool unlink( value_type& val )
1164 if ( !find_position( val, pos, key_comparator(), false ) ) {
1165 m_Stat.onUnlinkFailed();
1169 node_type * pDel = pos.pCur;
1170 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1172 unsigned int nHeight = pDel->height();
1173 typename gc::Guard gDel;
1174 gDel.assign( node_traits::to_value_ptr(pDel) );
1176 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1178 m_Stat.onRemoveNode( nHeight );
1179 m_Stat.onUnlinkSuccess();
1183 m_Stat.onUnlinkFailed();
1187 /// Extracts the item from the set with specified \p key
1188 /** \anchor cds_intrusive_SkipListSet_hp_extract
1189 The function searches an item with key equal to \p key in the set,
1190 unlinks it from the set, and returns it in \p dest parameter.
1191 If the item with key equal to \p key is not found the function returns \p false.
1193 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1195 The \ref disposer specified in \p Traits class template parameter is called automatically
1196 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1197 will be destroyed or released.
1198 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1202 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1206 skip_list::guarded_ptr gp;
1207 theList.extract( gp, 5 );
1211 // Destructor of gp releases internal HP guard
1215 template <typename Q>
1216 bool extract( guarded_ptr& dest, Q const& key )
1218 return extract_( dest.guard(), key, key_comparator() );
1221 /// Extracts the item from the set with comparing functor \p pred
1223 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1224 but \p pred predicate is used for key comparing.
1226 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1228 \p pred must imply the same element order as the comparator used for building the set.
1230 template <typename Q, typename Less>
1231 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 )
1332 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1335 /// Deletes the item from the set
1336 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1337 The function searches an item with key equal to \p key in the set,
1338 call \p f functor with item found, unlinks it from the set, and returns \p true.
1339 The \ref disposer specified in \p Traits class template parameter is called
1340 by garbage collector \p GC asynchronously.
1342 The \p Func interface is
1345 void operator()( value_type const& item );
1349 If the item with key equal to \p key is not found the function return \p false.
1351 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1353 template <typename Q, typename Func>
1354 bool erase( Q const& key, Func f )
1356 return erase_( key, key_comparator(), f );
1359 /// Deletes the item from the set with comparing functor \p pred
1361 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1362 but \p pred predicate is used for key comparing.
1364 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1366 \p pred must imply the same element order as the comparator used for building the set.
1368 template <typename Q, typename Less, typename Func>
1369 bool erase_with( Q const& key, Less pred, Func f )
1371 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1375 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1376 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1377 The interface of \p Func functor is:
1380 void operator()( value_type& item, Q& key );
1383 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1385 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1386 that \p item cannot be disposed during functor is executing.
1387 The functor does not serialize simultaneous access to the set \p item. If such access is
1388 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1390 Note the compare functor specified for class \p Traits template parameter
1391 should accept a parameter of type \p Q that can be not the same as \p value_type.
1393 The function returns \p true if \p key is found, \p false otherwise.
1395 template <typename Q, typename Func>
1396 bool find( Q& key, Func f )
1398 return find_with_( key, key_comparator(), f );
1401 template <typename Q, typename Func>
1402 bool find( Q const& key, Func f )
1404 return find_with_( key, key_comparator(), f );
1408 /// Finds the key \p key with \p pred predicate for comparing
1410 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1411 but \p pred is used for key compare.
1413 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1415 \p pred must imply the same element order as the comparator used for building the set.
1417 template <typename Q, typename Less, typename Func>
1418 bool find_with( Q& key, Less pred, Func f )
1420 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1423 template <typename Q, typename Less, typename Func>
1424 bool find_with( Q const& key, Less pred, Func f )
1426 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1431 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1432 The function searches the item with key equal to \p key
1433 and returns \p true if it is found, and \p false otherwise.
1435 Note the compare functor specified for class \p Traits template parameter
1436 should accept a parameter of type \p Q that can be not the same as \p value_type.
1438 template <typename Q>
1439 bool find( Q const& key )
1441 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1444 /// Finds \p key with comparing functor \p pred
1446 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1447 but \p pred is used for comparing the keys.
1448 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1450 \p pred must imply the same element order as the comparator used for building the set.
1452 template <typename Q, typename Less>
1453 bool find_with( Q const& key, Less pred )
1455 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1458 /// Finds \p key and return the item found
1459 /** \anchor cds_intrusive_SkipListSet_hp_get
1460 The function searches the item with key equal to \p key
1461 and assigns the item found to guarded pointer \p ptr.
1462 The function returns \p true if \p key is found, and \p false otherwise.
1463 If \p key is not found the \p ptr parameter is not changed.
1465 The \ref disposer specified in \p Traits class template parameter is called
1466 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1467 will be destroyed or released.
1468 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1472 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1476 skip_list::guarded_ptr gp;
1477 if ( theList.get( gp, 5 )) {
1481 // Destructor of guarded_ptr releases internal HP guard
1485 Note the compare functor specified for class \p Traits template parameter
1486 should accept a parameter of type \p Q that can be not the same as \p value_type.
1488 template <typename Q>
1489 bool get( guarded_ptr& ptr, Q const& key )
1491 return get_with_( ptr.guard(), key, key_comparator() );
1494 /// Finds \p key and return the item found
1496 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1497 but \p pred is used for comparing the keys.
1499 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1501 \p pred must imply the same element order as the comparator used for building the set.
1503 template <typename Q, typename Less>
1504 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
1506 return get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1509 /// Returns item count in the set
1511 The value returned depends on item counter type provided by \p Traits template parameter.
1512 If it is \p atomicity::empty_item_counter this function always returns 0.
1513 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1518 return m_ItemCounter;
1521 /// Checks if the set is empty
1524 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1527 /// Clears the set (not atomic)
1529 The function unlink all items from the set.
1530 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1534 assert( set.empty() );
1536 the assertion could be raised.
1538 For each item the \ref disposer will be called after unlinking.
1543 while ( extract_min( gp ));
1546 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1547 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1549 return c_nMaxHeight;
1552 /// Returns const reference to internal statistics
1553 stat const& statistics() const
1559 }} // namespace cds::intrusive
1562 #endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H