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 bool unlink( value_type& val )
601 return unlink_at( &m_Head, val );
604 /// Deletes the item from the list
605 /** \anchor cds_intrusive_LazyList_hp_erase_val
606 The function searches an item with key equal to \p key in the list,
607 unlinks it from the list, and returns \p true.
608 If the item with the key equal to \p key is not found the function return \p false.
610 template <typename Q>
611 bool erase( Q const& key )
613 return erase_at( &m_Head, key, key_comparator());
616 /// Deletes the item from the list using \p pred predicate for searching
618 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
619 but \p pred is used for key comparing.
620 \p Less functor has the interface like \p std::less.
621 \p pred must imply the same element order as the comparator used for building the list.
623 template <typename Q, typename Less>
624 bool erase_with( Q const& key, Less pred )
627 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
630 /// Deletes the item from the list
631 /** \anchor cds_intrusive_LazyList_hp_erase_func
632 The function searches an item with key equal to \p key in the list,
633 call \p func functor with item found, unlinks it from the list, and returns \p true.
634 The \p Func interface is
637 void operator()( value_type const& item );
641 If \p key is not found the function return \p false.
643 template <typename Q, typename Func>
644 bool erase( const Q& key, Func func )
646 return erase_at( &m_Head, key, key_comparator(), func );
649 /// Deletes the item from the list using \p pred predicate for searching
651 The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
652 but \p pred is used for key comparing.
653 \p Less functor has the interface like \p std::less.
654 \p pred must imply the same element order as the comparator used for building the list.
656 template <typename Q, typename Less, typename Func>
657 bool erase_with( const Q& key, Less pred, Func func )
660 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
663 /// Extracts the item from the list with specified \p key
664 /** \anchor cds_intrusive_LazyList_hp_extract
665 The function searches an item with key equal to \p key,
666 unlinks it from the list, and returns it as \p guarded_ptr.
667 If \p key is not found the function returns an empty guarded pointer.
669 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
671 The \ref disposer specified in \p Traits class template parameter is called automatically
672 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
673 will be destroyed or released.
674 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
678 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
682 ord_list::guarded_ptr gp( theList.extract( 5 ));
686 // Destructor of gp releases internal HP guard
690 template <typename Q>
691 guarded_ptr extract( Q const& key )
694 extract_at( &m_Head, gp.guard(), key, key_comparator());
698 /// Extracts the item from the list with comparing functor \p pred
700 The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(Q const&)"
701 but \p pred predicate is used for key comparing.
703 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
705 \p pred must imply the same element order as the comparator used for building the list.
707 template <typename Q, typename Less>
708 guarded_ptr extract_with( Q const& key, Less pred )
712 extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
716 /// Finds the key \p key
717 /** \anchor cds_intrusive_LazyList_hp_find
718 The function searches the item with key equal to \p key and calls the functor \p f for item found.
719 The interface of \p Func functor is:
722 void operator()( value_type& item, Q& key );
725 where \p item is the item found, \p key is the <tt>find</tt> function argument.
727 The functor may change non-key fields of \p item.
728 While the functor \p f is calling the item \p item is locked.
730 The function returns \p true if \p key is found, \p false otherwise.
732 template <typename Q, typename Func>
733 bool find( Q& key, Func f )
735 return find_at( &m_Head, key, key_comparator(), f );
738 template <typename Q, typename Func>
739 bool find( Q const& key, Func f )
741 return find_at( &m_Head, key, key_comparator(), f );
745 /// Finds the key \p key using \p pred predicate for searching
747 The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
748 but \p pred is used for key comparing.
749 \p Less functor has the interface like \p std::less.
750 \p pred must imply the same element order as the comparator used for building the list.
752 template <typename Q, typename Less, typename Func>
753 bool find_with( Q& key, Less pred, Func f )
756 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
759 template <typename Q, typename Less, typename Func>
760 bool find_with( Q const& key, Less pred, Func f )
763 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
767 /// Checks whether the list contains \p key
769 The function searches the item with key equal to \p key
770 and returns \p true if it is found, and \p false otherwise.
772 template <typename Q>
773 bool contains( Q const& key )
775 return find_at( &m_Head, key, key_comparator());
778 template <typename Q>
779 CDS_DEPRECATED("deprecated, use contains()")
780 bool find( Q const& key )
782 return contains( key );
786 /// Checks whether the map contains \p key using \p pred predicate for searching
788 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
789 \p Less functor has the interface like \p std::less.
790 \p Less must imply the same element order as the comparator used for building the list.
792 template <typename Q, typename Less>
793 bool contains( Q const& key, Less pred )
796 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
799 template <typename Q, typename Less>
800 CDS_DEPRECATED("deprecated, use contains()")
801 bool find_with( Q const& key, Less pred )
803 return contains( key, pred );
807 /// Finds \p key and return the item found
808 /** \anchor cds_intrusive_LazyList_hp_get
809 The function searches the item with key equal to \p key
810 and returns an guarded pointer to it.
811 If \p key is not found the function returns an empty guarded pointer.
813 The \ref disposer specified in \p Traits class template parameter is called
814 by garbage collector \p GC automatically when returned \p guarded_ptr object
815 will be destroyed or released.
816 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
820 typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits > ord_list;
824 ord_list::guarded_ptr gp(theList.get( 5 ));
829 // Destructor of guarded_ptr releases internal HP guard
833 Note the compare functor specified for class \p Traits template parameter
834 should accept a parameter of type \p Q that can be not the same as \p value_type.
836 template <typename Q>
837 guarded_ptr get( Q const& key )
840 get_at( &m_Head, gp.guard(), key, key_comparator());
844 /// Finds \p key and return the item found
846 The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( Q const&)"
847 but \p pred is used for comparing the keys.
849 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
851 \p pred must imply the same element order as the comparator used for building the list.
853 template <typename Q, typename Less>
854 guarded_ptr get_with( Q const& key, Less pred )
858 get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
865 typename gc::Guard guard;
868 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
869 guard.assign( node_traits::to_value_ptr( h.ptr()));
870 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
871 m_Head.m_Lock.lock();
874 unlink_node( &m_Head, h.ptr(), &m_Head );
877 m_Head.m_Lock.unlock();
879 retire_node( h.ptr()) ; // free node
884 /// Checks if the list is empty
887 return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
890 /// Returns list's item count
892 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
893 this function always returns 0.
895 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
896 is empty. To check list emptyness use \p empty() method.
900 return m_ItemCounter.value();
905 // split-list support
906 bool insert_aux_node( node_type * pNode )
908 return insert_aux_node( &m_Head, pNode );
911 // split-list support
912 bool insert_aux_node( node_type * pHead, node_type * pNode )
914 assert( pNode != nullptr );
916 // Hack: convert node_type to value_type.
917 // In principle, auxiliary node cannot be reducible to value_type
918 // We assume that internal comparator can correctly distinguish aux and regular node.
919 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
922 bool insert_at( node_type * pHead, value_type& val )
924 link_checker::is_empty( node_traits::to_node_ptr( val ));
929 search( pHead, val, pos, key_comparator());
931 scoped_position_lock alp( pos );
932 if ( validate( pos.pPred, pos.pCur )) {
933 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
934 // failed: key already in list
938 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
947 template <typename Func>
948 bool insert_at( node_type * pHead, value_type& val, Func f )
950 link_checker::is_empty( node_traits::to_node_ptr( val ));
955 search( pHead, val, pos, key_comparator());
957 scoped_position_lock alp( pos );
958 if ( validate( pos.pPred, pos.pCur )) {
959 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
960 // failed: key already in list
964 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
974 template <typename Func>
975 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
981 search( pHead, val, pos, key_comparator());
983 scoped_position_lock alp( pos );
984 if ( validate( pos.pPred, pos.pCur )) {
985 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
986 // key already in the list
988 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
989 return std::make_pair( true, false );
994 return std::make_pair( false, false );
996 link_checker::is_empty( node_traits::to_node_ptr( val ));
998 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
999 func( true, val, val );
1001 return std::make_pair( true, true );
1008 bool unlink_at( node_type * pHead, value_type& val )
1014 search( pHead, val, pos, key_comparator());
1018 scoped_position_lock alp( pos );
1019 if ( validate( pos.pPred, pos.pCur )) {
1020 if ( pos.pCur != &m_Tail
1021 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1022 && node_traits::to_value_ptr( pos.pCur ) == &val )
1025 unlink_node( pos.pPred, pos.pCur, pHead );
1034 if ( nResult > 0 ) {
1035 retire_node( pos.pCur );
1044 template <typename Q, typename Compare, typename Func>
1045 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1048 search( pHead, val, pos, cmp );
1052 scoped_position_lock alp( pos );
1053 if ( validate( pos.pPred, pos.pCur )) {
1054 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1056 unlink_node( pos.pPred, pos.pCur, pHead );
1057 f( *node_traits::to_value_ptr( *pos.pCur ));
1067 if ( nResult > 0 ) {
1068 retire_node( pos.pCur );
1077 template <typename Q, typename Compare, typename Func>
1078 bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1081 return erase_at( pHead, val, cmp, f, pos );
1084 template <typename Q, typename Compare>
1085 bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1088 return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1091 template <typename Q, typename Compare>
1092 bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
1095 if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1096 gp.set( pos.guards.template get<value_type>(position::guard_current_item));
1102 template <typename Q, typename Compare, typename Func>
1103 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1107 search( pHead, val, pos, cmp );
1108 if ( pos.pCur != &m_Tail ) {
1109 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1110 if ( !pos.pCur->is_marked()
1111 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1113 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1120 template <typename Q, typename Compare>
1121 bool find_at( node_type * pHead, Q const& val, Compare cmp )
1125 search( pHead, val, pos, cmp );
1126 return pos.pCur != &m_Tail
1127 && !pos.pCur->is_marked()
1128 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1131 template <typename Q, typename Compare>
1132 bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
1136 search( pHead, val, pos, cmp );
1137 if ( pos.pCur != &m_Tail
1138 && !pos.pCur->is_marked()
1139 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1141 gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
1151 template <typename Q, typename Compare>
1152 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1154 node_type const* pTail = &m_Tail;
1156 marked_node_ptr pCur( pHead );
1157 marked_node_ptr pPrev( pHead );
1159 while ( pCur.ptr() != pTail ) {
1160 if ( pCur.ptr() != pHead ) {
1161 if ( cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) >= 0 )
1165 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1168 pCur = pos.guards.protect( position::guard_current_item, pPrev->m_pNext,
1169 []( marked_node_ptr p ) { return node_traits::to_value_ptr( p.ptr()); }
1171 assert( pCur.ptr() != nullptr );
1173 pPrev = pCur = pHead;
1176 pos.pCur = pCur.ptr();
1177 pos.pPred = pPrev.ptr();
1180 static bool validate( node_type * pPred, node_type * pCur )
1182 return !pPred->is_marked()
1183 && !pCur->is_marked()
1184 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1189 }} // namespace cds::intrusive
1191 #endif // CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H