3 #ifndef __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
4 #define __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
6 #include <mutex> // unique_lock
7 #include <cds/intrusive/details/lazy_list_base.h>
8 #include <cds/gc/guarded_ptr.h>
10 namespace cds { namespace intrusive {
12 /// Lazy ordered single-linked list
13 /** @ingroup cds_intrusive_list
14 \anchor cds_intrusive_LazyList_hp
16 Usually, ordered single-linked list is used as a building block for the hash table implementation.
17 The complexity of searching is <tt>O(N)</tt>.
20 - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
21 "A Lazy Concurrent List-Based Set Algorithm"
23 The lazy list is based on an optimistic locking scheme for inserts and removes,
24 eliminating the need to use the equivalent of an atomically markable
25 reference. It also has a novel wait-free membership \p find operation
26 that does not need to perform cleanup operations and is more efficient.
29 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see lazy_list::node).
30 - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
31 or it must have a member of type lazy_list::node (for lazy_list::member_hook).
32 - \p Traits - type traits. See lazy_list::traits for explanation.
33 It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
34 argument. For example, the following traits-based declaration of \p gc::HP lazy list
36 #include <cds/intrusive/lazy_list_hp.h>
37 // Declare item stored in your list
38 struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
41 // Declare comparator for the item
42 struct my_compare { ... }
45 struct my_traits: public cds::intrusive::lazy_list::traits
47 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
48 typedef my_compare compare;
51 // Declare traits-based list
52 typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits > traits_based_list;
54 is equivalent for the following option-based list
56 #include <cds/intrusive/lazy_list_hp.h>
58 // item struct and my_compare are the same
60 // Declare option-based list
61 typedef cds::intrusive::LazyList< cds::gc::HP, item,
62 typename cds::intrusive::lazy_list::make_traits<
63 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
64 ,cds::intrusive::opt::compare< my_compare > // item comparator option
70 There are different specializations of this template for each garbage collecting schema used.
71 You should select GC needed and include appropriate .h-file:
72 - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
73 - for gc::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
74 - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
75 - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
77 Then, you should incorporate lazy_list::node into your struct \p T and provide
78 appropriate \p lazy_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits
79 a struct based on \p lazy_list::traits should be defined.
81 Example for gc::DHP and base hook:
83 // Include GC-related lazy list specialization
84 #include <cds/intrusive/lazy_list_dhp.h>
86 // Data stored in lazy list
87 struct my_data: public cds::intrusive::lazy_list::node< cds::gc::DHP >
96 // my_data comparing functor
98 int operator()( const my_data& d1, const my_data& d2 )
100 return d1.strKey.compare( d2.strKey );
103 int operator()( const my_data& d, const std::string& s )
105 return d.strKey.compare(s);
108 int operator()( const std::string& s, const my_data& d )
110 return s.compare( d.strKey );
115 struct my_traits: public cds::intrusive::lazy_list::traits
117 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
118 typedef my_data_cmp compare;
122 typedef cds::intrusive::LazyList< cds::gc::DHP, my_data, my_traits > traits_based_list;
125 Equivalent option-based code:
127 // GC-related specialization
128 #include <cds/intrusive/lazy_list_dhp.h>
137 // Declare option-based list
138 typedef cds::intrusive::LazyList< cds::gc::DHP
140 , typename cds::intrusive::lazy_list::make_traits<
141 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
142 ,cds::intrusive::opt::compare< my_data_cmp >
151 #ifdef CDS_DOXYGEN_INVOKED
152 ,class Traits = lazy_list::traits
160 typedef GC gc; ///< Garbage collector
161 typedef T value_type; ///< type of value stored in the list
162 typedef Traits traits; ///< Traits template parameter
164 typedef typename traits::hook hook; ///< hook type
165 typedef typename hook::node_type node_type; ///< node type
167 # ifdef CDS_DOXYGEN_INVOKED
168 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
170 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
173 typedef typename traits::disposer disposer; ///< disposer
174 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
175 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
177 typedef typename traits::back_off back_off ; ///< back-off strategy
178 typedef typename traits::item_counter item_counter ; ///< Item counting policy used
179 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
181 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
184 // Rebind traits (split-list support)
185 template <typename... Options>
186 struct rebind_options {
190 , typename cds::opt::make_options< traits, Options...>::type
196 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
197 typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
204 item_counter m_ItemCounter ; ///< Item counter
207 struct clean_disposer {
208 void operator()( value_type * p )
210 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
215 /// Position pointer for item search
217 node_type * pPred ; ///< Previous node
218 node_type * pCur ; ///< Current node
220 typename gc::template GuardArray<2> guards ; ///< Guards array
227 /// Locks nodes \p pPred and \p pCur
230 pPred->m_Lock.lock();
234 /// Unlocks nodes \p pPred and \p pCur
237 pCur->m_Lock.unlock();
238 pPred->m_Lock.unlock();
242 class auto_lock_position {
245 auto_lock_position( position& pos )
250 ~auto_lock_position()
259 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
261 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
263 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
264 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
267 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
269 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
271 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
272 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_release) ; // logically deleting
273 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // logical removal + back-link for search
274 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
275 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // back-link for search
278 void retire_node( node_type * pNode )
280 assert( pNode != nullptr );
281 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
287 template <bool IsConst>
290 friend class LazyList;
293 value_type * m_pNode;
294 typename gc::Guard m_Guard;
298 assert( m_pNode != nullptr );
301 typename gc::Guard g;
302 node_type * pCur = node_traits::to_node_ptr( m_pNode );
303 if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) { // if pCur is not tail node
306 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
307 g.assign( node_traits::to_value_ptr( pNext ));
308 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr() );
310 m_pNode = m_Guard.assign( g.template get<value_type>() );
317 if ( m_pNode != nullptr ) {
318 typename gc::Guard g;
319 node_type * pNode = node_traits::to_node_ptr( m_pNode );
321 // Dummy tail node could not be marked
322 while ( pNode->is_marked() ) {
323 node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
324 g.assign( node_traits::to_value_ptr( p ));
325 if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr() )
328 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
329 m_pNode = m_Guard.assign( g.template get<value_type>() );
333 iterator_type( node_type * pNode )
335 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
340 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
341 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
347 iterator_type( iterator_type const& src )
350 m_pNode = m_Guard.assign( src.m_pNode );
356 value_ptr operator ->() const
361 value_ref operator *() const
363 assert( m_pNode != nullptr );
368 iterator_type& operator ++()
375 iterator_type& operator = (iterator_type const& src)
377 m_pNode = src.m_pNode;
378 m_Guard.assign( m_pNode );
383 bool operator ==(iterator_type<C> const& i ) const
385 return m_pNode == i.m_pNode;
388 bool operator !=(iterator_type<C> const& i ) const
390 return m_pNode != i.m_pNode;
398 The forward iterator for lazy list has some features:
399 - it has no post-increment operator
400 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
401 For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
402 may be thrown if a limit of guard count per thread is exceeded.
403 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
404 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
405 deleting operations it is no guarantee that you iterate all item in the list.
407 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
408 for debug purpose only.
410 typedef iterator_type<false> iterator;
411 /// Const forward iterator
413 For iterator's features and requirements see \ref iterator
415 typedef iterator_type<true> const_iterator;
417 /// Returns a forward iterator addressing the first element in a list
419 For empty list \code begin() == end() \endcode
423 iterator it( &m_Head );
424 ++it ; // skip dummy head
428 /// Returns an iterator that addresses the location succeeding the last element in a list
430 Do not use the value returned by <tt>end</tt> function to access any item.
432 The returned value can be used only to control reaching the end of the list.
433 For empty list \code begin() == end() \endcode
437 return iterator( &m_Tail );
440 /// Returns a forward const iterator addressing the first element in a list
442 const_iterator begin() const
444 return get_const_begin();
446 const_iterator cbegin()
448 return get_const_begin();
452 /// Returns an const iterator that addresses the location succeeding the last element in a list
454 const_iterator end() const
456 return get_const_end();
458 const_iterator cend()
460 return get_const_end();
466 const_iterator get_const_begin() const
468 const_iterator it( const_cast<node_type *>( &m_Head ));
469 ++it ; // skip dummy head
472 const_iterator get_const_end() const
474 return const_iterator( const_cast<node_type *>(&m_Tail) );
479 /// Default constructor initializes empty list
482 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
483 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
486 /// Destroys the list object
490 assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
491 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
496 The function inserts \p val in the list if the list does not contain
497 an item with key equal to \p val.
499 Returns \p true if \p val is linked into the list, \p false otherwise.
501 bool insert( value_type& val )
503 return insert_at( &m_Head, val );
508 This function is intended for derived non-intrusive containers.
510 The function allows to split new item creating into two part:
511 - create item with key only
512 - insert new item into the list
513 - if inserting is success, calls \p f functor to initialize value-field of \p val.
515 The functor signature is:
517 void func( value_type& val );
519 where \p val is the item inserted.
520 While the functor \p f is working the item \p val is locked.
521 The user-defined functor is called only if the inserting is success.
523 template <typename Func>
524 bool insert( value_type& val, Func f )
526 return insert_at( &m_Head, val, f );
529 /// Ensures that the \p item exists in the list
531 The operation performs inserting or changing data with lock-free manner.
533 If the item \p val not found in the list, then \p val is inserted into the list.
534 Otherwise, the functor \p func is called with item found.
535 The functor signature is:
537 void func( bool bNew, value_type& item, value_type& val );
540 - \p bNew - \p true if the item has been inserted, \p false otherwise
541 - \p item - item of the list
542 - \p val - argument \p val passed into the \p ensure function
543 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
544 refer to the same thing.
546 The functor may change non-key fields of the \p item.
547 While the functor \p f is working the item \p item is locked.
549 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
550 \p second is \p true if new item has been added or \p false if the item with \p key
551 already is in the list.
553 template <typename Func>
554 std::pair<bool, bool> ensure( value_type& val, Func func )
556 return ensure_at( &m_Head, val, func );
559 /// Unlinks the item \p val from the list
561 The function searches the item \p val in the list and unlink it from the list
562 if it is found and it is equal to \p val.
564 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
565 and deletes the item found. \p unlink finds an item by key and deletes it
566 only if \p val is an item of that list, i.e. the pointer to item found
567 is equal to <tt> &val </tt>.
569 The function returns \p true if success and \p false otherwise.
571 bool unlink( value_type& val )
573 return unlink_at( &m_Head, val );
576 /// Deletes the item from the list
577 /** \anchor cds_intrusive_LazyList_hp_erase_val
578 The function searches an item with key equal to \p key in the list,
579 unlinks it from the list, and returns \p true.
580 If the item with the key equal to \p key is not found the function return \p false.
582 template <typename Q>
583 bool erase( Q const& key )
585 return erase_at( &m_Head, key, key_comparator() );
588 /// Deletes the item from the list using \p pred predicate for searching
590 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
591 but \p pred is used for key comparing.
592 \p Less functor has the interface like \p std::less.
593 \p pred must imply the same element order as the comparator used for building the list.
595 template <typename Q, typename Less>
596 bool erase_with( Q const& key, Less pred )
598 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
601 /// Deletes the item from the list
602 /** \anchor cds_intrusive_LazyList_hp_erase_func
603 The function searches an item with key equal to \p key in the list,
604 call \p func functor with item found, unlinks it from the list, and returns \p true.
605 The \p Func interface is
608 void operator()( value_type const& item );
612 If \p key is not found the function return \p false.
614 template <typename Q, typename Func>
615 bool erase( const Q& key, Func func )
617 return erase_at( &m_Head, key, key_comparator(), func );
620 /// Deletes the item from the list using \p pred predicate for searching
622 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
623 but \p pred is used for key comparing.
624 \p Less functor has the interface like \p std::less.
625 \p pred must imply the same element order as the comparator used for building the list.
627 template <typename Q, typename Less, typename Func>
628 bool erase_with( const Q& key, Less pred, Func func )
630 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
633 /// Extracts the item from the list with specified \p key
634 /** \anchor cds_intrusive_LazyList_hp_extract
635 The function searches an item with key equal to \p key,
636 unlinks it from the list, and returns it in \p dest parameter.
637 If the item with key equal to \p key is not found the function returns \p false.
639 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
641 The \ref disposer specified in \p Traits class template parameter is called automatically
642 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
643 will be destroyed or released.
644 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
648 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
652 ord_list::guarded_ptr gp;
653 theList.extract( gp, 5 );
657 // Destructor of gp releases internal HP guard
661 template <typename Q>
662 bool extract( guarded_ptr& dest, Q const& key )
664 return extract_at( &m_Head, dest.guard(), key, key_comparator() );
667 /// Extracts the item from the list with comparing functor \p pred
669 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
670 but \p pred predicate is used for key comparing.
672 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
674 \p pred must imply the same element order as the comparator used for building the list.
676 template <typename Q, typename Less>
677 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
679 return extract_at( &m_Head, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
682 /// Finds the key \p key
683 /** \anchor cds_intrusive_LazyList_hp_find
684 The function searches the item with key equal to \p key and calls the functor \p f for item found.
685 The interface of \p Func functor is:
688 void operator()( value_type& item, Q& key );
691 where \p item is the item found, \p key is the <tt>find</tt> function argument.
693 The functor may change non-key fields of \p item.
694 While the functor \p f is calling the item \p item is locked.
696 The function returns \p true if \p key is found, \p false otherwise.
698 template <typename Q, typename Func>
699 bool find( Q& key, Func f )
701 return find_at( &m_Head, key, key_comparator(), f );
704 /// Finds the key \p key using \p pred predicate for searching
706 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
707 but \p pred is used for key comparing.
708 \p Less functor has the interface like \p std::less.
709 \p pred must imply the same element order as the comparator used for building the list.
711 template <typename Q, typename Less, typename Func>
712 bool find_with( Q& key, Less pred, Func f )
714 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
717 /// Finds the key \p key
718 /** \anchor cds_intrusive_LazyList_hp_find_val
719 The function searches the item with key equal to \p key
720 and returns \p true if it is found, and \p false otherwise
722 template <typename Q>
723 bool find( Q const & key )
725 return find_at( &m_Head, key, key_comparator() );
728 /// Finds \p key using \p pred predicate for searching
730 The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
731 but \p pred is used for key comparing.
732 \p Less functor has the interface like \p std::less.
733 \p pred must imply the same element order as the comparator used for building the list.
735 template <typename Q, typename Less>
736 bool find_with( Q const& key, Less pred )
738 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
741 /// Finds \p key and return the item found
742 /** \anchor cds_intrusive_LazyList_hp_get
743 The function searches the item with key equal to \p key
744 and assigns the item found to guarded pointer \p ptr.
745 The function returns \p true if \p key is found, and \p false otherwise.
746 If \p key is not found the \p ptr parameter is not changed.
748 The \ref disposer specified in \p Traits class template parameter is called
749 by garbage collector \p GC automatically when returned \ref guarded_ptr object
750 will be destroyed or released.
751 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
755 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
759 ord_list::guarded_ptr gp;
760 if ( theList.get( gp, 5 )) {
764 // Destructor of guarded_ptr releases internal HP guard
768 Note the compare functor specified for class \p Traits template parameter
769 should accept a parameter of type \p Q that can be not the same as \p value_type.
771 template <typename Q>
772 bool get( guarded_ptr& ptr, Q const& key )
774 return get_at( &m_Head, ptr.guard(), key, key_comparator() );
777 /// Finds \p key and return the item found
779 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
780 but \p pred is used for comparing the keys.
782 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
784 \p pred must imply the same element order as the comparator used for building the list.
786 template <typename Q, typename Less>
787 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
789 return get_at( &m_Head, ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
795 typename gc::Guard guard;
798 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
799 guard.assign( node_traits::to_value_ptr( h.ptr() ));
800 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
801 m_Head.m_Lock.lock();
804 unlink_node( &m_Head, h.ptr(), &m_Head );
807 m_Head.m_Lock.unlock();
809 retire_node( h.ptr() ) ; // free node
814 /// Checks if the list is empty
817 return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
820 /// Returns list's item count
822 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
823 this function always returns 0.
825 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
826 is empty. To check list emptyness use \p empty() method.
830 return m_ItemCounter.value();
835 // split-list support
836 bool insert_aux_node( node_type * pNode )
838 return insert_aux_node( &m_Head, pNode );
841 // split-list support
842 bool insert_aux_node( node_type * pHead, node_type * pNode )
844 assert( pNode != nullptr );
846 // Hack: convert node_type to value_type.
847 // In principle, auxiliary node cannot be reducible to value_type
848 // We assume that internal comparator can correctly distinguish aux and regular node.
849 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
852 bool insert_at( node_type * pHead, value_type& val )
854 link_checker::is_empty( node_traits::to_node_ptr( val ) );
859 search( pHead, val, pos, key_comparator() );
861 auto_lock_position alp( pos );
862 if ( validate( pos.pPred, pos.pCur )) {
863 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
864 // failed: key already in list
868 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
877 template <typename Func>
878 bool insert_at( node_type * pHead, value_type& val, Func f )
880 link_checker::is_empty( node_traits::to_node_ptr( val ) );
885 search( pHead, val, pos, key_comparator() );
887 auto_lock_position alp( pos );
888 if ( validate( pos.pPred, pos.pCur )) {
889 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
890 // failed: key already in list
894 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
904 template <typename Func>
905 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
911 search( pHead, val, pos, key_comparator() );
913 auto_lock_position alp( pos );
914 if ( validate( pos.pPred, pos.pCur )) {
915 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
916 // key already in the list
918 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
919 return std::make_pair( true, false );
923 link_checker::is_empty( node_traits::to_node_ptr( val ) );
925 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
926 func( true, val, val );
928 return std::make_pair( true, true );
935 bool unlink_at( node_type * pHead, value_type& val )
941 search( pHead, val, pos, key_comparator() );
945 auto_lock_position alp( pos );
946 if ( validate( pos.pPred, pos.pCur ) ) {
947 if ( pos.pCur != &m_Tail
948 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
949 && node_traits::to_value_ptr( pos.pCur ) == &val )
952 unlink_node( pos.pPred, pos.pCur, pHead );
962 retire_node( pos.pCur );
971 template <typename Q, typename Compare, typename Func>
972 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
975 search( pHead, val, pos, cmp );
979 auto_lock_position alp( pos );
980 if ( validate( pos.pPred, pos.pCur )) {
981 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
983 unlink_node( pos.pPred, pos.pCur, pHead );
984 f( *node_traits::to_value_ptr( *pos.pCur ) );
995 retire_node( pos.pCur );
1004 template <typename Q, typename Compare, typename Func>
1005 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1008 return erase_at( pHead, val, cmp, f, pos );
1011 template <typename Q, typename Compare>
1012 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1015 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1018 template <typename Q, typename Compare>
1019 bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1022 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1023 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1029 template <typename Q, typename Compare, typename Func>
1030 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1034 search( pHead, val, pos, cmp );
1035 if ( pos.pCur != &m_Tail ) {
1036 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1037 if ( !pos.pCur->is_marked()
1038 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1040 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1047 template <typename Q, typename Compare>
1048 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1052 search( pHead, val, pos, cmp );
1053 return pos.pCur != &m_Tail
1054 && !pos.pCur->is_marked()
1055 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1058 template <typename Q, typename Compare>
1059 bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1063 search( pHead, val, pos, cmp );
1064 if ( pos.pCur != &m_Tail
1065 && !pos.pCur->is_marked()
1066 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1068 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1078 template <typename Q, typename Compare>
1079 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1081 const node_type * pTail = &m_Tail;
1083 marked_node_ptr pCur( pHead );
1084 marked_node_ptr pPrev( pHead );
1088 while ( pCur.ptr() != pTail )
1090 if ( pCur.ptr() != pHead ) {
1091 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1095 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1099 pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1100 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1101 if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1105 assert( pCur.ptr() != nullptr );
1108 pos.pCur = pCur.ptr();
1109 pos.pPred = pPrev.ptr();
1112 static bool validate( node_type * pPred, node_type * pCur )
1114 return !pPred->is_marked()
1115 && !pCur->is_marked()
1116 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1121 }} // namespace cds::intrusive
1123 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H