3 #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H
4 #define CDSLIB_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_traits {
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 /// pointer to extracted node
234 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
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() const
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() const
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.
448 template <typename Func>
449 bool insert( value_type& val, Func f )
451 return insert_at( &m_Head, val, f );
454 /// Ensures that the \p item exists in the list
456 The operation performs inserting or changing data with lock-free manner.
458 If the item \p val not found in the list, then \p val is inserted into the list.
459 Otherwise, the functor \p func is called with item found.
460 The functor signature is:
463 void operator()( bool bNew, value_type& item, value_type& val );
467 - \p bNew - \p true if the item has been inserted, \p false otherwise
468 - \p item - item of the list
469 - \p val - argument \p val passed into the \p ensure function
470 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
471 refers to the same thing.
473 The functor may change non-key fields of the \p item.
474 While the functor \p f is calling the item \p item is locked.
476 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
477 \p second is true if new item has been added or \p false if the item with \p key
478 already is in the list.
481 template <typename Func>
482 std::pair<bool, bool> ensure( value_type& val, Func func )
484 return ensure_at( &m_Head, val, func );
487 /// Unlinks the item \p val from the list
489 The function searches the item \p val in the list and unlink it from the list
490 if it is found and it is equal to \p val.
492 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
493 and deletes the item found. \p unlink finds an item by key and deletes it
494 only if \p val is an item of that list, i.e. the pointer to item found
495 is equal to <tt> &val </tt>.
497 The function returns \p true if success and \p false otherwise.
499 RCU \p synchronize method can be called.
500 Note that depending on RCU type used the \ref disposer call can be deferred.
502 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
503 deadlock checking policy is opt::v::rcu_throw_deadlock.
505 bool unlink( value_type& val )
507 return unlink_at( &m_Head, val );
510 /// Deletes the item from the list
511 /** \anchor cds_intrusive_LazyList_rcu_find_erase
512 The function searches an item with key equal to \p key in the list,
513 unlinks it from the list, and returns \p true.
514 If the item with the key equal to \p key is not found the function return \p false.
516 RCU \p synchronize method can be called.
517 Note that depending on RCU type used the \ref disposer call can be deferred.
519 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
520 deadlock checking policy is opt::v::rcu_throw_deadlock.
522 template <typename Q>
523 bool erase( Q const& key )
525 return erase_at( &m_Head, key, key_comparator() );
528 /// Deletes the item from the list using \p pred predicate for searching
530 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
531 but \p pred is used for key comparing.
532 \p Less functor has the interface like \p std::less.
533 \p pred must imply the same element order as the comparator used for building the list.
535 template <typename Q, typename Less>
536 bool erase_with( Q const& key, Less pred )
539 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
542 /// Deletes the item from the list
543 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
544 The function searches an item with key equal to \p key in the list,
545 call \p func functor with item found, unlinks it from the list, and returns \p true.
546 The \p Func interface is
549 void operator()( value_type const& item );
553 If the item with the key equal to \p key is not found the function return \p false.
555 RCU \p synchronize method can be called.
556 Note that depending on RCU type used the \ref disposer call can be deferred.
558 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
559 deadlock checking policy is opt::v::rcu_throw_deadlock.
561 template <typename Q, typename Func>
562 bool erase( Q const& key, Func func )
564 return erase_at( &m_Head, key, key_comparator(), func );
567 /// Deletes the item from the list using \p pred predicate for searching
569 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
570 but \p pred is used for key comparing.
571 \p Less functor has the interface like \p std::less.
572 \p pred must imply the same element order as the comparator used for building the list.
574 template <typename Q, typename Less, typename Func>
575 bool erase_with( Q const& key, Less pred, Func func )
578 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
581 /// Extracts an item from the list
583 \anchor cds_intrusive_LazyList_rcu_extract
584 The function searches an item with key equal to \p key in the list,
585 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
586 If the item is not found the function returns empty \p exempt_ptr.
588 @note The function does NOT call RCU read-side lock or synchronization,
589 and does NOT dispose the item found. It just excludes the item from the list
590 and returns a pointer to it.
591 You should manually lock RCU before calling this function, and you should manually synchronize RCU
592 outside the RCU lock region before reusing returned pointer.
595 #include <cds/urcu/general_buffered.h>
596 #include <cds/intrusive/lazy_list_rcu.h>
598 typedef cds::urcu::gc< general_buffered<> > rcu;
599 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
601 rcu_lazy_list theList;
604 rcu_lazy_list::exempt_ptr p1;
606 // first, we should lock RCU
609 // Now, you can apply extract function
610 // Note that you must not delete the item found inside the RCU lock
611 p1 = theList.extract( 10 )
613 // do something with p1
618 // We may safely release p1 here
619 // release() passes the pointer to RCU reclamation cycle:
620 // it invokes RCU retire_ptr function with the disposer you provided for the list.
624 template <typename Q>
625 exempt_ptr extract( Q const& key )
627 return exempt_ptr( extract_at( &m_Head, key, key_comparator() ));
630 /// Extracts an item from the list using \p pred predicate for searching
632 This function is the analog for \p extract(Q const&).
634 The \p pred is a predicate used for key comparing.
635 \p Less has the interface like \p std::less.
636 \p pred must imply the same element order as \ref key_comparator.
638 template <typename Q, typename Less>
639 exempt_ptr extract_with( Q const& key, Less pred )
642 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() ));
645 /// Finds the key \p key
646 /** \anchor cds_intrusive_LazyList_rcu_find_func
647 The function searches the item with key equal to \p key
648 and calls the functor \p f for item found.
649 The interface of \p Func functor is:
652 void operator()( value_type& item, Q& key );
655 where \p item is the item found, \p key is the <tt>find</tt> function argument.
657 The functor may change non-key fields of \p item.
658 While the functor \p f is calling the item found \p item is locked.
660 The function returns \p true if \p key is found, \p false otherwise.
662 template <typename Q, typename Func>
663 bool find( Q& key, Func f ) const
665 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
668 template <typename Q, typename Func>
669 bool find( Q const& key, Func f ) const
671 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
675 /// Finds the key \p key 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& key, Less pred, Func f ) const
686 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
689 template <typename Q, typename Less, typename Func>
690 bool find_with( Q const& key, Less pred, Func f ) const
693 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
697 /// Finds the key \p key
698 /** \anchor cds_intrusive_LazyList_rcu_find_val
699 The function searches the item with key equal to \p key
700 and returns \p true if \p key found or \p false otherwise.
702 template <typename Q>
703 bool find( Q const& key ) const
705 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator() );
708 /// Finds the key \p key using \p pred predicate for searching
710 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
711 but \p pred is used for key comparing.
712 \p Less functor has the interface like \p std::less.
713 \p pred must imply the same element order as the comparator used for building the list.
715 template <typename Q, typename Less>
716 bool find_with( Q const& key, Less pred ) const
719 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>() );
722 /// Finds the key \p key and return the item found
723 /** \anchor cds_intrusive_LazyList_rcu_get
724 The function searches the item with key equal to \p key and returns the pointer to item found.
725 If \p key is not found it returns \p nullptr.
727 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
729 RCU should be locked before call of this function.
730 Returned item is valid only while RCU is locked:
732 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
737 ord_list::rcu_lock lock;
739 foo * pVal = theList.get( 5 );
744 // Unlock RCU by rcu_lock destructor
745 // pVal can be retired by disposer at any time after RCU has been unlocked
749 template <typename Q>
750 value_type * get( Q const& key ) const
752 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
755 /// Finds the key \p key and return the item found
757 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
758 but \p pred is used for comparing the keys.
760 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
762 \p pred must imply the same element order as the comparator used for building the list.
764 template <typename Q, typename Less>
765 value_type * get_with( Q const& key, Less pred ) const
768 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
771 /// Clears the list using default disposer
773 The function clears the list using default (provided in class template) disposer functor.
775 RCU \p synchronize method can be called.
776 Note that depending on RCU type used the \ref disposer call can be deferred.
778 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
779 deadlock checking policy is opt::v::rcu_throw_deadlock.
784 check_deadlock_policy::check();
790 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
791 if ( pHead == &m_Tail )
794 m_Head.m_Lock.lock();
795 pHead->m_Lock.lock();
797 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
798 unlink_node( &m_Head, pHead, &m_Head );
800 pHead->m_Lock.unlock();
801 m_Head.m_Lock.unlock();
805 dispose_node( pHead );
810 /// Checks if the list is empty
813 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
816 /// Returns list's item count
818 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
819 this function always returns 0.
821 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
822 is empty. To check list emptyness use \ref empty() method.
826 return m_ItemCounter.value();
831 // split-list support
832 bool insert_aux_node( node_type * pNode )
834 return insert_aux_node( &m_Head, pNode );
837 // split-list support
838 bool insert_aux_node( node_type * pHead, node_type * pNode )
840 assert( pHead != nullptr );
841 assert( pNode != nullptr );
843 // Hack: convert node_type to value_type.
844 // In principle, auxiliary node can be non-reducible to value_type
845 // We assume that comparator can correctly distinguish aux and regular node.
846 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
849 bool insert_at( node_type * pHead, value_type& val, bool bLock = true )
851 link_checker::is_empty( node_traits::to_node_ptr( val ) );
857 search( pHead, val, pos );
859 auto_lock_position alp( pos );
860 if ( validate( pos.pPred, pos.pCur )) {
861 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
862 // failed: key already in list
866 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
875 template <typename Func>
876 bool insert_at( node_type * pHead, value_type& val, Func f )
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 );
903 iterator insert_at_( node_type * pHead, value_type& val, bool bLock = true )
906 if ( insert_at( pHead, val, false ))
907 return iterator( node_traits::to_node_ptr( val ));
912 template <typename Func>
913 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func, bool bLock = true )
920 search( pHead, val, pos );
922 auto_lock_position alp( pos );
923 if ( validate( pos.pPred, pos.pCur )) {
924 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
925 // key already in the list
927 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
928 return std::make_pair( iterator( pos.pCur ), false );
932 link_checker::is_empty( node_traits::to_node_ptr( val ) );
934 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
935 func( true, val, val );
937 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
944 template <typename Func>
945 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func, bool bLock = true )
948 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func, false );
949 return std::make_pair( ret.first != end(), ret.second );
952 bool unlink_at( node_type * pHead, value_type& val )
956 check_deadlock_policy::check();
962 search( pHead, val, pos );
964 auto_lock_position alp( pos );
965 if ( validate( pos.pPred, pos.pCur ) ) {
966 if ( pos.pCur != &m_Tail
967 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
968 && node_traits::to_value_ptr( pos.pCur ) == &val )
971 unlink_node( pos.pPred, pos.pCur, pHead );
983 dispose_node( pos.pCur );
991 template <typename Q, typename Compare, typename Func>
992 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
994 check_deadlock_policy::check();
1000 search( pHead, val, pos, cmp );
1002 auto_lock_position alp( pos );
1003 if ( validate( pos.pPred, pos.pCur )) {
1004 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1006 unlink_node( pos.pPred, pos.pCur, pHead );
1007 f( *node_traits::to_value_ptr( *pos.pCur ) );
1019 if ( nResult > 0 ) {
1020 dispose_node( pos.pCur );
1028 template <typename Q, typename Compare, typename Func>
1029 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1032 return erase_at( pHead, val, cmp, f, pos );
1035 template <typename Q, typename Compare>
1036 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1039 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1042 template <typename Q, typename Compare>
1043 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1046 assert( gc::is_locked() ) ; // RCU must be locked!!!
1049 search( pHead, val, pos, cmp );
1052 auto_lock_position alp( pos );
1053 if ( validate( pos.pPred, pos.pCur )) {
1054 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1056 unlink_node( pos.pPred, pos.pCur, pHead );
1068 return node_traits::to_value_ptr( pos.pCur );
1074 template <typename Q, typename Compare, typename Func>
1075 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f, bool bLock = true ) const
1079 rcu_lock l( bLock );
1080 search( pHead, val, pos, cmp );
1081 if ( pos.pCur != &m_Tail ) {
1082 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1083 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1085 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1092 template <typename Q, typename Compare>
1093 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1096 return find_at_( pHead, val, cmp ) != end();
1099 template <typename Q, typename Compare>
1100 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1102 assert( gc::is_locked() );
1106 search( pHead, val, pos, cmp );
1107 if ( pos.pCur != &m_Tail ) {
1108 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1109 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1111 return const_iterator( pos.pCur );
1117 template <typename Q, typename Compare>
1118 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1120 value_type * pFound = nullptr;
1121 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1129 template <typename Q>
1130 void search( node_type * pHead, Q const& key, position& pos ) const
1132 search( pHead, key, pos, key_comparator() );
1135 template <typename Q, typename Compare>
1136 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1138 // RCU should be locked!!!
1139 assert( gc::is_locked() );
1141 node_type const* pTail = &m_Tail;
1143 marked_node_ptr pCur(pHead);
1144 marked_node_ptr pPrev(pHead);
1146 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1148 pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1151 pos.pCur = pCur.ptr();
1152 pos.pPred = pPrev.ptr();
1155 static bool validate( node_type * pPred, node_type * pCur )
1157 // RCU lock should be locked!!!
1158 assert( gc::is_locked() );
1160 return !pPred->is_marked()
1161 && !pCur->is_marked()
1162 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1168 }} // namespace cds::intrusive
1170 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H