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>
11 namespace cds { namespace intrusive {
13 /// Lazy ordered single-linked list
14 /** @ingroup cds_intrusive_list
15 \anchor cds_intrusive_LazyList_hp
17 Usually, ordered single-linked list is used as a building block for the hash table implementation.
18 The complexity of searching is <tt>O(N)</tt>.
21 - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
22 "A Lazy Concurrent List-Based Set Algorithm"
24 The lazy list is based on an optimistic locking scheme for inserts and removes,
25 eliminating the need to use the equivalent of an atomically markable
26 reference. It also has a novel wait-free membership \p find operation
27 that does not need to perform cleanup operations and is more efficient.
30 - \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).
31 - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
32 or it must have a member of type lazy_list::node (for lazy_list::member_hook).
33 - \p Traits - type traits. See lazy_list::type_traits for explanation.
35 It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
36 argument. For example, the following traits-based declaration of gc::HP lazy list
38 #include <cds/intrusive/lazy_list_hp.h>
39 // Declare item stored in your list
40 struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
43 // Declare comparator for the item
44 struct my_compare { ... }
46 // Declare type_traits
47 struct my_traits: public cds::intrusive::lazy_list::type_traits
49 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
50 typedef my_compare compare;
53 // Declare traits-based list
54 typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits > traits_based_list;
57 is equivalent for the following option-based list
59 #include <cds/intrusive/lazy_list_hp.h>
61 // item struct and my_compare are the same
63 // Declare option-based list
64 typedef cds::intrusive::LazyList< cds::gc::HP, item,
65 typename cds::intrusive::lazy_list::make_traits<
66 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
67 ,cds::intrusive::opt::compare< my_compare > // item comparator option
72 Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are:
73 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
74 If the option is not specified, <tt>lazy_list::base_hook<></tt> and gc::HP is used.
75 - opt::compare - key comparison functor. No default functor is provided.
76 If the option is not specified, the opt::less is used.
77 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
78 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
79 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
80 of GC schema the disposer may be called asynchronously.
81 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
82 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that means no item counting.
83 - opt::allocator - an allocator needed for dummy head and tail nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
84 The option applies only to gc::HRC garbage collector.
85 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
86 or opt::v::sequential_consistent (sequentially consisnent memory model).
89 There are different specializations of this template for each garbage collecting schema used.
90 You should select GC needed and include appropriate .h-file:
91 - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
92 - for gc::PTB: \code #include <cds/intrusive/lazy_list_ptb.h> \endcode
93 - for gc::HRC: \code #include <cds/intrusive/lazy_list_hrc.h> \endcode
94 - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
95 - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
97 Then, you should incorporate lazy_list::node into your struct \p T and provide
98 appropriate lazy_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits
99 a struct based on lazy_list::type_traits should be defined.
101 Example for gc::PTB and base hook:
103 // Include GC-related lazy list specialization
104 #include <cds/intrusive/lazy_list_ptb.h>
106 // Data stored in lazy list
107 struct my_data: public cds::intrusive::lazy_list::node< cds::gc::PTB >
116 // my_data comparing functor
118 int operator()( const my_data& d1, const my_data& d2 )
120 return d1.strKey.compare( d2.strKey );
123 int operator()( const my_data& d, const std::string& s )
125 return d.strKey.compare(s);
128 int operator()( const std::string& s, const my_data& d )
130 return s.compare( d.strKey );
135 // Declare type_traits
136 struct my_traits: public cds::intrusive::lazy_list::type_traits
138 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::PTB > > hook;
139 typedef my_data_cmp compare;
143 typedef cds::intrusive::LazyList< cds::gc::PTB, my_data, my_traits > traits_based_list;
146 Equivalent option-based code:
148 // GC-related specialization
149 #include <cds/intrusive/lazy_list_ptb.h>
158 // Declare option-based list
159 typedef cds::intrusive::LazyList< cds::gc::PTB
161 , typename cds::intrusive::lazy_list::make_traits<
162 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
163 ,cds::intrusive::opt::compare< my_data_cmp >
172 #ifdef CDS_DOXYGEN_INVOKED
173 ,class Traits = lazy_list::type_traits
181 typedef T value_type ; ///< type of value stored in the list
182 typedef Traits options ; ///< Traits template parameter
184 typedef typename options::hook hook ; ///< hook type
185 typedef typename hook::node_type node_type ; ///< node type
187 # ifdef CDS_DOXYGEN_INVOKED
188 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
190 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
193 typedef typename options::disposer disposer ; ///< disposer used
194 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
195 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
197 typedef GC gc ; ///< Garbage collector
198 typedef typename options::back_off back_off ; ///< back-off strategy
199 typedef typename options::item_counter item_counter ; ///< Item counting policy used
200 typedef typename options::memory_model memory_model; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
202 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
205 // Rebind options (split-list support)
206 template <typename... Options>
207 struct rebind_options {
211 , typename cds::opt::make_options< options, Options...>::type
217 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
218 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
222 typedef lazy_list::boundary_nodes<
224 ,typename opt::select_default< typename options::boundary_node_type, node_type >::type
225 ,typename options::allocator
227 boundary_nodes m_Boundary ; ///< Head & tail dummy nodes
231 return m_Boundary.head();
233 node_type const * head() const
235 return m_Boundary.head();
239 return m_Boundary.tail();
241 node_type const * tail() const
243 return m_Boundary.tail();
247 item_counter m_ItemCounter ; ///< Item counter
250 struct clean_disposer {
251 void operator()( value_type * p )
253 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
258 /// Position pointer for item search
260 node_type * pPred ; ///< Previous node
261 node_type * pCur ; ///< Current node
263 typename gc::template GuardArray<2> guards ; ///< Guards array
270 /// Locks nodes \p pPred and \p pCur
273 pPred->m_Lock.lock();
277 /// Unlocks nodes \p pPred and \p pCur
280 pCur->m_Lock.unlock();
281 pPred->m_Lock.unlock();
285 class auto_lock_position {
288 auto_lock_position( position& pos )
293 ~auto_lock_position()
302 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
304 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
306 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
307 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
310 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
312 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
314 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
315 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_release) ; // logically deleting
316 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // logical removal + back-link for search
317 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
318 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // back-link for search
321 void retire_node( node_type * pNode )
323 assert( pNode != nullptr );
324 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
330 template <bool IsConst>
333 friend class LazyList;
336 value_type * m_pNode;
337 typename gc::Guard m_Guard;
341 assert( m_pNode != nullptr );
344 typename gc::Guard g;
345 node_type * pCur = node_traits::to_node_ptr( m_pNode );
346 if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) { // if pCur is not tail node
349 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
350 g.assign( node_traits::to_value_ptr( pNext ));
351 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr() );
353 m_pNode = m_Guard.assign( g.template get<value_type>() );
360 if ( m_pNode != nullptr ) {
361 typename gc::Guard g;
362 node_type * pNode = node_traits::to_node_ptr( m_pNode );
364 // Dummy tail node could not be marked
365 while ( pNode->is_marked() ) {
366 node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
367 g.assign( node_traits::to_value_ptr( p ));
368 if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr() )
371 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
372 m_pNode = m_Guard.assign( g.template get<value_type>() );
376 iterator_type( node_type * pNode )
378 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
383 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
384 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
390 iterator_type( iterator_type const& src )
393 m_pNode = m_Guard.assign( src.m_pNode );
399 value_ptr operator ->() const
404 value_ref operator *() const
406 assert( m_pNode != nullptr );
411 iterator_type& operator ++()
418 iterator_type& operator = (iterator_type const& src)
420 m_pNode = src.m_pNode;
421 m_Guard.assign( m_pNode );
426 bool operator ==(iterator_type<C> const& i ) const
428 return m_pNode == i.m_pNode;
431 bool operator !=(iterator_type<C> const& i ) const
433 return m_pNode != i.m_pNode;
441 The forward iterator for lazy list has some features:
442 - it has no post-increment operator
443 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
444 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
445 may be thrown if a limit of guard count per thread is exceeded.
446 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
447 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
448 deleting operations it is no guarantee that you iterate all item in the list.
450 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
451 for debug purpose only.
453 typedef iterator_type<false> iterator;
454 /// Const forward iterator
456 For iterator's features and requirements see \ref iterator
458 typedef iterator_type<true> const_iterator;
460 /// Returns a forward iterator addressing the first element in a list
462 For empty list \code begin() == end() \endcode
466 iterator it( head() );
467 ++it ; // skip dummy head
471 /// Returns an iterator that addresses the location succeeding the last element in a list
473 Do not use the value returned by <tt>end</tt> function to access any item.
475 The returned value can be used only to control reaching the end of the list.
476 For empty list \code begin() == end() \endcode
480 return iterator( tail() );
483 /// Returns a forward const iterator addressing the first element in a list
485 const_iterator begin() const
487 return get_const_begin();
489 const_iterator cbegin()
491 return get_const_begin();
495 /// Returns an const iterator that addresses the location succeeding the last element in a list
497 const_iterator end() const
499 return get_const_end();
501 const_iterator cend()
503 return get_const_end();
509 const_iterator get_const_begin() const
511 const_iterator it( const_cast<node_type *>( head() ));
512 ++it ; // skip dummy head
515 const_iterator get_const_end() const
517 return const_iterator( const_cast<node_type *>( tail() ));
522 /// Default constructor initializes empty list
525 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
527 //m_pTail = cxx_allocator().New();
528 head()->m_pNext.store( marked_node_ptr( tail() ), memory_model::memory_order_relaxed );
531 /// Destroys the list object
535 assert( head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail() );
536 head()->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
541 The function inserts \p val in the list if the list does not contain
542 an item with key equal to \p val.
544 Returns \p true if \p val is linked into the list, \p false otherwise.
546 bool insert( value_type& val )
548 return insert_at( head(), val );
553 This function is intended for derived non-intrusive containers.
555 The function allows to split new item creating into two part:
556 - create item with key only
557 - insert new item into the list
558 - if inserting is success, calls \p f functor to initialize value-field of \p val.
560 The functor signature is:
562 void func( value_type& val );
564 where \p val is the item inserted.
565 While the functor \p f is working the item \p val is locked.
566 The user-defined functor is called only if the inserting is success and may be passed by reference
569 template <typename Func>
570 bool insert( value_type& val, Func f )
572 return insert_at( head(), val, f );
575 /// Ensures that the \p item exists in the list
577 The operation performs inserting or changing data with lock-free manner.
579 If the item \p val not found in the list, then \p val is inserted into the list.
580 Otherwise, the functor \p func is called with item found.
581 The functor signature is:
583 void func( bool bNew, value_type& item, value_type& val );
586 - \p bNew - \p true if the item has been inserted, \p false otherwise
587 - \p item - item of the list
588 - \p val - argument \p val passed into the \p ensure function
589 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
590 refer to the same thing.
592 The functor may change non-key fields of the \p item.
593 While the functor \p f is working the item \p item is locked.
595 You may pass \p func argument by reference using \p std::ref.
597 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
598 \p second is \p true if new item has been added or \p false if the item with \p key
599 already is in the list.
601 template <typename Func>
602 std::pair<bool, bool> ensure( value_type& val, Func func )
604 return ensure_at( head(), val, func );
607 /// Unlinks the item \p val from the list
609 The function searches the item \p val in the list and unlink it from the list
610 if it is found and it is equal to \p val.
612 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
613 and deletes the item found. \p unlink finds an item by key and deletes it
614 only if \p val is an item of that list, i.e. the pointer to item found
615 is equal to <tt> &val </tt>.
617 The function returns \p true if success and \p false otherwise.
619 bool unlink( value_type& val )
621 return unlink_at( head(), val );
624 /// Deletes the item from the list
625 /** \anchor cds_intrusive_LazyList_hp_erase_val
626 The function searches an item with key equal to \p val in the list,
627 unlinks it from the list, and returns \p true.
628 If the item with the key equal to \p val is not found the function return \p false.
630 template <typename Q>
631 bool erase( Q const& val )
633 return erase_at( head(), val, key_comparator() );
636 /// Deletes the item from the list using \p pred predicate for searching
638 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
639 but \p pred is used for key comparing.
640 \p Less functor has the interface like \p std::less.
641 \p pred must imply the same element order as the comparator used for building the list.
643 template <typename Q, typename Less>
644 bool erase_with( Q const& val, Less pred )
646 return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
649 /// Deletes the item from the list
650 /** \anchor cds_intrusive_LazyList_hp_erase_func
651 The function searches an item with key equal to \p val in the list,
652 call \p func functor with item found, unlinks it from the list, and returns \p true.
653 The \p Func interface is
656 void operator()( value_type const& item );
659 The functor may be passed by reference using <tt>boost:ref</tt>
661 If the item with the key equal to \p val is not found the function return \p false.
663 template <typename Q, typename Func>
664 bool erase( const Q& val, Func func )
666 return erase_at( head(), val, key_comparator(), func );
669 /// Deletes the item from the list using \p pred predicate for searching
671 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
672 but \p pred is used for key comparing.
673 \p Less functor has the interface like \p std::less.
674 \p pred must imply the same element order as the comparator used for building the list.
676 template <typename Q, typename Less, typename Func>
677 bool erase_with( const Q& val, Less pred, Func func )
679 return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), func );
682 /// Extracts the item from the list with specified \p key
683 /** \anchor cds_intrusive_LazyList_hp_extract
684 The function searches an item with key equal to \p key,
685 unlinks it from the list, and returns it in \p dest parameter.
686 If the item with key equal to \p key is not found the function returns \p false.
688 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
690 The \ref disposer specified in \p Traits class template parameter is called automatically
691 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
692 will be destroyed or released.
693 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
697 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
701 ord_list::guarded_ptr gp;
702 theList.extract( gp, 5 );
706 // Destructor of gp releases internal HP guard
710 template <typename Q>
711 bool extract( guarded_ptr& dest, Q const& key )
713 return extract_at( head(), dest.guard(), key, key_comparator() );
716 /// Extracts the item from the list with comparing functor \p pred
718 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
719 but \p pred predicate is used for key comparing.
721 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
723 \p pred must imply the same element order as the comparator used for building the list.
725 template <typename Q, typename Less>
726 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
728 return extract_at( head(), dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
731 /// Finds the key \p val
732 /** \anchor cds_intrusive_LazyList_hp_find
733 The function searches the item with key equal to \p val and calls the functor \p f for item found.
734 The interface of \p Func functor is:
737 void operator()( value_type& item, Q& val );
740 where \p item is the item found, \p val is the <tt>find</tt> function argument.
742 You may pass \p f argument by reference using \p std::ref.
744 The functor may change non-key fields of \p item.
745 While the functor \p f is calling the item \p item is locked.
747 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
748 may modify both arguments.
750 The function returns \p true if \p val is found, \p false otherwise.
752 template <typename Q, typename Func>
753 bool find( Q& val, Func f )
755 return find_at( head(), val, key_comparator(), f );
758 /// Finds the key \p val using \p pred predicate for searching
760 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
761 but \p pred is used for key comparing.
762 \p Less functor has the interface like \p std::less.
763 \p pred must imply the same element order as the comparator used for building the list.
765 template <typename Q, typename Less, typename Func>
766 bool find_with( Q& val, Less pred, Func f )
768 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
771 /// Finds the key \p val
772 /** \anchor cds_intrusive_LazyList_hp_find_const
773 The function searches the item with key equal to \p val and calls the functor \p f for item found.
774 The interface of \p Func functor is:
777 void operator()( value_type& item, Q const& val );
780 where \p item is the item found, \p val is the \p find function argument.
782 You may pass \p f argument by reference using \p std::ref.
784 The functor may change non-key fields of \p item.
785 While the functor \p f is calling the item \p item is locked.
787 The function returns \p true if \p val is found, \p false otherwise.
789 template <typename Q, typename Func>
790 bool find( Q const& val, Func f )
792 return find_at( head(), val, key_comparator(), f );
795 /// Finds the key \p val using \p pred predicate for searching
797 The function is an analog of \ref cds_intrusive_LazyList_hp_find_const "find(Q const&, Func)"
798 but \p pred is used for key comparing.
799 \p Less functor has the interface like \p std::less.
800 \p pred must imply the same element order as the comparator used for building the list.
802 template <typename Q, typename Less, typename Func>
803 bool find_with( Q const& val, Less pred, Func f )
805 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
808 /// Finds the key \p val
809 /** \anchor cds_intrusive_LazyList_hp_find_val
810 The function searches the item with key equal to \p val
811 and returns \p true if it is found, and \p false otherwise
813 template <typename Q>
814 bool find( Q const & val )
816 return find_at( head(), val, key_comparator() );
819 /// Finds the key \p val using \p pred predicate for searching
821 The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
822 but \p pred is used for key comparing.
823 \p Less functor has the interface like \p std::less.
824 \p pred must imply the same element order as the comparator used for building the list.
826 template <typename Q, typename Less>
827 bool find_with( Q const& val, Less pred )
829 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
832 /// Finds the key \p val and return the item found
833 /** \anchor cds_intrusive_LazyList_hp_get
834 The function searches the item with key equal to \p val
835 and assigns the item found to guarded pointer \p ptr.
836 The function returns \p true if \p val is found, and \p false otherwise.
837 If \p val is not found the \p ptr parameter is not changed.
839 The \ref disposer specified in \p Traits class template parameter is called
840 by garbage collector \p GC automatically when returned \ref guarded_ptr object
841 will be destroyed or released.
842 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
846 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
850 ord_list::guarded_ptr gp;
851 if ( theList.get( gp, 5 )) {
855 // Destructor of guarded_ptr releases internal HP guard
859 Note the compare functor specified for class \p Traits template parameter
860 should accept a parameter of type \p Q that can be not the same as \p value_type.
862 template <typename Q>
863 bool get( guarded_ptr& ptr, Q const& val )
865 return get_at( head(), ptr.guard(), val, key_comparator() );
868 /// Finds the key \p val and return the item found
870 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
871 but \p pred is used for comparing the keys.
873 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
875 \p pred must imply the same element order as the comparator used for building the list.
877 template <typename Q, typename Less>
878 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
880 return get_at( head(), ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
885 The function unlink all items from the list.
889 typename gc::Guard guard;
892 h = head()->m_pNext.load(memory_model::memory_order_relaxed);
893 guard.assign( node_traits::to_value_ptr( h.ptr() ));
894 if ( head()->m_pNext.load(memory_model::memory_order_acquire) == h ) {
895 head()->m_Lock.lock();
898 unlink_node( head(), h.ptr(), head() );
901 head()->m_Lock.unlock();
903 retire_node( h.ptr() ) ; // free node
908 /// Checks if the list is empty
911 return head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail();
914 /// Returns list's item count
916 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
917 this function always returns 0.
919 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
920 is empty. To check list emptyness use \ref empty() method.
924 return m_ItemCounter.value();
929 // split-list support
930 bool insert_aux_node( node_type * pNode )
932 return insert_aux_node( head(), pNode );
935 // split-list support
936 bool insert_aux_node( node_type * pHead, node_type * pNode )
938 assert( pNode != nullptr );
940 // Hack: convert node_type to value_type.
941 // In principle, auxiliary node can be non-reducible to value_type
942 // We assume that comparator can correctly distinguish aux and regular node.
943 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
946 bool insert_at( node_type * pHead, value_type& val )
948 link_checker::is_empty( node_traits::to_node_ptr( val ) );
953 search( pHead, val, pos, key_comparator() );
955 auto_lock_position alp( pos );
956 if ( validate( pos.pPred, pos.pCur )) {
957 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
958 // failed: key already in list
962 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
971 template <typename Func>
972 bool insert_at( node_type * pHead, value_type& val, Func f )
974 link_checker::is_empty( node_traits::to_node_ptr( val ) );
979 search( pHead, val, pos, key_comparator() );
981 auto_lock_position alp( pos );
982 if ( validate( pos.pPred, pos.pCur )) {
983 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
984 // failed: key already in list
988 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
998 template <typename Func>
999 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
1005 search( pHead, val, pos, key_comparator() );
1007 auto_lock_position alp( pos );
1008 if ( validate( pos.pPred, pos.pCur )) {
1009 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1010 // key already in the list
1012 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1013 return std::make_pair( true, false );
1017 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1019 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1020 func( true, val, val );
1022 return std::make_pair( true, true );
1029 bool unlink_at( node_type * pHead, value_type& val )
1035 search( pHead, val, pos, key_comparator() );
1039 auto_lock_position alp( pos );
1040 if ( validate( pos.pPred, pos.pCur ) ) {
1041 if ( pos.pCur != tail()
1042 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1043 && node_traits::to_value_ptr( pos.pCur ) == &val )
1046 unlink_node( pos.pPred, pos.pCur, pHead );
1055 if ( nResult > 0 ) {
1056 retire_node( pos.pCur );
1065 template <typename Q, typename Compare, typename Func>
1066 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1069 search( pHead, val, pos, cmp );
1073 auto_lock_position alp( pos );
1074 if ( validate( pos.pPred, pos.pCur )) {
1075 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1077 unlink_node( pos.pPred, pos.pCur, pHead );
1078 f( *node_traits::to_value_ptr( *pos.pCur ) );
1088 if ( nResult > 0 ) {
1089 retire_node( pos.pCur );
1098 template <typename Q, typename Compare, typename Func>
1099 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1102 return erase_at( pHead, val, cmp, f, pos );
1105 template <typename Q, typename Compare>
1106 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1109 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1112 template <typename Q, typename Compare>
1113 bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1116 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1117 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1123 template <typename Q, typename Compare, typename Func>
1124 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1128 search( pHead, val, pos, cmp );
1129 if ( pos.pCur != tail() ) {
1130 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1131 if ( !pos.pCur->is_marked()
1132 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1134 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1141 template <typename Q, typename Compare>
1142 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1146 search( pHead, val, pos, cmp );
1147 return pos.pCur != tail()
1148 && !pos.pCur->is_marked()
1149 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1152 template <typename Q, typename Compare>
1153 bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1157 search( pHead, val, pos, cmp );
1158 if ( pos.pCur != tail()
1159 && !pos.pCur->is_marked()
1160 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1162 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1172 template <typename Q, typename Compare>
1173 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1175 const node_type * pTail = tail();
1177 marked_node_ptr pCur( pHead );
1178 marked_node_ptr pPrev( pHead );
1182 while ( pCur.ptr() != pTail )
1184 if ( pCur.ptr() != pHead ) {
1185 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1189 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1193 pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1194 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1195 if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1199 assert( pCur.ptr() != nullptr );
1202 pos.pCur = pCur.ptr();
1203 pos.pPred = pPrev.ptr();
1206 static bool validate( node_type * pPred, node_type * pCur )
1208 return !pPred->is_marked()
1209 && !pCur->is_marked()
1210 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1215 }} // namespace cds::intrusive
1217 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H