3 #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
4 #define CDSLIB_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 {
15 namespace michael_list {
17 /// Node specialization for uRCU
18 template <class RCU, typename Tag>
19 struct node< cds::urcu::gc< RCU >, Tag >
21 typedef cds::urcu::gc< RCU > gc; ///< Garbage collector
22 typedef Tag tag; ///< tag
24 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
25 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
27 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
28 node * m_pDelChain; ///< Deleted node chain (local for a thread)
30 CDS_CONSTEXPR node() CDS_NOEXCEPT
32 , m_pDelChain( nullptr )
35 } // namespace michael_list
38 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
39 /** @ingroup cds_intrusive_list
40 \anchor cds_intrusive_MichaelList_rcu
42 Usually, ordered single-linked list is used as a building block for the hash table implementation.
43 The complexity of searching is <tt>O(N)</tt>.
46 - \p RCU - one of \ref cds_urcu_gc "RCU type"
47 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
48 cds::intrusive::micheal_list::node
49 - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
50 list with \p cds::intrusive::michael_list::make_traits metafunction,
51 see \ref cds_intrusive_MichaelList_hp "here" for explanations.
54 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
55 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
56 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
58 #include <cds/urcu/general_buffered.h>
59 #include <cds/intrusive/michael_list_rcu.h>
61 // Now, you can declare Michael's list for type Foo and default traits:
62 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
65 template < typename RCU, typename T,
66 #ifdef CDS_DOXYGEN_INVOKED
67 class Traits = michael_list::traits
72 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
75 typedef T value_type; ///< type of value stored in the list
76 typedef Traits traits; ///< Traits template parameter
78 typedef typename traits::hook hook; ///< hook type
79 typedef typename hook::node_type node_type; ///< node type
81 # ifdef CDS_DOXYGEN_INVOKED
82 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
84 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
87 typedef typename traits::disposer disposer; ///< disposer used
88 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
89 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
91 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
92 typedef typename traits::back_off back_off; ///< back-off strategy
93 typedef typename traits::item_counter item_counter; ///< Item counting policy used
94 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
95 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
97 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
98 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
101 // Rebind traits (split-list support)
102 template <typename... Options>
103 struct rebind_traits {
107 , typename cds::opt::make_options< traits, Options...>::type
113 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
114 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
115 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
117 atomic_node_ptr m_pHead ; ///< Head pointer
118 item_counter m_ItemCounter ; ///< Item counter
128 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
130 static void clear_links( node_type * pNode )
132 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
133 pNode->m_pDelChain = nullptr;
136 struct clear_and_dispose {
137 void operator()( value_type * p )
139 assert( p != nullptr );
140 clear_links( node_traits::to_node_ptr(p));
145 static void dispose_node( node_type * pNode )
148 assert( !gc::is_locked() );
150 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
153 /// Position pointer for item search
155 atomic_node_ptr * pPrev ; ///< Previous node
156 node_type * pCur ; ///< Current node
157 node_type * pNext ; ///< Next node
159 atomic_node_ptr& refHead;
160 node_type * pDelChain; ///< Head of deleted node chain
162 position( atomic_node_ptr& head )
164 , pDelChain( nullptr )
169 assert( !gc::is_locked() );
171 node_type * chain = pDelChain;
173 auto f = [&chain]() -> cds::urcu::retired_ptr {
174 node_type * p = chain;
175 chain = p->m_pDelChain;
176 return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
178 gc::batch_retire(std::ref(f));
186 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
191 bool link_node( node_type * pNode, position& pos )
193 assert( pNode != nullptr );
194 link_checker::is_empty( pNode );
196 marked_node_ptr p( pos.pCur );
197 pNode->m_pNext.store( p, memory_model::memory_order_release );
198 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
201 static void link_to_remove_chain( position& pos, node_type * pDel )
203 assert( pDel->m_pDelChain == nullptr );
205 pDel->m_pDelChain = pos.pDelChain;
206 pos.pDelChain = pDel;
209 bool unlink_node( position& pos, erase_node_mask nMask )
211 // Mark the node (logical deletion)
212 marked_node_ptr next(pos.pNext, 0);
214 if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )) {
216 // Try physical removal - fast path
217 marked_node_ptr cur(pos.pCur);
218 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
219 if ( nMask == erase_mask )
220 link_to_remove_chain( pos, pos.pCur );
224 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
234 template <bool IsConst>
237 friend class MichaelList;
238 value_type * m_pNode;
243 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
244 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
249 explicit iterator_type( node_type * pNode)
252 m_pNode = node_traits::to_value_ptr( *pNode );
256 explicit iterator_type( atomic_node_ptr const& refNode)
258 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
259 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
263 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
264 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
270 iterator_type( const iterator_type& src )
271 : m_pNode( src.m_pNode )
274 value_ptr operator ->() const
279 value_ref operator *() const
281 assert( m_pNode != nullptr );
286 iterator_type& operator ++()
293 iterator_type operator ++(int)
295 iterator_type i(*this);
300 iterator_type& operator = (const iterator_type& src)
302 m_pNode = src.m_pNode;
307 bool operator ==(iterator_type<C> const& i ) const
309 return m_pNode == i.m_pNode;
312 bool operator !=(iterator_type<C> const& i ) const
314 return m_pNode != i.m_pNode;
321 typedef iterator_type<false> iterator;
322 /// Const forward iterator
323 typedef iterator_type<true> const_iterator;
325 /// Returns a forward iterator addressing the first element in a list
327 For empty list \code begin() == end() \endcode
331 return iterator( m_pHead );
334 /// Returns an iterator that addresses the location succeeding the last element in a list
336 Do not use the value returned by <tt>end</tt> function to access any item.
337 Internally, <tt>end</tt> returning value equals to \p nullptr.
339 The returned value can be used only to control reaching the end of the list.
340 For empty list \code begin() == end() \endcode
347 /// Returns a forward const iterator addressing the first element in a list
348 const_iterator begin() const
350 return const_iterator(m_pHead );
352 /// Returns a forward const iterator addressing the first element in a list
353 const_iterator cbegin() const
355 return const_iterator(m_pHead );
358 /// Returns an const iterator that addresses the location succeeding the last element in a list
359 const_iterator end() const
361 return const_iterator();
363 /// Returns an const iterator that addresses the location succeeding the last element in a list
364 const_iterator cend() const
366 return const_iterator();
370 /// Default constructor initializes empty list
374 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
385 The function inserts \p val in the list if the list does not contain
386 an item with key equal to \p val.
388 The function makes RCU lock internally.
390 Returns \p true if \p val is linked into the list, \p false otherwise.
392 bool insert( value_type& val )
394 return insert_at( m_pHead, val );
399 This function is intended for derived non-intrusive containers.
401 The function allows to split new item creating into two part:
402 - create item with key only
403 - insert new item into the list
404 - if inserting is success, calls \p f functor to initialize value-field of \p val.
406 The functor signature is:
408 void func( value_type& val );
410 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
411 \p val no any other changes could be made on this list's item by concurrent threads.
412 The user-defined functor is called only if the inserting is success.
414 The function makes RCU lock internally.
416 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
418 template <typename Func>
419 bool insert( value_type& val, Func f )
421 return insert_at( m_pHead, val, f );
424 /// Ensures that the \p item exists in the list
426 The operation performs inserting or changing data with lock-free manner.
428 If the item \p val not found in the list, then \p val is inserted into the list.
429 Otherwise, the functor \p func is called with item found.
430 The functor signature is:
433 void operator()( bool bNew, value_type& item, value_type& val );
437 - \p bNew - \p true if the item has been inserted, \p false otherwise
438 - \p item - item of the list
439 - \p val - argument \p val passed into the \p ensure function
440 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
441 refer to the same thing.
443 The functor may change non-key fields of the \p item; however, \p func must guarantee
444 that during changing no any other modifications could be made on this item by concurrent threads.
446 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
447 \p second is true if new item has been added or \p false if the item with \p key
448 already is in the list.
450 The function makes RCU lock internally.
452 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
454 template <typename Func>
455 std::pair<bool, bool> ensure( value_type& val, Func func )
457 return ensure_at( m_pHead, val, func );
460 /// Unlinks the item \p val from the list
462 The function searches the item \p val in the list and unlink it from the list
463 if it is found and it is equal to \p val.
465 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
466 and deletes the item found. \p unlink finds an item by key and deletes it
467 only if \p val is an item of that list, i.e. the pointer to the item found
468 is equal to <tt> &val </tt>.
470 The function returns \p true if success and \p false otherwise.
472 RCU \p synchronize method can be called.
473 Note that depending on RCU type used the \ref disposer call can be deferred.
475 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
476 deadlock checking policy is opt::v::rcu_throw_deadlock.
478 bool unlink( value_type& val )
480 return unlink_at( m_pHead, val );
483 /// Deletes the item from the list
484 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
485 The function searches an item with key equal to \p key in the list,
486 unlinks it from the list, and returns \p true.
487 If the item with the key equal to \p key is not found the function return \p false.
489 RCU \p synchronize method can be called.
490 Note that depending on RCU type used the \ref disposer call can be deferred.
492 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
493 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
495 template <typename Q>
496 bool erase( Q const& key )
498 return erase_at( m_pHead, key, key_comparator() );
501 /// Deletes the item from the list using \p pred predicate for searching
503 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
504 but \p pred is used for key comparing.
505 \p Less functor has the interface like \p std::less.
506 \p pred must imply the same element order as the comparator used for building the list.
508 template <typename Q, typename Less>
509 bool erase_with( Q const& key, Less pred )
512 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
515 /// Deletes the item from the list
516 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
517 The function searches an item with key equal to \p key in the list,
518 call \p func functor with item found, unlinks it from the list, and returns \p true.
519 The \p Func interface is
522 void operator()( value_type const& item );
526 If the item with the key equal to \p key is not found the function return \p false.
528 RCU \p synchronize method can be called.
529 Note that depending on RCU type used the \ref disposer call can be deferred.
531 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
532 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
534 template <typename Q, typename Func>
535 bool erase( Q const& key, Func func )
537 return erase_at( m_pHead, key, key_comparator(), func );
540 /// Deletes the item from the list using \p pred predicate for searching
542 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
543 but \p pred is used for key comparing.
544 \p Less functor has the interface like \p std::less.
545 \p pred must imply the same element order as the comparator used for building the list.
547 template <typename Q, typename Less, typename Func>
548 bool erase_with( Q const& key, Less pred, Func func )
551 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
554 /// Extracts an item from the list
556 @anchor cds_intrusive_MichaelList_rcu_extract
557 The function searches an item with key equal to \p key in the list,
558 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
559 If \p key is not found the function returns an empty \p exempt_ptr.
561 @note The function does NOT dispose the item found. It just unlinks the item from the list
562 and returns a pointer to item found.
563 You shouldn't lock RCU before calling this function, and you should manually release
564 \p dest exempt pointer outside the RCU lock before reusing the pointer.
567 #include <cds/urcu/general_buffered.h>
568 #include <cds/intrusive/michael_list_rcu.h>
570 typedef cds::urcu::gc< general_buffered<> > rcu;
571 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
573 rcu_michael_list theList;
576 rcu_michael_list::exempt_ptr p1;
578 // The RCU should NOT be locked when extract() is called!
579 assert( !rcu::is_locked() );
581 // You can call extract() function
582 p1 = theList.extract( 10 );
584 // do something with p1
588 // We may safely release p1 here
589 // release() passes the pointer to RCU reclamation cycle:
590 // it invokes RCU retire_ptr function with the disposer you provided for the list.
594 template <typename Q>
595 exempt_ptr extract( Q const& key )
597 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
600 /// Extracts an item from the list using \p pred predicate for searching
602 This function is the analog for \p extract(Q const&)
604 The \p pred is a predicate used for key comparing.
605 \p Less has the interface like \p std::less.
606 \p pred must imply the same element order as \ref key_comparator.
608 template <typename Q, typename Less>
609 exempt_ptr extract_with( Q const& key, Less pred )
612 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
615 /// Find the key \p val
616 /** \anchor cds_intrusive_MichaelList_rcu_find_func
617 The function searches the item with key equal to \p key
618 and calls the functor \p f for item found.
619 The interface of \p Func functor is:
622 void operator()( value_type& item, Q& key );
625 where \p item is the item found, \p key is the <tt>find</tt> function argument.
627 The functor can change non-key fields of \p item.
628 The function \p find does not serialize simultaneous access to the list \p item. If such access is
629 possible you must provide your own synchronization schema to exclude unsafe item modifications.
631 The function makes RCU lock internally.
633 The function returns \p true if \p val is found, \p false otherwise.
635 template <typename Q, typename Func>
636 bool find( Q& key, Func f )
638 return find_at( m_pHead, key, key_comparator(), f );
641 template <typename Q, typename Func>
642 bool find( Q const& key, Func f )
644 return find_at( m_pHead, key, key_comparator(), f );
648 /// Finds \p key using \p pred predicate for searching
650 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
651 but \p pred is used for key comparing.
652 \p Less functor has the interface like \p std::less.
653 \p pred must imply the same element order as the comparator used for building the list.
655 template <typename Q, typename Less, typename Func>
656 bool find_with( Q& key, Less pred, Func f )
659 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
662 template <typename Q, typename Less, typename Func>
663 bool find_with( Q const& key, Less pred, Func f )
666 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
671 /** \anchor cds_intrusive_MichaelList_rcu_find_val
672 The function searches the item with key equal to \p key
673 and returns \p true if \p val found or \p false otherwise.
675 template <typename Q>
676 bool find( Q const& key )
678 return find_at( m_pHead, key, key_comparator() );
681 /// Finds \p key using \p pred predicate for searching
683 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
684 but \p pred is used for key comparing.
685 \p Less functor has the interface like \p std::less.
686 \p pred must imply the same element order as the comparator used for building the list.
688 template <typename Q, typename Less>
689 bool find_with( Q const& key, Less pred )
692 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
695 /// Finds \p key and return the item found
696 /** \anchor cds_intrusive_MichaelList_rcu_get
697 The function searches the item with key equal to \p key and returns the pointer to item found.
698 If \p key is not found it returns \p nullptr.
700 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
702 RCU should be locked before call of this function.
703 Returned item is valid only while RCU is locked:
705 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
710 ord_list::rcu_lock lock;
712 foo * pVal = theList.get( 5 );
717 // Unlock RCU by rcu_lock destructor
718 // pVal can be retired by disposer at any time after RCU has been unlocked
722 template <typename Q>
723 value_type * get( Q const& key )
725 return get_at( m_pHead, key, key_comparator());
728 /// Finds \p key and return the item found
730 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
731 but \p pred is used for comparing the keys.
733 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
735 \p pred must imply the same element order as the comparator used for building the list.
737 template <typename Q, typename Less>
738 value_type * get_with( Q const& key, Less pred )
741 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
744 /// Clears the list using default disposer
746 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
748 RCU \p synchronize method can be called.
749 Note that depending on RCU type used the \ref disposer invocation can be deferred.
751 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
752 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
757 check_deadlock_policy::check();
759 marked_node_ptr pHead;
763 pHead = m_pHead.load(memory_model::memory_order_acquire);
766 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
767 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
769 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
774 dispose_node( pHead.ptr() );
779 /// Check if the list is empty
782 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
785 /// Returns list's item count
787 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
788 this function always returns 0.
790 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
791 is empty. To check list emptyness use \p empty() method.
795 return m_ItemCounter.value();
800 // split-list support
801 bool insert_aux_node( node_type * pNode )
803 return insert_aux_node( m_pHead, pNode );
806 // split-list support
807 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
809 assert( pNode != nullptr );
811 // Hack: convert node_type to value_type.
812 // In principle, auxiliary node can be non-reducible to value_type
813 // We assume that comparator can correctly distinguish between aux and regular node.
814 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
817 bool insert_at( atomic_node_ptr& refHead, value_type& val )
819 position pos( refHead );
822 return insert_at_locked( pos, val );
826 template <typename Func>
827 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
829 link_checker::is_empty( node_traits::to_node_ptr( val ) );
830 position pos( refHead );
835 if ( search( refHead, val, pos, key_comparator()))
838 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
845 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
851 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
854 if ( insert_at_locked( refHead, val ))
855 return iterator( node_traits::to_node_ptr( val ));
859 template <typename Func>
860 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
862 position pos( refHead );
865 return ensure_at_locked( pos, val, func );
869 template <typename Func>
870 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
872 position pos( refHead );
875 std::pair<iterator, bool> ret = ensure_at_locked( pos, val, func );
876 return std::make_pair( ret.first != end(), ret.second );
880 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
882 position pos( refHead );
884 check_deadlock_policy::check();
889 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
891 if ( !unlink_node( pos, erase_mask )) {
902 template <typename Q, typename Compare, typename Func>
903 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
906 check_deadlock_policy::check();
911 if ( !search( pos.refHead, val, pos, cmp ) )
913 if ( !unlink_node( pos, erase_mask )) {
919 f( *node_traits::to_value_ptr( *pos.pCur ) );
925 template <typename Q, typename Compare, typename Func>
926 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
928 position pos( refHead );
929 return erase_at( pos, val, cmp, f );
932 template <typename Q, typename Compare>
933 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
935 position pos( refHead );
936 return erase_at( pos, val, cmp, [](value_type const&){} );
939 template <typename Q, typename Compare >
940 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
942 position pos( refHead );
944 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
949 if ( !search( refHead, val, pos, cmp ) )
951 if ( !unlink_node( pos, extract_mask )) {
957 return node_traits::to_value_ptr( pos.pCur );
962 template <typename Q, typename Compare, typename Func>
963 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
965 position pos( refHead );
969 if ( search( refHead, val, pos, cmp ) ) {
970 assert( pos.pCur != nullptr );
971 f( *node_traits::to_value_ptr( *pos.pCur ), val );
978 template <typename Q, typename Compare>
979 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
981 position pos( refHead );
984 return find_at_locked( pos, val, cmp ) != cend();
988 template <typename Q, typename Compare>
989 value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
991 value_type * pFound = nullptr;
992 return find_at( refHead, val, cmp,
993 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1001 template <typename Q, typename Compare>
1002 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1004 // RCU lock should be locked!!!
1005 assert( gc::is_locked() );
1007 atomic_node_ptr * pPrev;
1008 marked_node_ptr pNext;
1009 marked_node_ptr pCur;
1015 pCur = pPrev->load(memory_model::memory_order_acquire);
1019 if ( !pCur.ptr() ) {
1022 pos.pNext = nullptr;
1026 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1028 if ( pPrev->load(memory_model::memory_order_relaxed) != pCur
1029 || pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed))
1035 if ( pNext.bits() ) {
1036 // pCur is marked as deleted. Try to unlink it from the list
1037 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1038 if ( pNext.bits() == erase_mask )
1039 link_to_remove_chain( pos, pCur.ptr() );
1045 assert( pCur.ptr() != nullptr );
1046 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1049 pos.pCur = pCur.ptr();
1050 pos.pNext = pNext.ptr();
1053 pPrev = &( pCur->m_pNext );
1061 bool insert_at_locked( position& pos, value_type& val )
1063 // RCU lock should be locked!!!
1064 assert( gc::is_locked() );
1065 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1068 if ( search( pos.refHead, val, pos, key_comparator() ) )
1071 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1077 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1081 template <typename Func>
1082 std::pair<iterator, bool> ensure_at_locked( position& pos, value_type& val, Func func )
1084 // RCU lock should be locked!!!
1085 assert( gc::is_locked() );
1088 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1089 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1091 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1092 return std::make_pair( iterator( pos.pCur ), false );
1095 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1097 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1099 func( true, val , val );
1100 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1103 // clear the next field
1104 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1109 template <typename Q, typename Compare>
1110 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1112 assert( gc::is_locked() );
1114 if ( search( pos.refHead, val, pos, cmp ) ) {
1115 assert( pos.pCur != nullptr );
1116 return const_iterator( pos.pCur );
1123 }} // namespace cds::intrusive
1125 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H