3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_RCU_H
4 #define __CDS_INTRUSIVE_MICHAEL_LIST_RCU_H
6 #include <cds/intrusive/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 <CDS_DECL_OPTIONS7>
83 struct rebind_options {
87 , typename cds::opt::make_options< options, CDS_OPTIONS7>::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 # ifndef CDS_CXX11_LAMBDA_SUPPORT
111 struct empty_erase_functor {
112 void operator()( value_type const & item )
120 : pFound(null_ptr<value_type *>())
123 template <typename Q>
124 void operator()( value_type& item, Q& val )
132 static void clear_links( node_type * pNode )
134 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
137 struct clear_and_dispose {
138 void operator()( value_type * p )
140 assert( p != null_ptr<value_type *>() );
141 clear_links( node_traits::to_node_ptr(p));
148 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
153 static void dispose_node( node_type * pNode )
156 assert( !gc::is_locked() );
158 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
161 bool link_node( node_type * pNode, position& pos )
163 assert( pNode != null_ptr<node_type *>() );
164 link_checker::is_empty( pNode );
166 marked_node_ptr p( pos.pCur );
167 pNode->m_pNext.store( p, memory_model::memory_order_relaxed );
168 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
171 bool unlink_node( position& pos )
173 // Mark the node (logical deleting)
174 marked_node_ptr next(pos.pNext, 0);
175 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed )) {
176 marked_node_ptr cur(pos.pCur);
177 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
180 CDS_VERIFY( pos.pCur->m_pNext.compare_exchange_strong( next, next ^ 1, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
188 template <bool IsConst>
191 friend class MichaelList;
192 value_type * m_pNode;
197 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
198 m_pNode = p ? node_traits::to_value_ptr(p) : null_ptr<value_type *>();
203 explicit iterator_type( node_type * pNode)
206 m_pNode = node_traits::to_value_ptr( *pNode );
208 m_pNode = null_ptr<value_type *>();
210 explicit iterator_type( atomic_node_ptr const& refNode)
212 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
213 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : null_ptr<value_type *>();
217 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
218 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
221 : m_pNode(null_ptr<value_type *>())
224 iterator_type( const iterator_type& src )
225 : m_pNode( src.m_pNode )
228 value_ptr operator ->() const
233 value_ref operator *() const
235 assert( m_pNode != null_ptr<value_type *>() );
240 iterator_type& operator ++()
247 iterator_type operator ++(int)
249 iterator_type i(*this);
254 iterator_type& operator = (const iterator_type& src)
256 m_pNode = src.m_pNode;
261 bool operator ==(iterator_type<C> const& i ) const
263 return m_pNode == i.m_pNode;
266 bool operator !=(iterator_type<C> const& i ) const
268 return m_pNode != i.m_pNode;
275 typedef iterator_type<false> iterator;
276 /// Const forward iterator
277 typedef iterator_type<true> const_iterator;
279 /// Returns a forward iterator addressing the first element in a list
281 For empty list \code begin() == end() \endcode
285 return iterator( m_pHead );
288 /// Returns an iterator that addresses the location succeeding the last element in a list
290 Do not use the value returned by <tt>end</tt> function to access any item.
291 Internally, <tt>end</tt> returning value equals to \p NULL.
293 The returned value can be used only to control reaching the end of the list.
294 For empty list \code begin() == end() \endcode
301 /// Returns a forward const iterator addressing the first element in a list
302 const_iterator begin() const
304 return const_iterator(m_pHead );
306 /// Returns a forward const iterator addressing the first element in a list
307 const_iterator cbegin()
309 return const_iterator(m_pHead );
312 /// Returns an const iterator that addresses the location succeeding the last element in a list
313 const_iterator end() const
315 return const_iterator();
317 /// Returns an const iterator that addresses the location succeeding the last element in a list
318 const_iterator cend()
320 return const_iterator();
324 /// Default constructor initializes empty list
326 : m_pHead( null_ptr<node_type *>())
328 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
339 The function inserts \p val in the list if the list does not contain
340 an item with key equal to \p val.
342 The function makes RCU lock internally.
344 Returns \p true if \p val is linked into the list, \p false otherwise.
346 bool insert( value_type& val )
348 return insert_at( m_pHead, val );
353 This function is intended for derived non-intrusive containers.
355 The function allows to split new item creating into two part:
356 - create item with key only
357 - insert new item into the list
358 - if inserting is success, calls \p f functor to initialize value-field of \p val.
360 The functor signature is:
362 void func( value_type& val );
364 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
365 \p val no any other changes could be made on this list's item by concurrent threads.
366 The user-defined functor is called only if the inserting is success and may be passed by reference
367 using <tt>boost::ref</tt>.
369 The function makes RCU lock internally.
371 template <typename Func>
372 bool insert( value_type& val, Func f )
374 return insert_at( m_pHead, val, f );
377 /// Ensures that the \p item exists in the list
379 The operation performs inserting or changing data with lock-free manner.
381 If the item \p val not found in the list, then \p val is inserted into the list.
382 Otherwise, the functor \p func is called with item found.
383 The functor signature is:
386 void operator()( bool bNew, value_type& item, value_type& val );
390 - \p bNew - \p true if the item has been inserted, \p false otherwise
391 - \p item - item of the list
392 - \p val - argument \p val passed into the \p ensure function
393 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
394 refer to the same thing.
396 The functor may change non-key fields of the \p item; however, \p func must guarantee
397 that during changing no any other modifications could be made on this item by concurrent threads.
399 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
401 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
402 \p second is true if new item has been added or \p false if the item with \p key
403 already is in the list.
405 The function makes RCU lock internally.
408 template <typename Func>
409 std::pair<bool, bool> ensure( value_type& val, Func func )
411 return ensure_at( m_pHead, val, func );
414 /// Unlinks the item \p val from the list
416 The function searches the item \p val in the list and unlink it from the list
417 if it is found and it is equal to \p val.
419 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
420 and deletes the item found. \p unlink finds an item by key and deletes it
421 only if \p val is an item of that list, i.e. the pointer to item found
422 is equal to <tt> &val </tt>.
424 The function returns \p true if success and \p false otherwise.
426 RCU \p synchronize method can be called.
427 Note that depending on RCU type used the \ref disposer call can be deferred.
429 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
430 deadlock checking policy is opt::v::rcu_throw_deadlock.
432 bool unlink( value_type& val )
434 return unlink_at( m_pHead, val );
437 /// Deletes the item from the list
438 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
439 The function searches an item with key equal to \p val in the list,
440 unlinks it from the list, and returns \p true.
441 If the item with the key equal to \p val is not found the function return \p false.
443 RCU \p synchronize method can be called.
444 Note that depending on RCU type used the \ref disposer call can be deferred.
446 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
447 the deadlock checking policy is opt::v::rcu_throw_deadlock.
449 template <typename Q>
450 bool erase( Q const& val )
452 return erase_at( m_pHead, val, key_comparator() );
455 /// Deletes the item from the list using \p pred predicate for searching
457 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
458 but \p pred is used for key comparing.
459 \p Less functor has the interface like \p std::less.
460 \p pred must imply the same element order as the comparator used for building the list.
462 template <typename Q, typename Less>
463 bool erase_with( Q const& val, Less pred )
465 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
468 /// Deletes the item from the list
469 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
470 The function searches an item with key equal to \p val in the list,
471 call \p func functor with item found, unlinks it from the list, and returns \p true.
472 The \p Func interface is
475 void operator()( value_type const& item );
478 The functor may be passed by reference using <tt>boost:ref</tt>
480 If the item with the key equal to \p val is not found the function return \p false.
482 RCU \p synchronize method can be called.
483 Note that depending on RCU type used the \ref disposer call can be deferred.
485 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
486 the deadlock checking policy is opt::v::rcu_throw_deadlock.
488 template <typename Q, typename Func>
489 bool erase( Q const& val, Func func )
491 return erase_at( m_pHead, val, key_comparator(), func );
494 /// Deletes the item from the list using \p pred predicate for searching
496 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
497 but \p pred is used for key comparing.
498 \p Less functor has the interface like \p std::less.
499 \p pred must imply the same element order as the comparator used for building the list.
501 template <typename Q, typename Less, typename Func>
502 bool erase_with( Q const& val, Less pred, Func func )
504 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), func );
507 /// Extracts an item from the list
509 @anchor cds_intrusive_MichaelList_rcu_extract
510 The function searches an item with key equal to \p val in the list,
511 unlinks it from the list, and returns pointer to an item found in \p dest parameter.
512 If the item with the key equal to \p val is not found the function returns \p false,
515 @note The function does NOT call RCU read-side lock or synchronization,
516 and does NOT dispose the item found. It just excludes the item from the list
517 and returns a pointer to item found.
518 You should lock RCU before calling this function, and you should manually release
519 \p dest exempt pointer outside the RCU lock before reusing the pointer.
522 #include <cds/urcu/general_buffered.h>
523 #include <cds/intrusive/michael_list_rcu.h>
525 typedef cds::urcu::gc< general_buffered<> > rcu;
526 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
528 rcu_michael_list theList;
531 rcu_michael_list::exempt_ptr p1;
533 // first, we should lock RCU
536 // Now, you can apply extract function
537 // Note that you must not delete the item found inside the RCU lock
538 if ( theList.extract( p1, 10 )) {
539 // do something with p1
544 // We may safely release p1 here
545 // release() passes the pointer to RCU reclamation cycle:
546 // it invokes RCU retire_ptr function with the disposer you provided for the list.
550 template <typename Q>
551 bool extract( exempt_ptr& dest, Q const& val )
553 dest = extract_at( m_pHead, val, key_comparator() );
554 return !dest.empty();
557 /// Extracts an item from the list using \p pred predicate for searching
559 This function is the analog for \ref cds_intrusive_MichaelList_rcu_extract "extract(exempt_ptr&, Q const&)".
561 The \p pred is a predicate used for key comparing.
562 \p Less has the interface like \p std::less.
563 \p pred must imply the same element order as \ref key_comparator.
565 template <typename Q, typename Less>
566 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
568 dest = extract_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
569 return !dest.empty();
572 /// Find the key \p val
573 /** \anchor cds_intrusive_MichaelList_rcu_find_func
574 The function searches the item with key equal to \p val
575 and calls the functor \p f for item found.
576 The interface of \p Func functor is:
579 void operator()( value_type& item, Q& val );
582 where \p item is the item found, \p val is the <tt>find</tt> function argument.
584 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
586 The functor can change non-key fields of \p item.
587 The function \p find does not serialize simultaneous access to the list \p item. If such access is
588 possible you must provide your own synchronization schema to exclude unsafe item modifications.
590 The function makes RCU lock internally.
592 The function returns \p true if \p val is found, \p false otherwise.
594 template <typename Q, typename Func>
595 bool find( Q& val, Func f ) const
597 return find_at( const_cast<atomic_node_ptr&>(m_pHead), val, key_comparator(), f );
600 /// Finds the key \p val using \p pred predicate for searching
602 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_func "find(Q&, Func)"
603 but \p pred is used for key comparing.
604 \p Less functor has the interface like \p std::less.
605 \p pred must imply the same element order as the comparator used for building the list.
607 template <typename Q, typename Less, typename Func>
608 bool find_with( Q& val, Less pred, Func f ) const
610 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
613 /// Find the key \p val
614 /** \anchor cds_intrusive_MichaelList_rcu_find_cfunc
615 The function searches the item with key equal to \p val
616 and calls the functor \p f for item found.
617 The interface of \p Func functor is:
620 void operator()( value_type& item, Q const& val );
623 where \p item is the item found, \p val is the <tt>find</tt> function argument.
625 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
627 The functor can change non-key fields of \p item.
628 The function \p find does not serialize simultaneous access to the list \p item. If such access is
629 possible you must provide your own synchronization schema to exclude unsafe item modifications.
631 The function makes RCU lock internally.
633 The function returns \p true if \p val is found, \p false otherwise.
635 template <typename Q, typename Func>
636 bool find( Q const& val, Func f ) const
638 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, key_comparator(), f );
641 /// Finds the key \p val using \p pred predicate for searching
643 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_cfunc "find(Q const&, Func)"
644 but \p pred is used for key comparing.
645 \p Less functor has the interface like \p std::less.
646 \p pred must imply the same element order as the comparator used for building the list.
648 template <typename Q, typename Less, typename Func>
649 bool find_with( Q const& val, Less pred, Func f ) const
651 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
654 /// Find the key \p val
655 /** \anchor cds_intrusive_MichaelList_rcu_find_val
656 The function searches the item with key equal to \p val
657 and returns \p true if \p val found or \p false otherwise.
659 template <typename Q>
660 bool find( Q const& val ) const
662 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, key_comparator() );
665 /// Finds the key \p val using \p pred predicate for searching
667 The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)"
668 but \p pred is used for key comparing.
669 \p Less functor has the interface like \p std::less.
670 \p pred must imply the same element order as the comparator used for building the list.
672 template <typename Q, typename Less>
673 bool find_with( Q const& val, Less pred ) const
675 return find_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>() );
678 /// Finds the key \p val and return the item found
679 /** \anchor cds_intrusive_MichaelList_rcu_get
680 The function searches the item with key equal to \p val and returns the pointer to item found.
681 If \p val is not found it returns \p NULL.
683 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
685 RCU should be locked before call of this function.
686 Returned item is valid only while RCU is locked:
688 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
693 ord_list::rcu_lock lock;
695 foo * pVal = theList.get( 5 );
700 // Unlock RCU by rcu_lock destructor
701 // pVal can be retired by disposer at any time after RCU has been unlocked
705 template <typename Q>
706 value_type * get( Q const& val ) const
708 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), val, key_comparator());
711 /// Finds the key \p val and return the item found
713 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
714 but \p pred is used for comparing the keys.
716 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
718 \p pred must imply the same element order as the comparator used for building the list.
720 template <typename Q, typename Less>
721 value_type * get_with( Q const& val, Less pred ) const
723 return get_at( const_cast<atomic_node_ptr&>( m_pHead ), val, cds::opt::details::make_comparator_from_less<Less>());
726 /// Clears the list using default disposer
728 The function clears the list using default (provided in class template) disposer functor.
730 RCU \p synchronize method can be called.
731 Note that depending on RCU type used the \ref disposer invocation can be deferred.
733 The function can throw cds::urcu::rcu_deadlock exception if an deadlock is encountered and
734 deadlock checking policy is opt::v::rcu_throw_deadlock.
739 check_deadlock_policy::check();
741 marked_node_ptr pHead;
745 pHead = m_pHead.load(memory_model::memory_order_consume);
748 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
749 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
751 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
756 dispose_node( pHead.ptr() );
761 /// Check if the list is empty
764 return m_pHead.load(memory_model::memory_order_relaxed).all() == null_ptr<node_type *>();
767 /// Returns list's item count
769 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
770 this function always returns 0.
772 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
773 is empty. To check list emptyness use \ref empty() method.
777 return m_ItemCounter.value();
782 // split-list support
783 bool insert_aux_node( node_type * pNode )
785 return insert_aux_node( m_pHead, pNode );
788 // split-list support
789 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
791 assert( pNode != null_ptr<node_type *>() );
793 // Hack: convert node_type to value_type.
794 // In principle, auxiliary node can be non-reducible to value_type
795 // We assume that comparator can correctly distinguish between aux and regular node.
796 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
799 bool insert_at( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
801 link_checker::is_empty( node_traits::to_node_ptr( val ) );
806 if ( search( refHead, val, pos, key_comparator() ) )
809 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 template <typename Func>
820 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
822 link_checker::is_empty( node_traits::to_node_ptr( val ) );
827 if ( search( refHead, val, pos, key_comparator() ) )
830 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
831 cds::unref(f)( val );
837 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
841 iterator insert_at_( atomic_node_ptr& refHead, value_type& val, bool bLock = true )
844 if ( insert_at( refHead, val, false ))
845 return iterator( node_traits::to_node_ptr( val ));
849 template <typename Func>
850 std::pair<iterator, bool> ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
856 if ( search( refHead, val, pos, key_comparator() ) ) {
857 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
859 unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ), val );
860 return std::make_pair( iterator( pos.pCur ), false );
863 link_checker::is_empty( node_traits::to_node_ptr( val ) );
865 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
867 unref(func)( true, val , val );
868 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
871 // clear the next field
872 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
877 template <typename Func>
878 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bLock = true )
881 std::pair<iterator, bool> ret = ensure_at_( refHead, val, func, false );
882 return std::make_pair( ret.first != end(), ret.second );
885 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
889 check_deadlock_policy::check();
894 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
896 if ( !unlink_node( pos )) {
903 dispose_node( pos.pCur );
908 template <typename Q, typename Compare, typename Func>
909 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f, position& pos )
912 check_deadlock_policy::check();
917 if ( !search( refHead, val, pos, cmp ) )
919 if ( !unlink_node( pos )) {
925 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
927 dispose_node( pos.pCur );
932 template <typename Q, typename Compare, typename Func>
933 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
936 return erase_at( refHead, val, cmp, f, pos );
939 template <typename Q, typename Compare>
940 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
943 # ifdef CDS_CXX11_LAMBDA_SUPPORT
944 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
946 return erase_at( refHead, val, cmp, empty_erase_functor(), pos );
950 template <typename Q, typename Compare >
951 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
955 assert( gc::is_locked() ) ; // RCU must be locked!!!
958 if ( !search( refHead, val, pos, cmp ) )
959 return null_ptr<value_type *>();
960 if ( !unlink_node( pos )) {
966 return node_traits::to_value_ptr( pos.pCur );
970 template <typename Q, typename Compare, typename Func>
971 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
976 if ( search( refHead, val, pos, cmp ) ) {
977 assert( pos.pCur != null_ptr<node_type *>() );
978 unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
984 template <typename Q, typename Compare>
985 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
988 return find_at_( refHead, val, cmp ) != end();
991 template <typename Q, typename Compare>
992 value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
994 # ifdef CDS_CXX11_LAMBDA_SUPPORT
995 value_type * pFound = null_ptr<value_type *>();
996 return find_at( refHead, val, cmp,
997 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
998 ? pFound : null_ptr<value_type *>();
1001 return find_at( refHead, val, cmp, cds::ref(gf) )
1002 ? gf.pFound : null_ptr<value_type *>();
1006 template <typename Q, typename Compare>
1007 const_iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp ) const
1009 assert( gc::is_locked() );
1012 if ( search( refHead, val, pos, cmp ) ) {
1013 assert( pos.pCur != null_ptr<node_type *>() );
1014 return const_iterator( pos.pCur );
1024 template <typename Q, typename Compare>
1025 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp ) const
1027 // RCU lock should be locked!!!
1028 assert( gc::is_locked() );
1030 atomic_node_ptr * pPrev;
1031 marked_node_ptr pNext;
1032 marked_node_ptr pCur;
1038 pCur = pPrev->load(memory_model::memory_order_acquire);
1039 pNext = null_ptr<node_type *>();
1042 if ( !pCur.ptr() ) {
1044 pos.pCur = pCur.ptr();
1045 pos.pNext = pNext.ptr();
1049 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1051 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
1052 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)
1053 || pNext.bits() != 0 ) // pNext contains deletion mark for pCur
1055 // if pCur is marked as deleted (pNext.bits() != 0)
1056 // we wait for physical removal.
1057 // Helping technique is not suitable for RCU since it requires
1058 // that the RCU should be in unlocking state.
1063 assert( pCur.ptr() != null_ptr<node_type *>() );
1064 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1067 pos.pCur = pCur.ptr();
1068 pos.pNext = pNext.ptr();
1071 pPrev = &( pCur->m_pNext );
1078 }} // namespace cds::intrusive
1080 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_NOGC_H