3 #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
4 #define CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/urcu/details/check_deadlock.h>
8 #include <cds/details/binary_functor_wrapper.h>
9 #include <cds/details/make_const_type.h>
10 #include <cds/urcu/exempt_ptr.h>
12 namespace cds { namespace intrusive {
15 namespace michael_list {
17 /// Node specialization for uRCU
18 template <class RCU, typename Tag>
19 struct node< cds::urcu::gc< RCU >, Tag >
21 typedef cds::urcu::gc< RCU > gc; ///< Garbage collector
22 typedef Tag tag; ///< tag
24 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
25 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
27 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
28 node * m_pDelChain; ///< Deleted node chain (local for a thread)
30 CDS_CONSTEXPR node() CDS_NOEXCEPT
32 , m_pDelChain( nullptr )
35 } // namespace michael_list
38 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
39 /** @ingroup cds_intrusive_list
40 \anchor cds_intrusive_MichaelList_rcu
42 Usually, ordered single-linked list is used as a building block for the hash table implementation.
43 The complexity of searching is <tt>O(N)</tt>.
46 - \p RCU - one of \ref cds_urcu_gc "RCU type"
47 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
48 cds::intrusive::micheal_list::node
49 - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
50 list with \p cds::intrusive::michael_list::make_traits metafunction,
51 see \ref cds_intrusive_MichaelList_hp "here" for explanations.
54 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
55 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
56 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
58 #include <cds/urcu/general_buffered.h>
59 #include <cds/intrusive/michael_list_rcu.h>
61 // Now, you can declare Michael's list for type Foo and default traits:
62 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
65 template < typename RCU, typename T,
66 #ifdef CDS_DOXYGEN_INVOKED
67 class Traits = michael_list::traits
72 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
75 typedef T value_type; ///< type of value stored in the list
76 typedef Traits traits; ///< Traits template parameter
78 typedef typename traits::hook hook; ///< hook type
79 typedef typename hook::node_type node_type; ///< node type
81 # ifdef CDS_DOXYGEN_INVOKED
82 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
84 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
87 typedef typename traits::disposer disposer; ///< disposer used
88 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
89 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
91 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
92 typedef typename traits::back_off back_off; ///< back-off strategy
93 typedef typename traits::item_counter item_counter; ///< Item counting policy used
94 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
95 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
97 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
98 static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
101 // Rebind traits (split-list support)
102 template <typename... Options>
103 struct rebind_traits {
107 , typename cds::opt::make_options< traits, Options...>::type
113 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
114 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
115 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
117 atomic_node_ptr m_pHead ; ///< Head pointer
118 item_counter m_ItemCounter ; ///< Item counter
121 /// Position pointer for item search
123 atomic_node_ptr * pPrev ; ///< Previous node
124 node_type * pCur ; ///< Current node
125 node_type * pNext ; ///< Next node
127 atomic_node_ptr& refHead;
128 node_type * pDelChain; ///< Head of deleted node chain
130 position( atomic_node_ptr& head )
132 , pDelChain( nullptr )
138 assert( pDelChain == nullptr );
148 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
150 static void clear_links( node_type * pNode )
152 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
153 pNode->m_pDelChain = nullptr;
156 struct clear_and_dispose {
157 void operator()( value_type * p )
159 assert( p != nullptr );
160 clear_links( node_traits::to_node_ptr(p));
167 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
172 static void dispose_node( node_type * pNode )
175 assert( !gc::is_locked() );
177 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
180 bool link_node( node_type * pNode, position& pos )
182 assert( pNode != nullptr );
183 link_checker::is_empty( pNode );
185 marked_node_ptr p( pos.pCur );
186 pNode->m_pNext.store( p, memory_model::memory_order_release );
187 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
190 static void link_to_remove_chain( position& pos, node_type * pDel )
192 assert( pDel->m_pDelChain == nullptr );
194 pDel->m_pDelChain = pos.pDelChain;
195 pos.pDelChain = pDel;
198 static void free_node_chain( position& pos )
200 assert( !gc::is_locked() );
202 node_type * p = pos.pDelChain;
204 pos.pDelChain = nullptr;
206 node_type * pNext = p->m_pDelChain;
213 bool unlink_node( position& pos, bool bExtract )
215 // Mark the node (logical deletion)
216 marked_node_ptr next(pos.pNext, 0);
218 int const nMask = bExtract ? extract_mask : erase_mask;
219 if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )) {
221 // Try physical removal
222 marked_node_ptr cur(pos.pCur);
223 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
225 link_to_remove_chain( pos, pos.pCur );
228 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
238 template <bool IsConst>
241 friend class MichaelList;
242 value_type * m_pNode;
247 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
248 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
253 explicit iterator_type( node_type * pNode)
256 m_pNode = node_traits::to_value_ptr( *pNode );
260 explicit iterator_type( atomic_node_ptr const& refNode)
262 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
263 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
267 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
268 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
274 iterator_type( const iterator_type& src )
275 : m_pNode( src.m_pNode )
278 value_ptr operator ->() const
283 value_ref operator *() const
285 assert( m_pNode != nullptr );
290 iterator_type& operator ++()
297 iterator_type operator ++(int)
299 iterator_type i(*this);
304 iterator_type& operator = (const iterator_type& src)
306 m_pNode = src.m_pNode;
311 bool operator ==(iterator_type<C> const& i ) const
313 return m_pNode == i.m_pNode;
316 bool operator !=(iterator_type<C> const& i ) const
318 return m_pNode != i.m_pNode;
325 typedef iterator_type<false> iterator;
326 /// Const forward iterator
327 typedef iterator_type<true> const_iterator;
329 /// Returns a forward iterator addressing the first element in a list
331 For empty list \code begin() == end() \endcode
335 return iterator( m_pHead );
338 /// Returns an iterator that addresses the location succeeding the last element in a list
340 Do not use the value returned by <tt>end</tt> function to access any item.
341 Internally, <tt>end</tt> returning value equals to \p nullptr.
343 The returned value can be used only to control reaching the end of the list.
344 For empty list \code begin() == end() \endcode
351 /// Returns a forward const iterator addressing the first element in a list
352 const_iterator begin() const
354 return const_iterator(m_pHead );
356 /// Returns a forward const iterator addressing the first element in a list
357 const_iterator cbegin() const
359 return const_iterator(m_pHead );
362 /// Returns an const iterator that addresses the location succeeding the last element in a list
363 const_iterator end() const
365 return const_iterator();
367 /// Returns an const iterator that addresses the location succeeding the last element in a list
368 const_iterator cend() const
370 return const_iterator();
374 /// Default constructor initializes empty list
378 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
389 The function inserts \p val in the list if the list does not contain
390 an item with key equal to \p val.
392 The function makes RCU lock internally.
394 Returns \p true if \p val is linked into the list, \p false otherwise.
396 bool insert( value_type& val )
398 return insert_at( m_pHead, val );
403 This function is intended for derived non-intrusive containers.
405 The function allows to split new item creating into two part:
406 - create item with key only
407 - insert new item into the list
408 - if inserting is success, calls \p f functor to initialize value-field of \p val.
410 The functor signature is:
412 void func( value_type& val );
414 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
415 \p val no any other changes could be made on this list's item by concurrent threads.
416 The user-defined functor is called only if the inserting is success.
418 The function makes RCU lock internally.
420 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
422 template <typename Func>
423 bool insert( value_type& val, Func f )
425 return insert_at( m_pHead, val, f );
428 /// Ensures that the \p item exists in the list
430 The operation performs inserting or changing data with lock-free manner.
432 If the item \p val not found in the list, then \p val is inserted into the list.
433 Otherwise, the functor \p func is called with item found.
434 The functor signature is:
437 void operator()( bool bNew, value_type& item, value_type& val );
441 - \p bNew - \p true if the item has been inserted, \p false otherwise
442 - \p item - item of the list
443 - \p val - argument \p val passed into the \p ensure function
444 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
445 refer to the same thing.
447 The functor may change non-key fields of the \p item; however, \p func must guarantee
448 that during changing no any other modifications could be made on this item by concurrent threads.
450 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
451 \p second is true if new item has been added or \p false if the item with \p key
452 already is in the list.
454 The function makes RCU lock internally.
456 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
458 template <typename Func>
459 std::pair<bool, bool> ensure( value_type& val, Func func )
461 return ensure_at( m_pHead, val, func );
464 /// Unlinks the item \p val from the list
466 The function searches the item \p val in the list and unlink it from the list
467 if it is found and it is equal to \p val.
469 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
470 and deletes the item found. \p unlink finds an item by key and deletes it
471 only if \p val is an item of that list, i.e. the pointer to the item found
472 is equal to <tt> &val </tt>.
474 The function returns \p true if success and \p false otherwise.
476 RCU \p synchronize method can be called.
477 Note that depending on RCU type used the \ref disposer call can be deferred.
479 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
480 deadlock checking policy is opt::v::rcu_throw_deadlock.
482 bool unlink( value_type& val )
484 return unlink_at( m_pHead, val );
487 /// Deletes the item from the list
488 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
489 The function searches an item with key equal to \p key in the list,
490 unlinks it from the list, and returns \p true.
491 If the item with the key equal to \p key is not found the function return \p false.
493 RCU \p synchronize method can be called.
494 Note that depending on RCU type used the \ref disposer call can be deferred.
496 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
497 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
499 template <typename Q>
500 bool erase( Q const& key )
502 return erase_at( m_pHead, key, key_comparator() );
505 /// Deletes the item from the list using \p pred predicate for searching
507 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
508 but \p pred is used for key comparing.
509 \p Less functor has the interface like \p std::less.
510 \p pred must imply the same element order as the comparator used for building the list.
512 template <typename Q, typename Less>
513 bool erase_with( Q const& key, Less pred )
516 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
519 /// Deletes the item from the list
520 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
521 The function searches an item with key equal to \p key in the list,
522 call \p func functor with item found, unlinks it from the list, and returns \p true.
523 The \p Func interface is
526 void operator()( value_type const& item );
530 If the item with the key equal to \p key is not found the function return \p false.
532 RCU \p synchronize method can be called.
533 Note that depending on RCU type used the \ref disposer call can be deferred.
535 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
536 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
538 template <typename Q, typename Func>
539 bool erase( Q const& key, Func func )
541 return erase_at( m_pHead, key, key_comparator(), func );
544 /// Deletes the item from the list using \p pred predicate for searching
546 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
547 but \p pred is used for key comparing.
548 \p Less functor has the interface like \p std::less.
549 \p pred must imply the same element order as the comparator used for building the list.
551 template <typename Q, typename Less, typename Func>
552 bool erase_with( Q const& key, Less pred, Func func )
555 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
558 /// Extracts an item from the list
560 @anchor cds_intrusive_MichaelList_rcu_extract
561 The function searches an item with key equal to \p key in the list,
562 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
563 If \p key is not found the function returns an empty \p exempt_ptr.
565 @note The function does NOT call RCU read-side lock or synchronization,
566 and does NOT dispose the item found. It just unlinks the item from the list
567 and returns a pointer to item found.
568 You should lock RCU before calling this function, and you should manually release
569 \p dest exempt pointer outside the RCU lock before reusing the pointer.
572 #include <cds/urcu/general_buffered.h>
573 #include <cds/intrusive/michael_list_rcu.h>
575 typedef cds::urcu::gc< general_buffered<> > rcu;
576 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
578 rcu_michael_list theList;
581 rcu_michael_list::exempt_ptr p1;
583 // first, we should lock RCU
586 // Now, you can apply extract function
587 // Note that you must not delete the item found inside the RCU lock
588 p1 = theList.extract( 10 )
590 // do something with p1
595 // We may safely release p1 here
596 // release() passes the pointer to RCU reclamation cycle:
597 // it invokes RCU retire_ptr function with the disposer you provided for the list.
601 template <typename Q>
602 exempt_ptr extract( Q const& key )
604 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
607 /// Extracts an item from the list using \p pred predicate for searching
609 This function is the analog for \p extract(Q const&)
611 The \p pred is a predicate used for key comparing.
612 \p Less has the interface like \p std::less.
613 \p pred must imply the same element order as \ref key_comparator.
615 template <typename Q, typename Less>
616 exempt_ptr extract_with( Q const& key, Less pred )
619 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
622 /// Find the key \p val
623 /** \anchor cds_intrusive_MichaelList_rcu_find_func
624 The function searches the item with key equal to \p key
625 and calls the functor \p f for item found.
626 The interface of \p Func functor is:
629 void operator()( value_type& item, Q& key );
632 where \p item is the item found, \p key is the <tt>find</tt> function argument.
634 The functor can change non-key fields of \p item.
635 The function \p find does not serialize simultaneous access to the list \p item. If such access is
636 possible you must provide your own synchronization schema to exclude unsafe item modifications.
638 The function makes RCU lock internally.
640 The function returns \p true if \p val is found, \p false otherwise.
642 template <typename Q, typename Func>
643 bool find( Q& key, Func f ) const
645 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
648 template <typename Q, typename Func>
649 bool find( Q const& key, Func f ) const
651 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, key_comparator(), f );
655 /// Finds \p key using \p pred predicate for searching
657 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
658 but \p pred is used for key comparing.
659 \p Less functor has the interface like \p std::less.
660 \p pred must imply the same element order as the comparator used for building the list.
662 template <typename Q, typename Less, typename Func>
663 bool find_with( Q& key, Less pred, Func f ) const
666 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
669 template <typename Q, typename Less, typename Func>
670 bool find_with( Q const& key, Less pred, Func f ) const
673 return find_at( const_cast<atomic_node_ptr&>(m_pHead), key, cds::opt::details::make_comparator_from_less<Less>(), f );
678 /** \anchor cds_intrusive_MichaelList_rcu_find_val
679 The function searches the item with key equal to \p key
680 and returns \p true if \p val found or \p false otherwise.
682 template <typename Q>
683 bool find( Q const& key ) const
685 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator() );
688 /// Finds \p key using \p pred predicate for searching
690 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
691 but \p pred is used for key comparing.
692 \p Less functor has the interface like \p std::less.
693 \p pred must imply the same element order as the comparator used for building the list.
695 template <typename Q, typename Less>
696 bool find_with( Q const& key, Less pred ) const
699 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>() );
702 /// Finds \p key and return the item found
703 /** \anchor cds_intrusive_MichaelList_rcu_get
704 The function searches the item with key equal to \p key and returns the pointer to item found.
705 If \p key is not found it returns \p nullptr.
707 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
709 RCU should be locked before call of this function.
710 Returned item is valid only while RCU is locked:
712 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
717 ord_list::rcu_lock lock;
719 foo * pVal = theList.get( 5 );
724 // Unlock RCU by rcu_lock destructor
725 // pVal can be retired by disposer at any time after RCU has been unlocked
729 template <typename Q>
730 value_type * get( Q const& key ) const
732 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, key_comparator());
735 /// Finds \p key and return the item found
737 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
738 but \p pred is used for comparing the keys.
740 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
742 \p pred must imply the same element order as the comparator used for building the list.
744 template <typename Q, typename Less>
745 value_type * get_with( Q const& key, Less pred ) const
748 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), key, cds::opt::details::make_comparator_from_less<Less>());
751 /// Clears the list using default disposer
753 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
755 RCU \p synchronize method can be called.
756 Note that depending on RCU type used the \ref disposer invocation can be deferred.
758 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
759 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
764 check_deadlock_policy::check();
766 marked_node_ptr pHead;
770 pHead = m_pHead.load(memory_model::memory_order_acquire);
773 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
774 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
776 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
781 dispose_node( pHead.ptr() );
786 /// Check if the list is empty
789 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
792 /// Returns list's item count
794 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
795 this function always returns 0.
797 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
798 is empty. To check list emptyness use \p empty() method.
802 return m_ItemCounter.value();
807 // split-list support
808 bool insert_aux_node( node_type * pNode )
810 return insert_aux_node( m_pHead, pNode );
813 // split-list support
814 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
816 assert( pNode != nullptr );
818 // Hack: convert node_type to value_type.
819 // In principle, auxiliary node can be non-reducible to value_type
820 // We assume that comparator can correctly distinguish between aux and regular node.
821 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
824 bool insert_at( atomic_node_ptr& refHead, value_type& val )
827 return insert_at_locked( refHead, val );
830 bool insert_at_locked( atomic_node_ptr& refHead, value_type& val )
832 // RCU lock should be locked!!!
833 assert( gc::is_locked() );
835 link_checker::is_empty( node_traits::to_node_ptr( val ) );
836 position pos( refHead );
839 if ( search( refHead, val, pos, key_comparator() ) )
842 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
848 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
852 template <typename Func>
853 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
855 link_checker::is_empty( node_traits::to_node_ptr( val ) );
856 position pos( refHead );
860 if ( search( refHead, val, pos, key_comparator() ) )
863 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
870 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
874 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
877 if ( insert_at_locked( refHead, val ))
878 return iterator( node_traits::to_node_ptr( val ));
882 template <typename Func>
883 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func )
886 return ensure_at_locked( refHead, val, func );
889 template <typename Func>
890 std::pair<iterator, bool> ensure_at_locked( atomic_node_ptr& refHead, value_type& val, Func func )
892 position pos( refHead );
894 // RCU lock should be locked!!!
895 assert( gc::is_locked() );
898 if ( search( refHead, val, pos, key_comparator() ) ) {
899 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
901 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
902 return std::make_pair( iterator( pos.pCur ), false );
905 link_checker::is_empty( node_traits::to_node_ptr( val ) );
907 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
909 func( true, val , val );
910 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
913 // clear the next field
914 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
919 template <typename Func>
920 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
923 std::pair<iterator, bool> ret = ensure_at_locked( refHead, val, func );
924 return std::make_pair( ret.first != end(), ret.second );
927 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
929 position pos( refHead );
931 check_deadlock_policy::check();
936 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
938 if ( !unlink_node( pos, false )) {
945 free_node_chain( pos );
950 template <typename Q, typename Compare, typename Func>
951 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
954 check_deadlock_policy::check();
959 if ( !search( refHead, val, pos, cmp ) )
961 if ( !unlink_node( pos, false )) {
967 f( *node_traits::to_value_ptr( *pos.pCur ) );
969 free_node_chain( pos );
974 template <typename Q, typename Compare, typename Func>
975 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
977 position pos( refHead );
978 return erase_at( refHead, val, cmp, f, pos );
981 template <typename Q, typename Compare>
982 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
984 position pos( refHead );
985 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
988 template <typename Q, typename Compare >
989 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
991 position pos( refHead );
993 assert( gc::is_locked() ) ; // RCU must be locked!!!
996 if ( !search( refHead, val, pos, cmp ) )
998 if ( !unlink_node( pos, true )) {
1004 return node_traits::to_value_ptr( pos.pCur );
1008 template <typename Q, typename Compare, typename Func>
1009 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f ) const
1011 position pos( refHead );
1014 if ( search( refHead, val, pos, cmp ) ) {
1015 assert( pos.pCur != nullptr );
1016 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1022 template <typename Q, typename Compare>
1023 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1026 return find_at_( refHead, val, cmp ) != end();
1029 template <typename Q, typename Compare>
1030 value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1032 value_type * pFound = nullptr;
1033 return find_at( refHead, val, cmp,
1034 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1038 template <typename Q, typename Compare>
1039 const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1041 assert( gc::is_locked() );
1042 position pos( refHead );
1044 if ( search( refHead, val, pos, cmp ) ) {
1045 assert( pos.pCur != nullptr );
1046 return const_iterator( pos.pCur );
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 );
1115 }} // namespace cds::intrusive
1117 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H