3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_RCU_H
4 #define __CDS_INTRUSIVE_MICHAEL_LIST_RCU_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/urcu/details/check_deadlock.h>
8 #include <cds/details/binary_functor_wrapper.h>
9 #include <cds/details/make_const_type.h>
10 #include <cds/urcu/exempt_ptr.h>
12 namespace cds { namespace intrusive {
14 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
15 /** @ingroup cds_intrusive_list
16 \anchor cds_intrusive_MichaelList_rcu
18 Usually, ordered single-linked list is used as a building block for the hash table implementation.
19 The complexity of searching is <tt>O(N)</tt>.
22 - \p RCU - one of \ref cds_urcu_gc "RCU type"
23 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
24 cds::intrusive::micheal_list::node
25 - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
26 list with \p cds::intrusive::michael_list::make_traits metafunction,
27 see \ref cds_intrusive_MichaelList_hp "here" for explanations.
30 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
31 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
32 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
34 #include <cds/urcu/general_buffered.h>
35 #include <cds/intrusive/michael_list_rcu.h>
37 // Now, you can declare Michael's list for type Foo and default traits:
38 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
41 template < typename RCU, typename T,
42 #ifdef CDS_DOXYGEN_INVOKED
43 class Traits = michael_list::traits
48 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
51 typedef T value_type; ///< type of value stored in the list
52 typedef Traits traits; ///< Traits template parameter
54 typedef typename traits::hook hook; ///< hook type
55 typedef typename hook::node_type node_type; ///< node type
57 # ifdef CDS_DOXYGEN_INVOKED
58 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
60 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
63 typedef typename traits::disposer disposer; ///< disposer used
64 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
65 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
67 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
68 typedef typename traits::back_off back_off; ///< back-off strategy
69 typedef typename traits::item_counter item_counter; ///< Item counting policy used
70 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
71 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
73 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
74 static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
77 // Rebind traits (split-list support)
78 template <typename... Options>
79 struct rebind_traits {
83 , typename cds::opt::make_options< traits, Options...>::type
89 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
90 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
91 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
93 atomic_node_ptr m_pHead ; ///< Head pointer
94 item_counter m_ItemCounter ; ///< Item counter
97 /// Position pointer for item search
99 atomic_node_ptr * pPrev ; ///< Previous node
100 node_type * pCur ; ///< Current node
101 node_type * pNext ; ///< Next node
104 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
106 static void clear_links( node_type * pNode )
108 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
111 struct clear_and_dispose {
112 void operator()( value_type * p )
114 assert( p != nullptr );
115 clear_links( node_traits::to_node_ptr(p));
122 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
127 static void dispose_node( node_type * pNode )
130 assert( !gc::is_locked() );
132 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
135 bool link_node( node_type * pNode, position& pos )
137 assert( pNode != nullptr );
138 link_checker::is_empty( pNode );
140 marked_node_ptr p( pos.pCur );
141 pNode->m_pNext.store( p, memory_model::memory_order_relaxed );
142 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
145 bool unlink_node( position& pos )
147 // Mark the node (logical deleting)
148 marked_node_ptr next(pos.pNext, 0);
149 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
150 marked_node_ptr cur(pos.pCur);
151 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
154 CDS_VERIFY( pos.pCur->m_pNext.compare_exchange_strong( next, next ^ 1, memory_model::memory_order_release, atomics::memory_order_relaxed ));
162 template <bool IsConst>
165 friend class MichaelList;
166 value_type * m_pNode;
171 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
172 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
177 explicit iterator_type( node_type * pNode)
180 m_pNode = node_traits::to_value_ptr( *pNode );
184 explicit iterator_type( atomic_node_ptr const& refNode)
186 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
187 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
191 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
192 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
198 iterator_type( const iterator_type& src )
199 : m_pNode( src.m_pNode )
202 value_ptr operator ->() const
207 value_ref operator *() const
209 assert( m_pNode != nullptr );
214 iterator_type& operator ++()
221 iterator_type operator ++(int)
223 iterator_type i(*this);
228 iterator_type& operator = (const iterator_type& src)
230 m_pNode = src.m_pNode;
235 bool operator ==(iterator_type<C> const& i ) const
237 return m_pNode == i.m_pNode;
240 bool operator !=(iterator_type<C> const& i ) const
242 return m_pNode != i.m_pNode;
249 typedef iterator_type<false> iterator;
250 /// Const forward iterator
251 typedef iterator_type<true> const_iterator;
253 /// Returns a forward iterator addressing the first element in a list
255 For empty list \code begin() == end() \endcode
259 return iterator( m_pHead );
262 /// Returns an iterator that addresses the location succeeding the last element in a list
264 Do not use the value returned by <tt>end</tt> function to access any item.
265 Internally, <tt>end</tt> returning value equals to \p nullptr.
267 The returned value can be used only to control reaching the end of the list.
268 For empty list \code begin() == end() \endcode
275 /// Returns a forward const iterator addressing the first element in a list
276 const_iterator begin() const
278 return const_iterator(m_pHead );
280 /// Returns a forward const iterator addressing the first element in a list
281 const_iterator cbegin() const
283 return const_iterator(m_pHead );
286 /// Returns an const iterator that addresses the location succeeding the last element in a list
287 const_iterator end() const
289 return const_iterator();
291 /// Returns an const iterator that addresses the location succeeding the last element in a list
292 const_iterator cend() const
294 return const_iterator();
298 /// Default constructor initializes empty list
302 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
313 The function inserts \p val in the list if the list does not contain
314 an item with key equal to \p val.
316 The function makes RCU lock internally.
318 Returns \p true if \p val is linked into the list, \p false otherwise.
320 bool insert( value_type& val )
322 return insert_at( m_pHead, val );
327 This function is intended for derived non-intrusive containers.
329 The function allows to split new item creating into two part:
330 - create item with key only
331 - insert new item into the list
332 - if inserting is success, calls \p f functor to initialize value-field of \p val.
334 The functor signature is:
336 void func( value_type& val );
338 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
339 \p val no any other changes could be made on this list's item by concurrent threads.
340 The user-defined functor is called only if the inserting is success.
342 The function makes RCU lock internally.
344 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
346 template <typename Func>
347 bool insert( value_type& val, Func f )
349 return insert_at( m_pHead, val, f );
352 /// Ensures that the \p item exists in the list
354 The operation performs inserting or changing data with lock-free manner.
356 If the item \p val not found in the list, then \p val is inserted into the list.
357 Otherwise, the functor \p func is called with item found.
358 The functor signature is:
361 void operator()( bool bNew, value_type& item, value_type& val );
365 - \p bNew - \p true if the item has been inserted, \p false otherwise
366 - \p item - item of the list
367 - \p val - argument \p val passed into the \p ensure function
368 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
369 refer to the same thing.
371 The functor may change non-key fields of the \p item; however, \p func must guarantee
372 that during changing no any other modifications could be made on this item by concurrent threads.
374 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
375 \p second is true if new item has been added or \p false if the item with \p key
376 already is in the list.
378 The function makes RCU lock internally.
380 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
382 template <typename Func>
383 std::pair<bool, bool> ensure( value_type& val, Func func )
385 return ensure_at( m_pHead, val, func );
388 /// Unlinks the item \p val from the list
390 The function searches the item \p val in the list and unlink it from the list
391 if it is found and it is equal to \p val.
393 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
394 and deletes the item found. \p unlink finds an item by key and deletes it
395 only if \p val is an item of that list, i.e. the pointer to the item found
396 is equal to <tt> &val </tt>.
398 The function returns \p true if success and \p false otherwise.
400 RCU \p synchronize method can be called.
401 Note that depending on RCU type used the \ref disposer call can be deferred.
403 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
404 deadlock checking policy is opt::v::rcu_throw_deadlock.
406 bool unlink( value_type& val )
408 return unlink_at( m_pHead, val );
411 /// Deletes the item from the list
412 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
413 The function searches an item with key equal to \p key in the list,
414 unlinks it from the list, and returns \p true.
415 If the item with the key equal to \p key is not found the function return \p false.
417 RCU \p synchronize method can be called.
418 Note that depending on RCU type used the \ref disposer call can be deferred.
420 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
421 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
423 template <typename Q>
424 bool erase( Q const& key )
426 return erase_at( m_pHead, key, key_comparator() );
429 /// Deletes the item from the list using \p pred predicate for searching
431 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
432 but \p pred is used for key comparing.
433 \p Less functor has the interface like \p std::less.
434 \p pred must imply the same element order as the comparator used for building the list.
436 template <typename Q, typename Less>
437 bool erase_with( Q const& key, Less pred )
439 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
442 /// Deletes the item from the list
443 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
444 The function searches an item with key equal to \p key in the list,
445 call \p func functor with item found, unlinks it from the list, and returns \p true.
446 The \p Func interface is
449 void operator()( value_type const& item );
453 If the item with the key equal to \p key is not found the function return \p false.
455 RCU \p synchronize method can be called.
456 Note that depending on RCU type used the \ref disposer call can be deferred.
458 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
459 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
461 template <typename Q, typename Func>
462 bool erase( Q const& key, Func func )
464 return erase_at( m_pHead, key, key_comparator(), func );
467 /// Deletes the item from the list using \p pred predicate for searching
469 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
470 but \p pred is used for key comparing.
471 \p Less functor has the interface like \p std::less.
472 \p pred must imply the same element order as the comparator used for building the list.
474 template <typename Q, typename Less, typename Func>
475 bool erase_with( Q const& key, Less pred, Func func )
477 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
480 /// Extracts an item from the list
482 @anchor cds_intrusive_MichaelList_rcu_extract
483 The function searches an item with key equal to \p key in the list,
484 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
485 If \p key is not found the function returns an empty \p exempt_ptr.
487 @note The function does NOT call RCU read-side lock or synchronization,
488 and does NOT dispose the item found. It just unlinks the item from the list
489 and returns a pointer to item found.
490 You should lock RCU before calling this function, and you should manually release
491 \p dest exempt pointer outside the RCU lock before reusing the pointer.
494 #include <cds/urcu/general_buffered.h>
495 #include <cds/intrusive/michael_list_rcu.h>
497 typedef cds::urcu::gc< general_buffered<> > rcu;
498 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
500 rcu_michael_list theList;
503 rcu_michael_list::exempt_ptr p1;
505 // first, we should lock RCU
508 // Now, you can apply extract function
509 // Note that you must not delete the item found inside the RCU lock
510 p1 = theList.extract( 10 )
512 // do something with p1
517 // We may safely release p1 here
518 // release() passes the pointer to RCU reclamation cycle:
519 // it invokes RCU retire_ptr function with the disposer you provided for the list.
523 template <typename Q>
524 exempt_ptr extract( Q const& key )
526 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
529 /// Extracts an item from the list using \p pred predicate for searching
531 This function is the analog for \ref cds_intrusive_MichaelList_rcu_extract "extract(exempt_ptr&, Q const&)".
533 The \p pred is a predicate used for key comparing.
534 \p Less has the interface like \p std::less.
535 \p pred must imply the same element order as \ref key_comparator.
537 template <typename Q, typename Less>
538 exempt_ptr extract_with( Q const& key, Less pred )
540 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
543 /// Find the key \p val
544 /** \anchor cds_intrusive_MichaelList_rcu_find_func
545 The function searches the item with key equal to \p key
546 and calls the functor \p f for item found.
547 The interface of \p Func functor is:
550 void operator()( value_type& item, Q& key );
553 where \p item is the item found, \p key is the <tt>find</tt> function argument.
555 The functor can change non-key fields of \p item.
556 The function \p find does not serialize simultaneous access to the list \p item. If such access is
557 possible you must provide your own synchronization schema to exclude unsafe item modifications.
559 The function makes RCU lock internally.
561 The function returns \p true if \p val is found, \p false otherwise.
563 template <typename Q, typename Func>
564 bool find( Q& key, Func f ) const
566 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
569 template <typename Q, typename Func>
570 bool find( Q const& key, Func f ) const
572 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
576 /// Finds \p key using \p pred predicate for searching
578 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
579 but \p pred is used for key comparing.
580 \p Less functor has the interface like \p std::less.
581 \p pred must imply the same element order as the comparator used for building the list.
583 template <typename Q, typename Less, typename Func>
584 bool find_with( Q& key, Less pred, Func f ) const
586 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
589 template <typename Q, typename Less, typename Func>
590 bool find_with( Q const& key, Less pred, Func f ) const
592 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, cds::opt::details::make_comparator_from_less<Less>(), f );
597 /** \anchor cds_intrusive_MichaelList_rcu_find_val
598 The function searches the item with key equal to \p key
599 and returns \p true if \p val found or \p false otherwise.
601 template <typename Q>
602 bool find( Q const& key ) const
604 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator() );
607 /// Finds \p key using \p pred predicate for searching
609 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
610 but \p pred is used for key comparing.
611 \p Less functor has the interface like \p std::less.
612 \p pred must imply the same element order as the comparator used for building the list.
614 template <typename Q, typename Less>
615 bool find_with( Q const& key, Less pred ) const
617 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>() );
620 /// Finds \p key and return the item found
621 /** \anchor cds_intrusive_MichaelList_rcu_get
622 The function searches the item with key equal to \p key and returns the pointer to item found.
623 If \p key is not found it returns \p nullptr.
625 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
627 RCU should be locked before call of this function.
628 Returned item is valid only while RCU is locked:
630 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
635 ord_list::rcu_lock lock;
637 foo * pVal = theList.get( 5 );
642 // Unlock RCU by rcu_lock destructor
643 // pVal can be retired by disposer at any time after RCU has been unlocked
647 template <typename Q>
648 value_type * get( Q const& key ) const
650 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator());
653 /// Finds \p key and return the item found
655 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
656 but \p pred is used for comparing the keys.
658 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
660 \p pred must imply the same element order as the comparator used for building the list.
662 template <typename Q, typename Less>
663 value_type * get_with( Q const& key, Less pred ) const
665 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>());
668 /// Clears the list using default disposer
670 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
672 RCU \p synchronize method can be called.
673 Note that depending on RCU type used the \ref disposer invocation can be deferred.
675 The function can throw cds::urcu::rcu_deadlock exception if an deadlock is encountered and
676 deadlock checking policy is opt::v::rcu_throw_deadlock.
681 check_deadlock_policy::check();
683 marked_node_ptr pHead;
687 pHead = m_pHead.load(memory_model::memory_order_consume);
690 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
691 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
693 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
698 dispose_node( pHead.ptr() );
703 /// Check if the list is empty
706 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
709 /// Returns list's item count
711 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
712 this function always returns 0.
714 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
715 is empty. To check list emptyness use \p empty() method.
719 return m_ItemCounter.value();
724 // split-list support
725 bool insert_aux_node( node_type * pNode )
727 return insert_aux_node( m_pHead, pNode );
730 // split-list support
731 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
733 assert( pNode != nullptr );
735 // Hack: convert node_type to value_type.
736 // In principle, auxiliary node can be non-reducible to value_type
737 // We assume that comparator can correctly distinguish between aux and regular node.
738 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
741 bool insert_at( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
743 link_checker::is_empty( node_traits::to_node_ptr( val ) );
748 if ( search( refHead, val, pos, key_comparator() ) )
751 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
757 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
761 template <typename Func>
762 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
764 link_checker::is_empty( node_traits::to_node_ptr( val ) );
769 if ( search( refHead, val, pos, key_comparator() ) )
772 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
779 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
783 iterator insert_at_( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
786 if ( insert_at( refHead, val, false ))
787 return iterator( node_traits::to_node_ptr( val ));
791 template <typename Func>
792 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
798 if ( search( refHead, val, pos, key_comparator() ) ) {
799 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
801 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
802 return std::make_pair( iterator( pos.pCur ), false );
805 link_checker::is_empty( node_traits::to_node_ptr( val ) );
807 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
809 func( true, val , val );
810 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
813 // clear the next field
814 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
819 template <typename Func>
820 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
823 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func, false );
824 return std::make_pair( ret.first != end(), ret.second );
827 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
831 check_deadlock_policy::check();
836 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
838 if ( !unlink_node( pos )) {
845 dispose_node( pos.pCur );
850 template <typename Q, typename Compare, typename Func>
851 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
854 check_deadlock_policy::check();
859 if ( !search( refHead, val, pos, cmp ) )
861 if ( !unlink_node( pos )) {
867 f( *node_traits::to_value_ptr( *pos.pCur ) );
869 dispose_node( pos.pCur );
874 template <typename Q, typename Compare, typename Func>
875 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
878 return erase_at( refHead, val, cmp, f, pos );
881 template <typename Q, typename Compare>
882 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
885 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
888 template <typename Q, typename Compare >
889 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
893 assert( gc::is_locked() ) ; // RCU must be locked!!!
896 if ( !search( refHead, val, pos, cmp ) )
898 if ( !unlink_node( pos )) {
904 return node_traits::to_value_ptr( pos.pCur );
908 template <typename Q, typename Compare, typename Func>
909 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
914 if ( search( refHead, val, pos, cmp ) ) {
915 assert( pos.pCur != nullptr );
916 f( *node_traits::to_value_ptr( *pos.pCur ), val );
922 template <typename Q, typename Compare>
923 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
926 return find_at_( refHead, val, cmp ) != end();
929 template <typename Q, typename Compare>
930 value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
932 value_type * pFound = nullptr;
933 return find_at( refHead, val, cmp,
934 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
938 template <typename Q, typename Compare>
939 const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
941 assert( gc::is_locked() );
944 if ( search( refHead, val, pos, cmp ) ) {
945 assert( pos.pCur != nullptr );
946 return const_iterator( pos.pCur );
956 template <typename Q, typename Compare>
957 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp ) const
959 // RCU lock should be locked!!!
960 assert( gc::is_locked() );
962 atomic_node_ptr * pPrev;
963 marked_node_ptr pNext;
964 marked_node_ptr pCur;
970 pCur = pPrev->load(memory_model::memory_order_acquire);
976 pos.pCur = pCur.ptr();
977 pos.pNext = pNext.ptr();
981 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
983 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
984 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)
985 || pNext.bits() != 0 ) // pNext contains deletion mark for pCur
987 // if pCur is marked as deleted (pNext.bits() != 0)
988 // we wait for physical removal.
989 // Helping technique is not suitable for RCU since it requires
990 // that the RCU should be in unlocking state.
995 assert( pCur.ptr() != nullptr );
996 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
999 pos.pCur = pCur.ptr();
1000 pos.pNext = pNext.ptr();
1003 pPrev = &( pCur->m_pNext );
1010 }} // namespace cds::intrusive
1012 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H