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 called the item \p val is locked so
521 the functor has an exclusive access to the item.
522 The user-defined functor is called only if the inserting is success.
524 template <typename Func>
525 bool insert( value_type& val, Func f )
527 return insert_at( &m_Head, val, f );
530 /// Ensures that the \p item exists in the list
532 The operation performs inserting or changing data with lock-free manner.
534 If the item \p val not found in the list, then \p val is inserted into the list.
535 Otherwise, the functor \p func is called with item found.
536 The functor signature is:
538 void func( bool bNew, value_type& item, value_type& val );
541 - \p bNew - \p true if the item has been inserted, \p false otherwise
542 - \p item - item of the list
543 - \p val - argument \p val passed into the \p ensure function
544 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
545 refer to the same thing.
547 The functor may change non-key fields of the \p item.
548 While the functor \p f is working the item \p item is locked,
549 so \p f has exclusive access to the item.
551 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
552 \p second is \p true if new item has been added or \p false if the item with \p key
553 already is in the list.
555 template <typename Func>
556 std::pair<bool, bool> ensure( value_type& val, Func func )
558 return ensure_at( &m_Head, val, func );
561 /// Unlinks the item \p val from the list
563 The function searches the item \p val in the list and unlink it from the list
564 if it is found and it is equal to \p val.
566 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
567 and deletes the item found. \p unlink finds an item by key and deletes it
568 only if \p val is an item of that list, i.e. the pointer to item found
569 is equal to <tt> &val </tt>.
571 The function returns \p true if success and \p false otherwise.
573 bool unlink( value_type& val )
575 return unlink_at( &m_Head, val );
578 /// Deletes the item from the list
579 /** \anchor cds_intrusive_LazyList_hp_erase_val
580 The function searches an item with key equal to \p key in the list,
581 unlinks it from the list, and returns \p true.
582 If the item with the key equal to \p key is not found the function return \p false.
584 template <typename Q>
585 bool erase( Q const& key )
587 return erase_at( &m_Head, key, key_comparator() );
590 /// Deletes the item from the list using \p pred predicate for searching
592 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
593 but \p pred is used for key comparing.
594 \p Less functor has the interface like \p std::less.
595 \p pred must imply the same element order as the comparator used for building the list.
597 template <typename Q, typename Less>
598 bool erase_with( Q const& key, Less pred )
600 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
603 /// Deletes the item from the list
604 /** \anchor cds_intrusive_LazyList_hp_erase_func
605 The function searches an item with key equal to \p key in the list,
606 call \p func functor with item found, unlinks it from the list, and returns \p true.
607 The \p Func interface is
610 void operator()( value_type const& item );
614 If \p key is not found the function return \p false.
616 template <typename Q, typename Func>
617 bool erase( const Q& key, Func func )
619 return erase_at( &m_Head, key, key_comparator(), func );
622 /// Deletes the item from the list using \p pred predicate for searching
624 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
625 but \p pred is used for key comparing.
626 \p Less functor has the interface like \p std::less.
627 \p pred must imply the same element order as the comparator used for building the list.
629 template <typename Q, typename Less, typename Func>
630 bool erase_with( const Q& key, Less pred, Func func )
632 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
635 /// Extracts the item from the list with specified \p key
636 /** \anchor cds_intrusive_LazyList_hp_extract
637 The function searches an item with key equal to \p key,
638 unlinks it from the list, and returns it in \p dest parameter.
639 If the item with key equal to \p key is not found the function returns \p false.
641 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
643 The \ref disposer specified in \p Traits class template parameter is called automatically
644 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
645 will be destroyed or released.
646 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
650 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
654 ord_list::guarded_ptr gp;
655 theList.extract( gp, 5 );
659 // Destructor of gp releases internal HP guard
663 template <typename Q>
664 bool extract( guarded_ptr& dest, Q const& key )
666 return extract_at( &m_Head, dest.guard(), key, key_comparator() );
669 /// Extracts the item from the list with comparing functor \p pred
671 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
672 but \p pred predicate is used for key comparing.
674 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
676 \p pred must imply the same element order as the comparator used for building the list.
678 template <typename Q, typename Less>
679 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
681 return extract_at( &m_Head, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
684 /// Finds the key \p key
685 /** \anchor cds_intrusive_LazyList_hp_find
686 The function searches the item with key equal to \p key and calls the functor \p f for item found.
687 The interface of \p Func functor is:
690 void operator()( value_type& item, Q& key );
693 where \p item is the item found, \p key is the <tt>find</tt> function argument.
695 The functor may change non-key fields of \p item.
696 While the functor \p f is calling the item \p item is locked.
698 The function returns \p true if \p key is found, \p false otherwise.
700 template <typename Q, typename Func>
701 bool find( Q& key, Func f )
703 return find_at( &m_Head, key, key_comparator(), f );
706 /// Finds the key \p key using \p pred predicate for searching
708 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
709 but \p pred is used for key comparing.
710 \p Less functor has the interface like \p std::less.
711 \p pred must imply the same element order as the comparator used for building the list.
713 template <typename Q, typename Less, typename Func>
714 bool find_with( Q& key, Less pred, Func f )
716 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
719 /// Finds the key \p key
720 /** \anchor cds_intrusive_LazyList_hp_find_val
721 The function searches the item with key equal to \p key
722 and returns \p true if it is found, and \p false otherwise
724 template <typename Q>
725 bool find( Q const & key )
727 return find_at( &m_Head, key, key_comparator() );
730 /// Finds \p key using \p pred predicate for searching
732 The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
733 but \p pred is used for key comparing.
734 \p Less functor has the interface like \p std::less.
735 \p pred must imply the same element order as the comparator used for building the list.
737 template <typename Q, typename Less>
738 bool find_with( Q const& key, Less pred )
740 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
743 /// Finds \p key and return the item found
744 /** \anchor cds_intrusive_LazyList_hp_get
745 The function searches the item with key equal to \p key
746 and assigns the item found to guarded pointer \p ptr.
747 The function returns \p true if \p key is found, and \p false otherwise.
748 If \p key is not found the \p ptr parameter is not changed.
750 The \ref disposer specified in \p Traits class template parameter is called
751 by garbage collector \p GC automatically when returned \ref guarded_ptr object
752 will be destroyed or released.
753 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
757 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
761 ord_list::guarded_ptr gp;
762 if ( theList.get( gp, 5 )) {
766 // Destructor of guarded_ptr releases internal HP guard
770 Note the compare functor specified for class \p Traits template parameter
771 should accept a parameter of type \p Q that can be not the same as \p value_type.
773 template <typename Q>
774 bool get( guarded_ptr& ptr, Q const& key )
776 return get_at( &m_Head, ptr.guard(), key, key_comparator() );
779 /// Finds \p key and return the item found
781 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
782 but \p pred is used for comparing the keys.
784 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
786 \p pred must imply the same element order as the comparator used for building the list.
788 template <typename Q, typename Less>
789 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
791 return get_at( &m_Head, ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
797 typename gc::Guard guard;
800 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
801 guard.assign( node_traits::to_value_ptr( h.ptr() ));
802 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
803 m_Head.m_Lock.lock();
806 unlink_node( &m_Head, h.ptr(), &m_Head );
809 m_Head.m_Lock.unlock();
811 retire_node( h.ptr() ) ; // free node
816 /// Checks if the list is empty
819 return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
822 /// Returns list's item count
824 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
825 this function always returns 0.
827 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
828 is empty. To check list emptyness use \p empty() method.
832 return m_ItemCounter.value();
837 // split-list support
838 bool insert_aux_node( node_type * pNode )
840 return insert_aux_node( &m_Head, pNode );
843 // split-list support
844 bool insert_aux_node( node_type * pHead, node_type * pNode )
846 assert( pNode != nullptr );
848 // Hack: convert node_type to value_type.
849 // In principle, auxiliary node cannot be reducible to value_type
850 // We assume that internal comparator can correctly distinguish aux and regular node.
851 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
854 bool insert_at( node_type * pHead, value_type& val )
856 link_checker::is_empty( node_traits::to_node_ptr( val ) );
861 search( pHead, val, pos, key_comparator() );
863 auto_lock_position alp( pos );
864 if ( validate( pos.pPred, pos.pCur )) {
865 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
866 // failed: key already in list
870 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
879 template <typename Func>
880 bool insert_at( node_type * pHead, value_type& val, Func f )
882 link_checker::is_empty( node_traits::to_node_ptr( val ) );
887 search( pHead, val, pos, key_comparator() );
889 auto_lock_position alp( pos );
890 if ( validate( pos.pPred, pos.pCur )) {
891 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
892 // failed: key already in list
896 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
906 template <typename Func>
907 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
913 search( pHead, val, pos, key_comparator() );
915 auto_lock_position alp( pos );
916 if ( validate( pos.pPred, pos.pCur )) {
917 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
918 // key already in the list
920 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
921 return std::make_pair( true, false );
925 link_checker::is_empty( node_traits::to_node_ptr( val ) );
927 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
928 func( true, val, val );
930 return std::make_pair( true, true );
937 bool unlink_at( node_type * pHead, value_type& val )
943 search( pHead, val, pos, key_comparator() );
947 auto_lock_position alp( pos );
948 if ( validate( pos.pPred, pos.pCur ) ) {
949 if ( pos.pCur != &m_Tail
950 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
951 && node_traits::to_value_ptr( pos.pCur ) == &val )
954 unlink_node( pos.pPred, pos.pCur, pHead );
964 retire_node( pos.pCur );
973 template <typename Q, typename Compare, typename Func>
974 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
977 search( pHead, val, pos, cmp );
981 auto_lock_position alp( pos );
982 if ( validate( pos.pPred, pos.pCur )) {
983 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
985 unlink_node( pos.pPred, pos.pCur, pHead );
986 f( *node_traits::to_value_ptr( *pos.pCur ) );
997 retire_node( pos.pCur );
1006 template <typename Q, typename Compare, typename Func>
1007 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1010 return erase_at( pHead, val, cmp, f, pos );
1013 template <typename Q, typename Compare>
1014 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1017 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1020 template <typename Q, typename Compare>
1021 bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1024 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1025 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1031 template <typename Q, typename Compare, typename Func>
1032 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1036 search( pHead, val, pos, cmp );
1037 if ( pos.pCur != &m_Tail ) {
1038 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1039 if ( !pos.pCur->is_marked()
1040 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1042 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1049 template <typename Q, typename Compare>
1050 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1054 search( pHead, val, pos, cmp );
1055 return pos.pCur != &m_Tail
1056 && !pos.pCur->is_marked()
1057 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1060 template <typename Q, typename Compare>
1061 bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1065 search( pHead, val, pos, cmp );
1066 if ( pos.pCur != &m_Tail
1067 && !pos.pCur->is_marked()
1068 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1070 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1080 template <typename Q, typename Compare>
1081 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1083 const node_type * pTail = &m_Tail;
1085 marked_node_ptr pCur( pHead );
1086 marked_node_ptr pPrev( pHead );
1090 while ( pCur.ptr() != pTail )
1092 if ( pCur.ptr() != pHead ) {
1093 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1097 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1101 pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1102 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1103 if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1107 assert( pCur.ptr() != nullptr );
1110 pos.pCur = pCur.ptr();
1111 pos.pPred = pPrev.ptr();
1114 static bool validate( node_type * pPred, node_type * pCur )
1116 return !pPred->is_marked()
1117 && !pCur->is_marked()
1118 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1123 }} // namespace cds::intrusive
1125 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H