3 #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H
4 #define CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/gc/nogc.h>
8 #include <cds/details/make_const_type.h>
11 namespace cds { namespace intrusive {
13 namespace michael_list {
17 - Tag - a tag used to distinguish between different implementation
19 template <typename Tag>
20 struct node<gc::nogc, Tag>
22 typedef gc::nogc gc ; ///< Garbage collector
23 typedef Tag tag ; ///< tag
25 typedef atomics::atomic< node * > atomic_ptr ; ///< atomic marked pointer
27 atomic_ptr m_pNext ; ///< pointer to the next node in the container
33 } // namespace michael_list
35 /// Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
36 /** @ingroup cds_intrusive_list
37 \anchor cds_intrusive_MichaelList_nogc
39 This specialization is intended for so-called append-only usage when no item
40 reclamation may be performed. The class does not support item removal.
42 See \ref cds_intrusive_MichaelList_hp "MichaelList" for description of template parameters.
44 template < typename T,
45 #ifdef CDS_DOXYGEN_INVOKED
46 class Traits = michael_list::traits
51 class MichaelList<gc::nogc, T, Traits>
54 typedef gc::nogc gc; ///< Garbage collector
55 typedef T value_type; ///< type of value to be stored in the queue
56 typedef Traits traits; ///< List traits
58 typedef typename traits::hook hook; ///< hook type
59 typedef typename hook::node_type node_type; ///< node type
61 # ifdef CDS_DOXYGEN_INVOKED
62 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
64 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
67 typedef typename traits::disposer disposer; ///< disposer used
68 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
69 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
71 typedef typename traits::back_off back_off; ///< back-off strategy
72 typedef typename traits::item_counter item_counter; ///< Item counting policy used
73 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
76 // Rebind traits (split-list support)
77 template <typename... Options>
78 struct rebind_traits {
82 , typename cds::opt::make_options< traits, Options...>::type
88 typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
89 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
91 atomic_node_ptr m_pHead; ///< Head pointer
92 item_counter m_ItemCounter; ///< Item counter
95 /// Position pointer for item search
97 atomic_node_ptr * pPrev ; ///< Previous node
98 node_type * pCur ; ///< Current node
99 node_type * pNext ; ///< Next node
105 static void clear_links( node_type * pNode )
107 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
110 template <class Disposer>
111 static void dispose_node( node_type * pNode, Disposer disp )
113 clear_links( pNode );
114 disp( node_traits::to_value_ptr( *pNode ));
117 template <class Disposer>
118 static void dispose_value( value_type& val, Disposer disp )
120 dispose_node( node_traits::to_node_ptr( val ), disp );
123 static bool link_node( node_type * pNode, position& pos )
125 assert( pNode != nullptr );
126 link_checker::is_empty( pNode );
128 pNode->m_pNext.store( pos.pCur, memory_model::memory_order_relaxed );
129 return pos.pPrev->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
135 template <bool IsConst>
138 friend class MichaelList;
139 value_type * m_pNode;
144 node_type * pNode = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_acquire);
146 m_pNode = node_traits::to_value_ptr( *pNode );
153 explicit iterator_type( node_type * pNode)
156 m_pNode = node_traits::to_value_ptr( *pNode );
160 explicit iterator_type( atomic_node_ptr const& refNode)
162 node_type * pNode = refNode.load(memory_model::memory_order_relaxed);
164 m_pNode = node_traits::to_value_ptr( *pNode );
170 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
171 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
177 iterator_type( const iterator_type& src )
178 : m_pNode( src.m_pNode )
181 value_ptr operator ->() const
186 value_ref operator *() const
188 assert( m_pNode != nullptr );
193 iterator_type& operator ++()
200 iterator_type operator ++(int)
202 iterator_type i(*this);
207 iterator_type& operator = (const iterator_type& src)
209 m_pNode = src.m_pNode;
214 bool operator ==(iterator_type<C> const& i ) const
216 return m_pNode == i.m_pNode;
219 bool operator !=(iterator_type<C> const& i ) const
221 return m_pNode != i.m_pNode;
228 typedef iterator_type<false> iterator;
229 /// Const forward iterator
230 typedef iterator_type<true> const_iterator;
232 /// Returns a forward iterator addressing the first element in a list
234 For empty list \code begin() == end() \endcode
238 return iterator(m_pHead.load(memory_model::memory_order_relaxed) );
241 /// Returns an iterator that addresses the location succeeding the last element in a list
243 Do not use the value returned by <tt>end</tt> function to access any item.
244 Internally, <tt>end</tt> returning value equals to \p nullptr.
246 The returned value can be used only to control reaching the end of the list.
247 For empty list \code begin() == end() \endcode
254 /// Returns a forward const iterator addressing the first element in a list
255 const_iterator begin() const
257 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
259 /// Returns a forward const iterator addressing the first element in a list
260 const_iterator cbegin() const
262 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
265 /// Returns an const iterator that addresses the location succeeding the last element in a list
266 const_iterator end() const
268 return const_iterator();
270 /// Returns an const iterator that addresses the location succeeding the last element in a list
271 const_iterator cend() const
273 return const_iterator();
277 /// Default constructor initializes empty list
281 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
284 /// Destroys the list objects
292 The function inserts \p val in the list if the list does not contain
293 an item with key equal to \p val.
295 Returns \p true if \p val is linked into the list, \p false otherwise.
297 bool insert( value_type& val )
299 return insert_at( m_pHead, val );
304 The operation performs inserting or changing data with lock-free manner.
306 If the item \p val not found in the list, then \p val is inserted into the list
307 iff \p bAllowInsert is \p true.
308 Otherwise, the functor \p func is called with item found.
309 The functor signature is:
312 void operator()( bool bNew, value_type& item, value_type& val );
316 - \p bNew - \p true if the item has been inserted, \p false otherwise
317 - \p item - item of the list
318 - \p val - argument \p val passed into the \p update() function
319 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
320 refer to the same thing.
322 The functor may change non-key fields of the \p item; however, \p func must guarantee
323 that during changing no any other modifications could be made on this item by concurrent threads.
325 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
326 \p second is \p true if new item has been added or \p false if the item with \p key
327 already is in the list.
329 template <typename Func>
330 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
332 return update_at( m_pHead, val, func, bAllowInsert );
335 template <typename Func>
336 CDS_DEPRECATED("ensure() is deprecated, use update()")
337 std::pair<bool, bool> ensure( value_type& val, Func func )
339 return update( val, func );
343 /// Finds the key \p val
344 /** \anchor cds_intrusive_MichaelList_nogc_find_func
345 The function searches the item with key equal to \p key
346 and calls the functor \p f for item found.
347 The interface of \p Func functor is:
350 void operator()( value_type& item, Q& key );
353 where \p item is the item found, \p key is the <tt>find</tt> function argument.
355 The functor can change non-key fields of \p item.
356 The function \p find does not serialize simultaneous access to the list \p item. If such access is
357 possible you must provide your own synchronization schema to exclude unsafe item modifications.
359 The function returns \p true if \p val is found, \p false otherwise.
361 template <typename Q, typename Func>
362 bool find( Q& key, Func f )
364 return find_at( m_pHead, key, key_comparator(), f );
367 template <typename Q, typename Func>
368 bool find( Q const& key, Func f )
370 return find_at( m_pHead, key, key_comparator(), f );
374 /// Finds the key \p key using \p pred predicate for searching
376 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
377 but \p pred is used for key comparing.
378 \p Less functor has the interface like \p std::less.
379 \p pred must imply the same element order as the comparator used for building the list.
381 template <typename Q, typename Less, typename Func>
382 bool find_with( Q& key, Less pred, Func f )
385 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
388 template <typename Q, typename Less, typename Func>
389 bool find_with( Q const& key, Less pred, Func f )
392 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
396 /// Checks whether the list contains \p key
398 The function searches the item with key equal to \p key
399 and returns \p true if it is found, and \p false otherwise.
401 template <typename Q>
402 value_type * contains( Q const& key )
404 return find_at( m_pHead, key, key_comparator() );
407 template <typename Q>
408 CDS_DEPRECATED("deprecated, use contains()")
409 value_type * find( Q const& key )
411 return contains( key );
415 /// Checks whether the map contains \p key using \p pred predicate for searching
417 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
418 \p Less functor has the interface like \p std::less.
419 \p Less must imply the same element order as the comparator used for building the list.
421 template <typename Q, typename Less>
422 value_type * contains( Q const& key, Less pred )
425 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
428 template <typename Q, typename Less>
429 CDS_DEPRECATED("deprecated, use contains()")
430 value_type * find_with( Q const& key, Less pred )
432 return contains( key, pred );
438 The function unlink all items from the list.
440 For each unlinked item the item disposer \p disp is called after unlinking.
442 template <typename Disposer>
443 void clear( Disposer disp )
445 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
446 do {} while ( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed ) );
449 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
450 dispose_node( pHead, disp );
456 /// Clears the list using default disposer
458 The function clears the list using default (provided in class template) disposer functor.
465 /// Checks if the list is empty
468 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
471 /// Returns list's item count
473 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
474 this function always returns 0.
476 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
477 is empty. To check list emptyness use \p empty() method.
481 return m_ItemCounter.value();
486 // split-list support
487 bool insert_aux_node( node_type * pNode )
489 return insert_aux_node( m_pHead, pNode );
492 // split-list support
493 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
495 assert( pNode != nullptr );
497 // Hack: convert node_type to value_type.
498 // In principle, auxiliary node can be non-reducible to value_type
499 // We assume that comparator can correctly distinguish aux and regular node.
500 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
503 bool insert_at( atomic_node_ptr& refHead, value_type& val )
505 link_checker::is_empty( node_traits::to_node_ptr( val ) );
509 if ( search( refHead, val, key_comparator(), pos ) )
512 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
519 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
521 if ( insert_at( refHead, val ))
522 return iterator( node_traits::to_node_ptr( val ));
526 template <typename Func>
527 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
532 if ( search( refHead, val, key_comparator(), pos ) ) {
533 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
535 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
536 return std::make_pair( iterator( pos.pCur ), false );
540 return std::make_pair( end(), false );
542 link_checker::is_empty( node_traits::to_node_ptr( val ) );
544 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
546 func( true, val , val );
547 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
553 template <typename Func>
554 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
556 std::pair<iterator, bool> ret = update_at_( refHead, val, func, bAllowInsert );
557 return std::make_pair( ret.first != end(), ret.second );
560 template <typename Q, typename Compare, typename Func>
561 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
565 if ( search( refHead, val, cmp, pos ) ) {
566 assert( pos.pCur != nullptr );
567 f( *node_traits::to_value_ptr( *pos.pCur ), val );
573 template <typename Q, typename Compare>
574 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
576 iterator it = find_at_( refHead, val, cmp );
582 template <typename Q, typename Compare>
583 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
587 if ( search( refHead, val, cmp, pos ) ) {
588 assert( pos.pCur != nullptr );
589 return iterator( pos.pCur );
599 template <typename Q, typename Compare >
600 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
602 atomic_node_ptr * pPrev;
610 pCur = pPrev->load(memory_model::memory_order_acquire);
621 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
622 if ( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext ) {
627 if ( pPrev->load(memory_model::memory_order_acquire) != pCur ) {
632 assert( pCur != nullptr );
633 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
640 pPrev = &( pCur->m_pNext );
647 }} // namespace cds::intrusive
649 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H