2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
32 #define CDSLIB_INTRUSIVE_MICHAEL_LIST_RCU_H
34 #include <cds/intrusive/details/michael_list_base.h>
35 #include <cds/urcu/details/check_deadlock.h>
36 #include <cds/details/binary_functor_wrapper.h>
37 #include <cds/details/make_const_type.h>
38 #include <cds/urcu/exempt_ptr.h>
39 #include <cds/urcu/raw_ptr.h>
40 #include <cds/intrusive/details/raw_ptr_disposer.h>
42 namespace cds { namespace intrusive {
45 namespace michael_list {
47 /// Node specialization for uRCU
48 template <class RCU, typename Tag>
49 struct node< cds::urcu::gc< RCU >, Tag >
51 typedef cds::urcu::gc< RCU > gc; ///< Garbage collector
52 typedef Tag tag; ///< tag
54 typedef cds::details::marked_ptr<node, 3> marked_ptr; ///< marked pointer
55 typedef typename gc::template atomic_marked_ptr<marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
57 atomic_marked_ptr m_pNext; ///< pointer to the next node in the container
58 node * m_pDelChain; ///< Deleted node chain (local for a thread)
60 CDS_CONSTEXPR node() CDS_NOEXCEPT
62 , m_pDelChain( nullptr )
65 } // namespace michael_list
68 /// Michael's lock-free ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
69 /** @ingroup cds_intrusive_list
70 \anchor cds_intrusive_MichaelList_rcu
72 Usually, ordered single-linked list is used as a building block for the hash table implementation.
73 The complexity of searching is <tt>O(N)</tt>.
76 - \p RCU - one of \ref cds_urcu_gc "RCU type"
77 - \p T - type to be stored in the list; the type \p T should be based on (or has a member of type)
78 cds::intrusive::micheal_list::node
79 - \p Traits - type traits. See \p michael_list::traits for explanation. It is possible to declare option-based
80 list with \p cds::intrusive::michael_list::make_traits metafunction,
81 see \ref cds_intrusive_MichaelList_hp "here" for explanations.
84 Before including <tt><cds/intrusive/michael_list_rcu.h></tt> you should include appropriate RCU header file,
85 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
86 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
88 #include <cds/urcu/general_buffered.h>
89 #include <cds/intrusive/michael_list_rcu.h>
91 // Now, you can declare Michael's list for type Foo and default traits:
92 typedef cds::intrusive::MichaelList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
95 template < typename RCU, typename T,
96 #ifdef CDS_DOXYGEN_INVOKED
97 class Traits = michael_list::traits
102 class MichaelList<cds::urcu::gc<RCU>, T, Traits>
105 typedef T value_type; ///< type of value stored in the list
106 typedef Traits traits; ///< Traits template parameter
108 typedef typename traits::hook hook; ///< hook type
109 typedef typename hook::node_type node_type; ///< node type
111 # ifdef CDS_DOXYGEN_INVOKED
112 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
114 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
117 typedef typename traits::disposer disposer; ///< disposer used
118 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
119 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
121 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
122 typedef typename traits::back_off back_off; ///< back-off strategy
123 typedef typename traits::item_counter item_counter; ///< Item counting policy used
124 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
125 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
126 typedef typename traits::stat stat; ///< Internal statistics
128 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
129 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
132 // Rebind traits (split-list support)
133 template <typename... Options>
134 struct rebind_traits {
138 , typename cds::opt::make_options< traits, Options...>::type
143 template <typename Stat>
144 using select_stat_wrapper = michael_list::select_stat_wrapper< Stat >;
148 typedef typename node_type::marked_ptr marked_node_ptr; ///< Marked node pointer
149 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
150 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
152 atomic_node_ptr m_pHead; ///< Head pointer
153 item_counter m_ItemCounter; ///< Item counter
154 stat m_Stat; ///< Internal statistics
164 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
166 static void clear_links( node_type * pNode )
168 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release );
169 pNode->m_pDelChain = nullptr;
172 struct clear_and_dispose {
173 void operator()( value_type * p )
175 assert( p != nullptr );
176 clear_links( node_traits::to_node_ptr(p));
181 static void dispose_node( node_type * pNode )
184 assert( !gc::is_locked() );
186 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
189 static void dispose_chain( node_type * pChain )
192 assert( !gc::is_locked() );
194 auto f = [&pChain]() -> cds::urcu::retired_ptr {
195 node_type * p = pChain;
197 pChain = p->m_pDelChain;
198 return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
200 return cds::urcu::make_retired_ptr<clear_and_dispose>( static_cast<value_type *>(nullptr));
202 gc::batch_retire(std::ref(f));
206 /// Position pointer for item search
208 atomic_node_ptr * pPrev ; ///< Previous node
209 node_type * pCur ; ///< Current node
210 node_type * pNext ; ///< Next node
212 atomic_node_ptr& refHead;
213 node_type * pDelChain; ///< Head of deleted node chain
215 position( atomic_node_ptr& head )
217 , pDelChain( nullptr )
222 dispose_chain( pDelChain );
229 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
233 struct chain_disposer {
234 void operator()( node_type * pChain ) const
236 dispose_chain( pChain );
239 typedef cds::intrusive::details::raw_ptr_disposer< gc, node_type, chain_disposer> raw_ptr_disposer;
243 /// Result of \p get(), \p get_with() functions - pointer to the node found
244 typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr;
249 bool link_node( node_type * pNode, position& pos )
251 assert( pNode != nullptr );
252 link_checker::is_empty( pNode );
254 marked_node_ptr p( pos.pCur );
255 pNode->m_pNext.store( p, memory_model::memory_order_release );
256 if ( cds_likely( pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )))
259 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
263 static void link_to_remove_chain( position& pos, node_type * pDel )
265 assert( pDel->m_pDelChain == nullptr );
267 pDel->m_pDelChain = pos.pDelChain;
268 pos.pDelChain = pDel;
271 bool unlink_node( position& pos, erase_node_mask nMask )
273 assert(gc::is_locked() );
275 // Mark the node (logical deletion)
276 marked_node_ptr next(pos.pNext, 0);
278 if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
280 // Try physical removal - fast path
281 marked_node_ptr cur(pos.pCur);
282 if ( cds_likely( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
283 if ( nMask == erase_mask )
284 link_to_remove_chain( pos, pos.pCur );
288 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
298 template <bool IsConst>
301 friend class MichaelList;
302 value_type * m_pNode;
307 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
308 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
313 explicit iterator_type( node_type * pNode)
316 m_pNode = node_traits::to_value_ptr( *pNode );
320 explicit iterator_type( atomic_node_ptr const& refNode)
322 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
323 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
327 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
328 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
334 iterator_type( const iterator_type& src )
335 : m_pNode( src.m_pNode )
338 value_ptr operator ->() const
343 value_ref operator *() const
345 assert( m_pNode != nullptr );
350 iterator_type& operator ++()
357 iterator_type operator ++(int)
359 iterator_type i(*this);
364 iterator_type& operator = (const iterator_type& src)
366 m_pNode = src.m_pNode;
371 bool operator ==(iterator_type<C> const& i ) const
373 return m_pNode == i.m_pNode;
376 bool operator !=(iterator_type<C> const& i ) const
378 return m_pNode != i.m_pNode;
384 ///@name Forward iterators (thread-safe only under RCU lock)
388 You may safely use iterators in multi-threaded environment only under RCU lock.
389 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
391 typedef iterator_type<false> iterator;
393 /// Const forward iterator
394 typedef iterator_type<true> const_iterator;
396 /// Returns a forward iterator addressing the first element in a list
398 For empty list \code begin() == end() \endcode
402 return iterator( m_pHead );
405 /// Returns an iterator that addresses the location succeeding the last element in a list
407 Do not use the value returned by <tt>end</tt> function to access any item.
408 Internally, <tt>end</tt> returning value equals to \p nullptr.
410 The returned value can be used only to control reaching the end of the list.
411 For empty list \code begin() == end() \endcode
418 /// Returns a forward const iterator addressing the first element in a list
419 const_iterator begin() const
421 return const_iterator(m_pHead );
423 /// Returns a forward const iterator addressing the first element in a list
424 const_iterator cbegin() const
426 return const_iterator(m_pHead );
429 /// Returns an const iterator that addresses the location succeeding the last element in a list
430 const_iterator end() const
432 return const_iterator();
434 /// Returns an const iterator that addresses the location succeeding the last element in a list
435 const_iterator cend() const
437 return const_iterator();
442 /// Default constructor initializes empty list
446 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
450 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
451 explicit MichaelList( Stat& st )
465 The function inserts \p val in the list if the list does not contain
466 an item with key equal to \p val.
468 The function makes RCU lock internally.
470 Returns \p true if \p val is linked into the list, \p false otherwise.
472 bool insert( value_type& val )
474 return insert_at( m_pHead, val );
479 This function is intended for derived non-intrusive containers.
481 The function allows to split new item creating into two part:
482 - create item with key only
483 - insert new item into the list
484 - if inserting is success, calls \p f functor to initialize value-field of \p val.
486 The functor signature is:
488 void func( value_type& val );
490 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
491 \p val no any other changes could be made on this list's item by concurrent threads.
492 The user-defined functor is called only if the inserting is success.
494 The function makes RCU lock internally.
496 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
498 template <typename Func>
499 bool insert( value_type& val, Func f )
501 return insert_at( m_pHead, val, f );
506 The operation performs inserting or changing data with lock-free manner.
508 If the item \p val not found in the list, then \p val is inserted into the list
509 iff \p bAllowInsert is \p true.
510 Otherwise, the functor \p func is called with item found.
511 The functor signature is:
514 void operator()( bool bNew, value_type& item, value_type& val );
518 - \p bNew - \p true if the item has been inserted, \p false otherwise
519 - \p item - item of the list
520 - \p val - argument \p val passed into the \p update() function
521 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
522 refer to the same thing.
524 The functor may change non-key fields of the \p item; however, \p func must guarantee
525 that during changing no any other modifications could be made on this item by concurrent threads.
527 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
528 \p second is \p true if new item has been added or \p false if the item with \p key
529 already is in the list.
531 The function makes RCU lock internally.
533 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
535 template <typename Func>
536 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
538 return update_at( m_pHead, val, func, bAllowInsert );
541 template <typename Func>
542 CDS_DEPRECATED("ensure() is deprecated, use update()")
543 std::pair<bool, bool> ensure( value_type& val, Func func )
545 return update( val, func, true );
549 /// Unlinks the item \p val from the list
551 The function searches the item \p val in the list and unlink it from the list
552 if it is found and it is equal to \p val.
554 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
555 and deletes the item found. \p %unlink() finds an item by key and deletes it
556 only if \p val is an item of that list, i.e. the pointer to the item found
557 is equal to <tt> &val </tt>.
559 The function returns \p true if success and \p false otherwise.
561 RCU \p synchronize method can be called.
562 Note that depending on RCU type used the \ref disposer call can be deferred.
564 \p disposer specified in \p Traits is called for unlinked item.
566 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
567 deadlock checking policy is opt::v::rcu_throw_deadlock.
569 bool unlink( value_type& val )
571 return unlink_at( m_pHead, val );
574 /// Deletes the item from the list
576 The function searches an item with key equal to \p key in the list,
577 unlinks it from the list, and returns \p true.
578 If the item with the key equal to \p key is not found the function return \p false.
580 RCU \p synchronize method can be called.
581 Note that depending on RCU type used the \ref disposer call can be deferred.
583 \p disposer specified in \p Traits is called for deleted item.
585 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
586 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
588 template <typename Q>
589 bool erase( Q const& key )
591 return erase_at( m_pHead, key, key_comparator() );
594 /// Deletes the item from the list using \p pred predicate for searching
596 The function is an analog of \p erase(Q const&)
597 but \p pred is used for key comparing.
598 \p Less functor has the interface like \p std::less.
599 \p pred must imply the same element order as the comparator used for building the list.
601 \p disposer specified in \p Traits is called for deleted item.
603 template <typename Q, typename Less>
604 bool erase_with( Q const& key, Less pred )
607 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
610 /// Deletes the item from the list
612 The function searches an item with key equal to \p key in the list,
613 call \p func functor with item found, unlinks it from the list, and returns \p true.
614 The \p Func interface is
617 void operator()( value_type const& item );
621 If the item with the key equal to \p key is not found the function return \p false.
623 RCU \p synchronize method can be called.
624 Note that depending on RCU type used the \ref disposer call can be deferred.
626 \p disposer specified in \p Traits is called for deleted item.
628 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
629 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
631 template <typename Q, typename Func>
632 bool erase( Q const& key, Func func )
634 return erase_at( m_pHead, key, key_comparator(), func );
637 /// Deletes the item from the list using \p pred predicate for searching
639 The function is an analog of \p erase(Q const&, Func)
640 but \p pred is used for key comparing.
641 \p Less functor has the interface like \p std::less.
642 \p pred must imply the same element order as the comparator used for building the list.
644 \p disposer specified in \p Traits is called for deleted item.
646 template <typename Q, typename Less, typename Func>
647 bool erase_with( Q const& key, Less pred, Func func )
650 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
653 /// Extracts an item from the list
655 The function searches an item with key equal to \p key in the list,
656 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
657 If \p key is not found the function returns an empty \p exempt_ptr.
659 @note The function does NOT dispose the item found. It just unlinks the item from the list
660 and returns a pointer to item found.
661 You shouldn't lock RCU for current thread before calling this function, and you should manually release
662 the returned exempt pointer before reusing it.
665 #include <cds/urcu/general_buffered.h>
666 #include <cds/intrusive/michael_list_rcu.h>
668 typedef cds::urcu::gc< general_buffered<> > rcu;
669 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
671 rcu_michael_list theList;
674 rcu_michael_list::exempt_ptr p1;
676 // The RCU should NOT be locked when extract() is called!
677 assert( !rcu::is_locked() );
679 // You can call extract() function
680 p1 = theList.extract( 10 );
682 // do something with p1
686 // We may safely release p1 here
687 // release() passes the pointer to RCU reclamation cycle:
688 // it invokes RCU retire_ptr function with the disposer you provided for the list.
692 template <typename Q>
693 exempt_ptr extract( Q const& key )
695 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
698 /// Extracts an item from the list using \p pred predicate for searching
700 This function is the analog for \p extract(Q const&)
702 The \p pred is a predicate used for key comparing.
703 \p Less has the interface like \p std::less.
704 \p pred must imply the same element order as \ref key_comparator.
706 template <typename Q, typename Less>
707 exempt_ptr extract_with( Q const& key, Less pred )
710 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
713 /// Find the key \p val
715 The function searches the item with key equal to \p key
716 and calls the functor \p f for item found.
717 The interface of \p Func functor is:
720 void operator()( value_type& item, Q& key );
723 where \p item is the item found, \p key is the <tt>find</tt> function argument.
725 The functor can change non-key fields of \p item.
726 The function \p find does not serialize simultaneous access to the list \p item. If such access is
727 possible you must provide your own synchronization schema to exclude unsafe item modifications.
729 The function makes RCU lock internally.
731 The function returns \p true if \p val is found, \p false otherwise.
733 template <typename Q, typename Func>
734 bool find( Q& key, Func f )
736 return find_at( m_pHead, key, key_comparator(), f );
739 template <typename Q, typename Func>
740 bool find( Q const& key, Func f )
742 return find_at( m_pHead, key, key_comparator(), f );
746 /// Finds \p key using \p pred predicate for searching
748 The function is an analog of \p find(Q&, Func)
749 but \p pred is used for key comparing.
750 \p Less functor has the interface like \p std::less.
751 \p pred must imply the same element order as the comparator used for building the list.
753 template <typename Q, typename Less, typename Func>
754 bool find_with( Q& key, Less pred, Func f )
757 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
760 template <typename Q, typename Less, typename Func>
761 bool find_with( Q const& key, Less pred, Func f )
764 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
768 /// Checks whether the list contains \p key
770 The function searches the item with key equal to \p key
771 and returns \p true if it is found, and \p false otherwise.
773 template <typename Q>
774 bool contains( Q const& key )
776 return find_at( m_pHead, key, key_comparator() );
779 template <typename Q>
780 CDS_DEPRECATED("deprecated, use contains()")
781 bool find( Q const& key )
783 return contains( key );
787 /// Checks whether the map contains \p key using \p pred predicate for searching
789 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
790 \p Less functor has the interface like \p std::less.
791 \p Less must imply the same element order as the comparator used for building the list.
793 template <typename Q, typename Less>
794 bool contains( Q const& key, Less pred )
797 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
800 template <typename Q, typename Less>
801 CDS_DEPRECATED("deprecated, use contains()")
802 bool find_with( Q const& key, Less pred )
804 return contains( key, pred );
808 /// Finds \p key and return the item found
809 /** \anchor cds_intrusive_MichaelList_rcu_get
810 The function searches the item with key equal to \p key and returns the pointer to item found.
811 If \p key is not found it returns empty \p raw_ptr object.
813 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
815 RCU should be locked before call of this function.
816 Returned item is valid only while RCU is locked:
818 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
821 typename ord_list::raw_ptr rp;
824 ord_list::rcu_lock lock;
826 rp = theList.get( 5 );
831 // Unlock RCU by rcu_lock destructor
832 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
834 // You can manually release rp after RCU-locked section
838 template <typename Q>
839 raw_ptr get( Q const& key )
841 return get_at( m_pHead, key, key_comparator());
844 /// Finds \p key and return the item found
846 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
847 but \p pred is used for comparing the keys.
849 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
851 \p pred must imply the same element order as the comparator used for building the list.
853 template <typename Q, typename Less>
854 raw_ptr get_with( Q const& key, Less pred )
857 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
860 /// Clears the list using default disposer
862 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
864 RCU \p synchronize method can be called.
865 Note that depending on RCU type used the \ref disposer invocation can be deferred.
867 The function can throw \p cds::urcu::rcu_deadlock exception if a deadlock is encountered and
868 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
873 check_deadlock_policy::check();
875 marked_node_ptr pHead;
879 pHead = m_pHead.load(memory_model::memory_order_acquire);
882 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
883 if ( cds_unlikely( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed )))
885 if ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed )))
890 dispose_node( pHead.ptr() );
895 /// Check if the list is empty
898 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
901 /// Returns list's item count
903 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
904 this function always returns 0.
906 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
907 is empty. To check list emptyness use \p empty() method.
911 return m_ItemCounter.value();
914 /// Returns const reference to internal statistics
915 stat const& statistics() const
921 // split-list support
922 bool insert_aux_node( node_type * pNode )
924 return insert_aux_node( m_pHead, pNode );
927 // split-list support
928 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
930 assert( pNode != nullptr );
932 // Hack: convert node_type to value_type.
933 // In principle, auxiliary node can be non-reducible to value_type
934 // We assume that comparator can correctly distinguish between aux and regular node.
935 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
938 bool insert_at( atomic_node_ptr& refHead, value_type& val )
940 position pos( refHead );
943 return insert_at_locked( pos, val );
947 template <typename Func>
948 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
950 position pos( refHead );
955 if ( search( refHead, val, pos, key_comparator())) {
956 m_Stat.onInsertFailed();
960 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
963 m_Stat.onInsertSuccess();
968 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
969 m_Stat.onInsertRetry();
975 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
978 if ( insert_at_locked( refHead, val ))
979 return iterator( node_traits::to_node_ptr( val ));
983 template <typename Func>
984 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
986 position pos( refHead );
989 return update_at_locked( pos, val, func, bInsert );
993 template <typename Func>
994 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
996 position pos( refHead );
999 std::pair<iterator, bool> ret = update_at_locked( pos, val, func, bInsert );
1000 return std::make_pair( ret.first != end(), ret.second );
1004 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1006 position pos( refHead );
1008 check_deadlock_policy::check();
1013 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val ) {
1014 m_Stat.onEraseFailed();
1017 if ( !unlink_node( pos, erase_mask )) {
1019 m_Stat.onEraseRetry();
1025 m_Stat.onEraseSuccess();
1030 template <typename Q, typename Compare, typename Func>
1031 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
1034 check_deadlock_policy::check();
1040 if ( !search( pos.refHead, val, pos, cmp ) ) {
1041 m_Stat.onEraseFailed();
1045 // store pCur since it may be changed by unlink_node() slow path
1047 if ( !unlink_node( pos, erase_mask )) {
1049 m_Stat.onEraseRetry();
1054 f( *node_traits::to_value_ptr( pDel ) );
1056 m_Stat.onEraseSuccess();
1061 template <typename Q, typename Compare, typename Func>
1062 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
1064 position pos( refHead );
1065 return erase_at( pos, val, cmp, f );
1068 template <typename Q, typename Compare>
1069 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
1071 position pos( refHead );
1072 return erase_at( pos, val, cmp, [](value_type const&){} );
1075 template <typename Q, typename Compare >
1076 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1078 position pos( refHead );
1080 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
1082 node_type * pExtracted;
1086 if ( !search( refHead, val, pos, cmp )) {
1087 m_Stat.onEraseFailed();
1091 // store pCur since it may be changed by unlink_node() slow path
1092 pExtracted = pos.pCur;
1093 if ( !unlink_node( pos, extract_mask )) {
1095 m_Stat.onEraseRetry();
1100 value_type * pRet = node_traits::to_value_ptr( pExtracted );
1101 assert( pExtracted->m_pDelChain == nullptr );
1102 m_Stat.onEraseSuccess();
1108 template <typename Q, typename Compare, typename Func>
1109 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1111 position pos( refHead );
1115 if ( search( refHead, val, pos, cmp ) ) {
1116 assert( pos.pCur != nullptr );
1117 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1118 m_Stat.onFindSuccess();
1123 m_Stat.onFindFailed();
1127 template <typename Q, typename Compare>
1128 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1130 position pos( refHead );
1133 return find_at_locked( pos, val, cmp ) != cend();
1137 template <typename Q, typename Compare>
1138 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1140 // RCU should be locked!
1141 assert(gc::is_locked() );
1143 position pos( refHead );
1145 if ( search( refHead, val, pos, cmp )) {
1146 m_Stat.onFindSuccess();
1147 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1150 m_Stat.onFindFailed();
1151 return raw_ptr( raw_ptr_disposer( pos ));
1158 template <typename Q, typename Compare>
1159 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1161 // RCU lock should be locked!!!
1162 assert( gc::is_locked() );
1164 atomic_node_ptr * pPrev;
1165 marked_node_ptr pNext;
1166 marked_node_ptr pCur;
1172 pCur = pPrev->load(memory_model::memory_order_acquire);
1176 if ( !pCur.ptr() ) {
1179 pos.pNext = nullptr;
1183 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1185 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire) != pCur
1186 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire )))
1192 if ( pNext.bits() ) {
1193 // pCur is marked as deleted. Try to unlink it from the list
1194 if ( cds_likely( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
1195 if ( pNext.bits() == erase_mask )
1196 link_to_remove_chain( pos, pCur.ptr() );
1197 m_Stat.onHelpingSuccess();
1200 m_Stat.onHelpingFailed();
1204 assert( pCur.ptr() != nullptr );
1205 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1208 pos.pCur = pCur.ptr();
1209 pos.pNext = pNext.ptr();
1212 pPrev = &( pCur->m_pNext );
1220 bool insert_at_locked( position& pos, value_type& val )
1222 // RCU lock should be locked!!!
1223 assert( gc::is_locked() );
1226 if ( search( pos.refHead, val, pos, key_comparator() )) {
1227 m_Stat.onInsertFailed();
1231 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1233 m_Stat.onInsertSuccess();
1238 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1239 m_Stat.onInsertRetry();
1243 template <typename Func>
1244 std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
1246 // RCU should be locked!!!
1247 assert( gc::is_locked() );
1250 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1251 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1253 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1254 m_Stat.onUpdateExisting();
1255 return std::make_pair( iterator( pos.pCur ), false );
1259 m_Stat.onUpdateFailed();
1260 return std::make_pair( end(), false );
1263 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1265 func( true, val , val );
1266 m_Stat.onUpdateNew();
1267 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1270 // clear the next field
1271 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1272 m_Stat.onUpdateRetry();
1277 template <typename Q, typename Compare>
1278 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1280 assert( gc::is_locked() );
1282 if ( search( pos.refHead, val, pos, cmp ) ) {
1283 assert( pos.pCur != nullptr );
1284 m_Stat.onFindSuccess();
1285 return const_iterator( pos.pCur );
1288 m_Stat.onFindFailed();
1294 }} // namespace cds::intrusive
1296 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H