3 #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
4 #define CDSLIB_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::intrusive::skip_list::implementation_tag implementation_tag;
352 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
354 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
356 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
357 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
359 static unsigned int const c_nMaxHeight = std::conditional<
360 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
361 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
362 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
366 static unsigned int const c_nMinHeight = 5;
370 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
371 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
375 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
377 typedef typename std::conditional<
378 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
379 ,intrusive_node_builder
380 ,typename traits::internal_node_builder
381 >::type node_builder;
383 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
385 // c_nMaxHeight * 2 - pPred/pSucc guards
386 // + 1 - for erase, unlink
388 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
390 node_type * pPrev[ c_nMaxHeight ];
391 node_type * pSucc[ c_nMaxHeight ];
393 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
394 node_type * pCur; // guarded by guards; needed only for \p update()
399 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
401 item_counter m_ItemCounter; ///< item counter
402 random_level_generator m_RandomLevelGen; ///< random level generator instance
403 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
404 mutable stat m_Stat; ///< internal statistics
408 unsigned int random_level()
410 // Random generator produces a number from range [0..31]
411 // We need a number from range [1..32]
412 return m_RandomLevelGen() + 1;
415 template <typename Q>
416 node_type * build_node( Q v )
418 return node_builder::make_tower( v, m_RandomLevelGen );
421 static value_type * gc_protect( marked_node_ptr p )
423 return node_traits::to_value_ptr( p.ptr() );
426 static void dispose_node( value_type * pVal )
428 assert( pVal != nullptr );
429 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
433 template <typename Q, typename Compare >
434 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
437 marked_node_ptr pSucc;
438 marked_node_ptr pCur;
440 // Hazard pointer array:
441 // pPred: [nLevel * 2]
442 // pSucc: [nLevel * 2 + 1]
445 pPred = m_Head.head();
448 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
449 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
451 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
453 // pCur.bits() means that pPred is logically deleted
457 if ( pCur.ptr() == nullptr ) {
458 // end of the list at level nLevel - goto next level
462 // pSucc contains deletion mark for pCur
463 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
465 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
468 if ( pSucc.bits() ) {
469 // pCur is marked, i.e. logically deleted.
470 marked_node_ptr p( pCur.ptr() );
471 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
472 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
475 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
476 m_Stat.onEraseWhileFind();
482 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
485 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
487 else if ( nCmp == 0 && bStopIfFound )
495 pos.pPrev[ nLevel ] = pPred;
496 pos.pSucc[ nLevel ] = pCur.ptr();
503 pos.pCur = pCur.ptr();
504 return pCur.ptr() && nCmp == 0;
507 bool find_min_position( position& pos )
510 marked_node_ptr pSucc;
511 marked_node_ptr pCur;
513 // Hazard pointer array:
514 // pPred: [nLevel * 2]
515 // pSucc: [nLevel * 2 + 1]
518 pPred = m_Head.head();
520 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
521 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
522 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
524 // pCur.bits() means that pPred is logically deleted
525 // head cannot be deleted
526 assert( pCur.bits() == 0 );
530 // pSucc contains deletion mark for pCur
531 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
533 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
536 if ( pSucc.bits() ) {
537 // pCur is marked, i.e. logically deleted.
538 marked_node_ptr p( pCur.ptr() );
539 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
540 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
543 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
544 m_Stat.onEraseWhileFind();
552 pos.pPrev[ nLevel ] = pPred;
553 pos.pSucc[ nLevel ] = pCur.ptr();
556 return (pos.pCur = pCur.ptr()) != nullptr;
559 bool find_max_position( position& pos )
562 marked_node_ptr pSucc;
563 marked_node_ptr pCur;
565 // Hazard pointer array:
566 // pPred: [nLevel * 2]
567 // pSucc: [nLevel * 2 + 1]
570 pPred = m_Head.head();
572 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
573 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
575 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
577 // pCur.bits() means that pPred is logically deleted
581 if ( pCur.ptr() == nullptr ) {
582 // end of the list at level nLevel - goto next level
586 // pSucc contains deletion mark for pCur
587 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
589 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
592 if ( pSucc.bits() ) {
593 // pCur is marked, i.e. logically deleted.
594 marked_node_ptr p( pCur.ptr() );
595 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
596 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
599 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
600 m_Stat.onEraseWhileFind();
610 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
611 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
616 pos.pPrev[ nLevel ] = pPred;
617 pos.pSucc[ nLevel ] = pCur.ptr();
620 return (pos.pCur = pCur.ptr()) != nullptr;
623 template <typename Func>
624 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
626 unsigned int nHeight = pNode->height();
628 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
629 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
633 marked_node_ptr p( pos.pSucc[0] );
634 pNode->next( 0 ).store( p, memory_model::memory_order_release );
635 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ))
641 // Insert at level 1..max
642 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
645 marked_node_ptr q( pos.pSucc[ nLevel ]);
646 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
647 // pNode has been marked as removed while we are inserting it
650 m_Stat.onLogicDeleteWhileInsert();
654 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
657 // Renew insert position
658 m_Stat.onRenewInsertPosition();
659 if ( !find_position( val, pos, key_comparator(), false )) {
660 // The node has been deleted while we are inserting it
661 m_Stat.onNotFoundWhileInsert();
669 template <typename Func>
670 bool try_remove_at( node_type * pDel, position& pos, Func f )
672 assert( pDel != nullptr );
674 marked_node_ptr pSucc;
676 // logical deletion (marking)
677 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
679 pSucc = pDel->next(nLevel);
680 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
681 memory_model::memory_order_release, atomics::memory_order_relaxed ))
689 marked_node_ptr p( pDel->next(0).load(memory_model::memory_order_relaxed).ptr() );
690 if ( pDel->next(0).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_relaxed ))
692 f( *node_traits::to_value_ptr( pDel ));
697 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
698 pSucc = pDel->next(nLevel).load(memory_model::memory_order_relaxed);
699 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
700 memory_model::memory_order_acquire, atomics::memory_order_relaxed) )
703 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
704 m_Stat.onSlowErase();
709 // Fast erasing success
710 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
711 m_Stat.onFastErase();
716 // Another thread is deleting pDel right now
720 m_Stat.onEraseRetry();
724 enum finsd_fastpath_result {
726 find_fastpath_not_found,
729 template <typename Q, typename Compare, typename Func>
730 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
733 typename gc::template GuardArray<2> guards;
734 marked_node_ptr pCur;
735 marked_node_ptr pNull;
739 pPred = m_Head.head();
740 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
741 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
745 while ( pCur != pNull ) {
747 unsigned int nAttempt = 0;
748 while ( pCur.bits() && nAttempt++ < 16 ) {
750 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
755 // Maybe, we are on deleted node sequence
756 // Abort searching, try slow-path
757 return find_fastpath_abort;
762 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
766 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
768 else if ( nCmp == 0 ) {
770 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
771 return find_fastpath_found;
773 else // pCur > val - go down
779 return find_fastpath_not_found;
782 template <typename Q, typename Compare, typename Func>
783 bool find_slowpath( Q& val, Compare cmp, Func f )
786 if ( find_position( val, pos, cmp, true )) {
787 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
789 f( *node_traits::to_value_ptr( pos.pCur ), val );
796 template <typename Q, typename Compare, typename Func>
797 bool find_with_( Q& val, Compare cmp, Func f )
799 switch ( find_fastpath( val, cmp, f )) {
800 case find_fastpath_found:
801 m_Stat.onFindFastSuccess();
803 case find_fastpath_not_found:
804 m_Stat.onFindFastFailed();
810 if ( find_slowpath( val, cmp, f )) {
811 m_Stat.onFindSlowSuccess();
815 m_Stat.onFindSlowFailed();
819 template <typename Q, typename Compare>
820 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
822 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
825 template <typename Q, typename Compare, typename Func>
826 bool erase_( Q const& val, Compare cmp, Func f )
830 if ( !find_position( val, pos, cmp, false ) ) {
831 m_Stat.onEraseFailed();
835 node_type * pDel = pos.pCur;
836 typename gc::Guard gDel;
837 gDel.assign( node_traits::to_value_ptr(pDel) );
838 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
840 unsigned int nHeight = pDel->height();
841 if ( try_remove_at( pDel, pos, f )) {
843 m_Stat.onRemoveNode( nHeight );
844 m_Stat.onEraseSuccess();
848 m_Stat.onEraseFailed();
852 template <typename Q, typename Compare>
853 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
858 if ( !find_position( val, pos, cmp, false ) ) {
859 m_Stat.onExtractFailed();
864 node_type * pDel = pos.pCur;
865 guard.set( node_traits::to_value_ptr(pDel));
866 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
868 unsigned int nHeight = pDel->height();
869 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
871 m_Stat.onRemoveNode( nHeight );
872 m_Stat.onExtractSuccess();
875 m_Stat.onExtractRetry();
879 bool extract_min_( typename guarded_ptr::native_guard& gDel )
884 if ( !find_min_position( pos ) ) {
886 m_Stat.onExtractMinFailed();
891 node_type * pDel = pos.pCur;
893 unsigned int nHeight = pDel->height();
894 gDel.set( node_traits::to_value_ptr(pDel) );
896 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
898 m_Stat.onRemoveNode( nHeight );
899 m_Stat.onExtractMinSuccess();
903 m_Stat.onExtractMinRetry();
907 bool extract_max_( typename guarded_ptr::native_guard& gDel )
912 if ( !find_max_position( pos ) ) {
914 m_Stat.onExtractMaxFailed();
919 node_type * pDel = pos.pCur;
921 unsigned int nHeight = pDel->height();
922 gDel.set( node_traits::to_value_ptr(pDel) );
924 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
926 m_Stat.onRemoveNode( nHeight );
927 m_Stat.onExtractMaxSuccess();
931 m_Stat.onExtractMaxRetry();
935 void increase_height( unsigned int nHeight )
937 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
938 if ( nCur < nHeight )
939 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
944 /// Default constructor
946 The constructor checks whether the count of guards is enough
947 for skip-list and may raise an exception if not.
950 : m_Head( c_nMaxHeight )
951 , m_nHeight( c_nMinHeight )
953 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
955 gc::check_available_guards( c_nHazardPtrCount );
957 // Barrier for head node
958 atomics::atomic_thread_fence( memory_model::memory_order_release );
961 /// Clears and destructs the skip-list
969 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
971 /// Const iterator type
972 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
974 /// Returns a forward iterator addressing the first element in a set
977 return iterator( *m_Head.head() );
980 /// Returns a forward const iterator addressing the first element in a set
981 const_iterator begin() const
983 return const_iterator( *m_Head.head() );
985 /// Returns a forward const iterator addressing the first element in a set
986 const_iterator cbegin() const
988 return const_iterator( *m_Head.head() );
991 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
997 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
998 const_iterator end() const
1000 return const_iterator();
1002 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1003 const_iterator cend() const
1005 return const_iterator();
1009 /// Inserts new node
1011 The function inserts \p val in the set if it does not contain
1012 an item with key equal to \p val.
1014 Returns \p true if \p val is placed into the set, \p false otherwise.
1016 bool insert( value_type& val )
1018 return insert( val, []( value_type& ) {} );
1021 /// Inserts new node
1023 This function is intended for derived non-intrusive containers.
1025 The function allows to split creating of new item into two part:
1026 - create item with key only
1027 - insert new item into the set
1028 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1030 The functor signature is:
1032 void func( value_type& val );
1034 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1035 \p val no any other changes could be made on this set's item by concurrent threads.
1036 The user-defined functor is called only if the inserting is success.
1038 template <typename Func>
1039 bool insert( value_type& val, Func f )
1041 typename gc::Guard gNew;
1042 gNew.assign( &val );
1044 node_type * pNode = node_traits::to_node_ptr( val );
1045 scoped_node_ptr scp( pNode );
1046 unsigned int nHeight = pNode->height();
1047 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1048 bool bTowerMade = false;
1053 if ( find_position( val, pos, key_comparator(), true )) {
1054 // scoped_node_ptr deletes the node tower if we create it
1058 m_Stat.onInsertFailed();
1063 build_node( pNode );
1064 nHeight = pNode->height();
1069 if ( !insert_at_position( val, pNode, pos, f )) {
1070 m_Stat.onInsertRetry();
1074 increase_height( nHeight );
1076 m_Stat.onAddNode( nHeight );
1077 m_Stat.onInsertSuccess();
1083 /// Updates the node
1085 The operation performs inserting or changing data with lock-free manner.
1087 If the item \p val is not found in the set, then \p val is inserted into the set
1088 iff \p bInsert is \p true.
1089 Otherwise, the functor \p func is called with item found.
1090 The functor \p func signature is:
1092 void func( bool bNew, value_type& item, value_type& val );
1095 - \p bNew - \p true if the item has been inserted, \p false otherwise
1096 - \p item - item of the set
1097 - \p val - argument \p val passed into the \p %update() function
1098 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1099 refer to the same thing.
1101 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1102 i.e. the node has been inserted or updated,
1103 \p second is \p true if new item has been added or \p false if the item with \p key
1106 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1108 template <typename Func>
1109 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
1111 typename gc::Guard gNew;
1112 gNew.assign( &val );
1114 node_type * pNode = node_traits::to_node_ptr( val );
1115 scoped_node_ptr scp( pNode );
1116 unsigned int nHeight = pNode->height();
1117 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1118 bool bTowerMade = false;
1123 bool bFound = find_position( val, pos, key_comparator(), true );
1125 // scoped_node_ptr deletes the node tower if we create it before
1129 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1130 m_Stat.onUpdateExist();
1131 return std::make_pair( true, false );
1136 return std::make_pair( false, false );
1140 build_node( pNode );
1141 nHeight = pNode->height();
1146 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1147 m_Stat.onInsertRetry();
1151 increase_height( nHeight );
1154 m_Stat.onAddNode( nHeight );
1155 m_Stat.onUpdateNew();
1156 return std::make_pair( true, true );
1161 // Deprecated, use update() instead
1162 template <typename Func>
1163 std::pair<bool, bool> ensure( value_type& val, Func func )
1165 return update( val, func, true );
1169 /// Unlinks the item \p val from the set
1171 The function searches the item \p val in the set and unlink it from the set
1172 if it is found and is equal to \p val.
1174 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1175 and deletes the item found. \p %unlink() finds an item by key and deletes it
1176 only if \p val is an item of that set, i.e. the pointer to item found
1177 is equal to <tt> &val </tt>.
1179 The \p disposer specified in \p Traits class template parameter is called
1180 by garbage collector \p GC asynchronously.
1182 The function returns \p true if success and \p false otherwise.
1184 bool unlink( value_type& val )
1188 if ( !find_position( val, pos, key_comparator(), false ) ) {
1189 m_Stat.onUnlinkFailed();
1193 node_type * pDel = pos.pCur;
1194 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1196 unsigned int nHeight = pDel->height();
1197 typename gc::Guard gDel;
1198 gDel.assign( node_traits::to_value_ptr(pDel) );
1200 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1202 m_Stat.onRemoveNode( nHeight );
1203 m_Stat.onUnlinkSuccess();
1207 m_Stat.onUnlinkFailed();
1211 /// Extracts the item from the set with specified \p key
1212 /** \anchor cds_intrusive_SkipListSet_hp_extract
1213 The function searches an item with key equal to \p key in the set,
1214 unlinks it from the set, and returns it as \p guarded_ptr object.
1215 If \p key is not found the function returns an empty guarded pointer.
1217 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1219 The \p disposer specified in \p Traits class template parameter is called automatically
1220 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1221 will be destroyed or released.
1222 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1226 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1230 skip_list::guarded_ptr gp(theList.extract( 5 ));
1235 // Destructor of gp releases internal HP guard
1239 template <typename Q>
1240 guarded_ptr extract( Q const& key )
1243 extract_( gp.guard(), key, key_comparator() );
1247 /// Extracts the item from the set with comparing functor \p pred
1249 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1250 but \p pred predicate is used for key comparing.
1252 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1254 \p pred must imply the same element order as the comparator used for building the set.
1256 template <typename Q, typename Less>
1257 guarded_ptr extract_with( Q const& key, Less pred )
1261 extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1265 /// Extracts an item with minimal key from the list
1267 The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
1268 If the skip-list is empty the function returns an empty guarded pointer.
1270 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1271 It means that the function gets leftmost item and tries to unlink it.
1272 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1273 So, the function returns the item with minimum key at the moment of list traversing.
1275 The \p disposer specified in \p Traits class template parameter is called
1276 by garbage collector \p GC automatically when returned \p guarded_ptr object
1277 will be destroyed or released.
1278 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1282 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1286 skip_list::guarded_ptr gp(theList.extract_min());
1291 // Destructor of gp releases internal HP guard
1295 guarded_ptr extract_min()
1298 extract_min_( gp.guard() );
1302 /// Extracts an item with maximal key from the list
1304 The function searches an item with maximal key, unlinks it, and returns the pointer to item
1305 as \p guarded_ptr object.
1306 If the skip-list is empty the function returns an empty \p guarded_ptr.
1308 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1309 It means that the function gets rightmost item and tries to unlink it.
1310 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1311 So, the function returns the item with maximum key at the moment of list traversing.
1313 The \p disposer specified in \p Traits class template parameter is called
1314 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1315 will be destroyed or released.
1316 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1320 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1324 skip_list::guarded_ptr gp( theList.extract_max( gp ));
1329 // Destructor of gp releases internal HP guard
1333 guarded_ptr extract_max()
1336 extract_max_( gp.guard() );
1340 /// Deletes the item from the set
1341 /** \anchor cds_intrusive_SkipListSet_hp_erase
1342 The function searches an item with key equal to \p key in the set,
1343 unlinks it from the set, and returns \p true.
1344 If the item with key equal to \p key is not found the function return \p false.
1346 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1348 template <typename Q>
1349 bool erase( Q const& key )
1351 return erase_( key, key_comparator(), [](value_type const&) {} );
1354 /// Deletes the item from the set with comparing functor \p pred
1356 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1357 but \p pred predicate is used for key comparing.
1359 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1361 \p pred must imply the same element order as the comparator used for building the set.
1363 template <typename Q, typename Less>
1364 bool erase_with( Q const& key, Less pred )
1367 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1370 /// Deletes the item from the set
1371 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1372 The function searches an item with key equal to \p key in the set,
1373 call \p f functor with item found, unlinks it from the set, and returns \p true.
1374 The \ref disposer specified in \p Traits class template parameter is called
1375 by garbage collector \p GC asynchronously.
1377 The \p Func interface is
1380 void operator()( value_type const& item );
1384 If the item with key equal to \p key is not found the function return \p false.
1386 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1388 template <typename Q, typename Func>
1389 bool erase( Q const& key, Func f )
1391 return erase_( key, key_comparator(), f );
1394 /// Deletes the item from the set with comparing functor \p pred
1396 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1397 but \p pred predicate is used for key comparing.
1399 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1401 \p pred must imply the same element order as the comparator used for building the set.
1403 template <typename Q, typename Less, typename Func>
1404 bool erase_with( Q const& key, Less pred, Func f )
1407 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1411 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1412 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1413 The interface of \p Func functor is:
1416 void operator()( value_type& item, Q& key );
1419 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1421 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1422 that \p item cannot be disposed during functor is executing.
1423 The functor does not serialize simultaneous access to the set \p item. If such access is
1424 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1426 Note the compare functor specified for class \p Traits template parameter
1427 should accept a parameter of type \p Q that can be not the same as \p value_type.
1429 The function returns \p true if \p key is found, \p false otherwise.
1431 template <typename Q, typename Func>
1432 bool find( Q& key, Func f )
1434 return find_with_( key, key_comparator(), f );
1437 template <typename Q, typename Func>
1438 bool find( Q const& key, Func f )
1440 return find_with_( key, key_comparator(), f );
1444 /// Finds the key \p key with \p pred predicate for comparing
1446 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1447 but \p pred is used for key compare.
1449 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1451 \p pred must imply the same element order as the comparator used for building the set.
1453 template <typename Q, typename Less, typename Func>
1454 bool find_with( Q& key, Less pred, Func f )
1457 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1460 template <typename Q, typename Less, typename Func>
1461 bool find_with( Q const& key, Less pred, Func f )
1464 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1469 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1470 The function searches the item with key equal to \p key
1471 and returns \p true if it is found, and \p false otherwise.
1473 Note the compare functor specified for class \p Traits template parameter
1474 should accept a parameter of type \p Q that can be not the same as \p value_type.
1476 template <typename Q>
1477 bool find( Q const& key )
1479 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1482 /// Finds \p key with comparing functor \p pred
1484 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1485 but \p pred is used for comparing the keys.
1486 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1488 \p pred must imply the same element order as the comparator used for building the set.
1490 template <typename Q, typename Less>
1491 bool find_with( Q const& key, Less pred )
1494 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1497 /// Finds \p key and return the item found
1498 /** \anchor cds_intrusive_SkipListSet_hp_get
1499 The function searches the item with key equal to \p key
1500 and returns the pointer to the item found as \p guarded_ptr.
1501 If \p key is not found the function returns an empt guarded pointer.
1503 The \p disposer specified in \p Traits class template parameter is called
1504 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1505 will be destroyed or released.
1506 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1510 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1514 skip_list::guarded_ptr gp(theList.get( 5 ));
1519 // Destructor of guarded_ptr releases internal HP guard
1523 Note the compare functor specified for class \p Traits template parameter
1524 should accept a parameter of type \p Q that can be not the same as \p value_type.
1526 template <typename Q>
1527 guarded_ptr get( Q const& key )
1530 get_with_( gp.guard(), key, key_comparator() );
1534 /// Finds \p key and return the item found
1536 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1537 but \p pred is used for comparing the keys.
1539 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1541 \p pred must imply the same element order as the comparator used for building the set.
1543 template <typename Q, typename Less>
1544 guarded_ptr get_with( Q const& key, Less pred )
1548 get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1552 /// Returns item count in the set
1554 The value returned depends on item counter type provided by \p Traits template parameter.
1555 If it is \p atomicity::empty_item_counter this function always returns 0.
1556 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1561 return m_ItemCounter;
1564 /// Checks if the set is empty
1567 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1570 /// Clears the set (not atomic)
1572 The function unlink all items from the set.
1573 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1577 assert( set.empty() );
1579 the assertion could be raised.
1581 For each item the \ref disposer will be called after unlinking.
1586 while ( extract_min_( gp.guard() ));
1589 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1590 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1592 return c_nMaxHeight;
1595 /// Returns const reference to internal statistics
1596 stat const& statistics() const
1602 }} // namespace cds::intrusive
1605 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H