3 #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
4 #define CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/details/make_const_type.h>
9 namespace cds { namespace intrusive {
11 /// Michael's lock-free ordered single-linked list
12 /** @ingroup cds_intrusive_list
13 \anchor cds_intrusive_MichaelList_hp
15 Usually, ordered single-linked list is used as a building block for the hash table implementation.
16 The complexity of searching is <tt>O(N)</tt>.
19 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
22 - \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).
23 - \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)
24 or it must have a member of type \p michael_list::node (for \p michael_list::member_hook).
25 - \p Traits - type traits, default is \p michael_list::traits. It is possible to declare option-based
26 list with \p cds::intrusive::michael_list::make_traits metafunction:
27 For example, the following traits-based declaration of \p gc::HP Michael's list
29 #include <cds/intrusive/michael_list_hp.h>
30 // Declare item stored in your list
31 struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
37 // Declare comparator for the item
39 int operator()( item const& i1, item const& i2 ) const
41 return i1.nKey - i2.nKey;
46 struct my_traits: public cds::intrusive::michael_list::traits
48 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
49 typedef my_compare compare;
52 // Declare traits-based list
53 typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits > traits_based_list;
55 is equivalent for the following option-based list
57 #include <cds/intrusive/michael_list_hp.h>
59 // item struct and my_compare are the same
61 // Declare option-based list
62 typedef cds::intrusive::MichaelList< cds::gc::HP, item,
63 typename cds::intrusive::michael_list::make_traits<
64 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
65 ,cds::intrusive::opt::compare< my_compare > // item comparator option
71 There are different specializations of this template for each garbage collecting schema.
72 You should select GC needed and include appropriate .h-file:
73 - for \p gc::HP: <tt> <cds/intrusive/michael_list_hp.h> </tt>
74 - for \p gc::DHP: <tt> <cds/intrusive/michael_list_dhp.h> </tt>
75 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
76 - for \p gc::nogc: <tt> <cds/intrusive/michael_list_nogc.h> </tt>
77 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
79 Then, you should incorporate \p michael_list::node into your struct \p T and provide
80 appropriate \p michael_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
81 define a struct based on \p michael_list::traits.
83 Example for \p gc::DHP and base hook:
85 // Include GC-related Michael's list specialization
86 #include <cds/intrusive/michael_list_dhp.h>
88 // Data stored in Michael's list
89 struct my_data: public cds::intrusive::michael_list::node< cds::gc::DHP >
98 // my_data comparing functor
100 int operator()( const my_data& d1, const my_data& d2 )
102 return d1.strKey.compare( d2.strKey );
105 int operator()( const my_data& d, const std::string& s )
107 return d.strKey.compare(s);
110 int operator()( const std::string& s, const my_data& d )
112 return s.compare( d.strKey );
118 struct my_traits: public cds::intrusive::michael_list::traits
120 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
121 typedef my_data_cmp compare;
125 typedef cds::intrusive::MichaelList< cds::gc::DHP, my_data, my_traits > traits_based_list;
128 Equivalent option-based code:
130 // GC-related specialization
131 #include <cds/intrusive/michael_list_dhp.h>
140 // Declare option-based list
141 typedef cds::intrusive::MichaelList< cds::gc::DHP
143 , typename cds::intrusive::michael_list::make_traits<
144 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
145 ,cds::intrusive::opt::compare< my_data_cmp >
154 #ifdef CDS_DOXYGEN_INVOKED
155 ,class Traits = michael_list::traits
163 typedef T value_type; ///< type of value stored in the list
164 typedef Traits traits; ///< Traits template parameter
166 typedef typename traits::hook hook; ///< hook type
167 typedef typename hook::node_type node_type; ///< node type
169 # ifdef CDS_DOXYGEN_INVOKED
170 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
172 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
175 typedef typename traits::disposer disposer; ///< disposer used
176 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
177 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
179 typedef GC gc ; ///< Garbage collector
180 typedef typename traits::back_off back_off; ///< back-off strategy
181 typedef typename traits::item_counter item_counter; ///< Item counting policy used
182 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
184 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
187 // Rebind traits (split-list support)
188 template <typename... Options>
189 struct rebind_traits {
193 , typename cds::opt::make_options< traits, Options...>::type
199 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
200 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
202 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
204 atomic_node_ptr m_pHead; ///< Head pointer
205 item_counter m_ItemCounter; ///< Item counter
208 /// Position pointer for item search
210 atomic_node_ptr * pPrev ; ///< Previous node
211 node_type * pCur ; ///< Current node
212 node_type * pNext ; ///< Next node
214 typename gc::template GuardArray<3> guards ; ///< Guards array
223 struct clean_disposer {
224 void operator()( value_type * p )
226 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
227 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
229 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
236 static void retire_node( node_type * pNode )
238 assert( pNode != nullptr );
239 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
242 static bool link_node( node_type * pNode, position& pos )
244 assert( pNode != nullptr );
245 link_checker::is_empty( pNode );
247 marked_node_ptr cur(pos.pCur);
248 pNode->m_pNext.store( cur, memory_model::memory_order_release );
249 return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
252 static bool unlink_node( position& pos )
254 assert( pos.pPrev != nullptr );
255 assert( pos.pCur != nullptr );
257 // Mark the node (logical deleting)
258 marked_node_ptr next(pos.pNext, 0);
259 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
260 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
261 // CAS may be successful here or in other thread that searching something
262 marked_node_ptr cur(pos.pCur);
263 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
264 retire_node( pos.pCur );
273 template <bool IsConst>
276 friend class MichaelList;
279 value_type * m_pNode;
280 typename gc::Guard m_Guard;
285 typename gc::Guard g;
286 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
288 marked_node_ptr pNext;
290 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
291 g.assign( node_traits::to_value_ptr( pNext.ptr() ));
292 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
295 m_pNode = m_Guard.assign( g.template get<value_type>() );
304 iterator_type( atomic_node_ptr const& pNode )
307 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
309 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
315 if ( p == pNode.load(memory_model::memory_order_acquire) )
321 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
322 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
328 iterator_type( iterator_type const& src )
331 m_pNode = m_Guard.assign( src.m_pNode );
337 value_ptr operator ->() const
342 value_ref operator *() const
344 assert( m_pNode != nullptr );
349 iterator_type& operator ++()
355 iterator_type& operator = (iterator_type const& src)
357 m_pNode = src.m_pNode;
358 m_Guard.assign( m_pNode );
364 void operator ++(int)
371 bool operator ==(iterator_type<C> const& i ) const
373 return m_pNode == i.m_pNode;
376 bool operator !=(iterator_type<C> const& i ) const
378 return m_pNode != i.m_pNode;
386 The forward iterator for Michael's list has some features:
387 - it has no post-increment operator
388 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
389 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
390 may be thrown if the limit of guard count per thread is exceeded.
391 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
392 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
393 deleting operations there is no guarantee that you iterate all item in the list.
395 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
396 for debug purpose only.
398 The iterator interface:
402 // Default constructor
406 iterator( iterator const& src );
408 // Dereference operator
409 value_type * operator ->() const;
411 // Dereference operator
412 value_type& operator *() const;
414 // Preincrement operator
415 iterator& operator ++();
417 // Assignment operator
418 iterator& operator = (iterator const& src);
420 // Equality operators
421 bool operator ==(iterator const& i ) const;
422 bool operator !=(iterator const& i ) const;
426 typedef iterator_type<false> iterator;
427 /// Const forward iterator
429 For iterator's features and requirements see \ref iterator
431 typedef iterator_type<true> const_iterator;
433 /// Returns a forward iterator addressing the first element in a list
435 For empty list \code begin() == end() \endcode
439 return iterator( m_pHead );
442 /// Returns an iterator that addresses the location succeeding the last element in a list
444 Do not use the value returned by <tt>end</tt> function to access any item.
445 Internally, <tt>end</tt> returning value equals to \p nullptr.
447 The returned value can be used only to control reaching the end of the list.
448 For empty list <tt>begin() == end()</tt>
455 /// Returns a forward const iterator addressing the first element in a list
456 const_iterator cbegin() const
458 return const_iterator( m_pHead );
461 /// Returns a forward const iterator addressing the first element in a list
462 const_iterator begin() const
464 return const_iterator( m_pHead );
467 /// Returns an const iterator that addresses the location succeeding the last element in a list
468 const_iterator end() const
470 return const_iterator();
473 /// Returns an const iterator that addresses the location succeeding the last element in a list
474 const_iterator cend() const
476 return const_iterator();
480 /// Default constructor initializes empty list
484 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
487 /// Destroys the list object
495 The function inserts \p val into the list if the list does not contain
496 an item with key equal to \p val.
498 Returns \p true if \p val has been linked to the list, \p false otherwise.
500 bool insert( value_type& val )
502 return insert_at( m_pHead, val );
507 This function is intended for derived non-intrusive containers.
509 The function allows to split new item creating into two part:
510 - create item with key only
511 - insert new item into the list
512 - if inserting is success, calls \p f functor to initialize value-field of \p val.
514 The functor signature is:
516 void func( value_type& val );
518 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
519 \p val no any other changes could be made on this list's item by concurrent threads.
520 The user-defined functor is called only if the inserting is success.
522 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
524 template <typename Func>
525 bool insert( value_type& val, Func f )
527 return insert_at( m_pHead, val, f );
530 /// Ensures that the \p val exists in the list
532 The operation performs inserting or changing data with lock-free manner.
534 If the item \p val is not found in the list, then \p val is inserted.
535 Otherwise, the functor \p func is called with item found.
536 The functor signature is:
538 void func( bool bNew, value_type& item, value_type& val );
541 - \p bNew - \p true if the item has been inserted, \p false otherwise
542 - \p item - item of the list
543 - \p val - argument \p val passed into the \p ensure function
544 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
545 refers to the same thing.
547 The functor may change non-key fields of the \p item; however, \p func must guarantee
548 that during changing no any other modifications could be made on this item by concurrent threads.
550 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
551 \p second is \p true if new item has been added or \p false if the item with \p key
552 already is in the list.
554 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
556 template <typename Func>
557 std::pair<bool, bool> ensure( value_type& val, Func func )
559 return ensure_at( m_pHead, val, func );
562 /// Unlinks the item \p val from the list
564 The function searches the item \p val in the list and unlinks it from the list
565 if it is found and it is equal to \p val.
567 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
568 and deletes the item found. \p %unlink() finds an item by key and deletes it
569 only if \p val is an item of the list, i.e. the pointer to item found
570 is equal to <tt> &val </tt>.
572 The function returns \p true if success and \p false otherwise.
574 bool unlink( value_type& val )
576 return unlink_at( m_pHead, val );
579 /// Deletes the item from the list
580 /** \anchor cds_intrusive_MichaelList_hp_erase_val
581 The function searches an item with key equal to \p key in the list,
582 unlinks it from the list, and returns \p true.
583 If \p key is not found the function return \p false.
585 template <typename Q>
586 bool erase( Q const& key )
588 return erase_at( m_pHead, key, key_comparator() );
591 /// Deletes the item from the list using \p pred predicate for searching
593 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
594 but \p pred is used for key comparing.
595 \p Less functor has the interface like \p std::less.
596 \p pred must imply the same element order as the comparator used for building the list.
598 template <typename Q, typename Less>
599 bool erase_with( Q const& key, Less pred )
602 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
605 /// Deletes the item from the list
606 /** \anchor cds_intrusive_MichaelList_hp_erase_func
607 The function searches an item with key equal to \p key in the list,
608 call \p func functor with item found, unlinks it from the list, and returns \p true.
609 The \p Func interface is
612 void operator()( value_type const& item );
615 If \p key is not found the function return \p false, \p func is not called.
617 template <typename Q, typename Func>
618 bool erase( Q const& key, Func func )
620 return erase_at( m_pHead, key, key_comparator(), func );
623 /// Deletes the item from the list using \p pred predicate for searching
625 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
626 but \p pred is used for key comparing.
627 \p Less functor has the interface like \p std::less.
628 \p pred must imply the same element order as the comparator used for building the list.
630 template <typename Q, typename Less, typename Func>
631 bool erase_with( Q const& key, Less pred, Func f )
634 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
637 /// Extracts the item from the list with specified \p key
638 /** \anchor cds_intrusive_MichaelList_hp_extract
639 The function searches an item with key equal to \p key,
640 unlinks it from the list, and returns it as \p guarded_ptr.
641 If \p key is not found returns an empty guarded pointer.
643 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
645 The \ref disposer specified in \p Traits class template parameter is called automatically
646 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
647 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
651 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
655 ord_list::guarded_ptr gp(theList.extract( 5 ));
660 // Destructor of gp releases internal HP guard
664 template <typename Q>
665 guarded_ptr extract( Q const& key )
668 extract_at( m_pHead, gp.guard(), key, key_comparator() );
672 /// Extracts the item using compare functor \p pred
674 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
675 but \p pred predicate is used for key comparing.
677 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
679 \p pred must imply the same element order as the comparator used for building the list.
681 template <typename Q, typename Less>
682 guarded_ptr extract_with( Q const& key, Less pred )
686 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
690 /// Finds \p key in the list
691 /** \anchor cds_intrusive_MichaelList_hp_find_func
692 The function searches the item with key equal to \p key and calls the functor \p f for item found.
693 The interface of \p Func functor is:
696 void operator()( value_type& item, Q& key );
699 where \p item is the item found, \p key is the <tt>find</tt> function argument.
701 The functor may change non-key fields of \p item. Note that the function is only guarantee
702 that \p item cannot be disposed during functor is executing.
703 The function does not serialize simultaneous access to the \p item. If such access is
704 possible you must provide your own synchronization schema to keep out unsafe item modifications.
706 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
707 may modify both arguments.
709 The function returns \p true if \p val is found, \p false otherwise.
711 template <typename Q, typename Func>
712 bool find( Q& key, Func f )
714 return find_at( m_pHead, key, key_comparator(), f );
717 template <typename Q, typename Func>
718 bool find( Q const& key, Func f )
720 return find_at( m_pHead, key, key_comparator(), f );
724 /// Finds the \p key using \p pred predicate for searching
726 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
727 but \p pred is used for key comparing.
728 \p Less functor has the interface like \p std::less.
729 \p pred must imply the same element order as the comparator used for building the list.
731 template <typename Q, typename Less, typename Func>
732 bool find_with( Q& key, Less pred, Func f )
735 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
738 template <typename Q, typename Less, typename Func>
739 bool find_with( Q const& key, Less pred, Func f )
742 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
747 /** \anchor cds_intrusive_MichaelList_hp_find_val
748 The function searches the item with key equal to \p key
749 and returns \p true if it is found, and \p false otherwise
751 template <typename Q>
752 bool find( Q const& key )
754 return find_at( m_pHead, key, key_comparator() );
757 /// Finds the key \p val using \p pred predicate for searching
759 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
760 but \p pred is used for key comparing.
761 \p Less functor has the interface like \p std::less.
762 \p pred must imply the same element order as the comparator used for building the list.
764 template <typename Q, typename Less>
765 bool find_with( Q const& key, Less pred )
768 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
771 /// Finds the \p key and return the item found
772 /** \anchor cds_intrusive_MichaelList_hp_get
773 The function searches the item with key equal to \p key
774 and returns it as \p guarded_ptr.
775 If \p key is not found the function returns an empty guarded pointer.
777 The \ref disposer specified in \p Traits class template parameter is called
778 by garbage collector \p GC automatically when returned \ref guarded_ptr object
779 will be destroyed or released.
780 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
784 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
788 ord_list::guarded_ptr gp(theList.get( 5 ));
793 // Destructor of guarded_ptr releases internal HP guard
797 Note the compare functor specified for \p Traits template parameter
798 should accept a parameter of type \p Q that can be not the same as \p value_type.
800 template <typename Q>
801 guarded_ptr get( Q const& key )
804 get_at( m_pHead, gp.guard(), key, key_comparator() );
808 /// Finds the \p key and return the item found
810 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
811 but \p pred is used for comparing the keys.
813 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
815 \p pred must imply the same element order as the comparator used for building the list.
817 template <typename Q, typename Less>
818 guarded_ptr get_with( Q const& key, Less pred )
822 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
828 The function unlink all items from the list.
832 typename gc::Guard guard;
833 marked_node_ptr head;
835 head = m_pHead.load(memory_model::memory_order_relaxed);
837 guard.assign( node_traits::to_value_ptr( *head.ptr() ));
838 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
839 if ( head.ptr() == nullptr )
841 value_type& val = *node_traits::to_value_ptr( *head.ptr() );
847 /// Checks whether the list is empty
850 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
853 /// Returns list's item count
855 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
856 this function always returns 0.
858 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
859 is empty. To check list emptyness use \p empty() method.
863 return m_ItemCounter.value();
868 // split-list support
869 bool insert_aux_node( node_type * pNode )
871 return insert_aux_node( m_pHead, pNode );
874 // split-list support
875 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
877 assert( pNode != nullptr );
879 // Hack: convert node_type to value_type.
880 // In principle, auxiliary node can be non-reducible to value_type
881 // We assume that comparator can correctly distinguish aux and regular node.
882 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
885 bool insert_at( atomic_node_ptr& refHead, value_type& val )
887 node_type * pNode = node_traits::to_node_ptr( val );
888 link_checker::is_empty( pNode );
892 if ( search( refHead, val, pos, key_comparator() ) )
895 if ( link_node( pNode, pos ) ) {
901 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
905 template <typename Func>
906 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
908 node_type * pNode = node_traits::to_node_ptr( val );
909 link_checker::is_empty( pNode );
913 if ( search( refHead, val, pos, key_comparator() ) )
916 typename gc::Guard guard;
917 guard.assign( &val );
918 if ( link_node( pNode, pos ) ) {
925 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
929 template <typename Func>
930 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
934 node_type * pNode = node_traits::to_node_ptr( val );
936 if ( search( refHead, val, pos, key_comparator() ) ) {
937 if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
939 continue ; // the node found is marked as deleted
941 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
943 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
944 return std::make_pair( true, false );
947 typename gc::Guard guard;
948 guard.assign( &val );
949 if ( link_node( pNode, pos ) ) {
951 func( true, val, val );
952 return std::make_pair( true, true );
955 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
960 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
965 while ( search( refHead, val, pos, key_comparator() ) ) {
966 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
967 if ( unlink_node( pos ) ) {
980 template <typename Q, typename Compare, typename Func>
981 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
984 while ( search( refHead, val, pos, cmp )) {
985 if ( unlink_node( pos ) ) {
986 f( *node_traits::to_value_ptr( *pos.pCur ) );
996 template <typename Q, typename Compare, typename Func>
997 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1000 return erase_at( refHead, val, cmp, f, pos );
1003 template <typename Q, typename Compare>
1004 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1007 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1010 template <typename Q, typename Compare>
1011 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1015 while ( search( refHead, val, pos, cmp )) {
1016 if ( unlink_node( pos ) ) {
1017 dest.set( pos.guards.template get<value_type>( position::guard_current_item ) );
1027 template <typename Q, typename Compare>
1028 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1031 return search( refHead, val, pos, cmp );
1034 template <typename Q, typename Compare, typename Func>
1035 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1038 if ( search( refHead, val, pos, cmp )) {
1039 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1045 template <typename Q, typename Compare>
1046 bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1049 if ( search( refHead, val, pos, cmp )) {
1050 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1061 template <typename Q, typename Compare >
1062 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1064 atomic_node_ptr * pPrev;
1065 marked_node_ptr pNext;
1066 marked_node_ptr pCur;
1074 pCur = pPrev->load(memory_model::memory_order_relaxed);
1075 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1076 if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1080 if ( pCur.ptr() == nullptr ) {
1083 pos.pNext = nullptr;
1087 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1088 CDS_TSAN_ANNOTATE_HAPPENS_AFTER( pNext.ptr() );
1089 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1090 if ( pCur->m_pNext.load(memory_model::memory_order_acquire).all() != pNext.all() ) {
1095 if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr() ) {
1100 // pNext contains deletion mark for pCur
1101 if ( pNext.bits() == 1 ) {
1102 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1103 marked_node_ptr cur( pCur.ptr());
1104 if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1105 retire_node( pCur.ptr() );
1113 assert( pCur.ptr() != nullptr );
1114 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1117 pos.pCur = pCur.ptr();
1118 pos.pNext = pNext.ptr();
1121 pPrev = &( pCur->m_pNext );
1122 pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1125 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1130 }} // namespace cds::intrusive
1132 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H