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>
11 #include <cds/details/binary_functor_wrapper.h>
13 namespace cds { namespace intrusive {
17 template <typename Tag>
18 class node< cds::gc::nogc, Tag >
21 typedef cds::gc::nogc gc; ///< Garbage collector
22 typedef Tag tag; ///< tag
24 typedef atomics::atomic<node * > atomic_ptr;
25 typedef atomic_ptr tower_item_type;
28 atomic_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
29 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
30 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
33 /// Constructs a node of height 1 (a bottom-list node)
37 , m_arrNext( nullptr )
40 /// Constructs a node of height \p nHeight
41 void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
43 assert( nHeight > 0 );
44 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
45 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
48 m_arrNext = nextTower;
52 atomic_ptr * release_tower()
54 atomic_ptr * pTower = m_arrNext;
60 atomic_ptr * get_tower() const
65 /// Access to element of next pointer array
66 atomic_ptr& next( unsigned int nLevel )
68 assert( nLevel < height() );
69 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
71 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
74 /// Access to element of next pointer array (const version)
75 atomic_ptr const& next( unsigned int nLevel ) const
77 assert( nLevel < height() );
78 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
80 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
83 /// Access to element of next pointer array (same as \ref next function)
84 atomic_ptr& operator[]( unsigned int nLevel )
86 return next( nLevel );
89 /// Access to element of next pointer array (same as \ref next function)
90 atomic_ptr const& operator[]( unsigned int nLevel ) const
92 return next( nLevel );
95 /// Height of the node
96 unsigned int height() const
101 /// Clears internal links
104 assert( m_arrNext == nullptr );
105 m_pNext.store( nullptr, atomics::memory_order_release );
108 bool is_cleared() const
110 return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
111 && m_arrNext == nullptr
116 } // namespace skip_list
118 namespace skip_list { namespace details {
120 template <typename NodeTraits, typename BackOff, bool IsConst>
121 class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
124 typedef cds::gc::nogc gc;
125 typedef NodeTraits node_traits;
126 typedef BackOff back_off;
127 typedef typename node_traits::node_type node_type;
128 typedef typename node_traits::value_type value_type;
129 static bool const c_isConst = IsConst;
131 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
134 typedef typename node_type::atomic_ptr atomic_ptr;
137 public: // for internal use only!!!
138 iterator( node_type& refHead )
139 : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
142 static iterator from_node( node_type * pNode )
154 iterator( iterator const& s)
155 : m_pNode( s.m_pNode )
158 value_type * operator ->() const
160 assert( m_pNode != nullptr );
161 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
163 return node_traits::to_value_ptr( m_pNode );
166 value_ref operator *() const
168 assert( m_pNode != nullptr );
169 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
171 return *node_traits::to_value_ptr( m_pNode );
175 iterator& operator ++()
178 m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
182 iterator& operator =(const iterator& src)
184 m_pNode = src.m_pNode;
188 template <typename Bkoff, bool C>
189 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
191 return m_pNode == i.m_pNode;
193 template <typename Bkoff, bool C>
194 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
196 return !( *this == i );
199 }} // namespace skip_list::details
202 /// Lock-free skip-list set (template specialization for gc::nogc)
203 /** @ingroup cds_intrusive_map
204 @anchor cds_intrusive_SkipListSet_nogc
206 This specialization is so-called append-only when no item
207 reclamation may be performed. The class does not support deleting of list item.
209 See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
211 <b>Template arguments</b> :
212 - \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)
213 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
214 - \p Traits - type traits, default is \p skip_list::traits.
215 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
216 istead of \p Traits template argument.
220 The class supports a forward iterator (\ref iterator and \ref const_iterator).
221 The iteration is ordered.
223 The iterator class supports the following minimalistic interface:
230 iterator( iterator const& s);
232 value_type * operator ->() const;
233 value_type& operator *() const;
236 iterator& operator ++();
239 iterator& operator = (const iterator& src);
241 bool operator ==(iterator const& i ) const;
242 bool operator !=(iterator const& i ) const;
245 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
249 You should incorporate \p skip_list::node into your struct \p T and provide
250 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
251 define a struct based on \p skip_list::traits.
253 Example for base hook:
255 #include <cds/intrusive/skip_list_nogc.h>
257 // Data stored in skip list
258 struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
267 // my_data compare functor
269 int operator()( const my_data& d1, const my_data& d2 )
271 return d1.strKey.compare( d2.strKey );
274 int operator()( const my_data& d, const std::string& s )
276 return d.strKey.compare(s);
279 int operator()( const std::string& s, const my_data& d )
281 return s.compare( d.strKey );
287 struct my_traits: public cds::intrusive::skip_list::traits
289 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
290 typedef my_data_cmp compare;
293 // Declare skip-list set type
294 typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
297 Equivalent option-based code:
299 // GC-related specialization
300 #include <cds/intrusive/skip_list_nogc.h>
309 // Declare option-based skip-list set
310 typedef cds::intrusive::SkipListSet< cds::gc::nogc
312 , typename cds::intrusive::skip_list::make_traits<
313 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
314 ,cds::intrusive::opt::compare< my_data_cmp >
321 #ifdef CDS_DOXYGEN_INVOKED
322 ,typename Traits = skip_list::traits
327 class SkipListSet< cds::gc::nogc, T, Traits >
330 typedef cds::gc::nogc gc; ///< No garbage collector is used
331 typedef T value_type; ///< type of value stored in the skip-list
332 typedef Traits traits; ///< Traits template parameter
334 typedef typename traits::hook hook; ///< hook type
335 typedef typename hook::node_type node_type; ///< node type
337 # ifdef CDS_DOXYGEN_INVOKED
338 typedef implementation_defined key_comparator; ///< key comparison functor based on \p Traits::compare and \p Traits::less
340 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
342 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
344 typedef typename traits::item_counter item_counter; ///< Item counting policy
345 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
346 typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
347 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
348 typedef typename traits::back_off back_off; ///< Back-off strategy
349 typedef typename traits::stat stat; ///< internal statistics type
350 typedef typename traits::disposer disposer; ///< disposer
352 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
354 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
355 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
357 static unsigned int const c_nMaxHeight = std::conditional<
358 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
359 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
360 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
364 static unsigned int const c_nMinHeight = 3;
368 typedef typename node_type::atomic_ptr atomic_node_ptr; ///< Atomic node pointer
372 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
374 typedef typename std::conditional<
375 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
376 ,intrusive_node_builder
377 ,typename traits::internal_node_builder
378 >::type node_builder;
380 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
383 node_type * pPrev[ c_nMaxHeight ];
384 node_type * pSucc[ c_nMaxHeight ];
389 class head_node: public node_type
391 typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
394 head_node( unsigned int nHeight )
396 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
397 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
399 node_type::make_tower( nHeight, m_Tower );
402 node_type * head() const
404 return const_cast<node_type *>( static_cast<node_type const *>(this));
409 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
410 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
411 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
417 head_node m_Head; ///< head tower (max height)
419 item_counter m_ItemCounter; ///< item counter
420 random_level_generator m_RandomLevelGen; ///< random level generator instance
421 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
422 mutable stat m_Stat; ///< internal statistics
426 unsigned int random_level()
428 // Random generator produces a number from range [0..31]
429 // We need a number from range [1..32]
430 return m_RandomLevelGen() + 1;
433 template <typename Q>
434 node_type * build_node( Q v )
436 return node_builder::make_tower( v, m_RandomLevelGen );
439 static void dispose_node( node_type * pNode )
441 assert( pNode != nullptr );
442 typename node_builder::node_disposer()( pNode );
443 disposer()( node_traits::to_value_ptr( pNode ));
446 template <typename Q, typename Compare >
447 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
451 node_type * pCur = nullptr;
455 unsigned int nHeight = c_nMaxHeight;
457 if ( !bStrictSearch )
458 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
459 pPred = m_Head.head();
461 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
463 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
466 // end of the list at level nLevel - goto next level
470 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
472 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
473 || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
478 nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
481 else if ( nCmp == 0 && bStopIfFound )
487 pos.pPrev[ nLevel ] = pPred;
488 pos.pSucc[ nLevel ] = pCur;
496 return pCur && nCmp == 0;
499 template <typename Func>
500 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
502 unsigned int nHeight = pNode->height();
504 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
505 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
508 node_type * p = pos.pSucc[0];
509 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
510 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
516 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
517 node_type * p = nullptr;
519 node_type * q = pos.pSucc[ nLevel ];
521 if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
523 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
527 // Renew insert position
528 find_position( val, pos, key_comparator(), false, true );
534 template <typename Q, typename Compare, typename Func>
535 node_type * find_with_( Q& val, Compare cmp, Func f ) const
538 if ( find_position( val, pos, cmp, true, false )) {
539 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
541 f( *node_traits::to_value_ptr( pos.pCur ), val );
543 m_Stat.onFindFastSuccess();
547 m_Stat.onFindFastFailed();
552 void increase_height( unsigned int nHeight )
554 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
555 while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
560 /// Default constructor
562 The constructor checks whether the count of guards is enough
563 for skip-list and may raise an exception if not.
566 : m_Head( c_nMaxHeight )
567 , m_nHeight( c_nMinHeight )
569 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
571 // Barrier for head node
572 atomics::atomic_thread_fence( memory_model::memory_order_release );
575 /// Clears and destructs the skip-list
583 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
585 /// Const iterator type
586 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
588 /// Returns a forward iterator addressing the first element in a set
591 return iterator( *m_Head.head() );
594 /// Returns a forward const iterator addressing the first element in a set
595 const_iterator begin() const
597 return const_iterator( *m_Head.head() );
599 /// Returns a forward const iterator addressing the first element in a set
600 const_iterator cbegin() const
602 return const_iterator( *m_Head.head() );
605 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
611 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
612 const_iterator end() const
614 return const_iterator();
616 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
617 const_iterator cend() const
619 return const_iterator();
624 iterator nonconst_end() const
633 The function inserts \p val in the set if it does not contain
634 an item with key equal to \p val.
636 Returns \p true if \p val is placed into the set, \p false otherwise.
638 bool insert( value_type& val )
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 = nHeight > 1 && pNode->get_tower() != nullptr;
644 bool bTowerMade = false;
649 bool bFound = find_position( val, pos, key_comparator(), true, true );
651 // scoped_node_ptr deletes the node tower if we create it
655 m_Stat.onInsertFailed();
661 nHeight = pNode->height();
666 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
667 m_Stat.onInsertRetry();
671 increase_height( nHeight );
673 m_Stat.onAddNode( nHeight );
674 m_Stat.onInsertSuccess();
680 /// Ensures that the \p val exists in the set
682 The operation performs inserting or changing data with lock-free manner.
684 If the item \p val is not found in the set, then \p val is inserted into the set.
685 Otherwise, the functor \p func is called with item found.
686 The functor signature is:
688 void func( bool bNew, value_type& item, value_type& val );
691 - \p bNew - \p true if the item has been inserted, \p false otherwise
692 - \p item - item of the set
693 - \p val - argument \p val passed into the \p ensure function
694 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
695 refer to the same thing.
697 The functor can change non-key fields of the \p item; however, \p func must guarantee
698 that during changing no any other modifications could be made on this item by concurrent threads.
700 You can pass \p func argument by value or by reference using \p std::ref.
702 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
703 \p second is \p true if new item has been added or \p false if the item with \p key
704 already is in the set.
706 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
708 template <typename Func>
709 std::pair<bool, bool> ensure( value_type& val, Func func )
711 node_type * pNode = node_traits::to_node_ptr( val );
712 scoped_node_ptr scp( pNode );
713 unsigned int nHeight = pNode->height();
714 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
715 bool bTowerMade = false;
720 bool bFound = find_position( val, pos, key_comparator(), true, true );
722 // scoped_node_ptr deletes the node tower if we create it before
726 func( false, *node_traits::to_value_ptr(pos.pCur), val );
727 m_Stat.onEnsureExist();
728 return std::make_pair( true, false );
733 nHeight = pNode->height();
738 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
739 m_Stat.onInsertRetry();
743 increase_height( nHeight );
746 m_Stat.onAddNode( nHeight );
747 m_Stat.onEnsureNew();
748 return std::make_pair( true, true );
753 /** \anchor cds_intrusive_SkipListSet_nogc_find_func
754 The function searches the item with key equal to \p key and calls the functor \p f for item found.
755 The interface of \p Func functor is:
758 void operator()( value_type& item, Q& key );
761 where \p item is the item found, \p key is the <tt>find</tt> function argument.
763 You can pass \p f argument by value or by reference using \p std::ref.
765 The functor can change non-key fields of \p item. Note that the functor is only guarantee
766 that \p item cannot be disposed during functor is executing.
767 The functor does not serialize simultaneous access to the set \p item. If such access is
768 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
770 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
771 can modify both arguments.
773 Note the hash functor specified for class \p Traits template parameter
774 should accept a parameter of type \p Q that can be not the same as \p value_type.
776 The function returns \p true if \p key is found, \p false otherwise.
778 template <typename Q, typename Func>
779 bool find( Q& key, Func f ) const
781 return find_with_( key, key_comparator(), f ) != nullptr;
784 /// Finds the key \p key using \p pred predicate for comparing
786 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
787 but \p pred predicate is used for key compare.
788 \p Less has the interface like \p std::less.
789 \p pred must imply the same element order as the comparator used for building the set.
791 template <typename Q, typename Less, typename Func>
792 bool find_with( Q& key, Less pred, Func f ) const
794 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
798 /** \anchor cds_intrusive_SkipListSet_nogc_find_val
799 The function searches the item with key equal to \p key
800 and returns \p true if it is found, and \p false otherwise.
802 Note the hash functor specified for class \p Traits template parameter
803 should accept a parameter of type \p Q that can be not the same as \p value_type.
805 template <typename Q>
806 value_type * find( Q const& key ) const
808 node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
810 return node_traits::to_value_ptr( pNode );
814 /// Finds \p key using \p pred predicate for comparing
816 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
817 but \p pred predicate is used for key compare.
818 \p Less has the interface like \p std::less.
819 \p pred must imply the same element order as the comparator used for building the set.
821 template <typename Q, typename Less>
822 value_type * find_with( Q const& key, Less pred ) const
824 node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
826 return node_traits::to_value_ptr( pNode );
830 /// Gets minimum key from the set
832 If the set is empty the function returns \p nullptr
834 value_type * get_min() const
836 return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
839 /// Gets maximum key from the set
841 The function returns \p nullptr if the set is empty
843 value_type * get_max() const
847 unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
848 pPred = m_Head.head();
850 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
852 node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
855 // end of the list at level nLevel - goto next level
861 return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
864 /// Clears the set (non-atomic)
866 The function is not atomic.
867 Finding and/or inserting is prohibited while clearing.
868 Otherwise an unpredictable result may be encountered.
869 Thus, \p clear() may be used only for debugging purposes.
873 node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
875 m_ItemCounter.reset();
876 m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
879 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
880 dispose_node( pNode );
885 /// Returns item count in the set
887 The value returned depends on item counter type provided by \p Traits template parameter.
888 For \p atomicity::empty_item_counter the function always returns 0.
889 The function is not suitable for checking the set emptiness, use \p empty().
893 return m_ItemCounter;
896 /// Checks if the set is empty
899 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
902 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
903 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
908 /// Returns const reference to internal statistics
909 stat const& statistics() const
915 }} // namespace cds::intrusive
918 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H