3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H
4 #define __CDS_INTRUSIVE_LAZY_LIST_RCU_H
6 #include <mutex> // unique_lock
7 #include <cds/intrusive/details/lazy_list_base.h>
8 #include <cds/urcu/details/check_deadlock.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/exempt_ptr.h>
12 namespace cds { namespace intrusive {
14 /// Lazy list node for \ref cds_urcu_desc "RCU"
17 - Tag - a tag used to distinguish between different implementation
19 template <class RCU, typename Lock, typename Tag>
20 struct node<cds::urcu::gc<RCU>, Lock, Tag>
22 typedef cds::urcu::gc<RCU> gc ; ///< RCU schema
23 typedef Lock lock_type ; ///< Lock type
24 typedef Tag tag ; ///< tag
26 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
27 typedef atomics::atomic<marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
29 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the list
30 mutable lock_type m_Lock ; ///< Node lock
32 /// Checks if node is marked
33 bool is_marked() const
35 return m_pNext.load(atomics::memory_order_relaxed).bits() != 0;
43 /// Clears internal fields
46 m_pNext.store( marked_ptr(), atomics::memory_order_release );
49 } // namespace lazy_list
52 /// Lazy ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
53 /** @ingroup cds_intrusive_list
54 \anchor cds_intrusive_LazyList_rcu
56 Usually, ordered single-linked list is used as a building block for the hash table implementation.
57 The complexity of searching is <tt>O(N)</tt>.
60 - \p RCU - one of \ref cds_urcu_gc "RCU type"
61 - \p T - type to be stored in the list
62 - \p Traits - type traits. See lazy_list::type_traits for explanation.
64 It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
65 argument. Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are:
66 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
67 If the option is not specified, <tt>lazy_list::base_hook<></tt> is used.
68 - opt::compare - key comparison functor. No default functor is provided.
69 If the option is not specified, the opt::less is used.
70 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
71 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
72 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer
73 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
74 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
75 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
76 or opt::v::sequential_consistent (sequentially consisnent memory model).
79 Before including <tt><cds/intrusive/lazy_list_rcu.h></tt> you should include appropriate RCU header file,
80 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
81 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
83 #include <cds/urcu/general_buffered.h>
84 #include <cds/intrusive/lazy_list_rcu.h>
86 // Now, you can declare lazy list for type Foo and default traits:
87 typedef cds::intrusive::LazyList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_lazy_list;
94 #ifdef CDS_DOXYGEN_INVOKED
95 ,class Traits = lazy_list::type_traits
100 class LazyList<cds::urcu::gc<RCU>, T, Traits>
103 typedef T value_type ; ///< type of value stored in the list
104 typedef Traits options ; ///< Traits template parameter
106 typedef typename options::hook hook ; ///< hook type
107 typedef typename hook::node_type node_type ; ///< node type
109 # ifdef CDS_DOXYGEN_INVOKED
110 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
112 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
115 typedef typename options::disposer disposer ; ///< disposer used
116 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
117 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
119 typedef cds::urcu::gc<RCU> gc ; ///< RCU schema
120 typedef typename options::back_off back_off ; ///< back-off strategy (not used)
121 typedef typename options::item_counter item_counter ; ///< Item counting policy used
122 typedef typename options::memory_model memory_model ; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
123 typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
125 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
126 static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
129 // Rebind options (split-list support)
130 template <typename... Options>
131 struct rebind_options {
135 , typename cds::opt::make_options< options, Options...>::type
141 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
142 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
145 node_type m_Head ; ///< List head (dummy node)
146 node_type m_Tail; ///< List tail (dummy node)
147 item_counter m_ItemCounter ; ///< Item counter
151 /// Position pointer for item search
153 node_type * pPred ; ///< Previous node
154 node_type * pCur ; ///< Current node
156 /// Locks nodes \p pPred and \p pCur
159 pPred->m_Lock.lock();
163 /// Unlocks nodes \p pPred and \p pCur
166 pCur->m_Lock.unlock();
167 pPred->m_Lock.unlock();
171 class auto_lock_position {
174 auto_lock_position( position& pos )
179 ~auto_lock_position()
185 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
190 static void clear_links( node_type * pNode )
192 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
195 struct clear_and_dispose {
196 void operator()( value_type * p )
198 assert( p != nullptr );
199 clear_links( node_traits::to_node_ptr(p));
204 static void dispose_node( node_type * pNode )
207 assert( !gc::is_locked() );
209 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
212 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
214 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
216 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
217 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
220 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
222 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
223 assert( pCur != &m_Tail );
225 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
226 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_relaxed) ; // logically deleting
227 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ) ; // logical deletion + back-link for search
228 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_relaxed); // physically deleting
229 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ) ; // back-link for search
235 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
239 template <bool IsConst>
242 friend class LazyList;
245 value_type * m_pNode;
249 assert( m_pNode != nullptr );
251 node_type * pNode = node_traits::to_node_ptr( m_pNode );
252 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
253 if ( pNext != nullptr )
254 m_pNode = node_traits::to_value_ptr( pNext );
259 if ( m_pNode != nullptr ) {
260 node_type * pNode = node_traits::to_node_ptr( m_pNode );
262 // Dummy tail node could not be marked
263 while ( pNode->is_marked() )
264 pNode = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
266 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
267 m_pNode = node_traits::to_value_ptr( pNode );
271 iterator_type( node_type * pNode )
273 m_pNode = node_traits::to_value_ptr( pNode );
278 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
279 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
285 iterator_type( iterator_type const& src )
286 : m_pNode( src.m_pNode )
289 value_ptr operator ->() const
294 value_ref operator *() const
296 assert( m_pNode != nullptr );
301 iterator_type& operator ++()
309 iterator_type operator ++(int)
311 iterator_type i(*this);
317 iterator_type& operator = (iterator_type const& src)
319 m_pNode = src.m_pNode;
324 bool operator ==(iterator_type<C> const& i ) const
326 return m_pNode == i.m_pNode;
329 bool operator !=(iterator_type<C> const& i ) const
331 return m_pNode != i.m_pNode;
338 typedef iterator_type<false> iterator;
339 /// Const forward iterator
340 typedef iterator_type<true> const_iterator;
342 /// Returns a forward iterator addressing the first element in a list
344 For empty list \code begin() == end() \endcode
348 iterator it( &m_Head );
349 ++it ; // skip dummy head
353 /// Returns an iterator that addresses the location succeeding the last element in a list
355 Do not use the value returned by <tt>end</tt> function to access any item.
357 The returned value can be used only to control reaching the end of the list.
358 For empty list \code begin() == end() \endcode
362 return iterator( &m_Tail );
365 /// Returns a forward const iterator addressing the first element in a list
367 const_iterator begin() const
369 return get_const_begin();
371 const_iterator cbegin()
373 return get_const_begin();
377 /// Returns an const iterator that addresses the location succeeding the last element in a list
379 const_iterator end() const
381 return get_const_end();
383 const_iterator cend()
385 return get_const_end();
391 const_iterator get_const_begin() const
393 const_iterator it( const_cast<node_type *>( &m_Head ));
394 ++it ; // skip dummy head
397 const_iterator get_const_end() const
399 return const_iterator( const_cast<node_type *>( &m_Tail ));
404 /// Default constructor initializes empty list
407 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
408 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
411 /// Destroys the list object
416 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
417 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
422 The function inserts \p val in the list if the list does not contain
423 an item with key equal to \p val.
425 Returns \p true if \p val is linked into the list, \p false otherwise.
427 bool insert( value_type& val )
429 return insert_at( &m_Head, val );
434 This function is intended for derived non-intrusive containers.
436 The function allows to split new item creating into two part:
437 - create item with key only
438 - insert new item into the list
439 - if inserting is success, calls \p f functor to initialize value-field of \p val.
441 The functor signature is:
443 void func( value_type& val );
445 where \p val is the item inserted.
446 While the functor \p f is working the item \p val is locked.
447 The user-defined functor is called only if the inserting is success and may be passed by reference
450 template <typename Func>
451 bool insert( value_type& val, Func f )
453 return insert_at( &m_Head, val, f );
456 /// Ensures that the \p item exists in the list
458 The operation performs inserting or changing data with lock-free manner.
460 If the item \p val not found in the list, then \p val is inserted into the list.
461 Otherwise, the functor \p func is called with item found.
462 The functor signature is:
465 void operator()( bool bNew, value_type& item, value_type& val );
469 - \p bNew - \p true if the item has been inserted, \p false otherwise
470 - \p item - item of the list
471 - \p val - argument \p val passed into the \p ensure function
472 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
473 refers to the same thing.
475 The functor may change non-key fields of the \p item.
476 While the functor \p f is calling the item \p item is locked.
478 You may pass \p func argument by reference using \p std::ref.
480 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
481 \p second is true if new item has been added or \p false if the item with \p key
482 already is in the list.
485 template <typename Func>
486 std::pair<bool, bool> ensure( value_type& val, Func func )
488 return ensure_at( &m_Head, val, func );
491 /// Unlinks the item \p val from the list
493 The function searches the item \p val in the list and unlink it from the list
494 if it is found and it is equal to \p val.
496 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
497 and deletes the item found. \p unlink finds an item by key and deletes it
498 only if \p val is an item of that list, i.e. the pointer to item found
499 is equal to <tt> &val </tt>.
501 The function returns \p true if success and \p false otherwise.
503 RCU \p synchronize method can be called.
504 Note that depending on RCU type used the \ref disposer call can be deferred.
506 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
507 deadlock checking policy is opt::v::rcu_throw_deadlock.
509 bool unlink( value_type& val )
511 return unlink_at( &m_Head, val );
514 /// Deletes the item from the list
515 /** \anchor cds_intrusive_LazyList_rcu_find_erase
516 The function searches an item with key equal to \p val in the list,
517 unlinks it from the list, and returns \p true.
518 If the item with the key equal to \p val is not found the function return \p false.
520 RCU \p synchronize method can be called.
521 Note that depending on RCU type used the \ref disposer call can be deferred.
523 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
524 deadlock checking policy is opt::v::rcu_throw_deadlock.
526 template <typename Q>
527 bool erase( Q const& val )
529 return erase_at( &m_Head, val, key_comparator() );
532 /// Deletes the item from the list using \p pred predicate for searching
534 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
535 but \p pred is used for key comparing.
536 \p Less functor has the interface like \p std::less.
537 \p pred must imply the same element order as the comparator used for building the list.
539 template <typename Q, typename Less>
540 bool erase_with( Q const& val, Less pred )
542 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>());
546 /// Deletes the item from the list
547 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
548 The function searches an item with key equal to \p val in the list,
549 call \p func functor with item found, unlinks it from the list, and returns \p true.
550 The \p Func interface is
553 void operator()( value_type const& item );
556 The functor may be passed by reference using <tt>boost:ref</tt>
558 If the item with the key equal to \p val is not found the function return \p false.
560 RCU \p synchronize method can be called.
561 Note that depending on RCU type used the \ref disposer call can be deferred.
563 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
564 deadlock checking policy is opt::v::rcu_throw_deadlock.
566 template <typename Q, typename Func>
567 bool erase( Q const& val, Func func )
569 return erase_at( &m_Head, val, key_comparator(), func );
572 /// Deletes the item from the list using \p pred predicate for searching
574 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
575 but \p pred is used for key comparing.
576 \p Less functor has the interface like \p std::less.
577 \p pred must imply the same element order as the comparator used for building the list.
579 template <typename Q, typename Less, typename Func>
580 bool erase_with( Q const& val, Less pred, Func func )
582 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), func );
585 /// Extracts an item from the list
587 \anchor cds_intrusive_LazyList_rcu_extract
588 The function searches an item with key equal to \p val in the list,
589 unlinks it from the list, and returns pointer to an item found in \p dest parameter.
590 If the item with the key equal to \p val is not found the function returns \p false,
593 @note The function does NOT call RCU read-side lock or synchronization,
594 and does NOT dispose the item found. It just excludes the item from the list
595 and returns a pointer to item found.
596 You should lock RCU before calling this function, and you should manually synchronize RCU
597 outside the RCU lock region before reusing returned pointer.
600 #include <cds/urcu/general_buffered.h>
601 #include <cds/intrusive/lazy_list_rcu.h>
603 typedef cds::urcu::gc< general_buffered<> > rcu;
604 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
606 rcu_lazy_list theList;
609 rcu_lazy_list::exempt_ptr p1;
611 // first, we should lock RCU
614 // Now, you can apply extract function
615 // Note that you must not delete the item found inside the RCU lock
616 if ( theList.extract( p1, 10 )) {
617 // do something with p1
622 // We may safely release p1 here
623 // release() passes the pointer to RCU reclamation cycle:
624 // it invokes RCU retire_ptr function with the disposer you provided for the list.
628 template <typename Q>
629 bool extract( exempt_ptr& dest, Q const& val )
631 dest = extract_at( &m_Head, val, key_comparator() );
632 return !dest.empty();
635 /// Extracts an item from the list using \p pred predicate for searching
637 This function is the analog for \ref cds_intrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
639 The \p pred is a predicate used for key comparing.
640 \p Less has the interface like \p std::less.
641 \p pred must imply the same element order as \ref key_comparator.
643 template <typename Q, typename Less>
644 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
646 dest = extract_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
647 return !dest.empty();
650 /// Finds the key \p val
651 /** \anchor cds_intrusive_LazyList_rcu_find_func
652 The function searches the item with key equal to \p val
653 and calls the functor \p f for item found.
654 The interface of \p Func functor is:
657 void operator()( value_type& item, Q& val );
660 where \p item is the item found, \p val is the <tt>find</tt> function argument.
662 You may pass \p f argument by reference using \p std::ref.
664 The functor may change non-key fields of \p item.
665 While the functor \p f is calling the item found \p item is locked.
667 The function returns \p true if \p val is found, \p false otherwise.
669 template <typename Q, typename Func>
670 bool find( Q& val, Func f ) const
672 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator(), f );
675 /// Finds the key \p val using \p pred predicate for searching
677 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)"
678 but \p pred is used for key comparing.
679 \p Less functor has the interface like \p std::less.
680 \p pred must imply the same element order as the comparator used for building the list.
682 template <typename Q, typename Less, typename Func>
683 bool find_with( Q& val, Less pred, Func f ) const
685 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
688 /// Finds the key \p val
689 /** \anchor cds_intrusive_LazyList_rcu_find_cfunc
690 The function searches the item with key equal to \p val
691 and calls the functor \p f for item found.
692 The interface of \p Func functor is:
695 void operator()( value_type& item, Q const& val );
698 where \p item is the item found, \p val is the <tt>find</tt> function argument.
700 You may pass \p f argument by reference using \p std::ref.
702 The functor may change non-key fields of \p item.
703 While the functor \p f is calling the item found \p item is locked.
705 The function returns \p true if \p val is found, \p false otherwise.
707 template <typename Q, typename Func>
708 bool find( Q const& val, Func f ) const
710 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator(), f );
713 /// Finds the key \p val using \p pred predicate for searching
715 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_cfunc "find(Q&, Func)"
716 but \p pred is used for key comparing.
717 \p Less functor has the interface like \p std::less.
718 \p pred must imply the same element order as the comparator used for building the list.
720 template <typename Q, typename Less, typename Func>
721 bool find_with( Q const& val, Less pred, Func f ) const
723 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>(), f );
726 /// Finds the key \p val
727 /** \anchor cds_intrusive_LazyList_rcu_find_val
728 The function searches the item with key equal to \p val
729 and returns \p true if \p val found or \p false otherwise.
731 template <typename Q>
732 bool find( Q const& val ) const
734 return find_at( const_cast<node_type *>( &m_Head ), val, key_comparator() );
737 /// Finds the key \p val using \p pred predicate for searching
739 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
740 but \p pred is used for key comparing.
741 \p Less functor has the interface like \p std::less.
742 \p pred must imply the same element order as the comparator used for building the list.
744 template <typename Q, typename Less>
745 bool find_with( Q const& val, Less pred ) const
747 return find_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>() );
750 /// Finds the key \p val and return the item found
751 /** \anchor cds_intrusive_LazyList_rcu_get
752 The function searches the item with key equal to \p val and returns the pointer to item found.
753 If \p val is not found it returns \p nullptr.
755 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
757 RCU should be locked before call of this function.
758 Returned item is valid only while RCU is locked:
760 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
765 ord_list::rcu_lock lock;
767 foo * pVal = theList.get( 5 );
772 // Unlock RCU by rcu_lock destructor
773 // pVal can be retired by disposer at any time after RCU has been unlocked
777 template <typename Q>
778 value_type * get( Q const& val ) const
780 return get_at( const_cast<node_type *>( &m_Head ), val, key_comparator());
783 /// Finds the key \p val and return the item found
785 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
786 but \p pred is used for comparing the keys.
788 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
790 \p pred must imply the same element order as the comparator used for building the list.
792 template <typename Q, typename Less>
793 value_type * get_with( Q const& val, Less pred ) const
795 return get_at( const_cast<node_type *>( &m_Head ), val, cds::opt::details::make_comparator_from_less<Less>());
798 /// Clears the list using default disposer
800 The function clears the list using default (provided in class template) disposer functor.
802 RCU \p synchronize method can be called.
803 Note that depending on RCU type used the \ref disposer call can be deferred.
805 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
806 deadlock checking policy is opt::v::rcu_throw_deadlock.
811 check_deadlock_policy::check();
817 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
818 if ( pHead == &m_Tail )
821 m_Head.m_Lock.lock();
822 pHead->m_Lock.lock();
824 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
825 unlink_node( &m_Head, pHead, &m_Head );
827 pHead->m_Lock.unlock();
828 m_Head.m_Lock.unlock();
832 dispose_node( pHead );
837 /// Checks if the list is empty
840 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
843 /// Returns list's item count
845 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
846 this function always returns 0.
848 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
849 is empty. To check list emptyness use \ref empty() method.
853 return m_ItemCounter.value();
858 // split-list support
859 bool insert_aux_node( node_type * pNode )
861 return insert_aux_node( &m_Head, pNode );
864 // split-list support
865 bool insert_aux_node( node_type * pHead, node_type * pNode )
867 assert( pHead != nullptr );
868 assert( pNode != nullptr );
870 // Hack: convert node_type to value_type.
871 // In principle, auxiliary node can be non-reducible to value_type
872 // We assume that comparator can correctly distinguish aux and regular node.
873 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
876 bool insert_at( node_type * pHead, value_type& val, bool bLock = true )
878 link_checker::is_empty( node_traits::to_node_ptr( val ) );
884 search( pHead, val, pos );
886 auto_lock_position alp( pos );
887 if ( validate( pos.pPred, pos.pCur )) {
888 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
889 // failed: key already in list
893 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
902 template <typename Func>
903 bool insert_at( node_type * pHead, value_type& val, Func f )
905 link_checker::is_empty( node_traits::to_node_ptr( val ) );
911 search( pHead, val, pos );
913 auto_lock_position alp( pos );
914 if ( validate( pos.pPred, pos.pCur )) {
915 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
916 // failed: key already in list
920 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
930 iterator insert_at_( node_type * pHead, value_type& val, bool bLock = true )
933 if ( insert_at( pHead, val, false ))
934 return iterator( node_traits::to_node_ptr( val ));
939 template <typename Func>
940 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func, bool bLock = true )
947 search( pHead, val, pos );
949 auto_lock_position alp( pos );
950 if ( validate( pos.pPred, pos.pCur )) {
951 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
952 // key already in the list
954 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
955 return std::make_pair( iterator( pos.pCur ), false );
959 link_checker::is_empty( node_traits::to_node_ptr( val ) );
961 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
962 func( true, val, val );
964 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
971 template <typename Func>
972 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func, bool bLock = true )
975 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func, false );
976 return std::make_pair( ret.first != end(), ret.second );
979 bool unlink_at( node_type * pHead, value_type& val )
983 check_deadlock_policy::check();
989 search( pHead, val, pos );
991 auto_lock_position alp( pos );
992 if ( validate( pos.pPred, pos.pCur ) ) {
993 if ( pos.pCur != &m_Tail
994 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
995 && node_traits::to_value_ptr( pos.pCur ) == &val )
998 unlink_node( pos.pPred, pos.pCur, pHead );
1009 if ( nResult > 0 ) {
1010 dispose_node( pos.pCur );
1018 template <typename Q, typename Compare, typename Func>
1019 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
1021 check_deadlock_policy::check();
1027 search( pHead, val, pos, cmp );
1029 auto_lock_position alp( pos );
1030 if ( validate( pos.pPred, pos.pCur )) {
1031 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1033 unlink_node( pos.pPred, pos.pCur, pHead );
1034 f( *node_traits::to_value_ptr( *pos.pCur ) );
1046 if ( nResult > 0 ) {
1047 dispose_node( pos.pCur );
1055 template <typename Q, typename Compare, typename Func>
1056 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1059 return erase_at( pHead, val, cmp, f, pos );
1062 template <typename Q, typename Compare>
1063 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1066 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1069 template <typename Q, typename Compare>
1070 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1073 assert( gc::is_locked() ) ; // RCU must be locked!!!
1076 search( pHead, val, pos, cmp );
1079 auto_lock_position alp( pos );
1080 if ( validate( pos.pPred, pos.pCur )) {
1081 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1083 unlink_node( pos.pPred, pos.pCur, pHead );
1095 return node_traits::to_value_ptr( pos.pCur );
1101 template <typename Q, typename Compare, typename Func>
1102 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
1106 rcu_lock l( bLock );
1107 search( pHead, val, pos, cmp );
1108 if ( pos.pCur != &m_Tail ) {
1109 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1110 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1112 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1119 template <typename Q, typename Compare>
1120 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1123 return find_at_( pHead, val, cmp ) != end();
1126 template <typename Q, typename Compare>
1127 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1129 assert( gc::is_locked() );
1133 search( pHead, val, pos, cmp );
1134 if ( pos.pCur != &m_Tail ) {
1135 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1136 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1138 return const_iterator( pos.pCur );
1144 template <typename Q, typename Compare>
1145 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1147 value_type * pFound = nullptr;
1148 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1156 template <typename Q>
1157 void search( node_type * pHead, Q const& key, position& pos ) const
1159 search( pHead, key, pos, key_comparator() );
1162 template <typename Q, typename Compare>
1163 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1165 // RCU should be locked!!!
1166 assert( gc::is_locked() );
1168 node_type const* pTail = &m_Tail;
1170 marked_node_ptr pCur(pHead);
1171 marked_node_ptr pPrev(pHead);
1173 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1175 pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1178 pos.pCur = pCur.ptr();
1179 pos.pPred = pPrev.ptr();
1182 static bool validate( node_type * pPred, node_type * pCur )
1184 // RCU lock should be locked!!!
1185 assert( gc::is_locked() );
1187 return !pPred->is_marked()
1188 && !pCur->is_marked()
1189 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1195 }} // namespace cds::intrusive
1197 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H