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 );
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 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
325 \p second is true if new item has been added or \p false if the item with \p key
326 already is in the list.
329 template <typename Func>
330 std::pair<bool, bool> ensure( value_type& val, Func func )
332 return ensure_at( m_pHead, val, func );
335 /// Finds the key \p val
336 /** \anchor cds_intrusive_MichaelList_nogc_find_func
337 The function searches the item with key equal to \p key
338 and calls the functor \p f for item found.
339 The interface of \p Func functor is:
342 void operator()( value_type& item, Q& key );
345 where \p item is the item found, \p key is the <tt>find</tt> function argument.
347 The functor can change non-key fields of \p item.
348 The function \p find does not serialize simultaneous access to the list \p item. If such access is
349 possible you must provide your own synchronization schema to exclude unsafe item modifications.
351 The function returns \p true if \p val is found, \p false otherwise.
353 template <typename Q, typename Func>
354 bool find( Q& key, Func f )
356 return find_at( m_pHead, key, key_comparator(), f );
359 template <typename Q, typename Func>
360 bool find( Q const& key, Func f )
362 return find_at( m_pHead, key, key_comparator(), f );
366 /// Finds the key \p key using \p pred predicate for searching
368 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
369 but \p pred is used for key comparing.
370 \p Less functor has the interface like \p std::less.
371 \p pred must imply the same element order as the comparator used for building the list.
373 template <typename Q, typename Less, typename Func>
374 bool find_with( Q& key, Less pred, Func f )
377 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
380 template <typename Q, typename Less, typename Func>
381 bool find_with( Q const& key, Less pred, Func f )
384 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
389 /** \anchor cds_intrusive_MichaelList_nogc_find_val
390 The function searches the item with key equal to \p key
391 and returns pointer to value found or \p nullptr.
393 template <typename Q>
394 value_type * find( Q const& key )
396 return find_at( m_pHead, key, key_comparator() );
399 /// Finds \p key using \p pred predicate for searching
401 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_val "find(Q const&, Func)"
402 but \p pred is used for key comparing.
403 \p Less functor has the interface like \p std::less.
404 \p pred must imply the same element order as the comparator used for building the list.
406 template <typename Q, typename Less>
407 value_type * find_with( Q const& key, Less pred )
410 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
415 The function unlink all items from the list.
417 For each unlinked item the item disposer \p disp is called after unlinking.
419 template <typename Disposer>
420 void clear( Disposer disp )
422 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
423 do {} while ( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed ) );
426 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
427 dispose_node( pHead, disp );
433 /// Clears the list using default disposer
435 The function clears the list using default (provided in class template) disposer functor.
442 /// Checks if the list is empty
445 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
448 /// Returns list's item count
450 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
451 this function always returns 0.
453 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
454 is empty. To check list emptyness use \p empty() method.
458 return m_ItemCounter.value();
463 // split-list support
464 bool insert_aux_node( node_type * pNode )
466 return insert_aux_node( m_pHead, pNode );
469 // split-list support
470 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
472 assert( pNode != nullptr );
474 // Hack: convert node_type to value_type.
475 // In principle, auxiliary node can be non-reducible to value_type
476 // We assume that comparator can correctly distinguish aux and regular node.
477 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
480 bool insert_at( atomic_node_ptr& refHead, value_type& val )
482 link_checker::is_empty( node_traits::to_node_ptr( val ) );
486 if ( search( refHead, val, key_comparator(), pos ) )
489 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
496 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
498 if ( insert_at( refHead, val ))
499 return iterator( node_traits::to_node_ptr( val ));
503 template <typename Func>
504 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
509 if ( search( refHead, val, key_comparator(), pos ) ) {
510 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
512 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
513 return std::make_pair( iterator( pos.pCur ), false );
516 link_checker::is_empty( node_traits::to_node_ptr( val ) );
518 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
520 func( true, val , val );
521 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
527 template <typename Func>
528 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
530 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func );
531 return std::make_pair( ret.first != end(), ret.second );
534 template <typename Q, typename Compare, typename Func>
535 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
539 if ( search( refHead, val, cmp, pos ) ) {
540 assert( pos.pCur != nullptr );
541 f( *node_traits::to_value_ptr( *pos.pCur ), val );
547 template <typename Q, typename Compare>
548 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
550 iterator it = find_at_( refHead, val, cmp );
556 template <typename Q, typename Compare>
557 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
561 if ( search( refHead, val, cmp, pos ) ) {
562 assert( pos.pCur != nullptr );
563 return iterator( pos.pCur );
573 template <typename Q, typename Compare >
574 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
576 atomic_node_ptr * pPrev;
584 pCur = pPrev->load(memory_model::memory_order_acquire);
595 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
596 if ( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext ) {
601 if ( pPrev->load(memory_model::memory_order_acquire) != pCur ) {
606 assert( pCur != nullptr );
607 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
614 pPrev = &( pCur->m_pNext );
621 }} // namespace cds::intrusive
623 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H