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_MICHAEL_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
34 #include <cds/intrusive/details/michael_list_base.h>
35 #include <cds/details/make_const_type.h>
37 namespace cds { namespace intrusive {
39 /// Michael's lock-free ordered single-linked list
40 /** @ingroup cds_intrusive_list
41 \anchor cds_intrusive_MichaelList_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 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
50 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see \p michael_list::node).
51 - \p T - type to be stored in the list. The type must be based on \p michael_list::node (for \p michael_list::base_hook)
52 or it must have a member of type \p michael_list::node (for \p michael_list::member_hook).
53 - \p Traits - type traits, default is \p michael_list::traits. It is possible to declare option-based
54 list with \p cds::intrusive::michael_list::make_traits metafunction:
55 For example, the following traits-based declaration of \p gc::HP Michael's list
57 #include <cds/intrusive/michael_list_hp.h>
58 // Declare item stored in your list
59 struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
65 // Declare comparator for the item
67 int operator()( item const& i1, item const& i2 ) const
69 return i1.nKey - i2.nKey;
74 struct my_traits: public cds::intrusive::michael_list::traits
76 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
77 typedef my_compare compare;
80 // Declare traits-based list
81 typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits > traits_based_list;
83 is equivalent for the following option-based list
85 #include <cds/intrusive/michael_list_hp.h>
87 // item struct and my_compare are the same
89 // Declare option-based list
90 typedef cds::intrusive::MichaelList< cds::gc::HP, item,
91 typename cds::intrusive::michael_list::make_traits<
92 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
93 ,cds::intrusive::opt::compare< my_compare > // item comparator option
99 There are different specializations of this template for each garbage collecting schema.
100 You should select GC needed and include appropriate .h-file:
101 - for \p gc::HP: <tt> <cds/intrusive/michael_list_hp.h> </tt>
102 - for \p gc::DHP: <tt> <cds/intrusive/michael_list_dhp.h> </tt>
103 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
104 - for \p gc::nogc: <tt> <cds/intrusive/michael_list_nogc.h> </tt>
105 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
107 Then, you should incorporate \p michael_list::node into your struct \p T and provide
108 appropriate \p michael_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
109 define a struct based on \p michael_list::traits.
111 Example for \p gc::DHP and base hook:
113 // Include GC-related Michael's list specialization
114 #include <cds/intrusive/michael_list_dhp.h>
116 // Data stored in Michael's list
117 struct my_data: public cds::intrusive::michael_list::node< cds::gc::DHP >
126 // my_data comparing functor
128 int operator()( const my_data& d1, const my_data& d2 )
130 return d1.strKey.compare( d2.strKey );
133 int operator()( const my_data& d, const std::string& s )
135 return d.strKey.compare(s);
138 int operator()( const std::string& s, const my_data& d )
140 return s.compare( d.strKey );
146 struct my_traits: public cds::intrusive::michael_list::traits
148 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
149 typedef my_data_cmp compare;
153 typedef cds::intrusive::MichaelList< cds::gc::DHP, my_data, my_traits > traits_based_list;
156 Equivalent option-based code:
158 // GC-related specialization
159 #include <cds/intrusive/michael_list_dhp.h>
168 // Declare option-based list
169 typedef cds::intrusive::MichaelList< cds::gc::DHP
171 , typename cds::intrusive::michael_list::make_traits<
172 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
173 ,cds::intrusive::opt::compare< my_data_cmp >
182 #ifdef CDS_DOXYGEN_INVOKED
183 ,class Traits = michael_list::traits
191 typedef T value_type; ///< type of value stored in the list
192 typedef Traits traits; ///< Traits template parameter
194 typedef typename traits::hook hook; ///< hook type
195 typedef typename hook::node_type node_type; ///< node type
197 # ifdef CDS_DOXYGEN_INVOKED
198 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
200 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
203 typedef typename traits::disposer disposer; ///< disposer used
204 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
205 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
207 typedef GC gc ; ///< Garbage collector
208 typedef typename traits::back_off back_off; ///< back-off strategy
209 typedef typename traits::item_counter item_counter; ///< Item counting policy used
210 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
212 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
214 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
217 // Rebind traits (split-list support)
218 template <typename... Options>
219 struct rebind_traits {
223 , typename cds::opt::make_options< traits, Options...>::type
229 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
230 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
232 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
234 atomic_node_ptr m_pHead; ///< Head pointer
235 item_counter m_ItemCounter; ///< Item counter
238 /// Position pointer for item search
240 atomic_node_ptr * pPrev ; ///< Previous node
241 node_type * pCur ; ///< Current node
242 node_type * pNext ; ///< Next node
244 typename gc::template GuardArray<3> guards ; ///< Guards array
253 struct clean_disposer {
254 void operator()( value_type * p )
256 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
264 static void retire_node( node_type * pNode )
266 assert( pNode != nullptr );
267 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
270 static bool link_node( node_type * pNode, position& pos )
272 assert( pNode != nullptr );
273 link_checker::is_empty( pNode );
275 marked_node_ptr cur(pos.pCur);
276 pNode->m_pNext.store( cur, memory_model::memory_order_release );
277 if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )))
280 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
284 static bool unlink_node( position& pos )
286 assert( pos.pPrev != nullptr );
287 assert( pos.pCur != nullptr );
289 // Mark the node (logical deleting)
290 marked_node_ptr next(pos.pNext, 0);
291 if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
292 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
293 // CAS may be successful here or in other thread that searching something
294 marked_node_ptr cur(pos.pCur);
295 if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )))
296 retire_node( pos.pCur );
305 template <bool IsConst>
308 friend class MichaelList;
311 value_type * m_pNode;
312 typename gc::Guard m_Guard;
317 typename gc::Guard g;
318 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
320 marked_node_ptr pNext;
322 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
323 g.assign( node_traits::to_value_ptr( pNext.ptr()));
324 } while ( cds_unlikely( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)));
327 m_pNode = m_Guard.assign( g.template get<value_type>());
335 iterator_type( atomic_node_ptr const& pNode )
338 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
340 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr()));
346 if ( cds_likely( p == pNode.load(memory_model::memory_order_acquire)))
352 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
353 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
359 iterator_type( iterator_type const& src )
362 m_pNode = m_Guard.assign( src.m_pNode );
368 value_ptr operator ->() const
373 value_ref operator *() const
375 assert( m_pNode != nullptr );
380 iterator_type& operator ++()
386 iterator_type& operator = (iterator_type const& src)
388 m_pNode = src.m_pNode;
389 m_Guard.assign( m_pNode );
395 void operator ++(int)
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;
415 ///@name Forward iterators (only for debugging purpose)
419 The forward iterator for Michael's list has some features:
420 - it has no post-increment operator
421 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
422 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
423 may be thrown if the limit of guard count per thread is exceeded.
424 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
425 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
426 deleting operations there is no guarantee that you iterate all item in the list.
427 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
429 @warning Use this iterator on the concurrent container for debugging purpose only.
431 The iterator interface:
435 // Default constructor
439 iterator( iterator const& src );
441 // Dereference operator
442 value_type * operator ->() const;
444 // Dereference operator
445 value_type& operator *() const;
447 // Preincrement operator
448 iterator& operator ++();
450 // Assignment operator
451 iterator& operator = (iterator const& src);
453 // Equality operators
454 bool operator ==(iterator const& i ) const;
455 bool operator !=(iterator const& i ) const;
459 typedef iterator_type<false> iterator;
460 /// Const forward iterator
462 For iterator's features and requirements see \ref iterator
464 typedef iterator_type<true> const_iterator;
466 /// Returns a forward iterator addressing the first element in a list
468 For empty list \code begin() == end() \endcode
472 return iterator( m_pHead );
475 /// Returns an iterator that addresses the location succeeding the last element in a list
477 Do not use the value returned by <tt>end</tt> function to access any item.
478 Internally, <tt>end</tt> returning value equals to \p nullptr.
480 The returned value can be used only to control reaching the end of the list.
481 For empty list <tt>begin() == end()</tt>
488 /// Returns a forward const iterator addressing the first element in a list
489 const_iterator cbegin() const
491 return const_iterator( m_pHead );
494 /// Returns a forward const iterator addressing the first element in a list
495 const_iterator begin() const
497 return const_iterator( m_pHead );
500 /// Returns an const iterator that addresses the location succeeding the last element in a list
501 const_iterator end() const
503 return const_iterator();
506 /// Returns an const iterator that addresses the location succeeding the last element in a list
507 const_iterator cend() const
509 return const_iterator();
514 /// Default constructor initializes empty list
518 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
521 /// Destroys the list object
529 The function inserts \p val into the list if the list does not contain
530 an item with key equal to \p val.
532 Returns \p true if \p val has been linked to the list, \p false otherwise.
534 bool insert( value_type& val )
536 return insert_at( m_pHead, val );
541 This function is intended for derived non-intrusive containers.
543 The function allows to split new item creating into two part:
544 - create item with key only
545 - insert new item into the list
546 - if inserting is success, calls \p f functor to initialize value-field of \p val.
548 The functor signature is:
550 void func( value_type& val );
552 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
553 \p val no any other changes could be made on this list's item by concurrent threads.
554 The user-defined functor is called only if the inserting is success.
556 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
558 template <typename Func>
559 bool insert( value_type& val, Func f )
561 return insert_at( m_pHead, val, f );
566 The operation performs inserting or changing data with lock-free manner.
568 If the item \p val is not found in the list, then \p val is inserted
569 iff \p bInsert is \p true.
570 Otherwise, the functor \p func is called with item found.
571 The functor signature is:
573 void func( bool bNew, value_type& item, value_type& val );
576 - \p bNew - \p true if the item has been inserted, \p false otherwise
577 - \p item - item of the list
578 - \p val - argument \p val passed into the \p update() function
579 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
580 refers to the same thing.
582 The functor may change non-key fields of the \p item; however, \p func must guarantee
583 that during changing no any other modifications could be made on this item by concurrent threads.
585 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
586 \p second is \p true if new item has been added or \p false if the item with \p key
587 already is in the list.
589 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
591 template <typename Func>
592 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
594 return update_at( m_pHead, val, func, bInsert );
598 template <typename Func>
599 CDS_DEPRECATED("ensure() is deprecated, use update()")
600 std::pair<bool, bool> ensure( value_type& val, Func func )
602 return update( val, func, true );
606 /// Unlinks the item \p val from the list
608 The function searches the item \p val in the list and unlinks it from the list
609 if it is found and it is equal to \p val.
611 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
612 and deletes the item found. \p %unlink() finds an item by key and deletes it
613 only if \p val is an item of the list, i.e. the pointer to item found
614 is equal to <tt> &val </tt>.
616 \p disposer specified in \p Traits is called for deleted item.
618 The function returns \p true if success and \p false otherwise.
620 bool unlink( value_type& val )
622 return unlink_at( m_pHead, val );
625 /// Deletes the item from the list
626 /** \anchor cds_intrusive_MichaelList_hp_erase_val
627 The function searches an item with key equal to \p key in the list,
628 unlinks it from the list, and returns \p true.
629 If \p key is not found the function return \p false.
631 \p disposer specified in \p Traits is called for deleted item.
633 template <typename Q>
634 bool erase( Q const& key )
636 return erase_at( m_pHead, key, key_comparator());
639 /// Deletes the item from the list using \p pred predicate for searching
641 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
642 but \p pred is used for key comparing.
643 \p Less functor has the interface like \p std::less.
644 \p pred must imply the same element order as the comparator used for building the list.
646 \p disposer specified in \p Traits is called for deleted item.
648 template <typename Q, typename Less>
649 bool erase_with( Q const& key, Less pred )
652 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
655 /// Deletes the item from the list
656 /** \anchor cds_intrusive_MichaelList_hp_erase_func
657 The function searches an item with key equal to \p key in the list,
658 call \p func functor with item found, unlinks it from the list, and returns \p true.
659 The \p Func interface is
662 void operator()( value_type const& item );
665 If \p key is not found the function return \p false, \p func is not called.
667 \p disposer specified in \p Traits is called for deleted item.
669 template <typename Q, typename Func>
670 bool erase( Q const& key, Func func )
672 return erase_at( m_pHead, key, key_comparator(), func );
675 /// Deletes the item from the list using \p pred predicate for searching
677 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
678 but \p pred is used for key comparing.
679 \p Less functor has the interface like \p std::less.
680 \p pred must imply the same element order as the comparator used for building the list.
682 \p disposer specified in \p Traits is called for deleted item.
684 template <typename Q, typename Less, typename Func>
685 bool erase_with( Q const& key, Less pred, Func f )
688 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
691 /// Extracts the item from the list with specified \p key
692 /** \anchor cds_intrusive_MichaelList_hp_extract
693 The function searches an item with key equal to \p key,
694 unlinks it from the list, and returns it as \p guarded_ptr.
695 If \p key is not found returns an empty guarded pointer.
697 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
699 The \ref disposer specified in \p Traits class template parameter is called automatically
700 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
701 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
705 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
709 ord_list::guarded_ptr gp(theList.extract( 5 ));
714 // Destructor of gp releases internal HP guard
718 template <typename Q>
719 guarded_ptr extract( Q const& key )
722 extract_at( m_pHead, gp.guard(), key, key_comparator());
726 /// Extracts the item using compare functor \p pred
728 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
729 but \p pred predicate is used for key comparing.
731 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
733 \p pred must imply the same element order as the comparator used for building the list.
735 template <typename Q, typename Less>
736 guarded_ptr extract_with( Q const& key, Less pred )
740 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
744 /// Finds \p key in the list
745 /** \anchor cds_intrusive_MichaelList_hp_find_func
746 The function searches the item with key equal to \p key and calls the functor \p f for item found.
747 The interface of \p Func functor is:
750 void operator()( value_type& item, Q& key );
753 where \p item is the item found, \p key is the <tt>find</tt> function argument.
755 The functor may change non-key fields of \p item. Note that the function is only guarantee
756 that \p item cannot be disposed during functor is executing.
757 The function does not serialize simultaneous access to the \p item. If such access is
758 possible you must provide your own synchronization schema to keep out unsafe item modifications.
760 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
761 may modify both arguments.
763 The function returns \p true if \p val is found, \p false otherwise.
765 template <typename Q, typename Func>
766 bool find( Q& key, Func f )
768 return find_at( m_pHead, key, key_comparator(), f );
771 template <typename Q, typename Func>
772 bool find( Q const& key, Func f )
774 return find_at( m_pHead, key, key_comparator(), f );
778 /// Finds the \p key using \p pred predicate for searching
780 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
781 but \p pred is used for key comparing.
782 \p Less functor has the interface like \p std::less.
783 \p pred must imply the same element order as the comparator used for building the list.
785 template <typename Q, typename Less, typename Func>
786 bool find_with( Q& key, Less pred, Func f )
789 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
792 template <typename Q, typename Less, typename Func>
793 bool find_with( Q const& key, Less pred, Func f )
796 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
800 /// Checks whether the list contains \p key
802 The function searches the item with key equal to \p key
803 and returns \p true if it is found, and \p false otherwise.
805 template <typename Q>
806 bool contains( Q const& key )
808 return find_at( m_pHead, key, key_comparator());
811 template <typename Q>
812 CDS_DEPRECATED("deprecated, use contains()")
813 bool find( Q const& key )
815 return contains( key );
819 /// Checks whether the list contains \p key using \p pred predicate for searching
821 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
822 \p Less functor has the interface like \p std::less.
823 \p Less must imply the same element order as the comparator used for building the list.
825 template <typename Q, typename Less>
826 bool contains( Q const& key, Less pred )
829 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
832 template <typename Q, typename Less>
833 CDS_DEPRECATED("deprecated, use contains()")
834 bool find_with( Q const& key, Less pred )
836 return contains( key, pred );
840 /// Finds the \p key and return the item found
841 /** \anchor cds_intrusive_MichaelList_hp_get
842 The function searches the item with key equal to \p key
843 and returns it as \p guarded_ptr.
844 If \p key is not found the function returns an empty guarded pointer.
846 The \ref disposer specified in \p Traits class template parameter is called
847 by garbage collector \p GC automatically when returned \ref guarded_ptr object
848 will be destroyed or released.
849 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
853 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
857 ord_list::guarded_ptr gp(theList.get( 5 ));
862 // Destructor of guarded_ptr releases internal HP guard
866 Note the compare functor specified for \p Traits template parameter
867 should accept a parameter of type \p Q that can be not the same as \p value_type.
869 template <typename Q>
870 guarded_ptr get( Q const& key )
873 get_at( m_pHead, gp.guard(), key, key_comparator());
877 /// Finds the \p key and return the item found
879 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
880 but \p pred is used for comparing the keys.
882 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
884 \p pred must imply the same element order as the comparator used for building the list.
886 template <typename Q, typename Less>
887 guarded_ptr get_with( Q const& key, Less pred )
891 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
897 The function unlink all items from the list.
901 typename gc::Guard guard;
902 marked_node_ptr head;
904 head = m_pHead.load(memory_model::memory_order_relaxed);
906 guard.assign( node_traits::to_value_ptr( *head.ptr()));
907 if ( cds_likely( m_pHead.load(memory_model::memory_order_acquire) == head )) {
908 if ( head.ptr() == nullptr )
910 value_type& val = *node_traits::to_value_ptr( *head.ptr());
916 /// Checks whether the list is empty
919 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
922 /// Returns list's item count
924 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
925 this function always returns 0.
927 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
928 is empty. To check list emptyness use \p empty() method.
932 return m_ItemCounter.value();
937 // split-list support
938 bool insert_aux_node( node_type * pNode )
940 return insert_aux_node( m_pHead, pNode );
943 // split-list support
944 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
946 assert( pNode != nullptr );
948 // Hack: convert node_type to value_type.
949 // In principle, auxiliary node can be non-reducible to value_type
950 // We assume that comparator can correctly distinguish aux and regular node.
951 return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
954 bool insert_at( atomic_node_ptr& refHead, value_type& val )
956 node_type * pNode = node_traits::to_node_ptr( val );
960 if ( search( refHead, val, pos, key_comparator()))
963 if ( link_node( pNode, pos )) {
969 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
973 template <typename Func>
974 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
976 node_type * pNode = node_traits::to_node_ptr( val );
980 if ( search( refHead, val, pos, key_comparator()))
983 typename gc::Guard guard;
984 guard.assign( &val );
985 if ( link_node( pNode, pos )) {
992 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
996 template <typename Func>
997 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
1001 node_type * pNode = node_traits::to_node_ptr( val );
1003 if ( search( refHead, val, pos, key_comparator())) {
1004 if ( cds_unlikely( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits())) {
1006 continue; // the node found is marked as deleted
1008 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
1010 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1011 return std::make_pair( true, false );
1015 return std::make_pair( false, false );
1017 typename gc::Guard guard;
1018 guard.assign( &val );
1019 if ( link_node( pNode, pos )) {
1021 func( true, val, val );
1022 return std::make_pair( true, true );
1025 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1030 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1035 while ( search( refHead, val, pos, key_comparator())) {
1036 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
1037 if ( unlink_node( pos )) {
1050 template <typename Q, typename Compare, typename Func>
1051 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1054 while ( search( refHead, val, pos, cmp )) {
1055 if ( unlink_node( pos )) {
1056 f( *node_traits::to_value_ptr( *pos.pCur ));
1066 template <typename Q, typename Compare, typename Func>
1067 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1070 return erase_at( refHead, val, cmp, f, pos );
1073 template <typename Q, typename Compare>
1074 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1077 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1080 template <typename Q, typename Compare>
1081 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1085 while ( search( refHead, val, pos, cmp )) {
1086 if ( unlink_node( pos )) {
1087 dest.set( pos.guards.template get<value_type>( position::guard_current_item ));
1097 template <typename Q, typename Compare>
1098 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1101 return search( refHead, val, pos, cmp );
1104 template <typename Q, typename Compare, typename Func>
1105 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1108 if ( search( refHead, val, pos, cmp )) {
1109 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1115 template <typename Q, typename Compare>
1116 bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1119 if ( search( refHead, val, pos, cmp )) {
1120 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1131 template <typename Q, typename Compare >
1132 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1134 atomic_node_ptr * pPrev;
1135 marked_node_ptr pNext;
1136 marked_node_ptr pCur;
1144 pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1145 [](marked_node_ptr p) -> value_type *
1147 return node_traits::to_value_ptr( p.ptr());
1151 if ( pCur.ptr() == nullptr ) {
1154 pos.pNext = nullptr;
1158 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1159 [](marked_node_ptr p ) -> value_type *
1161 return node_traits::to_value_ptr( p.ptr());
1163 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr())) {
1168 // pNext contains deletion mark for pCur
1169 if ( pNext.bits() == 1 ) {
1170 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1171 marked_node_ptr cur( pCur.ptr());
1172 if ( cds_unlikely( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
1173 retire_node( pCur.ptr());
1181 assert( pCur.ptr() != nullptr );
1182 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1185 pos.pCur = pCur.ptr();
1186 pos.pNext = pNext.ptr();
1189 pPrev = &( pCur->m_pNext );
1190 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1193 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1198 }} // namespace cds::intrusive
1200 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H