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/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 # ifndef CDS_CXX11_LAMBDA_SUPPORT
414 struct empty_insert_functor {
415 void operator()( value_type& )
419 struct empty_find_functor {
420 template <typename Q>
421 void operator()( value_type& item, Q& val )
425 template <typename Func>
426 struct insert_at_ensure_functor {
428 insert_at_ensure_functor( Func f ) : m_func(f) {}
430 void operator()( value_type& item )
432 cds::unref( m_func)( true, item, item );
436 # endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
438 class head_node: public node_type
440 typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
443 head_node( unsigned int nHeight )
445 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
446 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
448 node_type::make_tower( nHeight, m_Tower );
451 node_type * head() const
453 return const_cast<node_type *>( static_cast<node_type const *>(this));
458 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
459 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
460 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
466 head_node m_Head ; ///< head tower (max height)
468 item_counter m_ItemCounter ; ///< item counter
469 random_level_generator m_RandomLevelGen ; ///< random level generator instance
470 atomics::atomic<unsigned int> m_nHeight ; ///< estimated high level
471 mutable stat m_Stat ; ///< internal statistics
475 unsigned int random_level()
477 // Random generator produces a number from range [0..31]
478 // We need a number from range [1..32]
479 return m_RandomLevelGen() + 1;
482 template <typename Q>
483 node_type * build_node( Q v )
485 return node_builder::make_tower( v, m_RandomLevelGen );
488 static void dispose_node( node_type * pNode )
490 assert( pNode != nullptr );
491 typename node_builder::node_disposer()( pNode );
492 disposer()( node_traits::to_value_ptr( pNode ));
495 template <typename Q, typename Compare >
496 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
500 node_type * pCur = nullptr;
504 unsigned int nHeight = c_nMaxHeight;
506 if ( !bStrictSearch )
507 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
508 pPred = m_Head.head();
510 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
512 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
515 // end of the list at level nLevel - goto next level
519 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
521 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
522 || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
527 nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
530 else if ( nCmp == 0 && bStopIfFound )
536 pos.pPrev[ nLevel ] = pPred;
537 pos.pSucc[ nLevel ] = pCur;
545 return pCur && nCmp == 0;
548 template <typename Func>
549 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
551 unsigned int nHeight = pNode->height();
553 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
554 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
557 node_type * p = pos.pSucc[0];
558 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
559 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
562 cds::unref( f )( val );
565 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
566 node_type * p = nullptr;
568 node_type * q = pos.pSucc[ nLevel ];
570 if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
572 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
576 // Renew insert position
577 find_position( val, pos, key_comparator(), false, true );
583 template <typename Q, typename Compare, typename Func>
584 node_type * find_with_( Q& val, Compare cmp, Func f ) const
587 if ( find_position( val, pos, cmp, true, false )) {
588 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
590 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
592 m_Stat.onFindFastSuccess();
596 m_Stat.onFindFastFailed();
601 void increase_height( unsigned int nHeight )
603 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
604 while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
609 /// Default constructor
611 The constructor checks whether the count of guards is enough
612 for skip-list and may raise an exception if not.
615 : m_Head( c_nMaxHeight )
616 , m_nHeight( c_nMinHeight )
618 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
620 // Barrier for head node
621 atomics::atomic_thread_fence( memory_model::memory_order_release );
624 /// Clears and destructs the skip-list
632 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
634 /// Const iterator type
635 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
637 /// Returns a forward iterator addressing the first element in a set
640 return iterator( *m_Head.head() );
643 /// Returns a forward const iterator addressing the first element in a set
645 const_iterator begin() const
647 return const_iterator( *m_Head.head() );
649 const_iterator cbegin()
651 return const_iterator( *m_Head.head() );
655 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
661 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
663 const_iterator end() const
665 return const_iterator();
667 const_iterator cend()
669 return const_iterator();
675 iterator nonconst_end() const
684 The function inserts \p val in the set if it does not contain
685 an item with key equal to \p val.
687 Returns \p true if \p val is placed into the set, \p false otherwise.
689 bool insert( value_type& val )
691 node_type * pNode = node_traits::to_node_ptr( val );
692 scoped_node_ptr scp( pNode );
693 unsigned int nHeight = pNode->height();
694 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
695 bool bTowerMade = false;
700 bool bFound = find_position( val, pos, key_comparator(), true, true );
702 // scoped_node_ptr deletes the node tower if we create it
706 m_Stat.onInsertFailed();
712 nHeight = pNode->height();
717 # ifndef CDS_CXX11_LAMBDA_SUPPORT
718 if ( !insert_at_position( val, pNode, pos, empty_insert_functor() ))
720 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} ))
723 m_Stat.onInsertRetry();
727 increase_height( nHeight );
729 m_Stat.onAddNode( nHeight );
730 m_Stat.onInsertSuccess();
736 /// Ensures that the \p val exists in the set
738 The operation performs inserting or changing data with lock-free manner.
740 If the item \p val is not found in the set, then \p val is inserted into the set.
741 Otherwise, the functor \p func is called with item found.
742 The functor signature is:
744 void func( bool bNew, value_type& item, value_type& val );
747 - \p bNew - \p true if the item has been inserted, \p false otherwise
748 - \p item - item of the set
749 - \p val - argument \p val passed into the \p ensure function
750 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
751 refer to the same thing.
753 The functor can change non-key fields of the \p item; however, \p func must guarantee
754 that during changing no any other modifications could be made on this item by concurrent threads.
756 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
758 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
759 \p second is \p true if new item has been added or \p false if the item with \p key
760 already is in the set.
762 template <typename Func>
763 std::pair<bool, bool> ensure( value_type& val, Func func )
765 node_type * pNode = node_traits::to_node_ptr( val );
766 scoped_node_ptr scp( pNode );
767 unsigned int nHeight = pNode->height();
768 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
769 bool bTowerMade = false;
771 # ifndef CDS_CXX11_LAMBDA_SUPPORT
772 insert_at_ensure_functor<Func> wrapper( func );
778 bool bFound = find_position( val, pos, key_comparator(), true, true );
780 // scoped_node_ptr deletes the node tower if we create it before
784 cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
785 m_Stat.onEnsureExist();
786 return std::make_pair( true, false );
791 nHeight = pNode->height();
796 # ifdef CDS_CXX11_LAMBDA_SUPPORT
797 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
799 if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
802 m_Stat.onInsertRetry();
806 increase_height( nHeight );
809 m_Stat.onAddNode( nHeight );
810 m_Stat.onEnsureNew();
811 return std::make_pair( true, true );
815 /// Finds the key \p val
816 /** \anchor cds_intrusive_SkipListSet_nogc_find_func
817 The function searches the item with key equal to \p val and calls the functor \p f for item found.
818 The interface of \p Func functor is:
821 void operator()( value_type& item, Q& val );
824 where \p item is the item found, \p val is the <tt>find</tt> function argument.
826 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
828 The functor can change non-key fields of \p item. Note that the functor is only guarantee
829 that \p item cannot be disposed during functor is executing.
830 The functor does not serialize simultaneous access to the set \p item. If such access is
831 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
833 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
834 can modify both arguments.
836 Note the hash functor specified for class \p Traits template parameter
837 should accept a parameter of type \p Q that can be not the same as \p value_type.
839 The function returns \p true if \p val is found, \p false otherwise.
841 template <typename Q, typename Func>
842 bool find( Q& val, Func f ) const
844 return find_with_( val, key_comparator(), f ) != nullptr;
847 /// Finds the key \p val using \p pred predicate for comparing
849 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
850 but \p pred predicate is used for key compare.
851 \p Less has the interface like \p std::less.
852 \p pred must imply the same element order as the comparator used for building the set.
854 template <typename Q, typename Less, typename Func>
855 bool find_with( Q& val, Less pred, Func f ) const
857 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
860 /// Finds the key \p val
861 /** \anchor cds_intrusive_SkipListSet_nogc_find_cfunc
862 The function searches the item with key equal to \p val and calls the functor \p f for item found.
863 The interface of \p Func functor is:
866 void operator()( value_type& item, Q const& val );
869 where \p item is the item found, \p val is the <tt>find</tt> function argument.
871 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
873 The functor can change non-key fields of \p item. Note that the functor is only guarantee
874 that \p item cannot be disposed during functor is executing.
875 The functor does not serialize simultaneous access to the set \p item. If such access is
876 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
878 Note the hash functor specified for class \p Traits template parameter
879 should accept a parameter of type \p Q that can be not the same as \p value_type.
881 The function returns \p true if \p val is found, \p false otherwise.
883 template <typename Q, typename Func>
884 bool find( Q const& val, Func f ) const
886 return find_with_( val, key_comparator(), f ) != nullptr;
889 /// Finds the key \p val using \p pred predicate for comparing
891 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_cfunc "find(Q const&, Func)"
892 but \p pred predicate is used for key compare.
893 \p Less has the interface like \p std::less.
894 \p pred must imply the same element order as the comparator used for building the set.
896 template <typename Q, typename Less, typename Func>
897 bool find_with( Q const& val, Less pred, Func f ) const
899 return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
902 /// Finds the key \p val
903 /** \anchor cds_intrusive_SkipListSet_nogc_find_val
904 The function searches the item with key equal to \p val
905 and returns \p true if it is found, and \p false otherwise.
907 Note the hash functor specified for class \p Traits template parameter
908 should accept a parameter of type \p Q that can be not the same as \p value_type.
910 template <typename Q>
911 value_type * find( Q const& val ) const
914 # ifdef CDS_CXX11_LAMBDA_SUPPORT
915 find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
917 find_with_( val, key_comparator(), empty_find_functor() );
920 return node_traits::to_value_ptr( pNode );
924 /// Finds the key \p val using \p pred predicate for comparing
926 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
927 but \p pred predicate is used for key compare.
928 \p Less has the interface like \p std::less.
929 \p pred must imply the same element order as the comparator used for building the set.
931 template <typename Q, typename Less>
932 value_type * find_with( Q const& val, Less pred ) const
935 # ifdef CDS_CXX11_LAMBDA_SUPPORT
936 find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
938 find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
941 return node_traits::to_value_ptr( pNode );
945 /// Gets minimum key from the set
947 If the set is empty the function returns \p nullptr
949 value_type * get_min() const
951 return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
954 /// Gets maximum key from the set
956 The function returns \p nullptr if the set is empty
958 value_type * get_max() const
962 unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
963 pPred = m_Head.head();
965 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
967 node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
970 // end of the list at level nLevel - goto next level
976 return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
979 /// Clears the set (non-atomic)
981 The function is not atomic.
982 Finding and/or inserting is prohibited while clearing.
983 Otherwise an unpredictable result may be encountered.
984 Thus, \p clear() may be used only for debugging purposes.
988 node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
990 m_ItemCounter.reset();
991 m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
994 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
995 dispose_node( pNode );
1000 /// Returns item count in the set
1002 The value returned depends on item counter type provided by \p Traits template parameter.
1003 If it is atomicity::empty_item_counter this function always returns 0.
1004 The function is not suitable for checking the set emptiness, use \ref empty
1005 member function for this purpose.
1009 return m_ItemCounter;
1012 /// Checks if the set is empty
1015 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1018 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1019 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1021 return c_nMaxHeight;
1024 /// Returns const reference to internal statistics
1025 stat const& statistics() const
1031 }} // namespace cds::intrusive
1034 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H