3 #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H
4 #define __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/gc/guarded_ptr.h>
8 #include <cds/details/make_const_type.h>
10 namespace cds { namespace intrusive {
12 /// Michael's lock-free ordered single-linked list
13 /** @ingroup cds_intrusive_list
14 \anchor cds_intrusive_MichaelList_hp
16 Usually, ordered single-linked list is used as a building block for the hash table implementation.
17 The complexity of searching is <tt>O(N)</tt>.
20 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
23 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see \p michael_list::node).
24 - \p T - type to be stored in the list. The type must be based on \p michael_list::node (for \p michael_list::base_hook)
25 or it must have a member of type \p michael_list::node (for \p michael_list::member_hook).
26 - \p Traits - type traits, default is \p michael_list::traits. It is possible to declare option-based
27 list with \p cds::intrusive::michael_list::make_traits metafunction:
28 For example, the following traits-based declaration of \p gc::HP Michael's list
30 #include <cds/intrusive/michael_list_hp.h>
31 // Declare item stored in your list
32 struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
38 // Declare comparator for the item
40 int operator()( item const& i1, item const& i2 ) const
42 return i1.nKey - i2.nKey;
47 struct my_traits: public cds::intrusive::michael_list::traits
49 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
50 typedef my_compare compare;
53 // Declare traits-based list
54 typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits > traits_based_list;
56 is equivalent for the following option-based list
58 #include <cds/intrusive/michael_list_hp.h>
60 // item struct and my_compare are the same
62 // Declare option-based list
63 typedef cds::intrusive::MichaelList< cds::gc::HP, item,
64 typename cds::intrusive::michael_list::make_traits<
65 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
66 ,cds::intrusive::opt::compare< my_compare > // item comparator option
72 There are different specializations of this template for each garbage collecting schema.
73 You should select GC needed and include appropriate .h-file:
74 - for \p gc::HP: <tt> <cds/intrusive/michael_list_hp.h> </tt>
75 - for \p gc::DHP: <tt> <cds/intrusive/michael_list_dhp.h> </tt>
76 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
77 - for \p gc::nogc: <tt> <cds/intrusive/michael_list_nogc.h> </tt>
78 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
80 Then, you should incorporate \p michael_list::node into your struct \p T and provide
81 appropriate \p michael_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
82 define a struct based on \p michael_list::traits.
84 Example for \p gc::DHP and base hook:
86 // Include GC-related Michael's list specialization
87 #include <cds/intrusive/michael_list_dhp.h>
89 // Data stored in Michael's list
90 struct my_data: public cds::intrusive::michael_list::node< cds::gc::DHP >
99 // my_data comparing functor
101 int operator()( const my_data& d1, const my_data& d2 )
103 return d1.strKey.compare( d2.strKey );
106 int operator()( const my_data& d, const std::string& s )
108 return d.strKey.compare(s);
111 int operator()( const std::string& s, const my_data& d )
113 return s.compare( d.strKey );
119 struct my_traits: public cds::intrusive::michael_list::traits
121 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
122 typedef my_data_cmp compare;
126 typedef cds::intrusive::MichaelList< cds::gc::DHP, my_data, my_traits > traits_based_list;
129 Equivalent option-based code:
131 // GC-related specialization
132 #include <cds/intrusive/michael_list_dhp.h>
141 // Declare option-based list
142 typedef cds::intrusive::MichaelList< cds::gc::DHP
144 , typename cds::intrusive::michael_list::make_traits<
145 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
146 ,cds::intrusive::opt::compare< my_data_cmp >
155 #ifdef CDS_DOXYGEN_INVOKED
156 ,class Traits = michael_list::traits
164 typedef T value_type; ///< type of value stored in the list
165 typedef Traits traits; ///< Traits template parameter
167 typedef typename traits::hook hook; ///< hook type
168 typedef typename hook::node_type node_type; ///< node type
170 # ifdef CDS_DOXYGEN_INVOKED
171 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
173 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
176 typedef typename traits::disposer disposer; ///< disposer used
177 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
178 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
180 typedef GC gc ; ///< Garbage collector
181 typedef typename traits::back_off back_off; ///< back-off strategy
182 typedef typename traits::item_counter item_counter; ///< Item counting policy used
183 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
185 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
188 // Rebind traits (split-list support)
189 template <typename... Options>
190 struct rebind_traits {
194 , typename cds::opt::make_options< traits, Options...>::type
200 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
201 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
203 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
205 atomic_node_ptr m_pHead; ///< Head pointer
206 item_counter m_ItemCounter; ///< Item counter
209 /// Position pointer for item search
211 atomic_node_ptr * pPrev ; ///< Previous node
212 node_type * pCur ; ///< Current node
213 node_type * pNext ; ///< Next node
215 typename gc::template GuardArray<3> guards ; ///< Guards array
224 struct clean_disposer {
225 void operator()( value_type * p )
227 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
235 static void retire_node( node_type * pNode )
237 assert( pNode != nullptr );
238 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
241 static bool link_node( node_type * pNode, position& pos )
243 assert( pNode != nullptr );
244 link_checker::is_empty( pNode );
246 marked_node_ptr cur(pos.pCur);
247 pNode->m_pNext.store( cur, memory_model::memory_order_relaxed );
248 return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
251 static bool unlink_node( position& pos )
253 assert( pos.pPrev != nullptr );
254 assert( pos.pCur != nullptr );
256 // Mark the node (logical deleting)
257 marked_node_ptr next(pos.pNext, 0);
258 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
259 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
260 // CAS may be successful here or in other thread that searching something
261 marked_node_ptr cur(pos.pCur);
262 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
263 retire_node( pos.pCur );
272 template <bool IsConst>
275 friend class MichaelList;
278 value_type * m_pNode;
279 typename gc::Guard m_Guard;
284 typename gc::Guard g;
285 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
287 marked_node_ptr pNext;
289 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
290 g.assign( node_traits::to_value_ptr( pNext.ptr() ));
291 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
294 m_pNode = m_Guard.assign( g.template get<value_type>() );
303 iterator_type( atomic_node_ptr const& pNode )
306 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
308 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
314 if ( p == pNode.load(memory_model::memory_order_acquire) )
320 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
321 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
327 iterator_type( iterator_type const& src )
330 m_pNode = m_Guard.assign( src.m_pNode );
336 value_ptr operator ->() const
341 value_ref operator *() const
343 assert( m_pNode != nullptr );
348 iterator_type& operator ++()
354 iterator_type& operator = (iterator_type const& src)
356 m_pNode = src.m_pNode;
357 m_Guard.assign( m_pNode );
363 void operator ++(int)
370 bool operator ==(iterator_type<C> const& i ) const
372 return m_pNode == i.m_pNode;
375 bool operator !=(iterator_type<C> const& i ) const
377 return m_pNode != i.m_pNode;
385 The forward iterator for Michael's list has some features:
386 - it has no post-increment operator
387 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
388 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
389 may be thrown if the limit of guard count per thread is exceeded.
390 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
391 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
392 deleting operations there is no guarantee that you iterate all item in the list.
394 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
395 for debug purpose only.
397 The iterator interface:
401 // Default constructor
405 iterator( iterator const& src );
407 // Dereference operator
408 value_type * operator ->() const;
410 // Dereference operator
411 value_type& operator *() const;
413 // Preincrement operator
414 iterator& operator ++();
416 // Assignment operator
417 iterator& operator = (iterator const& src);
419 // Equality operators
420 bool operator ==(iterator const& i ) const;
421 bool operator !=(iterator const& i ) const;
425 typedef iterator_type<false> iterator;
426 /// Const forward iterator
428 For iterator's features and requirements see \ref iterator
430 typedef iterator_type<true> const_iterator;
432 /// Returns a forward iterator addressing the first element in a list
434 For empty list \code begin() == end() \endcode
438 return iterator( m_pHead );
441 /// Returns an iterator that addresses the location succeeding the last element in a list
443 Do not use the value returned by <tt>end</tt> function to access any item.
444 Internally, <tt>end</tt> returning value equals to \p nullptr.
446 The returned value can be used only to control reaching the end of the list.
447 For empty list <tt>begin() == end()</tt>
454 /// Returns a forward const iterator addressing the first element in a list
455 const_iterator cbegin()
457 return const_iterator( m_pHead );
460 /// Returns a forward const iterator addressing the first element in a list
461 const_iterator begin() const
463 return const_iterator( m_pHead );
466 /// Returns an const iterator that addresses the location succeeding the last element in a list
467 const_iterator end() const
469 return const_iterator();
472 /// Returns an const iterator that addresses the location succeeding the last element in a list
473 const_iterator cend()
475 return const_iterator();
479 /// Default constructor initializes empty list
483 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
486 /// Destroys the list object
494 The function inserts \p val into the list if the list does not contain
495 an item with key equal to \p val.
497 Returns \p true if \p val has been linked to the list, \p false otherwise.
499 bool insert( value_type& val )
501 return insert_at( m_pHead, val );
506 This function is intended for derived non-intrusive containers.
508 The function allows to split new item creating into two part:
509 - create item with key only
510 - insert new item into the list
511 - if inserting is success, calls \p f functor to initialize value-field of \p val.
513 The functor signature is:
515 void func( value_type& val );
517 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
518 \p val no any other changes could be made on this list's item by concurrent threads.
519 The user-defined functor is called only if the inserting is success.
521 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
523 template <typename Func>
524 bool insert( value_type& val, Func f )
526 return insert_at( m_pHead, val, f );
529 /// Ensures that the \p val exists in the list
531 The operation performs inserting or changing data with lock-free manner.
533 If the item \p val is not found in the list, then \p val is inserted.
534 Otherwise, the functor \p func is called with item found.
535 The functor signature is:
537 void func( bool bNew, value_type& item, value_type& val );
540 - \p bNew - \p true if the item has been inserted, \p false otherwise
541 - \p item - item of the list
542 - \p val - argument \p val passed into the \p ensure function
543 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
544 refers to the same thing.
546 The functor may change non-key fields of the \p item; however, \p func must guarantee
547 that during changing no any other modifications could be made on this item by concurrent threads.
549 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
550 \p second is \p true if new item has been added or \p false if the item with \p key
551 already is in the list.
553 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
555 template <typename Func>
556 std::pair<bool, bool> ensure( value_type& val, Func func )
558 return ensure_at( m_pHead, val, func );
561 /// Unlinks the item \p val from the list
563 The function searches the item \p val in the list and unlinks it from the list
564 if it is found and it is equal to \p val.
566 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
567 and deletes the item found. \p %unlink() finds an item by key and deletes it
568 only if \p val is an item of the list, i.e. the pointer to item found
569 is equal to <tt> &val </tt>.
571 The function returns \p true if success and \p false otherwise.
573 bool unlink( value_type& val )
575 return unlink_at( m_pHead, val );
578 /// Deletes the item from the list
579 /** \anchor cds_intrusive_MichaelList_hp_erase_val
580 The function searches an item with key equal to \p key in the list,
581 unlinks it from the list, and returns \p true.
582 If \p key is not found the function return \p false.
584 template <typename Q>
585 bool erase( Q const& key )
587 return erase_at( m_pHead, key, key_comparator() );
590 /// Deletes the item from the list using \p pred predicate for searching
592 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
593 but \p pred is used for key comparing.
594 \p Less functor has the interface like \p std::less.
595 \p pred must imply the same element order as the comparator used for building the list.
597 template <typename Q, typename Less>
598 bool erase_with( Q const& key, Less pred )
600 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
603 /// Deletes the item from the list
604 /** \anchor cds_intrusive_MichaelList_hp_erase_func
605 The function searches an item with key equal to \p key in the list,
606 call \p func functor with item found, unlinks it from the list, and returns \p true.
607 The \p Func interface is
610 void operator()( value_type const& item );
613 If \p key is not found the function return \p false, \p func is not called.
615 template <typename Q, typename Func>
616 bool erase( Q const& key, Func func )
618 return erase_at( m_pHead, key, key_comparator(), func );
621 /// Deletes the item from the list using \p pred predicate for searching
623 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
624 but \p pred is used for key comparing.
625 \p Less functor has the interface like \p std::less.
626 \p pred must imply the same element order as the comparator used for building the list.
628 template <typename Q, typename Less, typename Func>
629 bool erase_with( Q const& key, Less pred, Func f )
631 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
634 /// Extracts the item from the list with specified \p key
635 /** \anchor cds_intrusive_MichaelList_hp_extract
636 The function searches an item with key equal to \p key,
637 unlinks it from the list, and returns it in \p dest parameter.
638 If the item with key equal to \p key is not found the function returns \p false.
640 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
642 The \ref disposer specified in \p Traits class template parameter is called automatically
643 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
644 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
648 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
652 ord_list::guarded_ptr gp;
653 theList.extract( gp, 5 );
657 // Destructor of gp releases internal HP guard
661 template <typename Q>
662 bool extract( guarded_ptr& dest, Q const& key )
664 return extract_at( m_pHead, dest.guard(), key, key_comparator() );
667 /// Extracts the item using compare functor \p pred
669 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
670 but \p pred predicate is used for key comparing.
672 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
674 \p pred must imply the same element order as the comparator used for building the list.
676 template <typename Q, typename Less>
677 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
679 return extract_at( m_pHead, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
682 /// Finds \p key in the list
683 /** \anchor cds_intrusive_MichaelList_hp_find_func
684 The function searches the item with key equal to \p key and calls the functor \p f for item found.
685 The interface of \p Func functor is:
688 void operator()( value_type& item, Q& key );
691 where \p item is the item found, \p key is the <tt>find</tt> function argument.
693 The functor may change non-key fields of \p item. Note that the function is only guarantee
694 that \p item cannot be disposed during functor is executing.
695 The function does not serialize simultaneous access to the \p item. If such access is
696 possible you must provide your own synchronization schema to keep out unsafe item modifications.
698 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
699 may modify both arguments.
701 The function returns \p true if \p val is found, \p false otherwise.
703 template <typename Q, typename Func>
704 bool find( Q& key, Func f )
706 return find_at( m_pHead, key, key_comparator(), f );
709 /// Finds the \p key using \p pred predicate for searching
711 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
712 but \p pred is used for key comparing.
713 \p Less functor has the interface like \p std::less.
714 \p pred must imply the same element order as the comparator used for building the list.
716 template <typename Q, typename Less, typename Func>
717 bool find_with( Q& key, Less pred, Func f )
719 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
723 /** \anchor cds_intrusive_MichaelList_hp_find_val
724 The function searches the item with key equal to \p key
725 and returns \p true if it is found, and \p false otherwise
727 template <typename Q>
728 bool find( Q const& key )
730 return find_at( m_pHead, key, key_comparator() );
733 /// Finds the key \p val using \p pred predicate for searching
735 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
736 but \p pred is used for key comparing.
737 \p Less functor has the interface like \p std::less.
738 \p pred must imply the same element order as the comparator used for building the list.
740 template <typename Q, typename Less>
741 bool find_with( Q const& key, Less pred )
743 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
746 /// Finds the \p key and return the item found
747 /** \anchor cds_intrusive_MichaelList_hp_get
748 The function searches the item with key equal to \p key
749 and assigns the item found to guarded pointer \p ptr.
750 The function returns \p true if \p key is found, and \p false otherwise.
751 If \p key is not found the \p ptr parameter is not changed.
753 The \ref disposer specified in \p Traits class template parameter is called
754 by garbage collector \p GC automatically when returned \ref guarded_ptr object
755 will be destroyed or released.
756 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
760 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
764 ord_list::guarded_ptr gp;
765 if ( theList.get( gp, 5 )) {
769 // Destructor of guarded_ptr releases internal HP guard
773 Note the compare functor specified for \p Traits template parameter
774 should accept a parameter of type \p Q that can be not the same as \p value_type.
776 template <typename Q>
777 bool get( guarded_ptr& ptr, Q const& key )
779 return get_at( m_pHead, ptr.guard(), key, key_comparator() );
782 /// Finds the \p key and return the item found
784 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
785 but \p pred is used for comparing the keys.
787 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
789 \p pred must imply the same element order as the comparator used for building the list.
791 template <typename Q, typename Less>
792 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
794 return get_at( m_pHead, ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
799 The function unlink all items from the list.
803 typename gc::Guard guard;
804 marked_node_ptr head;
806 head = m_pHead.load(memory_model::memory_order_relaxed);
808 guard.assign( node_traits::to_value_ptr( *head.ptr() ));
809 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
810 if ( head.ptr() == nullptr )
812 value_type& val = *node_traits::to_value_ptr( *head.ptr() );
818 /// Checks whether the list is empty
821 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
824 /// Returns list's item count
826 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
827 this function always returns 0.
829 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
830 is empty. To check list emptyness use \p empty() method.
834 return m_ItemCounter.value();
839 // split-list support
840 bool insert_aux_node( node_type * pNode )
842 return insert_aux_node( m_pHead, pNode );
845 // split-list support
846 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
848 assert( pNode != nullptr );
850 // Hack: convert node_type to value_type.
851 // In principle, auxiliary node can be non-reducible to value_type
852 // We assume that comparator can correctly distinguish aux and regular node.
853 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
856 bool insert_at( atomic_node_ptr& refHead, value_type& val )
858 node_type * pNode = node_traits::to_node_ptr( val );
859 link_checker::is_empty( pNode );
863 if ( search( refHead, val, pos, key_comparator() ) )
866 if ( link_node( pNode, pos ) ) {
872 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
876 template <typename Func>
877 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
879 node_type * pNode = node_traits::to_node_ptr( val );
880 link_checker::is_empty( pNode );
884 if ( search( refHead, val, pos, key_comparator() ) )
887 typename gc::Guard guard;
888 guard.assign( &val );
889 if ( link_node( pNode, pos ) ) {
896 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
900 template <typename Func>
901 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
905 node_type * pNode = node_traits::to_node_ptr( val );
907 if ( search( refHead, val, pos, key_comparator() ) ) {
908 if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
910 continue ; // the node found is marked as deleted
912 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
914 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
915 return std::make_pair( true, false );
918 typename gc::Guard guard;
919 guard.assign( &val );
920 if ( link_node( pNode, pos ) ) {
922 func( true, val, val );
923 return std::make_pair( true, true );
926 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
931 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
936 while ( search( refHead, val, pos, key_comparator() ) ) {
937 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
938 if ( unlink_node( pos ) ) {
951 template <typename Q, typename Compare, typename Func>
952 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
955 while ( search( refHead, val, pos, cmp )) {
956 if ( unlink_node( pos ) ) {
957 f( *node_traits::to_value_ptr( *pos.pCur ) );
967 template <typename Q, typename Compare, typename Func>
968 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
971 return erase_at( refHead, val, cmp, f, pos );
974 template <typename Q, typename Compare>
975 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
978 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
981 template <typename Q, typename Compare>
982 bool extract_at( atomic_node_ptr& refHead, typename gc::Guard& dest, Q const& val, Compare cmp )
986 while ( search( refHead, val, pos, cmp )) {
987 if ( unlink_node( pos ) ) {
988 dest.assign( pos.guards.template get<value_type>( position::guard_current_item ) );
998 template <typename Q, typename Compare>
999 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1002 return search( refHead, val, pos, cmp );
1005 template <typename Q, typename Compare, typename Func>
1006 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1009 if ( search( refHead, val, pos, cmp )) {
1010 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1016 template <typename Q, typename Compare>
1017 bool get_at( atomic_node_ptr& refHead, typename gc::Guard& guard, Q const& val, Compare cmp )
1020 if ( search( refHead, val, pos, cmp )) {
1021 guard.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1032 template <typename Q, typename Compare >
1033 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1035 atomic_node_ptr * pPrev;
1036 marked_node_ptr pNext;
1037 marked_node_ptr pCur;
1045 pCur = pPrev->load(memory_model::memory_order_relaxed);
1046 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1047 if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1051 if ( pCur.ptr() == nullptr ) {
1053 pos.pCur = pCur.ptr();
1054 pos.pNext = pNext.ptr();
1058 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1059 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1060 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
1065 if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
1070 // pNext contains deletion mark for pCur
1071 if ( pNext.bits() == 1 ) {
1072 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1073 marked_node_ptr cur( pCur.ptr());
1074 if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1075 retire_node( pCur.ptr() );
1083 assert( pCur.ptr() != nullptr );
1084 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1087 pos.pCur = pCur.ptr();
1088 pos.pNext = pNext.ptr();
1091 pPrev = &( pCur->m_pNext );
1092 pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1095 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1100 }} // namespace cds::intrusive
1102 #endif // #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H