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 typedef std::unique_lock< position > scoped_position_lock;
173 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
178 static void clear_links( node_type * pNode )
180 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
183 struct clear_and_dispose {
184 void operator()( value_type * p )
186 assert( p != nullptr );
187 clear_links( node_traits::to_node_ptr(p));
192 static void dispose_node( node_type * pNode )
195 assert( !gc::is_locked() );
197 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
200 static void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
202 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
204 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed );
205 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
208 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
210 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
211 assert( pCur != &m_Tail );
213 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
214 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
215 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
221 /// pointer to extracted node
222 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
223 /// Type of \p get() member function return value
224 typedef value_type * raw_ptr;
228 template <bool IsConst>
231 friend class LazyList;
234 value_type * m_pNode;
238 assert( m_pNode != nullptr );
240 node_type * pNode = node_traits::to_node_ptr( m_pNode );
241 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
242 if ( pNext != nullptr )
243 m_pNode = node_traits::to_value_ptr( pNext );
248 if ( m_pNode != nullptr ) {
249 node_type * pNode = node_traits::to_node_ptr( m_pNode );
251 // Dummy tail node could not be marked
252 while ( pNode->is_marked() )
253 pNode = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
255 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
256 m_pNode = node_traits::to_value_ptr( pNode );
260 iterator_type( node_type * pNode )
262 m_pNode = node_traits::to_value_ptr( pNode );
267 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
268 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
274 iterator_type( iterator_type const& src )
275 : m_pNode( src.m_pNode )
278 value_ptr operator ->() const
283 value_ref operator *() const
285 assert( m_pNode != nullptr );
290 iterator_type& operator ++()
298 iterator_type operator ++(int)
300 iterator_type i(*this);
306 iterator_type& operator = (iterator_type const& src)
308 m_pNode = src.m_pNode;
313 bool operator ==(iterator_type<C> const& i ) const
315 return m_pNode == i.m_pNode;
318 bool operator !=(iterator_type<C> const& i ) const
320 return m_pNode != i.m_pNode;
327 typedef iterator_type<false> iterator;
328 /// Const forward iterator
329 typedef iterator_type<true> const_iterator;
331 /// Returns a forward iterator addressing the first element in a list
333 For empty list \code begin() == end() \endcode
337 iterator it( &m_Head );
338 ++it ; // skip dummy head
342 /// Returns an iterator that addresses the location succeeding the last element in a list
344 Do not use the value returned by <tt>end</tt> function to access any item.
346 The returned value can be used only to control reaching the end of the list.
347 For empty list \code begin() == end() \endcode
351 return iterator( &m_Tail );
354 /// Returns a forward const iterator addressing the first element in a list
356 const_iterator begin() const
358 return get_const_begin();
360 const_iterator cbegin() const
362 return get_const_begin();
366 /// Returns an const iterator that addresses the location succeeding the last element in a list
368 const_iterator end() const
370 return get_const_end();
372 const_iterator cend() const
374 return get_const_end();
380 const_iterator get_const_begin() const
382 const_iterator it( const_cast<node_type *>( &m_Head ));
383 ++it ; // skip dummy head
386 const_iterator get_const_end() const
388 return const_iterator( const_cast<node_type *>( &m_Tail ));
393 /// Default constructor initializes empty list
396 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
397 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
400 /// Destroys the list object
405 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
406 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
411 The function inserts \p val in the list if the list does not contain
412 an item with key equal to \p val.
414 Returns \p true if \p val is linked into the list, \p false otherwise.
416 bool insert( value_type& val )
418 return insert_at( &m_Head, val );
423 This function is intended for derived non-intrusive containers.
425 The function allows to split new item creating into two part:
426 - create item with key only
427 - insert new item into the list
428 - if inserting is success, calls \p f functor to initialize value-field of \p val.
430 The functor signature is:
432 void func( value_type& val );
434 where \p val is the item inserted.
435 While the functor \p f is working the item \p val is locked.
436 The user-defined functor is called only if the inserting is success.
438 template <typename Func>
439 bool insert( value_type& val, Func f )
441 return insert_at( &m_Head, val, f );
446 The operation performs inserting or changing data with lock-free manner.
448 If the item \p val not found in the list, then \p val is inserted into the list
449 iff \p bAllowInsert is \p true.
450 Otherwise, the functor \p func is called with item found.
451 The functor signature is:
454 void operator()( bool bNew, value_type& item, value_type& val );
458 - \p bNew - \p true if the item has been inserted, \p false otherwise
459 - \p item - item of the list
460 - \p val - argument \p val passed into the \p update() function
461 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
462 refer to the same thing.
464 The functor may change non-key fields of the \p item.
465 While the functor \p f is calling the item \p item is locked.
467 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
468 \p second is \p true if new item has been added or \p false if the item with \p key
469 already is in the list.
471 The function makes RCU lock internally.
473 template <typename Func>
474 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
476 return update_at( &m_Head, val, func, bAllowInsert );
479 template <typename Func>
480 CDS_DEPRECATED("ensure() is deprecated, use update()")
481 std::pair<bool, bool> ensure( value_type& val, Func func )
483 return update( val, func, true );
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. The RCU should not be locked.
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. The RCU should not be locked.
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. The RCU should not be locked.
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 <tt>contains( key )</tt> but \p pred is used for key comparing.
678 \p Less functor has the interface like \p std::less.
679 \p pred must imply the same element order as the comparator used for building the list.
681 template <typename Q, typename Less, typename Func>
682 bool find_with( Q& key, Less pred, Func f ) const
685 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
688 template <typename Q, typename Less, typename Func>
689 bool find_with( Q const& key, Less pred, Func f ) const
692 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
696 /// Checks whether the list contains \p key
698 The function searches the item with key equal to \p key
699 and returns \p true if it is found, and \p false otherwise.
701 template <typename Q>
702 bool contains( Q const& key ) const
704 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator() );
707 template <typename Q>
708 CDS_DEPRECATED("deprecated, use contains()")
709 bool find( Q const& key ) const
711 return contains( key );
715 /// Checks whether the map contains \p key using \p pred predicate for searching
717 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
718 \p Less functor has the interface like \p std::less.
719 \p Less must imply the same element order as the comparator used for building the list.
721 template <typename Q, typename Less>
722 bool contains( Q const& key, Less pred ) const
725 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>() );
728 template <typename Q, typename Less>
729 CDS_DEPRECATED("deprecated, use contains()")
730 bool find_with( Q const& key, Less pred ) const
732 return contains( key, pred );
736 /// Finds the key \p key and return the item found
737 /** \anchor cds_intrusive_LazyList_rcu_get
738 The function searches the item with key equal to \p key and returns the pointer to item found.
739 If \p key is not found it returns \p nullptr.
741 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
743 RCU should be locked before call of this function.
744 Returned item is valid only while RCU is locked:
746 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
751 ord_list::rcu_lock lock;
753 foo * pVal = theList.get( 5 );
758 // Unlock RCU by rcu_lock destructor
759 // pVal can be retired by disposer at any time after RCU has been unlocked
763 template <typename Q>
764 value_type * get( Q const& key ) const
766 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
769 /// Finds the key \p key and return the item found
771 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
772 but \p pred is used for comparing the keys.
774 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
776 \p pred must imply the same element order as the comparator used for building the list.
778 template <typename Q, typename Less>
779 value_type * get_with( Q const& key, Less pred ) const
782 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
785 /// Clears the list using default disposer
787 The function clears the list using default (provided in class template) disposer functor.
789 RCU \p synchronize method can be called.
790 Note that depending on RCU type used the \ref disposer call can be deferred.
792 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
793 deadlock checking policy is opt::v::rcu_throw_deadlock.
798 check_deadlock_policy::check();
804 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
805 if ( pHead == &m_Tail )
808 m_Head.m_Lock.lock();
809 pHead->m_Lock.lock();
811 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
812 unlink_node( &m_Head, pHead, &m_Head );
814 pHead->m_Lock.unlock();
815 m_Head.m_Lock.unlock();
819 dispose_node( pHead );
824 /// Checks if the list is empty
827 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
830 /// Returns list's item count
832 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
833 this function always returns 0.
835 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
836 is empty. To check list emptyness use \ref empty() method.
840 return m_ItemCounter.value();
845 // split-list support
846 bool insert_aux_node( node_type * pNode )
848 return insert_aux_node( &m_Head, pNode );
851 // split-list support
852 bool insert_aux_node( node_type * pHead, node_type * pNode )
854 assert( pHead != nullptr );
855 assert( pNode != nullptr );
857 // Hack: convert node_type to value_type.
858 // Actually, an auxiliary node should not be converted to value_type
859 // We assume that comparator can correctly distinguish aux and regular node.
860 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
863 bool insert_at( node_type * pHead, value_type& val )
866 return insert_at_locked( pHead, val );
869 template <typename Func>
870 bool insert_at( node_type * pHead, value_type& val, Func f )
872 link_checker::is_empty( node_traits::to_node_ptr( val ) );
878 search( pHead, val, pos );
880 scoped_position_lock sl( pos );
881 if ( validate( pos.pPred, pos.pCur )) {
882 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
883 // failed: key already in list
887 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
896 iterator insert_at_( node_type * pHead, value_type& val )
899 if ( insert_at_locked( pHead, val ))
900 return iterator( node_traits::to_node_ptr( val ));
905 template <typename Func>
906 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
909 return update_at_locked( pHead, val, func, bAllowInsert );
912 template <typename Func>
913 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
916 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
917 return std::make_pair( ret.first != end(), ret.second );
920 bool unlink_at( node_type * pHead, value_type& val )
924 check_deadlock_policy::check();
930 search( pHead, val, pos );
932 scoped_position_lock alp( pos );
933 if ( validate( pos.pPred, pos.pCur ) ) {
934 if ( pos.pCur != &m_Tail
935 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
936 && node_traits::to_value_ptr( pos.pCur ) == &val )
939 unlink_node( pos.pPred, pos.pCur, pHead );
951 dispose_node( pos.pCur );
959 template <typename Q, typename Compare, typename Func>
960 bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
962 check_deadlock_policy::check();
968 search( pHead, val, pos, cmp );
970 scoped_position_lock alp( pos );
971 if ( validate( pos.pPred, pos.pCur )) {
972 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
974 unlink_node( pos.pPred, pos.pCur, pHead );
975 f( *node_traits::to_value_ptr( *pos.pCur ) );
987 dispose_node( pos.pCur );
995 template <typename Q, typename Compare, typename Func>
996 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
999 return erase_at( pHead, val, cmp, f, pos );
1002 template <typename Q, typename Compare>
1003 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1006 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1009 template <typename Q, typename Compare>
1010 value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1013 assert( gc::is_locked() ) ; // RCU must be locked!!!
1016 search( pHead, val, pos, cmp );
1019 scoped_position_lock alp( pos );
1020 if ( validate( pos.pPred, pos.pCur )) {
1021 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1023 unlink_node( pos.pPred, pos.pCur, pHead );
1035 return node_traits::to_value_ptr( pos.pCur );
1041 template <typename Q, typename Compare, typename Func>
1042 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1047 search( pHead, val, pos, cmp );
1048 if ( pos.pCur != &m_Tail ) {
1049 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1050 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1052 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1059 template <typename Q, typename Compare>
1060 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1063 return find_at_( pHead, val, cmp ) != end();
1066 template <typename Q, typename Compare>
1067 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1069 assert( gc::is_locked() );
1073 search( pHead, val, pos, cmp );
1074 if ( pos.pCur != &m_Tail ) {
1075 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1076 return const_iterator( pos.pCur );
1081 template <typename Q, typename Compare>
1082 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1084 value_type * pFound = nullptr;
1085 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1093 template <typename Q>
1094 void search( node_type * const pHead, Q const& key, position& pos ) const
1096 search( pHead, key, pos, key_comparator() );
1099 template <typename Q, typename Compare>
1100 void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1102 // RCU should be locked!!!
1103 assert( gc::is_locked() );
1105 node_type const* pTail = &m_Tail;
1107 marked_node_ptr pCur(pHead);
1108 marked_node_ptr pPrev(pHead);
1110 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1112 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1115 pos.pCur = pCur.ptr();
1116 pos.pPred = pPrev.ptr();
1119 static bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1121 // RCU lock should be locked!!!
1122 assert( gc::is_locked() );
1124 return !pPred->is_marked()
1125 && !pCur->is_marked()
1126 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1133 bool insert_at_locked( node_type * pHead, value_type& val )
1135 // RCU lock should be locked!!!
1136 assert( gc::is_locked() );
1138 link_checker::is_empty( node_traits::to_node_ptr( val ));
1143 search( pHead, val, pos );
1145 scoped_position_lock alp( pos );
1146 if ( validate( pos.pPred, pos.pCur ) ) {
1147 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1148 // failed: key already in list
1152 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1160 template <typename Func>
1161 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1163 // RCU lock should be locked!!!
1164 assert( gc::is_locked() );
1170 search( pHead, val, pos );
1172 scoped_position_lock alp( pos );
1173 if ( validate( pos.pPred, pos.pCur ) ) {
1174 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1175 // key already in the list
1177 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1178 return std::make_pair( iterator( pos.pCur ), false );
1182 if ( !bAllowInsert )
1183 return std::make_pair( end(), false );
1185 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1187 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1188 func( true, val, val );
1190 return std::make_pair( iterator( node_traits::to_node_ptr( val ) ), true );
1199 }} // namespace cds::intrusive
1201 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H