3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H
4 #define __CDS_INTRUSIVE_LAZY_LIST_RCU_H
6 #include <cds/intrusive/lazy_list_base.h>
7 #include <cds/urcu/details/check_deadlock.h>
8 #include <cds/details/binary_functor_wrapper.h>
9 #include <cds/urcu/exempt_ptr.h>
11 namespace cds { namespace intrusive {
13 /// Lazy list node for \ref cds_urcu_desc "RCU"
16 - Tag - a tag used to distinguish between different implementation
18 template <class RCU, typename Lock, typename Tag>
19 struct node<cds::urcu::gc<RCU>, Lock, Tag>
21 typedef cds::urcu::gc<RCU> gc ; ///< RCU schema
22 typedef Lock lock_type ; ///< Lock type
23 typedef Tag tag ; ///< tag
25 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
26 typedef CDS_ATOMIC::atomic<marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
28 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the list
29 mutable lock_type m_Lock ; ///< Node lock
31 /// Checks if node is marked
32 bool is_marked() const
34 return m_pNext.load(CDS_ATOMIC::memory_order_relaxed).bits() != 0;
39 : m_pNext( null_ptr<node *>())
42 /// Clears internal fields
45 m_pNext.store( marked_ptr(), CDS_ATOMIC::memory_order_release );
48 } // namespace lazy_list
51 /// Lazy ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
52 /** @ingroup cds_intrusive_list
53 \anchor cds_intrusive_LazyList_rcu
55 Usually, ordered single-linked list is used as a building block for the hash table implementation.
56 The complexity of searching is <tt>O(N)</tt>.
59 - \p RCU - one of \ref cds_urcu_gc "RCU type"
60 - \p T - type to be stored in the list
61 - \p Traits - type traits. See lazy_list::type_traits for explanation.
63 It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
64 argument. Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are:
65 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
66 If the option is not specified, <tt>lazy_list::base_hook<></tt> is used.
67 - opt::compare - key comparison functor. No default functor is provided.
68 If the option is not specified, the opt::less is used.
69 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
70 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
71 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer
72 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
73 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
74 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
75 or opt::v::sequential_consistent (sequentially consisnent memory model).
78 Before including <tt><cds/intrusive/lazy_list_rcu.h></tt> you should include appropriate RCU header file,
79 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
80 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
82 #include <cds/urcu/general_buffered.h>
83 #include <cds/intrusive/lazy_list_rcu.h>
85 // Now, you can declare lazy list for type Foo and default traits:
86 typedef cds::intrusive::LazyList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_lazy_list;
93 #ifdef CDS_DOXYGEN_INVOKED
94 ,class Traits = lazy_list::type_traits
99 class LazyList<cds::urcu::gc<RCU>, T, Traits>
102 typedef T value_type ; ///< type of value stored in the list
103 typedef Traits options ; ///< Traits template parameter
105 typedef typename options::hook hook ; ///< hook type
106 typedef typename hook::node_type node_type ; ///< node type
108 # ifdef CDS_DOXYGEN_INVOKED
109 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
111 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
114 typedef typename options::disposer disposer ; ///< disposer used
115 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
116 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
118 typedef cds::urcu::gc<RCU> gc ; ///< RCU schema
119 typedef typename options::back_off back_off ; ///< back-off strategy (not used)
120 typedef typename options::item_counter item_counter ; ///< Item counting policy used
121 typedef typename options::memory_model memory_model ; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
122 typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
124 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
125 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
128 // Rebind options (split-list support)
129 template <CDS_DECL_OPTIONS8>
130 struct rebind_options {
134 , typename cds::opt::make_options< options, CDS_OPTIONS8>::type
140 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
141 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
144 node_type m_Head ; ///< List head (dummy node)
145 node_type m_Tail; ///< List tail (dummy node)
146 item_counter m_ItemCounter ; ///< Item counter
150 /// Position pointer for item search
152 node_type * pPred ; ///< Previous node
153 node_type * pCur ; ///< Current node
155 /// Locks nodes \p pPred and \p pCur
158 pPred->m_Lock.lock();
162 /// Unlocks nodes \p pPred and \p pCur
165 pCur->m_Lock.unlock();
166 pPred->m_Lock.unlock();
170 class auto_lock_position {
173 auto_lock_position( position& pos )
178 ~auto_lock_position()
184 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
186 # ifndef CDS_CXX11_LAMBDA_SUPPORT
187 struct empty_erase_functor {
188 void operator()( value_type const& item )
196 : pFound(null_ptr<value_type *>())
199 template <typename Q>
200 void operator()( value_type& item, Q& val )
211 static void clear_links( node_type * pNode )
213 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
216 struct clear_and_dispose {
217 void operator()( value_type * p )
219 assert( p != null_ptr<value_type *>() );
220 clear_links( node_traits::to_node_ptr(p));
225 static void dispose_node( node_type * pNode )
228 assert( !gc::is_locked() );
230 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
233 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
235 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
237 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
238 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
241 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
243 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
244 assert( pCur != &m_Tail );
246 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
247 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_relaxed) ; // logically deleting
248 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ) ; // logical deletion + back-link for search
249 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_relaxed); // physically deleting
250 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ) ; // back-link for search
256 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
260 template <bool IsConst>
263 friend class LazyList;
266 value_type * m_pNode;
270 assert( m_pNode != null_ptr<value_type *>() );
272 node_type * pNode = node_traits::to_node_ptr( m_pNode );
273 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
274 if ( pNext != null_ptr<node_type *>() )
275 m_pNode = node_traits::to_value_ptr( pNext );
280 if ( m_pNode != null_ptr<value_type *>() ) {
281 node_type * pNode = node_traits::to_node_ptr( m_pNode );
283 // Dummy tail node could not be marked
284 while ( pNode->is_marked() )
285 pNode = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
287 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
288 m_pNode = node_traits::to_value_ptr( pNode );
292 iterator_type( node_type * pNode )
294 m_pNode = node_traits::to_value_ptr( pNode );
299 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
300 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
303 : m_pNode(null_ptr<value_type *>())
306 iterator_type( iterator_type const& src )
307 : m_pNode( src.m_pNode )
310 value_ptr operator ->() const
315 value_ref operator *() const
317 assert( m_pNode != null_ptr<value_type *>() );
322 iterator_type& operator ++()
330 iterator_type operator ++(int)
332 iterator_type i(*this);
338 iterator_type& operator = (iterator_type const& src)
340 m_pNode = src.m_pNode;
345 bool operator ==(iterator_type<C> const& i ) const
347 return m_pNode == i.m_pNode;
350 bool operator !=(iterator_type<C> const& i ) const
352 return m_pNode != i.m_pNode;
359 typedef iterator_type<false> iterator;
360 /// Const forward iterator
361 typedef iterator_type<true> const_iterator;
363 /// Returns a forward iterator addressing the first element in a list
365 For empty list \code begin() == end() \endcode
369 iterator it( &m_Head );
370 ++it ; // skip dummy head
374 /// Returns an iterator that addresses the location succeeding the last element in a list
376 Do not use the value returned by <tt>end</tt> function to access any item.
378 The returned value can be used only to control reaching the end of the list.
379 For empty list \code begin() == end() \endcode
383 return iterator( &m_Tail );
386 /// Returns a forward const iterator addressing the first element in a list
388 const_iterator begin() const
390 return get_const_begin();
392 const_iterator cbegin()
394 return get_const_begin();
398 /// Returns an const iterator that addresses the location succeeding the last element in a list
400 const_iterator end() const
402 return get_const_end();
404 const_iterator cend()
406 return get_const_end();
412 const_iterator get_const_begin() const
414 const_iterator it( const_cast<node_type *>( &m_Head ));
415 ++it ; // skip dummy head
418 const_iterator get_const_end() const
420 return const_iterator( const_cast<node_type *>( &m_Tail ));
425 /// 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" );
429 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
432 /// Destroys the list object
437 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
438 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
443 The function inserts \p val in the list if the list does not contain
444 an item with key equal to \p val.
446 Returns \p true if \p val is linked into the list, \p false otherwise.
448 bool insert( value_type& val )
450 return insert_at( &m_Head, val );
455 This function is intended for derived non-intrusive containers.
457 The function allows to split new item creating into two part:
458 - create item with key only
459 - insert new item into the list
460 - if inserting is success, calls \p f functor to initialize value-field of \p val.
462 The functor signature is:
464 void func( value_type& val );
466 where \p val is the item inserted.
467 While the functor \p f is working the item \p val is locked.
468 The user-defined functor is called only if the inserting is success and may be passed by reference
469 using <tt>boost::ref</tt>.
471 template <typename Func>
472 bool insert( value_type& val, Func f )
474 return insert_at( &m_Head, val, f );
477 /// Ensures that the \p item exists in the list
479 The operation performs inserting or changing data with lock-free manner.
481 If the item \p val not found in the list, then \p val is inserted into the list.
482 Otherwise, the functor \p func is called with item found.
483 The functor signature is:
486 void operator()( bool bNew, value_type& item, value_type& val );
490 - \p bNew - \p true if the item has been inserted, \p false otherwise
491 - \p item - item of the list
492 - \p val - argument \p val passed into the \p ensure function
493 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
494 refers to the same thing.
496 The functor may change non-key fields of the \p item.
497 While the functor \p f is calling the item \p item is locked.
499 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
501 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
502 \p second is true if new item has been added or \p false if the item with \p key
503 already is in the list.
506 template <typename Func>
507 std::pair<bool, bool> ensure( value_type& val, Func func )
509 return ensure_at( &m_Head, val, func );
512 /// Unlinks the item \p val from the list
514 The function searches the item \p val in the list and unlink it from the list
515 if it is found and it is equal to \p val.
517 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
518 and deletes the item found. \p unlink finds an item by key and deletes it
519 only if \p val is an item of that list, i.e. the pointer to item found
520 is equal to <tt> &val </tt>.
522 The function returns \p true if success and \p false otherwise.
524 RCU \p synchronize method can be called.
525 Note that depending on RCU type used the \ref disposer call can be deferred.
527 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
528 deadlock checking policy is opt::v::rcu_throw_deadlock.
530 bool unlink( value_type& val )
532 return unlink_at( &m_Head, val );
535 /// Deletes the item from the list
536 /** \anchor cds_intrusive_LazyList_rcu_find_erase
537 The function searches an item with key equal to \p val in the list,
538 unlinks it from the list, and returns \p true.
539 If the item with the key equal to \p val is not found the function return \p false.
541 RCU \p synchronize method can be called.
542 Note that depending on RCU type used the \ref disposer call can be deferred.
544 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
545 deadlock checking policy is opt::v::rcu_throw_deadlock.
547 template <typename Q>
548 bool erase( Q const& val )
550 return erase_at( &m_Head, val, key_comparator() );
553 /// Deletes the item from the list using \p pred predicate for searching
555 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
556 but \p pred is used for key comparing.
557 \p Less functor has the interface like \p std::less.
558 \p pred must imply the same element order as the comparator used for building the list.
560 template <typename Q, typename Less>
561 bool erase_with( Q const& val, Less pred )
563 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>());
567 /// Deletes the item from the list
568 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
569 The function searches an item with key equal to \p val in the list,
570 call \p func functor with item found, unlinks it from the list, and returns \p true.
571 The \p Func interface is
574 void operator()( value_type const& item );
577 The functor may be passed by reference using <tt>boost:ref</tt>
579 If the item with the key equal to \p val is not found the function return \p false.
581 RCU \p synchronize method can be called.
582 Note that depending on RCU type used the \ref disposer call can be deferred.
584 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
585 deadlock checking policy is opt::v::rcu_throw_deadlock.
587 template <typename Q, typename Func>
588 bool erase( Q const& val, Func func )
590 return erase_at( &m_Head, val, key_comparator(), func );
593 /// Deletes the item from the list using \p pred predicate for searching
595 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
596 but \p pred is used for key comparing.
597 \p Less functor has the interface like \p std::less.
598 \p pred must imply the same element order as the comparator used for building the list.
600 template <typename Q, typename Less, typename Func>
601 bool erase_with( Q const& val, Less pred, Func func )
603 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), func );
606 /// Extracts an item from the list
608 \anchor cds_intrusive_LazyList_rcu_extract
609 The function searches an item with key equal to \p val in the list,
610 unlinks it from the list, and returns pointer to an item found in \p dest parameter.
611 If the item with the key equal to \p val is not found the function returns \p false,
614 @note The function does NOT call RCU read-side lock or synchronization,
615 and does NOT dispose the item found. It just excludes the item from the list
616 and returns a pointer to item found.
617 You should lock RCU before calling this function, and you should manually synchronize RCU
618 outside the RCU lock region before reusing returned pointer.
621 #include <cds/urcu/general_buffered.h>
622 #include <cds/intrusive/lazy_list_rcu.h>
624 typedef cds::urcu::gc< general_buffered<> > rcu;
625 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
627 rcu_lazy_list theList;
630 rcu_lazy_list::exempt_ptr p1;
632 // first, we should lock RCU
635 // Now, you can apply extract function
636 // Note that you must not delete the item found inside the RCU lock
637 if ( theList.extract( p1, 10 )) {
638 // do something with p1
643 // We may safely release p1 here
644 // release() passes the pointer to RCU reclamation cycle:
645 // it invokes RCU retire_ptr function with the disposer you provided for the list.
649 template <typename Q>
650 bool extract( exempt_ptr& dest, Q const& val )
652 dest = extract_at( &m_Head, val, key_comparator() );
653 return !dest.empty();
656 /// Extracts an item from the list using \p pred predicate for searching
658 This function is the analog for \ref cds_intrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
660 The \p pred is a predicate used for key comparing.
661 \p Less has the interface like \p std::less.
662 \p pred must imply the same element order as \ref key_comparator.
664 template <typename Q, typename Less>
665 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
667 dest = extract_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
668 return !dest.empty();
671 /// Finds the key \p val
672 /** \anchor cds_intrusive_LazyList_rcu_find_func
673 The function searches the item with key equal to \p val
674 and calls the functor \p f for item found.
675 The interface of \p Func functor is:
678 void operator()( value_type& item, Q& val );
681 where \p item is the item found, \p val is the <tt>find</tt> function argument.
683 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
685 The functor may change non-key fields of \p item.
686 While the functor \p f is calling the item found \p item is locked.
688 The function returns \p true if \p val is found, \p false otherwise.
690 template <typename Q, typename Func>
691 bool find( Q& val, Func f ) const
693 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator(), f );
696 /// Finds the key \p val using \p pred predicate for searching
698 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)"
699 but \p pred is used for key comparing.
700 \p Less functor has the interface like \p std::less.
701 \p pred must imply the same element order as the comparator used for building the list.
703 template <typename Q, typename Less, typename Func>
704 bool find_with( Q& val, Less pred, Func f ) const
706 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
709 /// Finds the key \p val
710 /** \anchor cds_intrusive_LazyList_rcu_find_cfunc
711 The function searches the item with key equal to \p val
712 and calls the functor \p f for item found.
713 The interface of \p Func functor is:
716 void operator()( value_type& item, Q const& val );
719 where \p item is the item found, \p val is the <tt>find</tt> function argument.
721 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
723 The functor may change non-key fields of \p item.
724 While the functor \p f is calling the item found \p item is locked.
726 The function returns \p true if \p val is found, \p false otherwise.
728 template <typename Q, typename Func>
729 bool find( Q const& val, Func f ) const
731 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator(), f );
734 /// Finds the key \p val using \p pred predicate for searching
736 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_cfunc "find(Q&, Func)"
737 but \p pred is used for key comparing.
738 \p Less functor has the interface like \p std::less.
739 \p pred must imply the same element order as the comparator used for building the list.
741 template <typename Q, typename Less, typename Func>
742 bool find_with( Q const& val, Less pred, Func f ) const
744 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
747 /// Finds the key \p val
748 /** \anchor cds_intrusive_LazyList_rcu_find_val
749 The function searches the item with key equal to \p val
750 and returns \p true if \p val found or \p false otherwise.
752 template <typename Q>
753 bool find( Q const& val ) const
755 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator() );
758 /// Finds the key \p val using \p pred predicate for searching
760 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
761 but \p pred is used for key comparing.
762 \p Less functor has the interface like \p std::less.
763 \p pred must imply the same element order as the comparator used for building the list.
765 template <typename Q, typename Less>
766 bool find_with( Q const& val, Less pred ) const
768 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>() );
771 /// Finds the key \p val and return the item found
772 /** \anchor cds_intrusive_LazyList_rcu_get
773 The function searches the item with key equal to \p val and returns the pointer to item found.
774 If \p val is not found it returns \p NULL.
776 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
778 RCU should be locked before call of this function.
779 Returned item is valid only while RCU is locked:
781 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
786 ord_list::rcu_lock lock;
788 foo * pVal = theList.get( 5 );
793 // Unlock RCU by rcu_lock destructor
794 // pVal can be retired by disposer at any time after RCU has been unlocked
798 template <typename Q>
799 value_type * get( Q const& val ) const
801 return get_at( const_cast<node_type *>( &m_Head ), val, key_comparator());
804 /// Finds the key \p val and return the item found
806 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
807 but \p pred is used for comparing the keys.
809 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
811 \p pred must imply the same element order as the comparator used for building the list.
813 template <typename Q, typename Less>
814 value_type * get_with( Q const& val, Less pred ) const
816 return get_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>());
819 /// Clears the list using default disposer
821 The function clears the list using default (provided in class template) disposer functor.
823 RCU \p synchronize method can be called.
824 Note that depending on RCU type used the \ref disposer call can be deferred.
826 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
827 deadlock checking policy is opt::v::rcu_throw_deadlock.
832 check_deadlock_policy::check();
838 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
839 if ( pHead == &m_Tail )
842 m_Head.m_Lock.lock();
843 pHead->m_Lock.lock();
845 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
846 unlink_node( &m_Head, pHead, &m_Head );
848 pHead->m_Lock.unlock();
849 m_Head.m_Lock.unlock();
853 dispose_node( pHead );
858 /// Checks if the list is empty
861 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
864 /// Returns list's item count
866 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
867 this function always returns 0.
869 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
870 is empty. To check list emptyness use \ref empty() method.
874 return m_ItemCounter.value();
879 // split-list support
880 bool insert_aux_node( node_type * pNode )
882 return insert_aux_node( &m_Head, pNode );
885 // split-list support
886 bool insert_aux_node( node_type * pHead, node_type * pNode )
888 assert( pHead != null_ptr<node_type *>() );
889 assert( pNode != null_ptr<node_type *>() );
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 aux and regular node.
894 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
897 bool insert_at( node_type * pHead, value_type& val, bool bLock = true )
899 link_checker::is_empty( node_traits::to_node_ptr( val ) );
905 search( pHead, val, pos );
907 auto_lock_position alp( pos );
908 if ( validate( pos.pPred, pos.pCur )) {
909 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
910 // failed: key already in list
914 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
923 template <typename Func>
924 bool insert_at( node_type * pHead, value_type& val, Func f )
926 link_checker::is_empty( node_traits::to_node_ptr( val ) );
932 search( pHead, val, pos );
934 auto_lock_position alp( pos );
935 if ( validate( pos.pPred, pos.pCur )) {
936 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
937 // failed: key already in list
941 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
942 cds::unref(f)( val );
951 iterator insert_at_( node_type * pHead, value_type& val, bool bLock = true )
954 if ( insert_at( pHead, val, false ))
955 return iterator( node_traits::to_node_ptr( val ));
960 template <typename Func>
961 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func, bool bLock = true )
968 search( pHead, val, pos );
970 auto_lock_position alp( pos );
971 if ( validate( pos.pPred, pos.pCur )) {
972 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
973 // key already in the list
975 cds::unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
976 return std::make_pair( iterator( pos.pCur ), false );
980 link_checker::is_empty( node_traits::to_node_ptr( val ) );
982 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
983 cds::unref(func)( true, val, val );
985 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
992 template <typename Func>
993 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func, bool bLock = true )
996 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func, false );
997 return std::make_pair( ret.first != end(), ret.second );
1000 bool unlink_at( node_type * pHead, value_type& val )
1004 check_deadlock_policy::check();
1010 search( pHead, val, pos );
1012 auto_lock_position alp( pos );
1013 if ( validate( pos.pPred, pos.pCur ) ) {
1014 if ( pos.pCur != &m_Tail
1015 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1016 && node_traits::to_value_ptr( pos.pCur ) == &val )
1019 unlink_node( pos.pPred, pos.pCur, pHead );
1030 if ( nResult > 0 ) {
1031 dispose_node( pos.pCur );
1039 template <typename Q, typename Compare, typename Func>
1040 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
1042 check_deadlock_policy::check();
1048 search( pHead, val, pos, cmp );
1050 auto_lock_position alp( pos );
1051 if ( validate( pos.pPred, pos.pCur )) {
1052 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1054 unlink_node( pos.pPred, pos.pCur, pHead );
1055 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
1067 if ( nResult > 0 ) {
1068 dispose_node( pos.pCur );
1076 template <typename Q, typename Compare, typename Func>
1077 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1080 return erase_at( pHead, val, cmp, f, pos );
1083 template <typename Q, typename Compare>
1084 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1087 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1088 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1090 return erase_at( pHead, val, cmp, empty_erase_functor(), pos );
1094 template <typename Q, typename Compare>
1095 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1098 assert( gc::is_locked() ) ; // RCU must be locked!!!
1101 search( pHead, val, pos, cmp );
1104 auto_lock_position alp( pos );
1105 if ( validate( pos.pPred, pos.pCur )) {
1106 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1108 unlink_node( pos.pPred, pos.pCur, pHead );
1120 return node_traits::to_value_ptr( pos.pCur );
1121 return null_ptr<value_type *>();
1126 template <typename Q, typename Compare, typename Func>
1127 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
1131 rcu_lock l( bLock );
1132 search( pHead, val, pos, cmp );
1133 if ( pos.pCur != &m_Tail ) {
1134 cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1135 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1137 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
1144 template <typename Q, typename Compare>
1145 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1148 return find_at_( pHead, val, cmp ) != end();
1151 template <typename Q, typename Compare>
1152 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1154 assert( gc::is_locked() );
1158 search( pHead, val, pos, cmp );
1159 if ( pos.pCur != &m_Tail ) {
1160 cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1161 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1163 return const_iterator( pos.pCur );
1169 template <typename Q, typename Compare>
1170 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1172 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1173 value_type * pFound = null_ptr<value_type *>();
1174 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1175 ? pFound : null_ptr<value_type *>();
1178 return find_at( pHead , val, cmp, cds::ref(gf) ) ? gf.pFound : null_ptr<value_type *>();
1186 template <typename Q>
1187 void search( node_type * pHead, Q const& key, position& pos ) const
1189 search( pHead, key, pos, key_comparator() );
1192 template <typename Q, typename Compare>
1193 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1195 // RCU should be locked!!!
1196 assert( gc::is_locked() );
1198 node_type const* pTail = &m_Tail;
1200 marked_node_ptr pCur(pHead);
1201 marked_node_ptr pPrev(pHead);
1203 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1205 pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1208 pos.pCur = pCur.ptr();
1209 pos.pPred = pPrev.ptr();
1212 static bool validate( node_type * pPred, node_type * pCur )
1214 // RCU lock should be locked!!!
1215 assert( gc::is_locked() );
1217 return !pPred->is_marked()
1218 && !pCur->is_marked()
1219 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1225 }} // namespace cds::intrusive
1227 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H