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 );
522 /// Unlinks the item \p val from the list
524 The function searches the item \p val in the list and unlink it from the list
525 if it is found and it is equal to \p val.
527 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
528 and deletes the item found. \p unlink finds an item by key and deletes it
529 only if \p val is an item of that list, i.e. the pointer to the item found
530 is equal to <tt> &val </tt>.
532 The function returns \p true if success and \p false otherwise.
534 RCU \p synchronize method can be called.
535 Note that depending on RCU type used the \ref disposer call can be deferred.
537 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
538 deadlock checking policy is opt::v::rcu_throw_deadlock.
540 bool unlink( value_type& val )
542 return unlink_at( m_pHead, val );
545 /// Deletes the item from the list
546 /** \anchor cds_intrusive_MichaelList_rcu_erase_val
547 The function searches an item with key equal to \p key in the list,
548 unlinks it from the list, and returns \p true.
549 If the item with the key equal to \p key is not found the function return \p false.
551 RCU \p synchronize method can be called.
552 Note that depending on RCU type used the \ref disposer call can be deferred.
554 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
555 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
557 template <typename Q>
558 bool erase( Q const& key )
560 return erase_at( m_pHead, key, key_comparator() );
563 /// Deletes the item from the list using \p pred predicate for searching
565 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_val "erase(Q const&)"
566 but \p pred is used for key comparing.
567 \p Less functor has the interface like \p std::less.
568 \p pred must imply the same element order as the comparator used for building the list.
570 template <typename Q, typename Less>
571 bool erase_with( Q const& key, Less pred )
574 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
577 /// Deletes the item from the list
578 /** \anchor cds_intrusive_MichaelList_rcu_erase_func
579 The function searches an item with key equal to \p key in the list,
580 call \p func functor with item found, unlinks it from the list, and returns \p true.
581 The \p Func interface is
584 void operator()( value_type const& item );
588 If the item with the key equal to \p key is not found the function return \p false.
590 RCU \p synchronize method can be called.
591 Note that depending on RCU type used the \ref disposer call can be deferred.
593 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if a deadlock is detected and
594 the deadlock checking policy is \p opt::v::rcu_throw_deadlock.
596 template <typename Q, typename Func>
597 bool erase( Q const& key, Func func )
599 return erase_at( m_pHead, key, key_comparator(), func );
602 /// Deletes the item from the list using \p pred predicate for searching
604 The function is an analog of \ref cds_intrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
605 but \p pred is used for key comparing.
606 \p Less functor has the interface like \p std::less.
607 \p pred must imply the same element order as the comparator used for building the list.
609 template <typename Q, typename Less, typename Func>
610 bool erase_with( Q const& key, Less pred, Func func )
613 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), func );
616 /// Extracts an item from the list
618 @anchor cds_intrusive_MichaelList_rcu_extract
619 The function searches an item with key equal to \p key in the list,
620 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
621 If \p key is not found the function returns an empty \p exempt_ptr.
623 @note The function does NOT dispose the item found. It just unlinks the item from the list
624 and returns a pointer to item found.
625 You shouldn't lock RCU for current thread before calling this function, and you should manually release
626 \p dest exempt pointer outside the RCU lock before reusing it.
629 #include <cds/urcu/general_buffered.h>
630 #include <cds/intrusive/michael_list_rcu.h>
632 typedef cds::urcu::gc< general_buffered<> > rcu;
633 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
635 rcu_michael_list theList;
638 rcu_michael_list::exempt_ptr p1;
640 // The RCU should NOT be locked when extract() is called!
641 assert( !rcu::is_locked() );
643 // You can call extract() function
644 p1 = theList.extract( 10 );
646 // do something with p1
650 // We may safely release p1 here
651 // release() passes the pointer to RCU reclamation cycle:
652 // it invokes RCU retire_ptr function with the disposer you provided for the list.
656 template <typename Q>
657 exempt_ptr extract( Q const& key )
659 return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
662 /// Extracts an item from the list using \p pred predicate for searching
664 This function is the analog for \p extract(Q const&)
666 The \p pred is a predicate used for key comparing.
667 \p Less has the interface like \p std::less.
668 \p pred must imply the same element order as \ref key_comparator.
670 template <typename Q, typename Less>
671 exempt_ptr extract_with( Q const& key, Less pred )
674 return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
677 /// Find the key \p val
678 /** \anchor cds_intrusive_MichaelList_rcu_find_func
679 The function searches the item with key equal to \p key
680 and calls the functor \p f for item found.
681 The interface of \p Func functor is:
684 void operator()( value_type& item, Q& key );
687 where \p item is the item found, \p key is the <tt>find</tt> function argument.
689 The functor can change non-key fields of \p item.
690 The function \p find does not serialize simultaneous access to the list \p item. If such access is
691 possible you must provide your own synchronization schema to exclude unsafe item modifications.
693 The function makes RCU lock internally.
695 The function returns \p true if \p val is found, \p false otherwise.
697 template <typename Q, typename Func>
698 bool find( Q& key, Func f )
700 return find_at( m_pHead, key, key_comparator(), f );
703 template <typename Q, typename Func>
704 bool find( Q const& key, Func f )
706 return find_at( m_pHead, key, key_comparator(), f );
710 /// Finds \p key using \p pred predicate for searching
712 The function is an analog of \p find(Q&, Func)
713 but \p pred is used for key comparing.
714 \p Less functor has the interface like \p std::less.
715 \p pred must imply the same element order as the comparator used for building the list.
717 template <typename Q, typename Less, typename Func>
718 bool find_with( Q& key, Less pred, Func f )
721 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
724 template <typename Q, typename Less, typename Func>
725 bool find_with( Q const& key, Less pred, Func f )
728 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
732 /// Checks whether the list contains \p key
734 The function searches the item with key equal to \p key
735 and returns \p true if it is found, and \p false otherwise.
737 template <typename Q>
738 bool contains( Q const& key )
740 return find_at( m_pHead, key, key_comparator() );
743 template <typename Q>
744 CDS_DEPRECATED("deprecated, use contains()")
745 bool find( Q const& key )
747 return contains( key );
751 /// Checks whether the map contains \p key using \p pred predicate for searching
753 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
754 \p Less functor has the interface like \p std::less.
755 \p Less must imply the same element order as the comparator used for building the list.
757 template <typename Q, typename Less>
758 bool contains( Q const& key, Less pred )
761 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
764 template <typename Q, typename Less>
765 CDS_DEPRECATED("deprecated, use contains()")
766 bool find_with( Q const& key, Less pred )
768 return contains( key, pred );
772 /// Finds \p key and return the item found
773 /** \anchor cds_intrusive_MichaelList_rcu_get
774 The function searches the item with key equal to \p key and returns the pointer to item found.
775 If \p key is not found it returns empty \p raw_ptr object.
777 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
779 RCU should be locked before call of this function.
780 Returned item is valid only while RCU is locked:
782 typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
785 typename ord_list::raw_ptr rp;
788 ord_list::rcu_lock lock;
790 rp = theList.get( 5 );
795 // Unlock RCU by rcu_lock destructor
796 // Node owned by rp can be retired by disposer at any time after RCU has been unlocked
798 // You can manually release rp after RCU-locked section
802 template <typename Q>
803 raw_ptr get( Q const& key )
805 return get_at( m_pHead, key, key_comparator());
808 /// Finds \p key and return the item found
810 The function is an analog of \ref cds_intrusive_MichaelList_rcu_get "get(Q const&)"
811 but \p pred is used for comparing the keys.
813 \p Less functor has the semantics like \p std::less but should take arguments of type \p value_type and \p Q
815 \p pred must imply the same element order as the comparator used for building the list.
817 template <typename Q, typename Less>
818 raw_ptr get_with( Q const& key, Less pred )
821 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
824 /// Clears the list using default disposer
826 The function clears the list using default (provided by \p Traits class template argument) disposer functor.
828 RCU \p synchronize method can be called.
829 Note that depending on RCU type used the \ref disposer invocation can be deferred.
831 The function can throw \p cds::urcu::rcu_deadlock exception if an deadlock is encountered and
832 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
837 check_deadlock_policy::check();
839 marked_node_ptr pHead;
843 pHead = m_pHead.load(memory_model::memory_order_acquire);
846 marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
847 if ( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed ))
849 if ( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
854 dispose_node( pHead.ptr() );
859 /// Check if the list is empty
862 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
865 /// Returns list's item count
867 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
868 this function always returns 0.
870 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
871 is empty. To check list emptyness use \p empty() method.
875 return m_ItemCounter.value();
880 // split-list support
881 bool insert_aux_node( node_type * pNode )
883 return insert_aux_node( m_pHead, pNode );
886 // split-list support
887 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
889 assert( pNode != nullptr );
891 // Hack: convert node_type to value_type.
892 // In principle, auxiliary node can be non-reducible to value_type
893 // We assume that comparator can correctly distinguish between aux and regular node.
894 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
897 bool insert_at( atomic_node_ptr& refHead, value_type& val )
899 position pos( refHead );
902 return insert_at_locked( pos, val );
906 template <typename Func>
907 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
909 link_checker::is_empty( node_traits::to_node_ptr( val ) );
910 position pos( refHead );
915 if ( search( refHead, val, pos, key_comparator()))
918 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
925 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
931 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
934 if ( insert_at_locked( refHead, val ))
935 return iterator( node_traits::to_node_ptr( val ));
939 template <typename Func>
940 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
942 position pos( refHead );
945 return update_at_locked( pos, val, func, bInsert );
949 template <typename Func>
950 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
952 position pos( refHead );
955 std::pair<iterator, bool> ret = update_at_locked( pos, val, func, bInsert );
956 return std::make_pair( ret.first != end(), ret.second );
960 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
962 position pos( refHead );
964 check_deadlock_policy::check();
969 if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
971 if ( !unlink_node( pos, erase_mask )) {
982 template <typename Q, typename Compare, typename Func>
983 bool erase_at( position& pos, Q const& val, Compare cmp, Func f )
986 check_deadlock_policy::check();
992 if ( !search( pos.refHead, val, pos, cmp ) )
994 // store pCur since it may be changed by unlink_node() slow path
996 if ( !unlink_node( pos, erase_mask )) {
1002 f( *node_traits::to_value_ptr( pDel ) );
1008 template <typename Q, typename Compare, typename Func>
1009 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp, Func f )
1011 position pos( refHead );
1012 return erase_at( pos, val, cmp, f );
1015 template <typename Q, typename Compare>
1016 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp )
1018 position pos( refHead );
1019 return erase_at( pos, val, cmp, [](value_type const&){} );
1022 template <typename Q, typename Compare >
1023 value_type * extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1025 position pos( refHead );
1027 assert( !gc::is_locked() ) ; // RCU must not be locked!!!
1029 node_type * pExtracted;
1033 if ( !search( refHead, val, pos, cmp ) )
1035 // store pCur since it may be changed by unlink_node() slow path
1036 pExtracted = pos.pCur;
1037 if ( !unlink_node( pos, extract_mask )) {
1043 value_type * pRet = node_traits::to_value_ptr( pExtracted );
1044 assert( pExtracted->m_pDelChain == nullptr );
1050 template <typename Q, typename Compare, typename Func>
1051 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1053 position pos( refHead );
1057 if ( search( refHead, val, pos, cmp ) ) {
1058 assert( pos.pCur != nullptr );
1059 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1066 template <typename Q, typename Compare>
1067 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1069 position pos( refHead );
1072 return find_at_locked( pos, val, cmp ) != cend();
1076 template <typename Q, typename Compare>
1077 raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1079 // RCU should be locked!
1080 assert(gc::is_locked() );
1082 position pos( refHead );
1084 if ( search( refHead, val, pos, cmp ))
1085 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
1086 return raw_ptr( raw_ptr_disposer( pos ));
1093 template <typename Q, typename Compare>
1094 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1096 // RCU lock should be locked!!!
1097 assert( gc::is_locked() );
1099 atomic_node_ptr * pPrev;
1100 marked_node_ptr pNext;
1101 marked_node_ptr pCur;
1107 pCur = pPrev->load(memory_model::memory_order_acquire);
1111 if ( !pCur.ptr() ) {
1114 pos.pNext = nullptr;
1118 pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
1120 if ( pPrev->load(memory_model::memory_order_acquire) != pCur
1121 || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire))
1127 if ( pNext.bits() ) {
1128 // pCur is marked as deleted. Try to unlink it from the list
1129 if ( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1130 if ( pNext.bits() == erase_mask )
1131 link_to_remove_chain( pos, pCur.ptr() );
1137 assert( pCur.ptr() != nullptr );
1138 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1141 pos.pCur = pCur.ptr();
1142 pos.pNext = pNext.ptr();
1145 pPrev = &( pCur->m_pNext );
1153 bool insert_at_locked( position& pos, value_type& val )
1155 // RCU lock should be locked!!!
1156 assert( gc::is_locked() );
1157 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1160 if ( search( pos.refHead, val, pos, key_comparator() ) )
1163 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1169 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1173 template <typename Func>
1174 std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
1176 // RCU should be locked!!!
1177 assert( gc::is_locked() );
1180 if ( search( pos.refHead, val, pos, key_comparator() ) ) {
1181 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
1183 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1184 return std::make_pair( iterator( pos.pCur ), false );
1188 return std::make_pair( end(), false );
1190 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1192 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
1194 func( true, val , val );
1195 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1198 // clear the next field
1199 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1204 template <typename Q, typename Compare>
1205 const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
1207 assert( gc::is_locked() );
1209 if ( search( pos.refHead, val, pos, cmp ) ) {
1210 assert( pos.pCur != nullptr );
1211 return const_iterator( pos.pCur );
1218 }} // namespace cds::intrusive
1220 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H