3 #ifndef __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
4 #define __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
6 #include <mutex> // unique_lock
7 #include <cds/intrusive/details/lazy_list_base.h>
8 #include <cds/gc/guarded_ptr.h>
10 namespace cds { namespace intrusive {
12 /// Lazy ordered single-linked list
13 /** @ingroup cds_intrusive_list
14 \anchor cds_intrusive_LazyList_hp
16 Usually, ordered single-linked list is used as a building block for the hash table implementation.
17 The complexity of searching is <tt>O(N)</tt>.
20 - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
21 "A Lazy Concurrent List-Based Set Algorithm"
23 The lazy list is based on an optimistic locking scheme for inserts and removes,
24 eliminating the need to use the equivalent of an atomically markable
25 reference. It also has a novel wait-free membership \p find operation
26 that does not need to perform cleanup operations and is more efficient.
29 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see lazy_list::node).
30 - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
31 or it must have a member of type lazy_list::node (for lazy_list::member_hook).
32 - \p Traits - type traits. See lazy_list::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::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
92 - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
93 - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
95 Then, you should incorporate lazy_list::node into your struct \p T and provide
96 appropriate lazy_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits
97 a struct based on lazy_list::type_traits should be defined.
99 Example for gc::PTB and base hook:
101 // Include GC-related lazy list specialization
102 #include <cds/intrusive/lazy_list_dhp.h>
104 // Data stored in lazy list
105 struct my_data: public cds::intrusive::lazy_list::node< cds::gc::PTB >
114 // my_data comparing functor
116 int operator()( const my_data& d1, const my_data& d2 )
118 return d1.strKey.compare( d2.strKey );
121 int operator()( const my_data& d, const std::string& s )
123 return d.strKey.compare(s);
126 int operator()( const std::string& s, const my_data& d )
128 return s.compare( d.strKey );
133 // Declare type_traits
134 struct my_traits: public cds::intrusive::lazy_list::type_traits
136 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::PTB > > hook;
137 typedef my_data_cmp compare;
141 typedef cds::intrusive::LazyList< cds::gc::PTB, my_data, my_traits > traits_based_list;
144 Equivalent option-based code:
146 // GC-related specialization
147 #include <cds/intrusive/lazy_list_dhp.h>
156 // Declare option-based list
157 typedef cds::intrusive::LazyList< cds::gc::PTB
159 , typename cds::intrusive::lazy_list::make_traits<
160 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
161 ,cds::intrusive::opt::compare< my_data_cmp >
170 #ifdef CDS_DOXYGEN_INVOKED
171 ,class Traits = lazy_list::type_traits
179 typedef T value_type ; ///< type of value stored in the list
180 typedef Traits options ; ///< Traits template parameter
182 typedef typename options::hook hook ; ///< hook type
183 typedef typename hook::node_type node_type ; ///< node type
185 # ifdef CDS_DOXYGEN_INVOKED
186 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
188 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
191 typedef typename options::disposer disposer ; ///< disposer used
192 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
193 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
195 typedef GC gc ; ///< Garbage collector
196 typedef typename options::back_off back_off ; ///< back-off strategy
197 typedef typename options::item_counter item_counter ; ///< Item counting policy used
198 typedef typename options::memory_model memory_model; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
200 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
203 // Rebind options (split-list support)
204 template <typename... Options>
205 struct rebind_options {
209 , typename cds::opt::make_options< options, Options...>::type
215 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
216 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
223 item_counter m_ItemCounter ; ///< Item counter
226 struct clean_disposer {
227 void operator()( value_type * p )
229 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
234 /// Position pointer for item search
236 node_type * pPred ; ///< Previous node
237 node_type * pCur ; ///< Current node
239 typename gc::template GuardArray<2> guards ; ///< Guards array
246 /// Locks nodes \p pPred and \p pCur
249 pPred->m_Lock.lock();
253 /// Unlocks nodes \p pPred and \p pCur
256 pCur->m_Lock.unlock();
257 pPred->m_Lock.unlock();
261 class auto_lock_position {
264 auto_lock_position( position& pos )
269 ~auto_lock_position()
278 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
280 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
282 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
283 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
286 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
288 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
290 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
291 //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_release) ; // logically deleting
292 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // logical removal + back-link for search
293 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
294 //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ) ; // back-link for search
297 void retire_node( node_type * pNode )
299 assert( pNode != nullptr );
300 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
306 template <bool IsConst>
309 friend class LazyList;
312 value_type * m_pNode;
313 typename gc::Guard m_Guard;
317 assert( m_pNode != nullptr );
320 typename gc::Guard g;
321 node_type * pCur = node_traits::to_node_ptr( m_pNode );
322 if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) { // if pCur is not tail node
325 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
326 g.assign( node_traits::to_value_ptr( pNext ));
327 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr() );
329 m_pNode = m_Guard.assign( g.template get<value_type>() );
336 if ( m_pNode != nullptr ) {
337 typename gc::Guard g;
338 node_type * pNode = node_traits::to_node_ptr( m_pNode );
340 // Dummy tail node could not be marked
341 while ( pNode->is_marked() ) {
342 node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
343 g.assign( node_traits::to_value_ptr( p ));
344 if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr() )
347 if ( pNode != node_traits::to_node_ptr( m_pNode ) )
348 m_pNode = m_Guard.assign( g.template get<value_type>() );
352 iterator_type( node_type * pNode )
354 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
359 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
360 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
366 iterator_type( iterator_type const& src )
369 m_pNode = m_Guard.assign( src.m_pNode );
375 value_ptr operator ->() const
380 value_ref operator *() const
382 assert( m_pNode != nullptr );
387 iterator_type& operator ++()
394 iterator_type& operator = (iterator_type const& src)
396 m_pNode = src.m_pNode;
397 m_Guard.assign( m_pNode );
402 bool operator ==(iterator_type<C> const& i ) const
404 return m_pNode == i.m_pNode;
407 bool operator !=(iterator_type<C> const& i ) const
409 return m_pNode != i.m_pNode;
417 The forward iterator for lazy list has some features:
418 - it has no post-increment operator
419 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
420 For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
421 may be thrown if a limit of guard count per thread is exceeded.
422 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
423 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
424 deleting operations it is no guarantee that you iterate all item in the list.
426 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
427 for debug purpose only.
429 typedef iterator_type<false> iterator;
430 /// Const forward iterator
432 For iterator's features and requirements see \ref iterator
434 typedef iterator_type<true> const_iterator;
436 /// Returns a forward iterator addressing the first element in a list
438 For empty list \code begin() == end() \endcode
442 iterator it( &m_Head );
443 ++it ; // skip dummy head
447 /// Returns an iterator that addresses the location succeeding the last element in a list
449 Do not use the value returned by <tt>end</tt> function to access any item.
451 The returned value can be used only to control reaching the end of the list.
452 For empty list \code begin() == end() \endcode
456 return iterator( &m_Tail );
459 /// Returns a forward const iterator addressing the first element in a list
461 const_iterator begin() const
463 return get_const_begin();
465 const_iterator cbegin()
467 return get_const_begin();
471 /// Returns an const iterator that addresses the location succeeding the last element in a list
473 const_iterator end() const
475 return get_const_end();
477 const_iterator cend()
479 return get_const_end();
485 const_iterator get_const_begin() const
487 const_iterator it( const_cast<node_type *>( &m_Head ));
488 ++it ; // skip dummy head
491 const_iterator get_const_end() const
493 return const_iterator( const_cast<node_type *>(&m_Tail) );
498 /// Default constructor initializes empty list
501 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
502 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
505 /// Destroys the list object
509 assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
510 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
515 The function inserts \p val in the list if the list does not contain
516 an item with key equal to \p val.
518 Returns \p true if \p val is linked into the list, \p false otherwise.
520 bool insert( value_type& val )
522 return insert_at( &m_Head, val );
527 This function is intended for derived non-intrusive containers.
529 The function allows to split new item creating into two part:
530 - create item with key only
531 - insert new item into the list
532 - if inserting is success, calls \p f functor to initialize value-field of \p val.
534 The functor signature is:
536 void func( value_type& val );
538 where \p val is the item inserted.
539 While the functor \p f is working the item \p val is locked.
540 The user-defined functor is called only if the inserting is success.
542 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
544 template <typename Func>
545 bool insert( value_type& val, Func f )
547 return insert_at( &m_Head, val, f );
550 /// Ensures that the \p item exists in the list
552 The operation performs inserting or changing data with lock-free manner.
554 If the item \p val not found in the list, then \p val is inserted into the list.
555 Otherwise, the functor \p func is called with item found.
556 The functor signature is:
558 void func( bool bNew, value_type& item, value_type& val );
561 - \p bNew - \p true if the item has been inserted, \p false otherwise
562 - \p item - item of the list
563 - \p val - argument \p val passed into the \p ensure function
564 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
565 refer to the same thing.
567 The functor may change non-key fields of the \p item.
568 While the functor \p f is working the item \p item is locked.
570 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
571 \p second is \p true if new item has been added or \p false if the item with \p key
572 already is in the list.
574 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
576 template <typename Func>
577 std::pair<bool, bool> ensure( value_type& val, Func func )
579 return ensure_at( &m_Head, val, func );
582 /// Unlinks the item \p val from the list
584 The function searches the item \p val in the list and unlink it from the list
585 if it is found and it is equal to \p val.
587 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
588 and deletes the item found. \p unlink finds an item by key and deletes it
589 only if \p val is an item of that list, i.e. the pointer to item found
590 is equal to <tt> &val </tt>.
592 The function returns \p true if success and \p false otherwise.
594 bool unlink( value_type& val )
596 return unlink_at( &m_Head, val );
599 /// Deletes the item from the list
600 /** \anchor cds_intrusive_LazyList_hp_erase_val
601 The function searches an item with key equal to \p val in the list,
602 unlinks it from the list, and returns \p true.
603 If the item with the key equal to \p val is not found the function return \p false.
605 template <typename Q>
606 bool erase( Q const& val )
608 return erase_at( &m_Head, val, key_comparator() );
611 /// Deletes the item from the list using \p pred predicate for searching
613 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
614 but \p pred is used for key comparing.
615 \p Less functor has the interface like \p std::less.
616 \p pred must imply the same element order as the comparator used for building the list.
618 template <typename Q, typename Less>
619 bool erase_with( Q const& val, Less pred )
621 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
624 /// Deletes the item from the list
625 /** \anchor cds_intrusive_LazyList_hp_erase_func
626 The function searches an item with key equal to \p val in the list,
627 call \p func functor with item found, unlinks it from the list, and returns \p true.
628 The \p Func interface is
631 void operator()( value_type const& item );
634 The functor may be passed by reference using <tt>boost:ref</tt>
636 If the item with the key equal to \p val is not found the function return \p false.
638 template <typename Q, typename Func>
639 bool erase( const Q& val, Func func )
641 return erase_at( &m_Head, val, key_comparator(), func );
644 /// Deletes the item from the list using \p pred predicate for searching
646 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
647 but \p pred is used for key comparing.
648 \p Less functor has the interface like \p std::less.
649 \p pred must imply the same element order as the comparator used for building the list.
651 template <typename Q, typename Less, typename Func>
652 bool erase_with( const Q& val, Less pred, Func func )
654 return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), func );
657 /// Extracts the item from the list with specified \p key
658 /** \anchor cds_intrusive_LazyList_hp_extract
659 The function searches an item with key equal to \p key,
660 unlinks it from the list, and returns it in \p dest parameter.
661 If the item with key equal to \p key is not found the function returns \p false.
663 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
665 The \ref disposer specified in \p Traits class template parameter is called automatically
666 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
667 will be destroyed or released.
668 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
672 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
676 ord_list::guarded_ptr gp;
677 theList.extract( gp, 5 );
681 // Destructor of gp releases internal HP guard
685 template <typename Q>
686 bool extract( guarded_ptr& dest, Q const& key )
688 return extract_at( &m_Head, dest.guard(), key, key_comparator() );
691 /// Extracts the item from the list with comparing functor \p pred
693 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
694 but \p pred predicate is used for key comparing.
696 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
698 \p pred must imply the same element order as the comparator used for building the list.
700 template <typename Q, typename Less>
701 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
703 return extract_at( &m_Head, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
706 /// Finds the key \p val
707 /** \anchor cds_intrusive_LazyList_hp_find
708 The function searches the item with key equal to \p val and calls the functor \p f for item found.
709 The interface of \p Func functor is:
712 void operator()( value_type& item, Q& val );
715 where \p item is the item found, \p val is the <tt>find</tt> function argument.
717 You may pass \p f argument by reference using \p std::ref.
719 The functor may change non-key fields of \p item.
720 While the functor \p f is calling the item \p item is locked.
722 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
723 may modify both arguments.
725 The function returns \p true if \p val is found, \p false otherwise.
727 template <typename Q, typename Func>
728 bool find( Q& val, Func f )
730 return find_at( &m_Head, val, key_comparator(), f );
733 /// Finds the key \p val using \p pred predicate for searching
735 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
736 but \p pred is used for key comparing.
737 \p Less functor has the interface like \p std::less.
738 \p pred must imply the same element order as the comparator used for building the list.
740 template <typename Q, typename Less, typename Func>
741 bool find_with( Q& val, Less pred, Func f )
743 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
746 /// Finds the key \p val
747 /** \anchor cds_intrusive_LazyList_hp_find_const
748 The function searches the item with key equal to \p val and calls the functor \p f for item found.
749 The interface of \p Func functor is:
752 void operator()( value_type& item, Q const& val );
755 where \p item is the item found, \p val is the \p find function argument.
757 You may pass \p f argument by reference using \p std::ref.
759 The functor may change non-key fields of \p item.
760 While the functor \p f is calling the item \p item is locked.
762 The function returns \p true if \p val is found, \p false otherwise.
764 template <typename Q, typename Func>
765 bool find( Q const& val, Func f )
767 return find_at( &m_Head, val, key_comparator(), f );
770 /// Finds the key \p val using \p pred predicate for searching
772 The function is an analog of \ref cds_intrusive_LazyList_hp_find_const "find(Q const&, Func)"
773 but \p pred is used for key comparing.
774 \p Less functor has the interface like \p std::less.
775 \p pred must imply the same element order as the comparator used for building the list.
777 template <typename Q, typename Less, typename Func>
778 bool find_with( Q const& val, Less pred, Func f )
780 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
783 /// Finds the key \p val
784 /** \anchor cds_intrusive_LazyList_hp_find_val
785 The function searches the item with key equal to \p val
786 and returns \p true if it is found, and \p false otherwise
788 template <typename Q>
789 bool find( Q const & val )
791 return find_at( &m_Head, val, key_comparator() );
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_val "find(Q const&)"
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>
802 bool find_with( Q const& val, Less pred )
804 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
807 /// Finds the key \p val and return the item found
808 /** \anchor cds_intrusive_LazyList_hp_get
809 The function searches the item with key equal to \p val
810 and assigns the item found to guarded pointer \p ptr.
811 The function returns \p true if \p val is found, and \p false otherwise.
812 If \p val is not found the \p ptr parameter is not changed.
814 The \ref disposer specified in \p Traits class template parameter is called
815 by garbage collector \p GC automatically when returned \ref guarded_ptr object
816 will be destroyed or released.
817 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
821 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
825 ord_list::guarded_ptr gp;
826 if ( theList.get( gp, 5 )) {
830 // Destructor of guarded_ptr releases internal HP guard
834 Note the compare functor specified for class \p Traits template parameter
835 should accept a parameter of type \p Q that can be not the same as \p value_type.
837 template <typename Q>
838 bool get( guarded_ptr& ptr, Q const& val )
840 return get_at( &m_Head, ptr.guard(), val, key_comparator() );
843 /// Finds the key \p val and return the item found
845 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
846 but \p pred is used for comparing the keys.
848 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
850 \p pred must imply the same element order as the comparator used for building the list.
852 template <typename Q, typename Less>
853 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
855 return get_at( &m_Head, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
860 The function unlink all items from the list.
864 typename gc::Guard guard;
867 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
868 guard.assign( node_traits::to_value_ptr( h.ptr() ));
869 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
870 m_Head.m_Lock.lock();
873 unlink_node( &m_Head, h.ptr(), &m_Head );
876 m_Head.m_Lock.unlock();
878 retire_node( h.ptr() ) ; // free node
883 /// Checks if the list is empty
886 return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
889 /// Returns list's item count
891 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
892 this function always returns 0.
894 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
895 is empty. To check list emptyness use \ref empty() method.
899 return m_ItemCounter.value();
904 // split-list support
905 bool insert_aux_node( node_type * pNode )
907 return insert_aux_node( &m_Head, pNode );
910 // split-list support
911 bool insert_aux_node( node_type * pHead, node_type * pNode )
913 assert( pNode != nullptr );
915 // Hack: convert node_type to value_type.
916 // In principle, auxiliary node can be non-reducible to value_type
917 // We assume that comparator can correctly distinguish aux and regular node.
918 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
921 bool insert_at( node_type * pHead, value_type& val )
923 link_checker::is_empty( node_traits::to_node_ptr( val ) );
928 search( pHead, val, pos, key_comparator() );
930 auto_lock_position alp( pos );
931 if ( validate( pos.pPred, pos.pCur )) {
932 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
933 // failed: key already in list
937 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
946 template <typename Func>
947 bool insert_at( node_type * pHead, value_type& val, Func f )
949 link_checker::is_empty( node_traits::to_node_ptr( val ) );
954 search( pHead, val, pos, key_comparator() );
956 auto_lock_position alp( pos );
957 if ( validate( pos.pPred, pos.pCur )) {
958 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
959 // failed: key already in list
963 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
973 template <typename Func>
974 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
980 search( pHead, val, pos, key_comparator() );
982 auto_lock_position alp( pos );
983 if ( validate( pos.pPred, pos.pCur )) {
984 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
985 // key already in the list
987 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
988 return std::make_pair( true, false );
992 link_checker::is_empty( node_traits::to_node_ptr( val ) );
994 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
995 func( true, val, val );
997 return std::make_pair( true, true );
1004 bool unlink_at( node_type * pHead, value_type& val )
1010 search( pHead, val, pos, key_comparator() );
1014 auto_lock_position alp( pos );
1015 if ( validate( pos.pPred, pos.pCur ) ) {
1016 if ( pos.pCur != &m_Tail
1017 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1018 && node_traits::to_value_ptr( pos.pCur ) == &val )
1021 unlink_node( pos.pPred, pos.pCur, pHead );
1030 if ( nResult > 0 ) {
1031 retire_node( pos.pCur );
1040 template <typename Q, typename Compare, typename Func>
1041 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1044 search( pHead, val, pos, cmp );
1048 auto_lock_position alp( pos );
1049 if ( validate( pos.pPred, pos.pCur )) {
1050 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1052 unlink_node( pos.pPred, pos.pCur, pHead );
1053 f( *node_traits::to_value_ptr( *pos.pCur ) );
1063 if ( nResult > 0 ) {
1064 retire_node( pos.pCur );
1073 template <typename Q, typename Compare, typename Func>
1074 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1077 return erase_at( pHead, val, cmp, f, pos );
1080 template <typename Q, typename Compare>
1081 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1084 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1087 template <typename Q, typename Compare>
1088 bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1091 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1092 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1098 template <typename Q, typename Compare, typename Func>
1099 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1103 search( pHead, val, pos, cmp );
1104 if ( pos.pCur != &m_Tail ) {
1105 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1106 if ( !pos.pCur->is_marked()
1107 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1109 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1116 template <typename Q, typename Compare>
1117 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1121 search( pHead, val, pos, cmp );
1122 return pos.pCur != &m_Tail
1123 && !pos.pCur->is_marked()
1124 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1127 template <typename Q, typename Compare>
1128 bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1132 search( pHead, val, pos, cmp );
1133 if ( pos.pCur != &m_Tail
1134 && !pos.pCur->is_marked()
1135 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1137 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1147 template <typename Q, typename Compare>
1148 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1150 const node_type * pTail = &m_Tail;
1152 marked_node_ptr pCur( pHead );
1153 marked_node_ptr pPrev( pHead );
1157 while ( pCur.ptr() != pTail )
1159 if ( pCur.ptr() != pHead ) {
1160 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1164 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1168 pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1169 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1170 if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1174 assert( pCur.ptr() != nullptr );
1177 pos.pCur = pCur.ptr();
1178 pos.pPred = pPrev.ptr();
1181 static bool validate( node_type * pPred, node_type * pCur )
1183 return !pPred->is_marked()
1184 && !pCur->is_marked()
1185 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1190 }} // namespace cds::intrusive
1192 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H