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 >;
235 /// Type of \p get() member function return value
236 typedef value_type * get_result;
240 template <bool IsConst>
243 friend class LazyList;
246 value_type * m_pNode;
250 assert( m_pNode != nullptr );
252 node_type * pNode = node_traits::to_node_ptr( m_pNode );
253 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
254 if ( pNext != nullptr )
255 m_pNode = node_traits::to_value_ptr( pNext );
260 if ( m_pNode != nullptr ) {
261 node_type * pNode = node_traits::to_node_ptr( m_pNode );
263 // Dummy tail node could not be marked
264 while ( pNode->is_marked() )
265 pNode = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
267 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
268 m_pNode = node_traits::to_value_ptr( pNode );
272 iterator_type( node_type * pNode )
274 m_pNode = node_traits::to_value_ptr( pNode );
279 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
280 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
286 iterator_type( iterator_type const& src )
287 : m_pNode( src.m_pNode )
290 value_ptr operator ->() const
295 value_ref operator *() const
297 assert( m_pNode != nullptr );
302 iterator_type& operator ++()
310 iterator_type operator ++(int)
312 iterator_type i(*this);
318 iterator_type& operator = (iterator_type const& src)
320 m_pNode = src.m_pNode;
325 bool operator ==(iterator_type<C> const& i ) const
327 return m_pNode == i.m_pNode;
330 bool operator !=(iterator_type<C> const& i ) const
332 return m_pNode != i.m_pNode;
339 typedef iterator_type<false> iterator;
340 /// Const forward iterator
341 typedef iterator_type<true> const_iterator;
343 /// Returns a forward iterator addressing the first element in a list
345 For empty list \code begin() == end() \endcode
349 iterator it( &m_Head );
350 ++it ; // skip dummy head
354 /// Returns an iterator that addresses the location succeeding the last element in a list
356 Do not use the value returned by <tt>end</tt> function to access any item.
358 The returned value can be used only to control reaching the end of the list.
359 For empty list \code begin() == end() \endcode
363 return iterator( &m_Tail );
366 /// Returns a forward const iterator addressing the first element in a list
368 const_iterator begin() const
370 return get_const_begin();
372 const_iterator cbegin() const
374 return get_const_begin();
378 /// Returns an const iterator that addresses the location succeeding the last element in a list
380 const_iterator end() const
382 return get_const_end();
384 const_iterator cend() const
386 return get_const_end();
392 const_iterator get_const_begin() const
394 const_iterator it( const_cast<node_type *>( &m_Head ));
395 ++it ; // skip dummy head
398 const_iterator get_const_end() const
400 return const_iterator( const_cast<node_type *>( &m_Tail ));
405 /// Default constructor initializes empty list
408 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
409 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
412 /// Destroys the list object
417 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
418 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
423 The function inserts \p val in the list if the list does not contain
424 an item with key equal to \p val.
426 Returns \p true if \p val is linked into the list, \p false otherwise.
428 bool insert( value_type& val )
430 return insert_at( &m_Head, val );
435 This function is intended for derived non-intrusive containers.
437 The function allows to split new item creating into two part:
438 - create item with key only
439 - insert new item into the list
440 - if inserting is success, calls \p f functor to initialize value-field of \p val.
442 The functor signature is:
444 void func( value_type& val );
446 where \p val is the item inserted.
447 While the functor \p f is working the item \p val is locked.
448 The user-defined functor is called only if the inserting is success.
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 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
479 \p second is true if new item has been added or \p false if the item with \p key
480 already is in the list.
483 template <typename Func>
484 std::pair<bool, bool> ensure( value_type& val, Func func )
486 return ensure_at( &m_Head, val, func );
489 /// Unlinks the item \p val from the list
491 The function searches the item \p val in the list and unlink it from the list
492 if it is found and it is equal to \p val.
494 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
495 and deletes the item found. \p unlink finds an item by key and deletes it
496 only if \p val is an item of that list, i.e. the pointer to item found
497 is equal to <tt> &val </tt>.
499 The function returns \p true if success and \p false otherwise.
501 RCU \p synchronize method can be called. The RCU should not be locked.
502 Note that depending on RCU type used the \ref disposer call can be deferred.
504 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
505 deadlock checking policy is opt::v::rcu_throw_deadlock.
507 bool unlink( value_type& val )
509 return unlink_at( &m_Head, val );
512 /// Deletes the item from the list
513 /** \anchor cds_intrusive_LazyList_rcu_find_erase
514 The function searches an item with key equal to \p key in the list,
515 unlinks it from the list, and returns \p true.
516 If the item with the key equal to \p key is not found the function return \p false.
518 RCU \p synchronize method can be called. The RCU should not be locked.
519 Note that depending on RCU type used the \ref disposer call can be deferred.
521 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
522 deadlock checking policy is opt::v::rcu_throw_deadlock.
524 template <typename Q>
525 bool erase( Q const& key )
527 return erase_at( &m_Head, key, key_comparator() );
530 /// Deletes the item from the list using \p pred predicate for searching
532 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
533 but \p pred is used for key comparing.
534 \p Less functor has the interface like \p std::less.
535 \p pred must imply the same element order as the comparator used for building the list.
537 template <typename Q, typename Less>
538 bool erase_with( Q const& key, Less pred )
541 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
544 /// Deletes the item from the list
545 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
546 The function searches an item with key equal to \p key in the list,
547 call \p func functor with item found, unlinks it from the list, and returns \p true.
548 The \p Func interface is
551 void operator()( value_type const& item );
555 If the item with the key equal to \p key is not found the function return \p false.
557 RCU \p synchronize method can be called. The RCU should not be locked.
558 Note that depending on RCU type used the \ref disposer call can be deferred.
560 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
561 deadlock checking policy is opt::v::rcu_throw_deadlock.
563 template <typename Q, typename Func>
564 bool erase( Q const& key, Func func )
566 return erase_at( &m_Head, key, key_comparator(), func );
569 /// Deletes the item from the list using \p pred predicate for searching
571 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
572 but \p pred is used for key comparing.
573 \p Less functor has the interface like \p std::less.
574 \p pred must imply the same element order as the comparator used for building the list.
576 template <typename Q, typename Less, typename Func>
577 bool erase_with( Q const& key, Less pred, Func func )
580 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
583 /// Extracts an item from the list
585 \anchor cds_intrusive_LazyList_rcu_extract
586 The function searches an item with key equal to \p key in the list,
587 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
588 If the item is not found the function returns empty \p exempt_ptr.
590 @note The function does NOT call RCU read-side lock or synchronization,
591 and does NOT dispose the item found. It just excludes the item from the list
592 and returns a pointer to it.
593 You should manually lock RCU before calling this function, and you should manually synchronize RCU
594 outside the RCU lock region before reusing returned pointer.
597 #include <cds/urcu/general_buffered.h>
598 #include <cds/intrusive/lazy_list_rcu.h>
600 typedef cds::urcu::gc< general_buffered<> > rcu;
601 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
603 rcu_lazy_list theList;
606 rcu_lazy_list::exempt_ptr p1;
608 // first, we should lock RCU
611 // Now, you can apply extract function
612 // Note that you must not delete the item found inside the RCU lock
613 p1 = theList.extract( 10 )
615 // do something with p1
620 // We may safely release p1 here
621 // release() passes the pointer to RCU reclamation cycle:
622 // it invokes RCU retire_ptr function with the disposer you provided for the list.
626 template <typename Q>
627 exempt_ptr extract( Q const& key )
629 return exempt_ptr( extract_at( &m_Head, key, key_comparator() ));
632 /// Extracts an item from the list using \p pred predicate for searching
634 This function is the analog for \p extract(Q const&).
636 The \p pred is a predicate used for key comparing.
637 \p Less has the interface like \p std::less.
638 \p pred must imply the same element order as \ref key_comparator.
640 template <typename Q, typename Less>
641 exempt_ptr extract_with( Q const& key, Less pred )
644 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() ));
647 /// Finds the key \p key
648 /** \anchor cds_intrusive_LazyList_rcu_find_func
649 The function searches the item with key equal to \p key
650 and calls the functor \p f for item found.
651 The interface of \p Func functor is:
654 void operator()( value_type& item, Q& key );
657 where \p item is the item found, \p key is the <tt>find</tt> function argument.
659 The functor may change non-key fields of \p item.
660 While the functor \p f is calling the item found \p item is locked.
662 The function returns \p true if \p key is found, \p false otherwise.
664 template <typename Q, typename Func>
665 bool find( Q& key, Func f ) const
667 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
670 template <typename Q, typename Func>
671 bool find( Q const& key, Func f ) const
673 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
677 /// Finds the key \p key using \p pred predicate for searching
679 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)"
680 but \p pred is used for key comparing.
681 \p Less functor has the interface like \p std::less.
682 \p pred must imply the same element order as the comparator used for building the list.
684 template <typename Q, typename Less, typename Func>
685 bool find_with( Q& key, Less pred, Func f ) const
688 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
691 template <typename Q, typename Less, typename Func>
692 bool find_with( Q const& key, Less pred, Func f ) const
695 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
699 /// Finds the key \p key
700 /** \anchor cds_intrusive_LazyList_rcu_find_val
701 The function searches the item with key equal to \p key
702 and returns \p true if \p key found or \p false otherwise.
704 template <typename Q>
705 bool find( Q const& key ) const
707 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator() );
710 /// Finds the key \p key using \p pred predicate for searching
712 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)"
713 but \p pred is used for key comparing.
714 \p Less functor has the interface like \p std::less.
715 \p pred must imply the same element order as the comparator used for building the list.
717 template <typename Q, typename Less>
718 bool find_with( Q const& key, Less pred ) const
721 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>() );
724 /// Finds the key \p key and return the item found
725 /** \anchor cds_intrusive_LazyList_rcu_get
726 The function searches the item with key equal to \p key and returns the pointer to item found.
727 If \p key is not found it returns \p nullptr.
729 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
731 RCU should be locked before call of this function.
732 Returned item is valid only while RCU is locked:
734 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
739 ord_list::rcu_lock lock;
741 foo * pVal = theList.get( 5 );
746 // Unlock RCU by rcu_lock destructor
747 // pVal can be retired by disposer at any time after RCU has been unlocked
751 template <typename Q>
752 value_type * get( Q const& key ) const
754 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
757 /// Finds the key \p key and return the item found
759 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
760 but \p pred is used for comparing the keys.
762 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
764 \p pred must imply the same element order as the comparator used for building the list.
766 template <typename Q, typename Less>
767 value_type * get_with( Q const& key, Less pred ) const
770 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
773 /// Clears the list using default disposer
775 The function clears the list using default (provided in class template) disposer functor.
777 RCU \p synchronize method can be called.
778 Note that depending on RCU type used the \ref disposer call can be deferred.
780 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
781 deadlock checking policy is opt::v::rcu_throw_deadlock.
786 check_deadlock_policy::check();
792 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
793 if ( pHead == &m_Tail )
796 m_Head.m_Lock.lock();
797 pHead->m_Lock.lock();
799 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
800 unlink_node( &m_Head, pHead, &m_Head );
802 pHead->m_Lock.unlock();
803 m_Head.m_Lock.unlock();
807 dispose_node( pHead );
812 /// Checks if the list is empty
815 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
818 /// Returns list's item count
820 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
821 this function always returns 0.
823 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
824 is empty. To check list emptyness use \ref empty() method.
828 return m_ItemCounter.value();
833 // split-list support
834 bool insert_aux_node( node_type * pNode )
836 return insert_aux_node( &m_Head, pNode );
839 // split-list support
840 bool insert_aux_node( node_type * pHead, node_type * pNode )
842 assert( pHead != nullptr );
843 assert( pNode != nullptr );
845 // Hack: convert node_type to value_type.
846 // In principle, auxiliary node can be non-reducible to value_type
847 // We assume that comparator can correctly distinguish aux and regular node.
848 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
851 bool insert_at( node_type * pHead, value_type& val )
854 return insert_at_locked( pHead, val );
857 bool insert_at_locked( node_type * pHead, value_type& val )
859 // RCU lock should be locked!!!
860 assert( gc::is_locked() );
862 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 );
885 template <typename Func>
886 bool insert_at( node_type * pHead, value_type& val, Func f )
888 link_checker::is_empty( node_traits::to_node_ptr( val ) );
894 search( pHead, val, pos );
896 auto_lock_position alp( pos );
897 if ( validate( pos.pPred, pos.pCur )) {
898 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
899 // failed: key already in list
903 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
913 iterator insert_at_( node_type * pHead, value_type& val )
916 if ( insert_at_locked( pHead, val ))
917 return iterator( node_traits::to_node_ptr( val ));
922 template <typename Func>
923 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
926 return ensure_at_locked( pHead, val, func );
929 template <typename Func>
930 std::pair<iterator, bool> ensure_at_locked( node_type * pHead, value_type& val, Func func )
932 // RCU lock should be locked!!!
933 assert( gc::is_locked() );
939 search( pHead, val, pos );
941 auto_lock_position alp( pos );
942 if ( validate( pos.pPred, pos.pCur )) {
943 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
944 // key already in the list
946 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
947 return std::make_pair( iterator( pos.pCur ), false );
951 link_checker::is_empty( node_traits::to_node_ptr( val ) );
953 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
954 func( true, val, val );
956 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
963 template <typename Func>
964 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
967 std::pair<iterator, bool> ret = ensure_at_locked( pHead, val, func );
968 return std::make_pair( ret.first != end(), ret.second );
971 bool unlink_at( node_type * pHead, value_type& val )
975 check_deadlock_policy::check();
981 search( pHead, val, pos );
983 auto_lock_position alp( pos );
984 if ( validate( pos.pPred, pos.pCur ) ) {
985 if ( pos.pCur != &m_Tail
986 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
987 && node_traits::to_value_ptr( pos.pCur ) == &val )
990 unlink_node( pos.pPred, pos.pCur, pHead );
1001 if ( nResult > 0 ) {
1002 dispose_node( pos.pCur );
1010 template <typename Q, typename Compare, typename Func>
1011 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
1013 check_deadlock_policy::check();
1019 search( pHead, val, pos, cmp );
1021 auto_lock_position alp( pos );
1022 if ( validate( pos.pPred, pos.pCur )) {
1023 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1025 unlink_node( pos.pPred, pos.pCur, pHead );
1026 f( *node_traits::to_value_ptr( *pos.pCur ) );
1038 if ( nResult > 0 ) {
1039 dispose_node( pos.pCur );
1047 template <typename Q, typename Compare, typename Func>
1048 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1051 return erase_at( pHead, val, cmp, f, pos );
1054 template <typename Q, typename Compare>
1055 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1058 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1061 template <typename Q, typename Compare>
1062 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1065 assert( gc::is_locked() ) ; // RCU must be locked!!!
1068 search( pHead, val, pos, cmp );
1071 auto_lock_position alp( pos );
1072 if ( validate( pos.pPred, pos.pCur )) {
1073 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1075 unlink_node( pos.pPred, pos.pCur, pHead );
1087 return node_traits::to_value_ptr( pos.pCur );
1093 template <typename Q, typename Compare, typename Func>
1094 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1099 search( pHead, val, pos, cmp );
1100 if ( pos.pCur != &m_Tail ) {
1101 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1102 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1104 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1111 template <typename Q, typename Compare>
1112 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1115 return find_at_( pHead, val, cmp ) != end();
1118 template <typename Q, typename Compare>
1119 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1121 assert( gc::is_locked() );
1125 search( pHead, val, pos, cmp );
1126 if ( pos.pCur != &m_Tail ) {
1127 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1128 return const_iterator( pos.pCur );
1133 template <typename Q, typename Compare>
1134 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1136 value_type * pFound = nullptr;
1137 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1145 template <typename Q>
1146 void search( node_type * pHead, Q const& key, position& pos ) const
1148 search( pHead, key, pos, key_comparator() );
1151 template <typename Q, typename Compare>
1152 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1154 // RCU should be locked!!!
1155 assert( gc::is_locked() );
1157 node_type const* pTail = &m_Tail;
1159 marked_node_ptr pCur(pHead);
1160 marked_node_ptr pPrev(pHead);
1162 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1164 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1167 pos.pCur = pCur.ptr();
1168 pos.pPred = pPrev.ptr();
1171 static bool validate( node_type * pPred, node_type * pCur )
1173 // RCU lock should be locked!!!
1174 assert( gc::is_locked() );
1176 return !pPred->is_marked()
1177 && !pCur->is_marked()
1178 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1184 }} // namespace cds::intrusive
1186 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H