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>
11 #include <cds/urcu/raw_ptr.h>
12 #include <cds/intrusive/details/raw_ptr_disposer.h>
14 namespace cds { namespace intrusive {
17 namespace michael_list {
19 /// Node specialization for uRCU
20 template <class RCU, typename Tag>
21 struct node< cds::urcu::gc< RCU >, Tag >
23 typedef cds::urcu::gc< RCU > gc; ///< Garbage collector
24 typedef Tag tag; ///< tag
26 typedef cds::details::marked_ptr<node, 3> marked_ptr; ///< marked pointer
27 typedef typename gc::template atomic_marked_ptr<marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
29 atomic_marked_ptr m_pNext; ///< pointer to the next node in the container
30 node * m_pDelChain; ///< Deleted node chain (local for a thread)
32 CDS_CONSTEXPR node() CDS_NOEXCEPT
34 , m_pDelChain( nullptr )
37 } // namespace michael_list
40 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
41 /** @ingroup cds_intrusive_list
42 \anchor cds_intrusive_MichaelList_rcu
44 Usually, ordered single-linked list is used as a building block for the hash table implementation.
45 The complexity of searching is <tt>O(N)</tt>.
48 - \p RCU - one of \ref cds_urcu_gc "RCU type"
49 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
50 cds::intrusive::micheal_list::node
51 - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
52 list with \p cds::intrusive::michael_list::make_traits metafunction,
53 see \ref cds_intrusive_MichaelList_hp "here" for explanations.
56 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
57 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
58 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
60 #include <cds/urcu/general_buffered.h>
61 #include <cds/intrusive/michael_list_rcu.h>
63 // Now, you can declare Michael's list for type Foo and default traits:
64 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
67 template < typename RCU, typename T,
68 #ifdef CDS_DOXYGEN_INVOKED
69 class Traits = michael_list::traits
74 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
77 typedef T value_type; ///< type of value stored in the list
78 typedef Traits traits; ///< Traits template parameter
80 typedef typename traits::hook hook; ///< hook type
81 typedef typename hook::node_type node_type; ///< node type
83 # ifdef CDS_DOXYGEN_INVOKED
84 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
86 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
89 typedef typename traits::disposer disposer; ///< disposer used
90 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
91 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
93 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
94 typedef typename traits::back_off back_off; ///< back-off strategy
95 typedef typename traits::item_counter item_counter; ///< Item counting policy used
96 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
97 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
99 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
100 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
103 // Rebind traits (split-list support)
104 template <typename... Options>
105 struct rebind_traits {
109 , typename cds::opt::make_options< traits, Options...>::type
115 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
116 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
117 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
119 atomic_node_ptr m_pHead ; ///< Head pointer
120 item_counter m_ItemCounter ; ///< Item counter
130 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
132 static void clear_links( node_type * pNode )
134 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release );
135 pNode->m_pDelChain = nullptr;
138 struct clear_and_dispose {
139 void operator()( value_type * p )
141 assert( p != nullptr );
142 clear_links( node_traits::to_node_ptr(p));
147 static void dispose_node( node_type * pNode )
150 assert( !gc::is_locked() );
152 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
155 static void dispose_chain( node_type * pChain )
158 assert( !gc::is_locked() );
160 auto f = [&pChain]() -> cds::urcu::retired_ptr {
161 node_type * p = pChain;
163 pChain = p->m_pDelChain;
164 return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
166 return cds::urcu::make_retired_ptr<clear_and_dispose>( static_cast<value_type *>(nullptr));
168 gc::batch_retire(std::ref(f));
172 /// Position pointer for item search
174 atomic_node_ptr * pPrev ; ///< Previous node
175 node_type * pCur ; ///< Current node
176 node_type * pNext ; ///< Next node
178 atomic_node_ptr& refHead;
179 node_type * pDelChain; ///< Head of deleted node chain
181 position( atomic_node_ptr& head )
183 , pDelChain( nullptr )
188 dispose_chain( pDelChain );
195 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
199 struct chain_disposer {
200 void operator()( node_type * pChain ) const
202 dispose_chain( pChain );
205 typedef cds::intrusive::details::raw_ptr_disposer< gc, node_type, chain_disposer> raw_ptr_disposer;
209 /// Result of \p get(), \p get_with() functions - pointer to the node found
210 typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr;
215 bool link_node( node_type * pNode, position& pos )
217 assert( pNode != nullptr );
218 link_checker::is_empty( pNode );
220 marked_node_ptr p( pos.pCur );
221 pNode->m_pNext.store( p, memory_model::memory_order_release );
222 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
225 static void link_to_remove_chain( position& pos, node_type * pDel )
227 assert( pDel->m_pDelChain == nullptr );
229 pDel->m_pDelChain = pos.pDelChain;
230 pos.pDelChain = pDel;
233 bool unlink_node( position& pos, erase_node_mask nMask )
235 // Mark the node (logical deletion)
236 marked_node_ptr next(pos.pNext, 0);
238 if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )) {
240 // Try physical removal - fast path
241 marked_node_ptr cur(pos.pCur);
242 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
243 if ( nMask == erase_mask )
244 link_to_remove_chain( pos, pos.pCur );
248 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
258 template <bool IsConst>
261 friend class MichaelList;
262 value_type * m_pNode;
267 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
268 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
273 explicit iterator_type( node_type * pNode)
276 m_pNode = node_traits::to_value_ptr( *pNode );
280 explicit iterator_type( atomic_node_ptr const& refNode)
282 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
283 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
287 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
288 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
294 iterator_type( const iterator_type& src )
295 : m_pNode( src.m_pNode )
298 value_ptr operator ->() const
303 value_ref operator *() const
305 assert( m_pNode != nullptr );
310 iterator_type& operator ++()
317 iterator_type operator ++(int)
319 iterator_type i(*this);
324 iterator_type& operator = (const iterator_type& src)
326 m_pNode = src.m_pNode;
331 bool operator ==(iterator_type<C> const& i ) const
333 return m_pNode == i.m_pNode;
336 bool operator !=(iterator_type<C> const& i ) const
338 return m_pNode != i.m_pNode;
345 typedef iterator_type<false> iterator;
346 /// Const forward iterator
347 typedef iterator_type<true> const_iterator;
349 /// Returns a forward iterator addressing the first element in a list
351 For empty list \code begin() == end() \endcode
355 return iterator( m_pHead );
358 /// Returns an iterator that addresses the location succeeding the last element in a list
360 Do not use the value returned by <tt>end</tt> function to access any item.
361 Internally, <tt>end</tt> returning value equals to \p nullptr.
363 The returned value can be used only to control reaching the end of the list.
364 For empty list \code begin() == end() \endcode
371 /// Returns a forward const iterator addressing the first element in a list
372 const_iterator begin() const
374 return const_iterator(m_pHead );
376 /// Returns a forward const iterator addressing the first element in a list
377 const_iterator cbegin() const
379 return const_iterator(m_pHead );
382 /// Returns an const iterator that addresses the location succeeding the last element in a list
383 const_iterator end() const
385 return const_iterator();
387 /// Returns an const iterator that addresses the location succeeding the last element in a list
388 const_iterator cend() const
390 return const_iterator();
394 /// Default constructor initializes empty list
398 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
409 The function inserts \p val in the list if the list does not contain
410 an item with key equal to \p val.
412 The function makes RCU lock internally.
414 Returns \p true if \p val is linked into the list, \p false otherwise.
416 bool insert( value_type& val )
418 return insert_at( m_pHead, val );
423 This function is intended for derived non-intrusive containers.
425 The function allows to split new item creating into two part:
426 - create item with key only
427 - insert new item into the list
428 - if inserting is success, calls \p f functor to initialize value-field of \p val.
430 The functor signature is:
432 void func( value_type& val );
434 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
435 \p val no any other changes could be made on this list's item by concurrent threads.
436 The user-defined functor is called only if the inserting is success.
438 The function makes RCU lock internally.
440 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
442 template <typename Func>
443 bool insert( value_type& val, Func f )
445 return insert_at( m_pHead, val, f );
448 /// Ensures that the \p item exists in the list
450 The operation performs inserting or changing data with lock-free manner.
452 If the item \p val not found in the list, then \p val is inserted into the list.
453 Otherwise, the functor \p func is called with item found.
454 The functor signature is:
457 void operator()( bool bNew, value_type& item, value_type& val );
461 - \p bNew - \p true if the item has been inserted, \p false otherwise
462 - \p item - item of the list
463 - \p val - argument \p val passed into the \p ensure function
464 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
465 refer to the same thing.
467 The functor may change non-key fields of the \p item; however, \p func must guarantee
468 that during changing no any other modifications could be made on this item by concurrent threads.
470 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
471 \p second is true if new item has been added or \p false if the item with \p key
472 already is in the list.
474 The function makes RCU lock internally.
476 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
478 template <typename Func>
479 std::pair<bool, bool> ensure( value_type& val, Func func )
481 return ensure_at( m_pHead, val, func );
484 /// Unlinks the item \p val from the list
486 The function searches the item \p val in the list and unlink it from the list
487 if it is found and it is equal to \p val.
489 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
490 and deletes the item found. \p unlink finds an item by key and deletes it
491 only if \p val is an item of that list, i.e. the pointer to the item found
492 is equal to <tt> &val </tt>.
494 The function returns \p true if success and \p false otherwise.
496 RCU \p synchronize method can be called.
497 Note that depending on RCU type used the \ref disposer call can be deferred.
499 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
500 deadlock checking policy is opt::v::rcu_throw_deadlock.
502 bool unlink( value_type& val )
504 return unlink_at( m_pHead, val );
507 /// Deletes the item from the list
508 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
509 The function searches an item with key equal to \p key in the list,
510 unlinks it from the list, and returns \p true.
511 If the item with the key equal to \p key is not found the function return \p false.
513 RCU \p synchronize method can be called.
514 Note that depending on RCU type used the \ref disposer call can be deferred.
516 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
517 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
519 template <typename Q>
520 bool erase( Q const& key )
522 return erase_at( m_pHead, key, key_comparator() );
525 /// Deletes the item from the list using \p pred predicate for searching
527 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
528 but \p pred is used for key comparing.
529 \p Less functor has the interface like \p std::less.
530 \p pred must imply the same element order as the comparator used for building the list.
532 template <typename Q, typename Less>
533 bool erase_with( Q const& key, Less pred )
536 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
539 /// Deletes the item from the list
540 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
541 The function searches an item with key equal to \p key in the list,
542 call \p func functor with item found, unlinks it from the list, and returns \p true.
543 The \p Func interface is
546 void operator()( value_type const& item );
550 If the item with the key equal to \p key is not found the function return \p false.
552 RCU \p synchronize method can be called.
553 Note that depending on RCU type used the \ref disposer call can be deferred.
555 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
556 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
558 template <typename Q, typename Func>
559 bool erase( Q const& key, Func func )
561 return erase_at( m_pHead, key, key_comparator(), func );
564 /// Deletes the item from the list using \p pred predicate for searching
566 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
567 but \p pred is used for key comparing.
568 \p Less functor has the interface like \p std::less.
569 \p pred must imply the same element order as the comparator used for building the list.
571 template <typename Q, typename Less, typename Func>
572 bool erase_with( Q const& key, Less pred, Func func )
575 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
578 /// Extracts an item from the list
580 @anchor cds_intrusive_MichaelList_rcu_extract
581 The function searches an item with key equal to \p key in the list,
582 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
583 If \p key is not found the function returns an empty \p exempt_ptr.
585 @note The function does NOT dispose the item found. It just unlinks the item from the list
586 and returns a pointer to item found.
587 You shouldn't lock RCU for current thread before calling this function, and you should manually release
588 \p dest exempt pointer outside the RCU lock before reusing it.
591 #include <cds/urcu/general_buffered.h>
592 #include <cds/intrusive/michael_list_rcu.h>
594 typedef cds::urcu::gc< general_buffered<> > rcu;
595 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
597 rcu_michael_list theList;
600 rcu_michael_list::exempt_ptr p1;
602 // The RCU should NOT be locked when extract() is called!
603 assert( !rcu::is_locked() );
605 // You can call extract() function
606 p1 = theList.extract( 10 );
608 // do something with p1
612 // We may safely release p1 here
613 // release() passes the pointer to RCU reclamation cycle:
614 // it invokes RCU retire_ptr function with the disposer you provided for the list.
618 template <typename Q>
619 exempt_ptr extract( Q const& key )
621 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
624 /// Extracts an item from the list using \p pred predicate for searching
626 This function is the analog for \p extract(Q const&)
628 The \p pred is a predicate used for key comparing.
629 \p Less has the interface like \p std::less.
630 \p pred must imply the same element order as \ref key_comparator.
632 template <typename Q, typename Less>
633 exempt_ptr extract_with( Q const& key, Less pred )
636 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
639 /// Find the key \p val
640 /** \anchor cds_intrusive_MichaelList_rcu_find_func
641 The function searches the item with key equal to \p key
642 and calls the functor \p f for item found.
643 The interface of \p Func functor is:
646 void operator()( value_type& item, Q& key );
649 where \p item is the item found, \p key is the <tt>find</tt> function argument.
651 The functor can change non-key fields of \p item.
652 The function \p find does not serialize simultaneous access to the list \p item. If such access is
653 possible you must provide your own synchronization schema to exclude unsafe item modifications.
655 The function makes RCU lock internally.
657 The function returns \p true if \p val is found, \p false otherwise.
659 template <typename Q, typename Func>
660 bool find( Q& key, Func f )
662 return find_at( m_pHead, key, key_comparator(), f );
665 template <typename Q, typename Func>
666 bool find( Q const& key, Func f )
668 return find_at( m_pHead, key, key_comparator(), f );
672 /// Finds \p key using \p pred predicate for searching
674 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
675 but \p pred is used for key comparing.
676 \p Less functor has the interface like \p std::less.
677 \p pred must imply the same element order as the comparator used for building the list.
679 template <typename Q, typename Less, typename Func>
680 bool find_with( Q& key, Less pred, Func f )
683 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
686 template <typename Q, typename Less, typename Func>
687 bool find_with( Q const& key, Less pred, Func f )
690 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
695 /** \anchor cds_intrusive_MichaelList_rcu_find_val
696 The function searches the item with key equal to \p key
697 and returns \p true if \p val found or \p false otherwise.
699 template <typename Q>
700 bool find( Q const& key )
702 return find_at( m_pHead, key, key_comparator() );
705 /// Finds \p key using \p pred predicate for searching
707 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
708 but \p pred is used for key comparing.
709 \p Less functor has the interface like \p std::less.
710 \p pred must imply the same element order as the comparator used for building the list.
712 template <typename Q, typename Less>
713 bool find_with( Q const& key, Less pred )
716 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
719 /// Finds \p key and return the item found
720 /** \anchor cds_intrusive_MichaelList_rcu_get
721 The function searches the item with key equal to \p key and returns the pointer to item found.
722 If \p key is not found it returns empty \p raw_ptr object.
724 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
726 RCU should be locked before call of this function.
727 Returned item is valid only while RCU is locked:
729 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
732 typename ord_list::raw_ptr rp;
735 ord_list::rcu_lock lock;
737 rp = theList.get( 5 );
742 // Unlock RCU by rcu_lock destructor
743 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
745 // You can manually release rp after RCU-locked section
749 template <typename Q>
750 raw_ptr get( Q const& key )
752 return get_at( m_pHead, key, key_comparator());
755 /// Finds \p key and return the item found
757 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
758 but \p pred is used for comparing the keys.
760 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
762 \p pred must imply the same element order as the comparator used for building the list.
764 template <typename Q, typename Less>
765 raw_ptr get_with( Q const& key, Less pred )
768 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
771 /// Clears the list using default disposer
773 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
775 RCU \p synchronize method can be called.
776 Note that depending on RCU type used the \ref disposer invocation can be deferred.
778 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
779 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
784 check_deadlock_policy::check();
786 marked_node_ptr pHead;
790 pHead = m_pHead.load(memory_model::memory_order_acquire);
793 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
794 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
796 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
801 dispose_node( pHead.ptr() );
806 /// Check if the list is empty
809 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
812 /// Returns list's item count
814 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
815 this function always returns 0.
817 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
818 is empty. To check list emptyness use \p empty() method.
822 return m_ItemCounter.value();
827 // split-list support
828 bool insert_aux_node( node_type * pNode )
830 return insert_aux_node( m_pHead, pNode );
833 // split-list support
834 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
836 assert( pNode != nullptr );
838 // Hack: convert node_type to value_type.
839 // In principle, auxiliary node can be non-reducible to value_type
840 // We assume that comparator can correctly distinguish between aux and regular node.
841 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
844 bool insert_at( atomic_node_ptr& refHead, value_type& val )
846 position pos( refHead );
849 return insert_at_locked( pos, val );
853 template <typename Func>
854 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
856 link_checker::is_empty( node_traits::to_node_ptr( val ) );
857 position pos( refHead );
862 if ( search( refHead, val, pos, key_comparator()))
865 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
872 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
878 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
881 if ( insert_at_locked( refHead, val ))
882 return iterator( node_traits::to_node_ptr( val ));
886 template <typename Func>
887 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
889 position pos( refHead );
892 return ensure_at_locked( pos, val, func );
896 template <typename Func>
897 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
899 position pos( refHead );
902 std::pair<iterator, bool> ret = ensure_at_locked( pos, val, func );
903 return std::make_pair( ret.first != end(), ret.second );
907 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
909 position pos( refHead );
911 check_deadlock_policy::check();
916 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
918 if ( !unlink_node( pos, erase_mask )) {
929 template <typename Q, typename Compare, typename Func>
930 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
933 check_deadlock_policy::check();
938 if ( !search( pos.refHead, val, pos, cmp ) )
940 if ( !unlink_node( pos, erase_mask )) {
946 f( *node_traits::to_value_ptr( *pos.pCur ) );
952 template <typename Q, typename Compare, typename Func>
953 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
955 position pos( refHead );
956 return erase_at( pos, val, cmp, f );
959 template <typename Q, typename Compare>
960 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
962 position pos( refHead );
963 return erase_at( pos, val, cmp, [](value_type const&){} );
966 template <typename Q, typename Compare >
967 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
969 position pos( refHead );
971 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
976 if ( !search( refHead, val, pos, cmp ) )
978 if ( !unlink_node( pos, extract_mask )) {
984 return node_traits::to_value_ptr( pos.pCur );
989 template <typename Q, typename Compare, typename Func>
990 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
992 position pos( refHead );
996 if ( search( refHead, val, pos, cmp ) ) {
997 assert( pos.pCur != nullptr );
998 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1005 template <typename Q, typename Compare>
1006 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1008 position pos( refHead );
1011 return find_at_locked( pos, val, cmp ) != cend();
1015 template <typename Q, typename Compare>
1016 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1018 // RCU should be locked!
1019 assert(gc::is_locked() );
1021 position pos( refHead );
1023 if ( search( refHead, val, pos, cmp ))
1024 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1025 return raw_ptr( raw_ptr_disposer( pos ));
1032 template <typename Q, typename Compare>
1033 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1035 // RCU lock should be locked!!!
1036 assert( gc::is_locked() );
1038 atomic_node_ptr * pPrev;
1039 marked_node_ptr pNext;
1040 marked_node_ptr pCur;
1046 pCur = pPrev->load(memory_model::memory_order_acquire);
1050 if ( !pCur.ptr() ) {
1053 pos.pNext = nullptr;
1057 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1059 if ( pPrev->load(memory_model::memory_order_relaxed) != pCur
1060 || pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed))
1066 if ( pNext.bits() ) {
1067 // pCur is marked as deleted. Try to unlink it from the list
1068 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1069 if ( pNext.bits() == erase_mask )
1070 link_to_remove_chain( pos, pCur.ptr() );
1076 assert( pCur.ptr() != nullptr );
1077 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1080 pos.pCur = pCur.ptr();
1081 pos.pNext = pNext.ptr();
1084 pPrev = &( pCur->m_pNext );
1092 bool insert_at_locked( position& pos, value_type& val )
1094 // RCU lock should be locked!!!
1095 assert( gc::is_locked() );
1096 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1099 if ( search( pos.refHead, val, pos, key_comparator() ) )
1102 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1108 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1112 template <typename Func>
1113 std::pair<iterator, bool> ensure_at_locked( position& pos, value_type& val, Func func )
1115 // RCU lock should be locked!!!
1116 assert( gc::is_locked() );
1119 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1120 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1122 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1123 return std::make_pair( iterator( pos.pCur ), false );
1126 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1128 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1130 func( true, val , val );
1131 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1134 // clear the next field
1135 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1140 template <typename Q, typename Compare>
1141 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1143 assert( gc::is_locked() );
1145 if ( search( pos.refHead, val, pos, cmp ) ) {
1146 assert( pos.pCur != nullptr );
1147 return const_iterator( pos.pCur );
1154 }} // namespace cds::intrusive
1156 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H