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 atomics::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(atomics::memory_order_relaxed).bits() != 0;
42 /// Clears internal fields
45 m_pNext.store( marked_ptr(), atomics::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 <typename... Options>
130 struct rebind_options {
134 , typename cds::opt::make_options< options, Options...>::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;
189 static void clear_links( node_type * pNode )
191 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
194 struct clear_and_dispose {
195 void operator()( value_type * p )
197 assert( p != nullptr );
198 clear_links( node_traits::to_node_ptr(p));
203 static void dispose_node( node_type * pNode )
206 assert( !gc::is_locked() );
208 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
211 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
213 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
215 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
216 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
219 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
221 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
222 assert( pCur != &m_Tail );
224 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
225 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_relaxed) ; // logically deleting
226 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ) ; // logical deletion + back-link for search
227 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_relaxed); // physically deleting
228 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ) ; // back-link for search
234 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
238 template <bool IsConst>
241 friend class LazyList;
244 value_type * m_pNode;
248 assert( m_pNode != nullptr );
250 node_type * pNode = node_traits::to_node_ptr( m_pNode );
251 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
252 if ( pNext != nullptr )
253 m_pNode = node_traits::to_value_ptr( pNext );
258 if ( m_pNode != nullptr ) {
259 node_type * pNode = node_traits::to_node_ptr( m_pNode );
261 // Dummy tail node could not be marked
262 while ( pNode->is_marked() )
263 pNode = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
265 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
266 m_pNode = node_traits::to_value_ptr( pNode );
270 iterator_type( node_type * pNode )
272 m_pNode = node_traits::to_value_ptr( pNode );
277 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
278 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
284 iterator_type( iterator_type const& src )
285 : m_pNode( src.m_pNode )
288 value_ptr operator ->() const
293 value_ref operator *() const
295 assert( m_pNode != nullptr );
300 iterator_type& operator ++()
308 iterator_type operator ++(int)
310 iterator_type i(*this);
316 iterator_type& operator = (iterator_type const& src)
318 m_pNode = src.m_pNode;
323 bool operator ==(iterator_type<C> const& i ) const
325 return m_pNode == i.m_pNode;
328 bool operator !=(iterator_type<C> const& i ) const
330 return m_pNode != i.m_pNode;
337 typedef iterator_type<false> iterator;
338 /// Const forward iterator
339 typedef iterator_type<true> const_iterator;
341 /// Returns a forward iterator addressing the first element in a list
343 For empty list \code begin() == end() \endcode
347 iterator it( &m_Head );
348 ++it ; // skip dummy head
352 /// Returns an iterator that addresses the location succeeding the last element in a list
354 Do not use the value returned by <tt>end</tt> function to access any item.
356 The returned value can be used only to control reaching the end of the list.
357 For empty list \code begin() == end() \endcode
361 return iterator( &m_Tail );
364 /// Returns a forward const iterator addressing the first element in a list
366 const_iterator begin() const
368 return get_const_begin();
370 const_iterator cbegin()
372 return get_const_begin();
376 /// Returns an const iterator that addresses the location succeeding the last element in a list
378 const_iterator end() const
380 return get_const_end();
382 const_iterator cend()
384 return get_const_end();
390 const_iterator get_const_begin() const
392 const_iterator it( const_cast<node_type *>( &m_Head ));
393 ++it ; // skip dummy head
396 const_iterator get_const_end() const
398 return const_iterator( const_cast<node_type *>( &m_Tail ));
403 /// Default constructor initializes empty list
406 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
407 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
410 /// Destroys the list object
415 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
416 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
421 The function inserts \p val in the list if the list does not contain
422 an item with key equal to \p val.
424 Returns \p true if \p val is linked into the list, \p false otherwise.
426 bool insert( value_type& val )
428 return insert_at( &m_Head, val );
433 This function is intended for derived non-intrusive containers.
435 The function allows to split new item creating into two part:
436 - create item with key only
437 - insert new item into the list
438 - if inserting is success, calls \p f functor to initialize value-field of \p val.
440 The functor signature is:
442 void func( value_type& val );
444 where \p val is the item inserted.
445 While the functor \p f is working the item \p val is locked.
446 The user-defined functor is called only if the inserting is success and may be passed by reference
447 using <tt>boost::ref</tt>.
449 template <typename Func>
450 bool insert( value_type& val, Func f )
452 return insert_at( &m_Head, val, f );
455 /// Ensures that the \p item exists in the list
457 The operation performs inserting or changing data with lock-free manner.
459 If the item \p val not found in the list, then \p val is inserted into the list.
460 Otherwise, the functor \p func is called with item found.
461 The functor signature is:
464 void operator()( bool bNew, value_type& item, value_type& val );
468 - \p bNew - \p true if the item has been inserted, \p false otherwise
469 - \p item - item of the list
470 - \p val - argument \p val passed into the \p ensure function
471 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
472 refers to the same thing.
474 The functor may change non-key fields of the \p item.
475 While the functor \p f is calling the item \p item is locked.
477 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
479 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
480 \p second is true if new item has been added or \p false if the item with \p key
481 already is in the list.
484 template <typename Func>
485 std::pair<bool, bool> ensure( value_type& val, Func func )
487 return ensure_at( &m_Head, val, func );
490 /// Unlinks the item \p val from the list
492 The function searches the item \p val in the list and unlink it from the list
493 if it is found and it is equal to \p val.
495 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
496 and deletes the item found. \p unlink finds an item by key and deletes it
497 only if \p val is an item of that list, i.e. the pointer to item found
498 is equal to <tt> &val </tt>.
500 The function returns \p true if success and \p false otherwise.
502 RCU \p synchronize method can be called.
503 Note that depending on RCU type used the \ref disposer call can be deferred.
505 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
506 deadlock checking policy is opt::v::rcu_throw_deadlock.
508 bool unlink( value_type& val )
510 return unlink_at( &m_Head, val );
513 /// Deletes the item from the list
514 /** \anchor cds_intrusive_LazyList_rcu_find_erase
515 The function searches an item with key equal to \p val in the list,
516 unlinks it from the list, and returns \p true.
517 If the item with the key equal to \p val is not found the function return \p false.
519 RCU \p synchronize method can be called.
520 Note that depending on RCU type used the \ref disposer call can be deferred.
522 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
523 deadlock checking policy is opt::v::rcu_throw_deadlock.
525 template <typename Q>
526 bool erase( Q const& val )
528 return erase_at( &m_Head, val, key_comparator() );
531 /// Deletes the item from the list using \p pred predicate for searching
533 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
534 but \p pred is used for key comparing.
535 \p Less functor has the interface like \p std::less.
536 \p pred must imply the same element order as the comparator used for building the list.
538 template <typename Q, typename Less>
539 bool erase_with( Q const& val, Less pred )
541 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>());
545 /// Deletes the item from the list
546 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
547 The function searches an item with key equal to \p val in the list,
548 call \p func functor with item found, unlinks it from the list, and returns \p true.
549 The \p Func interface is
552 void operator()( value_type const& item );
555 The functor may be passed by reference using <tt>boost:ref</tt>
557 If the item with the key equal to \p val is not found the function return \p false.
559 RCU \p synchronize method can be called.
560 Note that depending on RCU type used the \ref disposer call can be deferred.
562 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
563 deadlock checking policy is opt::v::rcu_throw_deadlock.
565 template <typename Q, typename Func>
566 bool erase( Q const& val, Func func )
568 return erase_at( &m_Head, val, key_comparator(), func );
571 /// Deletes the item from the list using \p pred predicate for searching
573 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
574 but \p pred is used for key comparing.
575 \p Less functor has the interface like \p std::less.
576 \p pred must imply the same element order as the comparator used for building the list.
578 template <typename Q, typename Less, typename Func>
579 bool erase_with( Q const& val, Less pred, Func func )
581 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), func );
584 /// Extracts an item from the list
586 \anchor cds_intrusive_LazyList_rcu_extract
587 The function searches an item with key equal to \p val in the list,
588 unlinks it from the list, and returns pointer to an item found in \p dest parameter.
589 If the item with the key equal to \p val is not found the function returns \p false,
592 @note The function does NOT call RCU read-side lock or synchronization,
593 and does NOT dispose the item found. It just excludes the item from the list
594 and returns a pointer to item found.
595 You should lock RCU before calling this function, and you should manually synchronize RCU
596 outside the RCU lock region before reusing returned pointer.
599 #include <cds/urcu/general_buffered.h>
600 #include <cds/intrusive/lazy_list_rcu.h>
602 typedef cds::urcu::gc< general_buffered<> > rcu;
603 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
605 rcu_lazy_list theList;
608 rcu_lazy_list::exempt_ptr p1;
610 // first, we should lock RCU
613 // Now, you can apply extract function
614 // Note that you must not delete the item found inside the RCU lock
615 if ( theList.extract( p1, 10 )) {
616 // do something with p1
621 // We may safely release p1 here
622 // release() passes the pointer to RCU reclamation cycle:
623 // it invokes RCU retire_ptr function with the disposer you provided for the list.
627 template <typename Q>
628 bool extract( exempt_ptr& dest, Q const& val )
630 dest = extract_at( &m_Head, val, key_comparator() );
631 return !dest.empty();
634 /// Extracts an item from the list using \p pred predicate for searching
636 This function is the analog for \ref cds_intrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
638 The \p pred is a predicate used for key comparing.
639 \p Less has the interface like \p std::less.
640 \p pred must imply the same element order as \ref key_comparator.
642 template <typename Q, typename Less>
643 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
645 dest = extract_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
646 return !dest.empty();
649 /// Finds the key \p val
650 /** \anchor cds_intrusive_LazyList_rcu_find_func
651 The function searches the item with key equal to \p val
652 and calls the functor \p f for item found.
653 The interface of \p Func functor is:
656 void operator()( value_type& item, Q& val );
659 where \p item is the item found, \p val is the <tt>find</tt> function argument.
661 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
663 The functor may change non-key fields of \p item.
664 While the functor \p f is calling the item found \p item is locked.
666 The function returns \p true if \p val is found, \p false otherwise.
668 template <typename Q, typename Func>
669 bool find( Q& val, Func f ) const
671 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator(), f );
674 /// Finds the key \p val using \p pred predicate for searching
676 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)"
677 but \p pred is used for key comparing.
678 \p Less functor has the interface like \p std::less.
679 \p pred must imply the same element order as the comparator used for building the list.
681 template <typename Q, typename Less, typename Func>
682 bool find_with( Q& val, Less pred, Func f ) const
684 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
687 /// Finds the key \p val
688 /** \anchor cds_intrusive_LazyList_rcu_find_cfunc
689 The function searches the item with key equal to \p val
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 const& val );
697 where \p item is the item found, \p val is the <tt>find</tt> function argument.
699 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
701 The functor may change non-key fields of \p item.
702 While the functor \p f is calling the item found \p item is locked.
704 The function returns \p true if \p val is found, \p false otherwise.
706 template <typename Q, typename Func>
707 bool find( Q const& val, Func f ) const
709 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator(), f );
712 /// Finds the key \p val using \p pred predicate for searching
714 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_cfunc "find(Q&, Func)"
715 but \p pred is used for key comparing.
716 \p Less functor has the interface like \p std::less.
717 \p pred must imply the same element order as the comparator used for building the list.
719 template <typename Q, typename Less, typename Func>
720 bool find_with( Q const& val, Less pred, Func f ) const
722 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
725 /// Finds the key \p val
726 /** \anchor cds_intrusive_LazyList_rcu_find_val
727 The function searches the item with key equal to \p val
728 and returns \p true if \p val found or \p false otherwise.
730 template <typename Q>
731 bool find( Q const& val ) const
733 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator() );
736 /// Finds the key \p val using \p pred predicate for searching
738 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
739 but \p pred is used for key comparing.
740 \p Less functor has the interface like \p std::less.
741 \p pred must imply the same element order as the comparator used for building the list.
743 template <typename Q, typename Less>
744 bool find_with( Q const& val, Less pred ) const
746 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>() );
749 /// Finds the key \p val and return the item found
750 /** \anchor cds_intrusive_LazyList_rcu_get
751 The function searches the item with key equal to \p val and returns the pointer to item found.
752 If \p val is not found it returns \p nullptr.
754 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
756 RCU should be locked before call of this function.
757 Returned item is valid only while RCU is locked:
759 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
764 ord_list::rcu_lock lock;
766 foo * pVal = theList.get( 5 );
771 // Unlock RCU by rcu_lock destructor
772 // pVal can be retired by disposer at any time after RCU has been unlocked
776 template <typename Q>
777 value_type * get( Q const& val ) const
779 return get_at( const_cast<node_type *>( &m_Head ), val, key_comparator());
782 /// Finds the key \p val and return the item found
784 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
785 but \p pred is used for comparing the keys.
787 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
789 \p pred must imply the same element order as the comparator used for building the list.
791 template <typename Q, typename Less>
792 value_type * get_with( Q const& val, Less pred ) const
794 return get_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>());
797 /// Clears the list using default disposer
799 The function clears the list using default (provided in class template) disposer functor.
801 RCU \p synchronize method can be called.
802 Note that depending on RCU type used the \ref disposer call can be deferred.
804 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
805 deadlock checking policy is opt::v::rcu_throw_deadlock.
810 check_deadlock_policy::check();
816 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
817 if ( pHead == &m_Tail )
820 m_Head.m_Lock.lock();
821 pHead->m_Lock.lock();
823 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
824 unlink_node( &m_Head, pHead, &m_Head );
826 pHead->m_Lock.unlock();
827 m_Head.m_Lock.unlock();
831 dispose_node( pHead );
836 /// Checks if the list is empty
839 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
842 /// Returns list's item count
844 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
845 this function always returns 0.
847 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
848 is empty. To check list emptyness use \ref empty() method.
852 return m_ItemCounter.value();
857 // split-list support
858 bool insert_aux_node( node_type * pNode )
860 return insert_aux_node( &m_Head, pNode );
863 // split-list support
864 bool insert_aux_node( node_type * pHead, node_type * pNode )
866 assert( pHead != nullptr );
867 assert( pNode != nullptr );
869 // Hack: convert node_type to value_type.
870 // In principle, auxiliary node can be non-reducible to value_type
871 // We assume that comparator can correctly distinguish aux and regular node.
872 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
875 bool insert_at( node_type * pHead, value_type& val, bool bLock = true )
877 link_checker::is_empty( node_traits::to_node_ptr( val ) );
883 search( pHead, val, pos );
885 auto_lock_position alp( pos );
886 if ( validate( pos.pPred, pos.pCur )) {
887 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
888 // failed: key already in list
892 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
901 template <typename Func>
902 bool insert_at( node_type * pHead, value_type& val, Func f )
904 link_checker::is_empty( node_traits::to_node_ptr( val ) );
910 search( pHead, val, pos );
912 auto_lock_position alp( pos );
913 if ( validate( pos.pPred, pos.pCur )) {
914 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
915 // failed: key already in list
919 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
920 cds::unref(f)( val );
929 iterator insert_at_( node_type * pHead, value_type& val, bool bLock = true )
932 if ( insert_at( pHead, val, false ))
933 return iterator( node_traits::to_node_ptr( val ));
938 template <typename Func>
939 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func, bool bLock = true )
946 search( pHead, val, pos );
948 auto_lock_position alp( pos );
949 if ( validate( pos.pPred, pos.pCur )) {
950 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
951 // key already in the list
953 cds::unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
954 return std::make_pair( iterator( pos.pCur ), false );
958 link_checker::is_empty( node_traits::to_node_ptr( val ) );
960 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
961 cds::unref(func)( true, val, val );
963 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
970 template <typename Func>
971 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func, bool bLock = true )
974 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func, false );
975 return std::make_pair( ret.first != end(), ret.second );
978 bool unlink_at( node_type * pHead, value_type& val )
982 check_deadlock_policy::check();
988 search( pHead, val, pos );
990 auto_lock_position alp( pos );
991 if ( validate( pos.pPred, pos.pCur ) ) {
992 if ( pos.pCur != &m_Tail
993 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
994 && node_traits::to_value_ptr( pos.pCur ) == &val )
997 unlink_node( pos.pPred, pos.pCur, pHead );
1008 if ( nResult > 0 ) {
1009 dispose_node( pos.pCur );
1017 template <typename Q, typename Compare, typename Func>
1018 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
1020 check_deadlock_policy::check();
1026 search( pHead, val, pos, cmp );
1028 auto_lock_position alp( pos );
1029 if ( validate( pos.pPred, pos.pCur )) {
1030 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1032 unlink_node( pos.pPred, pos.pCur, pHead );
1033 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
1045 if ( nResult > 0 ) {
1046 dispose_node( pos.pCur );
1054 template <typename Q, typename Compare, typename Func>
1055 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1058 return erase_at( pHead, val, cmp, f, pos );
1061 template <typename Q, typename Compare>
1062 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1065 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1068 template <typename Q, typename Compare>
1069 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1072 assert( gc::is_locked() ) ; // RCU must be locked!!!
1075 search( pHead, val, pos, cmp );
1078 auto_lock_position alp( pos );
1079 if ( validate( pos.pPred, pos.pCur )) {
1080 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1082 unlink_node( pos.pPred, pos.pCur, pHead );
1094 return node_traits::to_value_ptr( pos.pCur );
1100 template <typename Q, typename Compare, typename Func>
1101 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
1105 rcu_lock l( bLock );
1106 search( pHead, val, pos, cmp );
1107 if ( pos.pCur != &m_Tail ) {
1108 cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1109 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1111 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
1118 template <typename Q, typename Compare>
1119 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1122 return find_at_( pHead, val, cmp ) != end();
1125 template <typename Q, typename Compare>
1126 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1128 assert( gc::is_locked() );
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 return const_iterator( pos.pCur );
1143 template <typename Q, typename Compare>
1144 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1146 value_type * pFound = nullptr;
1147 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1155 template <typename Q>
1156 void search( node_type * pHead, Q const& key, position& pos ) const
1158 search( pHead, key, pos, key_comparator() );
1161 template <typename Q, typename Compare>
1162 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1164 // RCU should be locked!!!
1165 assert( gc::is_locked() );
1167 node_type const* pTail = &m_Tail;
1169 marked_node_ptr pCur(pHead);
1170 marked_node_ptr pPrev(pHead);
1172 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1174 pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1177 pos.pCur = pCur.ptr();
1178 pos.pPred = pPrev.ptr();
1181 static bool validate( node_type * pPred, node_type * pCur )
1183 // RCU lock should be locked!!!
1184 assert( gc::is_locked() );
1186 return !pPred->is_marked()
1187 && !pCur->is_marked()
1188 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1194 }} // namespace cds::intrusive
1196 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H