2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H
34 #include <cds/intrusive/details/michael_list_base.h>
35 #include <cds/details/make_const_type.h>
37 namespace cds { namespace intrusive {
39 /// Michael's lock-free ordered single-linked list
40 /** @ingroup cds_intrusive_list
41 \anchor cds_intrusive_MichaelList_hp
43 Usually, ordered single-linked list is used as a building block for the hash table implementation.
44 The complexity of searching is <tt>O(N)</tt>.
47 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
50 - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see \p michael_list::node).
51 - \p T - type to be stored in the list. The type must be based on \p michael_list::node (for \p michael_list::base_hook)
52 or it must have a member of type \p michael_list::node (for \p michael_list::member_hook).
53 - \p Traits - type traits, default is \p michael_list::traits. It is possible to declare option-based
54 list with \p cds::intrusive::michael_list::make_traits metafunction:
55 For example, the following traits-based declaration of \p gc::HP Michael's list
57 #include <cds/intrusive/michael_list_hp.h>
58 // Declare item stored in your list
59 struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
65 // Declare comparator for the item
67 int operator()( item const& i1, item const& i2 ) const
69 return i1.nKey - i2.nKey;
74 struct my_traits: public cds::intrusive::michael_list::traits
76 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > hook;
77 typedef my_compare compare;
80 // Declare traits-based list
81 typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits > traits_based_list;
83 is equivalent for the following option-based list
85 #include <cds/intrusive/michael_list_hp.h>
87 // item struct and my_compare are the same
89 // Declare option-based list
90 typedef cds::intrusive::MichaelList< cds::gc::HP, item,
91 typename cds::intrusive::michael_list::make_traits<
92 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > > // hook option
93 ,cds::intrusive::opt::compare< my_compare > // item comparator option
99 There are different specializations of this template for each garbage collecting schema.
100 You should select GC needed and include appropriate .h-file:
101 - for \p gc::HP: <tt> <cds/intrusive/michael_list_hp.h> </tt>
102 - for \p gc::DHP: <tt> <cds/intrusive/michael_list_dhp.h> </tt>
103 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
104 - for \p gc::nogc: <tt> <cds/intrusive/michael_list_nogc.h> </tt>
105 See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
107 Then, you should incorporate \p michael_list::node into your struct \p T and provide
108 appropriate \p michael_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
109 define a struct based on \p michael_list::traits.
111 Example for \p gc::DHP and base hook:
113 // Include GC-related Michael's list specialization
114 #include <cds/intrusive/michael_list_dhp.h>
116 // Data stored in Michael's list
117 struct my_data: public cds::intrusive::michael_list::node< cds::gc::DHP >
126 // my_data comparing functor
128 int operator()( const my_data& d1, const my_data& d2 )
130 return d1.strKey.compare( d2.strKey );
133 int operator()( const my_data& d, const std::string& s )
135 return d.strKey.compare(s);
138 int operator()( const std::string& s, const my_data& d )
140 return s.compare( d.strKey );
146 struct my_traits: public cds::intrusive::michael_list::traits
148 typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > hook;
149 typedef my_data_cmp compare;
153 typedef cds::intrusive::MichaelList< cds::gc::DHP, my_data, my_traits > traits_based_list;
156 Equivalent option-based code:
158 // GC-related specialization
159 #include <cds/intrusive/michael_list_dhp.h>
168 // Declare option-based list
169 typedef cds::intrusive::MichaelList< cds::gc::DHP
171 , typename cds::intrusive::michael_list::make_traits<
172 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
173 ,cds::intrusive::opt::compare< my_data_cmp >
182 #ifdef CDS_DOXYGEN_INVOKED
183 ,class Traits = michael_list::traits
191 typedef T value_type; ///< type of value stored in the list
192 typedef Traits traits; ///< Traits template parameter
194 typedef typename traits::hook hook; ///< hook type
195 typedef typename hook::node_type node_type; ///< node type
197 # ifdef CDS_DOXYGEN_INVOKED
198 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
200 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
203 typedef typename traits::disposer disposer; ///< disposer used
204 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
205 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
207 typedef GC gc ; ///< Garbage collector
208 typedef typename traits::back_off back_off; ///< back-off strategy
209 typedef typename traits::item_counter item_counter; ///< Item counting policy used
210 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
212 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
215 // Rebind traits (split-list support)
216 template <typename... Options>
217 struct rebind_traits {
221 , typename cds::opt::make_options< traits, Options...>::type
227 typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
228 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
230 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
232 atomic_node_ptr m_pHead; ///< Head pointer
233 item_counter m_ItemCounter; ///< Item counter
236 /// Position pointer for item search
238 atomic_node_ptr * pPrev ; ///< Previous node
239 node_type * pCur ; ///< Current node
240 node_type * pNext ; ///< Next node
242 typename gc::template GuardArray<3> guards ; ///< Guards array
251 struct clean_disposer {
252 void operator()( value_type * p )
254 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
262 static void retire_node( node_type * pNode )
264 assert( pNode != nullptr );
265 gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
268 static bool link_node( node_type * pNode, position& pos )
270 assert( pNode != nullptr );
271 link_checker::is_empty( pNode );
273 marked_node_ptr cur(pos.pCur);
274 pNode->m_pNext.store( cur, memory_model::memory_order_release );
275 return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
278 static bool unlink_node( position& pos )
280 assert( pos.pPrev != nullptr );
281 assert( pos.pCur != nullptr );
283 // Mark the node (logical deleting)
284 marked_node_ptr next(pos.pNext, 0);
285 if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
286 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
287 // CAS may be successful here or in other thread that searching something
288 marked_node_ptr cur(pos.pCur);
289 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
290 retire_node( pos.pCur );
299 template <bool IsConst>
302 friend class MichaelList;
305 value_type * m_pNode;
306 typename gc::Guard m_Guard;
311 typename gc::Guard g;
312 node_type * pCur = node_traits::to_node_ptr( *m_pNode );
314 marked_node_ptr pNext;
316 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
317 g.assign( node_traits::to_value_ptr( pNext.ptr()));
318 } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire));
321 m_pNode = m_Guard.assign( g.template get<value_type>());
329 iterator_type( atomic_node_ptr const& pNode )
332 marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
334 m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr()));
340 if ( p == pNode.load(memory_model::memory_order_acquire))
346 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
347 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
353 iterator_type( iterator_type const& src )
356 m_pNode = m_Guard.assign( src.m_pNode );
362 value_ptr operator ->() const
367 value_ref operator *() const
369 assert( m_pNode != nullptr );
374 iterator_type& operator ++()
380 iterator_type& operator = (iterator_type const& src)
382 m_pNode = src.m_pNode;
383 m_Guard.assign( m_pNode );
389 void operator ++(int)
396 bool operator ==(iterator_type<C> const& i ) const
398 return m_pNode == i.m_pNode;
401 bool operator !=(iterator_type<C> const& i ) const
403 return m_pNode != i.m_pNode;
411 The forward iterator for Michael's list has some features:
412 - it has no post-increment operator
413 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
414 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
415 may be thrown if the limit of guard count per thread is exceeded.
416 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
417 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
418 deleting operations there is no guarantee that you iterate all item in the list.
420 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
421 for debug purpose only.
423 The iterator interface:
427 // Default constructor
431 iterator( iterator const& src );
433 // Dereference operator
434 value_type * operator ->() const;
436 // Dereference operator
437 value_type& operator *() const;
439 // Preincrement operator
440 iterator& operator ++();
442 // Assignment operator
443 iterator& operator = (iterator const& src);
445 // Equality operators
446 bool operator ==(iterator const& i ) const;
447 bool operator !=(iterator const& i ) const;
451 typedef iterator_type<false> iterator;
452 /// Const forward iterator
454 For iterator's features and requirements see \ref iterator
456 typedef iterator_type<true> const_iterator;
458 /// Returns a forward iterator addressing the first element in a list
460 For empty list \code begin() == end() \endcode
464 return iterator( m_pHead );
467 /// Returns an iterator that addresses the location succeeding the last element in a list
469 Do not use the value returned by <tt>end</tt> function to access any item.
470 Internally, <tt>end</tt> returning value equals to \p nullptr.
472 The returned value can be used only to control reaching the end of the list.
473 For empty list <tt>begin() == end()</tt>
480 /// Returns a forward const iterator addressing the first element in a list
481 const_iterator cbegin() const
483 return const_iterator( m_pHead );
486 /// Returns a forward const iterator addressing the first element in a list
487 const_iterator begin() const
489 return const_iterator( m_pHead );
492 /// Returns an const iterator that addresses the location succeeding the last element in a list
493 const_iterator end() const
495 return const_iterator();
498 /// Returns an const iterator that addresses the location succeeding the last element in a list
499 const_iterator cend() const
501 return const_iterator();
505 /// Default constructor initializes empty list
509 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
512 /// Destroys the list object
520 The function inserts \p val into the list if the list does not contain
521 an item with key equal to \p val.
523 Returns \p true if \p val has been linked to the list, \p false otherwise.
525 bool insert( value_type& val )
527 return insert_at( m_pHead, val );
532 This function is intended for derived non-intrusive containers.
534 The function allows to split new item creating into two part:
535 - create item with key only
536 - insert new item into the list
537 - if inserting is success, calls \p f functor to initialize value-field of \p val.
539 The functor signature is:
541 void func( value_type& val );
543 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
544 \p val no any other changes could be made on this list's item by concurrent threads.
545 The user-defined functor is called only if the inserting is success.
547 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
549 template <typename Func>
550 bool insert( value_type& val, Func f )
552 return insert_at( m_pHead, val, f );
557 The operation performs inserting or changing data with lock-free manner.
559 If the item \p val is not found in the list, then \p val is inserted
560 iff \p bInsert is \p true.
561 Otherwise, the functor \p func is called with item found.
562 The functor signature is:
564 void func( bool bNew, value_type& item, value_type& val );
567 - \p bNew - \p true if the item has been inserted, \p false otherwise
568 - \p item - item of the list
569 - \p val - argument \p val passed into the \p update() function
570 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
571 refers to the same thing.
573 The functor may change non-key fields of the \p item; however, \p func must guarantee
574 that during changing no any other modifications could be made on this item by concurrent threads.
576 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
577 \p second is \p true if new item has been added or \p false if the item with \p key
578 already is in the list.
580 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
582 template <typename Func>
583 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
585 return update_at( m_pHead, val, func, bInsert );
589 template <typename Func>
590 CDS_DEPRECATED("ensure() is deprecated, use update()")
591 std::pair<bool, bool> ensure( value_type& val, Func func )
593 return update( val, func, true );
597 /// Unlinks the item \p val from the list
599 The function searches the item \p val in the list and unlinks it from the list
600 if it is found and it is equal to \p val.
602 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
603 and deletes the item found. \p %unlink() finds an item by key and deletes it
604 only if \p val is an item of the list, i.e. the pointer to item found
605 is equal to <tt> &val </tt>.
607 The function returns \p true if success and \p false otherwise.
609 bool unlink( value_type& val )
611 return unlink_at( m_pHead, val );
614 /// Deletes the item from the list
615 /** \anchor cds_intrusive_MichaelList_hp_erase_val
616 The function searches an item with key equal to \p key in the list,
617 unlinks it from the list, and returns \p true.
618 If \p key is not found the function return \p false.
620 template <typename Q>
621 bool erase( Q const& key )
623 return erase_at( m_pHead, key, key_comparator());
626 /// Deletes the item from the list using \p pred predicate for searching
628 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
629 but \p pred is used for key comparing.
630 \p Less functor has the interface like \p std::less.
631 \p pred must imply the same element order as the comparator used for building the list.
633 template <typename Q, typename Less>
634 bool erase_with( Q const& key, Less pred )
637 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
640 /// Deletes the item from the list
641 /** \anchor cds_intrusive_MichaelList_hp_erase_func
642 The function searches an item with key equal to \p key in the list,
643 call \p func functor with item found, unlinks it from the list, and returns \p true.
644 The \p Func interface is
647 void operator()( value_type const& item );
650 If \p key is not found the function return \p false, \p func is not called.
652 template <typename Q, typename Func>
653 bool erase( Q const& key, Func func )
655 return erase_at( m_pHead, key, key_comparator(), func );
658 /// Deletes the item from the list using \p pred predicate for searching
660 The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
661 but \p pred is used for key comparing.
662 \p Less functor has the interface like \p std::less.
663 \p pred must imply the same element order as the comparator used for building the list.
665 template <typename Q, typename Less, typename Func>
666 bool erase_with( Q const& key, Less pred, Func f )
669 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
672 /// Extracts the item from the list with specified \p key
673 /** \anchor cds_intrusive_MichaelList_hp_extract
674 The function searches an item with key equal to \p key,
675 unlinks it from the list, and returns it as \p guarded_ptr.
676 If \p key is not found returns an empty guarded pointer.
678 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
680 The \ref disposer specified in \p Traits class template parameter is called automatically
681 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
682 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
686 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
690 ord_list::guarded_ptr gp(theList.extract( 5 ));
695 // Destructor of gp releases internal HP guard
699 template <typename Q>
700 guarded_ptr extract( Q const& key )
703 extract_at( m_pHead, gp.guard(), key, key_comparator());
707 /// Extracts the item using compare functor \p pred
709 The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
710 but \p pred predicate is used for key comparing.
712 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
714 \p pred must imply the same element order as the comparator used for building the list.
716 template <typename Q, typename Less>
717 guarded_ptr extract_with( Q const& key, Less pred )
721 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
725 /// Finds \p key in the list
726 /** \anchor cds_intrusive_MichaelList_hp_find_func
727 The function searches the item with key equal to \p key and calls the functor \p f for item found.
728 The interface of \p Func functor is:
731 void operator()( value_type& item, Q& key );
734 where \p item is the item found, \p key is the <tt>find</tt> function argument.
736 The functor may change non-key fields of \p item. Note that the function is only guarantee
737 that \p item cannot be disposed during functor is executing.
738 The function does not serialize simultaneous access to the \p item. If such access is
739 possible you must provide your own synchronization schema to keep out unsafe item modifications.
741 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
742 may modify both arguments.
744 The function returns \p true if \p val is found, \p false otherwise.
746 template <typename Q, typename Func>
747 bool find( Q& key, Func f )
749 return find_at( m_pHead, key, key_comparator(), f );
752 template <typename Q, typename Func>
753 bool find( Q const& key, Func f )
755 return find_at( m_pHead, key, key_comparator(), f );
759 /// Finds the \p key using \p pred predicate for searching
761 The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
762 but \p pred is used for key comparing.
763 \p Less functor has the interface like \p std::less.
764 \p pred must imply the same element order as the comparator used for building the list.
766 template <typename Q, typename Less, typename Func>
767 bool find_with( Q& key, Less pred, Func f )
770 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
773 template <typename Q, typename Less, typename Func>
774 bool find_with( Q const& key, Less pred, Func f )
777 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
781 /// Checks whether the list contains \p key
783 The function searches the item with key equal to \p key
784 and returns \p true if it is found, and \p false otherwise.
786 template <typename Q>
787 bool contains( Q const& key )
789 return find_at( m_pHead, key, key_comparator());
792 template <typename Q>
793 CDS_DEPRECATED("deprecated, use contains()")
794 bool find( Q const& key )
796 return contains( key );
800 /// Checks whether the list contains \p key using \p pred predicate for searching
802 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
803 \p Less functor has the interface like \p std::less.
804 \p Less must imply the same element order as the comparator used for building the list.
806 template <typename Q, typename Less>
807 bool contains( Q const& key, Less pred )
810 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
813 template <typename Q, typename Less>
814 CDS_DEPRECATED("deprecated, use contains()")
815 bool find_with( Q const& key, Less pred )
817 return contains( key, pred );
821 /// Finds the \p key and return the item found
822 /** \anchor cds_intrusive_MichaelList_hp_get
823 The function searches the item with key equal to \p key
824 and returns it as \p guarded_ptr.
825 If \p key is not found the function returns an empty guarded pointer.
827 The \ref disposer specified in \p Traits class template parameter is called
828 by garbage collector \p GC automatically when returned \ref guarded_ptr object
829 will be destroyed or released.
830 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
834 typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
838 ord_list::guarded_ptr gp(theList.get( 5 ));
843 // Destructor of guarded_ptr releases internal HP guard
847 Note the compare functor specified for \p Traits template parameter
848 should accept a parameter of type \p Q that can be not the same as \p value_type.
850 template <typename Q>
851 guarded_ptr get( Q const& key )
854 get_at( m_pHead, gp.guard(), key, key_comparator());
858 /// Finds the \p key and return the item found
860 The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
861 but \p pred is used for comparing the keys.
863 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
865 \p pred must imply the same element order as the comparator used for building the list.
867 template <typename Q, typename Less>
868 guarded_ptr get_with( Q const& key, Less pred )
872 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
878 The function unlink all items from the list.
882 typename gc::Guard guard;
883 marked_node_ptr head;
885 head = m_pHead.load(memory_model::memory_order_relaxed);
887 guard.assign( node_traits::to_value_ptr( *head.ptr()));
888 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
889 if ( head.ptr() == nullptr )
891 value_type& val = *node_traits::to_value_ptr( *head.ptr());
897 /// Checks whether the list is empty
900 return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
903 /// Returns list's item count
905 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
906 this function always returns 0.
908 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
909 is empty. To check list emptyness use \p empty() method.
913 return m_ItemCounter.value();
918 // split-list support
919 bool insert_aux_node( node_type * pNode )
921 return insert_aux_node( m_pHead, pNode );
924 // split-list support
925 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
927 assert( pNode != nullptr );
929 // Hack: convert node_type to value_type.
930 // In principle, auxiliary node can be non-reducible to value_type
931 // We assume that comparator can correctly distinguish aux and regular node.
932 return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
935 bool insert_at( atomic_node_ptr& refHead, value_type& val )
937 node_type * pNode = node_traits::to_node_ptr( val );
938 link_checker::is_empty( pNode );
942 if ( search( refHead, val, pos, key_comparator()))
945 if ( link_node( pNode, pos )) {
951 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
955 template <typename Func>
956 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
958 node_type * pNode = node_traits::to_node_ptr( val );
959 link_checker::is_empty( pNode );
963 if ( search( refHead, val, pos, key_comparator()))
966 typename gc::Guard guard;
967 guard.assign( &val );
968 if ( link_node( pNode, pos )) {
975 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
979 template <typename Func>
980 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
984 node_type * pNode = node_traits::to_node_ptr( val );
986 if ( search( refHead, val, pos, key_comparator())) {
987 if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits()) {
989 continue; // the node found is marked as deleted
991 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
993 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
994 return std::make_pair( true, false );
998 return std::make_pair( false, false );
1000 typename gc::Guard guard;
1001 guard.assign( &val );
1002 if ( link_node( pNode, pos )) {
1004 func( true, val, val );
1005 return std::make_pair( true, true );
1008 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
1013 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1018 while ( search( refHead, val, pos, key_comparator())) {
1019 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
1020 if ( unlink_node( pos )) {
1033 template <typename Q, typename Compare, typename Func>
1034 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1037 while ( search( refHead, val, pos, cmp )) {
1038 if ( unlink_node( pos )) {
1039 f( *node_traits::to_value_ptr( *pos.pCur ));
1049 template <typename Q, typename Compare, typename Func>
1050 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1053 return erase_at( refHead, val, cmp, f, pos );
1056 template <typename Q, typename Compare>
1057 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1060 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1063 template <typename Q, typename Compare>
1064 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1068 while ( search( refHead, val, pos, cmp )) {
1069 if ( unlink_node( pos )) {
1070 dest.set( pos.guards.template get<value_type>( position::guard_current_item ));
1080 template <typename Q, typename Compare>
1081 bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1084 return search( refHead, val, pos, cmp );
1087 template <typename Q, typename Compare, typename Func>
1088 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1091 if ( search( refHead, val, pos, cmp )) {
1092 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1098 template <typename Q, typename Compare>
1099 bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1102 if ( search( refHead, val, pos, cmp )) {
1103 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1114 template <typename Q, typename Compare >
1115 bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1117 atomic_node_ptr * pPrev;
1118 marked_node_ptr pNext;
1119 marked_node_ptr pCur;
1127 pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1128 [](marked_node_ptr p) -> value_type *
1130 return node_traits::to_value_ptr( p.ptr());
1134 if ( pCur.ptr() == nullptr ) {
1137 pos.pNext = nullptr;
1141 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1142 [](marked_node_ptr p ) -> value_type *
1144 return node_traits::to_value_ptr( p.ptr());
1146 if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr()) {
1151 // pNext contains deletion mark for pCur
1152 if ( pNext.bits() == 1 ) {
1153 // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1154 marked_node_ptr cur( pCur.ptr());
1155 if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1156 retire_node( pCur.ptr());
1164 assert( pCur.ptr() != nullptr );
1165 int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1168 pos.pCur = pCur.ptr();
1169 pos.pNext = pNext.ptr();
1172 pPrev = &( pCur->m_pNext );
1173 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1176 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1181 }} // namespace cds::intrusive
1183 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H