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;
375 typedef iterator_type<false> iterator;
376 /// Const forward iterator
377 typedef iterator_type<true> const_iterator;
379 /// Returns a forward iterator addressing the first element in a list
381 For empty list \code begin() == end() \endcode
385 return iterator( m_pHead );
388 /// Returns an iterator that addresses the location succeeding the last element in a list
390 Do not use the value returned by <tt>end</tt> function to access any item.
391 Internally, <tt>end</tt> returning value equals to \p nullptr.
393 The returned value can be used only to control reaching the end of the list.
394 For empty list \code begin() == end() \endcode
401 /// Returns a forward const iterator addressing the first element in a list
402 const_iterator begin() const
404 return const_iterator(m_pHead );
406 /// Returns a forward const iterator addressing the first element in a list
407 const_iterator cbegin() const
409 return const_iterator(m_pHead );
412 /// Returns an const iterator that addresses the location succeeding the last element in a list
413 const_iterator end() const
415 return const_iterator();
417 /// Returns an const iterator that addresses the location succeeding the last element in a list
418 const_iterator cend() const
420 return const_iterator();
424 /// Default constructor initializes empty list
428 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
439 The function inserts \p val in the list if the list does not contain
440 an item with key equal to \p val.
442 The function makes RCU lock internally.
444 Returns \p true if \p val is linked into the list, \p false otherwise.
446 bool insert( value_type& val )
448 return insert_at( m_pHead, val );
453 This function is intended for derived non-intrusive containers.
455 The function allows to split new item creating into two part:
456 - create item with key only
457 - insert new item into the list
458 - if inserting is success, calls \p f functor to initialize value-field of \p val.
460 The functor signature is:
462 void func( value_type& val );
464 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
465 \p val no any other changes could be made on this list's item by concurrent threads.
466 The user-defined functor is called only if the inserting is success.
468 The function makes RCU lock internally.
470 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
472 template <typename Func>
473 bool insert( value_type& val, Func f )
475 return insert_at( m_pHead, val, f );
480 The operation performs inserting or changing data with lock-free manner.
482 If the item \p val not found in the list, then \p val is inserted into the list
483 iff \p bAllowInsert is \p true.
484 Otherwise, the functor \p func is called with item found.
485 The functor signature is:
488 void operator()( bool bNew, value_type& item, value_type& val );
492 - \p bNew - \p true if the item has been inserted, \p false otherwise
493 - \p item - item of the list
494 - \p val - argument \p val passed into the \p update() function
495 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
496 refer to the same thing.
498 The functor may change non-key fields of the \p item; however, \p func must guarantee
499 that during changing no any other modifications could be made on this item by concurrent threads.
501 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
502 \p second is \p true if new item has been added or \p false if the item with \p key
503 already is in the list.
505 The function makes RCU lock internally.
507 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
509 template <typename Func>
510 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
512 return update_at( m_pHead, val, func, bAllowInsert );
515 template <typename Func>
516 CDS_DEPRECATED("ensure() is deprecated, use update()")
517 std::pair<bool, bool> ensure( value_type& val, Func func )
519 return update( val, func, true );
523 /// Unlinks the item \p val from the list
525 The function searches the item \p val in the list and unlink it from the list
526 if it is found and it is equal to \p val.
528 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
529 and deletes the item found. \p %unlink() finds an item by key and deletes it
530 only if \p val is an item of that list, i.e. the pointer to the item found
531 is equal to <tt> &val </tt>.
533 The function returns \p true if success and \p false otherwise.
535 RCU \p synchronize method can be called.
536 Note that depending on RCU type used the \ref disposer call can be deferred.
538 \p disposer specified in \p Traits is called for unlinked item.
540 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
541 deadlock checking policy is opt::v::rcu_throw_deadlock.
543 bool unlink( value_type& val )
545 return unlink_at( m_pHead, val );
548 /// Deletes the item from the list
550 The function searches an item with key equal to \p key in the list,
551 unlinks it from the list, and returns \p true.
552 If the item with the key equal to \p key is not found the function return \p false.
554 RCU \p synchronize method can be called.
555 Note that depending on RCU type used the \ref disposer call can be deferred.
557 \p disposer specified in \p Traits is called for deleted item.
559 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
560 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
562 template <typename Q>
563 bool erase( Q const& key )
565 return erase_at( m_pHead, key, key_comparator() );
568 /// Deletes the item from the list using \p pred predicate for searching
570 The function is an analog of \p erase(Q const&)
571 but \p pred is used for key comparing.
572 \p Less functor has the interface like \p std::less.
573 \p pred must imply the same element order as the comparator used for building the list.
575 \p disposer specified in \p Traits is called for deleted item.
577 template <typename Q, typename Less>
578 bool erase_with( Q const& key, Less pred )
581 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
584 /// Deletes the item from the list
586 The function searches an item with key equal to \p key in the list,
587 call \p func functor with item found, unlinks it from the list, and returns \p true.
588 The \p Func interface is
591 void operator()( value_type const& item );
595 If the item with the key equal to \p key is not found the function return \p false.
597 RCU \p synchronize method can be called.
598 Note that depending on RCU type used the \ref disposer call can be deferred.
600 \p disposer specified in \p Traits is called for deleted item.
602 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
603 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
605 template <typename Q, typename Func>
606 bool erase( Q const& key, Func func )
608 return erase_at( m_pHead, key, key_comparator(), func );
611 /// Deletes the item from the list using \p pred predicate for searching
613 The function is an analog of \p erase(Q const&, Func)
614 but \p pred is used for key comparing.
615 \p Less functor has the interface like \p std::less.
616 \p pred must imply the same element order as the comparator used for building the list.
618 \p disposer specified in \p Traits is called for deleted item.
620 template <typename Q, typename Less, typename Func>
621 bool erase_with( Q const& key, Less pred, Func func )
624 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
627 /// Extracts an item from the list
629 The function searches an item with key equal to \p key in the list,
630 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
631 If \p key is not found the function returns an empty \p exempt_ptr.
633 @note The function does NOT dispose the item found. It just unlinks the item from the list
634 and returns a pointer to item found.
635 You shouldn't lock RCU for current thread before calling this function, and you should manually release
636 the returned exempt pointer before reusing it.
639 #include <cds/urcu/general_buffered.h>
640 #include <cds/intrusive/michael_list_rcu.h>
642 typedef cds::urcu::gc< general_buffered<> > rcu;
643 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
645 rcu_michael_list theList;
648 rcu_michael_list::exempt_ptr p1;
650 // The RCU should NOT be locked when extract() is called!
651 assert( !rcu::is_locked() );
653 // You can call extract() function
654 p1 = theList.extract( 10 );
656 // do something with p1
660 // We may safely release p1 here
661 // release() passes the pointer to RCU reclamation cycle:
662 // it invokes RCU retire_ptr function with the disposer you provided for the list.
666 template <typename Q>
667 exempt_ptr extract( Q const& key )
669 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
672 /// Extracts an item from the list using \p pred predicate for searching
674 This function is the analog for \p extract(Q const&)
676 The \p pred is a predicate used for key comparing.
677 \p Less has the interface like \p std::less.
678 \p pred must imply the same element order as \ref key_comparator.
680 template <typename Q, typename Less>
681 exempt_ptr extract_with( Q const& key, Less pred )
684 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
687 /// Find the key \p val
689 The function searches the item with key equal to \p key
690 and calls the functor \p f for item found.
691 The interface of \p Func functor is:
694 void operator()( value_type& item, Q& key );
697 where \p item is the item found, \p key is the <tt>find</tt> function argument.
699 The functor can change non-key fields of \p item.
700 The function \p find does not serialize simultaneous access to the list \p item. If such access is
701 possible you must provide your own synchronization schema to exclude unsafe item modifications.
703 The function makes RCU lock internally.
705 The function returns \p true if \p val is found, \p false otherwise.
707 template <typename Q, typename Func>
708 bool find( Q& key, Func f )
710 return find_at( m_pHead, key, key_comparator(), f );
713 template <typename Q, typename Func>
714 bool find( Q const& key, Func f )
716 return find_at( m_pHead, key, key_comparator(), f );
720 /// Finds \p key using \p pred predicate for searching
722 The function is an analog of \p find(Q&, Func)
723 but \p pred is used for key comparing.
724 \p Less functor has the interface like \p std::less.
725 \p pred must imply the same element order as the comparator used for building the list.
727 template <typename Q, typename Less, typename Func>
728 bool find_with( Q& key, Less pred, Func f )
731 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
734 template <typename Q, typename Less, typename Func>
735 bool find_with( Q const& key, Less pred, Func f )
738 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
742 /// Checks whether the list contains \p key
744 The function searches the item with key equal to \p key
745 and returns \p true if it is found, and \p false otherwise.
747 template <typename Q>
748 bool contains( Q const& key )
750 return find_at( m_pHead, key, key_comparator() );
753 template <typename Q>
754 CDS_DEPRECATED("deprecated, use contains()")
755 bool find( Q const& key )
757 return contains( key );
761 /// Checks whether the map contains \p key using \p pred predicate for searching
763 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
764 \p Less functor has the interface like \p std::less.
765 \p Less must imply the same element order as the comparator used for building the list.
767 template <typename Q, typename Less>
768 bool contains( Q const& key, Less pred )
771 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
774 template <typename Q, typename Less>
775 CDS_DEPRECATED("deprecated, use contains()")
776 bool find_with( Q const& key, Less pred )
778 return contains( key, pred );
782 /// Finds \p key and return the item found
783 /** \anchor cds_intrusive_MichaelList_rcu_get
784 The function searches the item with key equal to \p key and returns the pointer to item found.
785 If \p key is not found it returns empty \p raw_ptr object.
787 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
789 RCU should be locked before call of this function.
790 Returned item is valid only while RCU is locked:
792 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
795 typename ord_list::raw_ptr rp;
798 ord_list::rcu_lock lock;
800 rp = theList.get( 5 );
805 // Unlock RCU by rcu_lock destructor
806 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
808 // You can manually release rp after RCU-locked section
812 template <typename Q>
813 raw_ptr get( Q const& key )
815 return get_at( m_pHead, key, key_comparator());
818 /// Finds \p key and return the item found
820 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
821 but \p pred is used for comparing the keys.
823 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
825 \p pred must imply the same element order as the comparator used for building the list.
827 template <typename Q, typename Less>
828 raw_ptr get_with( Q const& key, Less pred )
831 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
834 /// Clears the list using default disposer
836 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
838 RCU \p synchronize method can be called.
839 Note that depending on RCU type used the \ref disposer invocation can be deferred.
841 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
842 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
847 check_deadlock_policy::check();
849 marked_node_ptr pHead;
853 pHead = m_pHead.load(memory_model::memory_order_acquire);
856 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
857 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
859 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
864 dispose_node( pHead.ptr() );
869 /// Check if the list is empty
872 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
875 /// Returns list's item count
877 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
878 this function always returns 0.
880 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
881 is empty. To check list emptyness use \p empty() method.
885 return m_ItemCounter.value();
890 // split-list support
891 bool insert_aux_node( node_type * pNode )
893 return insert_aux_node( m_pHead, pNode );
896 // split-list support
897 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
899 assert( pNode != nullptr );
901 // Hack: convert node_type to value_type.
902 // In principle, auxiliary node can be non-reducible to value_type
903 // We assume that comparator can correctly distinguish between aux and regular node.
904 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
907 bool insert_at( atomic_node_ptr& refHead, value_type& val )
909 position pos( refHead );
912 return insert_at_locked( pos, val );
916 template <typename Func>
917 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
919 link_checker::is_empty( node_traits::to_node_ptr( val ) );
920 position pos( refHead );
925 if ( search( refHead, val, pos, key_comparator()))
928 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
935 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
941 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
944 if ( insert_at_locked( refHead, val ))
945 return iterator( node_traits::to_node_ptr( val ));
949 template <typename Func>
950 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
952 position pos( refHead );
955 return update_at_locked( pos, val, func, bInsert );
959 template <typename Func>
960 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
962 position pos( refHead );
965 std::pair<iterator, bool> ret = update_at_locked( pos, val, func, bInsert );
966 return std::make_pair( ret.first != end(), ret.second );
970 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
972 position pos( refHead );
974 check_deadlock_policy::check();
979 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
981 if ( !unlink_node( pos, erase_mask )) {
992 template <typename Q, typename Compare, typename Func>
993 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
996 check_deadlock_policy::check();
1002 if ( !search( pos.refHead, val, pos, cmp ) )
1004 // store pCur since it may be changed by unlink_node() slow path
1006 if ( !unlink_node( pos, erase_mask )) {
1012 f( *node_traits::to_value_ptr( pDel ) );
1018 template <typename Q, typename Compare, typename Func>
1019 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
1021 position pos( refHead );
1022 return erase_at( pos, val, cmp, f );
1025 template <typename Q, typename Compare>
1026 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
1028 position pos( refHead );
1029 return erase_at( pos, val, cmp, [](value_type const&){} );
1032 template <typename Q, typename Compare >
1033 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1035 position pos( refHead );
1037 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
1039 node_type * pExtracted;
1043 if ( !search( refHead, val, pos, cmp ) )
1045 // store pCur since it may be changed by unlink_node() slow path
1046 pExtracted = pos.pCur;
1047 if ( !unlink_node( pos, extract_mask )) {
1053 value_type * pRet = node_traits::to_value_ptr( pExtracted );
1054 assert( pExtracted->m_pDelChain == nullptr );
1060 template <typename Q, typename Compare, typename Func>
1061 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1063 position pos( refHead );
1067 if ( search( refHead, val, pos, cmp ) ) {
1068 assert( pos.pCur != nullptr );
1069 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1076 template <typename Q, typename Compare>
1077 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1079 position pos( refHead );
1082 return find_at_locked( pos, val, cmp ) != cend();
1086 template <typename Q, typename Compare>
1087 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1089 // RCU should be locked!
1090 assert(gc::is_locked() );
1092 position pos( refHead );
1094 if ( search( refHead, val, pos, cmp ))
1095 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1096 return raw_ptr( raw_ptr_disposer( pos ));
1103 template <typename Q, typename Compare>
1104 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1106 // RCU lock should be locked!!!
1107 assert( gc::is_locked() );
1109 atomic_node_ptr * pPrev;
1110 marked_node_ptr pNext;
1111 marked_node_ptr pCur;
1117 pCur = pPrev->load(memory_model::memory_order_acquire);
1121 if ( !pCur.ptr() ) {
1124 pos.pNext = nullptr;
1128 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1130 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
1131 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire))
1137 if ( pNext.bits() ) {
1138 // pCur is marked as deleted. Try to unlink it from the list
1139 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1140 if ( pNext.bits() == erase_mask )
1141 link_to_remove_chain( pos, pCur.ptr() );
1147 assert( pCur.ptr() != nullptr );
1148 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1151 pos.pCur = pCur.ptr();
1152 pos.pNext = pNext.ptr();
1155 pPrev = &( pCur->m_pNext );
1163 bool insert_at_locked( position& pos, value_type& val )
1165 // RCU lock should be locked!!!
1166 assert( gc::is_locked() );
1167 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1170 if ( search( pos.refHead, val, pos, key_comparator() ) )
1173 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1179 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1183 template <typename Func>
1184 std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
1186 // RCU should be locked!!!
1187 assert( gc::is_locked() );
1190 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1191 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1193 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1194 return std::make_pair( iterator( pos.pCur ), false );
1198 return std::make_pair( end(), false );
1200 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1202 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1204 func( true, val , val );
1205 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1208 // clear the next field
1209 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1214 template <typename Q, typename Compare>
1215 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1217 assert( gc::is_locked() );
1219 if ( search( pos.refHead, val, pos, cmp ) ) {
1220 assert( pos.pCur != nullptr );
1221 return const_iterator( pos.pCur );
1228 }} // namespace cds::intrusive
1230 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H