2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
34 #include <type_traits>
36 #include <functional> // ref
37 #include <cds/intrusive/details/skip_list_base.h>
38 #include <cds/opt/compare.h>
39 #include <cds/details/binary_functor_wrapper.h>
41 namespace cds { namespace intrusive {
44 namespace skip_list { namespace details {
46 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
50 typedef NodeTraits node_traits;
51 typedef BackOff back_off;
52 typedef typename node_traits::node_type node_type;
53 typedef typename node_traits::value_type value_type;
54 static CDS_CONSTEXPR bool const c_isConst = IsConst;
56 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type value_ref;
59 typedef typename node_type::marked_ptr marked_ptr;
60 typedef typename node_type::atomic_marked_ptr atomic_marked_ptr;
62 typename gc::Guard m_guard;
66 static value_type * gc_protect( marked_ptr p )
68 return node_traits::to_value_ptr( p.ptr() );
78 if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
79 // Current node is marked as deleted. So, its next pointer can point to anything
80 // In this case we interrupt our iteration and returns end() iterator.
85 marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
86 node_type * pp = p.ptr();
88 // p is marked as deleted. Spin waiting for physical removal
92 else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits() ) {
93 // p is marked as deleted. Spin waiting for physical removal
103 public: // for internal use only!!!
104 iterator( node_type& refHead )
110 marked_ptr p = m_guard.protect( refHead[0], gc_protect );
117 node_type * pp = p.ptr();
118 // Logically deleted node is marked from highest level
119 if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
133 iterator( iterator const& s)
134 : m_pNode( s.m_pNode )
136 m_guard.assign( node_traits::to_value_ptr(m_pNode) );
139 value_type * operator ->() const
141 assert( m_pNode != nullptr );
142 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
144 return node_traits::to_value_ptr( m_pNode );
147 value_ref operator *() const
149 assert( m_pNode != nullptr );
150 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
152 return *node_traits::to_value_ptr( m_pNode );
156 iterator& operator ++()
162 iterator& operator =(const iterator& src)
164 m_pNode = src.m_pNode;
165 m_guard.copy( src.m_guard );
169 template <typename Bkoff, bool C>
170 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
172 return m_pNode == i.m_pNode;
174 template <typename Bkoff, bool C>
175 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
177 return !( *this == i );
180 }} // namespace skip_list::details
183 /// Lock-free skip-list set
184 /** @ingroup cds_intrusive_map
185 @anchor cds_intrusive_SkipListSet_hp
187 The implementation of well-known probabilistic data structure called skip-list
188 invented by W.Pugh in his papers:
189 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
190 - [1990] W.Pugh A Skip List Cookbook
192 A skip-list is a probabilistic data structure that provides expected logarithmic
193 time search without the need of rebalance. The skip-list is a collection of sorted
194 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
195 Each list has a level, ranging from 0 to 32. The bottom-level list contains
196 all the nodes, and each higher-level list is a sublist of the lower-level lists.
197 Each node is created with a random top level (with a random height), and belongs
198 to all lists up to that level. The probability that a node has the height 1 is 1/2.
199 The probability that a node has the height N is 1/2 ** N (more precisely,
200 the distribution depends on an random generator provided, but our generators
203 The lock-free variant of skip-list is implemented according to book
204 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
205 chapter 14.4 "A Lock-Free Concurrent Skiplist".
207 <b>Template arguments</b>:
208 - \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.
209 - \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)
210 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
211 - \p Traits - skip-list traits, default is \p skip_list::traits.
212 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
215 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
216 the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
217 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
218 when you try to create skip-list object.
220 There are several specializations of \p %SkipListSet for each \p GC. You should include:
221 - <tt><cds/intrusive/skip_list_hp.h></tt> for \p gc::HP garbage collector
222 - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
223 - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for append-only set
224 - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
228 The class supports a forward iterator (\ref iterator and \ref const_iterator).
229 The iteration is ordered.
230 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
231 so, the element cannot be reclaimed while the iterator object is alive.
232 However, passing an iterator object between threads is dangerous.
234 @warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
235 all elements in the set: any concurrent deletion can exclude the element
236 pointed by the iterator from the set, and your iteration can be terminated
237 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
239 Remember, each iterator object requires 2 additional hazard pointers, that may be
240 a limited resource for \p GC like as \p gc::HP (for \p gc::DHP the count of
241 guards is unlimited).
243 The iterator class supports the following minimalistic interface:
250 iterator( iterator const& s);
252 value_type * operator ->() const;
253 value_type& operator *() const;
256 iterator& operator ++();
259 iterator& operator = (const iterator& src);
261 bool operator ==(iterator const& i ) const;
262 bool operator !=(iterator const& i ) const;
265 Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
269 You should incorporate \p skip_list::node into your struct \p T and provide
270 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
271 define a struct based on \p skip_list::traits.
273 Example for \p gc::HP and base hook:
275 // Include GC-related skip-list specialization
276 #include <cds/intrusive/skip_list_hp.h>
278 // Data stored in skip list
279 struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
288 // my_data compare functor
290 int operator()( const my_data& d1, const my_data& d2 )
292 return d1.strKey.compare( d2.strKey );
295 int operator()( const my_data& d, const std::string& s )
297 return d.strKey.compare(s);
300 int operator()( const std::string& s, const my_data& d )
302 return s.compare( d.strKey );
307 // Declare your traits
308 struct my_traits: public cds::intrusive::skip_list::traits
310 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
311 typedef my_data_cmp compare;
314 // Declare skip-list set type
315 typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits > traits_based_set;
318 Equivalent option-based code:
320 // GC-related specialization
321 #include <cds/intrusive/skip_list_hp.h>
330 // Declare option-based skip-list set
331 typedef cds::intrusive::SkipListSet< cds::gc::HP
333 , typename cds::intrusive::skip_list::make_traits<
334 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
335 ,cds::intrusive::opt::compare< my_data_cmp >
344 #ifdef CDS_DOXYGEN_INVOKED
345 ,typename Traits = skip_list::traits
353 typedef GC gc; ///< Garbage collector
354 typedef T value_type; ///< type of value stored in the skip-list
355 typedef Traits traits; ///< Traits template parameter
357 typedef typename traits::hook hook; ///< hook type
358 typedef typename hook::node_type node_type; ///< node type
360 # ifdef CDS_DOXYGEN_INVOKED
361 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
363 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
366 typedef typename traits::disposer disposer; ///< item disposer
367 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
369 typedef typename traits::item_counter item_counter; ///< Item counting policy
370 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
371 typedef typename traits::random_level_generator random_level_generator; ///< random level generator
372 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
373 typedef typename traits::back_off back_off; ///< Back-off strategy
374 typedef typename traits::stat stat; ///< internal statistics type
377 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
379 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
381 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
382 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
384 static unsigned int const c_nMaxHeight = std::conditional<
385 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
386 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
387 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
391 static unsigned int const c_nMinHeight = 5;
395 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
396 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
400 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
402 typedef typename std::conditional<
403 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
404 ,intrusive_node_builder
405 ,typename traits::internal_node_builder
406 >::type node_builder;
408 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
410 // c_nMaxHeight * 2 - pPred/pSucc guards
411 // + 1 - for erase, unlink
413 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
415 node_type * pPrev[ c_nMaxHeight ];
416 node_type * pSucc[ c_nMaxHeight ];
418 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
419 node_type * pCur; // guarded by guards; needed only for \p update()
424 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
426 item_counter m_ItemCounter; ///< item counter
427 random_level_generator m_RandomLevelGen; ///< random level generator instance
428 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
429 mutable stat m_Stat; ///< internal statistics
433 unsigned int random_level()
435 // Random generator produces a number from range [0..31]
436 // We need a number from range [1..32]
437 return m_RandomLevelGen() + 1;
440 template <typename Q>
441 node_type * build_node( Q v )
443 return node_builder::make_tower( v, m_RandomLevelGen );
446 static value_type * gc_protect( marked_node_ptr p )
448 return node_traits::to_value_ptr( p.ptr() );
451 static void dispose_node( value_type * pVal )
453 assert( pVal != nullptr );
454 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
458 template <typename Q, typename Compare >
459 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
462 marked_node_ptr pSucc;
463 marked_node_ptr pCur;
465 // Hazard pointer array:
466 // pPred: [nLevel * 2]
467 // pSucc: [nLevel * 2 + 1]
470 pPred = m_Head.head();
473 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
474 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
476 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
478 // pCur.bits() means that pPred is logically deleted
482 if ( pCur.ptr() == nullptr ) {
483 // end of the list at level nLevel - goto next level
487 // pSucc contains deletion mark for pCur
488 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
490 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
493 if ( pSucc.bits() ) {
494 // pCur is marked, i.e. logically deleted.
495 marked_node_ptr p( pCur.ptr() );
496 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
497 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
500 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
501 m_Stat.onEraseWhileFind();
507 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
510 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
512 else if ( nCmp == 0 && bStopIfFound )
520 pos.pPrev[ nLevel ] = pPred;
521 pos.pSucc[ nLevel ] = pCur.ptr();
528 pos.pCur = pCur.ptr();
529 return pCur.ptr() && nCmp == 0;
532 bool find_min_position( position& pos )
535 marked_node_ptr pSucc;
536 marked_node_ptr pCur;
538 // Hazard pointer array:
539 // pPred: [nLevel * 2]
540 // pSucc: [nLevel * 2 + 1]
543 pPred = m_Head.head();
545 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
546 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
547 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
549 // pCur.bits() means that pPred is logically deleted
550 // head cannot be deleted
551 assert( pCur.bits() == 0 );
555 // pSucc contains deletion mark for pCur
556 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
558 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
561 if ( pSucc.bits() ) {
562 // pCur is marked, i.e. logically deleted.
563 marked_node_ptr p( pCur.ptr() );
564 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
565 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
568 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
569 m_Stat.onEraseWhileFind();
577 pos.pPrev[ nLevel ] = pPred;
578 pos.pSucc[ nLevel ] = pCur.ptr();
581 return (pos.pCur = pCur.ptr()) != nullptr;
584 bool find_max_position( position& pos )
587 marked_node_ptr pSucc;
588 marked_node_ptr pCur;
590 // Hazard pointer array:
591 // pPred: [nLevel * 2]
592 // pSucc: [nLevel * 2 + 1]
595 pPred = m_Head.head();
597 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
598 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
600 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
602 // pCur.bits() means that pPred is logically deleted
606 if ( pCur.ptr() == nullptr ) {
607 // end of the list at level nLevel - goto next level
611 // pSucc contains deletion mark for pCur
612 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
614 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).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_acquire, atomics::memory_order_relaxed ))
624 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
625 m_Stat.onEraseWhileFind();
635 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
636 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
641 pos.pPrev[ nLevel ] = pPred;
642 pos.pSucc[ nLevel ] = pCur.ptr();
645 return (pos.pCur = pCur.ptr()) != nullptr;
648 template <typename Func>
649 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
651 unsigned int nHeight = pNode->height();
653 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
654 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
658 marked_node_ptr p( pos.pSucc[0] );
659 pNode->next( 0 ).store( p, memory_model::memory_order_release );
660 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ))
666 // Insert at level 1..max
667 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
670 marked_node_ptr q( pos.pSucc[ nLevel ]);
671 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
672 // pNode has been marked as removed while we are inserting it
675 m_Stat.onLogicDeleteWhileInsert();
679 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
682 // Renew insert position
683 m_Stat.onRenewInsertPosition();
684 if ( !find_position( val, pos, key_comparator(), false )) {
685 // The node has been deleted while we are inserting it
686 m_Stat.onNotFoundWhileInsert();
694 template <typename Func>
695 bool try_remove_at( node_type * pDel, position& pos, Func f )
697 assert( pDel != nullptr );
699 marked_node_ptr pSucc;
701 // logical deletion (marking)
702 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
704 pSucc = pDel->next(nLevel);
705 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
706 memory_model::memory_order_release, atomics::memory_order_relaxed ))
714 marked_node_ptr p( pDel->next(0).load(memory_model::memory_order_relaxed).ptr() );
715 if ( pDel->next(0).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_relaxed ))
717 f( *node_traits::to_value_ptr( pDel ));
722 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
723 pSucc = pDel->next(nLevel).load(memory_model::memory_order_relaxed);
724 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
725 memory_model::memory_order_acquire, atomics::memory_order_relaxed) )
728 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
729 m_Stat.onSlowErase();
734 // Fast erasing success
735 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
736 m_Stat.onFastErase();
741 // Another thread is deleting pDel right now
745 m_Stat.onEraseRetry();
749 enum finsd_fastpath_result {
751 find_fastpath_not_found,
754 template <typename Q, typename Compare, typename Func>
755 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
758 typename gc::template GuardArray<2> guards;
759 marked_node_ptr pCur;
760 marked_node_ptr pNull;
764 pPred = m_Head.head();
765 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
766 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
770 while ( pCur != pNull ) {
772 unsigned int nAttempt = 0;
773 while ( pCur.bits() && nAttempt++ < 16 ) {
775 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
780 // Maybe, we are on deleted node sequence
781 // Abort searching, try slow-path
782 return find_fastpath_abort;
787 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
791 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
793 else if ( nCmp == 0 ) {
795 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
796 return find_fastpath_found;
798 else // pCur > val - go down
804 return find_fastpath_not_found;
807 template <typename Q, typename Compare, typename Func>
808 bool find_slowpath( Q& val, Compare cmp, Func f )
811 if ( find_position( val, pos, cmp, true )) {
812 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
814 f( *node_traits::to_value_ptr( pos.pCur ), val );
821 template <typename Q, typename Compare, typename Func>
822 bool find_with_( Q& val, Compare cmp, Func f )
824 switch ( find_fastpath( val, cmp, f )) {
825 case find_fastpath_found:
826 m_Stat.onFindFastSuccess();
828 case find_fastpath_not_found:
829 m_Stat.onFindFastFailed();
835 if ( find_slowpath( val, cmp, f )) {
836 m_Stat.onFindSlowSuccess();
840 m_Stat.onFindSlowFailed();
844 template <typename Q, typename Compare>
845 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
847 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
850 template <typename Q, typename Compare, typename Func>
851 bool erase_( Q const& val, Compare cmp, Func f )
855 if ( !find_position( val, pos, cmp, false ) ) {
856 m_Stat.onEraseFailed();
860 node_type * pDel = pos.pCur;
861 typename gc::Guard gDel;
862 gDel.assign( node_traits::to_value_ptr(pDel) );
863 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
865 unsigned int nHeight = pDel->height();
866 if ( try_remove_at( pDel, pos, f )) {
868 m_Stat.onRemoveNode( nHeight );
869 m_Stat.onEraseSuccess();
873 m_Stat.onEraseFailed();
877 template <typename Q, typename Compare>
878 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
883 if ( !find_position( val, pos, cmp, false ) ) {
884 m_Stat.onExtractFailed();
889 node_type * pDel = pos.pCur;
890 guard.set( node_traits::to_value_ptr(pDel));
891 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
893 unsigned int nHeight = pDel->height();
894 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
896 m_Stat.onRemoveNode( nHeight );
897 m_Stat.onExtractSuccess();
900 m_Stat.onExtractRetry();
904 bool extract_min_( typename guarded_ptr::native_guard& gDel )
909 if ( !find_min_position( pos ) ) {
911 m_Stat.onExtractMinFailed();
916 node_type * pDel = pos.pCur;
918 unsigned int nHeight = pDel->height();
919 gDel.set( node_traits::to_value_ptr(pDel) );
921 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
923 m_Stat.onRemoveNode( nHeight );
924 m_Stat.onExtractMinSuccess();
928 m_Stat.onExtractMinRetry();
932 bool extract_max_( typename guarded_ptr::native_guard& gDel )
937 if ( !find_max_position( pos ) ) {
939 m_Stat.onExtractMaxFailed();
944 node_type * pDel = pos.pCur;
946 unsigned int nHeight = pDel->height();
947 gDel.set( node_traits::to_value_ptr(pDel) );
949 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
951 m_Stat.onRemoveNode( nHeight );
952 m_Stat.onExtractMaxSuccess();
956 m_Stat.onExtractMaxRetry();
960 void increase_height( unsigned int nHeight )
962 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
963 if ( nCur < nHeight )
964 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
969 /// Default constructor
971 The constructor checks whether the count of guards is enough
972 for skip-list and may raise an exception if not.
975 : m_Head( c_nMaxHeight )
976 , m_nHeight( c_nMinHeight )
978 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
980 gc::check_available_guards( c_nHazardPtrCount );
982 // Barrier for head node
983 atomics::atomic_thread_fence( memory_model::memory_order_release );
986 /// Clears and destructs the skip-list
994 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
996 /// Const iterator type
997 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
999 /// Returns a forward iterator addressing the first element in a set
1002 return iterator( *m_Head.head() );
1005 /// Returns a forward const iterator addressing the first element in a set
1006 const_iterator begin() const
1008 return const_iterator( *m_Head.head() );
1010 /// Returns a forward const iterator addressing the first element in a set
1011 const_iterator cbegin() const
1013 return const_iterator( *m_Head.head() );
1016 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1022 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1023 const_iterator end() const
1025 return const_iterator();
1027 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1028 const_iterator cend() const
1030 return const_iterator();
1034 /// Inserts new node
1036 The function inserts \p val in the set if it does not contain
1037 an item with key equal to \p val.
1039 Returns \p true if \p val is placed into the set, \p false otherwise.
1041 bool insert( value_type& val )
1043 return insert( val, []( value_type& ) {} );
1046 /// Inserts new node
1048 This function is intended for derived non-intrusive containers.
1050 The function allows to split creating of new item into two part:
1051 - create item with key only
1052 - insert new item into the set
1053 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1055 The functor signature is:
1057 void func( value_type& val );
1059 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1060 \p val no any other changes could be made on this set's item by concurrent threads.
1061 The user-defined functor is called only if the inserting is success.
1063 template <typename Func>
1064 bool insert( value_type& val, Func f )
1066 typename gc::Guard gNew;
1067 gNew.assign( &val );
1069 node_type * pNode = node_traits::to_node_ptr( val );
1070 scoped_node_ptr scp( pNode );
1071 unsigned int nHeight = pNode->height();
1072 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1073 bool bTowerMade = false;
1078 if ( find_position( val, pos, key_comparator(), true )) {
1079 // scoped_node_ptr deletes the node tower if we create it
1083 m_Stat.onInsertFailed();
1088 build_node( pNode );
1089 nHeight = pNode->height();
1094 if ( !insert_at_position( val, pNode, pos, f )) {
1095 m_Stat.onInsertRetry();
1099 increase_height( nHeight );
1101 m_Stat.onAddNode( nHeight );
1102 m_Stat.onInsertSuccess();
1108 /// Updates the node
1110 The operation performs inserting or changing data with lock-free manner.
1112 If the item \p val is not found in the set, then \p val is inserted into the set
1113 iff \p bInsert is \p true.
1114 Otherwise, the functor \p func is called with item found.
1115 The functor \p func signature is:
1117 void func( bool bNew, value_type& item, value_type& val );
1120 - \p bNew - \p true if the item has been inserted, \p false otherwise
1121 - \p item - item of the set
1122 - \p val - argument \p val passed into the \p %update() function
1123 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1124 refer to the same thing.
1126 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1127 i.e. the node has been inserted or updated,
1128 \p second is \p true if new item has been added or \p false if the item with \p key
1131 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1133 template <typename Func>
1134 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
1136 typename gc::Guard gNew;
1137 gNew.assign( &val );
1139 node_type * pNode = node_traits::to_node_ptr( val );
1140 scoped_node_ptr scp( pNode );
1141 unsigned int nHeight = pNode->height();
1142 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1143 bool bTowerMade = false;
1148 bool bFound = find_position( val, pos, key_comparator(), true );
1150 // scoped_node_ptr deletes the node tower if we create it before
1154 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1155 m_Stat.onUpdateExist();
1156 return std::make_pair( true, false );
1161 return std::make_pair( false, false );
1165 build_node( pNode );
1166 nHeight = pNode->height();
1171 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1172 m_Stat.onInsertRetry();
1176 increase_height( nHeight );
1179 m_Stat.onAddNode( nHeight );
1180 m_Stat.onUpdateNew();
1181 return std::make_pair( true, true );
1185 template <typename Func>
1186 CDS_DEPRECATED("ensure() is deprecated, use update()")
1187 std::pair<bool, bool> ensure( value_type& val, Func func )
1189 return update( val, func, true );
1193 /// Unlinks the item \p val from the set
1195 The function searches the item \p val in the set and unlink it from the set
1196 if it is found and is equal to \p val.
1198 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1199 and deletes the item found. \p %unlink() finds an item by key and deletes it
1200 only if \p val is an item of that set, i.e. the pointer to item found
1201 is equal to <tt> &val </tt>.
1203 The \p disposer specified in \p Traits class template parameter is called
1204 by garbage collector \p GC asynchronously.
1206 The function returns \p true if success and \p false otherwise.
1208 bool unlink( value_type& val )
1212 if ( !find_position( val, pos, key_comparator(), false ) ) {
1213 m_Stat.onUnlinkFailed();
1217 node_type * pDel = pos.pCur;
1218 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1220 unsigned int nHeight = pDel->height();
1221 typename gc::Guard gDel;
1222 gDel.assign( node_traits::to_value_ptr(pDel) );
1224 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1226 m_Stat.onRemoveNode( nHeight );
1227 m_Stat.onUnlinkSuccess();
1231 m_Stat.onUnlinkFailed();
1235 /// Extracts the item from the set with specified \p key
1236 /** \anchor cds_intrusive_SkipListSet_hp_extract
1237 The function searches an item with key equal to \p key in the set,
1238 unlinks it from the set, and returns it as \p guarded_ptr object.
1239 If \p key is not found the function returns an empty guarded pointer.
1241 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1243 The \p disposer specified in \p Traits class template parameter is called automatically
1244 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1245 will be destroyed or released.
1246 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1250 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1254 skip_list::guarded_ptr gp(theList.extract( 5 ));
1259 // Destructor of gp releases internal HP guard
1263 template <typename Q>
1264 guarded_ptr extract( Q const& key )
1267 extract_( gp.guard(), key, key_comparator() );
1271 /// Extracts the item from the set with comparing functor \p pred
1273 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1274 but \p pred predicate is used for key comparing.
1276 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1278 \p pred must imply the same element order as the comparator used for building the set.
1280 template <typename Q, typename Less>
1281 guarded_ptr extract_with( Q const& key, Less pred )
1285 extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1289 /// Extracts an item with minimal key from the list
1291 The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
1292 If the skip-list is empty the function returns an empty guarded pointer.
1294 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1295 It means that the function gets leftmost item and tries to unlink it.
1296 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1297 So, the function returns the item with minimum key at the moment of list traversing.
1299 The \p disposer specified in \p Traits class template parameter is called
1300 by garbage collector \p GC automatically when returned \p guarded_ptr object
1301 will be destroyed or released.
1302 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1306 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1310 skip_list::guarded_ptr gp(theList.extract_min());
1315 // Destructor of gp releases internal HP guard
1319 guarded_ptr extract_min()
1322 extract_min_( gp.guard() );
1326 /// Extracts an item with maximal key from the list
1328 The function searches an item with maximal key, unlinks it, and returns the pointer to item
1329 as \p guarded_ptr object.
1330 If the skip-list is empty the function returns an empty \p guarded_ptr.
1332 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1333 It means that the function gets rightmost item and tries to unlink it.
1334 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1335 So, the function returns the item with maximum key at the moment of list traversing.
1337 The \p disposer specified in \p Traits class template parameter is called
1338 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1339 will be destroyed or released.
1340 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1344 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1348 skip_list::guarded_ptr gp( theList.extract_max( gp ));
1353 // Destructor of gp releases internal HP guard
1357 guarded_ptr extract_max()
1360 extract_max_( gp.guard() );
1364 /// Deletes the item from the set
1365 /** \anchor cds_intrusive_SkipListSet_hp_erase
1366 The function searches an item with key equal to \p key in the set,
1367 unlinks it from the set, and returns \p true.
1368 If the item with key equal to \p key is not found the function return \p false.
1370 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1372 template <typename Q>
1373 bool erase( Q const& key )
1375 return erase_( key, key_comparator(), [](value_type const&) {} );
1378 /// Deletes the item from the set with comparing functor \p pred
1380 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1381 but \p pred predicate is used for key comparing.
1383 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1385 \p pred must imply the same element order as the comparator used for building the set.
1387 template <typename Q, typename Less>
1388 bool erase_with( Q const& key, Less pred )
1391 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1394 /// Deletes the item from the set
1395 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1396 The function searches an item with key equal to \p key in the set,
1397 call \p f functor with item found, unlinks it from the set, and returns \p true.
1398 The \ref disposer specified in \p Traits class template parameter is called
1399 by garbage collector \p GC asynchronously.
1401 The \p Func interface is
1404 void operator()( value_type const& item );
1408 If the item with key equal to \p key is not found the function return \p false.
1410 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1412 template <typename Q, typename Func>
1413 bool erase( Q const& key, Func f )
1415 return erase_( key, key_comparator(), f );
1418 /// Deletes the item from the set with comparing functor \p pred
1420 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1421 but \p pred predicate is used for key comparing.
1423 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1425 \p pred must imply the same element order as the comparator used for building the set.
1427 template <typename Q, typename Less, typename Func>
1428 bool erase_with( Q const& key, Less pred, Func f )
1431 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1435 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1436 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1437 The interface of \p Func functor is:
1440 void operator()( value_type& item, Q& key );
1443 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1445 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1446 that \p item cannot be disposed during functor is executing.
1447 The functor does not serialize simultaneous access to the set \p item. If such access is
1448 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1450 Note the compare functor specified for class \p Traits template parameter
1451 should accept a parameter of type \p Q that can be not the same as \p value_type.
1453 The function returns \p true if \p key is found, \p false otherwise.
1455 template <typename Q, typename Func>
1456 bool find( Q& key, Func f )
1458 return find_with_( key, key_comparator(), f );
1461 template <typename Q, typename Func>
1462 bool find( Q const& key, Func f )
1464 return find_with_( key, key_comparator(), f );
1468 /// Finds the key \p key with \p pred predicate for comparing
1470 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1471 but \p pred is used for key compare.
1473 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1475 \p pred must imply the same element order as the comparator used for building the set.
1477 template <typename Q, typename Less, typename Func>
1478 bool find_with( Q& key, Less pred, Func f )
1481 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1484 template <typename Q, typename Less, typename Func>
1485 bool find_with( Q const& key, Less pred, Func f )
1488 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1492 /// Checks whether the set contains \p key
1494 The function searches the item with key equal to \p key
1495 and returns \p true if it is found, and \p false otherwise.
1497 template <typename Q>
1498 bool contains( Q const& key )
1500 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1503 template <typename Q>
1504 CDS_DEPRECATED("deprecated, use contains()")
1505 bool find( Q const& key )
1507 return contains( key );
1511 /// Checks whether the set contains \p key using \p pred predicate for searching
1513 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1514 \p Less functor has the interface like \p std::less.
1515 \p Less must imply the same element order as the comparator used for building the set.
1517 template <typename Q, typename Less>
1518 bool contains( Q const& key, Less pred )
1521 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1524 template <typename Q, typename Less>
1525 CDS_DEPRECATED("deprecated, use contains()")
1526 bool find_with( Q const& key, Less pred )
1528 return contains( key, pred );
1532 /// Finds \p key and return the item found
1533 /** \anchor cds_intrusive_SkipListSet_hp_get
1534 The function searches the item with key equal to \p key
1535 and returns the pointer to the item found as \p guarded_ptr.
1536 If \p key is not found the function returns an empt guarded pointer.
1538 The \p disposer specified in \p Traits class template parameter is called
1539 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1540 will be destroyed or released.
1541 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1545 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1549 skip_list::guarded_ptr gp(theList.get( 5 ));
1554 // Destructor of guarded_ptr releases internal HP guard
1558 Note the compare functor specified for class \p Traits template parameter
1559 should accept a parameter of type \p Q that can be not the same as \p value_type.
1561 template <typename Q>
1562 guarded_ptr get( Q const& key )
1565 get_with_( gp.guard(), key, key_comparator() );
1569 /// Finds \p key and return the item found
1571 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1572 but \p pred is used for comparing the keys.
1574 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1576 \p pred must imply the same element order as the comparator used for building the set.
1578 template <typename Q, typename Less>
1579 guarded_ptr get_with( Q const& key, Less pred )
1583 get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1587 /// Returns item count in the set
1589 The value returned depends on item counter type provided by \p Traits template parameter.
1590 If it is \p atomicity::empty_item_counter this function always returns 0.
1591 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1596 return m_ItemCounter;
1599 /// Checks if the set is empty
1602 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1605 /// Clears the set (not atomic)
1607 The function unlink all items from the set.
1608 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1612 assert( set.empty() );
1614 the assertion could be raised.
1616 For each item the \ref disposer will be called after unlinking.
1621 while ( extract_min_( gp.guard() ));
1624 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1625 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1627 return c_nMaxHeight;
1630 /// Returns const reference to internal statistics
1631 stat const& statistics() const
1637 }} // namespace cds::intrusive
1640 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H