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>
13 namespace cds { namespace intrusive {
16 namespace michael_list {
18 /// Node specialization for uRCU
19 template <class RCU, typename Tag>
20 struct node< cds::urcu::gc< RCU >, Tag >
22 typedef cds::urcu::gc< RCU > gc; ///< Garbage collector
23 typedef Tag tag; ///< tag
25 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
26 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
28 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
29 node * m_pDelChain; ///< Deleted node chain (local for a thread)
31 CDS_CONSTEXPR node() CDS_NOEXCEPT
33 , m_pDelChain( nullptr )
36 } // namespace michael_list
39 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
40 /** @ingroup cds_intrusive_list
41 \anchor cds_intrusive_MichaelList_rcu
43 Usually, ordered single-linked list is used as a building block for the hash table implementation.
44 The complexity of searching is <tt>O(N)</tt>.
47 - \p RCU - one of \ref cds_urcu_gc "RCU type"
48 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
49 cds::intrusive::micheal_list::node
50 - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
51 list with \p cds::intrusive::michael_list::make_traits metafunction,
52 see \ref cds_intrusive_MichaelList_hp "here" for explanations.
55 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
56 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
57 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
59 #include <cds/urcu/general_buffered.h>
60 #include <cds/intrusive/michael_list_rcu.h>
62 // Now, you can declare Michael's list for type Foo and default traits:
63 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
66 template < typename RCU, typename T,
67 #ifdef CDS_DOXYGEN_INVOKED
68 class Traits = michael_list::traits
73 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
76 typedef T value_type; ///< type of value stored in the list
77 typedef Traits traits; ///< Traits template parameter
79 typedef typename traits::hook hook; ///< hook type
80 typedef typename hook::node_type node_type; ///< node type
82 # ifdef CDS_DOXYGEN_INVOKED
83 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
85 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
88 typedef typename traits::disposer disposer; ///< disposer used
89 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
90 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
92 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
93 typedef typename traits::back_off back_off; ///< back-off strategy
94 typedef typename traits::item_counter item_counter; ///< Item counting policy used
95 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
96 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
98 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
99 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
102 // Rebind traits (split-list support)
103 template <typename... Options>
104 struct rebind_traits {
108 , typename cds::opt::make_options< traits, Options...>::type
114 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
115 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
116 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
118 atomic_node_ptr m_pHead ; ///< Head pointer
119 item_counter m_ItemCounter ; ///< Item counter
129 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
131 static void clear_links( node_type * pNode )
133 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
134 pNode->m_pDelChain = nullptr;
137 struct clear_and_dispose {
138 void operator()( value_type * p )
140 assert( p != nullptr );
141 clear_links( node_traits::to_node_ptr(p));
146 static void dispose_node( node_type * pNode )
149 assert( !gc::is_locked() );
151 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
154 static void dispose_chain( node_type * pChain )
157 assert( !gc::is_locked() );
159 auto f = [&pChain]() -> cds::urcu::retired_ptr {
160 node_type * p = pChain;
161 pChain = p->m_pDelChain;
162 return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
164 gc::batch_retire(std::ref(f));
168 /// Position pointer for item search
170 atomic_node_ptr * pPrev ; ///< Previous node
171 node_type * pCur ; ///< Current node
172 node_type * pNext ; ///< Next node
174 atomic_node_ptr& refHead;
175 node_type * pDelChain; ///< Head of deleted node chain
177 position( atomic_node_ptr& head )
179 , pDelChain( nullptr )
184 dispose_chain( pDelChain );
191 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
195 struct raw_ptr_disposer
197 node_type * pReclaimedChain;
200 : pReclaimedChain( nullptr )
203 raw_ptr_disposer( position& pos )
204 : pReclaimedChain( pos.pDelChain )
206 pos.pDelChain = nullptr;
209 raw_ptr_disposer( raw_ptr_disposer&& d )
210 : pReclaimedChain( d.pReclaimedChain )
212 d.pReclaimedChain = nullptr;
215 raw_ptr_disposer( raw_ptr_disposer const& ) = delete;
224 if ( pReclaimedChain ) {
225 dispose_chain( pReclaimedChain );
226 pReclaimedChain = nullptr;
233 /// Result of \p get(), \p get_with() functions - pointer to the node found
234 typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr;
239 bool link_node( node_type * pNode, position& pos )
241 assert( pNode != nullptr );
242 link_checker::is_empty( pNode );
244 marked_node_ptr p( pos.pCur );
245 pNode->m_pNext.store( p, memory_model::memory_order_release );
246 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
249 static void link_to_remove_chain( position& pos, node_type * pDel )
251 assert( pDel->m_pDelChain == nullptr );
253 pDel->m_pDelChain = pos.pDelChain;
254 pos.pDelChain = pDel;
257 bool unlink_node( position& pos, erase_node_mask nMask )
259 // Mark the node (logical deletion)
260 marked_node_ptr next(pos.pNext, 0);
262 if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )) {
264 // Try physical removal - fast path
265 marked_node_ptr cur(pos.pCur);
266 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
267 if ( nMask == erase_mask )
268 link_to_remove_chain( pos, pos.pCur );
272 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
282 template <bool IsConst>
285 friend class MichaelList;
286 value_type * m_pNode;
291 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
292 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
297 explicit iterator_type( node_type * pNode)
300 m_pNode = node_traits::to_value_ptr( *pNode );
304 explicit iterator_type( atomic_node_ptr const& refNode)
306 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
307 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
311 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
312 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
318 iterator_type( const iterator_type& src )
319 : m_pNode( src.m_pNode )
322 value_ptr operator ->() const
327 value_ref operator *() const
329 assert( m_pNode != nullptr );
334 iterator_type& operator ++()
341 iterator_type operator ++(int)
343 iterator_type i(*this);
348 iterator_type& operator = (const iterator_type& src)
350 m_pNode = src.m_pNode;
355 bool operator ==(iterator_type<C> const& i ) const
357 return m_pNode == i.m_pNode;
360 bool operator !=(iterator_type<C> const& i ) const
362 return m_pNode != i.m_pNode;
369 typedef iterator_type<false> iterator;
370 /// Const forward iterator
371 typedef iterator_type<true> const_iterator;
373 /// Returns a forward iterator addressing the first element in a list
375 For empty list \code begin() == end() \endcode
379 return iterator( m_pHead );
382 /// Returns an iterator that addresses the location succeeding the last element in a list
384 Do not use the value returned by <tt>end</tt> function to access any item.
385 Internally, <tt>end</tt> returning value equals to \p nullptr.
387 The returned value can be used only to control reaching the end of the list.
388 For empty list \code begin() == end() \endcode
395 /// Returns a forward const iterator addressing the first element in a list
396 const_iterator begin() const
398 return const_iterator(m_pHead );
400 /// Returns a forward const iterator addressing the first element in a list
401 const_iterator cbegin() const
403 return const_iterator(m_pHead );
406 /// Returns an const iterator that addresses the location succeeding the last element in a list
407 const_iterator end() const
409 return const_iterator();
411 /// Returns an const iterator that addresses the location succeeding the last element in a list
412 const_iterator cend() const
414 return const_iterator();
418 /// Default constructor initializes empty list
422 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
433 The function inserts \p val in the list if the list does not contain
434 an item with key equal to \p val.
436 The function makes RCU lock internally.
438 Returns \p true if \p val is linked into the list, \p false otherwise.
440 bool insert( value_type& val )
442 return insert_at( m_pHead, val );
447 This function is intended for derived non-intrusive containers.
449 The function allows to split new item creating into two part:
450 - create item with key only
451 - insert new item into the list
452 - if inserting is success, calls \p f functor to initialize value-field of \p val.
454 The functor signature is:
456 void func( value_type& val );
458 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
459 \p val no any other changes could be made on this list's item by concurrent threads.
460 The user-defined functor is called only if the inserting is success.
462 The function makes RCU lock internally.
464 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
466 template <typename Func>
467 bool insert( value_type& val, Func f )
469 return insert_at( m_pHead, val, f );
472 /// Ensures that the \p item exists in the list
474 The operation performs inserting or changing data with lock-free manner.
476 If the item \p val not found in the list, then \p val is inserted into the list.
477 Otherwise, the functor \p func is called with item found.
478 The functor signature is:
481 void operator()( bool bNew, value_type& item, value_type& val );
485 - \p bNew - \p true if the item has been inserted, \p false otherwise
486 - \p item - item of the list
487 - \p val - argument \p val passed into the \p ensure function
488 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
489 refer to the same thing.
491 The functor may change non-key fields of the \p item; however, \p func must guarantee
492 that during changing no any other modifications could be made on this item by concurrent threads.
494 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
495 \p second is true if new item has been added or \p false if the item with \p key
496 already is in the list.
498 The function makes RCU lock internally.
500 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
502 template <typename Func>
503 std::pair<bool, bool> ensure( value_type& val, Func func )
505 return ensure_at( m_pHead, val, func );
508 /// Unlinks the item \p val from the list
510 The function searches the item \p val in the list and unlink it from the list
511 if it is found and it is equal to \p val.
513 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
514 and deletes the item found. \p unlink finds an item by key and deletes it
515 only if \p val is an item of that list, i.e. the pointer to the item found
516 is equal to <tt> &val </tt>.
518 The function returns \p true if success and \p false otherwise.
520 RCU \p synchronize method can be called.
521 Note that depending on RCU type used the \ref disposer call can be deferred.
523 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
524 deadlock checking policy is opt::v::rcu_throw_deadlock.
526 bool unlink( value_type& val )
528 return unlink_at( m_pHead, val );
531 /// Deletes the item from the list
532 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
533 The function searches an item with key equal to \p key in the list,
534 unlinks it from the list, and returns \p true.
535 If the item with the key equal to \p key is not found the function return \p false.
537 RCU \p synchronize method can be called.
538 Note that depending on RCU type used the \ref disposer call can be deferred.
540 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
541 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
543 template <typename Q>
544 bool erase( Q const& key )
546 return erase_at( m_pHead, key, key_comparator() );
549 /// Deletes the item from the list using \p pred predicate for searching
551 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
552 but \p pred is used for key comparing.
553 \p Less functor has the interface like \p std::less.
554 \p pred must imply the same element order as the comparator used for building the list.
556 template <typename Q, typename Less>
557 bool erase_with( Q const& key, Less pred )
560 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
563 /// Deletes the item from the list
564 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
565 The function searches an item with key equal to \p key in the list,
566 call \p func functor with item found, unlinks it from the list, and returns \p true.
567 The \p Func interface is
570 void operator()( value_type const& item );
574 If the item with the key equal to \p key is not found the function return \p false.
576 RCU \p synchronize method can be called.
577 Note that depending on RCU type used the \ref disposer call can be deferred.
579 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
580 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
582 template <typename Q, typename Func>
583 bool erase( Q const& key, Func func )
585 return erase_at( m_pHead, key, key_comparator(), func );
588 /// Deletes the item from the list using \p pred predicate for searching
590 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
591 but \p pred is used for key comparing.
592 \p Less functor has the interface like \p std::less.
593 \p pred must imply the same element order as the comparator used for building the list.
595 template <typename Q, typename Less, typename Func>
596 bool erase_with( Q const& key, Less pred, Func func )
599 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
602 /// Extracts an item from the list
604 @anchor cds_intrusive_MichaelList_rcu_extract
605 The function searches an item with key equal to \p key in the list,
606 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
607 If \p key is not found the function returns an empty \p exempt_ptr.
609 @note The function does NOT dispose the item found. It just unlinks the item from the list
610 and returns a pointer to item found.
611 You shouldn't lock RCU for current thread before calling this function, and you should manually release
612 \p dest exempt pointer outside the RCU lock before reusing it.
615 #include <cds/urcu/general_buffered.h>
616 #include <cds/intrusive/michael_list_rcu.h>
618 typedef cds::urcu::gc< general_buffered<> > rcu;
619 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
621 rcu_michael_list theList;
624 rcu_michael_list::exempt_ptr p1;
626 // The RCU should NOT be locked when extract() is called!
627 assert( !rcu::is_locked() );
629 // You can call extract() function
630 p1 = theList.extract( 10 );
632 // do something with p1
636 // We may safely release p1 here
637 // release() passes the pointer to RCU reclamation cycle:
638 // it invokes RCU retire_ptr function with the disposer you provided for the list.
642 template <typename Q>
643 exempt_ptr extract( Q const& key )
645 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
648 /// Extracts an item from the list using \p pred predicate for searching
650 This function is the analog for \p extract(Q const&)
652 The \p pred is a predicate used for key comparing.
653 \p Less has the interface like \p std::less.
654 \p pred must imply the same element order as \ref key_comparator.
656 template <typename Q, typename Less>
657 exempt_ptr extract_with( Q const& key, Less pred )
660 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
663 /// Find the key \p val
664 /** \anchor cds_intrusive_MichaelList_rcu_find_func
665 The function searches the item with key equal to \p key
666 and calls the functor \p f for item found.
667 The interface of \p Func functor is:
670 void operator()( value_type& item, Q& key );
673 where \p item is the item found, \p key is the <tt>find</tt> function argument.
675 The functor can change non-key fields of \p item.
676 The function \p find does not serialize simultaneous access to the list \p item. If such access is
677 possible you must provide your own synchronization schema to exclude unsafe item modifications.
679 The function makes RCU lock internally.
681 The function returns \p true if \p val is found, \p false otherwise.
683 template <typename Q, typename Func>
684 bool find( Q& key, Func f )
686 return find_at( m_pHead, key, key_comparator(), f );
689 template <typename Q, typename Func>
690 bool find( Q const& key, Func f )
692 return find_at( m_pHead, key, key_comparator(), f );
696 /// Finds \p key using \p pred predicate for searching
698 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
699 but \p pred is used for key comparing.
700 \p Less functor has the interface like \p std::less.
701 \p pred must imply the same element order as the comparator used for building the list.
703 template <typename Q, typename Less, typename Func>
704 bool find_with( Q& key, Less pred, Func f )
707 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
710 template <typename Q, typename Less, typename Func>
711 bool find_with( Q const& key, Less pred, Func f )
714 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
719 /** \anchor cds_intrusive_MichaelList_rcu_find_val
720 The function searches the item with key equal to \p key
721 and returns \p true if \p val found or \p false otherwise.
723 template <typename Q>
724 bool find( Q const& key )
726 return find_at( m_pHead, key, key_comparator() );
729 /// Finds \p key using \p pred predicate for searching
731 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
732 but \p pred is used for key comparing.
733 \p Less functor has the interface like \p std::less.
734 \p pred must imply the same element order as the comparator used for building the list.
736 template <typename Q, typename Less>
737 bool find_with( Q const& key, Less pred )
740 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
743 /// Finds \p key and return the item found
744 /** \anchor cds_intrusive_MichaelList_rcu_get
745 The function searches the item with key equal to \p key and returns the pointer to item found.
746 If \p key is not found it returns empty \p raw_ptr object.
748 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
750 RCU should be locked before call of this function.
751 Returned item is valid only while RCU is locked:
753 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
756 typename ord_list::raw_ptr rp;
759 ord_list::rcu_lock lock;
761 rp = theList.get( 5 );
766 // Unlock RCU by rcu_lock destructor
767 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
769 // You can manually release rp after RCU-locked section
773 template <typename Q>
774 raw_ptr get( Q const& key )
776 return get_at( m_pHead, key, key_comparator());
779 /// Finds \p key and return the item found
781 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
782 but \p pred is used for comparing the keys.
784 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
786 \p pred must imply the same element order as the comparator used for building the list.
788 template <typename Q, typename Less>
789 raw_ptr get_with( Q const& key, Less pred )
792 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
795 /// Clears the list using default disposer
797 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
799 RCU \p synchronize method can be called.
800 Note that depending on RCU type used the \ref disposer invocation can be deferred.
802 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
803 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
808 check_deadlock_policy::check();
810 marked_node_ptr pHead;
814 pHead = m_pHead.load(memory_model::memory_order_acquire);
817 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
818 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
820 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
825 dispose_node( pHead.ptr() );
830 /// Check if the list is empty
833 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
836 /// Returns list's item count
838 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
839 this function always returns 0.
841 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
842 is empty. To check list emptyness use \p empty() method.
846 return m_ItemCounter.value();
851 // split-list support
852 bool insert_aux_node( node_type * pNode )
854 return insert_aux_node( m_pHead, pNode );
857 // split-list support
858 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
860 assert( pNode != nullptr );
862 // Hack: convert node_type to value_type.
863 // In principle, auxiliary node can be non-reducible to value_type
864 // We assume that comparator can correctly distinguish between aux and regular node.
865 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
868 bool insert_at( atomic_node_ptr& refHead, value_type& val )
870 position pos( refHead );
873 return insert_at_locked( pos, val );
877 template <typename Func>
878 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
880 link_checker::is_empty( node_traits::to_node_ptr( val ) );
881 position pos( refHead );
886 if ( search( refHead, val, pos, key_comparator()))
889 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
896 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
902 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
905 if ( insert_at_locked( refHead, val ))
906 return iterator( node_traits::to_node_ptr( val ));
910 template <typename Func>
911 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
913 position pos( refHead );
916 return ensure_at_locked( pos, val, func );
920 template <typename Func>
921 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
923 position pos( refHead );
926 std::pair<iterator, bool> ret = ensure_at_locked( pos, val, func );
927 return std::make_pair( ret.first != end(), ret.second );
931 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
933 position pos( refHead );
935 check_deadlock_policy::check();
940 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
942 if ( !unlink_node( pos, erase_mask )) {
953 template <typename Q, typename Compare, typename Func>
954 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
957 check_deadlock_policy::check();
962 if ( !search( pos.refHead, val, pos, cmp ) )
964 if ( !unlink_node( pos, erase_mask )) {
970 f( *node_traits::to_value_ptr( *pos.pCur ) );
976 template <typename Q, typename Compare, typename Func>
977 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
979 position pos( refHead );
980 return erase_at( pos, val, cmp, f );
983 template <typename Q, typename Compare>
984 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
986 position pos( refHead );
987 return erase_at( pos, val, cmp, [](value_type const&){} );
990 template <typename Q, typename Compare >
991 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
993 position pos( refHead );
995 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
1000 if ( !search( refHead, val, pos, cmp ) )
1002 if ( !unlink_node( pos, extract_mask )) {
1008 return node_traits::to_value_ptr( pos.pCur );
1013 template <typename Q, typename Compare, typename Func>
1014 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1016 position pos( refHead );
1020 if ( search( refHead, val, pos, cmp ) ) {
1021 assert( pos.pCur != nullptr );
1022 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1029 template <typename Q, typename Compare>
1030 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1032 position pos( refHead );
1035 return find_at_locked( pos, val, cmp ) != cend();
1039 template <typename Q, typename Compare>
1040 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1042 // RCU should be locked!
1043 assert(gc::is_locked() );
1045 position pos( refHead );
1047 if ( search( refHead, val, pos, cmp ))
1048 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1049 return raw_ptr( raw_ptr_disposer( pos ));
1056 template <typename Q, typename Compare>
1057 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1059 // RCU lock should be locked!!!
1060 assert( gc::is_locked() );
1062 atomic_node_ptr * pPrev;
1063 marked_node_ptr pNext;
1064 marked_node_ptr pCur;
1070 pCur = pPrev->load(memory_model::memory_order_acquire);
1074 if ( !pCur.ptr() ) {
1077 pos.pNext = nullptr;
1081 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1083 if ( pPrev->load(memory_model::memory_order_relaxed) != pCur
1084 || pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed))
1090 if ( pNext.bits() ) {
1091 // pCur is marked as deleted. Try to unlink it from the list
1092 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1093 if ( pNext.bits() == erase_mask )
1094 link_to_remove_chain( pos, pCur.ptr() );
1100 assert( pCur.ptr() != nullptr );
1101 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1104 pos.pCur = pCur.ptr();
1105 pos.pNext = pNext.ptr();
1108 pPrev = &( pCur->m_pNext );
1116 bool insert_at_locked( position& pos, value_type& val )
1118 // RCU lock should be locked!!!
1119 assert( gc::is_locked() );
1120 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1123 if ( search( pos.refHead, val, pos, key_comparator() ) )
1126 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1132 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1136 template <typename Func>
1137 std::pair<iterator, bool> ensure_at_locked( position& pos, value_type& val, Func func )
1139 // RCU lock should be locked!!!
1140 assert( gc::is_locked() );
1143 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1144 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1146 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1147 return std::make_pair( iterator( pos.pCur ), false );
1150 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1152 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1154 func( true, val , val );
1155 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1158 // clear the next field
1159 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1164 template <typename Q, typename Compare>
1165 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1167 assert( gc::is_locked() );
1169 if ( search( pos.refHead, val, pos, cmp ) ) {
1170 assert( pos.pCur != nullptr );
1171 return const_iterator( pos.pCur );
1178 }} // namespace cds::intrusive
1180 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H