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 \p lazy_list::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::traits
100 class LazyList<cds::urcu::gc<RCU>, T, Traits>
103 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
104 typedef T value_type; ///< type of value stored in the list
105 typedef Traits traits; ///< Traits template parameter
107 typedef typename traits::hook hook; ///< hook type
108 typedef typename hook::node_type node_type; ///< node type
110 # ifdef CDS_DOXYGEN_INVOKED
111 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
113 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
116 typedef typename traits::disposer disposer; ///< disposer used
117 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
118 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
120 typedef typename traits::back_off back_off; ///< back-off strategy (not used)
121 typedef typename traits::item_counter item_counter; ///< Item counting policy used
122 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
123 typedef typename traits::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 traits (split-list support)
130 template <typename... Options>
131 struct rebind_options {
135 , typename cds::opt::make_options< traits, 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( 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
233 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node
237 template <bool IsConst>
240 friend class LazyList;
243 value_type * m_pNode;
247 assert( m_pNode != nullptr );
249 node_type * pNode = node_traits::to_node_ptr( m_pNode );
250 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
251 if ( pNext != nullptr )
252 m_pNode = node_traits::to_value_ptr( pNext );
257 if ( m_pNode != nullptr ) {
258 node_type * pNode = node_traits::to_node_ptr( m_pNode );
260 // Dummy tail node could not be marked
261 while ( pNode->is_marked() )
262 pNode = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
264 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
265 m_pNode = node_traits::to_value_ptr( pNode );
269 iterator_type( node_type * pNode )
271 m_pNode = node_traits::to_value_ptr( pNode );
276 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
277 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
283 iterator_type( iterator_type const& src )
284 : m_pNode( src.m_pNode )
287 value_ptr operator ->() const
292 value_ref operator *() const
294 assert( m_pNode != nullptr );
299 iterator_type& operator ++()
307 iterator_type operator ++(int)
309 iterator_type i(*this);
315 iterator_type& operator = (iterator_type const& src)
317 m_pNode = src.m_pNode;
322 bool operator ==(iterator_type<C> const& i ) const
324 return m_pNode == i.m_pNode;
327 bool operator !=(iterator_type<C> const& i ) const
329 return m_pNode != i.m_pNode;
336 typedef iterator_type<false> iterator;
337 /// Const forward iterator
338 typedef iterator_type<true> const_iterator;
340 /// Returns a forward iterator addressing the first element in a list
342 For empty list \code begin() == end() \endcode
346 iterator it( &m_Head );
347 ++it ; // skip dummy head
351 /// Returns an iterator that addresses the location succeeding the last element in a list
353 Do not use the value returned by <tt>end</tt> function to access any item.
355 The returned value can be used only to control reaching the end of the list.
356 For empty list \code begin() == end() \endcode
360 return iterator( &m_Tail );
363 /// Returns a forward const iterator addressing the first element in a list
365 const_iterator begin() const
367 return get_const_begin();
369 const_iterator cbegin()
371 return get_const_begin();
375 /// Returns an const iterator that addresses the location succeeding the last element in a list
377 const_iterator end() const
379 return get_const_end();
381 const_iterator cend()
383 return get_const_end();
389 const_iterator get_const_begin() const
391 const_iterator it( const_cast<node_type *>( &m_Head ));
392 ++it ; // skip dummy head
395 const_iterator get_const_end() const
397 return const_iterator( const_cast<node_type *>( &m_Tail ));
402 /// Default constructor initializes empty list
405 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
406 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
409 /// Destroys the list object
414 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
415 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
420 The function inserts \p val in the list if the list does not contain
421 an item with key equal to \p val.
423 Returns \p true if \p val is linked into the list, \p false otherwise.
425 bool insert( value_type& val )
427 return insert_at( &m_Head, val );
432 This function is intended for derived non-intrusive containers.
434 The function allows to split new item creating into two part:
435 - create item with key only
436 - insert new item into the list
437 - if inserting is success, calls \p f functor to initialize value-field of \p val.
439 The functor signature is:
441 void func( value_type& val );
443 where \p val is the item inserted.
444 While the functor \p f is working the item \p val is locked.
445 The user-defined functor is called only if the inserting is success.
447 template <typename Func>
448 bool insert( value_type& val, Func f )
450 return insert_at( &m_Head, val, f );
453 /// Ensures that the \p item exists in the list
455 The operation performs inserting or changing data with lock-free manner.
457 If the item \p val not found in the list, then \p val is inserted into the list.
458 Otherwise, the functor \p func is called with item found.
459 The functor signature is:
462 void operator()( bool bNew, value_type& item, value_type& val );
466 - \p bNew - \p true if the item has been inserted, \p false otherwise
467 - \p item - item of the list
468 - \p val - argument \p val passed into the \p ensure function
469 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
470 refers to the same thing.
472 The functor may change non-key fields of the \p item.
473 While the functor \p f is calling the item \p item is locked.
475 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
476 \p second is true if new item has been added or \p false if the item with \p key
477 already is in the list.
480 template <typename Func>
481 std::pair<bool, bool> ensure( value_type& val, Func func )
483 return ensure_at( &m_Head, val, func );
486 /// Unlinks the item \p val from the list
488 The function searches the item \p val in the list and unlink it from the list
489 if it is found and it is equal to \p val.
491 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
492 and deletes the item found. \p unlink finds an item by key and deletes it
493 only if \p val is an item of that list, i.e. the pointer to item found
494 is equal to <tt> &val </tt>.
496 The function returns \p true if success and \p false otherwise.
498 RCU \p synchronize method can be called.
499 Note that depending on RCU type used the \ref disposer call can be deferred.
501 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
502 deadlock checking policy is opt::v::rcu_throw_deadlock.
504 bool unlink( value_type& val )
506 return unlink_at( &m_Head, val );
509 /// Deletes the item from the list
510 /** \anchor cds_intrusive_LazyList_rcu_find_erase
511 The function searches an item with key equal to \p key in the list,
512 unlinks it from the list, and returns \p true.
513 If the item with the key equal to \p key is not found the function return \p false.
515 RCU \p synchronize method can be called.
516 Note that depending on RCU type used the \ref disposer call can be deferred.
518 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
519 deadlock checking policy is opt::v::rcu_throw_deadlock.
521 template <typename Q>
522 bool erase( Q const& key )
524 return erase_at( &m_Head, key, key_comparator() );
527 /// Deletes the item from the list using \p pred predicate for searching
529 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
530 but \p pred is used for key comparing.
531 \p Less functor has the interface like \p std::less.
532 \p pred must imply the same element order as the comparator used for building the list.
534 template <typename Q, typename Less>
535 bool erase_with( Q const& key, Less pred )
537 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
541 /// Deletes the item from the list
542 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
543 The function searches an item with key equal to \p key in the list,
544 call \p func functor with item found, unlinks it from the list, and returns \p true.
545 The \p Func interface is
548 void operator()( value_type const& item );
552 If the item with the key equal to \p key is not found the function return \p false.
554 RCU \p synchronize method can be called.
555 Note that depending on RCU type used the \ref disposer call can be deferred.
557 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
558 deadlock checking policy is opt::v::rcu_throw_deadlock.
560 template <typename Q, typename Func>
561 bool erase( Q const& key, Func func )
563 return erase_at( &m_Head, key, key_comparator(), func );
566 /// Deletes the item from the list using \p pred predicate for searching
568 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
569 but \p pred is used for key comparing.
570 \p Less functor has the interface like \p std::less.
571 \p pred must imply the same element order as the comparator used for building the list.
573 template <typename Q, typename Less, typename Func>
574 bool erase_with( Q const& key, Less pred, Func func )
576 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
579 /// Extracts an item from the list
581 \anchor cds_intrusive_LazyList_rcu_extract
582 The function searches an item with key equal to \p key in the list,
583 unlinks it from the list, and returns pointer to an item found in \p dest parameter.
584 If the item with the key equal to \p key is not found the function returns \p false,
587 @note The function does NOT call RCU read-side lock or synchronization,
588 and does NOT dispose the item found. It just excludes the item from the list
589 and returns a pointer to item found.
590 You should lock RCU before calling this function, and you should manually synchronize RCU
591 outside the RCU lock region before reusing returned pointer.
594 #include <cds/urcu/general_buffered.h>
595 #include <cds/intrusive/lazy_list_rcu.h>
597 typedef cds::urcu::gc< general_buffered<> > rcu;
598 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
600 rcu_lazy_list theList;
603 rcu_lazy_list::exempt_ptr p1;
605 // first, we should lock RCU
608 // Now, you can apply extract function
609 // Note that you must not delete the item found inside the RCU lock
610 if ( theList.extract( p1, 10 )) {
611 // do something with p1
616 // We may safely release p1 here
617 // release() passes the pointer to RCU reclamation cycle:
618 // it invokes RCU retire_ptr function with the disposer you provided for the list.
622 template <typename Q>
623 bool extract( exempt_ptr& dest, Q const& key )
625 dest = extract_at( &m_Head, key, key_comparator() );
626 return !dest.empty();
629 /// Extracts an item from the list using \p pred predicate for searching
631 This function is the analog for \ref cds_intrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
633 The \p pred is a predicate used for key comparing.
634 \p Less has the interface like \p std::less.
635 \p pred must imply the same element order as \ref key_comparator.
637 template <typename Q, typename Less>
638 bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
640 dest = extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
641 return !dest.empty();
644 /// Finds the key \p key
645 /** \anchor cds_intrusive_LazyList_rcu_find_func
646 The function searches the item with key equal to \p key
647 and calls the functor \p f for item found.
648 The interface of \p Func functor is:
651 void operator()( value_type& item, Q& key );
654 where \p item is the item found, \p key is the <tt>find</tt> function argument.
656 You may pass \p f argument by reference using \p std::ref.
658 The functor may change non-key fields of \p item.
659 While the functor \p f is calling the item found \p item is locked.
661 The function returns \p true if \p key is found, \p false otherwise.
663 template <typename Q, typename Func>
664 bool find( Q& key, Func f ) const
666 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
669 /// Finds the key \p key using \p pred predicate for searching
671 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)"
672 but \p pred is used for key comparing.
673 \p Less functor has the interface like \p std::less.
674 \p pred must imply the same element order as the comparator used for building the list.
676 template <typename Q, typename Less, typename Func>
677 bool find_with( Q& key, Less pred, Func f ) const
679 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
682 /// Finds the key \p key
683 /** \anchor cds_intrusive_LazyList_rcu_find_val
684 The function searches the item with key equal to \p key
685 and returns \p true if \p key found or \p false otherwise.
687 template <typename Q>
688 bool find( Q const& key ) const
690 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator() );
693 /// Finds the key \p key using \p pred predicate for searching
695 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
696 but \p pred is used for key comparing.
697 \p Less functor has the interface like \p std::less.
698 \p pred must imply the same element order as the comparator used for building the list.
700 template <typename Q, typename Less>
701 bool find_with( Q const& key, Less pred ) const
703 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>() );
706 /// Finds the key \p key and return the item found
707 /** \anchor cds_intrusive_LazyList_rcu_get
708 The function searches the item with key equal to \p key and returns the pointer to item found.
709 If \p key is not found it returns \p nullptr.
711 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
713 RCU should be locked before call of this function.
714 Returned item is valid only while RCU is locked:
716 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
721 ord_list::rcu_lock lock;
723 foo * pVal = theList.get( 5 );
728 // Unlock RCU by rcu_lock destructor
729 // pVal can be retired by disposer at any time after RCU has been unlocked
733 template <typename Q>
734 value_type * get( Q const& key ) const
736 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
739 /// Finds the key \p key and return the item found
741 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
742 but \p pred is used for comparing the keys.
744 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
746 \p pred must imply the same element order as the comparator used for building the list.
748 template <typename Q, typename Less>
749 value_type * get_with( Q const& key, Less pred ) const
751 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
754 /// Clears the list using default disposer
756 The function clears the list using default (provided in class template) disposer functor.
758 RCU \p synchronize method can be called.
759 Note that depending on RCU type used the \ref disposer call can be deferred.
761 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
762 deadlock checking policy is opt::v::rcu_throw_deadlock.
767 check_deadlock_policy::check();
773 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
774 if ( pHead == &m_Tail )
777 m_Head.m_Lock.lock();
778 pHead->m_Lock.lock();
780 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
781 unlink_node( &m_Head, pHead, &m_Head );
783 pHead->m_Lock.unlock();
784 m_Head.m_Lock.unlock();
788 dispose_node( pHead );
793 /// Checks if the list is empty
796 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
799 /// Returns list's item count
801 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
802 this function always returns 0.
804 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
805 is empty. To check list emptyness use \ref empty() method.
809 return m_ItemCounter.value();
814 // split-list support
815 bool insert_aux_node( node_type * pNode )
817 return insert_aux_node( &m_Head, pNode );
820 // split-list support
821 bool insert_aux_node( node_type * pHead, node_type * pNode )
823 assert( pHead != nullptr );
824 assert( pNode != nullptr );
826 // Hack: convert node_type to value_type.
827 // In principle, auxiliary node can be non-reducible to value_type
828 // We assume that comparator can correctly distinguish aux and regular node.
829 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
832 bool insert_at( node_type * pHead, value_type& val, bool bLock = true )
834 link_checker::is_empty( node_traits::to_node_ptr( val ) );
840 search( pHead, val, pos );
842 auto_lock_position alp( pos );
843 if ( validate( pos.pPred, pos.pCur )) {
844 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
845 // failed: key already in list
849 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
858 template <typename Func>
859 bool insert_at( node_type * pHead, value_type& val, Func f )
861 link_checker::is_empty( node_traits::to_node_ptr( val ) );
867 search( pHead, val, pos );
869 auto_lock_position alp( pos );
870 if ( validate( pos.pPred, pos.pCur )) {
871 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
872 // failed: key already in list
876 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
886 iterator insert_at_( node_type * pHead, value_type& val, bool bLock = true )
889 if ( insert_at( pHead, val, false ))
890 return iterator( node_traits::to_node_ptr( val ));
895 template <typename Func>
896 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func, bool bLock = true )
903 search( pHead, val, pos );
905 auto_lock_position alp( pos );
906 if ( validate( pos.pPred, pos.pCur )) {
907 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
908 // key already in the list
910 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
911 return std::make_pair( iterator( pos.pCur ), false );
915 link_checker::is_empty( node_traits::to_node_ptr( val ) );
917 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
918 func( true, val, val );
920 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
927 template <typename Func>
928 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func, bool bLock = true )
931 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func, false );
932 return std::make_pair( ret.first != end(), ret.second );
935 bool unlink_at( node_type * pHead, value_type& val )
939 check_deadlock_policy::check();
945 search( pHead, val, pos );
947 auto_lock_position alp( pos );
948 if ( validate( pos.pPred, pos.pCur ) ) {
949 if ( pos.pCur != &m_Tail
950 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
951 && node_traits::to_value_ptr( pos.pCur ) == &val )
954 unlink_node( pos.pPred, pos.pCur, pHead );
966 dispose_node( pos.pCur );
974 template <typename Q, typename Compare, typename Func>
975 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
977 check_deadlock_policy::check();
983 search( pHead, val, pos, cmp );
985 auto_lock_position alp( pos );
986 if ( validate( pos.pPred, pos.pCur )) {
987 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
989 unlink_node( pos.pPred, pos.pCur, pHead );
990 f( *node_traits::to_value_ptr( *pos.pCur ) );
1002 if ( nResult > 0 ) {
1003 dispose_node( pos.pCur );
1011 template <typename Q, typename Compare, typename Func>
1012 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1015 return erase_at( pHead, val, cmp, f, pos );
1018 template <typename Q, typename Compare>
1019 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1022 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1025 template <typename Q, typename Compare>
1026 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1029 assert( gc::is_locked() ) ; // RCU must be locked!!!
1032 search( pHead, val, pos, cmp );
1035 auto_lock_position alp( pos );
1036 if ( validate( pos.pPred, pos.pCur )) {
1037 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1039 unlink_node( pos.pPred, pos.pCur, pHead );
1051 return node_traits::to_value_ptr( pos.pCur );
1057 template <typename Q, typename Compare, typename Func>
1058 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
1062 rcu_lock l( bLock );
1063 search( pHead, val, pos, cmp );
1064 if ( pos.pCur != &m_Tail ) {
1065 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1066 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1068 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1075 template <typename Q, typename Compare>
1076 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1079 return find_at_( pHead, val, cmp ) != end();
1082 template <typename Q, typename Compare>
1083 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1085 assert( gc::is_locked() );
1089 search( pHead, val, pos, cmp );
1090 if ( pos.pCur != &m_Tail ) {
1091 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1092 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1094 return const_iterator( pos.pCur );
1100 template <typename Q, typename Compare>
1101 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1103 value_type * pFound = nullptr;
1104 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1112 template <typename Q>
1113 void search( node_type * pHead, Q const& key, position& pos ) const
1115 search( pHead, key, pos, key_comparator() );
1118 template <typename Q, typename Compare>
1119 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1121 // RCU should be locked!!!
1122 assert( gc::is_locked() );
1124 node_type const* pTail = &m_Tail;
1126 marked_node_ptr pCur(pHead);
1127 marked_node_ptr pPrev(pHead);
1129 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1131 pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1134 pos.pCur = pCur.ptr();
1135 pos.pPred = pPrev.ptr();
1138 static bool validate( node_type * pPred, node_type * pCur )
1140 // RCU lock should be locked!!!
1141 assert( gc::is_locked() );
1143 return !pPred->is_marked()
1144 && !pCur->is_marked()
1145 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1151 }} // namespace cds::intrusive
1153 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_RCU_H