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::PTB: \code #include <cds/intrusive/michael_list_ptb.h> \endcode
93 - for gc::HRC: \code #include <cds/intrusive/michael_list_hrc.h> \endcode
94 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
95 - for gc::nogc: \code #include <cds/intrusive/michael_list_nogc.h> \endcode
96 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
98 Then, you should incorporate michael_list::node into your struct \p T and provide
99 appropriate michael_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
100 define a struct based on michael_list::type_traits.
102 Example for gc::PTB and base hook:
104 // Include GC-related Michael's list specialization
105 #include <cds/intrusive/michael_list_ptb.h>
107 // Data stored in Michael's list
108 struct my_data: public cds::intrusive::michael_list::node< cds::gc::PTB >
117 // my_data comparing functor
119 int operator()( const my_data& d1, const my_data& d2 )
121 return d1.strKey.compare( d2.strKey );
124 int operator()( const my_data& d, const std::string& s )
126 return d.strKey.compare(s);
129 int operator()( const std::string& s, const my_data& d )
131 return s.compare( d.strKey );
136 // Declare type_traits
137 struct my_traits: public cds::intrusive::michael_list::type_traits
139 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > > hook;
140 typedef my_data_cmp compare;
144 typedef cds::intrusive::MichaelList< cds::gc::PTB, my_data, my_traits > traits_based_list;
147 Equivalent option-based code:
149 // GC-related specialization
150 #include <cds/intrusive/michael_list_ptb.h>
159 // Declare option-based list
160 typedef cds::intrusive::MichaelList< cds::gc::PTB
162 , typename cds::intrusive::michael_list::make_traits<
163 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
164 ,cds::intrusive::opt::compare< my_data_cmp >
173 #ifdef CDS_DOXYGEN_INVOKED
174 ,class Traits = michael_list::type_traits
182 typedef T value_type ; ///< type of value stored in the list
183 typedef Traits options ; ///< Traits template parameter
185 typedef typename options::hook hook ; ///< hook type
186 typedef typename hook::node_type node_type ; ///< node type
188 # ifdef CDS_DOXYGEN_INVOKED
189 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
191 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
194 typedef typename options::disposer disposer ; ///< disposer used
195 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
196 typedef typename michael_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
198 typedef GC gc ; ///< Garbage collector
199 typedef typename options::back_off back_off ; ///< back-off strategy
200 typedef typename options::item_counter item_counter ; ///< Item counting policy used
201 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
203 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
206 // Rebind options (split-list support)
207 template <typename... Options>
208 struct rebind_options {
212 , typename cds::opt::make_options< options, Options...>::type
218 typedef typename node_type::atomic_marked_ptr atomic_node_ptr ; ///< Atomic node pointer
219 typedef typename node_type::marked_ptr marked_node_ptr ; ///< Node marked pointer
221 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
223 atomic_node_ptr m_pHead ; ///< Head pointer
224 item_counter m_ItemCounter ; ///< Item counter
227 /// Position pointer for item search
229 atomic_node_ptr * pPrev ; ///< Previous node
230 node_type * pCur ; ///< Current node
231 node_type * pNext ; ///< Next node
233 typename gc::template GuardArray<3> guards ; ///< Guards array
242 struct clean_disposer {
243 void operator()( value_type * p )
245 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
254 void retire_node( node_type * pNode )
256 assert( pNode != nullptr );
257 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
260 bool link_node( node_type * pNode, position& pos )
262 assert( pNode != nullptr );
263 link_checker::is_empty( pNode );
265 marked_node_ptr cur(pos.pCur);
266 pNode->m_pNext.store( cur, memory_model::memory_order_relaxed );
267 return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
270 bool unlink_node( position& pos )
272 assert( pos.pPrev != nullptr );
273 assert( pos.pCur != nullptr );
275 // Mark the node (logical deleting)
276 marked_node_ptr next(pos.pNext, 0);
277 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
278 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
279 // CAS may be successful here or in other thread that searching something
280 marked_node_ptr cur(pos.pCur);
281 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
282 retire_node( pos.pCur );
291 template <bool IsConst>
294 friend class MichaelList;
297 value_type * m_pNode;
298 typename gc::Guard m_Guard;
303 typename gc::Guard g;
304 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
306 marked_node_ptr pNext;
308 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
309 g.assign( node_traits::to_value_ptr( pNext.ptr() ));
310 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
313 m_pNode = m_Guard.assign( g.template get<value_type>() );
322 iterator_type( atomic_node_ptr const& pNode )
325 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
327 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
333 if ( p == pNode.load(memory_model::memory_order_acquire) )
339 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
340 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
346 iterator_type( iterator_type const& src )
349 m_pNode = m_Guard.assign( src.m_pNode );
355 value_ptr operator ->() const
360 value_ref operator *() const
362 assert( m_pNode != nullptr );
367 iterator_type& operator ++()
373 iterator_type& operator = (iterator_type const& src)
375 m_pNode = src.m_pNode;
376 m_Guard.assign( m_pNode );
382 void operator ++(int)
389 bool operator ==(iterator_type<C> const& i ) const
391 return m_pNode == i.m_pNode;
394 bool operator !=(iterator_type<C> const& i ) const
396 return m_pNode != i.m_pNode;
404 The forward iterator for Michael's list has some features:
405 - it has no post-increment operator
406 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
407 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
408 may be thrown if a limit of guard count per thread is exceeded.
409 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
410 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
411 deleting operations it is no guarantee that you iterate all item in the list.
413 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
414 for debug purpose only.
416 The iterator interface:
420 // Default constructor
424 iterator( iterator const& src );
426 // Dereference operator
427 value_type * operator ->() const;
429 // Dereference operator
430 value_type& operator *() const;
432 // Preincrement operator
433 iterator& operator ++();
435 // Assignment operator
436 iterator& operator = (iterator const& src);
438 // Equality operators
439 bool operator ==(iterator const& i ) const;
440 bool operator !=(iterator const& i ) const;
444 typedef iterator_type<false> iterator;
445 /// Const forward iterator
447 For iterator's features and requirements see \ref iterator
449 typedef iterator_type<true> const_iterator;
451 /// Returns a forward iterator addressing the first element in a list
453 For empty list \code begin() == end() \endcode
457 return iterator( m_pHead );
460 /// Returns an iterator that addresses the location succeeding the last element in a list
462 Do not use the value returned by <tt>end</tt> function to access any item.
463 Internally, <tt>end</tt> returning value equals to \p nullptr.
465 The returned value can be used only to control reaching the end of the list.
466 For empty list <tt>begin() == end()</tt>
473 /// Returns a forward const iterator addressing the first element in a list
474 const_iterator cbegin()
476 return const_iterator( m_pHead );
479 /// Returns a forward const iterator addressing the first element in a list
480 const_iterator begin() const
482 return const_iterator( m_pHead );
485 /// Returns an const iterator that addresses the location succeeding the last element in a list
486 const_iterator end() const
488 return const_iterator();
491 /// Returns an const iterator that addresses the location succeeding the last element in a list
492 const_iterator cend()
494 return const_iterator();
498 /// Default constructor initializes empty list
502 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
505 /// Destroys the list object
513 The function inserts \p val in the list if the list does not contain
514 an item with key equal to \p val.
516 Returns \p true if \p val is linked into the list, \p false otherwise.
518 bool insert( value_type& val )
520 return insert_at( m_pHead, val );
525 This function is intended for derived non-intrusive containers.
527 The function allows to split new item creating into two part:
528 - create item with key only
529 - insert new item into the list
530 - if inserting is success, calls \p f functor to initialize value-field of \p val.
532 The functor signature is:
534 void func( value_type& val );
536 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
537 \p val no any other changes could be made on this list's item by concurrent threads.
538 The user-defined functor is called only if the inserting is success and may be passed by reference
539 using <tt>boost::ref</tt>.
541 template <typename Func>
542 bool insert( value_type& val, Func f )
544 return insert_at( m_pHead, val, f );
547 /// Ensures that the \p item exists in the list
549 The operation performs inserting or changing data with lock-free manner.
551 If the item \p val not found in the list, then \p val is inserted into the list.
552 Otherwise, the functor \p func is called with item found.
553 The functor signature is:
555 void func( bool bNew, value_type& item, value_type& val );
558 - \p bNew - \p true if the item has been inserted, \p false otherwise
559 - \p item - item of the list
560 - \p val - argument \p val passed into the \p ensure function
561 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
562 refers to the same thing.
564 The functor may change non-key fields of the \p item; however, \p func must guarantee
565 that during changing no any other modifications could be made on this item by concurrent threads.
567 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
569 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
570 \p second is \p true if new item has been added or \p false if the item with \p key
571 already is in the list.
573 template <typename Func>
574 std::pair<bool, bool> ensure( value_type& val, Func func )
576 return ensure_at( m_pHead, val, func );
579 /// Unlinks the item \p val from the list
581 The function searches the item \p val in the list and unlink it from the list
582 if it is found and it is equal to \p val.
584 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
585 and deletes the item found. \p unlink finds an item by key and deletes it
586 only if \p val is an item of that list, i.e. the pointer to item found
587 is equal to <tt> &val </tt>.
589 The function returns \p true if success and \p false otherwise.
591 bool unlink( value_type& val )
593 return unlink_at( m_pHead, val );
596 /// Deletes the item from the list
597 /** \anchor cds_intrusive_MichaelList_hp_erase_val
598 The function searches an item with key equal to \p val in the list,
599 unlinks it from the list, and returns \p true.
600 If the item with the key equal to \p val is not found the function return \p false.
602 template <typename Q>
603 bool erase( Q const& val )
605 return erase_at( m_pHead, val, key_comparator() );
608 /// Deletes the item from the list using \p pred predicate for searching
610 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
611 but \p pred is used for key comparing.
612 \p Less functor has the interface like \p std::less.
613 \p pred must imply the same element order as the comparator used for building the list.
615 template <typename Q, typename Less>
616 bool erase_with( Q const& val, Less pred )
618 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>());
621 /// Deletes the item from the list
622 /** \anchor cds_intrusive_MichaelList_hp_erase_func
623 The function searches an item with key equal to \p val in the list,
624 call \p func functor with item found, unlinks it from the list, and returns \p true.
625 The \p Func interface is
628 void operator()( value_type const& item );
631 The functor may be passed by reference using <tt>boost:ref</tt>
633 If the item with the key equal to \p val is not found the function return \p false.
635 template <typename Q, typename Func>
636 bool erase( Q const& val, Func func )
638 return erase_at( m_pHead, val, key_comparator(), func );
641 /// Deletes the item from the list using \p pred predicate for searching
643 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
644 but \p pred is used for key comparing.
645 \p Less functor has the interface like \p std::less.
646 \p pred must imply the same element order as the comparator used for building the list.
648 template <typename Q, typename Less, typename Func>
649 bool erase_with( Q const& val, Less pred, Func f )
651 return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
654 /// Extracts the item from the list with specified \p key
655 /** \anchor cds_intrusive_MichaelList_hp_extract
656 The function searches an item with key equal to \p key,
657 unlinks it from the list, and returns it in \p dest parameter.
658 If the item with key equal to \p key is not found the function returns \p false.
660 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
662 The \ref disposer specified in \p Traits class template parameter is called automatically
663 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
664 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
668 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
672 ord_list::guarded_ptr gp;
673 theList.extract( gp, 5 );
677 // Destructor of gp releases internal HP guard
681 template <typename Q>
682 bool extract( guarded_ptr& dest, Q const& key )
684 return extract_at( m_pHead, dest.guard(), key, key_comparator() );
687 /// Extracts the item using compare functor \p pred
689 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
690 but \p pred predicate is used for key comparing.
692 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
694 \p pred must imply the same element order as the comparator used for building the list.
696 template <typename Q, typename Less>
697 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
699 return extract_at( m_pHead, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
702 /// Finds the key \p val
703 /** \anchor cds_intrusive_MichaelList_hp_find_func
704 The function searches the item with key equal to \p val and calls the functor \p f for item found.
705 The interface of \p Func functor is:
708 void operator()( value_type& item, Q& val );
711 where \p item is the item found, \p val is the <tt>find</tt> function argument.
713 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
715 The functor may change non-key fields of \p item. Note that the function is only guarantee
716 that \p item cannot be disposed during functor is executing.
717 The function does not serialize simultaneous access to the list \p item. If such access is
718 possible you must provide your own synchronization schema to exclude unsafe item modifications.
720 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
721 may modify both arguments.
723 The function returns \p true if \p val is found, \p false otherwise.
725 template <typename Q, typename Func>
726 bool find( Q& val, Func f )
728 return find_at( m_pHead, val, key_comparator(), f );
731 /// Finds the key \p val using \p pred predicate for searching
733 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
734 but \p pred is used for key comparing.
735 \p Less functor has the interface like \p std::less.
736 \p pred must imply the same element order as the comparator used for building the list.
738 template <typename Q, typename Less, typename Func>
739 bool find_with( Q& val, Less pred, Func f )
741 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
744 /// Finds the key \p val
745 /** \anchor cds_intrusive_MichaelList_hp_find_cfunc
746 The function searches the item with key equal to \p val and calls the functor \p f for item found.
747 The interface of \p Func functor is:
750 void operator()( value_type& item, Q const& val );
753 where \p item is the item found, \p val is the <tt>find</tt> function argument.
755 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
757 The functor may change non-key fields of \p item. Note that the function is only guarantee
758 that \p item cannot be disposed during functor is executing.
759 The function does not serialize simultaneous access to the list \p item. If such access is
760 possible you must provide your own synchronization schema to exclude unsafe item modifications.
762 The function returns \p true if \p val is found, \p false otherwise.
764 template <typename Q, typename Func>
765 bool find( Q const& val, Func f )
767 return find_at( m_pHead, val, key_comparator(), f );
770 /// Finds the key \p val using \p pred predicate for searching
772 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_cfunc "find(Q const&, Func)"
773 but \p pred is used for key comparing.
774 \p Less functor has the interface like \p std::less.
775 \p pred must imply the same element order as the comparator used for building the list.
777 template <typename Q, typename Less, typename Func>
778 bool find_with( Q const& val, Less pred, Func f )
780 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
783 /// Finds the key \p val
784 /** \anchor cds_intrusive_MichaelList_hp_find_val
785 The function searches the item with key equal to \p val
786 and returns \p true if it is found, and \p false otherwise
788 template <typename Q>
789 bool find( Q const & val )
791 return find_at( m_pHead, val, key_comparator() );
794 /// Finds the key \p val using \p pred predicate for searching
796 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
797 but \p pred is used for key comparing.
798 \p Less functor has the interface like \p std::less.
799 \p pred must imply the same element order as the comparator used for building the list.
801 template <typename Q, typename Less>
802 bool find_with( Q const& val, Less pred )
804 return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
807 /// Finds the key \p val and return the item found
808 /** \anchor cds_intrusive_MichaelList_hp_get
809 The function searches the item with key equal to \p val
810 and assigns the item found to guarded pointer \p ptr.
811 The function returns \p true if \p val is found, and \p false otherwise.
812 If \p val is not found the \p ptr parameter is not changed.
814 The \ref disposer specified in \p Traits class template parameter is called
815 by garbage collector \p GC automatically when returned \ref guarded_ptr object
816 will be destroyed or released.
817 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
821 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
825 ord_list::guarded_ptr gp;
826 if ( theList.get( gp, 5 )) {
830 // Destructor of guarded_ptr releases internal HP guard
834 Note the compare functor specified for \p Traits template parameter
835 should accept a parameter of type \p Q that can be not the same as \p value_type.
837 template <typename Q>
838 bool get( guarded_ptr& ptr, Q const& val )
840 return get_at( m_pHead, ptr.guard(), val, key_comparator() );
843 /// Finds the key \p val and return the item found
845 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
846 but \p pred is used for comparing the keys.
848 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
850 \p pred must imply the same element order as the comparator used for building the list.
852 template <typename Q, typename Less>
853 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
855 return get_at( m_pHead, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
860 The function unlink all items from the list.
864 typename gc::Guard guard;
865 marked_node_ptr head;
867 head = m_pHead.load(memory_model::memory_order_relaxed);
869 guard.assign( node_traits::to_value_ptr( *head.ptr() ));
870 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
871 if ( head.ptr() == nullptr )
873 value_type& val = *node_traits::to_value_ptr( *head.ptr() );
879 /// Checks if the list is empty
882 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
885 /// Returns list's item count
887 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
888 this function always returns 0.
890 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
891 is empty. To check list emptyness use \ref empty() method.
895 return m_ItemCounter.value();
900 // split-list support
901 bool insert_aux_node( node_type * pNode )
903 return insert_aux_node( m_pHead, pNode );
906 // split-list support
907 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
909 assert( pNode != nullptr );
911 // Hack: convert node_type to value_type.
912 // In principle, auxiliary node can be non-reducible to value_type
913 // We assume that comparator can correctly distinguish aux and regular node.
914 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
917 bool insert_at( atomic_node_ptr& refHead, value_type& val )
919 node_type * pNode = node_traits::to_node_ptr( val );
920 link_checker::is_empty( pNode );
924 if ( search( refHead, val, pos, key_comparator() ) )
927 if ( link_node( pNode, pos ) ) {
933 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
937 template <typename Func>
938 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
940 node_type * pNode = node_traits::to_node_ptr( val );
941 link_checker::is_empty( pNode );
945 if ( search( refHead, val, pos, key_comparator() ) )
948 typename gc::Guard guard;
949 guard.assign( &val );
950 if ( link_node( pNode, pos ) ) {
951 cds::unref(f)( val );
957 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
961 template <typename Func>
962 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
966 node_type * pNode = node_traits::to_node_ptr( val );
968 if ( search( refHead, val, pos, key_comparator() ) ) {
969 if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
971 continue ; // the node found is marked as deleted
973 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
975 unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
976 return std::make_pair( true, false );
979 typename gc::Guard guard;
980 guard.assign( &val );
981 if ( link_node( pNode, pos ) ) {
983 unref(func)( true, val, val );
984 return std::make_pair( true, true );
987 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
992 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
997 while ( search( refHead, val, pos, key_comparator() ) ) {
998 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
999 if ( unlink_node( pos ) ) {
1012 template <typename Q, typename Compare, typename Func>
1013 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1016 while ( search( refHead, val, pos, cmp )) {
1017 if ( unlink_node( pos ) ) {
1018 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
1028 template <typename Q, typename Compare, typename Func>
1029 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1032 return erase_at( refHead, val, cmp, f, pos );
1035 template <typename Q, typename Compare>
1036 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1039 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1042 template <typename Q, typename Compare>
1043 bool extract_at( atomic_node_ptr& refHead, typename gc::Guard& dest, Q const& val, Compare cmp )
1047 while ( search( refHead, val, pos, cmp )) {
1048 if ( unlink_node( pos ) ) {
1049 dest.assign( pos.guards.template get<value_type>( position::guard_current_item ) );
1059 template <typename Q, typename Compare>
1060 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1063 return search( refHead, val, pos, cmp );
1066 template <typename Q, typename Compare, typename Func>
1067 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1070 if ( search( refHead, val, pos, cmp )) {
1071 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
1077 template <typename Q, typename Compare>
1078 bool get_at( atomic_node_ptr& refHead, typename gc::Guard& guard, Q const& val, Compare cmp )
1081 if ( search( refHead, val, pos, cmp )) {
1082 guard.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1093 template <typename Q, typename Compare >
1094 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1096 atomic_node_ptr * pPrev;
1097 marked_node_ptr pNext;
1098 marked_node_ptr pCur;
1106 pCur = pPrev->load(memory_model::memory_order_relaxed);
1107 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1108 if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1112 if ( pCur.ptr() == nullptr ) {
1114 pos.pCur = pCur.ptr();
1115 pos.pNext = pNext.ptr();
1119 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1120 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1121 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
1126 if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
1131 // pNext contains deletion mark for pCur
1132 if ( pNext.bits() == 1 ) {
1133 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1134 marked_node_ptr cur( pCur.ptr());
1135 if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1136 retire_node( pCur.ptr() );
1144 assert( pCur.ptr() != nullptr );
1145 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1148 pos.pCur = pCur.ptr();
1149 pos.pNext = pNext.ptr();
1152 pPrev = &( pCur->m_pNext );
1153 pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1156 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1161 }} // namespace cds::intrusive
1163 #endif // #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H