3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_RCU_H
4 #define __CDS_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/urcu/exempt_ptr.h>
11 namespace cds { namespace intrusive {
13 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
14 /** @ingroup cds_intrusive_list
15 \anchor cds_intrusive_MichaelList_rcu
17 Usually, ordered single-linked list is used as a building block for the hash table implementation.
18 The complexity of searching is <tt>O(N)</tt>.
21 - \p RCU - one of \ref cds_urcu_gc "RCU type"
22 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
23 cds::intrusive::micheal_list::node
24 - \p Traits - type traits. See michael_list::type_traits for explanation.
26 It is possible to declare option-based list with \p %cds::intrusive::michael_list::make_traits metafunction istead of \p Traits template
27 argument. Template argument list \p Options of cds::intrusive::michael_list::make_traits metafunction are:
28 - opt::hook - hook used. Possible values are: michael_list::base_hook, michael_list::member_hook, michael_list::traits_hook.
29 If the option is not specified, <tt>michael_list::base_hook<></tt> is used.
30 - opt::compare - key comparison functor. No default functor is provided.
31 If the option is not specified, the opt::less is used.
32 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
33 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer
34 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
35 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
36 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
37 or opt::v::sequential_consistent (sequentially consisnent memory model).
40 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
41 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
42 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
44 #include <cds/urcu/general_buffered.h>
45 #include <cds/intrusive/michael_list_rcu.h>
47 // Now, you can declare Michael's list for type Foo and default traits:
48 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
51 template < typename RCU, typename T, class Traits >
52 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
55 typedef T value_type ; ///< type of value stored in the queue
56 typedef Traits options ; ///< Traits template parameter
58 typedef typename options::hook hook ; ///< hook type
59 typedef typename hook::node_type node_type ; ///< node type
61 # ifdef CDS_DOXYGEN_INVOKED
62 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
64 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
67 typedef typename options::disposer disposer ; ///< disposer used
68 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
69 typedef typename michael_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
71 typedef cds::urcu::gc<RCU> gc ; ///< RCU schema
72 typedef typename options::back_off back_off ; ///< back-off strategy
73 typedef typename options::item_counter item_counter; ///< Item counting policy used
74 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
75 typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
77 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
78 static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
81 // Rebind options (split-list support)
82 template <typename... Options>
83 struct rebind_options {
87 , typename cds::opt::make_options< options, Options...>::type
93 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
94 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
95 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
97 atomic_node_ptr m_pHead ; ///< Head pointer
98 item_counter m_ItemCounter ; ///< Item counter
101 /// Position pointer for item search
103 atomic_node_ptr * pPrev ; ///< Previous node
104 node_type * pCur ; ///< Current node
105 node_type * pNext ; ///< Next node
108 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
110 static void clear_links( node_type * pNode )
112 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
115 struct clear_and_dispose {
116 void operator()( value_type * p )
118 assert( p != nullptr );
119 clear_links( node_traits::to_node_ptr(p));
126 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
131 static void dispose_node( node_type * pNode )
134 assert( !gc::is_locked() );
136 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
139 bool link_node( node_type * pNode, position& pos )
141 assert( pNode != nullptr );
142 link_checker::is_empty( pNode );
144 marked_node_ptr p( pos.pCur );
145 pNode->m_pNext.store( p, memory_model::memory_order_relaxed );
146 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
149 bool unlink_node( position& pos )
151 // Mark the node (logical deleting)
152 marked_node_ptr next(pos.pNext, 0);
153 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
154 marked_node_ptr cur(pos.pCur);
155 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
158 CDS_VERIFY( pos.pCur->m_pNext.compare_exchange_strong( next, next ^ 1, memory_model::memory_order_release, atomics::memory_order_relaxed ));
166 template <bool IsConst>
169 friend class MichaelList;
170 value_type * m_pNode;
175 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
176 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
181 explicit iterator_type( node_type * pNode)
184 m_pNode = node_traits::to_value_ptr( *pNode );
188 explicit iterator_type( atomic_node_ptr const& refNode)
190 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
191 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
195 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
196 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
202 iterator_type( const iterator_type& src )
203 : m_pNode( src.m_pNode )
206 value_ptr operator ->() const
211 value_ref operator *() const
213 assert( m_pNode != nullptr );
218 iterator_type& operator ++()
225 iterator_type operator ++(int)
227 iterator_type i(*this);
232 iterator_type& operator = (const iterator_type& src)
234 m_pNode = src.m_pNode;
239 bool operator ==(iterator_type<C> const& i ) const
241 return m_pNode == i.m_pNode;
244 bool operator !=(iterator_type<C> const& i ) const
246 return m_pNode != i.m_pNode;
253 typedef iterator_type<false> iterator;
254 /// Const forward iterator
255 typedef iterator_type<true> const_iterator;
257 /// Returns a forward iterator addressing the first element in a list
259 For empty list \code begin() == end() \endcode
263 return iterator( m_pHead );
266 /// Returns an iterator that addresses the location succeeding the last element in a list
268 Do not use the value returned by <tt>end</tt> function to access any item.
269 Internally, <tt>end</tt> returning value equals to \p nullptr.
271 The returned value can be used only to control reaching the end of the list.
272 For empty list \code begin() == end() \endcode
279 /// Returns a forward const iterator addressing the first element in a list
280 const_iterator begin() const
282 return const_iterator(m_pHead );
284 /// Returns a forward const iterator addressing the first element in a list
285 const_iterator cbegin()
287 return const_iterator(m_pHead );
290 /// Returns an const iterator that addresses the location succeeding the last element in a list
291 const_iterator end() const
293 return const_iterator();
295 /// Returns an const iterator that addresses the location succeeding the last element in a list
296 const_iterator cend()
298 return const_iterator();
302 /// Default constructor initializes empty list
306 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
317 The function inserts \p val in the list if the list does not contain
318 an item with key equal to \p val.
320 The function makes RCU lock internally.
322 Returns \p true if \p val is linked into the list, \p false otherwise.
324 bool insert( value_type& val )
326 return insert_at( m_pHead, val );
331 This function is intended for derived non-intrusive containers.
333 The function allows to split new item creating into two part:
334 - create item with key only
335 - insert new item into the list
336 - if inserting is success, calls \p f functor to initialize value-field of \p val.
338 The functor signature is:
340 void func( value_type& val );
342 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
343 \p val no any other changes could be made on this list's item by concurrent threads.
344 The user-defined functor is called only if the inserting is success and may be passed by reference
347 The function makes RCU lock internally.
349 template <typename Func>
350 bool insert( value_type& val, Func f )
352 return insert_at( m_pHead, val, f );
355 /// Ensures that the \p item exists in the list
357 The operation performs inserting or changing data with lock-free manner.
359 If the item \p val not found in the list, then \p val is inserted into the list.
360 Otherwise, the functor \p func is called with item found.
361 The functor signature is:
364 void operator()( bool bNew, value_type& item, value_type& val );
368 - \p bNew - \p true if the item has been inserted, \p false otherwise
369 - \p item - item of the list
370 - \p val - argument \p val passed into the \p ensure function
371 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
372 refer to the same thing.
374 The functor may change non-key fields of the \p item; however, \p func must guarantee
375 that during changing no any other modifications could be made on this item by concurrent threads.
377 You can pass \p func argument by value or by reference using \p std::ref.
379 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
380 \p second is true if new item has been added or \p false if the item with \p key
381 already is in the list.
383 The function makes RCU lock internally.
386 template <typename Func>
387 std::pair<bool, bool> ensure( value_type& val, Func func )
389 return ensure_at( m_pHead, val, func );
392 /// Unlinks the item \p val from the list
394 The function searches the item \p val in the list and unlink it from the list
395 if it is found and it is equal to \p val.
397 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
398 and deletes the item found. \p unlink finds an item by key and deletes it
399 only if \p val is an item of that list, i.e. the pointer to item found
400 is equal to <tt> &val </tt>.
402 The function returns \p true if success and \p false otherwise.
404 RCU \p synchronize method can be called.
405 Note that depending on RCU type used the \ref disposer call can be deferred.
407 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
408 deadlock checking policy is opt::v::rcu_throw_deadlock.
410 bool unlink( value_type& val )
412 return unlink_at( m_pHead, val );
415 /// Deletes the item from the list
416 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
417 The function searches an item with key equal to \p val in the list,
418 unlinks it from the list, and returns \p true.
419 If the item with the key equal to \p val is not found the function return \p false.
421 RCU \p synchronize method can be called.
422 Note that depending on RCU type used the \ref disposer call can be deferred.
424 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
425 the deadlock checking policy is opt::v::rcu_throw_deadlock.
427 template <typename Q>
428 bool erase( Q const& val )
430 return erase_at( m_pHead, val, key_comparator() );
433 /// Deletes the item from the list using \p pred predicate for searching
435 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
436 but \p pred is used for key comparing.
437 \p Less functor has the interface like \p std::less.
438 \p pred must imply the same element order as the comparator used for building the list.
440 template <typename Q, typename Less>
441 bool erase_with( Q const& val, Less pred )
443 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
446 /// Deletes the item from the list
447 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
448 The function searches an item with key equal to \p val in the list,
449 call \p func functor with item found, unlinks it from the list, and returns \p true.
450 The \p Func interface is
453 void operator()( value_type const& item );
456 The functor may be passed by reference using <tt>boost:ref</tt>
458 If the item with the key equal to \p val is not found the function return \p false.
460 RCU \p synchronize method can be called.
461 Note that depending on RCU type used the \ref disposer call can be deferred.
463 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
464 the deadlock checking policy is opt::v::rcu_throw_deadlock.
466 template <typename Q, typename Func>
467 bool erase( Q const& val, Func func )
469 return erase_at( m_pHead, val, key_comparator(), func );
472 /// Deletes the item from the list using \p pred predicate for searching
474 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
475 but \p pred is used for key comparing.
476 \p Less functor has the interface like \p std::less.
477 \p pred must imply the same element order as the comparator used for building the list.
479 template <typename Q, typename Less, typename Func>
480 bool erase_with( Q const& val, Less pred, Func func )
482 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), func );
485 /// Extracts an item from the list
487 @anchor cds_intrusive_MichaelList_rcu_extract
488 The function searches an item with key equal to \p val in the list,
489 unlinks it from the list, and returns pointer to an item found in \p dest parameter.
490 If the item with the key equal to \p val is not found the function returns \p false,
493 @note The function does NOT call RCU read-side lock or synchronization,
494 and does NOT dispose the item found. It just excludes the item from the list
495 and returns a pointer to item found.
496 You should lock RCU before calling this function, and you should manually release
497 \p dest exempt pointer outside the RCU lock before reusing the pointer.
500 #include <cds/urcu/general_buffered.h>
501 #include <cds/intrusive/michael_list_rcu.h>
503 typedef cds::urcu::gc< general_buffered<> > rcu;
504 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
506 rcu_michael_list theList;
509 rcu_michael_list::exempt_ptr p1;
511 // first, we should lock RCU
514 // Now, you can apply extract function
515 // Note that you must not delete the item found inside the RCU lock
516 if ( theList.extract( p1, 10 )) {
517 // do something with p1
522 // We may safely release p1 here
523 // release() passes the pointer to RCU reclamation cycle:
524 // it invokes RCU retire_ptr function with the disposer you provided for the list.
528 template <typename Q>
529 bool extract( exempt_ptr& dest, Q const& val )
531 dest = extract_at( m_pHead, val, key_comparator() );
532 return !dest.empty();
535 /// Extracts an item from the list using \p pred predicate for searching
537 This function is the analog for \ref cds_intrusive_MichaelList_rcu_extract "extract(exempt_ptr&, Q const&)".
539 The \p pred is a predicate used for key comparing.
540 \p Less has the interface like \p std::less.
541 \p pred must imply the same element order as \ref key_comparator.
543 template <typename Q, typename Less>
544 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
546 dest = extract_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
547 return !dest.empty();
550 /// Find the key \p val
551 /** \anchor cds_intrusive_MichaelList_rcu_find_func
552 The function searches the item with key equal to \p val
553 and calls the functor \p f for item found.
554 The interface of \p Func functor is:
557 void operator()( value_type& item, Q& val );
560 where \p item is the item found, \p val is the <tt>find</tt> function argument.
562 You can pass \p f argument by value or by reference using \p std::ref.
564 The functor can change non-key fields of \p item.
565 The function \p find does not serialize simultaneous access to the list \p item. If such access is
566 possible you must provide your own synchronization schema to exclude unsafe item modifications.
568 The function makes RCU lock internally.
570 The function returns \p true if \p val is found, \p false otherwise.
572 template <typename Q, typename Func>
573 bool find( Q& val, Func f ) const
575 return find_at( const_cast<atomic_node_ptr&>(m_pHead), val, key_comparator(), f );
578 /// Finds the key \p val using \p pred predicate for searching
580 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
581 but \p pred is used for key comparing.
582 \p Less functor has the interface like \p std::less.
583 \p pred must imply the same element order as the comparator used for building the list.
585 template <typename Q, typename Less, typename Func>
586 bool find_with( Q& val, Less pred, Func f ) const
588 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
591 /// Find the key \p val
592 /** \anchor cds_intrusive_MichaelList_rcu_find_cfunc
593 The function searches the item with key equal to \p val
594 and calls the functor \p f for item found.
595 The interface of \p Func functor is:
598 void operator()( value_type& item, Q const& val );
601 where \p item is the item found, \p val is the <tt>find</tt> function argument.
603 You can pass \p f argument by value or by reference using \p std::ref.
605 The functor can change non-key fields of \p item.
606 The function \p find does not serialize simultaneous access to the list \p item. If such access is
607 possible you must provide your own synchronization schema to exclude unsafe item modifications.
609 The function makes RCU lock internally.
611 The function returns \p true if \p val is found, \p false otherwise.
613 template <typename Q, typename Func>
614 bool find( Q const& val, Func f ) const
616 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, key_comparator(), f );
619 /// Finds the key \p val using \p pred predicate for searching
621 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_cfunc "find(Q const&, Func)"
622 but \p pred is used for key comparing.
623 \p Less functor has the interface like \p std::less.
624 \p pred must imply the same element order as the comparator used for building the list.
626 template <typename Q, typename Less, typename Func>
627 bool find_with( Q const& val, Less pred, Func f ) const
629 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
632 /// Find the key \p val
633 /** \anchor cds_intrusive_MichaelList_rcu_find_val
634 The function searches the item with key equal to \p val
635 and returns \p true if \p val found or \p false otherwise.
637 template <typename Q>
638 bool find( Q const& val ) const
640 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, key_comparator() );
643 /// Finds the key \p val using \p pred predicate for searching
645 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
646 but \p pred is used for key comparing.
647 \p Less functor has the interface like \p std::less.
648 \p pred must imply the same element order as the comparator used for building the list.
650 template <typename Q, typename Less>
651 bool find_with( Q const& val, Less pred ) const
653 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>() );
656 /// Finds the key \p val and return the item found
657 /** \anchor cds_intrusive_MichaelList_rcu_get
658 The function searches the item with key equal to \p val and returns the pointer to item found.
659 If \p val is not found it returns \p nullptr.
661 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
663 RCU should be locked before call of this function.
664 Returned item is valid only while RCU is locked:
666 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
671 ord_list::rcu_lock lock;
673 foo * pVal = theList.get( 5 );
678 // Unlock RCU by rcu_lock destructor
679 // pVal can be retired by disposer at any time after RCU has been unlocked
683 template <typename Q>
684 value_type * get( Q const& val ) const
686 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), val, key_comparator());
689 /// Finds the key \p val and return the item found
691 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
692 but \p pred is used for comparing the keys.
694 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
696 \p pred must imply the same element order as the comparator used for building the list.
698 template <typename Q, typename Less>
699 value_type * get_with( Q const& val, Less pred ) const
701 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>());
704 /// Clears the list using default disposer
706 The function clears the list using default (provided in class template) disposer functor.
708 RCU \p synchronize method can be called.
709 Note that depending on RCU type used the \ref disposer invocation can be deferred.
711 The function can throw cds::urcu::rcu_deadlock exception if an deadlock is encountered and
712 deadlock checking policy is opt::v::rcu_throw_deadlock.
717 check_deadlock_policy::check();
719 marked_node_ptr pHead;
723 pHead = m_pHead.load(memory_model::memory_order_consume);
726 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
727 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
729 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
734 dispose_node( pHead.ptr() );
739 /// Check if the list is empty
742 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
745 /// Returns list's item count
747 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
748 this function always returns 0.
750 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
751 is empty. To check list emptyness use \ref empty() method.
755 return m_ItemCounter.value();
760 // split-list support
761 bool insert_aux_node( node_type * pNode )
763 return insert_aux_node( m_pHead, pNode );
766 // split-list support
767 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
769 assert( pNode != nullptr );
771 // Hack: convert node_type to value_type.
772 // In principle, auxiliary node can be non-reducible to value_type
773 // We assume that comparator can correctly distinguish between aux and regular node.
774 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
777 bool insert_at( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
779 link_checker::is_empty( node_traits::to_node_ptr( val ) );
784 if ( search( refHead, val, pos, key_comparator() ) )
787 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
793 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
797 template <typename Func>
798 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
800 link_checker::is_empty( node_traits::to_node_ptr( val ) );
805 if ( search( refHead, val, pos, key_comparator() ) )
808 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
815 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
819 iterator insert_at_( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
822 if ( insert_at( refHead, val, false ))
823 return iterator( node_traits::to_node_ptr( val ));
827 template <typename Func>
828 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
834 if ( search( refHead, val, pos, key_comparator() ) ) {
835 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
837 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
838 return std::make_pair( iterator( pos.pCur ), false );
841 link_checker::is_empty( node_traits::to_node_ptr( val ) );
843 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
845 func( true, val , val );
846 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
849 // clear the next field
850 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
855 template <typename Func>
856 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
859 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func, false );
860 return std::make_pair( ret.first != end(), ret.second );
863 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
867 check_deadlock_policy::check();
872 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
874 if ( !unlink_node( pos )) {
881 dispose_node( pos.pCur );
886 template <typename Q, typename Compare, typename Func>
887 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
890 check_deadlock_policy::check();
895 if ( !search( refHead, val, pos, cmp ) )
897 if ( !unlink_node( pos )) {
903 f( *node_traits::to_value_ptr( *pos.pCur ) );
905 dispose_node( pos.pCur );
910 template <typename Q, typename Compare, typename Func>
911 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
914 return erase_at( refHead, val, cmp, f, pos );
917 template <typename Q, typename Compare>
918 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
921 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
924 template <typename Q, typename Compare >
925 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
929 assert( gc::is_locked() ) ; // RCU must be locked!!!
932 if ( !search( refHead, val, pos, cmp ) )
934 if ( !unlink_node( pos )) {
940 return node_traits::to_value_ptr( pos.pCur );
944 template <typename Q, typename Compare, typename Func>
945 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
950 if ( search( refHead, val, pos, cmp ) ) {
951 assert( pos.pCur != nullptr );
952 f( *node_traits::to_value_ptr( *pos.pCur ), val );
958 template <typename Q, typename Compare>
959 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
962 return find_at_( refHead, val, cmp ) != end();
965 template <typename Q, typename Compare>
966 value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
968 value_type * pFound = nullptr;
969 return find_at( refHead, val, cmp,
970 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
974 template <typename Q, typename Compare>
975 const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
977 assert( gc::is_locked() );
980 if ( search( refHead, val, pos, cmp ) ) {
981 assert( pos.pCur != nullptr );
982 return const_iterator( pos.pCur );
992 template <typename Q, typename Compare>
993 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp ) const
995 // RCU lock should be locked!!!
996 assert( gc::is_locked() );
998 atomic_node_ptr * pPrev;
999 marked_node_ptr pNext;
1000 marked_node_ptr pCur;
1006 pCur = pPrev->load(memory_model::memory_order_acquire);
1010 if ( !pCur.ptr() ) {
1012 pos.pCur = pCur.ptr();
1013 pos.pNext = pNext.ptr();
1017 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1019 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
1020 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)
1021 || pNext.bits() != 0 ) // pNext contains deletion mark for pCur
1023 // if pCur is marked as deleted (pNext.bits() != 0)
1024 // we wait for physical removal.
1025 // Helping technique is not suitable for RCU since it requires
1026 // that the RCU should be in unlocking state.
1031 assert( pCur.ptr() != nullptr );
1032 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1035 pos.pCur = pCur.ptr();
1036 pos.pNext = pNext.ptr();
1039 pPrev = &( pCur->m_pNext );
1046 }} // namespace cds::intrusive
1048 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H