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_SKIP_LIST_NOGC_H
32 #define CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
34 #include <type_traits>
36 #include <cds/gc/nogc.h>
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 {
45 template <typename Tag>
46 class node< cds::gc::nogc, Tag >
49 typedef cds::gc::nogc gc; ///< Garbage collector
50 typedef Tag tag; ///< tag
52 typedef atomics::atomic<node * > atomic_ptr;
53 typedef atomic_ptr tower_item_type;
56 atomic_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
57 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
58 atomic_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
61 /// Constructs a node of height 1 (a bottom-list node)
65 , m_arrNext( nullptr )
68 /// Constructs a node of height \p nHeight
69 void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
71 assert( nHeight > 0 );
72 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
73 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
76 m_arrNext = nextTower;
80 atomic_ptr * release_tower()
82 atomic_ptr * pTower = m_arrNext;
88 atomic_ptr * get_tower() const
93 /// Access to element of next pointer array
94 atomic_ptr& next( unsigned int nLevel )
96 assert( nLevel < height() );
97 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
99 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
102 /// Access to element of next pointer array (const version)
103 atomic_ptr const& next( unsigned int nLevel ) const
105 assert( nLevel < height() );
106 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
108 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
111 /// Access to element of next pointer array (same as \ref next function)
112 atomic_ptr& operator[]( unsigned int nLevel )
114 return next( nLevel );
117 /// Access to element of next pointer array (same as \ref next function)
118 atomic_ptr const& operator[]( unsigned int nLevel ) const
120 return next( nLevel );
123 /// Height of the node
124 unsigned int height() const
129 /// Clears internal links
132 assert( m_arrNext == nullptr );
133 m_pNext.store( nullptr, atomics::memory_order_release );
136 bool is_cleared() const
138 return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
139 && m_arrNext == nullptr
144 } // namespace skip_list
146 namespace skip_list { namespace details {
148 template <typename NodeTraits, typename BackOff, bool IsConst>
149 class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
152 typedef cds::gc::nogc gc;
153 typedef NodeTraits node_traits;
154 typedef BackOff back_off;
155 typedef typename node_traits::node_type node_type;
156 typedef typename node_traits::value_type value_type;
157 static CDS_CONSTEXPR bool const c_isConst = IsConst;
159 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
160 friend class iterator< gc, node_traits, back_off, !c_isConst >;
163 typedef typename node_type::atomic_ptr atomic_ptr;
166 public: // for internal use only!!!
167 iterator( node_type& refHead )
168 : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
171 static iterator from_node( node_type * pNode )
183 iterator( iterator const& s)
184 : m_pNode( s.m_pNode )
187 value_type * operator ->() const
189 assert( m_pNode != nullptr );
190 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
192 return node_traits::to_value_ptr( m_pNode );
195 value_ref operator *() const
197 assert( m_pNode != nullptr );
198 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
200 return *node_traits::to_value_ptr( m_pNode );
204 iterator& operator ++()
207 m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
211 iterator& operator =(const iterator& src)
213 m_pNode = src.m_pNode;
217 template <typename Bkoff, bool C>
218 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
220 return m_pNode == i.m_pNode;
222 template <typename Bkoff, bool C>
223 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
225 return !( *this == i );
228 }} // namespace skip_list::details
231 /// Lock-free skip-list set (template specialization for gc::nogc)
232 /** @ingroup cds_intrusive_map
233 @anchor cds_intrusive_SkipListSet_nogc
235 This specialization is so-called append-only when no item
236 reclamation may be performed. The class does not support deleting of list item.
238 See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
240 <b>Template arguments</b> :
241 - \p T - type to be stored in the set. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
242 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
243 - \p Traits - type traits, default is \p skip_list::traits.
244 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
245 istead of \p Traits template argument.
249 The class supports a forward iterator (\ref iterator and \ref const_iterator).
250 The iteration is ordered.
252 The iterator class supports the following minimalistic interface:
259 iterator( iterator const& s);
261 value_type * operator ->() const;
262 value_type& operator *() const;
265 iterator& operator ++();
268 iterator& operator = (const iterator& src);
270 bool operator ==(iterator const& i ) const;
271 bool operator !=(iterator const& i ) const;
274 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
278 You should incorporate \p skip_list::node into your struct \p T and provide
279 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
280 define a struct based on \p skip_list::traits.
282 Example for base hook:
284 #include <cds/intrusive/skip_list_nogc.h>
286 // Data stored in skip list
287 struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
296 // my_data compare functor
298 int operator()( const my_data& d1, const my_data& d2 )
300 return d1.strKey.compare( d2.strKey );
303 int operator()( const my_data& d, const std::string& s )
305 return d.strKey.compare(s);
308 int operator()( const std::string& s, const my_data& d )
310 return s.compare( d.strKey );
316 struct my_traits: public cds::intrusive::skip_list::traits
318 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
319 typedef my_data_cmp compare;
322 // Declare skip-list set type
323 typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
326 Equivalent option-based code:
328 // GC-related specialization
329 #include <cds/intrusive/skip_list_nogc.h>
338 // Declare option-based skip-list set
339 typedef cds::intrusive::SkipListSet< cds::gc::nogc
341 , typename cds::intrusive::skip_list::make_traits<
342 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
343 ,cds::intrusive::opt::compare< my_data_cmp >
350 #ifdef CDS_DOXYGEN_INVOKED
351 ,typename Traits = skip_list::traits
356 class SkipListSet< cds::gc::nogc, T, Traits >
359 typedef cds::gc::nogc gc; ///< No garbage collector is used
360 typedef T value_type; ///< type of value stored in the skip-list
361 typedef Traits traits; ///< Traits template parameter
363 typedef typename traits::hook hook; ///< hook type
364 typedef typename hook::node_type node_type; ///< node type
366 # ifdef CDS_DOXYGEN_INVOKED
367 typedef implementation_defined key_comparator; ///< key comparison functor based on \p Traits::compare and \p Traits::less
369 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
371 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
373 typedef typename traits::item_counter item_counter; ///< Item counting policy
374 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
375 typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
376 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
377 typedef typename traits::back_off back_off; ///< Back-off strategy
378 typedef typename traits::stat stat; ///< internal statistics type
379 typedef typename traits::disposer disposer; ///< disposer
381 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
383 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
384 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
386 static unsigned int const c_nMaxHeight = std::conditional<
387 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
388 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
389 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
393 static unsigned int const c_nMinHeight = 3;
397 typedef typename node_type::atomic_ptr atomic_node_ptr; ///< Atomic node pointer
401 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
403 typedef typename std::conditional<
404 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
405 ,intrusive_node_builder
406 ,typename traits::internal_node_builder
407 >::type node_builder;
409 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
412 node_type * pPrev[ c_nMaxHeight ];
413 node_type * pSucc[ c_nMaxHeight ];
418 class head_node: public node_type
420 typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
423 head_node( unsigned int nHeight )
425 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
426 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
428 node_type::make_tower( nHeight, m_Tower );
431 node_type * head() const
433 return const_cast<node_type *>( static_cast<node_type const *>(this));
438 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
439 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
440 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
446 head_node m_Head; ///< head tower (max height)
448 item_counter m_ItemCounter; ///< item counter
449 random_level_generator m_RandomLevelGen; ///< random level generator instance
450 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
451 mutable stat m_Stat; ///< internal statistics
455 unsigned int random_level()
457 // Random generator produces a number from range [0..31]
458 // We need a number from range [1..32]
459 return m_RandomLevelGen() + 1;
462 template <typename Q>
463 node_type * build_node( Q v )
465 return node_builder::make_tower( v, m_RandomLevelGen );
468 static void dispose_node( node_type * pNode )
470 assert( pNode != nullptr );
471 typename node_builder::node_disposer()( pNode );
472 disposer()( node_traits::to_value_ptr( pNode ));
475 template <typename Q, typename Compare >
476 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
480 node_type * pCur = nullptr;
484 unsigned int nHeight = c_nMaxHeight;
486 if ( !bStrictSearch )
487 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
488 pPred = m_Head.head();
490 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
492 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
495 // end of the list at level nLevel - goto next level
499 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
501 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
502 || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
507 nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
510 else if ( nCmp == 0 && bStopIfFound )
516 pos.pPrev[ nLevel ] = pPred;
517 pos.pSucc[ nLevel ] = pCur;
525 return pCur && nCmp == 0;
528 template <typename Func>
529 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
531 unsigned int nHeight = pNode->height();
533 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
534 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
537 node_type * p = pos.pSucc[0];
538 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
539 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
545 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
546 node_type * p = nullptr;
548 node_type * q = pos.pSucc[ nLevel ];
550 if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
552 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
556 // Renew insert position
557 find_position( val, pos, key_comparator(), false, true );
563 template <typename Q, typename Compare, typename Func>
564 node_type * find_with_( Q& val, Compare cmp, Func f ) const
567 if ( find_position( val, pos, cmp, true, false )) {
568 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
570 f( *node_traits::to_value_ptr( pos.pCur ), val );
572 m_Stat.onFindFastSuccess();
576 m_Stat.onFindFastFailed();
581 void increase_height( unsigned int nHeight )
583 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
584 while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
589 /// Default constructor
591 The constructor checks whether the count of guards is enough
592 for skip-list and may raise an exception if not.
595 : m_Head( c_nMaxHeight )
596 , m_nHeight( c_nMinHeight )
598 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
600 // Barrier for head node
601 atomics::atomic_thread_fence( memory_model::memory_order_release );
604 /// Clears and destructs the skip-list
612 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
614 /// Const iterator type
615 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
617 /// Returns a forward iterator addressing the first element in a set
620 return iterator( *m_Head.head() );
623 /// Returns a forward const iterator addressing the first element in a set
624 const_iterator begin() const
626 return const_iterator( *m_Head.head() );
628 /// Returns a forward const iterator addressing the first element in a set
629 const_iterator cbegin() const
631 return const_iterator( *m_Head.head() );
634 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
640 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
641 const_iterator end() const
643 return const_iterator();
645 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
646 const_iterator cend() const
648 return const_iterator();
653 iterator nonconst_end() const
662 The function inserts \p val in the set if it does not contain
663 an item with key equal to \p val.
665 Returns \p true if \p val is placed into the set, \p false otherwise.
667 bool insert( value_type& val )
669 node_type * pNode = node_traits::to_node_ptr( val );
670 scoped_node_ptr scp( pNode );
671 unsigned int nHeight = pNode->height();
672 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
673 bool bTowerMade = false;
678 bool bFound = find_position( val, pos, key_comparator(), true, true );
680 // scoped_node_ptr deletes the node tower if we create it
684 m_Stat.onInsertFailed();
690 nHeight = pNode->height();
695 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
696 m_Stat.onInsertRetry();
700 increase_height( nHeight );
702 m_Stat.onAddNode( nHeight );
703 m_Stat.onInsertSuccess();
711 The operation performs inserting or changing data with lock-free manner.
713 If the item \p val is not found in the set, then \p val is inserted into the set
714 iff \p bInsert is \p true.
715 Otherwise, the functor \p func is called with item found.
716 The functor signature is:
718 void func( bool bNew, value_type& item, value_type& val );
721 - \p bNew - \p true if the item has been inserted, \p false otherwise
722 - \p item - item of the set
723 - \p val - argument \p val passed into the \p %update() function
724 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
725 refer to the same thing.
727 The functor can change non-key fields of the \p item; however, \p func must guarantee
728 that during changing no any other modifications could be made on this item by concurrent threads.
730 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
731 \p second is \p true if new item has been added or \p false if the item with \p key
732 already is in the set.
734 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
736 template <typename Func>
737 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
739 node_type * pNode = node_traits::to_node_ptr( val );
740 scoped_node_ptr scp( pNode );
741 unsigned int nHeight = pNode->height();
742 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
743 bool bTowerMade = false;
748 bool bFound = find_position( val, pos, key_comparator(), true, true );
750 // scoped_node_ptr deletes the node tower if we create it before
754 func( false, *node_traits::to_value_ptr(pos.pCur), val );
755 m_Stat.onUpdateExist();
756 return std::make_pair( true, false );
761 return std::make_pair( false, false );
766 nHeight = pNode->height();
771 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
772 m_Stat.onInsertRetry();
776 increase_height( nHeight );
779 m_Stat.onAddNode( nHeight );
780 m_Stat.onUpdateNew();
781 return std::make_pair( true, true );
785 template <typename Func>
786 CDS_DEPRECATED("ensure() is deprecated, use update()")
787 std::pair<bool, bool> ensure( value_type& val, Func func )
789 return update( val, func, true );
794 /** \anchor cds_intrusive_SkipListSet_nogc_find_func
795 The function searches the item with key equal to \p key and calls the functor \p f for item found.
796 The interface of \p Func functor is:
799 void operator()( value_type& item, Q& key );
802 where \p item is the item found, \p key is the <tt>find</tt> function argument.
804 The functor can change non-key fields of \p item. Note that the functor is only guarantee
805 that \p item cannot be disposed during functor is executing.
806 The functor does not serialize simultaneous access to the set \p item. If such access is
807 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
809 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
810 can modify both arguments.
812 Note the hash functor specified for class \p Traits template parameter
813 should accept a parameter of type \p Q that can be not the same as \p value_type.
815 The function returns \p true if \p key is found, \p false otherwise.
817 template <typename Q, typename Func>
818 bool find( Q& key, Func f ) const
820 return find_with_( key, key_comparator(), f ) != nullptr;
823 template <typename Q, typename Func>
824 bool find( Q const& key, Func f ) const
826 return find_with_( key, key_comparator(), f ) != nullptr;
830 /// Finds the key \p key using \p pred predicate for comparing
832 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
833 but \p pred predicate is used for key compare.
834 \p Less has the interface like \p std::less.
835 \p pred must imply the same element order as the comparator used for building the set.
837 template <typename Q, typename Less, typename Func>
838 bool find_with( Q& key, Less pred, Func f ) const
841 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
844 template <typename Q, typename Less, typename Func>
845 bool find_with( Q const& key, Less pred, Func f ) const
848 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
852 /// Checks whether the set contains \p key
854 The function searches the item with key equal to \p key
855 and returns pointer to item found or \p nullptr.
857 template <typename Q>
858 value_type * contains( Q const& key ) const
860 node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
862 return node_traits::to_value_ptr( pNode );
866 template <typename Q>
867 CDS_DEPRECATED("deprecated, use contains()")
868 value_type * find( Q const& key ) const
870 return contains( key );
874 /// Checks whether the set contains \p key using \p pred predicate for searching
876 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
877 \p Less functor has the interface like \p std::less.
878 \p Less must imply the same element order as the comparator used for building the set.
880 template <typename Q, typename Less>
881 value_type * contains( Q const& key, Less pred ) const
884 node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
886 return node_traits::to_value_ptr( pNode );
890 template <typename Q, typename Less>
891 CDS_DEPRECATED("deprecated, use contains()")
892 value_type * find_with( Q const& key, Less pred ) const
894 return contains( key, pred );
898 /// Gets minimum key from the set
900 If the set is empty the function returns \p nullptr
902 value_type * get_min() const
904 return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
907 /// Gets maximum key from the set
909 The function returns \p nullptr if the set is empty
911 value_type * get_max() const
915 unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
916 pPred = m_Head.head();
918 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
920 node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
923 // end of the list at level nLevel - goto next level
929 return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
932 /// Clears the set (non-atomic)
934 The function is not atomic.
935 Finding and/or inserting is prohibited while clearing.
936 Otherwise an unpredictable result may be encountered.
937 Thus, \p clear() may be used only for debugging purposes.
941 node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
943 m_ItemCounter.reset();
944 m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
947 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
948 dispose_node( pNode );
953 /// Returns item count in the set
955 The value returned depends on item counter type provided by \p Traits template parameter.
956 For \p atomicity::empty_item_counter the function always returns 0.
957 The function is not suitable for checking the set emptiness, use \p empty().
961 return m_ItemCounter;
964 /// Checks if the set is empty
967 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
970 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
971 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
976 /// Returns const reference to internal statistics
977 stat const& statistics() const
983 }} // namespace cds::intrusive
986 #endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_IMPL_H