2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
34 #include <mutex> // unique_lock
35 #include <cds/intrusive/details/lazy_list_base.h>
37 namespace cds { namespace intrusive {
39 /// Lazy ordered single-linked list
40 /** @ingroup cds_intrusive_list
41 \anchor cds_intrusive_LazyList_hp
43 Usually, ordered single-linked list is used as a building block for the hash table implementation.
44 The complexity of searching is <tt>O(N)</tt>.
47 - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
48 "A Lazy Concurrent List-Based Set Algorithm"
50 The lazy list is based on an optimistic locking scheme for inserts and removes,
51 eliminating the need to use the equivalent of an atomically markable
52 reference. It also has a novel wait-free membership \p find operation
53 that does not need to perform cleanup operations and is more efficient.
56 - \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).
57 - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
58 or it must have a member of type lazy_list::node (for lazy_list::member_hook).
59 - \p Traits - type traits. See lazy_list::traits for explanation.
60 It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
61 argument. For example, the following traits-based declaration of \p gc::HP lazy list
63 #include <cds/intrusive/lazy_list_hp.h>
64 // Declare item stored in your list
65 struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
68 // Declare comparator for the item
69 struct my_compare { ... }
72 struct my_traits: public cds::intrusive::lazy_list::traits
74 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
75 typedef my_compare compare;
78 // Declare traits-based list
79 typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits > traits_based_list;
81 is equivalent for the following option-based list
83 #include <cds/intrusive/lazy_list_hp.h>
85 // item struct and my_compare are the same
87 // Declare option-based list
88 typedef cds::intrusive::LazyList< cds::gc::HP, item,
89 typename cds::intrusive::lazy_list::make_traits<
90 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
91 ,cds::intrusive::opt::compare< my_compare > // item comparator option
97 There are different specializations of this template for each garbage collecting schema used.
98 You should select GC needed and include appropriate .h-file:
99 - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
100 - for gc::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
101 - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
102 - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
104 Then, you should incorporate lazy_list::node into your struct \p T and provide
105 appropriate \p lazy_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits
106 a struct based on \p lazy_list::traits should be defined.
108 Example for gc::DHP and base hook:
110 // Include GC-related lazy list specialization
111 #include <cds/intrusive/lazy_list_dhp.h>
113 // Data stored in lazy list
114 struct my_data: public cds::intrusive::lazy_list::node< cds::gc::DHP >
123 // my_data comparing functor
125 int operator()( const my_data& d1, const my_data& d2 )
127 return d1.strKey.compare( d2.strKey );
130 int operator()( const my_data& d, const std::string& s )
132 return d.strKey.compare(s);
135 int operator()( const std::string& s, const my_data& d )
137 return s.compare( d.strKey );
142 struct my_traits: public cds::intrusive::lazy_list::traits
144 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
145 typedef my_data_cmp compare;
149 typedef cds::intrusive::LazyList< cds::gc::DHP, my_data, my_traits > traits_based_list;
152 Equivalent option-based code:
154 // GC-related specialization
155 #include <cds/intrusive/lazy_list_dhp.h>
164 // Declare option-based list
165 typedef cds::intrusive::LazyList< cds::gc::DHP
167 , typename cds::intrusive::lazy_list::make_traits<
168 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
169 ,cds::intrusive::opt::compare< my_data_cmp >
178 #ifdef CDS_DOXYGEN_INVOKED
179 ,class Traits = lazy_list::traits
187 typedef GC gc; ///< Garbage collector
188 typedef T value_type; ///< type of value stored in the list
189 typedef Traits traits; ///< Traits template parameter
191 typedef typename traits::hook hook; ///< hook type
192 typedef typename hook::node_type node_type; ///< node type
194 # ifdef CDS_DOXYGEN_INVOKED
195 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
197 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
200 typedef typename traits::disposer disposer; ///< disposer
201 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
202 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
204 typedef typename traits::back_off back_off ; ///< back-off strategy
205 typedef typename traits::item_counter item_counter ; ///< Item counting policy used
206 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
208 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
211 // Rebind traits (split-list support)
212 template <typename... Options>
213 struct rebind_traits {
217 , typename cds::opt::make_options< traits, Options...>::type
223 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
224 typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
231 item_counter m_ItemCounter ; ///< Item counter
234 struct clean_disposer {
235 void operator()( value_type * p )
237 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
242 /// Position pointer for item search
244 node_type * pPred ; ///< Previous node
245 node_type * pCur ; ///< Current node
247 typename gc::template GuardArray<2> guards ; ///< Guards array
254 /// Locks nodes \p pPred and \p pCur
257 pPred->m_Lock.lock();
261 /// Unlocks nodes \p pPred and \p pCur
264 pCur->m_Lock.unlock();
265 pPred->m_Lock.unlock();
269 typedef std::unique_lock< position > scoped_position_lock;
274 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
276 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
278 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
279 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
282 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
284 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
286 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
287 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ); // logical removal + back-link for search
288 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
291 void retire_node( node_type * pNode )
293 assert( pNode != nullptr );
294 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
300 template <bool IsConst>
303 friend class LazyList;
306 value_type * m_pNode;
307 typename gc::Guard m_Guard;
311 assert( m_pNode != nullptr );
314 typename gc::Guard g;
315 node_type * pCur = node_traits::to_node_ptr( m_pNode );
316 if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) { // if pCur is not tail node
319 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
320 g.assign( node_traits::to_value_ptr( pNext ));
321 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr());
323 m_pNode = m_Guard.assign( g.template get<value_type>());
330 if ( m_pNode != nullptr ) {
331 typename gc::Guard g;
332 node_type * pNode = node_traits::to_node_ptr( m_pNode );
334 // Dummy tail node could not be marked
335 while ( pNode->is_marked()) {
336 node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
337 g.assign( node_traits::to_value_ptr( p ));
338 if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr())
341 if ( pNode != node_traits::to_node_ptr( m_pNode ))
342 m_pNode = m_Guard.assign( g.template get<value_type>());
346 iterator_type( node_type * pNode )
348 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
353 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
354 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
360 iterator_type( iterator_type const& src )
363 m_pNode = m_Guard.assign( src.m_pNode );
369 value_ptr operator ->() const
374 value_ref operator *() const
376 assert( m_pNode != nullptr );
381 iterator_type& operator ++()
388 iterator_type& operator = (iterator_type const& src)
390 m_pNode = src.m_pNode;
391 m_Guard.assign( m_pNode );
396 bool operator ==(iterator_type<C> const& i ) const
398 return m_pNode == i.m_pNode;
401 bool operator !=(iterator_type<C> const& i ) const
403 return m_pNode != i.m_pNode;
411 The forward iterator for lazy list has some features:
412 - it has no post-increment operator
413 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
414 For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
415 may be thrown if a limit of guard count per thread is exceeded.
416 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
417 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
418 deleting operations it is no guarantee that you iterate all item in the list.
420 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
421 for debug purpose only.
423 typedef iterator_type<false> iterator;
424 /// Const forward iterator
426 For iterator's features and requirements see \ref iterator
428 typedef iterator_type<true> const_iterator;
430 /// Returns a forward iterator addressing the first element in a list
432 For empty list \code begin() == end() \endcode
436 iterator it( &m_Head );
437 ++it ; // skip dummy head
441 /// Returns an iterator that addresses the location succeeding the last element in a list
443 Do not use the value returned by <tt>end</tt> function to access any item.
445 The returned value can be used only to control reaching the end of the list.
446 For empty list \code begin() == end() \endcode
450 return iterator( &m_Tail );
453 /// Returns a forward const iterator addressing the first element in a list
455 const_iterator begin() const
457 return get_const_begin();
459 const_iterator cbegin() const
461 return get_const_begin();
465 /// Returns an const iterator that addresses the location succeeding the last element in a list
467 const_iterator end() const
469 return get_const_end();
471 const_iterator cend() const
473 return get_const_end();
479 const_iterator get_const_begin() const
481 const_iterator it( const_cast<node_type *>( &m_Head ));
482 ++it ; // skip dummy head
485 const_iterator get_const_end() const
487 return const_iterator( const_cast<node_type *>(&m_Tail));
492 /// Default constructor initializes empty list
495 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
496 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
499 /// Destroys the list object
503 assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
504 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
509 The function inserts \p val in the list if the list does not contain
510 an item with key equal to \p val.
512 Returns \p true if \p val is linked into the list, \p false otherwise.
514 bool insert( value_type& val )
516 return insert_at( &m_Head, val );
521 This function is intended for derived non-intrusive containers.
523 The function allows to split new item creating into two part:
524 - create item with key only
525 - insert new item into the list
526 - if inserting is success, calls \p f functor to initialize value-field of \p val.
528 The functor signature is:
530 void func( value_type& val );
532 where \p val is the item inserted.
533 While the functor \p f is called the item \p val is locked so
534 the functor has an exclusive access to the item.
535 The user-defined functor is called only if the inserting is success.
537 template <typename Func>
538 bool insert( value_type& val, Func f )
540 return insert_at( &m_Head, val, f );
545 The operation performs inserting or changing data with lock-free manner.
547 If the item \p val not found in the list, then \p val is inserted into the list
548 iff \p bAllowInsert is \p true.
549 Otherwise, the functor \p func is called with item found.
550 The functor signature is:
553 void operator()( bool bNew, value_type& item, value_type& val );
557 - \p bNew - \p true if the item has been inserted, \p false otherwise
558 - \p item - item of the list
559 - \p val - argument \p val passed into the \p update() function
560 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
561 refer to the same thing.
563 The functor may change non-key fields of the \p item.
564 While the functor \p f is working the item \p item is locked,
565 so \p func has exclusive access to the item.
567 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
568 \p second is \p true if new item has been added or \p false if the item with \p key
569 already is in the list.
571 The function makes RCU lock internally.
573 template <typename Func>
574 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
576 return update_at( &m_Head, val, func, bAllowInsert );
579 template <typename Func>
580 CDS_DEPRECATED("ensure() is deprecated, use update()")
581 std::pair<bool, bool> ensure( value_type& val, Func func )
583 return update( val, func, true );
587 /// Unlinks the item \p val from the list
589 The function searches the item \p val in the list and unlink it from the list
590 if it is found and it is equal to \p val.
592 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
593 and deletes the item found. \p unlink finds an item by key and deletes it
594 only if \p val is an item of that list, i.e. the pointer to item found
595 is equal to <tt> &val </tt>.
597 The function returns \p true if success and \p false otherwise.
599 \p disposer specified in \p Traits is called for unlinked item.
601 bool unlink( value_type& val )
603 return unlink_at( &m_Head, val );
606 /// Deletes the item from the list
607 /** \anchor cds_intrusive_LazyList_hp_erase_val
608 The function searches an item with key equal to \p key in the list,
609 unlinks it from the list, and returns \p true.
610 If the item with the key equal to \p key is not found the function return \p false.
612 \p disposer specified in \p Traits is called for deleted item.
614 template <typename Q>
615 bool erase( Q const& key )
617 return erase_at( &m_Head, key, key_comparator());
620 /// Deletes the item from the list using \p pred predicate for searching
622 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
623 but \p pred is used for key comparing.
624 \p Less functor has the interface like \p std::less.
625 \p pred must imply the same element order as the comparator used for building the list.
627 \p disposer specified in \p Traits is called for deleted item.
629 template <typename Q, typename Less>
630 bool erase_with( Q const& key, Less pred )
633 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
636 /// Deletes the item from the list
637 /** \anchor cds_intrusive_LazyList_hp_erase_func
638 The function searches an item with key equal to \p key in the list,
639 call \p func functor with item found, unlinks it from the list, and returns \p true.
640 The \p Func interface is
643 void operator()( value_type const& item );
647 If \p key is not found the function return \p false.
649 \p disposer specified in \p Traits is called for deleted item.
651 template <typename Q, typename Func>
652 bool erase( const Q& key, Func func )
654 return erase_at( &m_Head, key, key_comparator(), func );
657 /// Deletes the item from the list using \p pred predicate for searching
659 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
660 but \p pred is used for key comparing.
661 \p Less functor has the interface like \p std::less.
662 \p pred must imply the same element order as the comparator used for building the list.
664 \p disposer specified in \p Traits is called for deleted item.
666 template <typename Q, typename Less, typename Func>
667 bool erase_with( const Q& key, Less pred, Func func )
670 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
673 /// Extracts the item from the list with specified \p key
674 /** \anchor cds_intrusive_LazyList_hp_extract
675 The function searches an item with key equal to \p key,
676 unlinks it from the list, and returns it as \p guarded_ptr.
677 If \p key is not found the function returns an empty guarded pointer.
679 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
681 The \ref disposer specified in \p Traits class template parameter is called automatically
682 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
683 will be destroyed or released.
684 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
688 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
692 ord_list::guarded_ptr gp( theList.extract( 5 ));
696 // Destructor of gp releases internal HP guard
700 template <typename Q>
701 guarded_ptr extract( Q const& key )
704 extract_at( &m_Head, gp.guard(), key, key_comparator());
708 /// Extracts the item from the list with comparing functor \p pred
710 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(Q const&)"
711 but \p pred predicate is used for key comparing.
713 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
715 \p pred must imply the same element order as the comparator used for building the list.
717 template <typename Q, typename Less>
718 guarded_ptr extract_with( Q const& key, Less pred )
722 extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
726 /// Finds the key \p key
727 /** \anchor cds_intrusive_LazyList_hp_find
728 The function searches the item with key equal to \p key and calls the functor \p f for item found.
729 The interface of \p Func functor is:
732 void operator()( value_type& item, Q& key );
735 where \p item is the item found, \p key is the <tt>find</tt> function argument.
737 The functor may change non-key fields of \p item.
738 While the functor \p f is calling the item \p item is locked.
740 The function returns \p true if \p key is found, \p false otherwise.
742 template <typename Q, typename Func>
743 bool find( Q& key, Func f )
745 return find_at( &m_Head, key, key_comparator(), f );
748 template <typename Q, typename Func>
749 bool find( Q const& key, Func f )
751 return find_at( &m_Head, key, key_comparator(), f );
755 /// Finds the key \p key using \p pred predicate for searching
757 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
758 but \p pred is used for key comparing.
759 \p Less functor has the interface like \p std::less.
760 \p pred must imply the same element order as the comparator used for building the list.
762 template <typename Q, typename Less, typename Func>
763 bool find_with( Q& key, Less pred, Func f )
766 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
769 template <typename Q, typename Less, typename Func>
770 bool find_with( Q const& key, Less pred, Func f )
773 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
777 /// Checks whether the list contains \p key
779 The function searches the item with key equal to \p key
780 and returns \p true if it is found, and \p false otherwise.
782 template <typename Q>
783 bool contains( Q const& key )
785 return find_at( &m_Head, key, key_comparator());
788 template <typename Q>
789 CDS_DEPRECATED("deprecated, use contains()")
790 bool find( Q const& key )
792 return contains( key );
796 /// Checks whether the map contains \p key using \p pred predicate for searching
798 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
799 \p Less functor has the interface like \p std::less.
800 \p Less must imply the same element order as the comparator used for building the list.
802 template <typename Q, typename Less>
803 bool contains( Q const& key, Less pred )
806 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
809 template <typename Q, typename Less>
810 CDS_DEPRECATED("deprecated, use contains()")
811 bool find_with( Q const& key, Less pred )
813 return contains( key, pred );
817 /// Finds \p key and return the item found
818 /** \anchor cds_intrusive_LazyList_hp_get
819 The function searches the item with key equal to \p key
820 and returns an guarded pointer to it.
821 If \p key is not found the function returns an empty guarded pointer.
823 The \ref disposer specified in \p Traits class template parameter is called
824 by garbage collector \p GC automatically when returned \p guarded_ptr object
825 will be destroyed or released.
826 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
830 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
834 ord_list::guarded_ptr gp(theList.get( 5 ));
839 // Destructor of guarded_ptr releases internal HP guard
843 Note the compare functor specified for class \p Traits template parameter
844 should accept a parameter of type \p Q that can be not the same as \p value_type.
846 template <typename Q>
847 guarded_ptr get( Q const& key )
850 get_at( &m_Head, gp.guard(), key, key_comparator());
854 /// Finds \p key and return the item found
856 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( Q const&)"
857 but \p pred is used for comparing the keys.
859 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
861 \p pred must imply the same element order as the comparator used for building the list.
863 template <typename Q, typename Less>
864 guarded_ptr get_with( Q const& key, Less pred )
868 get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
875 typename gc::Guard guard;
878 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
879 guard.assign( node_traits::to_value_ptr( h.ptr()));
880 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
881 m_Head.m_Lock.lock();
884 unlink_node( &m_Head, h.ptr(), &m_Head );
887 m_Head.m_Lock.unlock();
889 retire_node( h.ptr()) ; // free node
894 /// Checks if the list is empty
897 return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
900 /// Returns list's item count
902 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
903 this function always returns 0.
905 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
906 is empty. To check list emptyness use \p empty() method.
910 return m_ItemCounter.value();
915 // split-list support
916 bool insert_aux_node( node_type * pNode )
918 return insert_aux_node( &m_Head, pNode );
921 // split-list support
922 bool insert_aux_node( node_type * pHead, node_type * pNode )
924 assert( pNode != nullptr );
926 // Hack: convert node_type to value_type.
927 // In principle, auxiliary node cannot be reducible to value_type
928 // We assume that internal comparator can correctly distinguish aux and regular node.
929 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
932 bool insert_at( node_type * pHead, value_type& val )
934 link_checker::is_empty( node_traits::to_node_ptr( val ));
939 search( pHead, val, pos, key_comparator());
941 scoped_position_lock alp( pos );
942 if ( validate( pos.pPred, pos.pCur )) {
943 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
944 // failed: key already in list
948 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
957 template <typename Func>
958 bool insert_at( node_type * pHead, value_type& val, Func f )
960 link_checker::is_empty( node_traits::to_node_ptr( val ));
965 search( pHead, val, pos, key_comparator());
967 scoped_position_lock alp( pos );
968 if ( validate( pos.pPred, pos.pCur )) {
969 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
970 // failed: key already in list
974 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
984 template <typename Func>
985 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
991 search( pHead, val, pos, key_comparator());
993 scoped_position_lock alp( pos );
994 if ( validate( pos.pPred, pos.pCur )) {
995 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
996 // key already in the list
998 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
999 return std::make_pair( true, false );
1003 if ( !bAllowInsert )
1004 return std::make_pair( false, false );
1006 link_checker::is_empty( node_traits::to_node_ptr( val ));
1008 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1009 func( true, val, val );
1011 return std::make_pair( true, true );
1018 bool unlink_at( node_type * pHead, value_type& val )
1024 search( pHead, val, pos, key_comparator());
1028 scoped_position_lock alp( pos );
1029 if ( validate( pos.pPred, pos.pCur )) {
1030 if ( pos.pCur != &m_Tail
1031 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1032 && node_traits::to_value_ptr( pos.pCur ) == &val )
1035 unlink_node( pos.pPred, pos.pCur, pHead );
1044 if ( nResult > 0 ) {
1045 retire_node( pos.pCur );
1054 template <typename Q, typename Compare, typename Func>
1055 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1058 search( pHead, val, pos, cmp );
1062 scoped_position_lock alp( pos );
1063 if ( validate( pos.pPred, pos.pCur )) {
1064 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1066 unlink_node( pos.pPred, pos.pCur, pHead );
1067 f( *node_traits::to_value_ptr( *pos.pCur ));
1077 if ( nResult > 0 ) {
1078 retire_node( pos.pCur );
1087 template <typename Q, typename Compare, typename Func>
1088 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1091 return erase_at( pHead, val, cmp, f, pos );
1094 template <typename Q, typename Compare>
1095 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1098 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1101 template <typename Q, typename Compare>
1102 bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
1105 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1106 gp.set( pos.guards.template get<value_type>(position::guard_current_item));
1112 template <typename Q, typename Compare, typename Func>
1113 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1117 search( pHead, val, pos, cmp );
1118 if ( pos.pCur != &m_Tail ) {
1119 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1120 if ( !pos.pCur->is_marked()
1121 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1123 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1130 template <typename Q, typename Compare>
1131 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1135 search( pHead, val, pos, cmp );
1136 return pos.pCur != &m_Tail
1137 && !pos.pCur->is_marked()
1138 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1141 template <typename Q, typename Compare>
1142 bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
1146 search( pHead, val, pos, cmp );
1147 if ( pos.pCur != &m_Tail
1148 && !pos.pCur->is_marked()
1149 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1151 gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
1161 template <typename Q, typename Compare>
1162 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1164 node_type const* pTail = &m_Tail;
1166 marked_node_ptr pCur( pHead );
1167 marked_node_ptr pPrev( pHead );
1169 while ( pCur.ptr() != pTail ) {
1170 if ( pCur.ptr() != pHead ) {
1171 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) >= 0 )
1175 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1178 pCur = pos.guards.protect( position::guard_current_item, pPrev->m_pNext,
1179 []( marked_node_ptr p ) { return node_traits::to_value_ptr( p.ptr()); }
1181 assert( pCur.ptr() != nullptr );
1183 pPrev = pCur = pHead;
1186 pos.pCur = pCur.ptr();
1187 pos.pPred = pPrev.ptr();
1190 static bool validate( node_type * pPred, node_type * pCur )
1192 return !pPred->is_marked()
1193 && !pCur->is_marked()
1194 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1199 }} // namespace cds::intrusive
1201 #endif // CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H