3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
4 #define __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
8 #include <cds/intrusive/skip_list_base.h>
9 #include <cds/opt/compare.h>
11 #include <cds/details/binary_functor_wrapper.h>
12 #include <cds/gc/guarded_ptr.h>
14 namespace cds { namespace intrusive {
17 namespace skip_list { namespace details {
19 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
23 typedef NodeTraits node_traits;
24 typedef BackOff back_off;
25 typedef typename node_traits::node_type node_type;
26 typedef typename node_traits::value_type value_type;
27 static bool const c_isConst = IsConst;
29 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
32 typedef typename node_type::marked_ptr marked_ptr;
33 typedef typename node_type::atomic_marked_ptr atomic_marked_ptr;
35 typename gc::Guard m_guard;
39 static value_type * gc_protect( marked_ptr p )
41 return node_traits::to_value_ptr( p.ptr() );
51 if ( m_pNode->next( m_pNode->height() - 1 ).load( CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::memory_order_acquire ).bits() ) {
106 iterator( iterator const& s)
107 : m_pNode( s.m_pNode )
109 m_guard.assign( node_traits::to_value_ptr(m_pNode) );
112 value_type * operator ->() const
114 assert( m_pNode != nullptr );
115 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
117 return node_traits::to_value_ptr( m_pNode );
120 value_ref operator *() const
122 assert( m_pNode != nullptr );
123 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
125 return *node_traits::to_value_ptr( m_pNode );
129 iterator& operator ++()
135 iterator& operator = (const iterator& src)
137 m_pNode = src.m_pNode;
138 m_guard.copy( src.m_guard );
142 template <typename Bkoff, bool C>
143 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
145 return m_pNode == i.m_pNode;
147 template <typename Bkoff, bool C>
148 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
150 return !( *this == i );
153 }} // namespace skip_list::details
156 /// Lock-free skip-list set
157 /** @ingroup cds_intrusive_map
158 @anchor cds_intrusive_SkipListSet_hp
160 The implementation of well-known probabilistic data structure called skip-list
161 invented by W.Pugh in his papers:
162 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
163 - [1990] W.Pugh A Skip List Cookbook
165 A skip-list is a probabilistic data structure that provides expected logarithmic
166 time search without the need of rebalance. The skip-list is a collection of sorted
167 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
168 Each list has a level, ranging from 0 to 32. The bottom-level list contains
169 all the nodes, and each higher-level list is a sublist of the lower-level lists.
170 Each node is created with a random top level (with a random height), and belongs
171 to all lists up to that level. The probability that a node has the height 1 is 1/2.
172 The probability that a node has the height N is 1/2 ** N (more precisely,
173 the distribution depends on an random generator provided, but our generators
176 The lock-free variant of skip-list is implemented according to book
177 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
178 chapter 14.4 "A Lock-Free Concurrent Skiplist".
179 \note The algorithm described in this book cannot be directly adapted for C++ (roughly speaking,
180 the algo contains a lot of bugs). The \b libcds implementation applies the approach discovered
181 by M.Michael in his \ref cds_intrusive_MichaelList_hp "lock-free linked list".
183 <b>Template arguments</b>:
184 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see skip_list::node).
185 - \p T - type to be stored in the list. The type must be based on skip_list::node (for skip_list::base_hook)
186 or it must have a member of type skip_list::node (for skip_list::member_hook).
187 - \p Traits - type traits. See skip_list::type_traits for explanation.
189 It is possible to declare option-based list with cds::intrusive::skip_list::make_traits metafunction istead of \p Traits template
191 Template argument list \p Options of cds::intrusive::skip_list::make_traits metafunction are:
192 - opt::hook - hook used. Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
193 If the option is not specified, <tt>skip_list::base_hook<></tt> and gc::HP is used.
194 - opt::compare - key comparison functor. No default functor is provided.
195 If the option is not specified, the opt::less is used.
196 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
197 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
198 of GC schema the disposer may be called asynchronously.
199 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
200 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
201 or opt::v::sequential_consistent (sequentially consisnent memory model).
202 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
203 user-provided one. See skip_list::random_level_generator option description for explanation.
204 Default is \p %skip_list::turbo_pascal.
205 - opt::allocator - although the skip-list is an intrusive container,
206 an allocator should be provided to maintain variable randomly-calculated height of the node
207 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
208 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
209 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
210 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
212 \warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
213 the guard count is limited (like as gc::HP, gc::HRC). Those GCs should be explicitly initialized with
214 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
215 when you try to create skip-list object.
217 \note There are several specializations of \p %SkipListSet for each \p GC. You should include:
218 - <tt><cds/intrusive/skip_list_hp.h></tt> for gc::HP garbage collector
219 - <tt><cds/intrusive/skip_list_hrc.h></tt> for gc::HRC garbage collector
220 - <tt><cds/intrusive/skip_list_ptb.h></tt> for gc::PTB garbage collector
221 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for persistent set
222 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
226 The class supports a forward iterator (\ref iterator and \ref const_iterator).
227 The iteration is ordered.
228 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
229 so, the element cannot be reclaimed while the iterator object is alive.
230 However, passing an iterator object between threads is dangerous.
232 \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
233 all elements in the set: any concurrent deletion can exclude the element
234 pointed by the iterator from the set, and your iteration can be terminated
235 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
237 Remember, each iterator object requires 2 additional hazard pointers, that may be
238 a limited resource for \p GC like as gc::HP and gc::HRC (for gc::PTB the count of
239 guards is unlimited).
241 The iterator class supports the following minimalistic interface:
248 iterator( iterator const& s);
250 value_type * operator ->() const;
251 value_type& operator *() const;
254 iterator& operator ++();
257 iterator& operator = (const iterator& src);
259 bool operator ==(iterator const& i ) const;
260 bool operator !=(iterator const& i ) const;
263 Note, the iterator object returned by \ref end, \p cend member functions points to \p NULL and should not be dereferenced.
267 You should incorporate skip_list::node into your struct \p T and provide
268 appropriate skip_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
269 define a struct based on skip_list::type_traits.
271 Example for gc::HP and base hook:
273 // Include GC-related skip-list specialization
274 #include <cds/intrusive/skip_list_hp.h>
276 // Data stored in skip list
277 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
286 // my_data compare functor
288 int operator()( const my_data& d1, const my_data& d2 )
290 return d1.strKey.compare( d2.strKey );
293 int operator()( const my_data& d, const std::string& s )
295 return d.strKey.compare(s);
298 int operator()( const std::string& s, const my_data& d )
300 return s.compare( d.strKey );
305 // Declare type_traits
306 struct my_traits: public cds::intrusive::skip_list::type_traits
308 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
309 typedef my_data_cmp compare;
312 // Declare skip-list set type
313 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
316 Equivalent option-based code:
318 // GC-related specialization
319 #include <cds/intrusive/skip_list_hp.h>
328 // Declare option-based skip-list set
329 typedef cds::intrusive::SkipListSet< cds::gc::HP
331 , typename cds::intrusive::skip_list::make_traits<
332 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
333 ,cds::intrusive::opt::compare< my_data_cmp >
342 #ifdef CDS_DOXYGEN_INVOKED
343 ,typename Traits = skip_list::type_traits
351 typedef T value_type ; ///< type of value stored in the skip-list
352 typedef Traits options ; ///< Traits template parameter
354 typedef typename options::hook hook ; ///< hook type
355 typedef typename hook::node_type node_type ; ///< node type
357 # ifdef CDS_DOXYGEN_INVOKED
358 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
360 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
363 typedef typename options::disposer disposer ; ///< disposer used
364 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
366 typedef GC gc ; ///< Garbage collector
367 typedef typename options::item_counter item_counter ; ///< Item counting policy used
368 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
369 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
370 typedef typename options::allocator allocator_type ; ///< allocator for maintaining array of next pointers of the node
371 typedef typename options::back_off back_off ; ///< Back-off strategy
372 typedef typename options::stat stat ; ///< internal statistics type
375 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
377 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
379 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
380 but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
382 static unsigned int const c_nMaxHeight = std::conditional<
383 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
384 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
385 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
389 static unsigned int const c_nMinHeight = 5;
393 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic marked node pointer
394 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
398 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
400 typedef typename std::conditional<
401 std::is_same< typename options::internal_node_builder, cds::opt::none >::value
402 ,intrusive_node_builder
403 ,typename options::internal_node_builder
404 >::type node_builder;
406 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
408 // c_nMaxHeight * 2 - pPred/pSucc guards
409 // + 1 - for erase, unlink
411 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
413 node_type * pPrev[ c_nMaxHeight ];
414 node_type * pSucc[ c_nMaxHeight ];
416 typename gc::template GuardArray< c_nMaxHeight * 2 > guards ; ///< Guards array for pPrev/pSucc
418 node_type * pCur ; // guarded by guards; needed only for *ensure* function
421 # ifndef CDS_CXX11_LAMBDA_SUPPORT
422 struct empty_insert_functor {
423 void operator()( value_type& )
427 struct empty_erase_functor {
428 void operator()( value_type const& )
432 struct empty_find_functor {
433 template <typename Q>
434 void operator()( value_type& item, Q& val )
439 typename gc::Guard& m_guard;
441 get_functor( typename gc::Guard& gp )
445 template <typename Q>
446 void operator()( value_type& item, Q& val )
448 m_guard.assign( &item );
452 template <typename Func>
453 struct insert_at_ensure_functor {
455 insert_at_ensure_functor( Func f ) : m_func(f) {}
457 void operator()( value_type& item )
459 cds::unref( m_func)( true, item, item );
463 struct copy_value_functor {
464 template <typename Q>
465 void operator()( Q& dest, value_type const& src ) const
471 struct dummy_copy_functor {
472 template <typename Q>
473 void operator()( Q&, value_type const&) const {}
475 # endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
480 skip_list::details::head_node< node_type > m_Head ; ///< head tower (max height)
482 item_counter m_ItemCounter ; ///< item counter
483 random_level_generator m_RandomLevelGen ; ///< random level generator instance
484 CDS_ATOMIC::atomic<unsigned int> m_nHeight ; ///< estimated high level
485 mutable stat m_Stat ; ///< internal statistics
489 unsigned int random_level()
491 // Random generator produces a number from range [0..31]
492 // We need a number from range [1..32]
493 return m_RandomLevelGen() + 1;
496 template <typename Q>
497 node_type * build_node( Q v )
499 return node_builder::make_tower( v, m_RandomLevelGen );
502 static value_type * gc_protect( marked_node_ptr p )
504 return node_traits::to_value_ptr( p.ptr() );
507 static void dispose_node( value_type * pVal )
509 assert( pVal != nullptr );
510 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
514 template <typename Q, typename Compare >
515 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
518 marked_node_ptr pSucc;
519 marked_node_ptr pCur;
521 // Hazard pointer array:
522 // pPred: [nLevel * 2]
523 // pSucc: [nLevel * 2 + 1]
526 pPred = m_Head.head();
529 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
530 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
532 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
534 // pCur.bits() means that pPred is logically deleted
538 if ( pCur.ptr() == nullptr ) {
539 // end of the list at level nLevel - goto next level
543 // pSucc contains deletion mark for pCur
544 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
546 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
549 if ( pSucc.bits() ) {
550 // pCur is marked, i.e. logically deleted.
551 marked_node_ptr p( pCur.ptr() );
552 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
553 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
556 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
557 m_Stat.onEraseWhileFind();
563 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
566 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
568 else if ( nCmp == 0 && bStopIfFound )
576 pos.pPrev[ nLevel ] = pPred;
577 pos.pSucc[ nLevel ] = pCur.ptr();
584 pos.pCur = pCur.ptr();
585 return pCur.ptr() && nCmp == 0;
588 bool find_min_position( position& pos )
591 marked_node_ptr pSucc;
592 marked_node_ptr pCur;
594 // Hazard pointer array:
595 // pPred: [nLevel * 2]
596 // pSucc: [nLevel * 2 + 1]
599 pPred = m_Head.head();
601 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
602 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
603 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
605 // pCur.bits() means that pPred is logically deleted
606 // head cannot be deleted
607 assert( pCur.bits() == 0 );
611 // pSucc contains deletion mark for pCur
612 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
614 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
617 if ( pSucc.bits() ) {
618 // pCur is marked, i.e. logically deleted.
619 marked_node_ptr p( pCur.ptr() );
620 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
621 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
624 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
631 pos.pPrev[ nLevel ] = pPred;
632 pos.pSucc[ nLevel ] = pCur.ptr();
635 return (pos.pCur = pCur.ptr()) != nullptr;
638 bool find_max_position( position& pos )
641 marked_node_ptr pSucc;
642 marked_node_ptr pCur;
644 // Hazard pointer array:
645 // pPred: [nLevel * 2]
646 // pSucc: [nLevel * 2 + 1]
649 pPred = m_Head.head();
651 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
652 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
654 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
656 // pCur.bits() means that pPred is logically deleted
660 if ( pCur.ptr() == nullptr ) {
661 // end of the list at level nLevel - goto next level
665 // pSucc contains deletion mark for pCur
666 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
668 if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
671 if ( pSucc.bits() ) {
672 // pCur is marked, i.e. logically deleted.
673 marked_node_ptr p( pCur.ptr() );
674 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
675 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
678 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
687 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
688 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
693 pos.pPrev[ nLevel ] = pPred;
694 pos.pSucc[ nLevel ] = pCur.ptr();
697 return (pos.pCur = pCur.ptr()) != nullptr;
700 template <typename Func>
701 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
703 unsigned int nHeight = pNode->height();
705 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
706 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
709 marked_node_ptr p( pos.pSucc[0] );
710 pNode->next( 0 ).store( p, memory_model::memory_order_release );
711 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) ) {
714 cds::unref( f )( val );
717 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
720 marked_node_ptr q( pos.pSucc[ nLevel ]);
721 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) {
722 // pNode has been marked as removed while we are inserting it
725 m_Stat.onLogicDeleteWhileInsert();
729 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) )
732 // Renew insert position
733 m_Stat.onRenewInsertPosition();
734 if ( !find_position( val, pos, key_comparator(), false )) {
735 // The node has been deleted while we are inserting it
736 m_Stat.onNotFoundWhileInsert();
744 template <typename Func>
745 bool try_remove_at( node_type * pDel, position& pos, Func f )
747 assert( pDel != nullptr );
749 marked_node_ptr pSucc;
750 typename gc::Guard gSucc;
752 // logical deletion (marking)
753 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
755 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
756 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
757 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
765 pSucc = gSucc.protect( pDel->next(0), gc_protect );
766 marked_node_ptr p( pSucc.ptr() );
767 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
768 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
770 cds::unref(f)( *node_traits::to_value_ptr( pDel ));
775 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
776 pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
777 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
778 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed) )
781 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
782 m_Stat.onSlowErase();
787 // Fast erasing success
788 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
789 m_Stat.onFastErase();
800 enum finsd_fastpath_result {
802 find_fastpath_not_found,
805 template <typename Q, typename Compare, typename Func>
806 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
809 typename gc::template GuardArray<2> guards;
810 marked_node_ptr pCur;
811 marked_node_ptr pNull;
815 pPred = m_Head.head();
816 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
817 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
821 while ( pCur != pNull ) {
823 unsigned int nAttempt = 0;
824 while ( pCur.bits() && nAttempt++ < 16 ) {
826 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
831 // Maybe, we are on deleted node sequence
832 // Abort searching, try slow-path
833 return find_fastpath_abort;
838 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
842 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
844 else if ( nCmp == 0 ) {
846 cds::unref(f)( *node_traits::to_value_ptr( pCur.ptr() ), val );
847 return find_fastpath_found;
849 else // pCur > val - go down
855 return find_fastpath_not_found;
858 template <typename Q, typename Compare, typename Func>
859 bool find_slowpath( Q& val, Compare cmp, Func f )
862 if ( find_position( val, pos, cmp, true )) {
863 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
865 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
872 template <typename Q, typename Compare, typename Func>
873 bool find_with_( Q& val, Compare cmp, Func f )
875 switch ( find_fastpath( val, cmp, f )) {
876 case find_fastpath_found:
877 m_Stat.onFindFastSuccess();
879 case find_fastpath_not_found:
880 m_Stat.onFindFastFailed();
886 if ( find_slowpath( val, cmp, f )) {
887 m_Stat.onFindSlowSuccess();
891 m_Stat.onFindSlowFailed();
895 template <typename Q, typename Compare>
896 bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp )
898 # ifdef CDS_CXX11_LAMBDA_SUPPORT
899 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } );
901 get_functor gf(guard);
902 return find_with_( val, cmp, cds::ref(gf) );
906 template <typename Q, typename Compare, typename Func>
907 bool erase_( Q const& val, Compare cmp, Func f )
911 if ( !find_position( val, pos, cmp, false ) ) {
912 m_Stat.onEraseFailed();
916 node_type * pDel = pos.pCur;
917 typename gc::Guard gDel;
918 gDel.assign( node_traits::to_value_ptr(pDel) );
919 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
921 unsigned int nHeight = pDel->height();
922 if ( try_remove_at( pDel, pos, f )) {
924 m_Stat.onRemoveNode( nHeight );
925 m_Stat.onEraseSuccess();
929 m_Stat.onEraseFailed();
933 template <typename Q, typename Compare>
934 bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
939 if ( !find_position( val, pos, cmp, false ) ) {
940 m_Stat.onExtractFailed();
944 node_type * pDel = pos.pCur;
945 guard.assign( node_traits::to_value_ptr(pDel));
946 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
948 unsigned int nHeight = pDel->height();
949 if ( try_remove_at( pDel, pos,
950 # ifdef CDS_CXX11_LAMBDA_SUPPORT
951 [](value_type const&) {}
953 empty_erase_functor()
958 m_Stat.onRemoveNode( nHeight );
959 m_Stat.onExtractSuccess();
963 m_Stat.onExtractRetry();
967 bool extract_min_( typename gc::Guard& gDel )
972 if ( !find_min_position( pos ) ) {
974 m_Stat.onExtractMinFailed();
978 node_type * pDel = pos.pCur;
980 unsigned int nHeight = pDel->height();
981 gDel.assign( node_traits::to_value_ptr(pDel) );
983 if ( try_remove_at( pDel, pos,
984 # ifdef CDS_CXX11_LAMBDA_SUPPORT
985 [](value_type const&) {}
987 empty_erase_functor()
992 m_Stat.onRemoveNode( nHeight );
993 m_Stat.onExtractMinSuccess();
997 m_Stat.onExtractMinRetry();
1001 bool extract_max_( typename gc::Guard& gDel )
1006 if ( !find_max_position( pos ) ) {
1007 // The list is empty
1008 m_Stat.onExtractMaxFailed();
1012 node_type * pDel = pos.pCur;
1014 unsigned int nHeight = pDel->height();
1015 gDel.assign( node_traits::to_value_ptr(pDel) );
1017 if ( try_remove_at( pDel, pos,
1018 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1019 [](value_type const&) {}
1021 empty_erase_functor()
1026 m_Stat.onRemoveNode( nHeight );
1027 m_Stat.onExtractMaxSuccess();
1031 m_Stat.onExtractMaxRetry();
1035 void increase_height( unsigned int nHeight )
1037 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1038 if ( nCur < nHeight )
1039 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1044 /// Default constructor
1046 The constructor checks whether the count of guards is enough
1047 for skip-list and may raise an exception if not.
1050 : m_Head( c_nMaxHeight )
1051 , m_nHeight( c_nMinHeight )
1053 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
1055 gc::check_available_guards( c_nHazardPtrCount );
1057 // Barrier for head node
1058 CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
1061 /// Clears and destructs the skip-list
1069 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
1071 /// Const iterator type
1072 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
1074 /// Returns a forward iterator addressing the first element in a set
1077 return iterator( *m_Head.head() );
1080 /// Returns a forward const iterator addressing the first element in a set
1082 const_iterator begin() const
1084 return const_iterator( *m_Head.head() );
1086 const_iterator cbegin()
1088 return const_iterator( *m_Head.head() );
1092 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1098 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1100 const_iterator end() const
1102 return const_iterator();
1104 const_iterator cend()
1106 return const_iterator();
1111 /// Inserts new node
1113 The function inserts \p val in the set if it does not contain
1114 an item with key equal to \p val.
1116 Returns \p true if \p val is placed into the set, \p false otherwise.
1118 bool insert( value_type& val )
1120 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1121 return insert( val, []( value_type& ) {} );
1123 return insert( val, empty_insert_functor() );
1127 /// Inserts new node
1129 This function is intended for derived non-intrusive containers.
1131 The function allows to split creating of new item into two part:
1132 - create item with key only
1133 - insert new item into the set
1134 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1136 The functor signature is:
1138 void func( value_type& val );
1140 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1141 \p val no any other changes could be made on this set's item by concurrent threads.
1142 The user-defined functor is called only if the inserting is success and may be passed by reference
1143 using <tt>boost::ref</tt>
1145 template <typename Func>
1146 bool insert( value_type& val, Func f )
1148 typename gc::Guard gNew;
1149 gNew.assign( &val );
1151 node_type * pNode = node_traits::to_node_ptr( val );
1152 scoped_node_ptr scp( pNode );
1153 unsigned int nHeight = pNode->height();
1154 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1155 bool bTowerMade = false;
1160 bool bFound = find_position( val, pos, key_comparator(), true );
1162 // scoped_node_ptr deletes the node tower if we create it
1166 m_Stat.onInsertFailed();
1171 build_node( pNode );
1172 nHeight = pNode->height();
1177 if ( !insert_at_position( val, pNode, pos, f )) {
1178 m_Stat.onInsertRetry();
1182 increase_height( nHeight );
1184 m_Stat.onAddNode( nHeight );
1185 m_Stat.onInsertSuccess();
1191 /// Ensures that the \p val exists in the set
1193 The operation performs inserting or changing data with lock-free manner.
1195 If the item \p val is not found in the set, then \p val is inserted into the set.
1196 Otherwise, the functor \p func is called with item found.
1197 The functor signature is:
1199 void func( bool bNew, value_type& item, value_type& val );
1202 - \p bNew - \p true if the item has been inserted, \p false otherwise
1203 - \p item - item of the set
1204 - \p val - argument \p val passed into the \p ensure function
1205 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1206 refer to the same thing.
1208 The functor can change non-key fields of the \p item; however, \p func must guarantee
1209 that during changing no any other modifications could be made on this item by concurrent threads.
1211 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1213 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1214 \p second is \p true if new item has been added or \p false if the item with \p key
1215 already is in the set.
1217 template <typename Func>
1218 std::pair<bool, bool> ensure( value_type& val, Func func )
1220 typename gc::Guard gNew;
1221 gNew.assign( &val );
1223 node_type * pNode = node_traits::to_node_ptr( val );
1224 scoped_node_ptr scp( pNode );
1225 unsigned int nHeight = pNode->height();
1226 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1227 bool bTowerMade = false;
1229 # ifndef CDS_CXX11_LAMBDA_SUPPORT
1230 insert_at_ensure_functor<Func> wrapper( func );
1236 bool bFound = find_position( val, pos, key_comparator(), true );
1238 // scoped_node_ptr deletes the node tower if we create it before
1242 cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
1243 m_Stat.onEnsureExist();
1244 return std::make_pair( true, false );
1248 build_node( pNode );
1249 nHeight = pNode->height();
1254 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1255 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
1257 if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
1260 m_Stat.onInsertRetry();
1264 increase_height( nHeight );
1267 m_Stat.onAddNode( nHeight );
1268 m_Stat.onEnsureNew();
1269 return std::make_pair( true, true );
1273 /// Unlinks the item \p val from the set
1275 The function searches the item \p val in the set and unlink it from the set
1276 if it is found and is equal to \p val.
1278 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
1279 and deletes the item found. \p unlink finds an item by key and deletes it
1280 only if \p val is an item of that set, i.e. the pointer to item found
1281 is equal to <tt> &val </tt>.
1283 The \ref disposer specified in \p Traits class template parameter is called
1284 by garbage collector \p GC asynchronously.
1286 The function returns \p true if success and \p false otherwise.
1288 bool unlink( value_type& val )
1292 if ( !find_position( val, pos, key_comparator(), false ) ) {
1293 m_Stat.onUnlinkFailed();
1297 node_type * pDel = pos.pCur;
1298 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1300 unsigned int nHeight = pDel->height();
1301 typename gc::Guard gDel;
1302 gDel.assign( node_traits::to_value_ptr(pDel) );
1304 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos,
1305 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1306 [](value_type const&) {}
1308 empty_erase_functor()
1313 m_Stat.onRemoveNode( nHeight );
1314 m_Stat.onUnlinkSuccess();
1318 m_Stat.onUnlinkFailed();
1322 /// Extracts the item from the set with specified \p key
1323 /** \anchor cds_intrusive_SkipListSet_hp_extract
1324 The function searches an item with key equal to \p key in the set,
1325 unlinks it from the set, and returns it in \p dest parameter.
1326 If the item with key equal to \p key is not found the function returns \p false.
1328 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1330 The \ref disposer specified in \p Traits class template parameter is called automatically
1331 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
1332 will be destroyed or released.
1333 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1337 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1341 skip_list::guarded_ptr gp;
1342 theList.extract( gp, 5 );
1346 // Destructor of gp releases internal HP guard
1350 template <typename Q>
1351 bool extract( guarded_ptr& dest, Q const& key )
1353 return extract_( dest.guard(), key, key_comparator() );
1356 /// Extracts the item from the set with comparing functor \p pred
1358 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1359 but \p pred predicate is used for key comparing.
1361 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1363 \p pred must imply the same element order as the comparator used for building the set.
1365 template <typename Q, typename Less>
1366 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
1368 return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1371 /// Extracts an item with minimal key from the list
1373 The function searches an item with minimal key, unlinks it, and returns the item found in \p dest parameter.
1374 If the skip-list is empty the function returns \p false.
1376 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1377 It means that the function gets leftmost item and tries to unlink it.
1378 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1379 So, the function returns the item with minimum key at the moment of list traversing.
1381 The \ref disposer specified in \p Traits class template parameter is called
1382 by garbage collector \p GC automatically when returned \ref guarded_ptr object
1383 will be destroyed or released.
1384 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1388 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1392 skip_list::guarded_ptr gp;
1393 if ( theList.extract_min( gp )) {
1397 // Destructor of gp releases internal HP guard
1401 bool extract_min( guarded_ptr& dest)
1403 return extract_min_( dest.guard() );
1406 /// Extracts an item with maximal key from the list
1408 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p dest parameter.
1409 If the skip-list is empty the function returns empty \p guarded_ptr.
1411 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1412 It means that the function gets rightmost item and tries to unlink it.
1413 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1414 So, the function returns the item with maximum key at the moment of list traversing.
1416 The \ref disposer specified in \p Traits class template parameter is called
1417 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1418 will be destroyed or released.
1419 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1423 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1427 skip_list::guarded_ptr gp;
1428 if ( theList.extract_max( gp )) {
1432 // Destructor of gp releases internal HP guard
1436 bool extract_max( guarded_ptr& dest )
1438 return extract_max_( dest.guard() );
1441 /// Deletes the item from the set
1442 /** \anchor cds_intrusive_SkipListSet_hp_erase
1443 The function searches an item with key equal to \p val in the set,
1444 unlinks it from the set, and returns \p true.
1445 If the item with key equal to \p val is not found the function return \p false.
1447 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1449 template <typename Q>
1450 bool erase( Q const& val )
1452 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1453 return erase_( val, key_comparator(), [](value_type const&) {} );
1455 return erase_( val, key_comparator(), empty_erase_functor() );
1459 /// Deletes the item from the set with comparing functor \p pred
1461 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1462 but \p pred predicate is used for key comparing.
1464 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1466 \p pred must imply the same element order as the comparator used for building the set.
1468 template <typename Q, typename Less>
1469 bool erase_with( Q const& val, Less pred )
1471 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1472 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1474 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_erase_functor() );
1478 /// Deletes the item from the set
1479 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1480 The function searches an item with key equal to \p val in the set,
1481 call \p f functor with item found, unlinks it from the set, and returns \p true.
1482 The \ref disposer specified in \p Traits class template parameter is called
1483 by garbage collector \p GC asynchronously.
1485 The \p Func interface is
1488 void operator()( value_type const& item );
1491 The functor can be passed by reference with <tt>boost:ref</tt>
1493 If the item with key equal to \p val is not found the function return \p false.
1495 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1497 template <typename Q, typename Func>
1498 bool erase( Q const& val, Func f )
1500 return erase_( val, key_comparator(), f );
1503 /// Deletes the item from the set with comparing functor \p pred
1505 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1506 but \p pred predicate is used for key comparing.
1508 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1510 \p pred must imply the same element order as the comparator used for building the set.
1512 template <typename Q, typename Less, typename Func>
1513 bool erase_with( Q const& val, Less pred, Func f )
1515 return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1518 /// Finds the key \p val
1519 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1520 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1521 The interface of \p Func functor is:
1524 void operator()( value_type& item, Q& val );
1527 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1529 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1531 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1532 that \p item cannot be disposed during functor is executing.
1533 The functor does not serialize simultaneous access to the set \p item. If such access is
1534 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1536 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1537 can modify both arguments.
1539 Note the compare functor specified for class \p Traits template parameter
1540 should accept a parameter of type \p Q that can be not the same as \p value_type.
1542 The function returns \p true if \p val is found, \p false otherwise.
1544 template <typename Q, typename Func>
1545 bool find( Q& val, Func f )
1547 return find_with_( val, key_comparator(), f );
1550 /// Finds the key \p val with \p pred predicate for comparing
1552 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1553 but \p pred is used for key compare.
1555 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1557 \p pred must imply the same element order as the comparator used for building the set.
1559 template <typename Q, typename Less, typename Func>
1560 bool find_with( Q& val, Less pred, Func f )
1562 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1565 /// Finds the key \p val
1566 /** \anchor cds_intrusive_SkipListSet_hp_find_cfunc
1567 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1568 The interface of \p Func functor is:
1571 void operator()( value_type& item, Q const& val );
1574 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1576 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1578 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1579 that \p item cannot be disposed during functor is executing.
1580 The functor does not serialize simultaneous access to the set \p item. If such access is
1581 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1583 Note the compare functor specified for class \p Traits template parameter
1584 should accept a parameter of type \p Q that can be not the same as \p value_type.
1586 The function returns \p true if \p val is found, \p false otherwise.
1588 template <typename Q, typename Func>
1589 bool find( Q const& val, Func f )
1591 return find_with_( val, key_comparator(), f );
1594 /// Finds the key \p val with \p pred predicate for comparing
1596 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_cfunc "find(Q const&, Func)"
1597 but \p pred is used for key compare.
1598 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1600 \p pred must imply the same element order as the comparator used for building the set.
1602 template <typename Q, typename Less, typename Func>
1603 bool find_with( Q const& val, Less pred, Func f )
1605 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1608 /// Finds the key \p val
1609 /** \anchor cds_intrusive_SkipListSet_hp_find_val
1610 The function searches the item with key equal to \p val
1611 and returns \p true if it is found, and \p false otherwise.
1613 Note the compare functor specified for class \p Traits template parameter
1614 should accept a parameter of type \p Q that can be not the same as \p value_type.
1616 template <typename Q>
1617 bool find( Q const & val )
1619 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1620 return find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
1622 return find_with_( val, key_comparator(), empty_find_functor() );
1626 /// Finds the key \p val with comparing functor \p pred
1628 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1629 but \p pred is used for comparing the keys.
1630 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1632 \p pred must imply the same element order as the comparator used for building the set.
1634 template <typename Q, typename Less>
1635 bool find_with( Q const& val, Less pred )
1637 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1638 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1640 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
1644 /// Finds the key \p val and return the item found
1645 /** \anchor cds_intrusive_SkipListSet_hp_get
1646 The function searches the item with key equal to \p val
1647 and assigns the item found to guarded pointer \p ptr.
1648 The function returns \p true if \p val is found, and \p false otherwise.
1649 If \p val is not found the \p ptr parameter is not changed.
1651 The \ref disposer specified in \p Traits class template parameter is called
1652 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1653 will be destroyed or released.
1654 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1658 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1662 skip_list::guarded_ptr gp;
1663 if ( theList.get( gp, 5 )) {
1667 // Destructor of guarded_ptr releases internal HP guard
1671 Note the compare functor specified for class \p Traits template parameter
1672 should accept a parameter of type \p Q that can be not the same as \p value_type.
1674 template <typename Q>
1675 bool get( guarded_ptr& ptr, Q const& val )
1677 return get_with_( ptr.guard(), val, key_comparator() );
1680 /// Finds the key \p val and return the item found
1682 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1683 but \p pred is used for comparing the keys.
1685 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1687 \p pred must imply the same element order as the comparator used for building the set.
1689 template <typename Q, typename Less>
1690 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
1692 return get_with_( ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
1695 /// Returns item count in the set
1697 The value returned depends on item counter type provided by \p Traits template parameter.
1698 If it is atomicity::empty_item_counter this function always returns 0.
1699 Therefore, the function is not suitable for checking the set emptiness, use \ref empty
1700 member function for this purpose.
1704 return m_ItemCounter;
1707 /// Checks if the set is empty
1710 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1713 /// Clears the set (non-atomic)
1715 The function unlink all items from the set.
1716 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1720 assert( set.empty() );
1722 the assertion could be raised.
1724 For each item the \ref disposer will be called after unlinking.
1729 while ( extract_min( gp ));
1732 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1733 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1735 return c_nMaxHeight;
1738 /// Returns const reference to internal statistics
1739 stat const& statistics() const
1746 }} // namespace cds::intrusive
1749 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H