3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_IMPL_H
4 #define __CDS_INTRUSIVE_LAZY_LIST_IMPL_H
6 #include <cds/intrusive/lazy_list_base.h>
7 #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::type_traits for explanation.
34 It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
35 argument. For example, the following traits-based declaration of gc::HP lazy list
37 #include <cds/intrusive/lazy_list_hp.h>
38 // Declare item stored in your list
39 struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
42 // Declare comparator for the item
43 struct my_compare { ... }
45 // Declare type_traits
46 struct my_traits: public cds::intrusive::lazy_list::type_traits
48 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
49 typedef my_compare compare;
52 // Declare traits-based list
53 typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits > traits_based_list;
56 is equivalent for the following option-based list
58 #include <cds/intrusive/lazy_list_hp.h>
60 // item struct and my_compare are the same
62 // Declare option-based list
63 typedef cds::intrusive::LazyList< cds::gc::HP, item,
64 typename cds::intrusive::lazy_list::make_traits<
65 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
66 ,cds::intrusive::opt::compare< my_compare > // item comparator option
71 Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are:
72 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
73 If the option is not specified, <tt>lazy_list::base_hook<></tt> and gc::HP is used.
74 - opt::compare - key comparison functor. No default functor is provided.
75 If the option is not specified, the opt::less is used.
76 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
77 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
78 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
79 of GC schema the disposer may be called asynchronously.
80 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
81 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that means no item counting.
82 - opt::allocator - an allocator needed for dummy head and tail nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
83 The option applies only to gc::HRC garbage collector.
84 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
85 or opt::v::sequential_consistent (sequentially consisnent memory model).
88 There are different specializations of this template for each garbage collecting schema used.
89 You should select GC needed and include appropriate .h-file:
90 - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
91 - for gc::PTB: \code #include <cds/intrusive/lazy_list_ptb.h> \endcode
92 - for gc::HRC: \code #include <cds/intrusive/lazy_list_hrc.h> \endcode
93 - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
94 - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
96 Then, you should incorporate lazy_list::node into your struct \p T and provide
97 appropriate lazy_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits
98 a struct based on lazy_list::type_traits should be defined.
100 Example for gc::PTB and base hook:
102 // Include GC-related lazy list specialization
103 #include <cds/intrusive/lazy_list_ptb.h>
105 // Data stored in lazy list
106 struct my_data: public cds::intrusive::lazy_list::node< cds::gc::PTB >
115 // my_data comparing functor
117 int operator()( const my_data& d1, const my_data& d2 )
119 return d1.strKey.compare( d2.strKey );
122 int operator()( const my_data& d, const std::string& s )
124 return d.strKey.compare(s);
127 int operator()( const std::string& s, const my_data& d )
129 return s.compare( d.strKey );
134 // Declare type_traits
135 struct my_traits: public cds::intrusive::lazy_list::type_traits
137 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::PTB > > hook;
138 typedef my_data_cmp compare;
142 typedef cds::intrusive::LazyList< cds::gc::PTB, my_data, my_traits > traits_based_list;
145 Equivalent option-based code:
147 // GC-related specialization
148 #include <cds/intrusive/lazy_list_ptb.h>
157 // Declare option-based list
158 typedef cds::intrusive::LazyList< cds::gc::PTB
160 , typename cds::intrusive::lazy_list::make_traits<
161 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
162 ,cds::intrusive::opt::compare< my_data_cmp >
171 #ifdef CDS_DOXYGEN_INVOKED
172 ,class Traits = lazy_list::type_traits
180 typedef T value_type ; ///< type of value stored in the list
181 typedef Traits options ; ///< Traits template parameter
183 typedef typename options::hook hook ; ///< hook type
184 typedef typename hook::node_type node_type ; ///< node type
186 # ifdef CDS_DOXYGEN_INVOKED
187 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
189 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
192 typedef typename options::disposer disposer ; ///< disposer used
193 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
194 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
196 typedef GC gc ; ///< Garbage collector
197 typedef typename options::back_off back_off ; ///< back-off strategy
198 typedef typename options::item_counter item_counter ; ///< Item counting policy used
199 typedef typename options::memory_model memory_model; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
201 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
204 // Rebind options (split-list support)
205 template <CDS_DECL_OPTIONS8>
206 struct rebind_options {
210 , typename cds::opt::make_options< options, CDS_OPTIONS8>::type
216 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
217 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
221 typedef lazy_list::boundary_nodes<
223 ,typename opt::select_default< typename options::boundary_node_type, node_type >::type
224 ,typename options::allocator
226 boundary_nodes m_Boundary ; ///< Head & tail dummy nodes
230 return m_Boundary.head();
232 node_type const * head() const
234 return m_Boundary.head();
238 return m_Boundary.tail();
240 node_type const * tail() const
242 return m_Boundary.tail();
246 item_counter m_ItemCounter ; ///< Item counter
249 struct clean_disposer {
250 void operator()( value_type * p )
252 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
257 /// Position pointer for item search
259 node_type * pPred ; ///< Previous node
260 node_type * pCur ; ///< Current node
262 typename gc::template GuardArray<2> guards ; ///< Guards array
269 /// Locks nodes \p pPred and \p pCur
272 pPred->m_Lock.lock();
276 /// Unlocks nodes \p pPred and \p pCur
279 pCur->m_Lock.unlock();
280 pPred->m_Lock.unlock();
284 class auto_lock_position {
287 auto_lock_position( position& pos )
292 ~auto_lock_position()
298 # ifndef CDS_CXX11_LAMBDA_SUPPORT
299 struct empty_erase_functor {
300 void operator()( value_type const & item )
308 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
310 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
312 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
313 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
316 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
318 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
320 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
321 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_release) ; // logically deleting
322 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // logical removal + back-link for search
323 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
324 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // back-link for search
327 void retire_node( node_type * pNode )
329 assert( pNode != nullptr );
330 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
336 template <bool IsConst>
339 friend class LazyList;
342 value_type * m_pNode;
343 typename gc::Guard m_Guard;
347 assert( m_pNode != nullptr );
350 typename gc::Guard g;
351 node_type * pCur = node_traits::to_node_ptr( m_pNode );
352 if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) { // if pCur is not tail node
355 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
356 g.assign( node_traits::to_value_ptr( pNext ));
357 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr() );
359 m_pNode = m_Guard.assign( g.template get<value_type>() );
366 if ( m_pNode != nullptr ) {
367 typename gc::Guard g;
368 node_type * pNode = node_traits::to_node_ptr( m_pNode );
370 // Dummy tail node could not be marked
371 while ( pNode->is_marked() ) {
372 node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
373 g.assign( node_traits::to_value_ptr( p ));
374 if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr() )
377 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
378 m_pNode = m_Guard.assign( g.template get<value_type>() );
382 iterator_type( node_type * pNode )
384 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
389 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
390 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
396 iterator_type( iterator_type const& src )
399 m_pNode = m_Guard.assign( src.m_pNode );
405 value_ptr operator ->() const
410 value_ref operator *() const
412 assert( m_pNode != nullptr );
417 iterator_type& operator ++()
424 iterator_type& operator = (iterator_type const& src)
426 m_pNode = src.m_pNode;
427 m_Guard.assign( m_pNode );
432 bool operator ==(iterator_type<C> const& i ) const
434 return m_pNode == i.m_pNode;
437 bool operator !=(iterator_type<C> const& i ) const
439 return m_pNode != i.m_pNode;
447 The forward iterator for lazy list has some features:
448 - it has no post-increment operator
449 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
450 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
451 may be thrown if a limit of guard count per thread is exceeded.
452 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
453 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
454 deleting operations it is no guarantee that you iterate all item in the list.
456 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
457 for debug purpose only.
459 typedef iterator_type<false> iterator;
460 /// Const forward iterator
462 For iterator's features and requirements see \ref iterator
464 typedef iterator_type<true> const_iterator;
466 /// Returns a forward iterator addressing the first element in a list
468 For empty list \code begin() == end() \endcode
472 iterator it( head() );
473 ++it ; // skip dummy head
477 /// Returns an iterator that addresses the location succeeding the last element in a list
479 Do not use the value returned by <tt>end</tt> function to access any item.
481 The returned value can be used only to control reaching the end of the list.
482 For empty list \code begin() == end() \endcode
486 return iterator( tail() );
489 /// Returns a forward const iterator addressing the first element in a list
491 const_iterator begin() const
493 return get_const_begin();
495 const_iterator cbegin()
497 return get_const_begin();
501 /// Returns an const iterator that addresses the location succeeding the last element in a list
503 const_iterator end() const
505 return get_const_end();
507 const_iterator cend()
509 return get_const_end();
515 const_iterator get_const_begin() const
517 const_iterator it( const_cast<node_type *>( head() ));
518 ++it ; // skip dummy head
521 const_iterator get_const_end() const
523 return const_iterator( const_cast<node_type *>( tail() ));
528 /// Default constructor initializes empty list
531 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
533 //m_pTail = cxx_allocator().New();
534 head()->m_pNext.store( marked_node_ptr( tail() ), memory_model::memory_order_relaxed );
537 /// Destroys the list object
541 assert( head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail() );
542 head()->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
547 The function inserts \p val in the list if the list does not contain
548 an item with key equal to \p val.
550 Returns \p true if \p val is linked into the list, \p false otherwise.
552 bool insert( value_type& val )
554 return insert_at( head(), val );
559 This function is intended for derived non-intrusive containers.
561 The function allows to split new item creating into two part:
562 - create item with key only
563 - insert new item into the list
564 - if inserting is success, calls \p f functor to initialize value-field of \p val.
566 The functor signature is:
568 void func( value_type& val );
570 where \p val is the item inserted.
571 While the functor \p f is working the item \p val is locked.
572 The user-defined functor is called only if the inserting is success and may be passed by reference
573 using <tt>boost::ref</tt>.
575 template <typename Func>
576 bool insert( value_type& val, Func f )
578 return insert_at( head(), val, f );
581 /// Ensures that the \p item exists in the list
583 The operation performs inserting or changing data with lock-free manner.
585 If the item \p val not found in the list, then \p val is inserted into the list.
586 Otherwise, the functor \p func is called with item found.
587 The functor signature is:
589 void func( bool bNew, value_type& item, value_type& val );
592 - \p bNew - \p true if the item has been inserted, \p false otherwise
593 - \p item - item of the list
594 - \p val - argument \p val passed into the \p ensure function
595 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
596 refer to the same thing.
598 The functor may change non-key fields of the \p item.
599 While the functor \p f is working the item \p item is locked.
601 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
603 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
604 \p second is \p true if new item has been added or \p false if the item with \p key
605 already is in the list.
607 template <typename Func>
608 std::pair<bool, bool> ensure( value_type& val, Func func )
610 return ensure_at( head(), val, func );
613 /// Unlinks the item \p val from the list
615 The function searches the item \p val in the list and unlink it from the list
616 if it is found and it is equal to \p val.
618 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
619 and deletes the item found. \p unlink finds an item by key and deletes it
620 only if \p val is an item of that list, i.e. the pointer to item found
621 is equal to <tt> &val </tt>.
623 The function returns \p true if success and \p false otherwise.
625 bool unlink( value_type& val )
627 return unlink_at( head(), val );
630 /// Deletes the item from the list
631 /** \anchor cds_intrusive_LazyList_hp_erase_val
632 The function searches an item with key equal to \p val in the list,
633 unlinks it from the list, and returns \p true.
634 If the item with the key equal to \p val is not found the function return \p false.
636 template <typename Q>
637 bool erase( Q const& val )
639 return erase_at( head(), val, key_comparator() );
642 /// Deletes the item from the list using \p pred predicate for searching
644 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
645 but \p pred is used for key comparing.
646 \p Less functor has the interface like \p std::less.
647 \p pred must imply the same element order as the comparator used for building the list.
649 template <typename Q, typename Less>
650 bool erase_with( Q const& val, Less pred )
652 return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
655 /// Deletes the item from the list
656 /** \anchor cds_intrusive_LazyList_hp_erase_func
657 The function searches an item with key equal to \p val in the list,
658 call \p func functor with item found, unlinks it from the list, and returns \p true.
659 The \p Func interface is
662 void operator()( value_type const& item );
665 The functor may be passed by reference using <tt>boost:ref</tt>
667 If the item with the key equal to \p val is not found the function return \p false.
669 template <typename Q, typename Func>
670 bool erase( const Q& val, Func func )
672 return erase_at( head(), val, key_comparator(), func );
675 /// Deletes the item from the list using \p pred predicate for searching
677 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
678 but \p pred is used for key comparing.
679 \p Less functor has the interface like \p std::less.
680 \p pred must imply the same element order as the comparator used for building the list.
682 template <typename Q, typename Less, typename Func>
683 bool erase_with( const Q& val, Less pred, Func func )
685 return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), func );
688 /// Extracts the item from the list with specified \p key
689 /** \anchor cds_intrusive_LazyList_hp_extract
690 The function searches an item with key equal to \p key,
691 unlinks it from the list, and returns it in \p dest parameter.
692 If the item with key equal to \p key is not found the function returns \p false.
694 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
696 The \ref disposer specified in \p Traits class template parameter is called automatically
697 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
698 will be destroyed or released.
699 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
703 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
707 ord_list::guarded_ptr gp;
708 theList.extract( gp, 5 );
712 // Destructor of gp releases internal HP guard
716 template <typename Q>
717 bool extract( guarded_ptr& dest, Q const& key )
719 return extract_at( head(), dest.guard(), key, key_comparator() );
722 /// Extracts the item from the list with comparing functor \p pred
724 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
725 but \p pred predicate is used for key comparing.
727 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
729 \p pred must imply the same element order as the comparator used for building the list.
731 template <typename Q, typename Less>
732 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
734 return extract_at( head(), dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
737 /// Finds the key \p val
738 /** \anchor cds_intrusive_LazyList_hp_find
739 The function searches the item with key equal to \p val and calls the functor \p f for item found.
740 The interface of \p Func functor is:
743 void operator()( value_type& item, Q& val );
746 where \p item is the item found, \p val is the <tt>find</tt> function argument.
748 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
750 The functor may change non-key fields of \p item.
751 While the functor \p f is calling the item \p item is locked.
753 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
754 may modify both arguments.
756 The function returns \p true if \p val is found, \p false otherwise.
758 template <typename Q, typename Func>
759 bool find( Q& val, Func f )
761 return find_at( head(), val, key_comparator(), f );
764 /// Finds the key \p val using \p pred predicate for searching
766 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
767 but \p pred is used for key comparing.
768 \p Less functor has the interface like \p std::less.
769 \p pred must imply the same element order as the comparator used for building the list.
771 template <typename Q, typename Less, typename Func>
772 bool find_with( Q& val, Less pred, Func f )
774 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
777 /// Finds the key \p val
778 /** \anchor cds_intrusive_LazyList_hp_find_const
779 The function searches the item with key equal to \p val and calls the functor \p f for item found.
780 The interface of \p Func functor is:
783 void operator()( value_type& item, Q const& val );
786 where \p item is the item found, \p val is the \p find function argument.
788 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
790 The functor may change non-key fields of \p item.
791 While the functor \p f is calling the item \p item is locked.
793 The function returns \p true if \p val is found, \p false otherwise.
795 template <typename Q, typename Func>
796 bool find( Q const& val, Func f )
798 return find_at( head(), val, key_comparator(), f );
801 /// Finds the key \p val using \p pred predicate for searching
803 The function is an analog of \ref cds_intrusive_LazyList_hp_find_const "find(Q const&, Func)"
804 but \p pred is used for key comparing.
805 \p Less functor has the interface like \p std::less.
806 \p pred must imply the same element order as the comparator used for building the list.
808 template <typename Q, typename Less, typename Func>
809 bool find_with( Q const& val, Less pred, Func f )
811 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
814 /// Finds the key \p val
815 /** \anchor cds_intrusive_LazyList_hp_find_val
816 The function searches the item with key equal to \p val
817 and returns \p true if it is found, and \p false otherwise
819 template <typename Q>
820 bool find( Q const & val )
822 return find_at( head(), val, key_comparator() );
825 /// Finds the key \p val using \p pred predicate for searching
827 The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
828 but \p pred is used for key comparing.
829 \p Less functor has the interface like \p std::less.
830 \p pred must imply the same element order as the comparator used for building the list.
832 template <typename Q, typename Less>
833 bool find_with( Q const& val, Less pred )
835 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
838 /// Finds the key \p val and return the item found
839 /** \anchor cds_intrusive_LazyList_hp_get
840 The function searches the item with key equal to \p val
841 and assigns the item found to guarded pointer \p ptr.
842 The function returns \p true if \p val is found, and \p false otherwise.
843 If \p val is not found the \p ptr parameter is not changed.
845 The \ref disposer specified in \p Traits class template parameter is called
846 by garbage collector \p GC automatically when returned \ref guarded_ptr object
847 will be destroyed or released.
848 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
852 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
856 ord_list::guarded_ptr gp;
857 if ( theList.get( gp, 5 )) {
861 // Destructor of guarded_ptr releases internal HP guard
865 Note the compare functor specified for class \p Traits template parameter
866 should accept a parameter of type \p Q that can be not the same as \p value_type.
868 template <typename Q>
869 bool get( guarded_ptr& ptr, Q const& val )
871 return get_at( head(), ptr.guard(), val, key_comparator() );
874 /// Finds the key \p val and return the item found
876 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
877 but \p pred is used for comparing the keys.
879 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
881 \p pred must imply the same element order as the comparator used for building the list.
883 template <typename Q, typename Less>
884 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
886 return get_at( head(), ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
891 The function unlink all items from the list.
895 typename gc::Guard guard;
898 h = head()->m_pNext.load(memory_model::memory_order_relaxed);
899 guard.assign( node_traits::to_value_ptr( h.ptr() ));
900 if ( head()->m_pNext.load(memory_model::memory_order_acquire) == h ) {
901 head()->m_Lock.lock();
904 unlink_node( head(), h.ptr(), head() );
907 head()->m_Lock.unlock();
909 retire_node( h.ptr() ) ; // free node
914 /// Checks if the list is empty
917 return head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail();
920 /// Returns list's item count
922 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
923 this function always returns 0.
925 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
926 is empty. To check list emptyness use \ref empty() method.
930 return m_ItemCounter.value();
935 // split-list support
936 bool insert_aux_node( node_type * pNode )
938 return insert_aux_node( head(), pNode );
941 // split-list support
942 bool insert_aux_node( node_type * pHead, node_type * pNode )
944 assert( pNode != nullptr );
946 // Hack: convert node_type to value_type.
947 // In principle, auxiliary node can be non-reducible to value_type
948 // We assume that comparator can correctly distinguish aux and regular node.
949 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
952 bool insert_at( node_type * pHead, value_type& val )
954 link_checker::is_empty( node_traits::to_node_ptr( val ) );
959 search( pHead, val, pos, key_comparator() );
961 auto_lock_position alp( pos );
962 if ( validate( pos.pPred, pos.pCur )) {
963 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
964 // failed: key already in list
968 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
977 template <typename Func>
978 bool insert_at( node_type * pHead, value_type& val, Func f )
980 link_checker::is_empty( node_traits::to_node_ptr( val ) );
985 search( pHead, val, pos, key_comparator() );
987 auto_lock_position alp( pos );
988 if ( validate( pos.pPred, pos.pCur )) {
989 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
990 // failed: key already in list
994 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
995 cds::unref(f)( val );
1004 template <typename Func>
1005 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
1011 search( pHead, val, pos, key_comparator() );
1013 auto_lock_position alp( pos );
1014 if ( validate( pos.pPred, pos.pCur )) {
1015 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1016 // key already in the list
1018 cds::unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1019 return std::make_pair( true, false );
1023 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1025 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1026 cds::unref(func)( true, val, val );
1028 return std::make_pair( true, true );
1035 bool unlink_at( node_type * pHead, value_type& val )
1041 search( pHead, val, pos, key_comparator() );
1045 auto_lock_position alp( pos );
1046 if ( validate( pos.pPred, pos.pCur ) ) {
1047 if ( pos.pCur != tail()
1048 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1049 && node_traits::to_value_ptr( pos.pCur ) == &val )
1052 unlink_node( pos.pPred, pos.pCur, pHead );
1061 if ( nResult > 0 ) {
1062 retire_node( pos.pCur );
1071 template <typename Q, typename Compare, typename Func>
1072 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1075 search( pHead, val, pos, cmp );
1079 auto_lock_position alp( pos );
1080 if ( validate( pos.pPred, pos.pCur )) {
1081 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1083 unlink_node( pos.pPred, pos.pCur, pHead );
1084 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
1094 if ( nResult > 0 ) {
1095 retire_node( pos.pCur );
1104 template <typename Q, typename Compare, typename Func>
1105 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1108 return erase_at( pHead, val, cmp, f, pos );
1111 template <typename Q, typename Compare>
1112 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1115 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1116 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1118 return erase_at( pHead, val, cmp, empty_erase_functor(), pos );
1122 template <typename Q, typename Compare>
1123 bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1127 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1128 erase_at( pHead, val, cmp, [](value_type const &){}, pos )
1130 erase_at( pHead, val, cmp, empty_erase_functor(), pos )
1134 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1140 template <typename Q, typename Compare, typename Func>
1141 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1145 search( pHead, val, pos, cmp );
1146 if ( pos.pCur != tail() ) {
1147 cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1148 if ( !pos.pCur->is_marked()
1149 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1151 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
1158 template <typename Q, typename Compare>
1159 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1163 search( pHead, val, pos, cmp );
1164 return pos.pCur != tail()
1165 && !pos.pCur->is_marked()
1166 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1169 template <typename Q, typename Compare>
1170 bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1174 search( pHead, val, pos, cmp );
1175 if ( pos.pCur != tail()
1176 && !pos.pCur->is_marked()
1177 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1179 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1189 template <typename Q, typename Compare>
1190 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1192 const node_type * pTail = tail();
1194 marked_node_ptr pCur( pHead );
1195 marked_node_ptr pPrev( pHead );
1199 while ( pCur.ptr() != pTail )
1201 if ( pCur.ptr() != pHead ) {
1202 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1206 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1210 pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1211 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1212 if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1216 assert( pCur.ptr() != nullptr );
1219 pos.pCur = pCur.ptr();
1220 pos.pPred = pPrev.ptr();
1223 static bool validate( node_type * pPred, node_type * pCur )
1225 return !pPred->is_marked()
1226 && !pCur->is_marked()
1227 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1232 }} // namespace cds::intrusive
1234 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_IMPL_H