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 assert(gc::is_locked() );
237 // Mark the node (logical deletion)
238 marked_node_ptr next(pos.pNext, 0);
240 if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
242 // Try physical removal - fast path
243 marked_node_ptr cur(pos.pCur);
244 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
245 if ( nMask == erase_mask )
246 link_to_remove_chain( pos, pos.pCur );
250 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
260 template <bool IsConst>
263 friend class MichaelList;
264 value_type * m_pNode;
269 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
270 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
275 explicit iterator_type( node_type * pNode)
278 m_pNode = node_traits::to_value_ptr( *pNode );
282 explicit iterator_type( atomic_node_ptr const& refNode)
284 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
285 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
289 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
290 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
296 iterator_type( const iterator_type& src )
297 : m_pNode( src.m_pNode )
300 value_ptr operator ->() const
305 value_ref operator *() const
307 assert( m_pNode != nullptr );
312 iterator_type& operator ++()
319 iterator_type operator ++(int)
321 iterator_type i(*this);
326 iterator_type& operator = (const iterator_type& src)
328 m_pNode = src.m_pNode;
333 bool operator ==(iterator_type<C> const& i ) const
335 return m_pNode == i.m_pNode;
338 bool operator !=(iterator_type<C> const& i ) const
340 return m_pNode != i.m_pNode;
347 typedef iterator_type<false> iterator;
348 /// Const forward iterator
349 typedef iterator_type<true> const_iterator;
351 /// Returns a forward iterator addressing the first element in a list
353 For empty list \code begin() == end() \endcode
357 return iterator( m_pHead );
360 /// Returns an iterator that addresses the location succeeding the last element in a list
362 Do not use the value returned by <tt>end</tt> function to access any item.
363 Internally, <tt>end</tt> returning value equals to \p nullptr.
365 The returned value can be used only to control reaching the end of the list.
366 For empty list \code begin() == end() \endcode
373 /// Returns a forward const iterator addressing the first element in a list
374 const_iterator begin() const
376 return const_iterator(m_pHead );
378 /// Returns a forward const iterator addressing the first element in a list
379 const_iterator cbegin() const
381 return const_iterator(m_pHead );
384 /// Returns an const iterator that addresses the location succeeding the last element in a list
385 const_iterator end() const
387 return const_iterator();
389 /// Returns an const iterator that addresses the location succeeding the last element in a list
390 const_iterator cend() const
392 return const_iterator();
396 /// Default constructor initializes empty list
400 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
411 The function inserts \p val in the list if the list does not contain
412 an item with key equal to \p val.
414 The function makes RCU lock internally.
416 Returns \p true if \p val is linked into the list, \p false otherwise.
418 bool insert( value_type& val )
420 return insert_at( m_pHead, val );
425 This function is intended for derived non-intrusive containers.
427 The function allows to split new item creating into two part:
428 - create item with key only
429 - insert new item into the list
430 - if inserting is success, calls \p f functor to initialize value-field of \p val.
432 The functor signature is:
434 void func( value_type& val );
436 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
437 \p val no any other changes could be made on this list's item by concurrent threads.
438 The user-defined functor is called only if the inserting is success.
440 The function makes RCU lock internally.
442 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
444 template <typename Func>
445 bool insert( value_type& val, Func f )
447 return insert_at( m_pHead, val, f );
452 The operation performs inserting or changing data with lock-free manner.
454 If the item \p val not found in the list, then \p val is inserted into the list
455 iff \p bInsert is \p true.
456 Otherwise, the functor \p func is called with item found.
457 The functor signature is:
460 void operator()( bool bNew, value_type& item, value_type& val );
464 - \p bNew - \p true if the item has been inserted, \p false otherwise
465 - \p item - item of the list
466 - \p val - argument \p val passed into the \p update() function
467 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
468 refer to the same thing.
470 The functor may change non-key fields of the \p item; however, \p func must guarantee
471 that during changing no any other modifications could be made on this item by concurrent threads.
473 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
474 \p second is \p true if new item has been added or \p false if the item with \p key
475 already is in the list.
477 The function makes RCU lock internally.
479 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
481 template <typename Func>
482 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
484 return update_at( m_pHead, val, func, bInsert );
488 // Deprecated, use update()
489 template <typename Func>
490 std::pair<bool, bool> ensure( value_type& val, Func func )
492 return update( val, func, true );
495 /// Unlinks the item \p val from the list
497 The function searches the item \p val in the list and unlink it from the list
498 if it is found and it is equal to \p val.
500 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
501 and deletes the item found. \p unlink finds an item by key and deletes it
502 only if \p val is an item of that list, i.e. the pointer to the item found
503 is equal to <tt> &val </tt>.
505 The function returns \p true if success and \p false otherwise.
507 RCU \p synchronize method can be called.
508 Note that depending on RCU type used the \ref disposer call can be deferred.
510 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
511 deadlock checking policy is opt::v::rcu_throw_deadlock.
513 bool unlink( value_type& val )
515 return unlink_at( m_pHead, val );
518 /// Deletes the item from the list
519 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
520 The function searches an item with key equal to \p key in the list,
521 unlinks it from the list, and returns \p true.
522 If the item with the key equal to \p key is not found the function return \p false.
524 RCU \p synchronize method can be called.
525 Note that depending on RCU type used the \ref disposer call can be deferred.
527 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
528 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
530 template <typename Q>
531 bool erase( Q const& key )
533 return erase_at( m_pHead, key, key_comparator() );
536 /// Deletes the item from the list using \p pred predicate for searching
538 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
539 but \p pred is used for key comparing.
540 \p Less functor has the interface like \p std::less.
541 \p pred must imply the same element order as the comparator used for building the list.
543 template <typename Q, typename Less>
544 bool erase_with( Q const& key, Less pred )
547 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
550 /// Deletes the item from the list
551 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
552 The function searches an item with key equal to \p key in the list,
553 call \p func functor with item found, unlinks it from the list, and returns \p true.
554 The \p Func interface is
557 void operator()( value_type const& item );
561 If the item with the key equal to \p key is not found the function return \p false.
563 RCU \p synchronize method can be called.
564 Note that depending on RCU type used the \ref disposer call can be deferred.
566 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
567 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
569 template <typename Q, typename Func>
570 bool erase( Q const& key, Func func )
572 return erase_at( m_pHead, key, key_comparator(), func );
575 /// Deletes the item from the list using \p pred predicate for searching
577 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
578 but \p pred is used for key comparing.
579 \p Less functor has the interface like \p std::less.
580 \p pred must imply the same element order as the comparator used for building the list.
582 template <typename Q, typename Less, typename Func>
583 bool erase_with( Q const& key, Less pred, Func func )
586 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
589 /// Extracts an item from the list
591 @anchor cds_intrusive_MichaelList_rcu_extract
592 The function searches an item with key equal to \p key in the list,
593 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
594 If \p key is not found the function returns an empty \p exempt_ptr.
596 @note The function does NOT dispose the item found. It just unlinks the item from the list
597 and returns a pointer to item found.
598 You shouldn't lock RCU for current thread before calling this function, and you should manually release
599 \p dest exempt pointer outside the RCU lock before reusing it.
602 #include <cds/urcu/general_buffered.h>
603 #include <cds/intrusive/michael_list_rcu.h>
605 typedef cds::urcu::gc< general_buffered<> > rcu;
606 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
608 rcu_michael_list theList;
611 rcu_michael_list::exempt_ptr p1;
613 // The RCU should NOT be locked when extract() is called!
614 assert( !rcu::is_locked() );
616 // You can call extract() function
617 p1 = theList.extract( 10 );
619 // do something with p1
623 // We may safely release p1 here
624 // release() passes the pointer to RCU reclamation cycle:
625 // it invokes RCU retire_ptr function with the disposer you provided for the list.
629 template <typename Q>
630 exempt_ptr extract( Q const& key )
632 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
635 /// Extracts an item from the list using \p pred predicate for searching
637 This function is the analog for \p extract(Q const&)
639 The \p pred is a predicate used for key comparing.
640 \p Less has the interface like \p std::less.
641 \p pred must imply the same element order as \ref key_comparator.
643 template <typename Q, typename Less>
644 exempt_ptr extract_with( Q const& key, Less pred )
647 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
650 /// Find the key \p val
651 /** \anchor cds_intrusive_MichaelList_rcu_find_func
652 The function searches the item with key equal to \p key
653 and calls the functor \p f for item found.
654 The interface of \p Func functor is:
657 void operator()( value_type& item, Q& key );
660 where \p item is the item found, \p key is the <tt>find</tt> function argument.
662 The functor can change non-key fields of \p item.
663 The function \p find does not serialize simultaneous access to the list \p item. If such access is
664 possible you must provide your own synchronization schema to exclude unsafe item modifications.
666 The function makes RCU lock internally.
668 The function returns \p true if \p val is found, \p false otherwise.
670 template <typename Q, typename Func>
671 bool find( Q& key, Func f )
673 return find_at( m_pHead, key, key_comparator(), f );
676 template <typename Q, typename Func>
677 bool find( Q const& key, Func f )
679 return find_at( m_pHead, key, key_comparator(), f );
683 /// Finds \p key using \p pred predicate for searching
685 The function is an analog of \p find(Q&, Func)
686 but \p pred is used for key comparing.
687 \p Less functor has the interface like \p std::less.
688 \p pred must imply the same element order as the comparator used for building the list.
690 template <typename Q, typename Less, typename Func>
691 bool find_with( Q& key, Less pred, Func f )
694 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
697 template <typename Q, typename Less, typename Func>
698 bool find_with( Q const& key, Less pred, Func f )
701 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
706 /** \anchor cds_intrusive_MichaelList_rcu_find_val
707 The function searches the item with key equal to \p key
708 and returns \p true if \p val found or \p false otherwise.
710 template <typename Q>
711 bool find( Q const& key )
713 return find_at( m_pHead, key, key_comparator() );
716 /// Finds \p key using \p pred predicate for searching
718 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
719 but \p pred is used for key comparing.
720 \p Less functor has the interface like \p std::less.
721 \p pred must imply the same element order as the comparator used for building the list.
723 template <typename Q, typename Less>
724 bool find_with( Q const& key, Less pred )
727 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
730 /// Finds \p key and return the item found
731 /** \anchor cds_intrusive_MichaelList_rcu_get
732 The function searches the item with key equal to \p key and returns the pointer to item found.
733 If \p key is not found it returns empty \p raw_ptr object.
735 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
737 RCU should be locked before call of this function.
738 Returned item is valid only while RCU is locked:
740 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
743 typename ord_list::raw_ptr rp;
746 ord_list::rcu_lock lock;
748 rp = theList.get( 5 );
753 // Unlock RCU by rcu_lock destructor
754 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
756 // You can manually release rp after RCU-locked section
760 template <typename Q>
761 raw_ptr get( Q const& key )
763 return get_at( m_pHead, key, key_comparator());
766 /// Finds \p key and return the item found
768 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
769 but \p pred is used for comparing the keys.
771 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
773 \p pred must imply the same element order as the comparator used for building the list.
775 template <typename Q, typename Less>
776 raw_ptr get_with( Q const& key, Less pred )
779 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
782 /// Clears the list using default disposer
784 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
786 RCU \p synchronize method can be called.
787 Note that depending on RCU type used the \ref disposer invocation can be deferred.
789 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
790 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
795 check_deadlock_policy::check();
797 marked_node_ptr pHead;
801 pHead = m_pHead.load(memory_model::memory_order_acquire);
804 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
805 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
807 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
812 dispose_node( pHead.ptr() );
817 /// Check if the list is empty
820 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
823 /// Returns list's item count
825 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
826 this function always returns 0.
828 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
829 is empty. To check list emptyness use \p empty() method.
833 return m_ItemCounter.value();
838 // split-list support
839 bool insert_aux_node( node_type * pNode )
841 return insert_aux_node( m_pHead, pNode );
844 // split-list support
845 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
847 assert( pNode != nullptr );
849 // Hack: convert node_type to value_type.
850 // In principle, auxiliary node can be non-reducible to value_type
851 // We assume that comparator can correctly distinguish between aux and regular node.
852 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
855 bool insert_at( atomic_node_ptr& refHead, value_type& val )
857 position pos( refHead );
860 return insert_at_locked( pos, val );
864 template <typename Func>
865 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
867 link_checker::is_empty( node_traits::to_node_ptr( val ) );
868 position pos( refHead );
873 if ( search( refHead, val, pos, key_comparator()))
876 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
883 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
889 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
892 if ( insert_at_locked( refHead, val ))
893 return iterator( node_traits::to_node_ptr( val ));
897 template <typename Func>
898 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
900 position pos( refHead );
903 return update_at_locked( pos, val, func, bInsert );
907 template <typename Func>
908 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
910 return update_at_( refHead, val, func, true );
913 template <typename Func>
914 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
916 position pos( refHead );
919 std::pair<iterator, bool> ret = update_at_locked( pos, val, func, bInsert );
920 return std::make_pair( ret.first != end(), ret.second );
924 template <typename Func>
925 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
927 return update_at( refHead, val, func, true );
930 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
932 position pos( refHead );
934 check_deadlock_policy::check();
939 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
941 if ( !unlink_node( pos, erase_mask )) {
952 template <typename Q, typename Compare, typename Func>
953 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
956 check_deadlock_policy::check();
961 if ( !search( pos.refHead, val, pos, cmp ) )
963 if ( !unlink_node( pos, erase_mask )) {
969 f( *node_traits::to_value_ptr( *pos.pCur ) );
975 template <typename Q, typename Compare, typename Func>
976 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
978 position pos( refHead );
979 return erase_at( pos, val, cmp, f );
982 template <typename Q, typename Compare>
983 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
985 position pos( refHead );
986 return erase_at( pos, val, cmp, [](value_type const&){} );
989 template <typename Q, typename Compare >
990 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
992 position pos( refHead );
994 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
996 node_type * pExtracted;
1000 if ( !search( refHead, val, pos, cmp ) )
1002 // store pCur since it may be changed by unlink_node() slow path
1003 pExtracted = pos.pCur;
1004 if ( !unlink_node( pos, extract_mask )) {
1010 value_type * pRet = node_traits::to_value_ptr( pExtracted );
1011 assert( pExtracted->m_pDelChain == nullptr );
1017 template <typename Q, typename Compare, typename Func>
1018 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1020 position pos( refHead );
1024 if ( search( refHead, val, pos, cmp ) ) {
1025 assert( pos.pCur != nullptr );
1026 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1033 template <typename Q, typename Compare>
1034 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1036 position pos( refHead );
1039 return find_at_locked( pos, val, cmp ) != cend();
1043 template <typename Q, typename Compare>
1044 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1046 // RCU should be locked!
1047 assert(gc::is_locked() );
1049 position pos( refHead );
1051 if ( search( refHead, val, pos, cmp ))
1052 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1053 return raw_ptr( raw_ptr_disposer( pos ));
1060 template <typename Q, typename Compare>
1061 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1063 // RCU lock should be locked!!!
1064 assert( gc::is_locked() );
1066 atomic_node_ptr * pPrev;
1067 marked_node_ptr pNext;
1068 marked_node_ptr pCur;
1074 pCur = pPrev->load(memory_model::memory_order_acquire);
1078 if ( !pCur.ptr() ) {
1081 pos.pNext = nullptr;
1085 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1087 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
1088 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire))
1094 if ( pNext.bits() ) {
1095 // pCur is marked as deleted. Try to unlink it from the list
1096 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1097 if ( pNext.bits() == erase_mask )
1098 link_to_remove_chain( pos, pCur.ptr() );
1104 assert( pCur.ptr() != nullptr );
1105 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1108 pos.pCur = pCur.ptr();
1109 pos.pNext = pNext.ptr();
1112 pPrev = &( pCur->m_pNext );
1120 bool insert_at_locked( position& pos, value_type& val )
1122 // RCU lock should be locked!!!
1123 assert( gc::is_locked() );
1124 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1127 if ( search( pos.refHead, val, pos, key_comparator() ) )
1130 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1136 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1140 template <typename Func>
1141 std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
1143 // RCU lock should be locked!!!
1144 assert( gc::is_locked() );
1147 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1148 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1150 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1151 return std::make_pair( iterator( pos.pCur ), false );
1155 return std::make_pair( end(), false );
1157 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1159 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1161 func( true, val , val );
1162 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1165 // clear the next field
1166 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1171 template <typename Q, typename Compare>
1172 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1174 assert( gc::is_locked() );
1176 if ( search( pos.refHead, val, pos, cmp ) ) {
1177 assert( pos.pCur != nullptr );
1178 return const_iterator( pos.pCur );
1185 }} // namespace cds::intrusive
1187 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H