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::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 <typename... Options>
206 struct rebind_options {
210 , typename cds::opt::make_options< options, Options...>::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()
301 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
303 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
305 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
306 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
309 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
311 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
313 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
314 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_release) ; // logically deleting
315 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // logical removal + back-link for search
316 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
317 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // back-link for search
320 void retire_node( node_type * pNode )
322 assert( pNode != nullptr );
323 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
329 template <bool IsConst>
332 friend class LazyList;
335 value_type * m_pNode;
336 typename gc::Guard m_Guard;
340 assert( m_pNode != nullptr );
343 typename gc::Guard g;
344 node_type * pCur = node_traits::to_node_ptr( m_pNode );
345 if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) { // if pCur is not tail node
348 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
349 g.assign( node_traits::to_value_ptr( pNext ));
350 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr() );
352 m_pNode = m_Guard.assign( g.template get<value_type>() );
359 if ( m_pNode != nullptr ) {
360 typename gc::Guard g;
361 node_type * pNode = node_traits::to_node_ptr( m_pNode );
363 // Dummy tail node could not be marked
364 while ( pNode->is_marked() ) {
365 node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
366 g.assign( node_traits::to_value_ptr( p ));
367 if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr() )
370 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
371 m_pNode = m_Guard.assign( g.template get<value_type>() );
375 iterator_type( node_type * pNode )
377 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
382 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
383 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
389 iterator_type( iterator_type const& src )
392 m_pNode = m_Guard.assign( src.m_pNode );
398 value_ptr operator ->() const
403 value_ref operator *() const
405 assert( m_pNode != nullptr );
410 iterator_type& operator ++()
417 iterator_type& operator = (iterator_type const& src)
419 m_pNode = src.m_pNode;
420 m_Guard.assign( m_pNode );
425 bool operator ==(iterator_type<C> const& i ) const
427 return m_pNode == i.m_pNode;
430 bool operator !=(iterator_type<C> const& i ) const
432 return m_pNode != i.m_pNode;
440 The forward iterator for lazy list has some features:
441 - it has no post-increment operator
442 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
443 For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
444 may be thrown if a limit of guard count per thread is exceeded.
445 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
446 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
447 deleting operations it is no guarantee that you iterate all item in the list.
449 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
450 for debug purpose only.
452 typedef iterator_type<false> iterator;
453 /// Const forward iterator
455 For iterator's features and requirements see \ref iterator
457 typedef iterator_type<true> const_iterator;
459 /// Returns a forward iterator addressing the first element in a list
461 For empty list \code begin() == end() \endcode
465 iterator it( head() );
466 ++it ; // skip dummy head
470 /// Returns an iterator that addresses the location succeeding the last element in a list
472 Do not use the value returned by <tt>end</tt> function to access any item.
474 The returned value can be used only to control reaching the end of the list.
475 For empty list \code begin() == end() \endcode
479 return iterator( tail() );
482 /// Returns a forward const iterator addressing the first element in a list
484 const_iterator begin() const
486 return get_const_begin();
488 const_iterator cbegin()
490 return get_const_begin();
494 /// Returns an const iterator that addresses the location succeeding the last element in a list
496 const_iterator end() const
498 return get_const_end();
500 const_iterator cend()
502 return get_const_end();
508 const_iterator get_const_begin() const
510 const_iterator it( const_cast<node_type *>( head() ));
511 ++it ; // skip dummy head
514 const_iterator get_const_end() const
516 return const_iterator( const_cast<node_type *>( tail() ));
521 /// Default constructor initializes empty list
524 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
526 //m_pTail = cxx_allocator().New();
527 head()->m_pNext.store( marked_node_ptr( tail() ), memory_model::memory_order_relaxed );
530 /// Destroys the list object
534 assert( head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail() );
535 head()->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
540 The function inserts \p val in the list if the list does not contain
541 an item with key equal to \p val.
543 Returns \p true if \p val is linked into the list, \p false otherwise.
545 bool insert( value_type& val )
547 return insert_at( head(), val );
552 This function is intended for derived non-intrusive containers.
554 The function allows to split new item creating into two part:
555 - create item with key only
556 - insert new item into the list
557 - if inserting is success, calls \p f functor to initialize value-field of \p val.
559 The functor signature is:
561 void func( value_type& val );
563 where \p val is the item inserted.
564 While the functor \p f is working the item \p val is locked.
565 The user-defined functor is called only if the inserting is success and may be passed by reference
568 template <typename Func>
569 bool insert( value_type& val, Func f )
571 return insert_at( head(), val, f );
574 /// Ensures that the \p item exists in the list
576 The operation performs inserting or changing data with lock-free manner.
578 If the item \p val not found in the list, then \p val is inserted into the list.
579 Otherwise, the functor \p func is called with item found.
580 The functor signature is:
582 void func( bool bNew, value_type& item, value_type& val );
585 - \p bNew - \p true if the item has been inserted, \p false otherwise
586 - \p item - item of the list
587 - \p val - argument \p val passed into the \p ensure function
588 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
589 refer to the same thing.
591 The functor may change non-key fields of the \p item.
592 While the functor \p f is working the item \p item is locked.
594 You may pass \p func argument by reference using \p std::ref.
596 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
597 \p second is \p true if new item has been added or \p false if the item with \p key
598 already is in the list.
600 template <typename Func>
601 std::pair<bool, bool> ensure( value_type& val, Func func )
603 return ensure_at( head(), val, func );
606 /// Unlinks the item \p val from the list
608 The function searches the item \p val in the list and unlink it from the list
609 if it is found and it is equal to \p val.
611 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
612 and deletes the item found. \p unlink finds an item by key and deletes it
613 only if \p val is an item of that list, i.e. the pointer to item found
614 is equal to <tt> &val </tt>.
616 The function returns \p true if success and \p false otherwise.
618 bool unlink( value_type& val )
620 return unlink_at( head(), val );
623 /// Deletes the item from the list
624 /** \anchor cds_intrusive_LazyList_hp_erase_val
625 The function searches an item with key equal to \p val in the list,
626 unlinks it from the list, and returns \p true.
627 If the item with the key equal to \p val is not found the function return \p false.
629 template <typename Q>
630 bool erase( Q const& val )
632 return erase_at( head(), val, key_comparator() );
635 /// Deletes the item from the list using \p pred predicate for searching
637 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
638 but \p pred is used for key comparing.
639 \p Less functor has the interface like \p std::less.
640 \p pred must imply the same element order as the comparator used for building the list.
642 template <typename Q, typename Less>
643 bool erase_with( Q const& val, Less pred )
645 return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
648 /// Deletes the item from the list
649 /** \anchor cds_intrusive_LazyList_hp_erase_func
650 The function searches an item with key equal to \p val in the list,
651 call \p func functor with item found, unlinks it from the list, and returns \p true.
652 The \p Func interface is
655 void operator()( value_type const& item );
658 The functor may be passed by reference using <tt>boost:ref</tt>
660 If the item with the key equal to \p val is not found the function return \p false.
662 template <typename Q, typename Func>
663 bool erase( const Q& val, Func func )
665 return erase_at( head(), val, key_comparator(), func );
668 /// Deletes the item from the list using \p pred predicate for searching
670 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
671 but \p pred is used for key comparing.
672 \p Less functor has the interface like \p std::less.
673 \p pred must imply the same element order as the comparator used for building the list.
675 template <typename Q, typename Less, typename Func>
676 bool erase_with( const Q& val, Less pred, Func func )
678 return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), func );
681 /// Extracts the item from the list with specified \p key
682 /** \anchor cds_intrusive_LazyList_hp_extract
683 The function searches an item with key equal to \p key,
684 unlinks it from the list, and returns it in \p dest parameter.
685 If the item with key equal to \p key is not found the function returns \p false.
687 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
689 The \ref disposer specified in \p Traits class template parameter is called automatically
690 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
691 will be destroyed or released.
692 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
696 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
700 ord_list::guarded_ptr gp;
701 theList.extract( gp, 5 );
705 // Destructor of gp releases internal HP guard
709 template <typename Q>
710 bool extract( guarded_ptr& dest, Q const& key )
712 return extract_at( head(), dest.guard(), key, key_comparator() );
715 /// Extracts the item from the list with comparing functor \p pred
717 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
718 but \p pred predicate is used for key comparing.
720 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
722 \p pred must imply the same element order as the comparator used for building the list.
724 template <typename Q, typename Less>
725 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
727 return extract_at( head(), dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
730 /// Finds the key \p val
731 /** \anchor cds_intrusive_LazyList_hp_find
732 The function searches the item with key equal to \p val and calls the functor \p f for item found.
733 The interface of \p Func functor is:
736 void operator()( value_type& item, Q& val );
739 where \p item is the item found, \p val is the <tt>find</tt> function argument.
741 You may pass \p f argument by reference using \p std::ref.
743 The functor may change non-key fields of \p item.
744 While the functor \p f is calling the item \p item is locked.
746 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
747 may modify both arguments.
749 The function returns \p true if \p val is found, \p false otherwise.
751 template <typename Q, typename Func>
752 bool find( Q& val, Func f )
754 return find_at( head(), val, key_comparator(), f );
757 /// Finds the key \p val using \p pred predicate for searching
759 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
760 but \p pred is used for key comparing.
761 \p Less functor has the interface like \p std::less.
762 \p pred must imply the same element order as the comparator used for building the list.
764 template <typename Q, typename Less, typename Func>
765 bool find_with( Q& val, Less pred, Func f )
767 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
770 /// Finds the key \p val
771 /** \anchor cds_intrusive_LazyList_hp_find_const
772 The function searches the item with key equal to \p val and calls the functor \p f for item found.
773 The interface of \p Func functor is:
776 void operator()( value_type& item, Q const& val );
779 where \p item is the item found, \p val is the \p find function argument.
781 You may pass \p f argument by reference using \p std::ref.
783 The functor may change non-key fields of \p item.
784 While the functor \p f is calling the item \p item is locked.
786 The function returns \p true if \p val is found, \p false otherwise.
788 template <typename Q, typename Func>
789 bool find( Q const& val, Func f )
791 return find_at( head(), val, key_comparator(), f );
794 /// Finds the key \p val using \p pred predicate for searching
796 The function is an analog of \ref cds_intrusive_LazyList_hp_find_const "find(Q const&, Func)"
797 but \p pred is used for key comparing.
798 \p Less functor has the interface like \p std::less.
799 \p pred must imply the same element order as the comparator used for building the list.
801 template <typename Q, typename Less, typename Func>
802 bool find_with( Q const& val, Less pred, Func f )
804 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
807 /// Finds the key \p val
808 /** \anchor cds_intrusive_LazyList_hp_find_val
809 The function searches the item with key equal to \p val
810 and returns \p true if it is found, and \p false otherwise
812 template <typename Q>
813 bool find( Q const & val )
815 return find_at( head(), val, key_comparator() );
818 /// Finds the key \p val using \p pred predicate for searching
820 The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
821 but \p pred is used for key comparing.
822 \p Less functor has the interface like \p std::less.
823 \p pred must imply the same element order as the comparator used for building the list.
825 template <typename Q, typename Less>
826 bool find_with( Q const& val, Less pred )
828 return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
831 /// Finds the key \p val and return the item found
832 /** \anchor cds_intrusive_LazyList_hp_get
833 The function searches the item with key equal to \p val
834 and assigns the item found to guarded pointer \p ptr.
835 The function returns \p true if \p val is found, and \p false otherwise.
836 If \p val is not found the \p ptr parameter is not changed.
838 The \ref disposer specified in \p Traits class template parameter is called
839 by garbage collector \p GC automatically when returned \ref guarded_ptr object
840 will be destroyed or released.
841 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
845 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
849 ord_list::guarded_ptr gp;
850 if ( theList.get( gp, 5 )) {
854 // Destructor of guarded_ptr releases internal HP guard
858 Note the compare functor specified for class \p Traits template parameter
859 should accept a parameter of type \p Q that can be not the same as \p value_type.
861 template <typename Q>
862 bool get( guarded_ptr& ptr, Q const& val )
864 return get_at( head(), ptr.guard(), val, key_comparator() );
867 /// Finds the key \p val and return the item found
869 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
870 but \p pred is used for comparing the keys.
872 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
874 \p pred must imply the same element order as the comparator used for building the list.
876 template <typename Q, typename Less>
877 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
879 return get_at( head(), ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
884 The function unlink all items from the list.
888 typename gc::Guard guard;
891 h = head()->m_pNext.load(memory_model::memory_order_relaxed);
892 guard.assign( node_traits::to_value_ptr( h.ptr() ));
893 if ( head()->m_pNext.load(memory_model::memory_order_acquire) == h ) {
894 head()->m_Lock.lock();
897 unlink_node( head(), h.ptr(), head() );
900 head()->m_Lock.unlock();
902 retire_node( h.ptr() ) ; // free node
907 /// Checks if the list is empty
910 return head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail();
913 /// Returns list's item count
915 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
916 this function always returns 0.
918 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
919 is empty. To check list emptyness use \ref empty() method.
923 return m_ItemCounter.value();
928 // split-list support
929 bool insert_aux_node( node_type * pNode )
931 return insert_aux_node( head(), pNode );
934 // split-list support
935 bool insert_aux_node( node_type * pHead, node_type * pNode )
937 assert( pNode != nullptr );
939 // Hack: convert node_type to value_type.
940 // In principle, auxiliary node can be non-reducible to value_type
941 // We assume that comparator can correctly distinguish aux and regular node.
942 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
945 bool insert_at( node_type * pHead, value_type& val )
947 link_checker::is_empty( node_traits::to_node_ptr( val ) );
952 search( pHead, val, pos, key_comparator() );
954 auto_lock_position alp( pos );
955 if ( validate( pos.pPred, pos.pCur )) {
956 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
957 // failed: key already in list
961 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
970 template <typename Func>
971 bool insert_at( node_type * pHead, value_type& val, Func f )
973 link_checker::is_empty( node_traits::to_node_ptr( val ) );
978 search( pHead, val, pos, key_comparator() );
980 auto_lock_position alp( pos );
981 if ( validate( pos.pPred, pos.pCur )) {
982 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
983 // failed: key already in list
987 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
997 template <typename Func>
998 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
1004 search( pHead, val, pos, key_comparator() );
1006 auto_lock_position alp( pos );
1007 if ( validate( pos.pPred, pos.pCur )) {
1008 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1009 // key already in the list
1011 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1012 return std::make_pair( true, false );
1016 link_checker::is_empty( node_traits::to_node_ptr( val ) );
1018 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1019 func( true, val, val );
1021 return std::make_pair( true, true );
1028 bool unlink_at( node_type * pHead, value_type& val )
1034 search( pHead, val, pos, key_comparator() );
1038 auto_lock_position alp( pos );
1039 if ( validate( pos.pPred, pos.pCur ) ) {
1040 if ( pos.pCur != tail()
1041 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1042 && node_traits::to_value_ptr( pos.pCur ) == &val )
1045 unlink_node( pos.pPred, pos.pCur, pHead );
1054 if ( nResult > 0 ) {
1055 retire_node( pos.pCur );
1064 template <typename Q, typename Compare, typename Func>
1065 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1068 search( pHead, val, pos, cmp );
1072 auto_lock_position alp( pos );
1073 if ( validate( pos.pPred, pos.pCur )) {
1074 if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1076 unlink_node( pos.pPred, pos.pCur, pHead );
1077 f( *node_traits::to_value_ptr( *pos.pCur ) );
1087 if ( nResult > 0 ) {
1088 retire_node( pos.pCur );
1097 template <typename Q, typename Compare, typename Func>
1098 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1101 return erase_at( pHead, val, cmp, f, pos );
1104 template <typename Q, typename Compare>
1105 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1108 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1111 template <typename Q, typename Compare>
1112 bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1115 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1116 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1122 template <typename Q, typename Compare, typename Func>
1123 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1127 search( pHead, val, pos, cmp );
1128 if ( pos.pCur != tail() ) {
1129 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1130 if ( !pos.pCur->is_marked()
1131 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1133 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1140 template <typename Q, typename Compare>
1141 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1145 search( pHead, val, pos, cmp );
1146 return pos.pCur != tail()
1147 && !pos.pCur->is_marked()
1148 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1151 template <typename Q, typename Compare>
1152 bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1156 search( pHead, val, pos, cmp );
1157 if ( pos.pCur != tail()
1158 && !pos.pCur->is_marked()
1159 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1161 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1171 template <typename Q, typename Compare>
1172 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1174 const node_type * pTail = tail();
1176 marked_node_ptr pCur( pHead );
1177 marked_node_ptr pPrev( pHead );
1181 while ( pCur.ptr() != pTail )
1183 if ( pCur.ptr() != pHead ) {
1184 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1188 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1192 pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1193 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1194 if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1198 assert( pCur.ptr() != nullptr );
1201 pos.pCur = pCur.ptr();
1202 pos.pPred = pPrev.ptr();
1205 static bool validate( node_type * pPred, node_type * pCur )
1207 return !pPred->is_marked()
1208 && !pCur->is_marked()
1209 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1214 }} // namespace cds::intrusive
1216 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H