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
127 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
128 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
131 // Rebind traits (split-list support)
132 template <typename... Options>
133 struct rebind_traits {
137 , typename cds::opt::make_options< traits, Options...>::type
143 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Marked node pointer
144 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
145 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
147 atomic_node_ptr m_pHead ; ///< Head pointer
148 item_counter m_ItemCounter ; ///< Item counter
158 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
160 static void clear_links( node_type * pNode )
162 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release );
163 pNode->m_pDelChain = nullptr;
166 struct clear_and_dispose {
167 void operator()( value_type * p )
169 assert( p != nullptr );
170 clear_links( node_traits::to_node_ptr(p));
175 static void dispose_node( node_type * pNode )
178 assert( !gc::is_locked() );
180 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
183 static void dispose_chain( node_type * pChain )
186 assert( !gc::is_locked() );
188 auto f = [&pChain]() -> cds::urcu::retired_ptr {
189 node_type * p = pChain;
191 pChain = p->m_pDelChain;
192 return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
194 return cds::urcu::make_retired_ptr<clear_and_dispose>( static_cast<value_type *>(nullptr));
196 gc::batch_retire(std::ref(f));
200 /// Position pointer for item search
202 atomic_node_ptr * pPrev ; ///< Previous node
203 node_type * pCur ; ///< Current node
204 node_type * pNext ; ///< Next node
206 atomic_node_ptr& refHead;
207 node_type * pDelChain; ///< Head of deleted node chain
209 position( atomic_node_ptr& head )
211 , pDelChain( nullptr )
216 dispose_chain( pDelChain );
223 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node
227 struct chain_disposer {
228 void operator()( node_type * pChain ) const
230 dispose_chain( pChain );
233 typedef cds::intrusive::details::raw_ptr_disposer< gc, node_type, chain_disposer> raw_ptr_disposer;
237 /// Result of \p get(), \p get_with() functions - pointer to the node found
238 typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr;
243 bool link_node( node_type * pNode, position& pos )
245 assert( pNode != nullptr );
246 link_checker::is_empty( pNode );
248 marked_node_ptr p( pos.pCur );
249 pNode->m_pNext.store( p, memory_model::memory_order_release );
250 if ( cds_likely( pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )))
253 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
257 static void link_to_remove_chain( position& pos, node_type * pDel )
259 assert( pDel->m_pDelChain == nullptr );
261 pDel->m_pDelChain = pos.pDelChain;
262 pos.pDelChain = pDel;
265 bool unlink_node( position& pos, erase_node_mask nMask )
267 assert(gc::is_locked() );
269 // Mark the node (logical deletion)
270 marked_node_ptr next(pos.pNext, 0);
272 if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
274 // Try physical removal - fast path
275 marked_node_ptr cur(pos.pCur);
276 if ( cds_likely( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
277 if ( nMask == erase_mask )
278 link_to_remove_chain( pos, pos.pCur );
282 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
292 template <bool IsConst>
295 friend class MichaelList;
296 value_type * m_pNode;
301 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
302 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
307 explicit iterator_type( node_type * pNode)
310 m_pNode = node_traits::to_value_ptr( *pNode );
314 explicit iterator_type( atomic_node_ptr const& refNode)
316 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
317 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
321 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
322 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
328 iterator_type( const iterator_type& src )
329 : m_pNode( src.m_pNode )
332 value_ptr operator ->() const
337 value_ref operator *() const
339 assert( m_pNode != nullptr );
344 iterator_type& operator ++()
351 iterator_type operator ++(int)
353 iterator_type i(*this);
358 iterator_type& operator = (const iterator_type& src)
360 m_pNode = src.m_pNode;
365 bool operator ==(iterator_type<C> const& i ) const
367 return m_pNode == i.m_pNode;
370 bool operator !=(iterator_type<C> const& i ) const
372 return m_pNode != i.m_pNode;
378 ///@name Forward iterators (thread-safe only under RCU lock)
382 You may safely use iterators in multi-threaded environment only under RCU lock.
383 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
385 typedef iterator_type<false> iterator;
387 /// Const forward iterator
388 typedef iterator_type<true> const_iterator;
390 /// Returns a forward iterator addressing the first element in a list
392 For empty list \code begin() == end() \endcode
396 return iterator( m_pHead );
399 /// Returns an iterator that addresses the location succeeding the last element in a list
401 Do not use the value returned by <tt>end</tt> function to access any item.
402 Internally, <tt>end</tt> returning value equals to \p nullptr.
404 The returned value can be used only to control reaching the end of the list.
405 For empty list \code begin() == end() \endcode
412 /// Returns a forward const iterator addressing the first element in a list
413 const_iterator begin() const
415 return const_iterator(m_pHead );
417 /// Returns a forward const iterator addressing the first element in a list
418 const_iterator cbegin() const
420 return const_iterator(m_pHead );
423 /// Returns an const iterator that addresses the location succeeding the last element in a list
424 const_iterator end() const
426 return const_iterator();
428 /// Returns an const iterator that addresses the location succeeding the last element in a list
429 const_iterator cend() const
431 return const_iterator();
436 /// Default constructor initializes empty list
440 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
451 The function inserts \p val in the list if the list does not contain
452 an item with key equal to \p val.
454 The function makes RCU lock internally.
456 Returns \p true if \p val is linked into the list, \p false otherwise.
458 bool insert( value_type& val )
460 return insert_at( m_pHead, val );
465 This function is intended for derived non-intrusive containers.
467 The function allows to split new item creating into two part:
468 - create item with key only
469 - insert new item into the list
470 - if inserting is success, calls \p f functor to initialize value-field of \p val.
472 The functor signature is:
474 void func( value_type& val );
476 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
477 \p val no any other changes could be made on this list's item by concurrent threads.
478 The user-defined functor is called only if the inserting is success.
480 The function makes RCU lock internally.
482 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
484 template <typename Func>
485 bool insert( value_type& val, Func f )
487 return insert_at( m_pHead, val, f );
492 The operation performs inserting or changing data with lock-free manner.
494 If the item \p val not found in the list, then \p val is inserted into the list
495 iff \p bAllowInsert is \p true.
496 Otherwise, the functor \p func is called with item found.
497 The functor signature is:
500 void operator()( bool bNew, value_type& item, value_type& val );
504 - \p bNew - \p true if the item has been inserted, \p false otherwise
505 - \p item - item of the list
506 - \p val - argument \p val passed into the \p update() function
507 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
508 refer to the same thing.
510 The functor may change non-key fields of the \p item; however, \p func must guarantee
511 that during changing no any other modifications could be made on this item by concurrent threads.
513 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
514 \p second is \p true if new item has been added or \p false if the item with \p key
515 already is in the list.
517 The function makes RCU lock internally.
519 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
521 template <typename Func>
522 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
524 return update_at( m_pHead, val, func, bAllowInsert );
527 template <typename Func>
528 CDS_DEPRECATED("ensure() is deprecated, use update()")
529 std::pair<bool, bool> ensure( value_type& val, Func func )
531 return update( val, func, true );
535 /// Unlinks the item \p val from the list
537 The function searches the item \p val in the list and unlink it from the list
538 if it is found and it is equal to \p val.
540 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
541 and deletes the item found. \p %unlink() finds an item by key and deletes it
542 only if \p val is an item of that list, i.e. the pointer to the item found
543 is equal to <tt> &val </tt>.
545 The function returns \p true if success and \p false otherwise.
547 RCU \p synchronize method can be called.
548 Note that depending on RCU type used the \ref disposer call can be deferred.
550 \p disposer specified in \p Traits is called for unlinked item.
552 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
553 deadlock checking policy is opt::v::rcu_throw_deadlock.
555 bool unlink( value_type& val )
557 return unlink_at( m_pHead, val );
560 /// Deletes the item from the list
562 The function searches an item with key equal to \p key in the list,
563 unlinks it from the list, and returns \p true.
564 If the item with the key equal to \p key is not found the function return \p false.
566 RCU \p synchronize method can be called.
567 Note that depending on RCU type used the \ref disposer call can be deferred.
569 \p disposer specified in \p Traits is called for deleted item.
571 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
572 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
574 template <typename Q>
575 bool erase( Q const& key )
577 return erase_at( m_pHead, key, key_comparator() );
580 /// Deletes the item from the list using \p pred predicate for searching
582 The function is an analog of \p erase(Q const&)
583 but \p pred is used for key comparing.
584 \p Less functor has the interface like \p std::less.
585 \p pred must imply the same element order as the comparator used for building the list.
587 \p disposer specified in \p Traits is called for deleted item.
589 template <typename Q, typename Less>
590 bool erase_with( Q const& key, Less pred )
593 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
596 /// Deletes the item from the list
598 The function searches an item with key equal to \p key in the list,
599 call \p func functor with item found, unlinks it from the list, and returns \p true.
600 The \p Func interface is
603 void operator()( value_type const& item );
607 If the item with the key equal to \p key is not found the function return \p false.
609 RCU \p synchronize method can be called.
610 Note that depending on RCU type used the \ref disposer call can be deferred.
612 \p disposer specified in \p Traits is called for deleted item.
614 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
615 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
617 template <typename Q, typename Func>
618 bool erase( Q const& key, Func func )
620 return erase_at( m_pHead, key, key_comparator(), func );
623 /// Deletes the item from the list using \p pred predicate for searching
625 The function is an analog of \p erase(Q const&, Func)
626 but \p pred is used for key comparing.
627 \p Less functor has the interface like \p std::less.
628 \p pred must imply the same element order as the comparator used for building the list.
630 \p disposer specified in \p Traits is called for deleted item.
632 template <typename Q, typename Less, typename Func>
633 bool erase_with( Q const& key, Less pred, Func func )
636 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
639 /// Extracts an item from the list
641 The function searches an item with key equal to \p key in the list,
642 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
643 If \p key is not found the function returns an empty \p exempt_ptr.
645 @note The function does NOT dispose the item found. It just unlinks the item from the list
646 and returns a pointer to item found.
647 You shouldn't lock RCU for current thread before calling this function, and you should manually release
648 the returned exempt pointer before reusing it.
651 #include <cds/urcu/general_buffered.h>
652 #include <cds/intrusive/michael_list_rcu.h>
654 typedef cds::urcu::gc< general_buffered<> > rcu;
655 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
657 rcu_michael_list theList;
660 rcu_michael_list::exempt_ptr p1;
662 // The RCU should NOT be locked when extract() is called!
663 assert( !rcu::is_locked() );
665 // You can call extract() function
666 p1 = theList.extract( 10 );
668 // do something with p1
672 // We may safely release p1 here
673 // release() passes the pointer to RCU reclamation cycle:
674 // it invokes RCU retire_ptr function with the disposer you provided for the list.
678 template <typename Q>
679 exempt_ptr extract( Q const& key )
681 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
684 /// Extracts an item from the list using \p pred predicate for searching
686 This function is the analog for \p extract(Q const&)
688 The \p pred is a predicate used for key comparing.
689 \p Less has the interface like \p std::less.
690 \p pred must imply the same element order as \ref key_comparator.
692 template <typename Q, typename Less>
693 exempt_ptr extract_with( Q const& key, Less pred )
696 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
699 /// Find the key \p val
701 The function searches the item with key equal to \p key
702 and calls the functor \p f for item found.
703 The interface of \p Func functor is:
706 void operator()( value_type& item, Q& key );
709 where \p item is the item found, \p key is the <tt>find</tt> function argument.
711 The functor can change non-key fields of \p item.
712 The function \p find does not serialize simultaneous access to the list \p item. If such access is
713 possible you must provide your own synchronization schema to exclude unsafe item modifications.
715 The function makes RCU lock internally.
717 The function returns \p true if \p val is found, \p false otherwise.
719 template <typename Q, typename Func>
720 bool find( Q& key, Func f )
722 return find_at( m_pHead, key, key_comparator(), f );
725 template <typename Q, typename Func>
726 bool find( Q const& key, Func f )
728 return find_at( m_pHead, key, key_comparator(), f );
732 /// Finds \p key using \p pred predicate for searching
734 The function is an analog of \p find(Q&, Func)
735 but \p pred is used for key comparing.
736 \p Less functor has the interface like \p std::less.
737 \p pred must imply the same element order as the comparator used for building the list.
739 template <typename Q, typename Less, typename Func>
740 bool find_with( Q& key, Less pred, Func f )
743 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
746 template <typename Q, typename Less, typename Func>
747 bool find_with( Q const& key, Less pred, Func f )
750 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
754 /// Checks whether the list contains \p key
756 The function searches the item with key equal to \p key
757 and returns \p true if it is found, and \p false otherwise.
759 template <typename Q>
760 bool contains( Q const& key )
762 return find_at( m_pHead, key, key_comparator() );
765 template <typename Q>
766 CDS_DEPRECATED("deprecated, use contains()")
767 bool find( Q const& key )
769 return contains( key );
773 /// Checks whether the map contains \p key using \p pred predicate for searching
775 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
776 \p Less functor has the interface like \p std::less.
777 \p Less must imply the same element order as the comparator used for building the list.
779 template <typename Q, typename Less>
780 bool contains( Q const& key, Less pred )
783 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
786 template <typename Q, typename Less>
787 CDS_DEPRECATED("deprecated, use contains()")
788 bool find_with( Q const& key, Less pred )
790 return contains( key, pred );
794 /// Finds \p key and return the item found
795 /** \anchor cds_intrusive_MichaelList_rcu_get
796 The function searches the item with key equal to \p key and returns the pointer to item found.
797 If \p key is not found it returns empty \p raw_ptr object.
799 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
801 RCU should be locked before call of this function.
802 Returned item is valid only while RCU is locked:
804 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
807 typename ord_list::raw_ptr rp;
810 ord_list::rcu_lock lock;
812 rp = theList.get( 5 );
817 // Unlock RCU by rcu_lock destructor
818 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
820 // You can manually release rp after RCU-locked section
824 template <typename Q>
825 raw_ptr get( Q const& key )
827 return get_at( m_pHead, key, key_comparator());
830 /// Finds \p key and return the item found
832 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
833 but \p pred is used for comparing the keys.
835 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
837 \p pred must imply the same element order as the comparator used for building the list.
839 template <typename Q, typename Less>
840 raw_ptr get_with( Q const& key, Less pred )
843 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
846 /// Clears the list using default disposer
848 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
850 RCU \p synchronize method can be called.
851 Note that depending on RCU type used the \ref disposer invocation can be deferred.
853 The function can throw \p cds::urcu::rcu_deadlock exception if a deadlock is encountered and
854 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
859 check_deadlock_policy::check();
861 marked_node_ptr pHead;
865 pHead = m_pHead.load(memory_model::memory_order_acquire);
868 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
869 if ( cds_unlikely( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed )))
871 if ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed )))
876 dispose_node( pHead.ptr() );
881 /// Check if the list is empty
884 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
887 /// Returns list's item count
889 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
890 this function always returns 0.
892 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
893 is empty. To check list emptyness use \p empty() method.
897 return m_ItemCounter.value();
902 // split-list support
903 bool insert_aux_node( node_type * pNode )
905 return insert_aux_node( m_pHead, pNode );
908 // split-list support
909 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
911 assert( pNode != nullptr );
913 // Hack: convert node_type to value_type.
914 // In principle, auxiliary node can be non-reducible to value_type
915 // We assume that comparator can correctly distinguish between aux and regular node.
916 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
919 bool insert_at( atomic_node_ptr& refHead, value_type& val )
921 position pos( refHead );
924 return insert_at_locked( pos, val );
928 template <typename Func>
929 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
931 position pos( refHead );
936 if ( search( refHead, val, pos, key_comparator()))
939 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
946 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
952 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
955 if ( insert_at_locked( refHead, val ))
956 return iterator( node_traits::to_node_ptr( val ));
960 template <typename Func>
961 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
963 position pos( refHead );
966 return update_at_locked( pos, val, func, bInsert );
970 template <typename Func>
971 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
973 position pos( refHead );
976 std::pair<iterator, bool> ret = update_at_locked( pos, val, func, bInsert );
977 return std::make_pair( ret.first != end(), ret.second );
981 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
983 position pos( refHead );
985 check_deadlock_policy::check();
990 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
992 if ( !unlink_node( pos, erase_mask )) {
1003 template <typename Q, typename Compare, typename Func>
1004 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
1007 check_deadlock_policy::check();
1013 if ( !search( pos.refHead, val, pos, cmp ) )
1015 // store pCur since it may be changed by unlink_node() slow path
1017 if ( !unlink_node( pos, erase_mask )) {
1023 f( *node_traits::to_value_ptr( pDel ) );
1029 template <typename Q, typename Compare, typename Func>
1030 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
1032 position pos( refHead );
1033 return erase_at( pos, val, cmp, f );
1036 template <typename Q, typename Compare>
1037 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
1039 position pos( refHead );
1040 return erase_at( pos, val, cmp, [](value_type const&){} );
1043 template <typename Q, typename Compare >
1044 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1046 position pos( refHead );
1048 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
1050 node_type * pExtracted;
1054 if ( !search( refHead, val, pos, cmp ) )
1056 // store pCur since it may be changed by unlink_node() slow path
1057 pExtracted = pos.pCur;
1058 if ( !unlink_node( pos, extract_mask )) {
1064 value_type * pRet = node_traits::to_value_ptr( pExtracted );
1065 assert( pExtracted->m_pDelChain == nullptr );
1071 template <typename Q, typename Compare, typename Func>
1072 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1074 position pos( refHead );
1078 if ( search( refHead, val, pos, cmp ) ) {
1079 assert( pos.pCur != nullptr );
1080 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1087 template <typename Q, typename Compare>
1088 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1090 position pos( refHead );
1093 return find_at_locked( pos, val, cmp ) != cend();
1097 template <typename Q, typename Compare>
1098 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1100 // RCU should be locked!
1101 assert(gc::is_locked() );
1103 position pos( refHead );
1105 if ( search( refHead, val, pos, cmp ))
1106 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1107 return raw_ptr( raw_ptr_disposer( pos ));
1114 template <typename Q, typename Compare>
1115 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1117 // RCU lock should be locked!!!
1118 assert( gc::is_locked() );
1120 atomic_node_ptr * pPrev;
1121 marked_node_ptr pNext;
1122 marked_node_ptr pCur;
1128 pCur = pPrev->load(memory_model::memory_order_acquire);
1132 if ( !pCur.ptr() ) {
1135 pos.pNext = nullptr;
1139 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1141 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire) != pCur
1142 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire )))
1148 if ( pNext.bits() ) {
1149 // pCur is marked as deleted. Try to unlink it from the list
1150 if ( cds_likely( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
1151 if ( pNext.bits() == erase_mask )
1152 link_to_remove_chain( pos, pCur.ptr() );
1158 assert( pCur.ptr() != nullptr );
1159 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1162 pos.pCur = pCur.ptr();
1163 pos.pNext = pNext.ptr();
1166 pPrev = &( pCur->m_pNext );
1174 bool insert_at_locked( position& pos, value_type& val )
1176 // RCU lock should be locked!!!
1177 assert( gc::is_locked() );
1180 if ( search( pos.refHead, val, pos, key_comparator() ) )
1183 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1189 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1193 template <typename Func>
1194 std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
1196 // RCU should be locked!!!
1197 assert( gc::is_locked() );
1200 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1201 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1203 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1204 return std::make_pair( iterator( pos.pCur ), false );
1208 return std::make_pair( end(), false );
1210 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1212 func( true, val , val );
1213 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1216 // clear the next field
1217 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1222 template <typename Q, typename Compare>
1223 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1225 assert( gc::is_locked() );
1227 if ( search( pos.refHead, val, pos, cmp ) ) {
1228 assert( pos.pCur != nullptr );
1229 return const_iterator( pos.pCur );
1236 }} // namespace cds::intrusive
1238 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H