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>
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()
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 );
302 /// Ensures that the \p item exists in the list
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 Otherwise, the functor \p func is called with item found.
308 The functor signature is:
311 void operator()( bool bNew, value_type& item, value_type& val );
315 - \p bNew - \p true if the item has been inserted, \p false otherwise
316 - \p item - item of the list
317 - \p val - argument \p val passed into the \p ensure function
318 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
319 refer to the same thing.
321 The functor may change non-key fields of the \p item; however, \p func must guarantee
322 that during changing no any other modifications could be made on this item by concurrent threads.
324 You can pass \p func argument by value or by reference using \p std::ref.
326 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
327 \p second is true if new item has been added or \p false if the item with \p key
328 already is in the list.
331 template <typename Func>
332 std::pair<bool, bool> ensure( value_type& val, Func func )
334 return ensure_at( m_pHead, val, func );
337 /// Finds the key \p val
338 /** \anchor cds_intrusive_MichaelList_nogc_find_func
339 The function searches the item with key equal to \p key
340 and calls the functor \p f for item found.
341 The interface of \p Func functor is:
344 void operator()( value_type& item, Q& key );
347 where \p item is the item found, \p key is the <tt>find</tt> function argument.
349 The functor can change non-key fields of \p item.
350 The function \p find does not serialize simultaneous access to the list \p item. If such access is
351 possible you must provide your own synchronization schema to exclude unsafe item modifications.
353 The function returns \p true if \p val is found, \p false otherwise.
355 template <typename Q, typename Func>
356 bool find( Q& key, Func f )
358 return find_at( m_pHead, key, key_comparator(), f );
361 /// Finds the key \p key using \p pred predicate for searching
363 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
364 but \p pred is used for key comparing.
365 \p Less functor has the interface like \p std::less.
366 \p pred must imply the same element order as the comparator used for building the list.
368 template <typename Q, typename Less, typename Func>
369 bool find_with( Q& key, Less pred, Func f )
371 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
375 /** \anchor cds_intrusive_MichaelList_nogc_find_val
376 The function searches the item with key equal to \p key
377 and returns pointer to value found or \p nullptr.
379 template <typename Q>
380 value_type * find( Q const& key )
382 return find_at( m_pHead, key, key_comparator() );
385 /// Finds \p key using \p pred predicate for searching
387 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_val "find(Q const&, Func)"
388 but \p pred is used for key comparing.
389 \p Less functor has the interface like \p std::less.
390 \p pred must imply the same element order as the comparator used for building the list.
392 template <typename Q, typename Less>
393 value_type * find_with( Q const& key, Less pred )
395 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
400 The function unlink all items from the list.
402 For each unlinked item the item disposer \p disp is called after unlinking.
404 template <typename Disposer>
405 void clear( Disposer disp )
407 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
408 do {} while ( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed ) );
411 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
412 dispose_node( pHead, disp );
418 /// Clears the list using default disposer
420 The function clears the list using default (provided in class template) disposer functor.
427 /// Checks if the list is empty
430 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
433 /// Returns list's item count
435 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
436 this function always returns 0.
438 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
439 is empty. To check list emptyness use \p empty() method.
443 return m_ItemCounter.value();
448 // split-list support
449 bool insert_aux_node( node_type * pNode )
451 return insert_aux_node( m_pHead, pNode );
454 // split-list support
455 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
457 assert( pNode != nullptr );
459 // Hack: convert node_type to value_type.
460 // In principle, auxiliary node can be non-reducible to value_type
461 // We assume that comparator can correctly distinguish aux and regular node.
462 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
465 bool insert_at( atomic_node_ptr& refHead, value_type& val )
467 link_checker::is_empty( node_traits::to_node_ptr( val ) );
471 if ( search( refHead, val, key_comparator(), pos ) )
474 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
481 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
483 if ( insert_at( refHead, val ))
484 return iterator( node_traits::to_node_ptr( val ));
488 template <typename Func>
489 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
494 if ( search( refHead, val, key_comparator(), pos ) ) {
495 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
497 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
498 return std::make_pair( iterator( pos.pCur ), false );
501 link_checker::is_empty( node_traits::to_node_ptr( val ) );
503 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
505 func( true, val , val );
506 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
512 template <typename Func>
513 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
515 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func );
516 return std::make_pair( ret.first != end(), ret.second );
519 template <typename Q, typename Compare, typename Func>
520 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
524 if ( search( refHead, val, cmp, pos ) ) {
525 assert( pos.pCur != nullptr );
526 f( *node_traits::to_value_ptr( *pos.pCur ), val );
532 template <typename Q, typename Compare>
533 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
535 iterator it = find_at_( refHead, val, cmp );
541 template <typename Q, typename Compare>
542 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
546 if ( search( refHead, val, cmp, pos ) ) {
547 assert( pos.pCur != nullptr );
548 return iterator( pos.pCur );
558 template <typename Q, typename Compare >
559 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
561 atomic_node_ptr * pPrev;
569 pCur = pPrev->load(memory_model::memory_order_acquire);
580 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
581 if ( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext ) {
586 if ( pPrev->load(memory_model::memory_order_acquire) != pCur ) {
591 assert( pCur != nullptr );
592 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
599 pPrev = &( pCur->m_pNext );
606 }} // namespace cds::intrusive
608 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H