3 #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
4 #define CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
6 #include <cds/intrusive/details/michael_list_base.h>
7 #include <cds/details/make_const_type.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 \p michael_list::node).
23 - \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)
24 or it must have a member of type \p michael_list::node (for \p michael_list::member_hook).
25 - \p Traits - type traits, default is \p michael_list::traits. It is possible to declare option-based
26 list with \p cds::intrusive::michael_list::make_traits metafunction:
27 For example, the following traits-based declaration of \p gc::HP Michael's list
29 #include <cds/intrusive/michael_list_hp.h>
30 // Declare item stored in your list
31 struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
37 // Declare comparator for the item
39 int operator()( item const& i1, item const& i2 ) const
41 return i1.nKey - i2.nKey;
46 struct my_traits: public cds::intrusive::michael_list::traits
48 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
49 typedef my_compare compare;
52 // Declare traits-based list
53 typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits > traits_based_list;
55 is equivalent for the following option-based list
57 #include <cds/intrusive/michael_list_hp.h>
59 // item struct and my_compare are the same
61 // Declare option-based list
62 typedef cds::intrusive::MichaelList< cds::gc::HP, item,
63 typename cds::intrusive::michael_list::make_traits<
64 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
65 ,cds::intrusive::opt::compare< my_compare > // item comparator option
71 There are different specializations of this template for each garbage collecting schema.
72 You should select GC needed and include appropriate .h-file:
73 - for \p gc::HP: <tt> <cds/intrusive/michael_list_hp.h> </tt>
74 - for \p gc::DHP: <tt> <cds/intrusive/michael_list_dhp.h> </tt>
75 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
76 - for \p gc::nogc: <tt> <cds/intrusive/michael_list_nogc.h> </tt>
77 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
79 Then, you should incorporate \p michael_list::node into your struct \p T and provide
80 appropriate \p michael_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
81 define a struct based on \p michael_list::traits.
83 Example for \p gc::DHP and base hook:
85 // Include GC-related Michael's list specialization
86 #include <cds/intrusive/michael_list_dhp.h>
88 // Data stored in Michael's list
89 struct my_data: public cds::intrusive::michael_list::node< cds::gc::DHP >
98 // my_data comparing functor
100 int operator()( const my_data& d1, const my_data& d2 )
102 return d1.strKey.compare( d2.strKey );
105 int operator()( const my_data& d, const std::string& s )
107 return d.strKey.compare(s);
110 int operator()( const std::string& s, const my_data& d )
112 return s.compare( d.strKey );
118 struct my_traits: public cds::intrusive::michael_list::traits
120 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
121 typedef my_data_cmp compare;
125 typedef cds::intrusive::MichaelList< cds::gc::DHP, my_data, my_traits > traits_based_list;
128 Equivalent option-based code:
130 // GC-related specialization
131 #include <cds/intrusive/michael_list_dhp.h>
140 // Declare option-based list
141 typedef cds::intrusive::MichaelList< cds::gc::DHP
143 , typename cds::intrusive::michael_list::make_traits<
144 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
145 ,cds::intrusive::opt::compare< my_data_cmp >
154 #ifdef CDS_DOXYGEN_INVOKED
155 ,class Traits = michael_list::traits
163 typedef T value_type; ///< type of value stored in the list
164 typedef Traits traits; ///< Traits template parameter
166 typedef typename traits::hook hook; ///< hook type
167 typedef typename hook::node_type node_type; ///< node type
169 # ifdef CDS_DOXYGEN_INVOKED
170 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
172 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
175 typedef typename traits::disposer disposer; ///< disposer used
176 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
177 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
179 typedef GC gc ; ///< Garbage collector
180 typedef typename traits::back_off back_off; ///< back-off strategy
181 typedef typename traits::item_counter item_counter; ///< Item counting policy used
182 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
184 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
187 // Rebind traits (split-list support)
188 template <typename... Options>
189 struct rebind_traits {
193 , typename cds::opt::make_options< traits, Options...>::type
199 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
200 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
202 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
204 atomic_node_ptr m_pHead; ///< Head pointer
205 item_counter m_ItemCounter; ///< Item counter
208 /// Position pointer for item search
210 atomic_node_ptr * pPrev ; ///< Previous node
211 node_type * pCur ; ///< Current node
212 node_type * pNext ; ///< Next node
214 typename gc::template GuardArray<3> guards ; ///< Guards array
223 struct clean_disposer {
224 void operator()( value_type * p )
226 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
234 static void retire_node( node_type * pNode )
236 assert( pNode != nullptr );
237 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
240 static bool link_node( node_type * pNode, position& pos )
242 assert( pNode != nullptr );
243 link_checker::is_empty( pNode );
245 marked_node_ptr cur(pos.pCur);
246 pNode->m_pNext.store( cur, memory_model::memory_order_release );
247 return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
250 static bool unlink_node( position& pos )
252 assert( pos.pPrev != nullptr );
253 assert( pos.pCur != nullptr );
255 // Mark the node (logical deleting)
256 marked_node_ptr next(pos.pNext, 0);
257 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
258 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
259 // CAS may be successful here or in other thread that searching something
260 marked_node_ptr cur(pos.pCur);
261 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
262 retire_node( pos.pCur );
271 template <bool IsConst>
274 friend class MichaelList;
277 value_type * m_pNode;
278 typename gc::Guard m_Guard;
283 typename gc::Guard g;
284 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
286 marked_node_ptr pNext;
288 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
289 g.assign( node_traits::to_value_ptr( pNext.ptr() ));
290 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
293 m_pNode = m_Guard.assign( g.template get<value_type>() );
302 iterator_type( atomic_node_ptr const& pNode )
305 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
307 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
313 if ( p == pNode.load(memory_model::memory_order_acquire) )
319 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
320 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
326 iterator_type( iterator_type const& src )
329 m_pNode = m_Guard.assign( src.m_pNode );
335 value_ptr operator ->() const
340 value_ref operator *() const
342 assert( m_pNode != nullptr );
347 iterator_type& operator ++()
353 iterator_type& operator = (iterator_type const& src)
355 m_pNode = src.m_pNode;
356 m_Guard.assign( m_pNode );
362 void operator ++(int)
369 bool operator ==(iterator_type<C> const& i ) const
371 return m_pNode == i.m_pNode;
374 bool operator !=(iterator_type<C> const& i ) const
376 return m_pNode != i.m_pNode;
384 The forward iterator for Michael's list has some features:
385 - it has no post-increment operator
386 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
387 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
388 may be thrown if the limit of guard count per thread is exceeded.
389 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
390 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
391 deleting operations there is no guarantee that you iterate all item in the list.
393 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
394 for debug purpose only.
396 The iterator interface:
400 // Default constructor
404 iterator( iterator const& src );
406 // Dereference operator
407 value_type * operator ->() const;
409 // Dereference operator
410 value_type& operator *() const;
412 // Preincrement operator
413 iterator& operator ++();
415 // Assignment operator
416 iterator& operator = (iterator const& src);
418 // Equality operators
419 bool operator ==(iterator const& i ) const;
420 bool operator !=(iterator const& i ) const;
424 typedef iterator_type<false> iterator;
425 /// Const forward iterator
427 For iterator's features and requirements see \ref iterator
429 typedef iterator_type<true> const_iterator;
431 /// Returns a forward iterator addressing the first element in a list
433 For empty list \code begin() == end() \endcode
437 return iterator( m_pHead );
440 /// Returns an iterator that addresses the location succeeding the last element in a list
442 Do not use the value returned by <tt>end</tt> function to access any item.
443 Internally, <tt>end</tt> returning value equals to \p nullptr.
445 The returned value can be used only to control reaching the end of the list.
446 For empty list <tt>begin() == end()</tt>
453 /// Returns a forward const iterator addressing the first element in a list
454 const_iterator cbegin() const
456 return const_iterator( m_pHead );
459 /// Returns a forward const iterator addressing the first element in a list
460 const_iterator begin() const
462 return const_iterator( m_pHead );
465 /// Returns an const iterator that addresses the location succeeding the last element in a list
466 const_iterator end() const
468 return const_iterator();
471 /// Returns an const iterator that addresses the location succeeding the last element in a list
472 const_iterator cend() const
474 return const_iterator();
478 /// Default constructor initializes empty list
482 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
485 /// Destroys the list object
493 The function inserts \p val into the list if the list does not contain
494 an item with key equal to \p val.
496 Returns \p true if \p val has been linked to the list, \p false otherwise.
498 bool insert( value_type& val )
500 return insert_at( m_pHead, val );
505 This function is intended for derived non-intrusive containers.
507 The function allows to split new item creating into two part:
508 - create item with key only
509 - insert new item into the list
510 - if inserting is success, calls \p f functor to initialize value-field of \p val.
512 The functor signature is:
514 void func( value_type& val );
516 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
517 \p val no any other changes could be made on this list's item by concurrent threads.
518 The user-defined functor is called only if the inserting is success.
520 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
522 template <typename Func>
523 bool insert( value_type& val, Func f )
525 return insert_at( m_pHead, val, f );
530 The operation performs inserting or changing data with lock-free manner.
532 If the item \p val is not found in the list, then \p val is inserted
533 iff \p bInsert is \p true.
534 Otherwise, the functor \p func is called with item found.
535 The functor signature is:
537 void func( bool bNew, value_type& item, value_type& val );
540 - \p bNew - \p true if the item has been inserted, \p false otherwise
541 - \p item - item of the list
542 - \p val - argument \p val passed into the \p update() function
543 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
544 refers to the same thing.
546 The functor may change non-key fields of the \p item; however, \p func must guarantee
547 that during changing no any other modifications could be made on this item by concurrent threads.
549 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
550 \p second is \p true if new item has been added or \p false if the item with \p key
551 already is in the list.
553 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
555 template <typename Func>
556 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
558 return update_at( m_pHead, val, func, bInsert );
562 // Deprecated, use update()
563 template <typename Func>
564 std::pair<bool, bool> ensure( value_type& val, Func func )
566 return update( val, func, true );
570 /// Unlinks the item \p val from the list
572 The function searches the item \p val in the list and unlinks it from the list
573 if it is found and it is equal to \p val.
575 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
576 and deletes the item found. \p %unlink() finds an item by key and deletes it
577 only if \p val is an item of the list, i.e. the pointer to item found
578 is equal to <tt> &val </tt>.
580 The function returns \p true if success and \p false otherwise.
582 bool unlink( value_type& val )
584 return unlink_at( m_pHead, val );
587 /// Deletes the item from the list
588 /** \anchor cds_intrusive_MichaelList_hp_erase_val
589 The function searches an item with key equal to \p key in the list,
590 unlinks it from the list, and returns \p true.
591 If \p key is not found the function return \p false.
593 template <typename Q>
594 bool erase( Q const& key )
596 return erase_at( m_pHead, key, key_comparator() );
599 /// Deletes the item from the list using \p pred predicate for searching
601 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
602 but \p pred is used for key comparing.
603 \p Less functor has the interface like \p std::less.
604 \p pred must imply the same element order as the comparator used for building the list.
606 template <typename Q, typename Less>
607 bool erase_with( Q const& key, Less pred )
610 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
613 /// Deletes the item from the list
614 /** \anchor cds_intrusive_MichaelList_hp_erase_func
615 The function searches an item with key equal to \p key in the list,
616 call \p func functor with item found, unlinks it from the list, and returns \p true.
617 The \p Func interface is
620 void operator()( value_type const& item );
623 If \p key is not found the function return \p false, \p func is not called.
625 template <typename Q, typename Func>
626 bool erase( Q const& key, Func func )
628 return erase_at( m_pHead, key, key_comparator(), func );
631 /// Deletes the item from the list using \p pred predicate for searching
633 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
634 but \p pred is used for key comparing.
635 \p Less functor has the interface like \p std::less.
636 \p pred must imply the same element order as the comparator used for building the list.
638 template <typename Q, typename Less, typename Func>
639 bool erase_with( Q const& key, Less pred, Func f )
642 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
645 /// Extracts the item from the list with specified \p key
646 /** \anchor cds_intrusive_MichaelList_hp_extract
647 The function searches an item with key equal to \p key,
648 unlinks it from the list, and returns it as \p guarded_ptr.
649 If \p key is not found returns an empty guarded pointer.
651 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
653 The \ref disposer specified in \p Traits class template parameter is called automatically
654 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
655 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
659 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
663 ord_list::guarded_ptr gp(theList.extract( 5 ));
668 // Destructor of gp releases internal HP guard
672 template <typename Q>
673 guarded_ptr extract( Q const& key )
676 extract_at( m_pHead, gp.guard(), key, key_comparator() );
680 /// Extracts the item using compare functor \p pred
682 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
683 but \p pred predicate is used for key comparing.
685 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
687 \p pred must imply the same element order as the comparator used for building the list.
689 template <typename Q, typename Less>
690 guarded_ptr extract_with( Q const& key, Less pred )
694 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
698 /// Finds \p key in the list
699 /** \anchor cds_intrusive_MichaelList_hp_find_func
700 The function searches the item with key equal to \p key and calls the functor \p f for item found.
701 The interface of \p Func functor is:
704 void operator()( value_type& item, Q& key );
707 where \p item is the item found, \p key is the <tt>find</tt> function argument.
709 The functor may change non-key fields of \p item. Note that the function is only guarantee
710 that \p item cannot be disposed during functor is executing.
711 The function does not serialize simultaneous access to the \p item. If such access is
712 possible you must provide your own synchronization schema to keep out unsafe item modifications.
714 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
715 may modify both arguments.
717 The function returns \p true if \p val is found, \p false otherwise.
719 template <typename Q, typename Func>
720 bool find( Q& key, Func f )
722 return find_at( m_pHead, key, key_comparator(), f );
725 template <typename Q, typename Func>
726 bool find( Q const& key, Func f )
728 return find_at( m_pHead, key, key_comparator(), f );
732 /// Finds the \p key using \p pred predicate for searching
734 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
735 but \p pred is used for key comparing.
736 \p Less functor has the interface like \p std::less.
737 \p pred must imply the same element order as the comparator used for building the list.
739 template <typename Q, typename Less, typename Func>
740 bool find_with( Q& key, Less pred, Func f )
743 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
746 template <typename Q, typename Less, typename Func>
747 bool find_with( Q const& key, Less pred, Func f )
750 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
755 /** \anchor cds_intrusive_MichaelList_hp_find_val
756 The function searches the item with key equal to \p key
757 and returns \p true if it is found, and \p false otherwise
759 template <typename Q>
760 bool find( Q const& key )
762 return find_at( m_pHead, key, key_comparator() );
765 /// Finds the key \p val using \p pred predicate for searching
767 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
768 but \p pred is used for key comparing.
769 \p Less functor has the interface like \p std::less.
770 \p pred must imply the same element order as the comparator used for building the list.
772 template <typename Q, typename Less>
773 bool find_with( Q const& key, Less pred )
776 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
779 /// Finds the \p key and return the item found
780 /** \anchor cds_intrusive_MichaelList_hp_get
781 The function searches the item with key equal to \p key
782 and returns it as \p guarded_ptr.
783 If \p key is not found the function returns an empty guarded pointer.
785 The \ref disposer specified in \p Traits class template parameter is called
786 by garbage collector \p GC automatically when returned \ref guarded_ptr object
787 will be destroyed or released.
788 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
792 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
796 ord_list::guarded_ptr gp(theList.get( 5 ));
801 // Destructor of guarded_ptr releases internal HP guard
805 Note the compare functor specified for \p Traits template parameter
806 should accept a parameter of type \p Q that can be not the same as \p value_type.
808 template <typename Q>
809 guarded_ptr get( Q const& key )
812 get_at( m_pHead, gp.guard(), key, key_comparator() );
816 /// Finds the \p key and return the item found
818 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
819 but \p pred is used for comparing the keys.
821 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
823 \p pred must imply the same element order as the comparator used for building the list.
825 template <typename Q, typename Less>
826 guarded_ptr get_with( Q const& key, Less pred )
830 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
836 The function unlink all items from the list.
840 typename gc::Guard guard;
841 marked_node_ptr head;
843 head = m_pHead.load(memory_model::memory_order_relaxed);
845 guard.assign( node_traits::to_value_ptr( *head.ptr() ));
846 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
847 if ( head.ptr() == nullptr )
849 value_type& val = *node_traits::to_value_ptr( *head.ptr() );
855 /// Checks whether the list is empty
858 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
861 /// Returns list's item count
863 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
864 this function always returns 0.
866 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
867 is empty. To check list emptyness use \p empty() method.
871 return m_ItemCounter.value();
876 // split-list support
877 bool insert_aux_node( node_type * pNode )
879 return insert_aux_node( m_pHead, pNode );
882 // split-list support
883 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
885 assert( pNode != nullptr );
887 // Hack: convert node_type to value_type.
888 // In principle, auxiliary node can be non-reducible to value_type
889 // We assume that comparator can correctly distinguish aux and regular node.
890 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
893 bool insert_at( atomic_node_ptr& refHead, value_type& val )
895 node_type * pNode = node_traits::to_node_ptr( val );
896 link_checker::is_empty( pNode );
900 if ( search( refHead, val, pos, key_comparator() ) )
903 if ( link_node( pNode, pos ) ) {
909 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
913 template <typename Func>
914 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
916 node_type * pNode = node_traits::to_node_ptr( val );
917 link_checker::is_empty( pNode );
921 if ( search( refHead, val, pos, key_comparator() ) )
924 typename gc::Guard guard;
925 guard.assign( &val );
926 if ( link_node( pNode, pos ) ) {
933 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
937 template <typename Func>
938 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
942 node_type * pNode = node_traits::to_node_ptr( val );
944 if ( search( refHead, val, pos, key_comparator() ) ) {
945 if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
947 continue ; // the node found is marked as deleted
949 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
951 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
952 return std::make_pair( true, false );
956 return std::make_pair( false, false );
958 typename gc::Guard guard;
959 guard.assign( &val );
960 if ( link_node( pNode, pos ) ) {
962 func( true, val, val );
963 return std::make_pair( true, true );
966 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
971 template <typename Func>
972 std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
974 return update_at( refHead, val, func, true );
977 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
982 while ( search( refHead, val, pos, key_comparator() ) ) {
983 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
984 if ( unlink_node( pos ) ) {
997 template <typename Q, typename Compare, typename Func>
998 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1001 while ( search( refHead, val, pos, cmp )) {
1002 if ( unlink_node( pos ) ) {
1003 f( *node_traits::to_value_ptr( *pos.pCur ) );
1013 template <typename Q, typename Compare, typename Func>
1014 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1017 return erase_at( refHead, val, cmp, f, pos );
1020 template <typename Q, typename Compare>
1021 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1024 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1027 template <typename Q, typename Compare>
1028 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1032 while ( search( refHead, val, pos, cmp )) {
1033 if ( unlink_node( pos ) ) {
1034 dest.set( pos.guards.template get<value_type>( position::guard_current_item ) );
1044 template <typename Q, typename Compare>
1045 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1048 return search( refHead, val, pos, cmp );
1051 template <typename Q, typename Compare, typename Func>
1052 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1055 if ( search( refHead, val, pos, cmp )) {
1056 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1062 template <typename Q, typename Compare>
1063 bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1066 if ( search( refHead, val, pos, cmp )) {
1067 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1078 template <typename Q, typename Compare >
1079 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1081 atomic_node_ptr * pPrev;
1082 marked_node_ptr pNext;
1083 marked_node_ptr pCur;
1091 pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1092 [](marked_node_ptr p) -> value_type *
1094 return node_traits::to_value_ptr( p.ptr() );
1098 if ( pCur.ptr() == nullptr ) {
1101 pos.pNext = nullptr;
1105 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1106 [](marked_node_ptr p ) -> value_type *
1108 return node_traits::to_value_ptr( p.ptr() );
1110 if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr() ) {
1115 // pNext contains deletion mark for pCur
1116 if ( pNext.bits() == 1 ) {
1117 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1118 marked_node_ptr cur( pCur.ptr());
1119 if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1120 retire_node( pCur.ptr() );
1128 assert( pCur.ptr() != nullptr );
1129 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1132 pos.pCur = pCur.ptr();
1133 pos.pNext = pNext.ptr();
1136 pPrev = &( pCur->m_pNext );
1137 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1140 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1145 }} // namespace cds::intrusive
1147 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H