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;
394 // c_nMaxHeight * 2 - pPred/pSucc guards
395 // + 1 - for erase, unlink
397 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2; ///< Count of hazard pointer required for the skip-list
400 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
401 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
405 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
407 typedef typename std::conditional<
408 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
409 ,intrusive_node_builder
410 ,typename traits::internal_node_builder
411 >::type node_builder;
413 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
416 node_type * pPrev[ c_nMaxHeight ];
417 node_type * pSucc[ c_nMaxHeight ];
419 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
420 node_type * pCur; // guarded by guards; needed only for \p update()
425 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
427 item_counter m_ItemCounter; ///< item counter
428 random_level_generator m_RandomLevelGen; ///< random level generator instance
429 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
430 mutable stat m_Stat; ///< internal statistics
434 unsigned int random_level()
436 // Random generator produces a number from range [0..31]
437 // We need a number from range [1..32]
438 return m_RandomLevelGen() + 1;
441 template <typename Q>
442 node_type * build_node( Q v )
444 return node_builder::make_tower( v, m_RandomLevelGen );
447 static value_type * gc_protect( marked_node_ptr p )
449 return node_traits::to_value_ptr( p.ptr() );
452 static void dispose_node( value_type * pVal )
454 assert( pVal != nullptr );
455 typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
459 template <typename Q, typename Compare >
460 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
463 marked_node_ptr pSucc;
464 marked_node_ptr pCur;
466 // Hazard pointer array:
467 // pPred: [nLevel * 2]
468 // pSucc: [nLevel * 2 + 1]
471 pPred = m_Head.head();
474 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
475 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
477 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
479 // pCur.bits() means that pPred is logically deleted
483 if ( pCur.ptr() == nullptr ) {
484 // end of the list at level nLevel - goto next level
488 // pSucc contains deletion mark for pCur
489 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
491 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
494 if ( pSucc.bits() ) {
495 // pCur is marked, i.e. logically deleted.
496 marked_node_ptr p( pCur.ptr() );
497 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
498 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
501 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
502 m_Stat.onEraseWhileFind();
508 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
511 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ; // pPrev guard := cur guard
513 else if ( nCmp == 0 && bStopIfFound )
521 pos.pPrev[ nLevel ] = pPred;
522 pos.pSucc[ nLevel ] = pCur.ptr();
529 pos.pCur = pCur.ptr();
530 return pCur.ptr() && nCmp == 0;
533 bool find_min_position( position& pos )
536 marked_node_ptr pSucc;
537 marked_node_ptr pCur;
539 // Hazard pointer array:
540 // pPred: [nLevel * 2]
541 // pSucc: [nLevel * 2 + 1]
544 pPred = m_Head.head();
546 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
547 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
548 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
550 // pCur.bits() means that pPred is logically deleted
551 // head cannot be deleted
552 assert( pCur.bits() == 0 );
556 // pSucc contains deletion mark for pCur
557 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
559 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
562 if ( pSucc.bits() ) {
563 // pCur is marked, i.e. logically deleted.
564 marked_node_ptr p( pCur.ptr() );
565 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
566 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
569 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
570 m_Stat.onEraseWhileFind();
578 pos.pPrev[ nLevel ] = pPred;
579 pos.pSucc[ nLevel ] = pCur.ptr();
582 return (pos.pCur = pCur.ptr()) != nullptr;
585 bool find_max_position( position& pos )
588 marked_node_ptr pSucc;
589 marked_node_ptr pCur;
591 // Hazard pointer array:
592 // pPred: [nLevel * 2]
593 // pSucc: [nLevel * 2 + 1]
596 pPred = m_Head.head();
598 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
599 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
601 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
603 // pCur.bits() means that pPred is logically deleted
607 if ( pCur.ptr() == nullptr ) {
608 // end of the list at level nLevel - goto next level
612 // pSucc contains deletion mark for pCur
613 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
615 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
618 if ( pSucc.bits() ) {
619 // pCur is marked, i.e. logically deleted.
620 marked_node_ptr p( pCur.ptr() );
621 if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
622 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
625 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
626 m_Stat.onEraseWhileFind();
636 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
637 //pos.guards.copy( nLevel * 2, gCur ) ; // pPrev guard := gCur
642 pos.pPrev[ nLevel ] = pPred;
643 pos.pSucc[ nLevel ] = pCur.ptr();
646 return (pos.pCur = pCur.ptr()) != nullptr;
649 template <typename Func>
650 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
652 unsigned int nHeight = pNode->height();
654 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
655 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
659 marked_node_ptr p( pos.pSucc[0] );
660 pNode->next( 0 ).store( p, memory_model::memory_order_release );
661 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ))
667 // Insert at level 1..max
668 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
671 marked_node_ptr q( pos.pSucc[ nLevel ]);
672 if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
673 // pNode has been marked as removed while we are inserting it
676 m_Stat.onLogicDeleteWhileInsert();
680 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
683 // Renew insert position
684 m_Stat.onRenewInsertPosition();
685 if ( !find_position( val, pos, key_comparator(), false )) {
686 // The node has been deleted while we are inserting it
687 m_Stat.onNotFoundWhileInsert();
695 template <typename Func>
696 bool try_remove_at( node_type * pDel, position& pos, Func f )
698 assert( pDel != nullptr );
700 marked_node_ptr pSucc;
702 // logical deletion (marking)
703 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
705 pSucc = pDel->next(nLevel);
706 if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
707 memory_model::memory_order_release, atomics::memory_order_relaxed ))
715 marked_node_ptr p( pDel->next(0).load(memory_model::memory_order_relaxed).ptr() );
716 if ( pDel->next(0).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_relaxed ))
718 f( *node_traits::to_value_ptr( pDel ));
723 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
724 pSucc = pDel->next(nLevel).load(memory_model::memory_order_relaxed);
725 if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
726 memory_model::memory_order_acquire, atomics::memory_order_relaxed) )
729 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
730 m_Stat.onSlowErase();
735 // Fast erasing success
736 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
737 m_Stat.onFastErase();
742 // Another thread is deleting pDel right now
746 m_Stat.onEraseRetry();
750 enum finsd_fastpath_result {
752 find_fastpath_not_found,
755 template <typename Q, typename Compare, typename Func>
756 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
759 typename gc::template GuardArray<2> guards;
760 marked_node_ptr pCur;
761 marked_node_ptr pNull;
765 pPred = m_Head.head();
766 for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
767 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
771 while ( pCur != pNull ) {
773 unsigned int nAttempt = 0;
774 while ( pCur.bits() && nAttempt++ < 16 ) {
776 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
781 // Maybe, we are on deleted node sequence
782 // Abort searching, try slow-path
783 return find_fastpath_abort;
788 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
792 pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
794 else if ( nCmp == 0 ) {
796 f( *node_traits::to_value_ptr( pCur.ptr() ), val );
797 return find_fastpath_found;
799 else // pCur > val - go down
805 return find_fastpath_not_found;
808 template <typename Q, typename Compare, typename Func>
809 bool find_slowpath( Q& val, Compare cmp, Func f )
812 if ( find_position( val, pos, cmp, true )) {
813 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
815 f( *node_traits::to_value_ptr( pos.pCur ), val );
822 template <typename Q, typename Compare, typename Func>
823 bool find_with_( Q& val, Compare cmp, Func f )
825 switch ( find_fastpath( val, cmp, f )) {
826 case find_fastpath_found:
827 m_Stat.onFindFastSuccess();
829 case find_fastpath_not_found:
830 m_Stat.onFindFastFailed();
836 if ( find_slowpath( val, cmp, f )) {
837 m_Stat.onFindSlowSuccess();
841 m_Stat.onFindSlowFailed();
845 template <typename Q, typename Compare>
846 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
848 return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
851 template <typename Q, typename Compare, typename Func>
852 bool erase_( Q const& val, Compare cmp, Func f )
856 if ( !find_position( val, pos, cmp, false ) ) {
857 m_Stat.onEraseFailed();
861 node_type * pDel = pos.pCur;
862 typename gc::Guard gDel;
863 gDel.assign( node_traits::to_value_ptr(pDel) );
864 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
866 unsigned int nHeight = pDel->height();
867 if ( try_remove_at( pDel, pos, f )) {
869 m_Stat.onRemoveNode( nHeight );
870 m_Stat.onEraseSuccess();
874 m_Stat.onEraseFailed();
878 template <typename Q, typename Compare>
879 bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
884 if ( !find_position( val, pos, cmp, false ) ) {
885 m_Stat.onExtractFailed();
890 node_type * pDel = pos.pCur;
891 guard.set( node_traits::to_value_ptr(pDel));
892 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
894 unsigned int nHeight = pDel->height();
895 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
897 m_Stat.onRemoveNode( nHeight );
898 m_Stat.onExtractSuccess();
901 m_Stat.onExtractRetry();
905 bool extract_min_( typename guarded_ptr::native_guard& gDel )
910 if ( !find_min_position( pos ) ) {
912 m_Stat.onExtractMinFailed();
917 node_type * pDel = pos.pCur;
919 unsigned int nHeight = pDel->height();
920 gDel.set( node_traits::to_value_ptr(pDel) );
922 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
924 m_Stat.onRemoveNode( nHeight );
925 m_Stat.onExtractMinSuccess();
929 m_Stat.onExtractMinRetry();
933 bool extract_max_( typename guarded_ptr::native_guard& gDel )
938 if ( !find_max_position( pos ) ) {
940 m_Stat.onExtractMaxFailed();
945 node_type * pDel = pos.pCur;
947 unsigned int nHeight = pDel->height();
948 gDel.set( node_traits::to_value_ptr(pDel) );
950 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
952 m_Stat.onRemoveNode( nHeight );
953 m_Stat.onExtractMaxSuccess();
957 m_Stat.onExtractMaxRetry();
961 void increase_height( unsigned int nHeight )
963 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
964 if ( nCur < nHeight )
965 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
970 /// Default constructor
972 The constructor checks whether the count of guards is enough
973 for skip-list and may raise an exception if not.
976 : m_Head( c_nMaxHeight )
977 , m_nHeight( c_nMinHeight )
979 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
981 gc::check_available_guards( c_nHazardPtrCount );
983 // Barrier for head node
984 atomics::atomic_thread_fence( memory_model::memory_order_release );
987 /// Clears and destructs the skip-list
994 ///@name Forward iterators (only for debugging purpose)
998 The forward iterator has some features:
999 - it has no post-increment operator
1000 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
1001 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
1002 may be thrown if the limit of guard count per thread is exceeded.
1003 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
1004 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
1005 deleting operations there is no guarantee that you iterate all item in the list.
1006 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
1008 @warning Use this iterator on the concurrent container for debugging purpose only.
1010 The iterator interface:
1014 // Default constructor
1018 iterator( iterator const& src );
1020 // Dereference operator
1021 value_type * operator ->() const;
1023 // Dereference operator
1024 value_type& operator *() const;
1026 // Preincrement operator
1027 iterator& operator ++();
1029 // Assignment operator
1030 iterator& operator = (iterator const& src);
1032 // Equality operators
1033 bool operator ==(iterator const& i ) const;
1034 bool operator !=(iterator const& i ) const;
1038 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
1040 /// Const iterator type
1041 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
1043 /// Returns a forward iterator addressing the first element in a set
1046 return iterator( *m_Head.head() );
1049 /// Returns a forward const iterator addressing the first element in a set
1050 const_iterator begin() const
1052 return const_iterator( *m_Head.head() );
1054 /// Returns a forward const iterator addressing the first element in a set
1055 const_iterator cbegin() const
1057 return const_iterator( *m_Head.head() );
1060 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1066 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1067 const_iterator end() const
1069 return const_iterator();
1071 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1072 const_iterator cend() const
1074 return const_iterator();
1079 /// Inserts new node
1081 The function inserts \p val in the set if it does not contain
1082 an item with key equal to \p val.
1084 Returns \p true if \p val is placed into the set, \p false otherwise.
1086 bool insert( value_type& val )
1088 return insert( val, []( value_type& ) {} );
1091 /// Inserts new node
1093 This function is intended for derived non-intrusive containers.
1095 The function allows to split creating of new item into two part:
1096 - create item with key only
1097 - insert new item into the set
1098 - if inserting is success, calls \p f functor to initialize value-field of \p val.
1100 The functor signature is:
1102 void func( value_type& val );
1104 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1105 \p val no any other changes could be made on this set's item by concurrent threads.
1106 The user-defined functor is called only if the inserting is success.
1108 template <typename Func>
1109 bool insert( value_type& val, Func f )
1111 typename gc::Guard gNew;
1112 gNew.assign( &val );
1114 node_type * pNode = node_traits::to_node_ptr( val );
1115 scoped_node_ptr scp( pNode );
1116 unsigned int nHeight = pNode->height();
1117 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1118 bool bTowerMade = false;
1123 if ( find_position( val, pos, key_comparator(), true )) {
1124 // scoped_node_ptr deletes the node tower if we create it
1128 m_Stat.onInsertFailed();
1133 build_node( pNode );
1134 nHeight = pNode->height();
1139 if ( !insert_at_position( val, pNode, pos, f )) {
1140 m_Stat.onInsertRetry();
1144 increase_height( nHeight );
1146 m_Stat.onAddNode( nHeight );
1147 m_Stat.onInsertSuccess();
1153 /// Updates the node
1155 The operation performs inserting or changing data with lock-free manner.
1157 If the item \p val is not found in the set, then \p val is inserted into the set
1158 iff \p bInsert is \p true.
1159 Otherwise, the functor \p func is called with item found.
1160 The functor \p func signature is:
1162 void func( bool bNew, value_type& item, value_type& val );
1165 - \p bNew - \p true if the item has been inserted, \p false otherwise
1166 - \p item - item of the set
1167 - \p val - argument \p val passed into the \p %update() function
1168 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1169 refer to the same thing.
1171 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1172 i.e. the node has been inserted or updated,
1173 \p second is \p true if new item has been added or \p false if the item with \p key
1176 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1178 template <typename Func>
1179 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
1181 typename gc::Guard gNew;
1182 gNew.assign( &val );
1184 node_type * pNode = node_traits::to_node_ptr( val );
1185 scoped_node_ptr scp( pNode );
1186 unsigned int nHeight = pNode->height();
1187 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1188 bool bTowerMade = false;
1193 bool bFound = find_position( val, pos, key_comparator(), true );
1195 // scoped_node_ptr deletes the node tower if we create it before
1199 func( false, *node_traits::to_value_ptr(pos.pCur), val );
1200 m_Stat.onUpdateExist();
1201 return std::make_pair( true, false );
1206 return std::make_pair( false, false );
1210 build_node( pNode );
1211 nHeight = pNode->height();
1216 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1217 m_Stat.onInsertRetry();
1221 increase_height( nHeight );
1224 m_Stat.onAddNode( nHeight );
1225 m_Stat.onUpdateNew();
1226 return std::make_pair( true, true );
1230 template <typename Func>
1231 CDS_DEPRECATED("ensure() is deprecated, use update()")
1232 std::pair<bool, bool> ensure( value_type& val, Func func )
1234 return update( val, func, true );
1238 /// Unlinks the item \p val from the set
1240 The function searches the item \p val in the set and unlink it from the set
1241 if it is found and is equal to \p val.
1243 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1244 and deletes the item found. \p %unlink() finds an item by key and deletes it
1245 only if \p val is an item of that set, i.e. the pointer to item found
1246 is equal to <tt> &val </tt>.
1248 The \p disposer specified in \p Traits class template parameter is called
1249 by garbage collector \p GC asynchronously.
1251 The function returns \p true if success and \p false otherwise.
1253 bool unlink( value_type& val )
1257 if ( !find_position( val, pos, key_comparator(), false ) ) {
1258 m_Stat.onUnlinkFailed();
1262 node_type * pDel = pos.pCur;
1263 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1265 unsigned int nHeight = pDel->height();
1266 typename gc::Guard gDel;
1267 gDel.assign( node_traits::to_value_ptr(pDel) );
1269 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1271 m_Stat.onRemoveNode( nHeight );
1272 m_Stat.onUnlinkSuccess();
1276 m_Stat.onUnlinkFailed();
1280 /// Extracts the item from the set with specified \p key
1281 /** \anchor cds_intrusive_SkipListSet_hp_extract
1282 The function searches an item with key equal to \p key in the set,
1283 unlinks it from the set, and returns it as \p guarded_ptr object.
1284 If \p key is not found the function returns an empty guarded pointer.
1286 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1288 The \p disposer specified in \p Traits class template parameter is called automatically
1289 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1290 will be destroyed or released.
1291 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1295 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1299 skip_list::guarded_ptr gp(theList.extract( 5 ));
1304 // Destructor of gp releases internal HP guard
1308 template <typename Q>
1309 guarded_ptr extract( Q const& key )
1312 extract_( gp.guard(), key, key_comparator() );
1316 /// Extracts the item from the set with comparing functor \p pred
1318 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1319 but \p pred predicate is used for key comparing.
1321 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1323 \p pred must imply the same element order as the comparator used for building the set.
1325 template <typename Q, typename Less>
1326 guarded_ptr extract_with( Q const& key, Less pred )
1330 extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1334 /// Extracts an item with minimal key from the list
1336 The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
1337 If the skip-list is empty the function returns an empty guarded pointer.
1339 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1340 It means that the function gets leftmost item and tries to unlink it.
1341 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1342 So, the function returns the item with minimum key at the moment of list traversing.
1344 The \p disposer specified in \p Traits class template parameter is called
1345 by garbage collector \p GC automatically when returned \p guarded_ptr object
1346 will be destroyed or released.
1347 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1351 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1355 skip_list::guarded_ptr gp(theList.extract_min());
1360 // Destructor of gp releases internal HP guard
1364 guarded_ptr extract_min()
1367 extract_min_( gp.guard() );
1371 /// Extracts an item with maximal key from the list
1373 The function searches an item with maximal key, unlinks it, and returns the pointer to item
1374 as \p guarded_ptr object.
1375 If the skip-list is empty the function returns an empty \p guarded_ptr.
1377 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1378 It means that the function gets rightmost item and tries to unlink it.
1379 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1380 So, the function returns the item with maximum key at the moment of list traversing.
1382 The \p disposer specified in \p Traits class template parameter is called
1383 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1384 will be destroyed or released.
1385 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1389 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1393 skip_list::guarded_ptr gp( theList.extract_max( gp ));
1398 // Destructor of gp releases internal HP guard
1402 guarded_ptr extract_max()
1405 extract_max_( gp.guard() );
1409 /// Deletes the item from the set
1410 /** \anchor cds_intrusive_SkipListSet_hp_erase
1411 The function searches an item with key equal to \p key in the set,
1412 unlinks it from the set, and returns \p true.
1413 If the item with key equal to \p key is not found the function return \p false.
1415 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1417 template <typename Q>
1418 bool erase( Q const& key )
1420 return erase_( key, key_comparator(), [](value_type const&) {} );
1423 /// Deletes the item from the set with comparing functor \p pred
1425 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1426 but \p pred predicate is used for key comparing.
1428 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1430 \p pred must imply the same element order as the comparator used for building the set.
1432 template <typename Q, typename Less>
1433 bool erase_with( Q const& key, Less pred )
1436 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1439 /// Deletes the item from the set
1440 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1441 The function searches an item with key equal to \p key in the set,
1442 call \p f functor with item found, unlinks it from the set, and returns \p true.
1443 The \ref disposer specified in \p Traits class template parameter is called
1444 by garbage collector \p GC asynchronously.
1446 The \p Func interface is
1449 void operator()( value_type const& item );
1453 If the item with key equal to \p key is not found the function return \p false.
1455 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1457 template <typename Q, typename Func>
1458 bool erase( Q const& key, Func f )
1460 return erase_( key, key_comparator(), f );
1463 /// Deletes the item from the set with comparing functor \p pred
1465 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1466 but \p pred predicate is used for key comparing.
1468 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1470 \p pred must imply the same element order as the comparator used for building the set.
1472 template <typename Q, typename Less, typename Func>
1473 bool erase_with( Q const& key, Less pred, Func f )
1476 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1480 /** \anchor cds_intrusive_SkipListSet_hp_find_func
1481 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1482 The interface of \p Func functor is:
1485 void operator()( value_type& item, Q& key );
1488 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1490 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1491 that \p item cannot be disposed during functor is executing.
1492 The functor does not serialize simultaneous access to the set \p item. If such access is
1493 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1495 Note the compare functor specified for class \p Traits template parameter
1496 should accept a parameter of type \p Q that can be not the same as \p value_type.
1498 The function returns \p true if \p key is found, \p false otherwise.
1500 template <typename Q, typename Func>
1501 bool find( Q& key, Func f )
1503 return find_with_( key, key_comparator(), f );
1506 template <typename Q, typename Func>
1507 bool find( Q const& key, Func f )
1509 return find_with_( key, key_comparator(), f );
1513 /// Finds the key \p key with \p pred predicate for comparing
1515 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1516 but \p pred is used for key compare.
1518 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1520 \p pred must imply the same element order as the comparator used for building the set.
1522 template <typename Q, typename Less, typename Func>
1523 bool find_with( Q& key, Less pred, Func f )
1526 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1529 template <typename Q, typename Less, typename Func>
1530 bool find_with( Q const& key, Less pred, Func f )
1533 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1537 /// Checks whether the set contains \p key
1539 The function searches the item with key equal to \p key
1540 and returns \p true if it is found, and \p false otherwise.
1542 template <typename Q>
1543 bool contains( Q const& key )
1545 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1548 template <typename Q>
1549 CDS_DEPRECATED("deprecated, use contains()")
1550 bool find( Q const& key )
1552 return contains( key );
1556 /// Checks whether the set contains \p key using \p pred predicate for searching
1558 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1559 \p Less functor has the interface like \p std::less.
1560 \p Less must imply the same element order as the comparator used for building the set.
1562 template <typename Q, typename Less>
1563 bool contains( Q const& key, Less pred )
1566 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1569 template <typename Q, typename Less>
1570 CDS_DEPRECATED("deprecated, use contains()")
1571 bool find_with( Q const& key, Less pred )
1573 return contains( key, pred );
1577 /// Finds \p key and return the item found
1578 /** \anchor cds_intrusive_SkipListSet_hp_get
1579 The function searches the item with key equal to \p key
1580 and returns the pointer to the item found as \p guarded_ptr.
1581 If \p key is not found the function returns an empt guarded pointer.
1583 The \p disposer specified in \p Traits class template parameter is called
1584 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1585 will be destroyed or released.
1586 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1590 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1594 skip_list::guarded_ptr gp(theList.get( 5 ));
1599 // Destructor of guarded_ptr releases internal HP guard
1603 Note the compare functor specified for class \p Traits template parameter
1604 should accept a parameter of type \p Q that can be not the same as \p value_type.
1606 template <typename Q>
1607 guarded_ptr get( Q const& key )
1610 get_with_( gp.guard(), key, key_comparator() );
1614 /// Finds \p key and return the item found
1616 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1617 but \p pred is used for comparing the keys.
1619 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1621 \p pred must imply the same element order as the comparator used for building the set.
1623 template <typename Q, typename Less>
1624 guarded_ptr get_with( Q const& key, Less pred )
1628 get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1632 /// Returns item count in the set
1634 The value returned depends on item counter type provided by \p Traits template parameter.
1635 If it is \p atomicity::empty_item_counter this function always returns 0.
1636 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1641 return m_ItemCounter;
1644 /// Checks if the set is empty
1647 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1650 /// Clears the set (not atomic)
1652 The function unlink all items from the set.
1653 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1657 assert( set.empty() );
1659 the assertion could be raised.
1661 For each item the \ref disposer will be called after unlinking.
1666 while ( extract_min_( gp.guard() ));
1669 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1670 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1672 return c_nMaxHeight;
1675 /// Returns const reference to internal statistics
1676 stat const& statistics() const
1682 }} // namespace cds::intrusive
1685 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H