3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H
4 #define __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/gc/nogc.h>
9 namespace cds { namespace intrusive {
11 namespace michael_list {
15 - Tag - a tag used to distinguish between different implementation
17 template <typename Tag>
18 struct node<gc::nogc, Tag>
20 typedef gc::nogc gc ; ///< Garbage collector
21 typedef Tag tag ; ///< tag
23 typedef atomics::atomic< node * > atomic_ptr ; ///< atomic marked pointer
25 atomic_ptr m_pNext ; ///< pointer to the next node in the container
32 } // namespace michael_list
34 /// Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
35 /** @ingroup cds_intrusive_list
36 \anchor cds_intrusive_MichaelList_nogc
38 This specialization is intended for so-called persistent usage when no item
39 reclamation may be performed. The class does not support deleting of item.
41 See \ref cds_intrusive_MichaelList_hp "MichaelList" for description of template parameters.
43 The interface of the specialization is a slightly different.
45 template < typename T, class Traits >
46 class MichaelList<gc::nogc, T, Traits>
49 typedef T value_type ; ///< type of value stored in the queue
50 typedef Traits options ; ///< Traits template parameter
52 typedef typename options::hook hook ; ///< hook type
53 typedef typename hook::node_type node_type ; ///< node type
55 # ifdef CDS_DOXYGEN_INVOKED
56 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
58 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
61 typedef typename options::disposer disposer ; ///< disposer used
62 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
63 typedef typename michael_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
65 typedef gc::nogc gc ; ///< Garbage collector
66 typedef typename options::back_off back_off ; ///< back-off strategy
67 typedef typename options::item_counter item_counter ; ///< Item counting policy used
68 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
71 // Rebind options (split-list support)
72 template <typename... Options>
73 struct rebind_options {
77 , typename cds::opt::make_options< options, Options...>::type
83 typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
84 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
86 atomic_node_ptr m_pHead ; ///< Head pointer
87 item_counter m_ItemCounter ; ///< Item counter
90 /// Position pointer for item search
92 atomic_node_ptr * pPrev ; ///< Previous node
93 node_type * pCur ; ///< Current node
94 node_type * pNext ; ///< Next node
100 void clear_links( node_type * pNode )
102 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
105 template <class Disposer>
106 void dispose_node( node_type * pNode, Disposer disp )
108 clear_links( pNode );
109 disp( node_traits::to_value_ptr( *pNode ));
112 template <class Disposer>
113 void dispose_value( value_type& val, Disposer disp )
115 dispose_node( node_traits::to_node_ptr( val ), disp );
118 bool link_node( node_type * pNode, position& pos )
120 assert( pNode != nullptr );
121 link_checker::is_empty( pNode );
123 pNode->m_pNext.store( pos.pCur, memory_model::memory_order_relaxed );
124 return pos.pPrev->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
130 template <bool IS_CONST>
133 friend class MichaelList;
134 value_type * m_pNode;
139 node_type * pNode = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_acquire);
141 m_pNode = node_traits::to_value_ptr( *pNode );
148 explicit iterator_type( node_type * pNode)
151 m_pNode = node_traits::to_value_ptr( *pNode );
155 explicit iterator_type( atomic_node_ptr const& refNode)
157 node_type * pNode = refNode.load(memory_model::memory_order_relaxed);
159 m_pNode = node_traits::to_value_ptr( *pNode );
165 typedef typename cds::details::make_const_type<value_type, IS_CONST>::pointer value_ptr;
166 typedef typename cds::details::make_const_type<value_type, IS_CONST>::reference value_ref;
172 iterator_type( const iterator_type& src )
173 : m_pNode( src.m_pNode )
176 value_ptr operator ->() const
181 value_ref operator *() const
183 assert( m_pNode != nullptr );
188 iterator_type& operator ++()
195 iterator_type operator ++(int)
197 iterator_type i(*this);
202 iterator_type& operator = (const iterator_type& src)
204 m_pNode = src.m_pNode;
209 bool operator ==(iterator_type<C> const& i ) const
211 return m_pNode == i.m_pNode;
214 bool operator !=(iterator_type<C> const& i ) const
216 return m_pNode != i.m_pNode;
223 typedef iterator_type<false> iterator;
224 /// Const forward iterator
225 typedef iterator_type<true> const_iterator;
227 /// Returns a forward iterator addressing the first element in a list
229 For empty list \code begin() == end() \endcode
233 return iterator(m_pHead.load(memory_model::memory_order_relaxed) );
236 /// Returns an iterator that addresses the location succeeding the last element in a list
238 Do not use the value returned by <tt>end</tt> function to access any item.
239 Internally, <tt>end</tt> returning value equals to \p nullptr.
241 The returned value can be used only to control reaching the end of the list.
242 For empty list \code begin() == end() \endcode
249 /// Returns a forward const iterator addressing the first element in a list
250 const_iterator begin() const
252 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
254 /// Returns a forward const iterator addressing the first element in a list
255 const_iterator cbegin()
257 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
260 /// Returns an const iterator that addresses the location succeeding the last element in a list
261 const_iterator end() const
263 return const_iterator();
265 /// Returns an const iterator that addresses the location succeeding the last element in a list
266 const_iterator cend() const
268 return const_iterator();
272 /// Default constructor initializes empty list
276 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
279 /// Destroys the list objects
287 The function inserts \p val in the list if the list does not contain
288 an item with key equal to \p val.
290 Returns \p true if \p val is linked into the list, \p false otherwise.
292 bool insert( value_type& val )
294 return insert_at( m_pHead, val );
297 /// Ensures that the \p item exists in the list
299 The operation performs inserting or changing data with lock-free manner.
301 If the item \p val not found in the list, then \p val is inserted into the list.
302 Otherwise, the functor \p func is called with item found.
303 The functor signature is:
306 void operator()( bool bNew, value_type& item, value_type& val );
310 - \p bNew - \p true if the item has been inserted, \p false otherwise
311 - \p item - item of the list
312 - \p val - argument \p val passed into the \p ensure function
313 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
314 refer to the same thing.
316 The functor may change non-key fields of the \p item; however, \p func must guarantee
317 that during changing no any other modifications could be made on this item by concurrent threads.
319 You can pass \p func argument by value or by reference using \p std::ref.
321 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
322 \p second is true if new item has been added or \p false if the item with \p key
323 already is in the list.
326 template <typename Func>
327 std::pair<bool, bool> ensure( value_type& val, Func func )
329 return ensure_at( m_pHead, val, func );
332 /// Finds the key \p val
333 /** \anchor cds_intrusive_MichaelList_nogc_find_func
334 The function searches the item with key equal to \p val
335 and calls the functor \p f for item found.
336 The interface of \p Func functor is:
339 void operator()( value_type& item, Q& val );
342 where \p item is the item found, \p val is the <tt>find</tt> function argument.
344 You can pass \p f argument by value or by reference using \p std::ref.
346 The functor can change non-key fields of \p item.
347 The function \p find does not serialize simultaneous access to the list \p item. If such access is
348 possible you must provide your own synchronization schema to exclude unsafe item modifications.
350 The function returns \p true if \p val is found, \p false otherwise.
352 template <typename Q, typename Func>
353 bool find( Q& val, Func f )
355 return find_at( m_pHead, val, key_comparator(), f );
358 /// Finds the key \p val using \p pred predicate for searching
360 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
361 but \p pred is used for key comparing.
362 \p Less functor has the interface like \p std::less.
363 \p pred must imply the same element order as the comparator used for building the list.
365 template <typename Q, typename Less, typename Func>
366 bool find_with( Q& val, Less pred, Func f )
368 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
371 /// Finds the key \p val
372 /** \anchor cds_intrusive_MichaelList_nogc_find_cfunc
373 The function searches the item with key equal to \p val
374 and calls the functor \p f for item found.
375 The interface of \p Func functor is:
378 void operator()( value_type& item, Q const& val );
381 where \p item is the item found, \p val is the <tt>find</tt> function argument.
383 You can pass \p f argument by value or by reference using \p std::ref.
385 The functor can change non-key fields of \p item.
386 The function \p find does not serialize simultaneous access to the list \p item. If such access is
387 possible you must provide your own synchronization schema to exclude unsafe item modifications.
389 The function returns \p true if \p val is found, \p false otherwise.
391 template <typename Q, typename Func>
392 bool find( Q const& val, Func f )
394 return find_at( m_pHead, val, key_comparator(), f );
397 /// Finds the key \p val using \p pred predicate for searching
399 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_cfunc "find(Q const&, Func)"
400 but \p pred is used for key comparing.
401 \p Less functor has the interface like \p std::less.
402 \p pred must imply the same element order as the comparator used for building the list.
404 template <typename Q, typename Less, typename Func>
405 bool find_with( Q const& val, Less pred, Func f )
407 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
410 /// Finds the key \p val
411 /** \anchor cds_intrusive_MichaelList_nogc_find_val
412 The function searches the item with key equal to \p val
413 and returns pointer to value found or \p nullptr.
415 template <typename Q>
416 value_type * find( Q const & val )
418 return find_at( m_pHead, val, key_comparator() );
421 /// Finds the key \p val using \p pred predicate for searching
423 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_val "find(Q const&, Func)"
424 but \p pred is used for key comparing.
425 \p Less functor has the interface like \p std::less.
426 \p pred must imply the same element order as the comparator used for building the list.
428 template <typename Q, typename Less>
429 value_type * find_with( Q const& val, Less pred )
431 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>());
436 The function unlink all items from the list.
438 For each unlinked item the item disposer \p disp is called after unlinking.
440 template <typename Disposer>
441 void clear( Disposer disp )
443 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
444 do {} while ( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed ) );
447 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
448 dispose_node( pHead, disp );
454 /// Clears the list using default disposer
456 The function clears the list using default (provided in class template) disposer functor.
463 /// Checks if the list is empty
466 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
469 /// Returns list's item count
471 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
472 this function always returns 0.
474 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
475 is empty. To check list emptyness use \ref empty() method.
479 return m_ItemCounter.value();
484 // split-list support
485 bool insert_aux_node( node_type * pNode )
487 return insert_aux_node( m_pHead, pNode );
490 // split-list support
491 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
493 assert( pNode != nullptr );
495 // Hack: convert node_type to value_type.
496 // In principle, auxiliary node can be non-reducible to value_type
497 // We assume that comparator can correctly distinguish aux and regular node.
498 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
501 bool insert_at( atomic_node_ptr& refHead, value_type& val )
503 link_checker::is_empty( node_traits::to_node_ptr( val ) );
507 if ( search( refHead, val, key_comparator(), pos ) )
510 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
517 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
519 if ( insert_at( refHead, val ))
520 return iterator( node_traits::to_node_ptr( val ));
524 template <typename Func>
525 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
530 if ( search( refHead, val, key_comparator(), pos ) ) {
531 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
533 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
534 return std::make_pair( iterator( pos.pCur ), false );
537 link_checker::is_empty( node_traits::to_node_ptr( val ) );
539 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
541 func( true, val , val );
542 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
548 template <typename Func>
549 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
551 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func );
552 return std::make_pair( ret.first != end(), ret.second );
555 template <typename Q, typename Compare, typename Func>
556 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
560 if ( search( refHead, val, cmp, pos ) ) {
561 assert( pos.pCur != nullptr );
562 f( *node_traits::to_value_ptr( *pos.pCur ), val );
568 template <typename Q, typename Compare>
569 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
571 iterator it = find_at_( refHead, val, cmp );
577 template <typename Q, typename Compare>
578 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
582 if ( search( refHead, val, cmp, pos ) ) {
583 assert( pos.pCur != nullptr );
584 return iterator( pos.pCur );
594 template <typename Q, typename Compare >
595 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
597 atomic_node_ptr * pPrev;
605 pCur = pPrev->load(memory_model::memory_order_acquire);
616 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
617 if ( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext ) {
622 if ( pPrev->load(memory_model::memory_order_acquire) != pCur ) {
627 assert( pCur != nullptr );
628 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
635 pPrev = &( pCur->m_pNext );
642 }} // namespace cds::intrusive
644 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H