3 #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H
4 #define __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/gc/guarded_ptr.h>
9 namespace cds { namespace intrusive {
11 /// Michael's lock-free ordered single-linked list
12 /** @ingroup cds_intrusive_list
13 \anchor cds_intrusive_MichaelList_hp
15 Usually, ordered single-linked list is used as a building block for the hash table implementation.
16 The complexity of searching is <tt>O(N)</tt>.
19 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
22 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see michael_list::node).
23 - \p T - type to be stored in the list. The type must be based on michael_list::node (for michael_list::base_hook)
24 or it must have a member of type michael_list::node (for michael_list::member_hook).
25 - \p Traits - type traits. See michael_list::type_traits for explanation.
27 It is possible to declare option-based list with cds::intrusive::michael_list::make_traits metafunction istead of \p Traits template
30 Template argument list \p Options of cds::intrusive::michael_list::make_traits metafunction are:
31 - opt::hook - hook used. Possible values are: michael_list::base_hook, michael_list::member_hook, michael_list::traits_hook.
32 If the option is not specified, <tt>michael_list::base_hook<></tt> and gc::HP is used.
33 - opt::compare - key comparison functor. No default functor is provided.
34 If the option is not specified, the opt::less is used.
35 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
36 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
37 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
38 of GC schema the disposer may be called asynchronously.
39 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
40 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
41 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
42 or opt::v::sequential_consistent (sequentially consisnent memory model).
44 For example, the following traits-based declaration of gc::HP Michael's list
46 #include <cds/intrusive/michael_list_hp.h>
47 // Declare item stored in your list
48 struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
54 // Declare comparator for the item
56 int operator()( item const& i1, item const& i2 ) const
58 return i1.nKey - i2.nKey;
62 // Declare type_traits
63 struct my_traits: public cds::intrusive::michael_list::type_traits
65 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
66 typedef my_compare compare;
69 // Declare traits-based list
70 typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits > traits_based_list;
73 is equivalent for the following option-based list
75 #include <cds/intrusive/michael_list_hp.h>
77 // item struct and my_compare are the same
79 // Declare option-based list
80 typedef cds::intrusive::MichaelList< cds::gc::HP, item,
81 typename cds::intrusive::michael_list::make_traits<
82 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
83 ,cds::intrusive::opt::compare< my_compare > // item comparator option
89 There are different specializations of this template for each garbage collecting schema used.
90 You should select GC needed and include appropriate .h-file:
91 - for gc::HP: \code #include <cds/intrusive/michael_list_hp.h> \endcode
92 - for gc::DHP: \code #include <cds/intrusive/michael_list_dhp.h> \endcode
93 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
94 - for gc::nogc: \code #include <cds/intrusive/michael_list_nogc.h> \endcode
95 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
97 Then, you should incorporate michael_list::node into your struct \p T and provide
98 appropriate michael_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
99 define a struct based on michael_list::type_traits.
101 Example for gc::PTB and base hook:
103 // Include GC-related Michael's list specialization
104 #include <cds/intrusive/michael_list_dhp.h>
106 // Data stored in Michael's list
107 struct my_data: public cds::intrusive::michael_list::node< cds::gc::PTB >
116 // my_data comparing functor
118 int operator()( const my_data& d1, const my_data& d2 )
120 return d1.strKey.compare( d2.strKey );
123 int operator()( const my_data& d, const std::string& s )
125 return d.strKey.compare(s);
128 int operator()( const std::string& s, const my_data& d )
130 return s.compare( d.strKey );
135 // Declare type_traits
136 struct my_traits: public cds::intrusive::michael_list::type_traits
138 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > > hook;
139 typedef my_data_cmp compare;
143 typedef cds::intrusive::MichaelList< cds::gc::PTB, my_data, my_traits > traits_based_list;
146 Equivalent option-based code:
148 // GC-related specialization
149 #include <cds/intrusive/michael_list_dhp.h>
158 // Declare option-based list
159 typedef cds::intrusive::MichaelList< cds::gc::PTB
161 , typename cds::intrusive::michael_list::make_traits<
162 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
163 ,cds::intrusive::opt::compare< my_data_cmp >
172 #ifdef CDS_DOXYGEN_INVOKED
173 ,class Traits = michael_list::type_traits
181 typedef T value_type ; ///< type of value stored in the list
182 typedef Traits options ; ///< Traits template parameter
184 typedef typename options::hook hook ; ///< hook type
185 typedef typename hook::node_type node_type ; ///< node type
187 # ifdef CDS_DOXYGEN_INVOKED
188 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
190 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
193 typedef typename options::disposer disposer ; ///< disposer used
194 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
195 typedef typename michael_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
197 typedef GC gc ; ///< Garbage collector
198 typedef typename options::back_off back_off ; ///< back-off strategy
199 typedef typename options::item_counter item_counter ; ///< Item counting policy used
200 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
202 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
205 // Rebind options (split-list support)
206 template <typename... Options>
207 struct rebind_options {
211 , typename cds::opt::make_options< options, Options...>::type
217 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
218 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
220 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
222 atomic_node_ptr m_pHead ; ///< Head pointer
223 item_counter m_ItemCounter ; ///< Item counter
226 /// Position pointer for item search
228 atomic_node_ptr * pPrev ; ///< Previous node
229 node_type * pCur ; ///< Current node
230 node_type * pNext ; ///< Next node
232 typename gc::template GuardArray<3> guards ; ///< Guards array
241 struct clean_disposer {
242 void operator()( value_type * p )
244 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
253 void retire_node( node_type * pNode )
255 assert( pNode != nullptr );
256 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
259 bool link_node( node_type * pNode, position& pos )
261 assert( pNode != nullptr );
262 link_checker::is_empty( pNode );
264 marked_node_ptr cur(pos.pCur);
265 pNode->m_pNext.store( cur, memory_model::memory_order_relaxed );
266 return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
269 bool unlink_node( position& pos )
271 assert( pos.pPrev != nullptr );
272 assert( pos.pCur != nullptr );
274 // Mark the node (logical deleting)
275 marked_node_ptr next(pos.pNext, 0);
276 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
277 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
278 // CAS may be successful here or in other thread that searching something
279 marked_node_ptr cur(pos.pCur);
280 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
281 retire_node( pos.pCur );
290 template <bool IsConst>
293 friend class MichaelList;
296 value_type * m_pNode;
297 typename gc::Guard m_Guard;
302 typename gc::Guard g;
303 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
305 marked_node_ptr pNext;
307 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
308 g.assign( node_traits::to_value_ptr( pNext.ptr() ));
309 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
312 m_pNode = m_Guard.assign( g.template get<value_type>() );
321 iterator_type( atomic_node_ptr const& pNode )
324 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
326 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
332 if ( p == pNode.load(memory_model::memory_order_acquire) )
338 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
339 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
345 iterator_type( iterator_type const& src )
348 m_pNode = m_Guard.assign( src.m_pNode );
354 value_ptr operator ->() const
359 value_ref operator *() const
361 assert( m_pNode != nullptr );
366 iterator_type& operator ++()
372 iterator_type& operator = (iterator_type const& src)
374 m_pNode = src.m_pNode;
375 m_Guard.assign( m_pNode );
381 void operator ++(int)
388 bool operator ==(iterator_type<C> const& i ) const
390 return m_pNode == i.m_pNode;
393 bool operator !=(iterator_type<C> const& i ) const
395 return m_pNode != i.m_pNode;
403 The forward iterator for Michael's list has some features:
404 - it has no post-increment operator
405 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
406 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
407 may be thrown if a limit of guard count per thread is exceeded.
408 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
409 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
410 deleting operations it is no guarantee that you iterate all item in the list.
412 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
413 for debug purpose only.
415 The iterator interface:
419 // Default constructor
423 iterator( iterator const& src );
425 // Dereference operator
426 value_type * operator ->() const;
428 // Dereference operator
429 value_type& operator *() const;
431 // Preincrement operator
432 iterator& operator ++();
434 // Assignment operator
435 iterator& operator = (iterator const& src);
437 // Equality operators
438 bool operator ==(iterator const& i ) const;
439 bool operator !=(iterator const& i ) const;
443 typedef iterator_type<false> iterator;
444 /// Const forward iterator
446 For iterator's features and requirements see \ref iterator
448 typedef iterator_type<true> const_iterator;
450 /// Returns a forward iterator addressing the first element in a list
452 For empty list \code begin() == end() \endcode
456 return iterator( m_pHead );
459 /// Returns an iterator that addresses the location succeeding the last element in a list
461 Do not use the value returned by <tt>end</tt> function to access any item.
462 Internally, <tt>end</tt> returning value equals to \p nullptr.
464 The returned value can be used only to control reaching the end of the list.
465 For empty list <tt>begin() == end()</tt>
472 /// Returns a forward const iterator addressing the first element in a list
473 const_iterator cbegin()
475 return const_iterator( m_pHead );
478 /// Returns a forward const iterator addressing the first element in a list
479 const_iterator begin() const
481 return const_iterator( m_pHead );
484 /// Returns an const iterator that addresses the location succeeding the last element in a list
485 const_iterator end() const
487 return const_iterator();
490 /// Returns an const iterator that addresses the location succeeding the last element in a list
491 const_iterator cend()
493 return const_iterator();
497 /// Default constructor initializes empty list
501 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
504 /// Destroys the list object
512 The function inserts \p val in the list if the list does not contain
513 an item with key equal to \p val.
515 Returns \p true if \p val is linked into the list, \p false otherwise.
517 bool insert( value_type& val )
519 return insert_at( m_pHead, val );
524 This function is intended for derived non-intrusive containers.
526 The function allows to split new item creating into two part:
527 - create item with key only
528 - insert new item into the list
529 - if inserting is success, calls \p f functor to initialize value-field of \p val.
531 The functor signature is:
533 void func( value_type& val );
535 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
536 \p val no any other changes could be made on this list's item by concurrent threads.
537 The user-defined functor is called only if the inserting is success and may be passed by reference
540 template <typename Func>
541 bool insert( value_type& val, Func f )
543 return insert_at( m_pHead, val, f );
546 /// Ensures that the \p item exists in the list
548 The operation performs inserting or changing data with lock-free manner.
550 If the item \p val not found in the list, then \p val is inserted into the list.
551 Otherwise, the functor \p func is called with item found.
552 The functor signature is:
554 void func( bool bNew, value_type& item, value_type& val );
557 - \p bNew - \p true if the item has been inserted, \p false otherwise
558 - \p item - item of the list
559 - \p val - argument \p val passed into the \p ensure function
560 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
561 refers to the same thing.
563 The functor may change non-key fields of the \p item; however, \p func must guarantee
564 that during changing no any other modifications could be made on this item by concurrent threads.
566 You may pass \p func argument by reference using \p std::ref.
568 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
569 \p second is \p true if new item has been added or \p false if the item with \p key
570 already is in the list.
572 template <typename Func>
573 std::pair<bool, bool> ensure( value_type& val, Func func )
575 return ensure_at( m_pHead, val, func );
578 /// Unlinks the item \p val from the list
580 The function searches the item \p val in the list and unlink it from the list
581 if it is found and it is equal to \p val.
583 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
584 and deletes the item found. \p unlink finds an item by key and deletes it
585 only if \p val is an item of that list, i.e. the pointer to item found
586 is equal to <tt> &val </tt>.
588 The function returns \p true if success and \p false otherwise.
590 bool unlink( value_type& val )
592 return unlink_at( m_pHead, val );
595 /// Deletes the item from the list
596 /** \anchor cds_intrusive_MichaelList_hp_erase_val
597 The function searches an item with key equal to \p val in the list,
598 unlinks it from the list, and returns \p true.
599 If the item with the key equal to \p val is not found the function return \p false.
601 template <typename Q>
602 bool erase( Q const& val )
604 return erase_at( m_pHead, val, key_comparator() );
607 /// Deletes the item from the list using \p pred predicate for searching
609 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
610 but \p pred is used for key comparing.
611 \p Less functor has the interface like \p std::less.
612 \p pred must imply the same element order as the comparator used for building the list.
614 template <typename Q, typename Less>
615 bool erase_with( Q const& val, Less pred )
617 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>());
620 /// Deletes the item from the list
621 /** \anchor cds_intrusive_MichaelList_hp_erase_func
622 The function searches an item with key equal to \p val in the list,
623 call \p func functor with item found, unlinks it from the list, and returns \p true.
624 The \p Func interface is
627 void operator()( value_type const& item );
630 The functor may be passed by reference using <tt>boost:ref</tt>
632 If the item with the key equal to \p val is not found the function return \p false.
634 template <typename Q, typename Func>
635 bool erase( Q const& val, Func func )
637 return erase_at( m_pHead, val, key_comparator(), func );
640 /// Deletes the item from the list using \p pred predicate for searching
642 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
643 but \p pred is used for key comparing.
644 \p Less functor has the interface like \p std::less.
645 \p pred must imply the same element order as the comparator used for building the list.
647 template <typename Q, typename Less, typename Func>
648 bool erase_with( Q const& val, Less pred, Func f )
650 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
653 /// Extracts the item from the list with specified \p key
654 /** \anchor cds_intrusive_MichaelList_hp_extract
655 The function searches an item with key equal to \p key,
656 unlinks it from the list, and returns it in \p dest parameter.
657 If the item with key equal to \p key is not found the function returns \p false.
659 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
661 The \ref disposer specified in \p Traits class template parameter is called automatically
662 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
663 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
667 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
671 ord_list::guarded_ptr gp;
672 theList.extract( gp, 5 );
676 // Destructor of gp releases internal HP guard
680 template <typename Q>
681 bool extract( guarded_ptr& dest, Q const& key )
683 return extract_at( m_pHead, dest.guard(), key, key_comparator() );
686 /// Extracts the item using compare functor \p pred
688 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
689 but \p pred predicate is used for key comparing.
691 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
693 \p pred must imply the same element order as the comparator used for building the list.
695 template <typename Q, typename Less>
696 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
698 return extract_at( m_pHead, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
701 /// Finds the key \p val
702 /** \anchor cds_intrusive_MichaelList_hp_find_func
703 The function searches the item with key equal to \p val and calls the functor \p f for item found.
704 The interface of \p Func functor is:
707 void operator()( value_type& item, Q& val );
710 where \p item is the item found, \p val is the <tt>find</tt> function argument.
712 You may pass \p f argument by reference using \p std::ref.
714 The functor may change non-key fields of \p item. Note that the function is only guarantee
715 that \p item cannot be disposed during functor is executing.
716 The function does not serialize simultaneous access to the list \p item. If such access is
717 possible you must provide your own synchronization schema to exclude unsafe item modifications.
719 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
720 may modify both arguments.
722 The function returns \p true if \p val is found, \p false otherwise.
724 template <typename Q, typename Func>
725 bool find( Q& val, Func f )
727 return find_at( m_pHead, val, key_comparator(), f );
730 /// Finds the key \p val using \p pred predicate for searching
732 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
733 but \p pred is used for key comparing.
734 \p Less functor has the interface like \p std::less.
735 \p pred must imply the same element order as the comparator used for building the list.
737 template <typename Q, typename Less, typename Func>
738 bool find_with( Q& val, Less pred, Func f )
740 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
743 /// Finds the key \p val
744 /** \anchor cds_intrusive_MichaelList_hp_find_cfunc
745 The function searches the item with key equal to \p val and calls the functor \p f for item found.
746 The interface of \p Func functor is:
749 void operator()( value_type& item, Q const& val );
752 where \p item is the item found, \p val is the <tt>find</tt> function argument.
754 You may pass \p f argument by reference using \p std::ref.
756 The functor may change non-key fields of \p item. Note that the function is only guarantee
757 that \p item cannot be disposed during functor is executing.
758 The function does not serialize simultaneous access to the list \p item. If such access is
759 possible you must provide your own synchronization schema to exclude unsafe item modifications.
761 The function returns \p true if \p val is found, \p false otherwise.
763 template <typename Q, typename Func>
764 bool find( Q const& val, Func f )
766 return find_at( m_pHead, val, key_comparator(), f );
769 /// Finds the key \p val using \p pred predicate for searching
771 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_cfunc "find(Q const&, Func)"
772 but \p pred is used for key comparing.
773 \p Less functor has the interface like \p std::less.
774 \p pred must imply the same element order as the comparator used for building the list.
776 template <typename Q, typename Less, typename Func>
777 bool find_with( Q const& val, Less pred, Func f )
779 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
782 /// Finds the key \p val
783 /** \anchor cds_intrusive_MichaelList_hp_find_val
784 The function searches the item with key equal to \p val
785 and returns \p true if it is found, and \p false otherwise
787 template <typename Q>
788 bool find( Q const & val )
790 return find_at( m_pHead, val, key_comparator() );
793 /// Finds the key \p val using \p pred predicate for searching
795 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
796 but \p pred is used for key comparing.
797 \p Less functor has the interface like \p std::less.
798 \p pred must imply the same element order as the comparator used for building the list.
800 template <typename Q, typename Less>
801 bool find_with( Q const& val, Less pred )
803 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
806 /// Finds the key \p val and return the item found
807 /** \anchor cds_intrusive_MichaelList_hp_get
808 The function searches the item with key equal to \p val
809 and assigns the item found to guarded pointer \p ptr.
810 The function returns \p true if \p val is found, and \p false otherwise.
811 If \p val is not found the \p ptr parameter is not changed.
813 The \ref disposer specified in \p Traits class template parameter is called
814 by garbage collector \p GC automatically when returned \ref guarded_ptr object
815 will be destroyed or released.
816 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
820 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
824 ord_list::guarded_ptr gp;
825 if ( theList.get( gp, 5 )) {
829 // Destructor of guarded_ptr releases internal HP guard
833 Note the compare functor specified for \p Traits template parameter
834 should accept a parameter of type \p Q that can be not the same as \p value_type.
836 template <typename Q>
837 bool get( guarded_ptr& ptr, Q const& val )
839 return get_at( m_pHead, ptr.guard(), val, key_comparator() );
842 /// Finds the key \p val and return the item found
844 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
845 but \p pred is used for comparing the keys.
847 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
849 \p pred must imply the same element order as the comparator used for building the list.
851 template <typename Q, typename Less>
852 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
854 return get_at( m_pHead, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
859 The function unlink all items from the list.
863 typename gc::Guard guard;
864 marked_node_ptr head;
866 head = m_pHead.load(memory_model::memory_order_relaxed);
868 guard.assign( node_traits::to_value_ptr( *head.ptr() ));
869 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
870 if ( head.ptr() == nullptr )
872 value_type& val = *node_traits::to_value_ptr( *head.ptr() );
878 /// Checks if the list is empty
881 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
884 /// Returns list's item count
886 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
887 this function always returns 0.
889 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
890 is empty. To check list emptyness use \ref empty() method.
894 return m_ItemCounter.value();
899 // split-list support
900 bool insert_aux_node( node_type * pNode )
902 return insert_aux_node( m_pHead, pNode );
905 // split-list support
906 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
908 assert( pNode != nullptr );
910 // Hack: convert node_type to value_type.
911 // In principle, auxiliary node can be non-reducible to value_type
912 // We assume that comparator can correctly distinguish aux and regular node.
913 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
916 bool insert_at( atomic_node_ptr& refHead, value_type& val )
918 node_type * pNode = node_traits::to_node_ptr( val );
919 link_checker::is_empty( pNode );
923 if ( search( refHead, val, pos, key_comparator() ) )
926 if ( link_node( pNode, pos ) ) {
932 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
936 template <typename Func>
937 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
939 node_type * pNode = node_traits::to_node_ptr( val );
940 link_checker::is_empty( pNode );
944 if ( search( refHead, val, pos, key_comparator() ) )
947 typename gc::Guard guard;
948 guard.assign( &val );
949 if ( link_node( pNode, pos ) ) {
956 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
960 template <typename Func>
961 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
965 node_type * pNode = node_traits::to_node_ptr( val );
967 if ( search( refHead, val, pos, key_comparator() ) ) {
968 if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
970 continue ; // the node found is marked as deleted
972 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
974 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
975 return std::make_pair( true, false );
978 typename gc::Guard guard;
979 guard.assign( &val );
980 if ( link_node( pNode, pos ) ) {
982 func( true, val, val );
983 return std::make_pair( true, true );
986 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
991 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
996 while ( search( refHead, val, pos, key_comparator() ) ) {
997 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
998 if ( unlink_node( pos ) ) {
1011 template <typename Q, typename Compare, typename Func>
1012 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1015 while ( search( refHead, val, pos, cmp )) {
1016 if ( unlink_node( pos ) ) {
1017 f( *node_traits::to_value_ptr( *pos.pCur ) );
1027 template <typename Q, typename Compare, typename Func>
1028 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1031 return erase_at( refHead, val, cmp, f, pos );
1034 template <typename Q, typename Compare>
1035 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1038 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1041 template <typename Q, typename Compare>
1042 bool extract_at( atomic_node_ptr& refHead, typename gc::Guard& dest, Q const& val, Compare cmp )
1046 while ( search( refHead, val, pos, cmp )) {
1047 if ( unlink_node( pos ) ) {
1048 dest.assign( pos.guards.template get<value_type>( position::guard_current_item ) );
1058 template <typename Q, typename Compare>
1059 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1062 return search( refHead, val, pos, cmp );
1065 template <typename Q, typename Compare, typename Func>
1066 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1069 if ( search( refHead, val, pos, cmp )) {
1070 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1076 template <typename Q, typename Compare>
1077 bool get_at( atomic_node_ptr& refHead, typename gc::Guard& guard, Q const& val, Compare cmp )
1080 if ( search( refHead, val, pos, cmp )) {
1081 guard.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1092 template <typename Q, typename Compare >
1093 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1095 atomic_node_ptr * pPrev;
1096 marked_node_ptr pNext;
1097 marked_node_ptr pCur;
1105 pCur = pPrev->load(memory_model::memory_order_relaxed);
1106 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1107 if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1111 if ( pCur.ptr() == nullptr ) {
1113 pos.pCur = pCur.ptr();
1114 pos.pNext = pNext.ptr();
1118 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1119 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1120 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
1125 if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
1130 // pNext contains deletion mark for pCur
1131 if ( pNext.bits() == 1 ) {
1132 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1133 marked_node_ptr cur( pCur.ptr());
1134 if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1135 retire_node( pCur.ptr() );
1143 assert( pCur.ptr() != nullptr );
1144 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1147 pos.pCur = pCur.ptr();
1148 pos.pNext = pNext.ptr();
1151 pPrev = &( pCur->m_pNext );
1152 pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1155 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1160 }} // namespace cds::intrusive
1162 #endif // #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H