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
229 template <typename Stat>
230 using select_stat_wrapper = michael_list::select_stat_wrapper< Stat >;
234 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
235 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
237 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
239 atomic_node_ptr m_pHead; ///< Head pointer
240 item_counter m_ItemCounter; ///< Item counter
241 stat m_Stat; ///< Internal statistics
244 /// Position pointer for item search
246 atomic_node_ptr * pPrev ; ///< Previous node
247 node_type * pCur ; ///< Current node
248 node_type * pNext ; ///< Next node
250 typename gc::template GuardArray<3> guards ; ///< Guards array
259 struct clean_disposer {
260 void operator()( value_type * p )
262 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
270 static void retire_node( node_type * pNode )
272 assert( pNode != nullptr );
273 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
276 static bool link_node( node_type * pNode, position& pos )
278 assert( pNode != nullptr );
279 link_checker::is_empty( pNode );
281 marked_node_ptr cur(pos.pCur);
282 pNode->m_pNext.store( cur, memory_model::memory_order_release );
283 if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )))
286 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
290 static bool unlink_node( position& pos )
292 assert( pos.pPrev != nullptr );
293 assert( pos.pCur != nullptr );
295 // Mark the node (logical deleting)
296 marked_node_ptr next(pos.pNext, 0);
297 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 ))) {
298 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
299 // CAS may be successful here or in other thread that searching something
300 marked_node_ptr cur(pos.pCur);
301 if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )))
302 retire_node( pos.pCur );
311 template <bool IsConst>
314 friend class MichaelList;
317 value_type * m_pNode;
318 typename gc::Guard m_Guard;
323 typename gc::Guard g;
324 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
326 marked_node_ptr pNext;
328 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
329 g.assign( node_traits::to_value_ptr( pNext.ptr()));
330 } while ( cds_unlikely( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)));
333 m_pNode = m_Guard.assign( g.template get<value_type>());
341 iterator_type( atomic_node_ptr const& pNode )
344 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
346 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr()));
352 if ( cds_likely( p == pNode.load(memory_model::memory_order_acquire)))
358 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
359 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
365 iterator_type( iterator_type const& src )
368 m_pNode = m_Guard.assign( src.m_pNode );
374 value_ptr operator ->() const
379 value_ref operator *() const
381 assert( m_pNode != nullptr );
386 iterator_type& operator ++()
392 iterator_type& operator = (iterator_type const& src)
394 m_pNode = src.m_pNode;
395 m_Guard.assign( m_pNode );
401 void operator ++(int)
408 bool operator ==(iterator_type<C> const& i ) const
410 return m_pNode == i.m_pNode;
413 bool operator !=(iterator_type<C> const& i ) const
415 return m_pNode != i.m_pNode;
421 ///@name Forward iterators (only for debugging purpose)
425 The forward iterator for Michael's list has some features:
426 - it has no post-increment operator
427 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
428 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
429 may be thrown if the limit of guard count per thread is exceeded.
430 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
431 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
432 deleting operations there is no guarantee that you iterate all item in the list.
433 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
435 @warning Use this iterator on the concurrent container for debugging purpose only.
437 The iterator interface:
441 // Default constructor
445 iterator( iterator const& src );
447 // Dereference operator
448 value_type * operator ->() const;
450 // Dereference operator
451 value_type& operator *() const;
453 // Preincrement operator
454 iterator& operator ++();
456 // Assignment operator
457 iterator& operator = (iterator const& src);
459 // Equality operators
460 bool operator ==(iterator const& i ) const;
461 bool operator !=(iterator const& i ) const;
465 typedef iterator_type<false> iterator;
466 /// Const forward iterator
468 For iterator's features and requirements see \ref iterator
470 typedef iterator_type<true> const_iterator;
472 /// Returns a forward iterator addressing the first element in a list
474 For empty list \code begin() == end() \endcode
478 return iterator( m_pHead );
481 /// Returns an iterator that addresses the location succeeding the last element in a list
483 Do not use the value returned by <tt>end</tt> function to access any item.
484 Internally, <tt>end</tt> returning value equals to \p nullptr.
486 The returned value can be used only to control reaching the end of the list.
487 For empty list <tt>begin() == end()</tt>
494 /// Returns a forward const iterator addressing the first element in a list
495 const_iterator cbegin() const
497 return const_iterator( m_pHead );
500 /// Returns a forward const iterator addressing the first element in a list
501 const_iterator begin() const
503 return const_iterator( m_pHead );
506 /// Returns an const iterator that addresses the location succeeding the last element in a list
507 const_iterator end() const
509 return const_iterator();
512 /// Returns an const iterator that addresses the location succeeding the last element in a list
513 const_iterator cend() const
515 return const_iterator();
520 /// Default constructor initializes empty list
524 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
528 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
529 explicit MichaelList( Stat& st )
535 /// Destroys the list object
543 The function inserts \p val into the list if the list does not contain
544 an item with key equal to \p val.
546 Returns \p true if \p val has been linked to the list, \p false otherwise.
548 bool insert( value_type& val )
550 return insert_at( m_pHead, val );
555 This function is intended for derived non-intrusive containers.
557 The function allows to split new item creating into two part:
558 - create item with key only
559 - insert new item into the list
560 - if inserting is success, calls \p f functor to initialize value-field of \p val.
562 The functor signature is:
564 void func( value_type& val );
566 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
567 \p val no any other changes could be made on this list's item by concurrent threads.
568 The user-defined functor is called only if the inserting is success.
570 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
572 template <typename Func>
573 bool insert( value_type& val, Func f )
575 return insert_at( m_pHead, val, f );
580 The operation performs inserting or changing data with lock-free manner.
582 If the item \p val is not found in the list, then \p val is inserted
583 iff \p bInsert is \p true.
584 Otherwise, the functor \p func is called with item found.
585 The functor signature is:
587 void func( bool bNew, value_type& item, value_type& val );
590 - \p bNew - \p true if the item has been inserted, \p false otherwise
591 - \p item - item of the list
592 - \p val - argument \p val passed into the \p update() function
593 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
594 refers to the same thing.
596 The functor may change non-key fields of the \p item; however, \p func must guarantee
597 that during changing no any other modifications could be made on this item by concurrent threads.
599 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
600 \p second is \p true if new item has been added or \p false if the item with that key
603 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
605 template <typename Func>
606 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
608 return update_at( m_pHead, val, func, bInsert );
612 template <typename Func>
613 CDS_DEPRECATED("ensure() is deprecated, use update()")
614 std::pair<bool, bool> ensure( value_type& val, Func func )
616 return update( val, func, true );
620 /// Unlinks the item \p val from the list
622 The function searches the item \p val in the list and unlinks it from the list
623 if it is found and it is equal to \p val.
625 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
626 and deletes the item found. \p %unlink() finds an item by key and deletes it
627 only if \p val is an item of the list, i.e. the pointer to item found
628 is equal to <tt> &val </tt>.
630 \p disposer specified in \p Traits is called for deleted item.
632 The function returns \p true if success and \p false otherwise.
634 bool unlink( value_type& val )
636 return unlink_at( m_pHead, val );
639 /// Deletes the item from the list
640 /** \anchor cds_intrusive_MichaelList_hp_erase_val
641 The function searches an item with key equal to \p key in the list,
642 unlinks it from the list, and returns \p true.
643 If \p key is not found the function return \p false.
645 \p disposer specified in \p Traits is called for deleted item.
647 template <typename Q>
648 bool erase( Q const& key )
650 return erase_at( m_pHead, key, key_comparator());
653 /// Deletes the item from the list using \p pred predicate for searching
655 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
656 but \p pred is used for key comparing.
657 \p Less functor has the interface like \p std::less.
658 \p pred must imply the same element order as the comparator used for building the list.
660 \p disposer specified in \p Traits is called for deleted item.
662 template <typename Q, typename Less>
663 bool erase_with( Q const& key, Less pred )
666 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
669 /// Deletes the item from the list
670 /** \anchor cds_intrusive_MichaelList_hp_erase_func
671 The function searches an item with key equal to \p key in the list,
672 call \p func functor with item found, unlinks it from the list, and returns \p true.
673 The \p Func interface is
676 void operator()( value_type const& item );
679 If \p key is not found the function return \p false, \p func is not called.
681 \p disposer specified in \p Traits is called for deleted item.
683 template <typename Q, typename Func>
684 bool erase( Q const& key, Func func )
686 return erase_at( m_pHead, key, key_comparator(), func );
689 /// Deletes the item from the list using \p pred predicate for searching
691 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
692 but \p pred is used for key comparing.
693 \p Less functor has the interface like \p std::less.
694 \p pred must imply the same element order as the comparator used for building the list.
696 \p disposer specified in \p Traits is called for deleted item.
698 template <typename Q, typename Less, typename Func>
699 bool erase_with( Q const& key, Less pred, Func f )
702 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
705 /// Extracts the item from the list with specified \p key
706 /** \anchor cds_intrusive_MichaelList_hp_extract
707 The function searches an item with key equal to \p key,
708 unlinks it from the list, and returns it as \p guarded_ptr.
709 If \p key is not found returns an empty guarded pointer.
711 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
713 The \ref disposer specified in \p Traits class template parameter is called automatically
714 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
715 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
719 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
723 ord_list::guarded_ptr gp(theList.extract( 5 ));
728 // Destructor of gp releases internal HP guard
732 template <typename Q>
733 guarded_ptr extract( Q const& key )
735 return extract_at( m_pHead, key, key_comparator());
738 /// Extracts the item using compare functor \p pred
740 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
741 but \p pred predicate is used for key comparing.
743 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
745 \p pred must imply the same element order as the comparator used for building the list.
747 template <typename Q, typename Less>
748 guarded_ptr extract_with( Q const& key, Less pred )
751 return extract_at( m_pHead, 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 )
882 return get_at( m_pHead, key, key_comparator());
885 /// Finds the \p key and return the item found
887 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
888 but \p pred is used for comparing the keys.
890 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
892 \p pred must imply the same element order as the comparator used for building the list.
894 template <typename Q, typename Less>
895 guarded_ptr get_with( Q const& key, Less pred )
898 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
903 The function unlink all items from the list.
907 typename gc::Guard guard;
908 marked_node_ptr head;
910 head = m_pHead.load(memory_model::memory_order_relaxed);
912 guard.assign( node_traits::to_value_ptr( *head.ptr()));
913 if ( cds_likely( m_pHead.load(memory_model::memory_order_acquire) == head )) {
914 if ( head.ptr() == nullptr )
916 value_type& val = *node_traits::to_value_ptr( *head.ptr());
922 /// Checks whether the list is empty
925 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
928 /// Returns list's item count
930 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
931 this function always returns 0.
933 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
934 is empty. To check list emptiness use \p empty() method.
938 return m_ItemCounter.value();
941 /// Returns const reference to internal statistics
942 stat const& statistics() const
949 // split-list support
950 bool insert_aux_node( node_type * pNode )
952 return insert_aux_node( m_pHead, pNode );
955 // split-list support
956 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
958 assert( pNode != nullptr );
960 // Hack: convert node_type to value_type.
961 // In principle, auxiliary node can be non-reducible to value_type
962 // We assume that comparator can correctly distinguish aux and regular node.
963 return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
966 bool insert_at( atomic_node_ptr& refHead, value_type& val )
968 node_type * pNode = node_traits::to_node_ptr( val );
972 if ( search( refHead, val, pos, key_comparator())) {
973 m_Stat.onInsertFailed();
977 if ( link_node( pNode, pos )) {
979 m_Stat.onInsertSuccess();
983 m_Stat.onInsertRetry();
987 template <typename Func>
988 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
990 node_type * pNode = node_traits::to_node_ptr( val );
994 if ( search( refHead, val, pos, key_comparator())) {
995 m_Stat.onInsertFailed();
999 typename gc::Guard guard;
1000 guard.assign( &val );
1001 if ( link_node( pNode, pos )) {
1004 m_Stat.onInsertSuccess();
1008 m_Stat.onInsertRetry();
1012 template <typename Func>
1013 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
1017 node_type * pNode = node_traits::to_node_ptr( val );
1019 if ( search( refHead, val, pos, key_comparator())) {
1020 if ( cds_unlikely( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits())) {
1022 m_Stat.onUpdateMarked();
1023 continue; // the node found is marked as deleted
1025 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
1027 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1028 m_Stat.onUpdateExisting();
1029 return std::make_pair( true, false );
1033 m_Stat.onUpdateFailed();
1034 return std::make_pair( false, false );
1037 typename gc::Guard guard;
1038 guard.assign( &val );
1039 if ( link_node( pNode, pos )) {
1041 func( true, val, val );
1042 m_Stat.onUpdateNew();
1043 return std::make_pair( true, true );
1047 m_Stat.onUpdateRetry();
1051 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1056 while ( search( refHead, val, pos, key_comparator())) {
1057 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
1058 if ( unlink_node( pos )) {
1060 m_Stat.onEraseSuccess();
1067 m_Stat.onUpdateFailed();
1071 m_Stat.onEraseRetry();
1074 m_Stat.onEraseFailed();
1078 template <typename Q, typename Compare, typename Func>
1079 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1082 while ( search( refHead, val, pos, cmp )) {
1083 if ( unlink_node( pos )) {
1084 f( *node_traits::to_value_ptr( *pos.pCur ));
1086 m_Stat.onEraseSuccess();
1092 m_Stat.onEraseRetry();
1095 m_Stat.onEraseFailed();
1099 template <typename Q, typename Compare, typename Func>
1100 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1103 return erase_at( refHead, val, cmp, f, pos );
1106 template <typename Q, typename Compare>
1107 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1110 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1113 template <typename Q, typename Compare>
1114 guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1118 while ( search( refHead, val, pos, cmp )) {
1119 if ( unlink_node( pos )) {
1121 m_Stat.onEraseSuccess();
1122 return guarded_ptr( pos.guards.release( position::guard_current_item ));
1126 m_Stat.onEraseRetry();
1129 m_Stat.onEraseFailed();
1130 return guarded_ptr();
1133 template <typename Q, typename Compare>
1134 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1137 if ( search( refHead, val, pos, cmp ) ) {
1138 m_Stat.onFindSuccess();
1142 m_Stat.onFindFailed();
1146 template <typename Q, typename Compare, typename Func>
1147 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1150 if ( search( refHead, val, pos, cmp )) {
1151 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1152 m_Stat.onFindSuccess();
1156 m_Stat.onFindFailed();
1160 template <typename Q, typename Compare>
1161 guarded_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1164 if ( search( refHead, val, pos, cmp )) {
1165 m_Stat.onFindSuccess();
1166 return guarded_ptr( pos.guards.release( position::guard_current_item ));
1169 m_Stat.onFindFailed();
1170 return guarded_ptr();
1178 template <typename Q, typename Compare >
1179 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1181 atomic_node_ptr * pPrev;
1182 marked_node_ptr pNext;
1183 marked_node_ptr pCur;
1191 pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1192 [](marked_node_ptr p) -> value_type *
1194 return node_traits::to_value_ptr( p.ptr());
1198 if ( pCur.ptr() == nullptr ) {
1201 pos.pNext = nullptr;
1205 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1206 [](marked_node_ptr p ) -> value_type *
1208 return node_traits::to_value_ptr( p.ptr());
1210 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr())) {
1215 // pNext contains deletion mark for pCur
1216 if ( pNext.bits() == 1 ) {
1217 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1218 marked_node_ptr cur( pCur.ptr());
1219 if ( cds_unlikely( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
1220 retire_node( pCur.ptr());
1221 m_Stat.onHelpingSuccess();
1225 m_Stat.onHelpingFailed();
1230 assert( pCur.ptr() != nullptr );
1231 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1234 pos.pCur = pCur.ptr();
1235 pos.pNext = pNext.ptr();
1238 pPrev = &( pCur->m_pNext );
1239 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1242 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1247 }} // namespace cds::intrusive
1249 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H