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 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< 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 pointer to an item found in \p dest parameter.
485 If \p key is not found the function returns \p false, \p dest is empty.
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 if ( theList.extract( p1, 10 )) {
511 // do something with p1
516 // We may safely release p1 here
517 // release() passes the pointer to RCU reclamation cycle:
518 // it invokes RCU retire_ptr function with the disposer you provided for the list.
522 template <typename Q>
523 bool extract( exempt_ptr& dest, Q const& key )
525 dest = extract_at( m_pHead, key, key_comparator() );
526 return !dest.empty();
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 bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
540 dest = extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
541 return !dest.empty();
544 /// Find the key \p val
545 /** \anchor cds_intrusive_MichaelList_rcu_find_func
546 The function searches the item with key equal to \p key
547 and calls the functor \p f for item found.
548 The interface of \p Func functor is:
551 void operator()( value_type& item, Q& key );
554 where \p item is the item found, \p key is the <tt>find</tt> function argument.
556 The functor can change non-key fields of \p item.
557 The function \p find does not serialize simultaneous access to the list \p item. If such access is
558 possible you must provide your own synchronization schema to exclude unsafe item modifications.
560 The function makes RCU lock internally.
562 The function returns \p true if \p val is found, \p false otherwise.
564 template <typename Q, typename Func>
565 bool find( Q& key, Func f ) const
567 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
570 /// Finds \p key using \p pred predicate for searching
572 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
573 but \p pred is used for key comparing.
574 \p Less functor has the interface like \p std::less.
575 \p pred must imply the same element order as the comparator used for building the list.
577 template <typename Q, typename Less, typename Func>
578 bool find_with( Q& key, Less pred, Func f ) const
580 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
584 /** \anchor cds_intrusive_MichaelList_rcu_find_val
585 The function searches the item with key equal to \p key
586 and returns \p true if \p val found or \p false otherwise.
588 template <typename Q>
589 bool find( Q const& key ) const
591 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator() );
594 /// Finds \p key using \p pred predicate for searching
596 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
597 but \p pred is used for key comparing.
598 \p Less functor has the interface like \p std::less.
599 \p pred must imply the same element order as the comparator used for building the list.
601 template <typename Q, typename Less>
602 bool find_with( Q const& key, Less pred ) const
604 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>() );
607 /// Finds \p key and return the item found
608 /** \anchor cds_intrusive_MichaelList_rcu_get
609 The function searches the item with key equal to \p key and returns the pointer to item found.
610 If \p key is not found it returns \p nullptr.
612 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
614 RCU should be locked before call of this function.
615 Returned item is valid only while RCU is locked:
617 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
622 ord_list::rcu_lock lock;
624 foo * pVal = theList.get( 5 );
629 // Unlock RCU by rcu_lock destructor
630 // pVal can be retired by disposer at any time after RCU has been unlocked
634 template <typename Q>
635 value_type * get( Q const& key ) const
637 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator());
640 /// Finds \p key and return the item found
642 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
643 but \p pred is used for comparing the keys.
645 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
647 \p pred must imply the same element order as the comparator used for building the list.
649 template <typename Q, typename Less>
650 value_type * get_with( Q const& key, Less pred ) const
652 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>());
655 /// Clears the list using default disposer
657 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
659 RCU \p synchronize method can be called.
660 Note that depending on RCU type used the \ref disposer invocation can be deferred.
662 The function can throw cds::urcu::rcu_deadlock exception if an deadlock is encountered and
663 deadlock checking policy is opt::v::rcu_throw_deadlock.
668 check_deadlock_policy::check();
670 marked_node_ptr pHead;
674 pHead = m_pHead.load(memory_model::memory_order_consume);
677 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
678 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
680 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
685 dispose_node( pHead.ptr() );
690 /// Check if the list is empty
693 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
696 /// Returns list's item count
698 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
699 this function always returns 0.
701 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
702 is empty. To check list emptyness use \p empty() method.
706 return m_ItemCounter.value();
711 // split-list support
712 bool insert_aux_node( node_type * pNode )
714 return insert_aux_node( m_pHead, pNode );
717 // split-list support
718 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
720 assert( pNode != nullptr );
722 // Hack: convert node_type to value_type.
723 // In principle, auxiliary node can be non-reducible to value_type
724 // We assume that comparator can correctly distinguish between aux and regular node.
725 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
728 bool insert_at( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
730 link_checker::is_empty( node_traits::to_node_ptr( val ) );
735 if ( search( refHead, val, pos, key_comparator() ) )
738 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
744 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
748 template <typename Func>
749 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
751 link_checker::is_empty( node_traits::to_node_ptr( val ) );
756 if ( search( refHead, val, pos, key_comparator() ) )
759 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
766 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
770 iterator insert_at_( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
773 if ( insert_at( refHead, val, false ))
774 return iterator( node_traits::to_node_ptr( val ));
778 template <typename Func>
779 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
785 if ( search( refHead, val, pos, key_comparator() ) ) {
786 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
788 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
789 return std::make_pair( iterator( pos.pCur ), false );
792 link_checker::is_empty( node_traits::to_node_ptr( val ) );
794 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
796 func( true, val , val );
797 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
800 // clear the next field
801 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
806 template <typename Func>
807 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
810 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func, false );
811 return std::make_pair( ret.first != end(), ret.second );
814 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
818 check_deadlock_policy::check();
823 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
825 if ( !unlink_node( pos )) {
832 dispose_node( pos.pCur );
837 template <typename Q, typename Compare, typename Func>
838 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
841 check_deadlock_policy::check();
846 if ( !search( refHead, val, pos, cmp ) )
848 if ( !unlink_node( pos )) {
854 f( *node_traits::to_value_ptr( *pos.pCur ) );
856 dispose_node( pos.pCur );
861 template <typename Q, typename Compare, typename Func>
862 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
865 return erase_at( refHead, val, cmp, f, pos );
868 template <typename Q, typename Compare>
869 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
872 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
875 template <typename Q, typename Compare >
876 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
880 assert( gc::is_locked() ) ; // RCU must be locked!!!
883 if ( !search( refHead, val, pos, cmp ) )
885 if ( !unlink_node( pos )) {
891 return node_traits::to_value_ptr( pos.pCur );
895 template <typename Q, typename Compare, typename Func>
896 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
901 if ( search( refHead, val, pos, cmp ) ) {
902 assert( pos.pCur != nullptr );
903 f( *node_traits::to_value_ptr( *pos.pCur ), val );
909 template <typename Q, typename Compare>
910 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
913 return find_at_( refHead, val, cmp ) != end();
916 template <typename Q, typename Compare>
917 value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
919 value_type * pFound = nullptr;
920 return find_at( refHead, val, cmp,
921 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
925 template <typename Q, typename Compare>
926 const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
928 assert( gc::is_locked() );
931 if ( search( refHead, val, pos, cmp ) ) {
932 assert( pos.pCur != nullptr );
933 return const_iterator( pos.pCur );
943 template <typename Q, typename Compare>
944 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp ) const
946 // RCU lock should be locked!!!
947 assert( gc::is_locked() );
949 atomic_node_ptr * pPrev;
950 marked_node_ptr pNext;
951 marked_node_ptr pCur;
957 pCur = pPrev->load(memory_model::memory_order_acquire);
963 pos.pCur = pCur.ptr();
964 pos.pNext = pNext.ptr();
968 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
970 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
971 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)
972 || pNext.bits() != 0 ) // pNext contains deletion mark for pCur
974 // if pCur is marked as deleted (pNext.bits() != 0)
975 // we wait for physical removal.
976 // Helping technique is not suitable for RCU since it requires
977 // that the RCU should be in unlocking state.
982 assert( pCur.ptr() != nullptr );
983 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
986 pos.pCur = pCur.ptr();
987 pos.pNext = pNext.ptr();
990 pPrev = &( pCur->m_pNext );
997 }} // namespace cds::intrusive
999 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H