2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 // + 1 - for help_remove()
398 static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list
401 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
402 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
406 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
408 typedef typename std::conditional<
409 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
410 ,intrusive_node_builder
411 ,typename traits::internal_node_builder
412 >::type node_builder;
414 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
417 node_type * pPrev[ c_nMaxHeight ];
418 node_type * pSucc[ c_nMaxHeight ];
420 typename gc::template GuardArray< c_nMaxHeight * 2 > guards; ///< Guards array for pPrev/pSucc
421 node_type * pCur; // guarded by one of guards
426 /// Default constructor
428 The constructor checks whether the count of guards is enough
429 for skip-list and may raise an exception if not.
432 : m_Head( c_nMaxHeight )
433 , m_nHeight( c_nMinHeight )
435 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
437 gc::check_available_guards( c_nHazardPtrCount );
439 // Barrier for head node
440 atomics::atomic_thread_fence( memory_model::memory_order_release );
443 /// Clears and destructs the skip-list
450 ///@name Forward iterators (only for debugging purpose)
454 The forward iterator has some features:
455 - it has no post-increment operator
456 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
457 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
458 may be thrown if the limit of guard count per thread is exceeded.
459 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
460 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
461 deleting operations there is no guarantee that you iterate all item in the list.
462 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
464 @warning Use this iterator on the concurrent container for debugging purpose only.
466 The iterator interface:
470 // Default constructor
474 iterator( iterator const& src );
476 // Dereference operator
477 value_type * operator ->() const;
479 // Dereference operator
480 value_type& operator *() const;
482 // Preincrement operator
483 iterator& operator ++();
485 // Assignment operator
486 iterator& operator = (iterator const& src);
488 // Equality operators
489 bool operator ==(iterator const& i ) const;
490 bool operator !=(iterator const& i ) const;
494 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
496 /// Const iterator type
497 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
499 /// Returns a forward iterator addressing the first element in a set
502 return iterator( *m_Head.head());
505 /// Returns a forward const iterator addressing the first element in a set
506 const_iterator begin() const
508 return const_iterator( *m_Head.head());
510 /// Returns a forward const iterator addressing the first element in a set
511 const_iterator cbegin() const
513 return const_iterator( *m_Head.head());
516 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
522 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
523 const_iterator end() const
525 return const_iterator();
527 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
528 const_iterator cend() const
530 return const_iterator();
537 The function inserts \p val in the set if it does not contain
538 an item with key equal to \p val.
540 Returns \p true if \p val is placed into the set, \p false otherwise.
542 bool insert( value_type& val )
544 return insert( val, []( value_type& ) {} );
549 This function is intended for derived non-intrusive containers.
551 The function allows to split creating of new item into two part:
552 - create item with key only
553 - insert new item into the set
554 - if inserting is success, calls \p f functor to initialize value-field of \p val.
556 The functor signature is:
558 void func( value_type& val );
560 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
561 \p val no any other changes could be made on this set's item by concurrent threads.
562 The user-defined functor is called only if the inserting is success.
564 template <typename Func>
565 bool insert( value_type& val, Func f )
567 typename gc::Guard gNew;
570 node_type * pNode = node_traits::to_node_ptr( val );
571 scoped_node_ptr scp( pNode );
572 unsigned int nHeight = pNode->height();
573 bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
574 bool bTowerMade = false;
579 if ( find_position( val, pos, key_comparator(), true )) {
580 // scoped_node_ptr deletes the node tower if we create it
584 m_Stat.onInsertFailed();
590 nHeight = pNode->height();
591 bTowerMade = pNode->has_tower();
595 if ( !insert_at_position( val, pNode, pos, f )) {
596 m_Stat.onInsertRetry();
600 increase_height( nHeight );
602 m_Stat.onAddNode( nHeight );
603 m_Stat.onInsertSuccess();
611 The operation performs inserting or changing data with lock-free manner.
613 If the item \p val is not found in the set, then \p val is inserted into the set
614 iff \p bInsert is \p true.
615 Otherwise, the functor \p func is called with item found.
616 The functor \p func signature is:
618 void func( bool bNew, value_type& item, value_type& val );
621 - \p bNew - \p true if the item has been inserted, \p false otherwise
622 - \p item - item of the set
623 - \p val - argument \p val passed into the \p %update() function
624 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
625 refer to the same thing.
627 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
628 i.e. the node has been inserted or updated,
629 \p second is \p true if new item has been added or \p false if the item with \p key
632 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
634 template <typename Func>
635 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
637 typename gc::Guard gNew;
640 node_type * pNode = node_traits::to_node_ptr( val );
641 scoped_node_ptr scp( pNode );
642 unsigned int nHeight = pNode->height();
643 bool bTowerOk = pNode->has_tower();
644 bool bTowerMade = false;
649 bool bFound = find_position( val, pos, key_comparator(), true );
651 // scoped_node_ptr deletes the node tower if we create it before
655 func( false, *node_traits::to_value_ptr(pos.pCur), val );
656 m_Stat.onUpdateExist();
657 return std::make_pair( true, false );
662 return std::make_pair( false, false );
667 nHeight = pNode->height();
668 bTowerMade = pNode->has_tower();
672 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
673 m_Stat.onInsertRetry();
677 increase_height( nHeight );
680 m_Stat.onAddNode( nHeight );
681 m_Stat.onUpdateNew();
682 return std::make_pair( true, true );
686 template <typename Func>
687 CDS_DEPRECATED("ensure() is deprecated, use update()")
688 std::pair<bool, bool> ensure( value_type& val, Func func )
690 return update( val, func, true );
694 /// Unlinks the item \p val from the set
696 The function searches the item \p val in the set and unlink it from the set
697 if it is found and is equal to \p val.
699 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
700 and deletes the item found. \p %unlink() finds an item by key and deletes it
701 only if \p val is an item of that set, i.e. the pointer to item found
702 is equal to <tt> &val </tt>.
704 The \p disposer specified in \p Traits class template parameter is called
705 by garbage collector \p GC asynchronously.
707 The function returns \p true if success and \p false otherwise.
709 bool unlink( value_type& val )
713 if ( !find_position( val, pos, key_comparator(), false )) {
714 m_Stat.onUnlinkFailed();
718 node_type * pDel = pos.pCur;
719 assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
721 unsigned int nHeight = pDel->height();
722 typename gc::Guard gDel;
723 gDel.assign( node_traits::to_value_ptr(pDel));
725 if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
727 m_Stat.onRemoveNode( nHeight );
728 m_Stat.onUnlinkSuccess();
732 m_Stat.onUnlinkFailed();
736 /// Extracts the item from the set with specified \p key
737 /** \anchor cds_intrusive_SkipListSet_hp_extract
738 The function searches an item with key equal to \p key in the set,
739 unlinks it from the set, and returns it as \p guarded_ptr object.
740 If \p key is not found the function returns an empty guarded pointer.
742 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
744 The \p disposer specified in \p Traits class template parameter is called automatically
745 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
746 will be destroyed or released.
747 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
751 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
755 skip_list::guarded_ptr gp(theList.extract( 5 ));
760 // Destructor of gp releases internal HP guard
764 template <typename Q>
765 guarded_ptr extract( Q const& key )
767 return extract_( key, key_comparator());
770 /// Extracts the item from the set with comparing functor \p pred
772 The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
773 but \p pred predicate is used for key comparing.
775 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
777 \p pred must imply the same element order as the comparator used for building the set.
779 template <typename Q, typename Less>
780 guarded_ptr extract_with( Q const& key, Less pred )
783 return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
786 /// Extracts an item with minimal key from the list
788 The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
789 If the skip-list is empty the function returns an empty guarded pointer.
791 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
792 It means that the function gets leftmost item and tries to unlink it.
793 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
794 So, the function returns the item with minimum key at the moment of list traversing.
796 The \p disposer specified in \p Traits class template parameter is called
797 by garbage collector \p GC automatically when returned \p guarded_ptr object
798 will be destroyed or released.
799 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
803 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
807 skip_list::guarded_ptr gp(theList.extract_min());
812 // Destructor of gp releases internal HP guard
816 guarded_ptr extract_min()
818 return extract_min_();
821 /// Extracts an item with maximal key from the list
823 The function searches an item with maximal key, unlinks it, and returns the pointer to item
824 as \p guarded_ptr object.
825 If the skip-list is empty the function returns an empty \p guarded_ptr.
827 @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
828 It means that the function gets rightmost item and tries to unlink it.
829 During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
830 So, the function returns the item with maximum key at the moment of list traversing.
832 The \p disposer specified in \p Traits class template parameter is called
833 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
834 will be destroyed or released.
835 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
839 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
843 skip_list::guarded_ptr gp( theList.extract_max( gp ));
848 // Destructor of gp releases internal HP guard
852 guarded_ptr extract_max()
854 return extract_max_();
857 /// Deletes the item from the set
858 /** \anchor cds_intrusive_SkipListSet_hp_erase
859 The function searches an item with key equal to \p key in the set,
860 unlinks it from the set, and returns \p true.
861 If the item with key equal to \p key is not found the function return \p false.
863 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
865 template <typename Q>
866 bool erase( Q const& key )
868 return erase_( key, key_comparator(), [](value_type const&) {} );
871 /// Deletes the item from the set with comparing functor \p pred
873 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
874 but \p pred predicate is used for key comparing.
876 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
878 \p pred must imply the same element order as the comparator used for building the set.
880 template <typename Q, typename Less>
881 bool erase_with( Q const& key, Less pred )
884 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
887 /// Deletes the item from the set
888 /** \anchor cds_intrusive_SkipListSet_hp_erase_func
889 The function searches an item with key equal to \p key in the set,
890 call \p f functor with item found, unlinks it from the set, and returns \p true.
891 The \ref disposer specified in \p Traits class template parameter is called
892 by garbage collector \p GC asynchronously.
894 The \p Func interface is
897 void operator()( value_type const& item );
901 If the item with key equal to \p key is not found the function return \p false.
903 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
905 template <typename Q, typename Func>
906 bool erase( Q const& key, Func f )
908 return erase_( key, key_comparator(), f );
911 /// Deletes the item from the set with comparing functor \p pred
913 The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
914 but \p pred predicate is used for key comparing.
916 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
918 \p pred must imply the same element order as the comparator used for building the set.
920 template <typename Q, typename Less, typename Func>
921 bool erase_with( Q const& key, Less pred, Func f )
924 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
928 /** \anchor cds_intrusive_SkipListSet_hp_find_func
929 The function searches the item with key equal to \p key and calls the functor \p f for item found.
930 The interface of \p Func functor is:
933 void operator()( value_type& item, Q& key );
936 where \p item is the item found, \p key is the <tt>find</tt> function argument.
938 The functor can change non-key fields of \p item. Note that the functor is only guarantee
939 that \p item cannot be disposed during functor is executing.
940 The functor does not serialize simultaneous access to the set \p item. If such access is
941 possible you must provide your own synchronization on item level to exclude unsafe item modifications.
943 Note the compare functor specified for class \p Traits template parameter
944 should accept a parameter of type \p Q that can be not the same as \p value_type.
946 The function returns \p true if \p key is found, \p false otherwise.
948 template <typename Q, typename Func>
949 bool find( Q& key, Func f )
951 return find_with_( key, key_comparator(), f );
954 template <typename Q, typename Func>
955 bool find( Q const& key, Func f )
957 return find_with_( key, key_comparator(), f );
961 /// Finds the key \p key with \p pred predicate for comparing
963 The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
964 but \p pred is used for key compare.
966 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
968 \p pred must imply the same element order as the comparator used for building the set.
970 template <typename Q, typename Less, typename Func>
971 bool find_with( Q& key, Less pred, Func f )
974 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
977 template <typename Q, typename Less, typename Func>
978 bool find_with( Q const& key, Less pred, Func f )
981 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
985 /// Checks whether the set contains \p key
987 The function searches the item with key equal to \p key
988 and returns \p true if it is found, and \p false otherwise.
990 template <typename Q>
991 bool contains( Q const& key )
993 return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
996 template <typename Q>
997 CDS_DEPRECATED("deprecated, use contains()")
998 bool find( Q const& key )
1000 return contains( key );
1004 /// Checks whether the set contains \p key using \p pred predicate for searching
1006 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1007 \p Less functor has the interface like \p std::less.
1008 \p Less must imply the same element order as the comparator used for building the set.
1010 template <typename Q, typename Less>
1011 bool contains( Q const& key, Less pred )
1014 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1017 template <typename Q, typename Less>
1018 CDS_DEPRECATED("deprecated, use contains()")
1019 bool find_with( Q const& key, Less pred )
1021 return contains( key, pred );
1025 /// Finds \p key and return the item found
1026 /** \anchor cds_intrusive_SkipListSet_hp_get
1027 The function searches the item with key equal to \p key
1028 and returns the pointer to the item found as \p guarded_ptr.
1029 If \p key is not found the function returns an empt guarded pointer.
1031 The \p disposer specified in \p Traits class template parameter is called
1032 by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1033 will be destroyed or released.
1034 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1038 typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1042 skip_list::guarded_ptr gp(theList.get( 5 ));
1047 // Destructor of guarded_ptr releases internal HP guard
1051 Note the compare functor specified for class \p Traits template parameter
1052 should accept a parameter of type \p Q that can be not the same as \p value_type.
1054 template <typename Q>
1055 guarded_ptr get( Q const& key )
1057 return get_with_( key, key_comparator());
1060 /// Finds \p key and return the item found
1062 The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1063 but \p pred is used for comparing the keys.
1065 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1067 \p pred must imply the same element order as the comparator used for building the set.
1069 template <typename Q, typename Less>
1070 guarded_ptr get_with( Q const& key, Less pred )
1073 return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
1076 /// Returns item count in the set
1078 The value returned depends on item counter type provided by \p Traits template parameter.
1079 If it is \p atomicity::empty_item_counter this function always returns 0.
1080 Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1085 return m_ItemCounter;
1088 /// Checks if the set is empty
1091 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1094 /// Clears the set (not atomic)
1096 The function unlink all items from the set.
1097 The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1101 assert( set.empty());
1103 the assertion could be raised.
1105 For each item the \ref disposer will be called after unlinking.
1109 while ( extract_min_());
1112 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1113 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1115 return c_nMaxHeight;
1118 /// Returns const reference to internal statistics
1119 stat const& statistics() const
1126 unsigned int random_level()
1128 // Random generator produces a number from range [0..31]
1129 // We need a number from range [1..32]
1130 return m_RandomLevelGen() + 1;
1133 template <typename Q>
1134 node_type * build_node( Q v )
1136 return node_builder::make_tower( v, m_RandomLevelGen );
1139 static value_type * gc_protect( marked_node_ptr p )
1141 return node_traits::to_value_ptr( p.ptr());
1144 static void dispose_node( value_type * pVal )
1146 assert( pVal != nullptr );
1147 typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ));
1151 void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur )
1153 if ( pCur->is_upper_level( nLevel )) {
1154 marked_node_ptr p( pCur.ptr());
1155 typename gc::Guard hp;
1156 marked_node_ptr pSucc = hp.protect( pCur->next( nLevel ), gc_protect );
1158 if ( pSucc.bits() &&
1159 pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
1160 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1162 if ( pCur->level_unlinked()) {
1163 gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
1164 m_Stat.onEraseWhileFind();
1170 template <typename Q, typename Compare >
1171 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
1174 marked_node_ptr pSucc;
1175 marked_node_ptr pCur;
1177 // Hazard pointer array:
1178 // pPred: [nLevel * 2]
1179 // pSucc: [nLevel * 2 + 1]
1182 pPred = m_Head.head();
1185 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1186 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1188 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1190 // pCur.bits() means that pPred is logically deleted
1194 if ( pCur.ptr() == nullptr ) {
1195 // end of list at level nLevel - goto next level
1199 // pSucc contains deletion mark for pCur
1200 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1202 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1205 if ( pSucc.bits()) {
1206 // pCur is marked, i.e. logically deleted
1207 // try to help deleting pCur
1208 help_remove( nLevel, pPred, pCur );
1212 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1215 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
1217 else if ( nCmp == 0 && bStopIfFound )
1225 pos.pPrev[nLevel] = pPred;
1226 pos.pSucc[nLevel] = pCur.ptr();
1233 pos.pCur = pCur.ptr();
1234 return pCur.ptr() && nCmp == 0;
1237 bool find_min_position( position& pos )
1240 marked_node_ptr pSucc;
1241 marked_node_ptr pCur;
1243 // Hazard pointer array:
1244 // pPred: [nLevel * 2]
1245 // pSucc: [nLevel * 2 + 1]
1248 pPred = m_Head.head();
1250 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1251 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1252 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1254 // pCur.bits() means that pPred is logically deleted
1255 // head cannot be deleted
1256 assert( pCur.bits() == 0 );
1260 // pSucc contains deletion mark for pCur
1261 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1263 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1266 if ( pSucc.bits()) {
1267 // pCur is marked, i.e. logically deleted.
1268 // try to help deleting pCur
1269 help_remove( nLevel, pPred, pCur );
1275 pos.pPrev[nLevel] = pPred;
1276 pos.pSucc[nLevel] = pCur.ptr();
1279 return ( pos.pCur = pCur.ptr()) != nullptr;
1282 bool find_max_position( position& pos )
1285 marked_node_ptr pSucc;
1286 marked_node_ptr pCur;
1288 // Hazard pointer array:
1289 // pPred: [nLevel * 2]
1290 // pSucc: [nLevel * 2 + 1]
1293 pPred = m_Head.head();
1295 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1296 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1298 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1300 // pCur.bits() means that pPred is logically deleted
1304 if ( pCur.ptr() == nullptr ) {
1305 // end of the list at level nLevel - goto next level
1309 // pSucc contains deletion mark for pCur
1310 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1312 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1315 if ( pSucc.bits()) {
1316 // pCur is marked, i.e. logically deleted.
1317 // try to help deleting pCur
1318 help_remove( nLevel, pPred, pCur );
1326 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );
1331 pos.pPrev[nLevel] = pPred;
1332 pos.pSucc[nLevel] = pCur.ptr();
1335 return ( pos.pCur = pCur.ptr()) != nullptr;
1338 bool renew_insert_position( value_type& val, node_type * pNode, position& pos )
1341 marked_node_ptr pSucc;
1342 marked_node_ptr pCur;
1345 // Hazard pointer array:
1346 // pPred: [nLevel * 2]
1347 // pSucc: [nLevel * 2 + 1]
1350 pPred = m_Head.head();
1353 for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1354 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1356 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1358 // pCur.bits() means that pPred is logically deleted
1362 if ( pCur.ptr() == nullptr ) {
1363 // end of list at level nLevel - goto next level
1367 // pSucc contains deletion mark for pCur
1368 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1370 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1373 if ( pSucc.bits()) {
1374 // pCur is marked, i.e. logically deleted
1375 if ( pCur.ptr() == pNode ) {
1376 // Node is removing while we are inserting it
1379 // try to help deleting pCur
1380 help_remove( nLevel, pPred, pCur );
1384 nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1387 pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
1395 pos.pPrev[nLevel] = pPred;
1396 pos.pSucc[nLevel] = pCur.ptr();
1402 template <typename Func>
1403 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
1405 unsigned int const nHeight = pNode->height();
1407 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
1408 pNode->next( nLevel ).store( marked_node_ptr(), memory_model::memory_order_relaxed );
1410 // Insert at level 0
1412 marked_node_ptr p( pos.pSucc[0] );
1413 pNode->next( 0 ).store( p, memory_model::memory_order_relaxed );
1414 if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1420 // Insert at level 1..max
1421 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
1424 marked_node_ptr pSucc( pos.pSucc[nLevel] );
1427 // pNode->next can have "logical deleted" flag if another thread is removing pNode right now
1428 if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc,
1429 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1431 // pNode has been marked as removed while we are inserting it
1433 assert( p.bits() != 0 );
1435 // Here pNode is linked at least level 0 so level_unlinked() cannot returns true
1436 CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
1438 // pNode is linked up to nLevel - 1
1439 // Remove it via find_position()
1440 find_position( val, pos, key_comparator(), false );
1442 m_Stat.onLogicDeleteWhileInsert();
1447 // Link pNode into the list at nLevel
1448 if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( pSucc, marked_node_ptr( pNode ),
1449 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1455 // Renew insert position
1456 m_Stat.onRenewInsertPosition();
1458 if ( !renew_insert_position( val, pNode, pos )) {
1459 // The node has been deleted while we are inserting it
1460 // Update current height for concurent removing
1461 CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
1463 m_Stat.onRemoveWhileInsert();
1465 // help to removing val
1466 find_position( val, pos, key_comparator(), false );
1474 template <typename Func>
1475 bool try_remove_at( node_type * pDel, position& pos, Func f )
1477 assert( pDel != nullptr );
1479 marked_node_ptr pSucc;
1482 // logical deletion (marking)
1483 for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
1484 pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
1485 if ( pSucc.bits() == 0 ) {
1487 while ( !( pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
1488 memory_model::memory_order_release, atomics::memory_order_acquire )
1489 || pSucc.bits() != 0 ))
1492 m_Stat.onMarkFailed();
1497 marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr());
1499 if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_acquire ))
1501 f( *node_traits::to_value_ptr( pDel ));
1503 // Physical deletion
1507 for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
1509 pSucc = pDel->next( nLevel ).load( memory_model::memory_order_acquire );
1510 if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
1511 memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
1513 pDel->level_unlinked();
1518 if ( find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ))
1519 assert( pDel != pos.pCur );
1521 find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
1523 m_Stat.onSlowErase();
1528 // Fast erasing success
1529 gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
1530 m_Stat.onFastErase();
1533 else if ( p.bits()) {
1534 // Another thread is deleting pDel right now
1535 m_Stat.onEraseContention();
1538 m_Stat.onEraseRetry();
1543 enum finsd_fastpath_result {
1544 find_fastpath_found,
1545 find_fastpath_not_found,
1548 template <typename Q, typename Compare, typename Func>
1549 finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
1552 marked_node_ptr pCur;
1553 marked_node_ptr pNull;
1556 // 0 - pPred on level N
1557 // 1 - pCur on level N
1558 typename gc::template GuardArray<2> guards;
1560 unsigned attempt = 0;
1563 pPred = m_Head.head();
1564 for ( int nLevel = static_cast<int>( m_nHeight.load( memory_model::memory_order_relaxed ) - 1 ); nLevel >= 0; --nLevel ) {
1565 pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
1567 while ( pCur != pNull ) {
1569 // pPred is being removed
1570 if ( ++attempt < 4 ) {
1575 return find_fastpath_abort;
1579 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1581 guards.copy( 0, 1 );
1583 pCur = guards.protect( 1, pCur->next( nLevel ), gc_protect );
1585 else if ( nCmp == 0 ) {
1587 f( *node_traits::to_value_ptr( pCur.ptr()), val );
1588 return find_fastpath_found;
1591 // pCur > val - go down
1598 return find_fastpath_not_found;
1601 template <typename Q, typename Compare, typename Func>
1602 bool find_slowpath( Q& val, Compare cmp, Func f )
1605 if ( find_position( val, pos, cmp, true )) {
1606 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
1608 f( *node_traits::to_value_ptr( pos.pCur ), val );
1615 template <typename Q, typename Compare, typename Func>
1616 bool find_with_( Q& val, Compare cmp, Func f )
1618 switch ( find_fastpath( val, cmp, f )) {
1619 case find_fastpath_found:
1620 m_Stat.onFindFastSuccess();
1622 case find_fastpath_not_found:
1623 m_Stat.onFindFastFailed();
1629 if ( find_slowpath( val, cmp, f )) {
1630 m_Stat.onFindSlowSuccess();
1634 m_Stat.onFindSlowFailed();
1638 template <typename Q, typename Compare>
1639 guarded_ptr get_with_( Q const& val, Compare cmp )
1642 if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ))
1644 return guarded_ptr();
1647 template <typename Q, typename Compare, typename Func>
1648 bool erase_( Q const& val, Compare cmp, Func f )
1652 if ( !find_position( val, pos, cmp, false )) {
1653 m_Stat.onEraseFailed();
1657 node_type * pDel = pos.pCur;
1658 typename gc::Guard gDel;
1659 gDel.assign( node_traits::to_value_ptr( pDel ));
1660 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1662 unsigned int nHeight = pDel->height();
1663 if ( try_remove_at( pDel, pos, f )) {
1665 m_Stat.onRemoveNode( nHeight );
1666 m_Stat.onEraseSuccess();
1670 m_Stat.onEraseFailed();
1674 template <typename Q, typename Compare>
1675 guarded_ptr extract_( Q const& val, Compare cmp )
1681 if ( !find_position( val, pos, cmp, false )) {
1682 m_Stat.onExtractFailed();
1683 return guarded_ptr();
1686 node_type * pDel = pos.pCur;
1687 gp.reset( node_traits::to_value_ptr( pDel ));
1688 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1690 unsigned int nHeight = pDel->height();
1691 if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
1693 m_Stat.onRemoveNode( nHeight );
1694 m_Stat.onExtractSuccess();
1697 m_Stat.onExtractRetry();
1701 guarded_ptr extract_min_()
1707 if ( !find_min_position( pos )) {
1708 // The list is empty
1709 m_Stat.onExtractMinFailed();
1710 return guarded_ptr();
1713 node_type * pDel = pos.pCur;
1715 unsigned int nHeight = pDel->height();
1716 gp.reset( node_traits::to_value_ptr( pDel ));
1718 if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
1720 m_Stat.onRemoveNode( nHeight );
1721 m_Stat.onExtractMinSuccess();
1725 m_Stat.onExtractMinRetry();
1729 guarded_ptr extract_max_()
1735 if ( !find_max_position( pos )) {
1736 // The list is empty
1737 m_Stat.onExtractMaxFailed();
1738 return guarded_ptr();
1741 node_type * pDel = pos.pCur;
1743 unsigned int nHeight = pDel->height();
1744 gp.reset( node_traits::to_value_ptr( pDel ));
1746 if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
1748 m_Stat.onRemoveNode( nHeight );
1749 m_Stat.onExtractMaxSuccess();
1753 m_Stat.onExtractMaxRetry();
1757 void increase_height( unsigned int nHeight )
1759 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1760 if ( nCur < nHeight )
1761 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1766 node_type* p = m_Head.head()->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
1768 node_type* pNext = p->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
1769 dispose_node( node_traits::to_value_ptr( p ));
1778 skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
1780 item_counter m_ItemCounter; ///< item counter
1781 random_level_generator m_RandomLevelGen; ///< random level generator instance
1782 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
1783 mutable stat m_Stat; ///< internal statistics
1787 }} // namespace cds::intrusive
1790 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H