3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_NOGC_H
4 #define __CDS_INTRUSIVE_SKIP_LIST_NOGC_H
8 #include <cds/gc/nogc.h>
9 #include <cds/intrusive/details/skip_list_base.h>
10 #include <cds/opt/compare.h>
12 #include <cds/details/binary_functor_wrapper.h>
14 namespace cds { namespace intrusive {
18 template <typename Tag>
19 class node< cds::gc::nogc, Tag >
22 typedef cds::gc::nogc gc ; ///< Garbage collector
23 typedef Tag tag ; ///< tag
25 typedef atomics::atomic<node * > atomic_ptr;
26 typedef atomic_ptr tower_item_type;
29 atomic_ptr m_pNext ; ///< Next item in bottom-list (list at level 0)
30 unsigned int m_nHeight ; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
31 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
34 /// Constructs a node of height 1 (a bottom-list node)
38 , m_arrNext( nullptr )
41 /// Constructs a node of height \p nHeight
42 void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
44 assert( nHeight > 0 );
45 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
46 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
49 m_arrNext = nextTower;
53 atomic_ptr * release_tower()
55 atomic_ptr * pTower = m_arrNext;
61 atomic_ptr * get_tower() const
66 /// Access to element of next pointer array
67 atomic_ptr& next( unsigned int nLevel )
69 assert( nLevel < height() );
70 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
72 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
75 /// Access to element of next pointer array (const version)
76 atomic_ptr const& next( unsigned int nLevel ) const
78 assert( nLevel < height() );
79 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
81 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
84 /// Access to element of next pointer array (same as \ref next function)
85 atomic_ptr& operator[]( unsigned int nLevel )
87 return next( nLevel );
90 /// Access to element of next pointer array (same as \ref next function)
91 atomic_ptr const& operator[]( unsigned int nLevel ) const
93 return next( nLevel );
96 /// Height of the node
97 unsigned int height() const
102 /// Clears internal links
105 assert( m_arrNext == nullptr );
106 m_pNext.store( nullptr, atomics::memory_order_release );
109 bool is_cleared() const
111 return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
112 && m_arrNext == nullptr
117 } // namespace skip_list
119 namespace skip_list { namespace details {
121 template <typename NodeTraits, typename BackOff, bool IsConst>
122 class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
125 typedef cds::gc::nogc gc;
126 typedef NodeTraits node_traits;
127 typedef BackOff back_off;
128 typedef typename node_traits::node_type node_type;
129 typedef typename node_traits::value_type value_type;
130 static bool const c_isConst = IsConst;
132 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
135 typedef typename node_type::atomic_ptr atomic_ptr;
138 public: // for internal use only!!!
139 iterator( node_type& refHead )
140 : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
143 static iterator from_node( node_type * pNode )
155 iterator( iterator const& s)
156 : m_pNode( s.m_pNode )
159 value_type * operator ->() const
161 assert( m_pNode != nullptr );
162 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
164 return node_traits::to_value_ptr( m_pNode );
167 value_ref operator *() const
169 assert( m_pNode != nullptr );
170 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
172 return *node_traits::to_value_ptr( m_pNode );
176 iterator& operator ++()
179 m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
183 iterator& operator = (const iterator& src)
185 m_pNode = src.m_pNode;
189 template <typename Bkoff, bool C>
190 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
192 return m_pNode == i.m_pNode;
194 template <typename Bkoff, bool C>
195 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
197 return !( *this == i );
200 }} // namespace skip_list::details
203 /// Lock-free skip-list set (template specialization for gc::nogc)
204 /** @ingroup cds_intrusive_map
205 @anchor cds_intrusive_SkipListSet_nogc
207 This specialization is intended for so-called persistent usage when no item
208 reclamation may be performed. The class does not support deleting of list item.
210 See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
212 <b>Template arguments</b> :
213 - \p T - type to be stored in the set. The type must be based on skip_list::node (for skip_list::base_hook)
214 or it must have a member of type skip_list::node (for skip_list::member_hook).
215 - \p Traits - type traits. See skip_list::type_traits for explanation.
217 It is possible to declare option-based list with cds::intrusive::skip_list::make_traits metafunction istead of \p Traits template
219 Template argument list \p Options of cds::intrusive::skip_list::make_traits metafunction are:
220 - opt::hook - hook used. Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
221 If the option is not specified, <tt>skip_list::base_hook<></tt> and gc::HP is used.
222 - opt::compare - key comparison functor. No default functor is provided.
223 If the option is not specified, the opt::less is used.
224 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
225 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
226 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
227 or opt::v::sequential_consistent (sequentially consisnent memory model).
228 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
229 user-provided one. See skip_list::random_level_generator option description for explanation.
230 Default is \p %skip_list::turbo_pascal.
231 - opt::allocator - although the skip-list is an intrusive container,
232 an allocator should be provided to maintain variable randomly-calculated height of the node
233 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
234 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
235 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
236 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
237 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer.
238 The disposer is used only in object destructor and in \ref clear function.
242 The class supports a forward iterator (\ref iterator and \ref const_iterator).
243 The iteration is ordered.
245 The iterator class supports the following minimalistic interface:
252 iterator( iterator const& s);
254 value_type * operator ->() const;
255 value_type& operator *() const;
258 iterator& operator ++();
261 iterator& operator = (const iterator& src);
263 bool operator ==(iterator const& i ) const;
264 bool operator !=(iterator const& i ) const;
267 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
271 You should incorporate skip_list::node into your struct \p T and provide
272 appropriate skip_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
273 define a struct based on skip_list::type_traits.
275 Example for base hook:
277 #include <cds/intrusive/skip_list_nogc.h>
279 // Data stored in skip list
280 struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
289 // my_data compare functor
291 int operator()( const my_data& d1, const my_data& d2 )
293 return d1.strKey.compare( d2.strKey );
296 int operator()( const my_data& d, const std::string& s )
298 return d.strKey.compare(s);
301 int operator()( const std::string& s, const my_data& d )
303 return s.compare( d.strKey );
308 // Declare type_traits
309 struct my_traits: public cds::intrusive::skip_list::type_traits
311 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
312 typedef my_data_cmp compare;
315 // Declare skip-list set type
316 typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
319 Equivalent option-based code:
321 // GC-related specialization
322 #include <cds/intrusive/skip_list_nogc.h>
331 // Declare option-based skip-list set
332 typedef cds::intrusive::SkipListSet< cds::gc::nogc
334 , typename cds::intrusive::skip_list::make_traits<
335 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
336 ,cds::intrusive::opt::compare< my_data_cmp >
345 #ifdef CDS_DOXYGEN_INVOKED
346 ,typename Traits = skip_list::type_traits
351 class SkipListSet< cds::gc::nogc, T, Traits >
354 typedef T value_type ; ///< type of value stored in the skip-list
355 typedef Traits options ; ///< Traits template parameter
357 typedef typename options::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, options >::type key_comparator;
365 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
367 typedef cds::gc::nogc gc ; ///< No garbage collector is used
368 typedef typename options::item_counter item_counter ; ///< Item counting policy used
369 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
370 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
371 typedef typename options::allocator allocator_type ; ///< allocator for maintaining array of next pointers of the node
372 typedef typename options::back_off back_off ; ///< Back-off trategy
373 typedef typename options::stat stat ; ///< internal statistics type
374 typedef typename options::disposer disposer ; ///< disposer used
376 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
378 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
379 but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
381 static unsigned int const c_nMaxHeight = std::conditional<
382 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
383 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
384 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
388 static unsigned int const c_nMinHeight = 3;
392 typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
396 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
398 typedef typename std::conditional<
399 std::is_same< typename options::internal_node_builder, cds::opt::none >::value
400 ,intrusive_node_builder
401 ,typename options::internal_node_builder
402 >::type node_builder;
404 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
407 node_type * pPrev[ c_nMaxHeight ];
408 node_type * pSucc[ c_nMaxHeight ];
413 class head_node: public node_type
415 typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
418 head_node( unsigned int nHeight )
420 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
421 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
423 node_type::make_tower( nHeight, m_Tower );
426 node_type * head() const
428 return const_cast<node_type *>( static_cast<node_type const *>(this));
433 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
434 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
435 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
441 head_node m_Head ; ///< head tower (max height)
443 item_counter m_ItemCounter ; ///< item counter
444 random_level_generator m_RandomLevelGen ; ///< random level generator instance
445 atomics::atomic<unsigned int> m_nHeight ; ///< estimated high level
446 mutable stat m_Stat ; ///< internal statistics
450 unsigned int random_level()
452 // Random generator produces a number from range [0..31]
453 // We need a number from range [1..32]
454 return m_RandomLevelGen() + 1;
457 template <typename Q>
458 node_type * build_node( Q v )
460 return node_builder::make_tower( v, m_RandomLevelGen );
463 static void dispose_node( node_type * pNode )
465 assert( pNode != nullptr );
466 typename node_builder::node_disposer()( pNode );
467 disposer()( node_traits::to_value_ptr( pNode ));
470 template <typename Q, typename Compare >
471 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
475 node_type * pCur = nullptr;
479 unsigned int nHeight = c_nMaxHeight;
481 if ( !bStrictSearch )
482 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
483 pPred = m_Head.head();
485 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
487 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
490 // end of the list at level nLevel - goto next level
494 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
496 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
497 || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
502 nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
505 else if ( nCmp == 0 && bStopIfFound )
511 pos.pPrev[ nLevel ] = pPred;
512 pos.pSucc[ nLevel ] = pCur;
520 return pCur && nCmp == 0;
523 template <typename Func>
524 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
526 unsigned int nHeight = pNode->height();
528 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
529 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
532 node_type * p = pos.pSucc[0];
533 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
534 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
537 cds::unref( f )( val );
540 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
541 node_type * p = nullptr;
543 node_type * q = pos.pSucc[ nLevel ];
545 if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
547 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
551 // Renew insert position
552 find_position( val, pos, key_comparator(), false, true );
558 template <typename Q, typename Compare, typename Func>
559 node_type * find_with_( Q& val, Compare cmp, Func f ) const
562 if ( find_position( val, pos, cmp, true, false )) {
563 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
565 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
567 m_Stat.onFindFastSuccess();
571 m_Stat.onFindFastFailed();
576 void increase_height( unsigned int nHeight )
578 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
579 while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
584 /// Default constructor
586 The constructor checks whether the count of guards is enough
587 for skip-list and may raise an exception if not.
590 : m_Head( c_nMaxHeight )
591 , m_nHeight( c_nMinHeight )
593 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
595 // Barrier for head node
596 atomics::atomic_thread_fence( memory_model::memory_order_release );
599 /// Clears and destructs the skip-list
607 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
609 /// Const iterator type
610 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
612 /// Returns a forward iterator addressing the first element in a set
615 return iterator( *m_Head.head() );
618 /// Returns a forward const iterator addressing the first element in a set
620 const_iterator begin() const
622 return const_iterator( *m_Head.head() );
624 const_iterator cbegin()
626 return const_iterator( *m_Head.head() );
630 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
636 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
638 const_iterator end() const
640 return const_iterator();
642 const_iterator cend()
644 return const_iterator();
650 iterator nonconst_end() const
659 The function inserts \p val in the set if it does not contain
660 an item with key equal to \p val.
662 Returns \p true if \p val is placed into the set, \p false otherwise.
664 bool insert( value_type& val )
666 node_type * pNode = node_traits::to_node_ptr( val );
667 scoped_node_ptr scp( pNode );
668 unsigned int nHeight = pNode->height();
669 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
670 bool bTowerMade = false;
675 bool bFound = find_position( val, pos, key_comparator(), true, true );
677 // scoped_node_ptr deletes the node tower if we create it
681 m_Stat.onInsertFailed();
687 nHeight = pNode->height();
692 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
693 m_Stat.onInsertRetry();
697 increase_height( nHeight );
699 m_Stat.onAddNode( nHeight );
700 m_Stat.onInsertSuccess();
706 /// Ensures that the \p val exists in the set
708 The operation performs inserting or changing data with lock-free manner.
710 If the item \p val is not found in the set, then \p val is inserted into the set.
711 Otherwise, the functor \p func is called with item found.
712 The functor signature is:
714 void func( bool bNew, value_type& item, value_type& val );
717 - \p bNew - \p true if the item has been inserted, \p false otherwise
718 - \p item - item of the set
719 - \p val - argument \p val passed into the \p ensure function
720 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
721 refer to the same thing.
723 The functor can change non-key fields of the \p item; however, \p func must guarantee
724 that during changing no any other modifications could be made on this item by concurrent threads.
726 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
728 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
729 \p second is \p true if new item has been added or \p false if the item with \p key
730 already is in the set.
732 template <typename Func>
733 std::pair<bool, bool> ensure( value_type& val, Func func )
735 node_type * pNode = node_traits::to_node_ptr( val );
736 scoped_node_ptr scp( pNode );
737 unsigned int nHeight = pNode->height();
738 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
739 bool bTowerMade = false;
744 bool bFound = find_position( val, pos, key_comparator(), true, true );
746 // scoped_node_ptr deletes the node tower if we create it before
750 cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
751 m_Stat.onEnsureExist();
752 return std::make_pair( true, false );
757 nHeight = pNode->height();
762 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); })) {
763 m_Stat.onInsertRetry();
767 increase_height( nHeight );
770 m_Stat.onAddNode( nHeight );
771 m_Stat.onEnsureNew();
772 return std::make_pair( true, true );
776 /// Finds the key \p val
777 /** \anchor cds_intrusive_SkipListSet_nogc_find_func
778 The function searches the item with key equal to \p val and calls the functor \p f for item found.
779 The interface of \p Func functor is:
782 void operator()( value_type& item, Q& val );
785 where \p item is the item found, \p val is the <tt>find</tt> function argument.
787 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
789 The functor can change non-key fields of \p item. Note that the functor is only guarantee
790 that \p item cannot be disposed during functor is executing.
791 The functor does not serialize simultaneous access to the set \p item. If such access is
792 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
794 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
795 can modify both arguments.
797 Note the hash functor specified for class \p Traits template parameter
798 should accept a parameter of type \p Q that can be not the same as \p value_type.
800 The function returns \p true if \p val is found, \p false otherwise.
802 template <typename Q, typename Func>
803 bool find( Q& val, Func f ) const
805 return find_with_( val, key_comparator(), f ) != nullptr;
808 /// Finds the key \p val using \p pred predicate for comparing
810 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
811 but \p pred predicate is used for key compare.
812 \p Less has the interface like \p std::less.
813 \p pred must imply the same element order as the comparator used for building the set.
815 template <typename Q, typename Less, typename Func>
816 bool find_with( Q& val, Less pred, Func f ) const
818 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
821 /// Finds the key \p val
822 /** \anchor cds_intrusive_SkipListSet_nogc_find_cfunc
823 The function searches the item with key equal to \p val and calls the functor \p f for item found.
824 The interface of \p Func functor is:
827 void operator()( value_type& item, Q const& val );
830 where \p item is the item found, \p val is the <tt>find</tt> function argument.
832 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
834 The functor can change non-key fields of \p item. Note that the functor is only guarantee
835 that \p item cannot be disposed during functor is executing.
836 The functor does not serialize simultaneous access to the set \p item. If such access is
837 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
839 Note the hash functor specified for class \p Traits template parameter
840 should accept a parameter of type \p Q that can be not the same as \p value_type.
842 The function returns \p true if \p val is found, \p false otherwise.
844 template <typename Q, typename Func>
845 bool find( Q const& val, Func f ) const
847 return find_with_( val, key_comparator(), f ) != nullptr;
850 /// Finds the key \p val using \p pred predicate for comparing
852 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_cfunc "find(Q const&, Func)"
853 but \p pred predicate is used for key compare.
854 \p Less has the interface like \p std::less.
855 \p pred must imply the same element order as the comparator used for building the set.
857 template <typename Q, typename Less, typename Func>
858 bool find_with( Q const& val, Less pred, Func f ) const
860 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
863 /// Finds the key \p val
864 /** \anchor cds_intrusive_SkipListSet_nogc_find_val
865 The function searches the item with key equal to \p val
866 and returns \p true if it is found, and \p false otherwise.
868 Note the hash functor specified for class \p Traits template parameter
869 should accept a parameter of type \p Q that can be not the same as \p value_type.
871 template <typename Q>
872 value_type * find( Q const& val ) const
874 node_type * pNode = find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
876 return node_traits::to_value_ptr( pNode );
880 /// Finds the key \p val using \p pred predicate for comparing
882 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
883 but \p pred predicate is used for key compare.
884 \p Less has the interface like \p std::less.
885 \p pred must imply the same element order as the comparator used for building the set.
887 template <typename Q, typename Less>
888 value_type * find_with( Q const& val, Less pred ) const
890 node_type * pNode = find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
892 return node_traits::to_value_ptr( pNode );
896 /// Gets minimum key from the set
898 If the set is empty the function returns \p nullptr
900 value_type * get_min() const
902 return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
905 /// Gets maximum key from the set
907 The function returns \p nullptr if the set is empty
909 value_type * get_max() const
913 unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
914 pPred = m_Head.head();
916 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
918 node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
921 // end of the list at level nLevel - goto next level
927 return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
930 /// Clears the set (non-atomic)
932 The function is not atomic.
933 Finding and/or inserting is prohibited while clearing.
934 Otherwise an unpredictable result may be encountered.
935 Thus, \p clear() may be used only for debugging purposes.
939 node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
941 m_ItemCounter.reset();
942 m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
945 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
946 dispose_node( pNode );
951 /// Returns item count in the set
953 The value returned depends on item counter type provided by \p Traits template parameter.
954 If it is atomicity::empty_item_counter this function always returns 0.
955 The function is not suitable for checking the set emptiness, use \ref empty
956 member function for this purpose.
960 return m_ItemCounter;
963 /// Checks if the set is empty
966 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
969 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
970 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
975 /// Returns const reference to internal statistics
976 stat const& statistics() const
982 }} // namespace cds::intrusive
985 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H