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 * raw_ptr;
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 );
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 iff \p bAllowInsert is \p true.
462 Otherwise, the functor \p func is called with item found.
463 The functor signature is:
466 void operator()( bool bNew, value_type& item, value_type& val );
470 - \p bNew - \p true if the item has been inserted, \p false otherwise
471 - \p item - item of the list
472 - \p val - argument \p val passed into the \p update() function
473 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
474 refer to the same thing.
476 The functor may change non-key fields of the \p item.
477 While the functor \p f is calling the item \p item is locked.
479 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
480 \p second is \p true if new item has been added or \p false if the item with \p key
481 already is in the list.
483 The function makes RCU lock internally.
485 template <typename Func>
486 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
488 return update_at( &m_Head, val, func, bAllowInsert );
491 // Deprecated, use update()
492 template <typename Func>
493 std::pair<bool, bool> ensure( value_type& val, Func func )
495 return update( val, func, true );
499 /// Unlinks the item \p val from the list
501 The function searches the item \p val in the list and unlink it from the list
502 if it is found and it is equal to \p val.
504 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
505 and deletes the item found. \p unlink finds an item by key and deletes it
506 only if \p val is an item of that list, i.e. the pointer to item found
507 is equal to <tt> &val </tt>.
509 The function returns \p true if success and \p false otherwise.
511 RCU \p synchronize method can be called. The RCU should not be locked.
512 Note that depending on RCU type used the \ref disposer call can be deferred.
514 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
515 deadlock checking policy is opt::v::rcu_throw_deadlock.
517 bool unlink( value_type& val )
519 return unlink_at( &m_Head, val );
522 /// Deletes the item from the list
523 /** \anchor cds_intrusive_LazyList_rcu_find_erase
524 The function searches an item with key equal to \p key in the list,
525 unlinks it from the list, and returns \p true.
526 If the item with the key equal to \p key is not found the function return \p false.
528 RCU \p synchronize method can be called. The RCU should not be locked.
529 Note that depending on RCU type used the \ref disposer call can be deferred.
531 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
532 deadlock checking policy is opt::v::rcu_throw_deadlock.
534 template <typename Q>
535 bool erase( Q const& key )
537 return erase_at( &m_Head, key, key_comparator() );
540 /// Deletes the item from the list using \p pred predicate for searching
542 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
543 but \p pred is used for key comparing.
544 \p Less functor has the interface like \p std::less.
545 \p pred must imply the same element order as the comparator used for building the list.
547 template <typename Q, typename Less>
548 bool erase_with( Q const& key, Less pred )
551 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
554 /// Deletes the item from the list
555 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
556 The function searches an item with key equal to \p key in the list,
557 call \p func functor with item found, unlinks it from the list, and returns \p true.
558 The \p Func interface is
561 void operator()( value_type const& item );
565 If the item with the key equal to \p key is not found the function return \p false.
567 RCU \p synchronize method can be called. The RCU should not be locked.
568 Note that depending on RCU type used the \ref disposer call can be deferred.
570 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
571 deadlock checking policy is opt::v::rcu_throw_deadlock.
573 template <typename Q, typename Func>
574 bool erase( Q const& key, Func func )
576 return erase_at( &m_Head, key, key_comparator(), func );
579 /// Deletes the item from the list using \p pred predicate for searching
581 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
582 but \p pred is used for key comparing.
583 \p Less functor has the interface like \p std::less.
584 \p pred must imply the same element order as the comparator used for building the list.
586 template <typename Q, typename Less, typename Func>
587 bool erase_with( Q const& key, Less pred, Func func )
590 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
593 /// Extracts an item from the list
595 \anchor cds_intrusive_LazyList_rcu_extract
596 The function searches an item with key equal to \p key in the list,
597 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
598 If the item is not found the function returns empty \p exempt_ptr.
600 @note The function does NOT call RCU read-side lock or synchronization,
601 and does NOT dispose the item found. It just excludes the item from the list
602 and returns a pointer to it.
603 You should manually lock RCU before calling this function, and you should manually synchronize RCU
604 outside the RCU lock region before reusing returned pointer.
607 #include <cds/urcu/general_buffered.h>
608 #include <cds/intrusive/lazy_list_rcu.h>
610 typedef cds::urcu::gc< general_buffered<> > rcu;
611 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
613 rcu_lazy_list theList;
616 rcu_lazy_list::exempt_ptr p1;
618 // first, we should lock RCU
621 // Now, you can apply extract function
622 // Note that you must not delete the item found inside the RCU lock
623 p1 = theList.extract( 10 )
625 // do something with p1
630 // We may safely release p1 here
631 // release() passes the pointer to RCU reclamation cycle:
632 // it invokes RCU retire_ptr function with the disposer you provided for the list.
636 template <typename Q>
637 exempt_ptr extract( Q const& key )
639 return exempt_ptr( extract_at( &m_Head, key, key_comparator() ));
642 /// Extracts an item from the list using \p pred predicate for searching
644 This function is the analog for \p extract(Q const&).
646 The \p pred is a predicate used for key comparing.
647 \p Less has the interface like \p std::less.
648 \p pred must imply the same element order as \ref key_comparator.
650 template <typename Q, typename Less>
651 exempt_ptr extract_with( Q const& key, Less pred )
654 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() ));
657 /// Finds the key \p key
658 /** \anchor cds_intrusive_LazyList_rcu_find_func
659 The function searches the item with key equal to \p key
660 and calls the functor \p f for item found.
661 The interface of \p Func functor is:
664 void operator()( value_type& item, Q& key );
667 where \p item is the item found, \p key is the <tt>find</tt> function argument.
669 The functor may change non-key fields of \p item.
670 While the functor \p f is calling the item found \p item is locked.
672 The function returns \p true if \p key is found, \p false otherwise.
674 template <typename Q, typename Func>
675 bool find( Q& key, Func f ) const
677 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
680 template <typename Q, typename Func>
681 bool find( Q const& key, Func f ) const
683 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
687 /// Finds the key \p key using \p pred predicate for searching
689 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
690 \p Less functor has the interface like \p std::less.
691 \p pred must imply the same element order as the comparator used for building the list.
693 template <typename Q, typename Less, typename Func>
694 bool find_with( Q& key, Less pred, Func f ) const
697 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
700 template <typename Q, typename Less, typename Func>
701 bool find_with( Q const& key, Less pred, Func f ) const
704 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
708 /// Checks whether the list contains \p key
710 The function searches the item with key equal to \p key
711 and returns \p true if it is found, and \p false otherwise.
713 template <typename Q>
714 bool contains( Q const& key ) const
716 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator() );
719 // Deprecated, use contains()
720 template <typename Q>
721 bool find( Q const& key ) const
723 return contains( key );
727 /// Checks whether the map contains \p key using \p pred predicate for searching
729 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
730 \p Less functor has the interface like \p std::less.
731 \p Less must imply the same element order as the comparator used for building the list.
733 template <typename Q, typename Less>
734 bool contains( Q const& key, Less pred ) const
737 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>() );
740 // Deprecated, use contains()
741 template <typename Q, typename Less>
742 bool find_with( Q const& key, Less pred ) const
744 return contains( key, pred );
748 /// Finds the key \p key and return the item found
749 /** \anchor cds_intrusive_LazyList_rcu_get
750 The function searches the item with key equal to \p key and returns the pointer to item found.
751 If \p key is not found it returns \p nullptr.
753 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
755 RCU should be locked before call of this function.
756 Returned item is valid only while RCU is locked:
758 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
763 ord_list::rcu_lock lock;
765 foo * pVal = theList.get( 5 );
770 // Unlock RCU by rcu_lock destructor
771 // pVal can be retired by disposer at any time after RCU has been unlocked
775 template <typename Q>
776 value_type * get( Q const& key ) const
778 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
781 /// Finds the key \p key and return the item found
783 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
784 but \p pred is used for comparing the keys.
786 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
788 \p pred must imply the same element order as the comparator used for building the list.
790 template <typename Q, typename Less>
791 value_type * get_with( Q const& key, Less pred ) const
794 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
797 /// Clears the list using default disposer
799 The function clears the list using default (provided in class template) disposer functor.
801 RCU \p synchronize method can be called.
802 Note that depending on RCU type used the \ref disposer call can be deferred.
804 The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and
805 deadlock checking policy is opt::v::rcu_throw_deadlock.
810 check_deadlock_policy::check();
816 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
817 if ( pHead == &m_Tail )
820 m_Head.m_Lock.lock();
821 pHead->m_Lock.lock();
823 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
824 unlink_node( &m_Head, pHead, &m_Head );
826 pHead->m_Lock.unlock();
827 m_Head.m_Lock.unlock();
831 dispose_node( pHead );
836 /// Checks if the list is empty
839 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
842 /// Returns list's item count
844 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
845 this function always returns 0.
847 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
848 is empty. To check list emptyness use \ref empty() method.
852 return m_ItemCounter.value();
857 // split-list support
858 bool insert_aux_node( node_type * pNode )
860 return insert_aux_node( &m_Head, pNode );
863 // split-list support
864 bool insert_aux_node( node_type * pHead, node_type * pNode )
866 assert( pHead != nullptr );
867 assert( pNode != nullptr );
869 // Hack: convert node_type to value_type.
870 // In principle, auxiliary node can be non-reducible to value_type
871 // We assume that comparator can correctly distinguish aux and regular node.
872 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
875 bool insert_at( node_type * pHead, value_type& val )
878 return insert_at_locked( pHead, val );
881 bool insert_at_locked( node_type * pHead, value_type& val )
883 // RCU lock should be locked!!!
884 assert( gc::is_locked() );
886 link_checker::is_empty( node_traits::to_node_ptr( val ) );
891 search( pHead, val, pos );
893 auto_lock_position alp( pos );
894 if ( validate( pos.pPred, pos.pCur )) {
895 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
896 // failed: key already in list
900 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
909 template <typename Func>
910 bool insert_at( node_type * pHead, value_type& val, Func f )
912 link_checker::is_empty( node_traits::to_node_ptr( val ) );
918 search( pHead, val, pos );
920 auto_lock_position alp( pos );
921 if ( validate( pos.pPred, pos.pCur )) {
922 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
923 // failed: key already in list
927 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
937 iterator insert_at_( node_type * pHead, value_type& val )
940 if ( insert_at_locked( pHead, val ))
941 return iterator( node_traits::to_node_ptr( val ));
946 template <typename Func>
947 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
950 return update_at_locked( pHead, val, func, bAllowInsert );
953 template <typename Func>
954 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
956 // RCU lock should be locked!!!
957 assert( gc::is_locked() );
963 search( pHead, val, pos );
965 auto_lock_position alp( pos );
966 if ( validate( pos.pPred, pos.pCur )) {
967 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
968 // key already in the list
970 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
971 return std::make_pair( iterator( pos.pCur ), false );
976 return std::make_pair( end(), false );
978 link_checker::is_empty( node_traits::to_node_ptr( val ) );
980 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
981 func( true, val, val );
983 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
990 template <typename Func>
991 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
994 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
995 return std::make_pair( ret.first != end(), ret.second );
998 bool unlink_at( node_type * pHead, value_type& val )
1002 check_deadlock_policy::check();
1008 search( pHead, val, pos );
1010 auto_lock_position alp( pos );
1011 if ( validate( pos.pPred, pos.pCur ) ) {
1012 if ( pos.pCur != &m_Tail
1013 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1014 && node_traits::to_value_ptr( pos.pCur ) == &val )
1017 unlink_node( pos.pPred, pos.pCur, pHead );
1028 if ( nResult > 0 ) {
1029 dispose_node( pos.pCur );
1037 template <typename Q, typename Compare, typename Func>
1038 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f, position& pos )
1040 check_deadlock_policy::check();
1046 search( pHead, val, pos, cmp );
1048 auto_lock_position alp( pos );
1049 if ( validate( pos.pPred, pos.pCur )) {
1050 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1052 unlink_node( pos.pPred, pos.pCur, pHead );
1053 f( *node_traits::to_value_ptr( *pos.pCur ) );
1065 if ( nResult > 0 ) {
1066 dispose_node( pos.pCur );
1074 template <typename Q, typename Compare, typename Func>
1075 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1078 return erase_at( pHead, val, cmp, f, pos );
1081 template <typename Q, typename Compare>
1082 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1085 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1088 template <typename Q, typename Compare>
1089 value_type * extract_at( node_type * pHead, Q const& val, Compare cmp )
1092 assert( gc::is_locked() ) ; // RCU must be locked!!!
1095 search( pHead, val, pos, cmp );
1098 auto_lock_position alp( pos );
1099 if ( validate( pos.pPred, pos.pCur )) {
1100 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1102 unlink_node( pos.pPred, pos.pCur, pHead );
1114 return node_traits::to_value_ptr( pos.pCur );
1120 template <typename Q, typename Compare, typename Func>
1121 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1126 search( pHead, val, pos, cmp );
1127 if ( pos.pCur != &m_Tail ) {
1128 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1129 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1131 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1138 template <typename Q, typename Compare>
1139 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1142 return find_at_( pHead, val, cmp ) != end();
1145 template <typename Q, typename Compare>
1146 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1148 assert( gc::is_locked() );
1152 search( pHead, val, pos, cmp );
1153 if ( pos.pCur != &m_Tail ) {
1154 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1155 return const_iterator( pos.pCur );
1160 template <typename Q, typename Compare>
1161 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1163 value_type * pFound = nullptr;
1164 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1172 template <typename Q>
1173 void search( node_type * pHead, Q const& key, position& pos ) const
1175 search( pHead, key, pos, key_comparator() );
1178 template <typename Q, typename Compare>
1179 void search( node_type * pHead, Q const& key, position& pos, Compare cmp ) const
1181 // RCU should be locked!!!
1182 assert( gc::is_locked() );
1184 node_type const* pTail = &m_Tail;
1186 marked_node_ptr pCur(pHead);
1187 marked_node_ptr pPrev(pHead);
1189 while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
1191 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1194 pos.pCur = pCur.ptr();
1195 pos.pPred = pPrev.ptr();
1198 static bool validate( node_type * pPred, node_type * pCur )
1200 // RCU lock should be locked!!!
1201 assert( gc::is_locked() );
1203 return !pPred->is_marked()
1204 && !pCur->is_marked()
1205 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1211 }} // namespace cds::intrusive
1213 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H