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 traits::stat stat; ///< Internal statistics
205 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
206 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
208 typedef GC gc ; ///< Garbage collector
209 typedef typename traits::back_off back_off; ///< back-off strategy
210 typedef typename traits::item_counter item_counter; ///< Item counting policy used
211 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
213 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
215 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
218 // Rebind traits (split-list support)
219 template <typename... Options>
220 struct rebind_traits {
224 , typename cds::opt::make_options< traits, Options...>::type
230 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
231 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
233 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
235 atomic_node_ptr m_pHead; ///< Head pointer
236 item_counter m_ItemCounter; ///< Item counter
237 stat m_Stat; ///< Internal statistics
240 /// Position pointer for item search
242 atomic_node_ptr * pPrev ; ///< Previous node
243 node_type * pCur ; ///< Current node
244 node_type * pNext ; ///< Next node
246 typename gc::template GuardArray<3> guards ; ///< Guards array
255 struct clean_disposer {
256 void operator()( value_type * p )
258 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
266 static void retire_node( node_type * pNode )
268 assert( pNode != nullptr );
269 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
272 static bool link_node( node_type * pNode, position& pos )
274 assert( pNode != nullptr );
275 link_checker::is_empty( pNode );
277 marked_node_ptr cur(pos.pCur);
278 pNode->m_pNext.store( cur, memory_model::memory_order_release );
279 if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )))
282 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
286 static bool unlink_node( position& pos )
288 assert( pos.pPrev != nullptr );
289 assert( pos.pCur != nullptr );
291 // Mark the node (logical deleting)
292 marked_node_ptr next(pos.pNext, 0);
293 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 ))) {
294 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
295 // CAS may be successful here or in other thread that searching something
296 marked_node_ptr cur(pos.pCur);
297 if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )))
298 retire_node( pos.pCur );
307 template <bool IsConst>
310 friend class MichaelList;
313 value_type * m_pNode;
314 typename gc::Guard m_Guard;
319 typename gc::Guard g;
320 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
322 marked_node_ptr pNext;
324 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
325 g.assign( node_traits::to_value_ptr( pNext.ptr()));
326 } while ( cds_unlikely( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)));
329 m_pNode = m_Guard.assign( g.template get<value_type>());
337 iterator_type( atomic_node_ptr const& pNode )
340 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
342 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr()));
348 if ( cds_likely( p == pNode.load(memory_model::memory_order_acquire)))
354 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
355 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
361 iterator_type( iterator_type const& src )
364 m_pNode = m_Guard.assign( src.m_pNode );
370 value_ptr operator ->() const
375 value_ref operator *() const
377 assert( m_pNode != nullptr );
382 iterator_type& operator ++()
388 iterator_type& operator = (iterator_type const& src)
390 m_pNode = src.m_pNode;
391 m_Guard.assign( m_pNode );
397 void operator ++(int)
404 bool operator ==(iterator_type<C> const& i ) const
406 return m_pNode == i.m_pNode;
409 bool operator !=(iterator_type<C> const& i ) const
411 return m_pNode != i.m_pNode;
417 ///@name Forward iterators (only for debugging purpose)
421 The forward iterator for Michael's list has some features:
422 - it has no post-increment operator
423 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
424 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
425 may be thrown if the limit of guard count per thread is exceeded.
426 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
427 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
428 deleting operations there is no guarantee that you iterate all item in the list.
429 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
431 @warning Use this iterator on the concurrent container for debugging purpose only.
433 The iterator interface:
437 // Default constructor
441 iterator( iterator const& src );
443 // Dereference operator
444 value_type * operator ->() const;
446 // Dereference operator
447 value_type& operator *() const;
449 // Preincrement operator
450 iterator& operator ++();
452 // Assignment operator
453 iterator& operator = (iterator const& src);
455 // Equality operators
456 bool operator ==(iterator const& i ) const;
457 bool operator !=(iterator const& i ) const;
461 typedef iterator_type<false> iterator;
462 /// Const forward iterator
464 For iterator's features and requirements see \ref iterator
466 typedef iterator_type<true> const_iterator;
468 /// Returns a forward iterator addressing the first element in a list
470 For empty list \code begin() == end() \endcode
474 return iterator( m_pHead );
477 /// Returns an iterator that addresses the location succeeding the last element in a list
479 Do not use the value returned by <tt>end</tt> function to access any item.
480 Internally, <tt>end</tt> returning value equals to \p nullptr.
482 The returned value can be used only to control reaching the end of the list.
483 For empty list <tt>begin() == end()</tt>
490 /// Returns a forward const iterator addressing the first element in a list
491 const_iterator cbegin() const
493 return const_iterator( m_pHead );
496 /// Returns a forward const iterator addressing the first element in a list
497 const_iterator begin() const
499 return const_iterator( m_pHead );
502 /// Returns an const iterator that addresses the location succeeding the last element in a list
503 const_iterator end() const
505 return const_iterator();
508 /// Returns an const iterator that addresses the location succeeding the last element in a list
509 const_iterator cend() const
511 return const_iterator();
516 /// Default constructor initializes empty list
520 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
524 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
525 explicit MichaelList( Stat& st )
531 /// Destroys the list object
539 The function inserts \p val into the list if the list does not contain
540 an item with key equal to \p val.
542 Returns \p true if \p val has been linked to the list, \p false otherwise.
544 bool insert( value_type& val )
546 return insert_at( m_pHead, val );
551 This function is intended for derived non-intrusive containers.
553 The function allows to split new item creating into two part:
554 - create item with key only
555 - insert new item into the list
556 - if inserting is success, calls \p f functor to initialize value-field of \p val.
558 The functor signature is:
560 void func( value_type& val );
562 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
563 \p val no any other changes could be made on this list's item by concurrent threads.
564 The user-defined functor is called only if the inserting is success.
566 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
568 template <typename Func>
569 bool insert( value_type& val, Func f )
571 return insert_at( m_pHead, val, f );
576 The operation performs inserting or changing data with lock-free manner.
578 If the item \p val is not found in the list, then \p val is inserted
579 iff \p bInsert is \p true.
580 Otherwise, the functor \p func is called with item found.
581 The functor signature is:
583 void func( bool bNew, value_type& item, value_type& val );
586 - \p bNew - \p true if the item has been inserted, \p false otherwise
587 - \p item - item of the list
588 - \p val - argument \p val passed into the \p update() function
589 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
590 refers to the same thing.
592 The functor may change non-key fields of the \p item; however, \p func must guarantee
593 that during changing no any other modifications could be made on this item by concurrent threads.
595 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
596 \p second is \p true if new item has been added or \p false if the item with that key
599 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
601 template <typename Func>
602 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
604 return update_at( m_pHead, val, func, bInsert );
608 template <typename Func>
609 CDS_DEPRECATED("ensure() is deprecated, use update()")
610 std::pair<bool, bool> ensure( value_type& val, Func func )
612 return update( val, func, true );
616 /// Unlinks the item \p val from the list
618 The function searches the item \p val in the list and unlinks it from the list
619 if it is found and it is equal to \p val.
621 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
622 and deletes the item found. \p %unlink() finds an item by key and deletes it
623 only if \p val is an item of the list, i.e. the pointer to item found
624 is equal to <tt> &val </tt>.
626 \p disposer specified in \p Traits is called for deleted item.
628 The function returns \p true if success and \p false otherwise.
630 bool unlink( value_type& val )
632 return unlink_at( m_pHead, val );
635 /// Deletes the item from the list
636 /** \anchor cds_intrusive_MichaelList_hp_erase_val
637 The function searches an item with key equal to \p key in the list,
638 unlinks it from the list, and returns \p true.
639 If \p key is not found the function return \p false.
641 \p disposer specified in \p Traits is called for deleted item.
643 template <typename Q>
644 bool erase( Q const& key )
646 return erase_at( m_pHead, key, key_comparator());
649 /// Deletes the item from the list using \p pred predicate for searching
651 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
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 \p disposer specified in \p Traits is called for deleted item.
658 template <typename Q, typename Less>
659 bool erase_with( Q const& key, Less pred )
662 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
665 /// Deletes the item from the list
666 /** \anchor cds_intrusive_MichaelList_hp_erase_func
667 The function searches an item with key equal to \p key in the list,
668 call \p func functor with item found, unlinks it from the list, and returns \p true.
669 The \p Func interface is
672 void operator()( value_type const& item );
675 If \p key is not found the function return \p false, \p func is not called.
677 \p disposer specified in \p Traits is called for deleted item.
679 template <typename Q, typename Func>
680 bool erase( Q const& key, Func func )
682 return erase_at( m_pHead, key, key_comparator(), func );
685 /// Deletes the item from the list using \p pred predicate for searching
687 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
688 but \p pred is used for key comparing.
689 \p Less functor has the interface like \p std::less.
690 \p pred must imply the same element order as the comparator used for building the list.
692 \p disposer specified in \p Traits is called for deleted item.
694 template <typename Q, typename Less, typename Func>
695 bool erase_with( Q const& key, Less pred, Func f )
698 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
701 /// Extracts the item from the list with specified \p key
702 /** \anchor cds_intrusive_MichaelList_hp_extract
703 The function searches an item with key equal to \p key,
704 unlinks it from the list, and returns it as \p guarded_ptr.
705 If \p key is not found returns an empty guarded pointer.
707 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
709 The \ref disposer specified in \p Traits class template parameter is called automatically
710 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
711 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
715 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
719 ord_list::guarded_ptr gp(theList.extract( 5 ));
724 // Destructor of gp releases internal HP guard
728 template <typename Q>
729 guarded_ptr extract( Q const& key )
732 extract_at( m_pHead, gp.guard(), key, key_comparator());
736 /// Extracts the item using compare functor \p pred
738 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
739 but \p pred predicate is used for key comparing.
741 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
743 \p pred must imply the same element order as the comparator used for building the list.
745 template <typename Q, typename Less>
746 guarded_ptr extract_with( Q const& key, Less pred )
750 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
754 /// Finds \p key in the list
755 /** \anchor cds_intrusive_MichaelList_hp_find_func
756 The function searches the item with key equal to \p key and calls the functor \p f for item found.
757 The interface of \p Func functor is:
760 void operator()( value_type& item, Q& key );
763 where \p item is the item found, \p key is the <tt>find</tt> function argument.
765 The functor may change non-key fields of \p item. Note that the function is only guarantee
766 that \p item cannot be disposed during functor is executing.
767 The function does not serialize simultaneous access to the \p item. If such access is
768 possible you must provide your own synchronization schema to keep out unsafe item modifications.
770 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
771 may modify both arguments.
773 The function returns \p true if \p val is found, \p false otherwise.
775 template <typename Q, typename Func>
776 bool find( Q& key, Func f )
778 return find_at( m_pHead, key, key_comparator(), f );
781 template <typename Q, typename Func>
782 bool find( Q const& key, Func f )
784 return find_at( m_pHead, key, key_comparator(), f );
788 /// Finds the \p key using \p pred predicate for searching
790 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
791 but \p pred is used for key comparing.
792 \p Less functor has the interface like \p std::less.
793 \p pred must imply the same element order as the comparator used for building the list.
795 template <typename Q, typename Less, typename Func>
796 bool find_with( Q& key, Less pred, Func f )
799 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
802 template <typename Q, typename Less, typename Func>
803 bool find_with( Q const& key, Less pred, Func f )
806 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
810 /// Checks whether the list contains \p key
812 The function searches the item with key equal to \p key
813 and returns \p true if it is found, and \p false otherwise.
815 template <typename Q>
816 bool contains( Q const& key )
818 return find_at( m_pHead, key, key_comparator());
821 template <typename Q>
822 CDS_DEPRECATED("deprecated, use contains()")
823 bool find( Q const& key )
825 return contains( key );
829 /// Checks whether the list contains \p key using \p pred predicate for searching
831 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
832 \p Less functor has the interface like \p std::less.
833 \p Less must imply the same element order as the comparator used for building the list.
835 template <typename Q, typename Less>
836 bool contains( Q const& key, Less pred )
839 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
842 template <typename Q, typename Less>
843 CDS_DEPRECATED("deprecated, use contains()")
844 bool find_with( Q const& key, Less pred )
846 return contains( key, pred );
850 /// Finds the \p key and return the item found
851 /** \anchor cds_intrusive_MichaelList_hp_get
852 The function searches the item with key equal to \p key
853 and returns it as \p guarded_ptr.
854 If \p key is not found the function returns an empty guarded pointer.
856 The \ref disposer specified in \p Traits class template parameter is called
857 by garbage collector \p GC automatically when returned \ref guarded_ptr object
858 will be destroyed or released.
859 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
863 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
867 ord_list::guarded_ptr gp(theList.get( 5 ));
872 // Destructor of guarded_ptr releases internal HP guard
876 Note the compare functor specified for \p Traits template parameter
877 should accept a parameter of type \p Q that can be not the same as \p value_type.
879 template <typename Q>
880 guarded_ptr get( Q const& key )
883 get_at( m_pHead, gp.guard(), key, key_comparator());
887 /// Finds the \p key and return the item found
889 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
890 but \p pred is used for comparing the keys.
892 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
894 \p pred must imply the same element order as the comparator used for building the list.
896 template <typename Q, typename Less>
897 guarded_ptr get_with( Q const& key, Less pred )
901 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
907 The function unlink all items from the list.
911 typename gc::Guard guard;
912 marked_node_ptr head;
914 head = m_pHead.load(memory_model::memory_order_relaxed);
916 guard.assign( node_traits::to_value_ptr( *head.ptr()));
917 if ( cds_likely( m_pHead.load(memory_model::memory_order_acquire) == head )) {
918 if ( head.ptr() == nullptr )
920 value_type& val = *node_traits::to_value_ptr( *head.ptr());
926 /// Checks whether the list is empty
929 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
932 /// Returns list's item count
934 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
935 this function always returns 0.
937 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
938 is empty. To check list emptiness use \p empty() method.
942 return m_ItemCounter.value();
945 /// Returns const reference to internal statistics
946 stat const& statistics() const
953 // split-list support
954 bool insert_aux_node( node_type * pNode )
956 return insert_aux_node( m_pHead, pNode );
959 // split-list support
960 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
962 assert( pNode != nullptr );
964 // Hack: convert node_type to value_type.
965 // In principle, auxiliary node can be non-reducible to value_type
966 // We assume that comparator can correctly distinguish aux and regular node.
967 return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
970 bool insert_at( atomic_node_ptr& refHead, value_type& val )
972 node_type * pNode = node_traits::to_node_ptr( val );
976 if ( search( refHead, val, pos, key_comparator())) {
977 m_Stat.onInsertFailed();
981 if ( link_node( pNode, pos )) {
983 m_Stat.onInsertSuccess();
987 m_Stat.onInsertRetry();
991 template <typename Func>
992 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
994 node_type * pNode = node_traits::to_node_ptr( val );
998 if ( search( refHead, val, pos, key_comparator())) {
999 m_Stat.onInsertFailed();
1003 typename gc::Guard guard;
1004 guard.assign( &val );
1005 if ( link_node( pNode, pos )) {
1008 m_Stat.onInsertSuccess();
1012 m_Stat.onInsertRetry();
1016 template <typename Func>
1017 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
1021 node_type * pNode = node_traits::to_node_ptr( val );
1023 if ( search( refHead, val, pos, key_comparator())) {
1024 if ( cds_unlikely( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits())) {
1026 m_Stat.onUpdateMarked();
1027 continue; // the node found is marked as deleted
1029 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
1031 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1032 m_Stat.onUpdateExisting();
1033 return std::make_pair( true, false );
1037 m_Stat.onUpdateFailed();
1038 return std::make_pair( false, false );
1041 typename gc::Guard guard;
1042 guard.assign( &val );
1043 if ( link_node( pNode, pos )) {
1045 func( true, val, val );
1046 m_Stat.onUpdateNew();
1047 return std::make_pair( true, true );
1051 m_Stat.onUpdateRetry();
1055 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1060 while ( search( refHead, val, pos, key_comparator())) {
1061 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
1062 if ( unlink_node( pos )) {
1064 m_Stat.onEraseSuccess();
1071 m_Stat.onUpdateFailed();
1075 m_Stat.onEraseRetry();
1078 m_Stat.onEraseFailed();
1082 template <typename Q, typename Compare, typename Func>
1083 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1086 while ( search( refHead, val, pos, cmp )) {
1087 if ( unlink_node( pos )) {
1088 f( *node_traits::to_value_ptr( *pos.pCur ));
1090 m_Stat.onEraseSuccess();
1096 m_Stat.onEraseRetry();
1099 m_Stat.onEraseFailed();
1103 template <typename Q, typename Compare, typename Func>
1104 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1107 return erase_at( refHead, val, cmp, f, pos );
1110 template <typename Q, typename Compare>
1111 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1114 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1117 template <typename Q, typename Compare>
1118 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1122 while ( search( refHead, val, pos, cmp )) {
1123 if ( unlink_node( pos )) {
1124 dest.set( pos.guards.template get<value_type>( position::guard_current_item ));
1126 m_Stat.onEraseSuccess();
1131 m_Stat.onEraseRetry();
1134 m_Stat.onEraseFailed();
1138 template <typename Q, typename Compare>
1139 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1142 if ( search( refHead, val, pos, cmp ) ) {
1143 m_Stat.onFindSuccess();
1147 m_Stat.onFindFailed();
1151 template <typename Q, typename Compare, typename Func>
1152 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1155 if ( search( refHead, val, pos, cmp )) {
1156 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1157 m_Stat.onFindSuccess();
1161 m_Stat.onFindFailed();
1165 template <typename Q, typename Compare>
1166 bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1169 if ( search( refHead, val, pos, cmp )) {
1170 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1171 m_Stat.onFindSuccess();
1175 m_Stat.onFindFailed();
1184 template <typename Q, typename Compare >
1185 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1187 atomic_node_ptr * pPrev;
1188 marked_node_ptr pNext;
1189 marked_node_ptr pCur;
1197 pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1198 [](marked_node_ptr p) -> value_type *
1200 return node_traits::to_value_ptr( p.ptr());
1204 if ( pCur.ptr() == nullptr ) {
1207 pos.pNext = nullptr;
1211 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1212 [](marked_node_ptr p ) -> value_type *
1214 return node_traits::to_value_ptr( p.ptr());
1216 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr())) {
1221 // pNext contains deletion mark for pCur
1222 if ( pNext.bits() == 1 ) {
1223 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1224 marked_node_ptr cur( pCur.ptr());
1225 if ( cds_unlikely( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
1226 retire_node( pCur.ptr());
1227 m_Stat.onHelpingSuccess();
1231 m_Stat.onHelpingFailed();
1236 assert( pCur.ptr() != nullptr );
1237 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1240 pos.pCur = pCur.ptr();
1241 pos.pNext = pNext.ptr();
1244 pPrev = &( pCur->m_pNext );
1245 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1248 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1253 }} // namespace cds::intrusive
1255 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H