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 return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
253 static void link_to_remove_chain( position& pos, node_type * pDel )
255 assert( pDel->m_pDelChain == nullptr );
257 pDel->m_pDelChain = pos.pDelChain;
258 pos.pDelChain = pDel;
261 bool unlink_node( position& pos, erase_node_mask nMask )
263 assert(gc::is_locked() );
265 // Mark the node (logical deletion)
266 marked_node_ptr next(pos.pNext, 0);
268 if ( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
270 // Try physical removal - fast path
271 marked_node_ptr cur(pos.pCur);
272 if ( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
273 if ( nMask == erase_mask )
274 link_to_remove_chain( pos, pos.pCur );
278 search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
288 template <bool IsConst>
291 friend class MichaelList;
292 value_type * m_pNode;
297 node_type * p = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_relaxed).ptr();
298 m_pNode = p ? node_traits::to_value_ptr( p ) : nullptr;
303 explicit iterator_type( node_type * pNode)
306 m_pNode = node_traits::to_value_ptr( *pNode );
310 explicit iterator_type( atomic_node_ptr const& refNode)
312 node_type * pNode = refNode.load(memory_model::memory_order_relaxed).ptr();
313 m_pNode = pNode ? node_traits::to_value_ptr( *pNode ) : nullptr;
317 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
318 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
324 iterator_type( const iterator_type& src )
325 : m_pNode( src.m_pNode )
328 value_ptr operator ->() const
333 value_ref operator *() const
335 assert( m_pNode != nullptr );
340 iterator_type& operator ++()
347 iterator_type operator ++(int)
349 iterator_type i(*this);
354 iterator_type& operator = (const iterator_type& src)
356 m_pNode = src.m_pNode;
361 bool operator ==(iterator_type<C> const& i ) const
363 return m_pNode == i.m_pNode;
366 bool operator !=(iterator_type<C> const& i ) const
368 return m_pNode != i.m_pNode;
374 ///@name Forward iterators (thread-safe only under RCU lock)
378 You may safely use iterators in multi-threaded environment only under RCU lock.
379 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
381 typedef iterator_type<false> iterator;
383 /// Const forward iterator
384 typedef iterator_type<true> const_iterator;
386 /// Returns a forward iterator addressing the first element in a list
388 For empty list \code begin() == end() \endcode
392 return iterator( m_pHead );
395 /// Returns an iterator that addresses the location succeeding the last element in a list
397 Do not use the value returned by <tt>end</tt> function to access any item.
398 Internally, <tt>end</tt> returning value equals to \p nullptr.
400 The returned value can be used only to control reaching the end of the list.
401 For empty list \code begin() == end() \endcode
408 /// Returns a forward const iterator addressing the first element in a list
409 const_iterator begin() const
411 return const_iterator(m_pHead );
413 /// Returns a forward const iterator addressing the first element in a list
414 const_iterator cbegin() const
416 return const_iterator(m_pHead );
419 /// Returns an const iterator that addresses the location succeeding the last element in a list
420 const_iterator end() const
422 return const_iterator();
424 /// Returns an const iterator that addresses the location succeeding the last element in a list
425 const_iterator cend() const
427 return const_iterator();
432 /// Default constructor initializes empty list
436 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
447 The function inserts \p val in the list if the list does not contain
448 an item with key equal to \p val.
450 The function makes RCU lock internally.
452 Returns \p true if \p val is linked into the list, \p false otherwise.
454 bool insert( value_type& val )
456 return insert_at( m_pHead, val );
461 This function is intended for derived non-intrusive containers.
463 The function allows to split new item creating into two part:
464 - create item with key only
465 - insert new item into the list
466 - if inserting is success, calls \p f functor to initialize value-field of \p val.
468 The functor signature is:
470 void func( value_type& val );
472 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
473 \p val no any other changes could be made on this list's item by concurrent threads.
474 The user-defined functor is called only if the inserting is success.
476 The function makes RCU lock internally.
478 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
480 template <typename Func>
481 bool insert( value_type& val, Func f )
483 return insert_at( m_pHead, val, f );
488 The operation performs inserting or changing data with lock-free manner.
490 If the item \p val not found in the list, then \p val is inserted into the list
491 iff \p bAllowInsert is \p true.
492 Otherwise, the functor \p func is called with item found.
493 The functor signature is:
496 void operator()( bool bNew, value_type& item, value_type& val );
500 - \p bNew - \p true if the item has been inserted, \p false otherwise
501 - \p item - item of the list
502 - \p val - argument \p val passed into the \p update() function
503 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
504 refer to the same thing.
506 The functor may change non-key fields of the \p item; however, \p func must guarantee
507 that during changing no any other modifications could be made on this item by concurrent threads.
509 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
510 \p second is \p true if new item has been added or \p false if the item with \p key
511 already is in the list.
513 The function makes RCU lock internally.
515 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
517 template <typename Func>
518 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
520 return update_at( m_pHead, val, func, bAllowInsert );
523 template <typename Func>
524 CDS_DEPRECATED("ensure() is deprecated, use update()")
525 std::pair<bool, bool> ensure( value_type& val, Func func )
527 return update( val, func, true );
531 /// Unlinks the item \p val from the list
533 The function searches the item \p val in the list and unlink it from the list
534 if it is found and it is equal to \p val.
536 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
537 and deletes the item found. \p %unlink() finds an item by key and deletes it
538 only if \p val is an item of that list, i.e. the pointer to the item found
539 is equal to <tt> &val </tt>.
541 The function returns \p true if success and \p false otherwise.
543 RCU \p synchronize method can be called.
544 Note that depending on RCU type used the \ref disposer call can be deferred.
546 \p disposer specified in \p Traits is called for unlinked item.
548 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
549 deadlock checking policy is opt::v::rcu_throw_deadlock.
551 bool unlink( value_type& val )
553 return unlink_at( m_pHead, val );
556 /// Deletes the item from the list
558 The function searches an item with key equal to \p key in the list,
559 unlinks it from the list, and returns \p true.
560 If the item with the key equal to \p key is not found the function return \p false.
562 RCU \p synchronize method can be called.
563 Note that depending on RCU type used the \ref disposer call can be deferred.
565 \p disposer specified in \p Traits is called for deleted item.
567 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
568 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
570 template <typename Q>
571 bool erase( Q const& key )
573 return erase_at( m_pHead, key, key_comparator() );
576 /// Deletes the item from the list using \p pred predicate for searching
578 The function is an analog of \p erase(Q const&)
579 but \p pred is used for key comparing.
580 \p Less functor has the interface like \p std::less.
581 \p pred must imply the same element order as the comparator used for building the list.
583 \p disposer specified in \p Traits is called for deleted item.
585 template <typename Q, typename Less>
586 bool erase_with( Q const& key, Less pred )
589 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
592 /// Deletes the item from the list
594 The function searches an item with key equal to \p key in the list,
595 call \p func functor with item found, unlinks it from the list, and returns \p true.
596 The \p Func interface is
599 void operator()( value_type const& item );
603 If the item with the key equal to \p key is not found the function return \p false.
605 RCU \p synchronize method can be called.
606 Note that depending on RCU type used the \ref disposer call can be deferred.
608 \p disposer specified in \p Traits is called for deleted item.
610 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
611 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
613 template <typename Q, typename Func>
614 bool erase( Q const& key, Func func )
616 return erase_at( m_pHead, key, key_comparator(), func );
619 /// Deletes the item from the list using \p pred predicate for searching
621 The function is an analog of \p erase(Q const&, Func)
622 but \p pred is used for key comparing.
623 \p Less functor has the interface like \p std::less.
624 \p pred must imply the same element order as the comparator used for building the list.
626 \p disposer specified in \p Traits is called for deleted item.
628 template <typename Q, typename Less, typename Func>
629 bool erase_with( Q const& key, Less pred, Func func )
632 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
635 /// Extracts an item from the list
637 The function searches an item with key equal to \p key in the list,
638 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
639 If \p key is not found the function returns an empty \p exempt_ptr.
641 @note The function does NOT dispose the item found. It just unlinks the item from the list
642 and returns a pointer to item found.
643 You shouldn't lock RCU for current thread before calling this function, and you should manually release
644 the returned exempt pointer before reusing it.
647 #include <cds/urcu/general_buffered.h>
648 #include <cds/intrusive/michael_list_rcu.h>
650 typedef cds::urcu::gc< general_buffered<> > rcu;
651 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
653 rcu_michael_list theList;
656 rcu_michael_list::exempt_ptr p1;
658 // The RCU should NOT be locked when extract() is called!
659 assert( !rcu::is_locked() );
661 // You can call extract() function
662 p1 = theList.extract( 10 );
664 // do something with p1
668 // We may safely release p1 here
669 // release() passes the pointer to RCU reclamation cycle:
670 // it invokes RCU retire_ptr function with the disposer you provided for the list.
674 template <typename Q>
675 exempt_ptr extract( Q const& key )
677 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
680 /// Extracts an item from the list using \p pred predicate for searching
682 This function is the analog for \p extract(Q const&)
684 The \p pred is a predicate used for key comparing.
685 \p Less has the interface like \p std::less.
686 \p pred must imply the same element order as \ref key_comparator.
688 template <typename Q, typename Less>
689 exempt_ptr extract_with( Q const& key, Less pred )
692 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
695 /// Find the key \p val
697 The function searches the item with key equal to \p key
698 and calls the functor \p f for item found.
699 The interface of \p Func functor is:
702 void operator()( value_type& item, Q& key );
705 where \p item is the item found, \p key is the <tt>find</tt> function argument.
707 The functor can change non-key fields of \p item.
708 The function \p find does not serialize simultaneous access to the list \p item. If such access is
709 possible you must provide your own synchronization schema to exclude unsafe item modifications.
711 The function makes RCU lock internally.
713 The function returns \p true if \p val is found, \p false otherwise.
715 template <typename Q, typename Func>
716 bool find( Q& key, Func f )
718 return find_at( m_pHead, key, key_comparator(), f );
721 template <typename Q, typename Func>
722 bool find( Q const& key, Func f )
724 return find_at( m_pHead, key, key_comparator(), f );
728 /// Finds \p key using \p pred predicate for searching
730 The function is an analog of \p find(Q&, Func)
731 but \p pred is used for key comparing.
732 \p Less functor has the interface like \p std::less.
733 \p pred must imply the same element order as the comparator used for building the list.
735 template <typename Q, typename Less, typename Func>
736 bool find_with( Q& key, Less pred, Func f )
739 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
742 template <typename Q, typename Less, typename Func>
743 bool find_with( Q const& key, Less pred, Func f )
746 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
750 /// Checks whether the list contains \p key
752 The function searches the item with key equal to \p key
753 and returns \p true if it is found, and \p false otherwise.
755 template <typename Q>
756 bool contains( Q const& key )
758 return find_at( m_pHead, key, key_comparator() );
761 template <typename Q>
762 CDS_DEPRECATED("deprecated, use contains()")
763 bool find( Q const& key )
765 return contains( key );
769 /// Checks whether the map contains \p key using \p pred predicate for searching
771 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
772 \p Less functor has the interface like \p std::less.
773 \p Less must imply the same element order as the comparator used for building the list.
775 template <typename Q, typename Less>
776 bool contains( Q const& key, Less pred )
779 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
782 template <typename Q, typename Less>
783 CDS_DEPRECATED("deprecated, use contains()")
784 bool find_with( Q const& key, Less pred )
786 return contains( key, pred );
790 /// Finds \p key and return the item found
791 /** \anchor cds_intrusive_MichaelList_rcu_get
792 The function searches the item with key equal to \p key and returns the pointer to item found.
793 If \p key is not found it returns empty \p raw_ptr object.
795 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
797 RCU should be locked before call of this function.
798 Returned item is valid only while RCU is locked:
800 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
803 typename ord_list::raw_ptr rp;
806 ord_list::rcu_lock lock;
808 rp = theList.get( 5 );
813 // Unlock RCU by rcu_lock destructor
814 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
816 // You can manually release rp after RCU-locked section
820 template <typename Q>
821 raw_ptr get( Q const& key )
823 return get_at( m_pHead, key, key_comparator());
826 /// Finds \p key and return the item found
828 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
829 but \p pred is used for comparing the keys.
831 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
833 \p pred must imply the same element order as the comparator used for building the list.
835 template <typename Q, typename Less>
836 raw_ptr get_with( Q const& key, Less pred )
839 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
842 /// Clears the list using default disposer
844 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
846 RCU \p synchronize method can be called.
847 Note that depending on RCU type used the \ref disposer invocation can be deferred.
849 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
850 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
855 check_deadlock_policy::check();
857 marked_node_ptr pHead;
861 pHead = m_pHead.load(memory_model::memory_order_acquire);
864 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
865 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
867 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
872 dispose_node( pHead.ptr() );
877 /// Check if the list is empty
880 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
883 /// Returns list's item count
885 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
886 this function always returns 0.
888 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
889 is empty. To check list emptyness use \p empty() method.
893 return m_ItemCounter.value();
898 // split-list support
899 bool insert_aux_node( node_type * pNode )
901 return insert_aux_node( m_pHead, pNode );
904 // split-list support
905 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
907 assert( pNode != nullptr );
909 // Hack: convert node_type to value_type.
910 // In principle, auxiliary node can be non-reducible to value_type
911 // We assume that comparator can correctly distinguish between aux and regular node.
912 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
915 bool insert_at( atomic_node_ptr& refHead, value_type& val )
917 position pos( refHead );
920 return insert_at_locked( pos, val );
924 template <typename Func>
925 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
927 position pos( refHead );
932 if ( search( refHead, val, pos, key_comparator()))
935 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
942 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
948 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
951 if ( insert_at_locked( refHead, val ))
952 return iterator( node_traits::to_node_ptr( val ));
956 template <typename Func>
957 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
959 position pos( refHead );
962 return update_at_locked( pos, val, func, bInsert );
966 template <typename Func>
967 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
969 position pos( refHead );
972 std::pair<iterator, bool> ret = update_at_locked( pos, val, func, bInsert );
973 return std::make_pair( ret.first != end(), ret.second );
977 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
979 position pos( refHead );
981 check_deadlock_policy::check();
986 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
988 if ( !unlink_node( pos, erase_mask )) {
999 template <typename Q, typename Compare, typename Func>
1000 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
1003 check_deadlock_policy::check();
1009 if ( !search( pos.refHead, val, pos, cmp ) )
1011 // store pCur since it may be changed by unlink_node() slow path
1013 if ( !unlink_node( pos, erase_mask )) {
1019 f( *node_traits::to_value_ptr( pDel ) );
1025 template <typename Q, typename Compare, typename Func>
1026 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
1028 position pos( refHead );
1029 return erase_at( pos, val, cmp, f );
1032 template <typename Q, typename Compare>
1033 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
1035 position pos( refHead );
1036 return erase_at( pos, val, cmp, [](value_type const&){} );
1039 template <typename Q, typename Compare >
1040 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1042 position pos( refHead );
1044 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
1046 node_type * pExtracted;
1050 if ( !search( refHead, val, pos, cmp ) )
1052 // store pCur since it may be changed by unlink_node() slow path
1053 pExtracted = pos.pCur;
1054 if ( !unlink_node( pos, extract_mask )) {
1060 value_type * pRet = node_traits::to_value_ptr( pExtracted );
1061 assert( pExtracted->m_pDelChain == nullptr );
1067 template <typename Q, typename Compare, typename Func>
1068 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1070 position pos( refHead );
1074 if ( search( refHead, val, pos, cmp ) ) {
1075 assert( pos.pCur != nullptr );
1076 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1083 template <typename Q, typename Compare>
1084 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1086 position pos( refHead );
1089 return find_at_locked( pos, val, cmp ) != cend();
1093 template <typename Q, typename Compare>
1094 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1096 // RCU should be locked!
1097 assert(gc::is_locked() );
1099 position pos( refHead );
1101 if ( search( refHead, val, pos, cmp ))
1102 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1103 return raw_ptr( raw_ptr_disposer( pos ));
1110 template <typename Q, typename Compare>
1111 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1113 // RCU lock should be locked!!!
1114 assert( gc::is_locked() );
1116 atomic_node_ptr * pPrev;
1117 marked_node_ptr pNext;
1118 marked_node_ptr pCur;
1124 pCur = pPrev->load(memory_model::memory_order_acquire);
1128 if ( !pCur.ptr() ) {
1131 pos.pNext = nullptr;
1135 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1137 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
1138 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire))
1144 if ( pNext.bits() ) {
1145 // pCur is marked as deleted. Try to unlink it from the list
1146 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1147 if ( pNext.bits() == erase_mask )
1148 link_to_remove_chain( pos, pCur.ptr() );
1154 assert( pCur.ptr() != nullptr );
1155 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1158 pos.pCur = pCur.ptr();
1159 pos.pNext = pNext.ptr();
1162 pPrev = &( pCur->m_pNext );
1170 bool insert_at_locked( position& pos, value_type& val )
1172 // RCU lock should be locked!!!
1173 assert( gc::is_locked() );
1176 if ( search( pos.refHead, val, pos, key_comparator() ) )
1179 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1185 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1189 template <typename Func>
1190 std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
1192 // RCU should be locked!!!
1193 assert( gc::is_locked() );
1196 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1197 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1199 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1200 return std::make_pair( iterator( pos.pCur ), false );
1204 return std::make_pair( end(), false );
1206 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1208 func( true, val , val );
1209 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1212 // clear the next field
1213 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1218 template <typename Q, typename Compare>
1219 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1221 assert( gc::is_locked() );
1223 if ( search( pos.refHead, val, pos, cmp ) ) {
1224 assert( pos.pCur != nullptr );
1225 return const_iterator( pos.pCur );
1232 }} // namespace cds::intrusive
1234 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H