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_ITERABLE_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H
34 #include <cds/intrusive/details/iterable_list_base.h>
35 #include <cds/details/make_const_type.h>
37 namespace cds { namespace intrusive {
39 /// Iterable lock-free ordered single-linked list
40 /** @ingroup cds_intrusive_list
41 \anchor cds_intrusive_IterableList_hp
43 This lock-free list implementation supports thread-safe iterators.
44 Unlike \p cds::intrusive::MichaelList the iterable list does not require
45 any hook in \p T to be stored in the list.
47 Usually, ordered single-linked list is used as a building block for the hash table implementation.
48 The complexity of searching is <tt>O(N)</tt>.
51 - \p GC - Garbage collector used.
52 - \p T - type to be stored in the list.
53 - \p Traits - type traits, default is \p iterable_list::traits. It is possible to declare option-based
54 list with \p cds::intrusive::iterable_list::make_traits metafunction:
55 For example, the following traits-based declaration of \p gc::HP iterable list
57 #include <cds/intrusive/iterable_list_hp.h>
58 // Declare item stored in your list
65 // Declare comparator for the item
67 int operator()( foo const& i1, foo const& i2 ) const
69 return i1.nKey - i2.nKey;
74 struct my_traits: public cds::intrusive::iterable_list::traits
76 typedef my_compare compare;
80 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > list_type;
82 is equivalent for the following option-based list
84 #include <cds/intrusive/iterable_list_hp.h>
86 // foo struct and my_compare are the same
88 // Declare option-based list
89 typedef cds::intrusive::IterableList< cds::gc::HP, foo,
90 typename cds::intrusive::iterable_list::make_traits<
91 cds::intrusive::opt::compare< my_compare > // item comparator option
97 There are different specializations of this template for each garbage collecting schema.
98 You should select GC you want and include appropriate .h-file:
99 - for \p gc::HP: <tt> <cds/intrusive/iterable_list_hp.h> </tt>
100 - for \p gc::DHP: <tt> <cds/intrusive/iterable_list_dhp.h> </tt>
101 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
106 #ifdef CDS_DOXYGEN_INVOKED
107 ,class Traits = iterable_list::traits
115 typedef T value_type; ///< type of value stored in the list
116 typedef Traits traits; ///< Traits template parameter
118 typedef iterable_list::node< value_type > node_type; ///< node type
120 # ifdef CDS_DOXYGEN_INVOKED
121 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
123 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
126 typedef typename traits::disposer disposer; ///< disposer for \p value_type
128 typedef GC gc; ///< Garbage collector
129 typedef typename traits::back_off back_off; ///< back-off strategy
130 typedef typename traits::item_counter item_counter; ///< Item counting policy used
131 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
132 typedef typename traits::node_allocator node_allocator; ///< Node allocator
134 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
136 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
139 // Rebind traits (split-list support)
140 template <typename... Options>
141 struct rebind_traits {
142 typedef IterableList<
145 , typename cds::opt::make_options< traits, Options...>::type
151 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
152 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
154 atomic_node_ptr m_pHead; ///< Head pointer
155 item_counter m_ItemCounter; ///< Item counter
158 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
160 /// Position pointer for item search
162 atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead)
163 node_type * pPrev; ///< Previous node
164 node_type * pCur; ///< Current node
166 value_type * pFound; ///< Value of \p pCur->data, valid only if data found
167 typename gc::Guard guard; ///< guard for \p pFound
173 template <bool IsConst>
176 friend class IterableList;
181 typename gc::Guard m_Guard; // for m_pVal
186 m_pNode = m_pNode->next.load( memory_model::memory_order_relaxed );
189 m_pVal = m_Guard.protect( m_pNode->data );
195 explicit iterator_type( atomic_node_ptr const& pNode )
196 : m_pNode( pNode.load( memory_model::memory_order_relaxed ))
200 m_pVal = m_Guard.protect( m_pNode->data );
206 iterator_type( node_type* pNode, value_type* pVal )
211 assert( pVal != nullptr );
212 m_Guard.assign( pVal );
217 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
218 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
225 iterator_type( iterator_type const& src )
226 : m_pNode( src.m_pNode )
227 , m_pVal( src.m_pVal )
229 m_Guard.assign( m_pVal );
232 value_ptr operator ->() const
237 value_ref operator *() const
239 assert( m_pVal != nullptr );
244 iterator_type& operator ++()
250 iterator_type& operator = (iterator_type const& src)
252 m_pNode = src.m_pNode;
254 m_Guard.assign( m_pVal );
259 bool operator ==(iterator_type<C> const& i ) const
261 return m_pNode == i.m_pNode;
264 bool operator !=(iterator_type<C> const& i ) const
266 return m_pNode != i.m_pNode;
272 ///@name Thread-safe forward iterators
276 The forward iterator for iterable list has some features:
277 - it has no post-increment operator
278 - to protect the value, the iterator contains a GC-specific guard.
279 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
280 may be thrown if the limit of guard count per thread is exceeded.
281 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
282 - Iterator is thread-safe: event if the element the iterator points to is removed, the iterator stays valid because
283 it contains the guard keeping the value from to be recycled.
285 The iterator interface:
289 // Default constructor
293 iterator( iterator const& src );
295 // Dereference operator
296 value_type * operator ->() const;
298 // Dereference operator
299 value_type& operator *() const;
301 // Preincrement operator
302 iterator& operator ++();
304 // Assignment operator
305 iterator& operator = (iterator const& src);
307 // Equality operators
308 bool operator ==(iterator const& i ) const;
309 bool operator !=(iterator const& i ) const;
313 @note For two iterators pointed to the same element the value can be different;
317 assert( &(*it1) == &(*it2) );
319 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
320 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
321 Other iterator can observe modified value of the element.
323 typedef iterator_type<false> iterator;
324 /// Const forward iterator
326 For iterator's features and requirements see \ref iterator
328 typedef iterator_type<true> const_iterator;
330 /// Returns a forward iterator addressing the first element in a list
332 For empty list \code begin() == end() \endcode
336 return iterator( m_pHead );
339 /// Returns an iterator that addresses the location succeeding the last element in a list
341 Do not use the value returned by <tt>end</tt> function to access any item.
342 Internally, <tt>end</tt> returning value equals to \p nullptr.
344 The returned value can be used only to control reaching the end of the list.
345 For empty list <tt>begin() == end()</tt>
352 /// Returns a forward const iterator addressing the first element in a list
353 const_iterator cbegin() const
355 return const_iterator( m_pHead );
358 /// Returns a forward const iterator addressing the first element in a list
359 const_iterator begin() const
361 return const_iterator( m_pHead );
364 /// Returns an const iterator that addresses the location succeeding the last element in a list
365 const_iterator end() const
367 return const_iterator();
370 /// Returns an const iterator that addresses the location succeeding the last element in a list
371 const_iterator cend() const
373 return const_iterator();
378 /// Default constructor initializes empty list
383 /// Destroys the list object
391 The function inserts \p val into the list if the list does not contain
392 an item with key equal to \p val.
394 Returns \p true if \p val has been linked to the list, \p false otherwise.
396 bool insert( value_type& val )
398 return insert_at( m_pHead, val );
403 This function is intended for derived non-intrusive containers.
405 The function allows to split new item creating into two part:
406 - create item with key only
407 - insert new item into the list
408 - if inserting is success, calls \p f functor to initialize value-field of \p val.
410 The functor signature is:
412 void func( value_type& val );
414 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
415 \p val no any other changes could be made on this list's item by concurrent threads.
416 The user-defined functor is called only if the inserting is success.
418 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
420 template <typename Func>
421 bool insert( value_type& val, Func f )
423 return insert_at( m_pHead, val, f );
428 The operation performs inserting or changing data with lock-free manner.
430 If the item \p val is not found in the list, then \p val is inserted
431 iff \p bInsert is \p true.
432 Otherwise, the current element is changed to \p val, the element will be retired later
433 by call \p Traits::disposer.
434 The functor \p func is called after inserting or replacing, it signature is:
436 void func( value_type& val, value_type * old );
439 - \p val - argument \p val passed into the \p %update() function
440 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
442 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
443 \p second is \p true if \p val has been added or \p false if the item with that key
446 template <typename Func>
447 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
449 return update_at( m_pHead, val, func, bInsert );
454 The operation performs inserting or changing data with lock-free manner.
456 If the item \p val is not found in the list, then \p val is inserted
457 iff \p bInsert is \p true.
458 Otherwise, the current element is changed to \p val, the element will be retired later
459 by call \p Traits::disposer.
461 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
462 \p second is \p true if \p val has been added or \p false if the item with that key
465 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
467 return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
470 /// Unlinks the item \p val from the list
472 The function searches the item \p val in the list and unlinks it from the list
473 if it is found and it is equal to \p val.
475 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
476 and deletes the item found. \p %unlink() finds an item by key and deletes it
477 only if \p val is an item of the list, i.e. the pointer to item found
478 is equal to <tt> &val </tt>.
480 \p disposer specified in \p Traits is called for deleted item.
482 The function returns \p true if success and \p false otherwise.
484 bool unlink( value_type& val )
486 return unlink_at( m_pHead, val );
489 /// Deletes the item from the list
490 /** \anchor cds_intrusive_IterableList_hp_erase_val
491 The function searches an item with key equal to \p key in the list,
492 unlinks it from the list, and returns \p true.
493 If \p key is not found the function return \p false.
495 \p disposer specified in \p Traits is called for deleted item.
497 template <typename Q>
498 bool erase( Q const& key )
500 return erase_at( m_pHead, key, key_comparator());
503 /// Deletes the item from the list using \p pred predicate for searching
505 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
506 but \p pred is used for key comparing.
507 \p Less functor has the interface like \p std::less.
508 \p pred must imply the same element order as the comparator used for building the list.
510 \p disposer specified in \p Traits is called for deleted item.
512 template <typename Q, typename Less>
513 bool erase_with( Q const& key, Less pred )
516 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
519 /// Deletes the item from the list
520 /** \anchor cds_intrusive_IterableList_hp_erase_func
521 The function searches an item with key equal to \p key in the list,
522 call \p func functor with item found, unlinks it from the list, and returns \p true.
523 The \p Func interface is
526 void operator()( value_type const& item );
529 If \p key is not found the function return \p false, \p func is not called.
531 \p disposer specified in \p Traits is called for deleted item.
533 template <typename Q, typename Func>
534 bool erase( Q const& key, Func func )
536 return erase_at( m_pHead, key, key_comparator(), func );
539 /// Deletes the item from the list using \p pred predicate for searching
541 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
542 but \p pred is used for key comparing.
543 \p Less functor has the interface like \p std::less.
544 \p pred must imply the same element order as the comparator used for building the list.
546 \p disposer specified in \p Traits is called for deleted item.
548 template <typename Q, typename Less, typename Func>
549 bool erase_with( Q const& key, Less pred, Func f )
552 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
555 /// Extracts the item from the list with specified \p key
556 /** \anchor cds_intrusive_IterableList_hp_extract
557 The function searches an item with key equal to \p key,
558 unlinks it from the list, and returns it as \p guarded_ptr.
559 If \p key is not found returns an empty guarded pointer.
561 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
563 The \ref disposer specified in \p Traits class template parameter is called automatically
564 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
565 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
569 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
573 ord_list::guarded_ptr gp(theList.extract( 5 ));
578 // Destructor of gp releases internal HP guard
582 template <typename Q>
583 guarded_ptr extract( Q const& key )
586 extract_at( m_pHead, gp.guard(), key, key_comparator());
590 /// Extracts the item using compare functor \p pred
592 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
593 but \p pred predicate is used for key comparing.
595 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
597 \p pred must imply the same element order as the comparator used for building the list.
599 template <typename Q, typename Less>
600 guarded_ptr extract_with( Q const& key, Less pred )
604 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
608 /// Finds \p key in the list
609 /** \anchor cds_intrusive_IterableList_hp_find_func
610 The function searches the item with key equal to \p key and calls the functor \p f for item found.
611 The interface of \p Func functor is:
614 void operator()( value_type& item, Q& key );
617 where \p item is the item found, \p key is the \p %find() function argument.
619 The functor may change non-key fields of \p item. Note that the function is only guarantee
620 that \p item cannot be disposed during functor is executing.
621 The function does not serialize simultaneous access to the \p item. If such access is
622 possible you must provide your own synchronization schema to keep out unsafe item modifications.
624 The function returns \p true if \p val is found, \p false otherwise.
626 template <typename Q, typename Func>
627 bool find( Q& key, Func f ) const
629 return find_at( m_pHead, key, key_comparator(), f );
632 template <typename Q, typename Func>
633 bool find( Q const& key, Func f ) const
635 return find_at( m_pHead, key, key_comparator(), f );
639 /// Finds \p key in the list and returns iterator pointed to the item found
641 If \p key is not found the function returns \p end().
643 template <typename Q>
644 iterator find( Q& key ) const
646 return find_iterator_at( m_pHead, key, key_comparator());
649 template <typename Q>
650 iterator find( Q const& key ) const
652 return find_iterator_at( m_pHead, key, key_comparator() );
656 /// Finds the \p key using \p pred predicate for searching
658 The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
659 but \p pred is used for key comparing.
660 \p Less functor has the interface like \p std::less.
661 \p pred must imply the same element order as the comparator used for building the list.
663 template <typename Q, typename Less, typename Func>
664 bool find_with( Q& key, Less pred, Func f ) const
667 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
670 template <typename Q, typename Less, typename Func>
671 bool find_with( Q const& key, Less pred, Func f ) const
674 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
678 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
680 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
681 \p Less functor has the interface like \p std::less.
682 \p pred must imply the same element order as the comparator used for building the list.
684 If \p key is not found the function returns \p end().
686 template <typename Q, typename Less>
687 iterator find_with( Q& key, Less pred ) const
690 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
693 template <typename Q, typename Less>
694 iterator find_with( Q const& key, Less pred ) const
697 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
701 /// Checks whether the list contains \p key
703 The function searches the item with key equal to \p key
704 and returns \p true if it is found, and \p false otherwise.
706 template <typename Q>
707 bool contains( Q const& key ) const
709 return find_at( m_pHead, key, key_comparator());
712 /// Checks whether the list contains \p key using \p pred predicate for searching
714 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
715 \p Less functor has the interface like \p std::less.
716 \p Less must imply the same element order as the comparator used for building the list.
718 template <typename Q, typename Less>
719 bool contains( Q const& key, Less pred ) const
722 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
725 /// Finds the \p key and return the item found
726 /** \anchor cds_intrusive_IterableList_hp_get
727 The function searches the item with key equal to \p key
728 and returns it as \p guarded_ptr.
729 If \p key is not found the function returns an empty guarded pointer.
731 The \ref disposer specified in \p Traits class template parameter is called
732 by garbage collector \p GC automatically when returned \ref guarded_ptr object
733 will be destroyed or released.
734 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
738 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
742 ord_list::guarded_ptr gp(theList.get( 5 ));
747 // Destructor of guarded_ptr releases internal HP guard
751 Note the compare functor specified for \p Traits template parameter
752 should accept a parameter of type \p Q that can be not the same as \p value_type.
754 template <typename Q>
755 guarded_ptr get( Q const& key ) const
758 get_at( m_pHead, gp.guard(), key, key_comparator());
762 /// Finds the \p key and return the item found
764 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
765 but \p pred is used for comparing the keys.
767 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
769 \p pred must imply the same element order as the comparator used for building the list.
771 template <typename Q, typename Less>
772 guarded_ptr get_with( Q const& key, Less pred ) const
776 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
780 /// Clears the list (thread safe, not atomic)
784 for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
786 pos.pFound = pos.guard.protect( pos.pCur->data );
789 if ( cds_likely( unlink_node( pos ))) {
797 /// Checks if the list is empty
799 Emptiness is checked by item counting: if item count is zero then the set is empty.
800 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
808 /// Returns list's item count
810 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
811 this function always returns 0.
815 return m_ItemCounter.value();
821 // split-list support
822 bool insert_aux_node( node_type * pNode )
824 return insert_aux_node( m_pHead, pNode );
827 // split-list support
828 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
830 assert( pNode != nullptr );
832 // Hack: convert node_type to value_type.
833 // In principle, auxiliary node can be non-reducible to value_type
834 // We assume that comparator can correctly distinguish aux and regular node.
835 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
839 bool insert_at( atomic_node_ptr& refHead, value_type& val )
844 if ( search( refHead, val, pos, key_comparator() ) )
847 if ( link_node( &val, pos ) ) {
854 template <typename Func>
855 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
859 typename gc::Guard guard;
860 guard.assign( &val );
863 if ( search( refHead, val, pos, key_comparator() ) )
866 if ( link_node( &val, pos ) ) {
874 template <typename Func>
875 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
879 typename gc::Guard guard;
880 guard.assign( &val );
883 if ( search( refHead, val, pos, key_comparator() ) ) {
884 // try to replace pCur->data with val
885 assert( pos.pFound != nullptr );
886 assert( key_comparator()(*pos.pFound, val) == 0 );
888 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
889 if ( pos.pFound != &val ) {
890 retire_data( pos.pFound );
891 func( val, pos.pFound );
893 return std::make_pair( true, false );
898 return std::make_pair( false, false );
900 if ( link_node( &val, pos ) ) {
901 func( val, static_cast<value_type*>( nullptr ));
903 return std::make_pair( true, true );
909 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
914 while ( search( refHead, val, pos, key_comparator())) {
915 if ( pos.pFound == &val ) {
916 if ( unlink_node( pos )) {
929 template <typename Q, typename Compare, typename Func>
930 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
933 while ( search( refHead, val, pos, cmp )) {
934 if ( unlink_node( pos )) {
945 template <typename Q, typename Compare, typename Func>
946 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
949 return erase_at( refHead, val, cmp, f, pos );
952 template <typename Q, typename Compare>
953 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
956 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
959 template <typename Q, typename Compare>
960 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
964 while ( search( refHead, val, pos, cmp )) {
965 if ( unlink_node( pos )) {
966 dest.set( pos.pFound );
976 template <typename Q, typename Compare>
977 bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
980 return search( refHead, val, pos, cmp );
983 template <typename Q, typename Compare, typename Func>
984 bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const
987 if ( search( refHead, val, pos, cmp )) {
988 assert( pos.pFound != nullptr );
989 f( *pos.pFound, val );
995 template <typename Q, typename Compare>
996 iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
999 if ( search( refHead, val, pos, cmp )) {
1000 assert( pos.pCur != nullptr );
1001 assert( pos.pFound != nullptr );
1002 return iterator( pos.pCur, pos.pFound );
1007 template <typename Q, typename Compare>
1008 bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const
1011 if ( search( refHead, val, pos, cmp )) {
1012 guard.set( pos.pFound );
1022 template <typename Q, typename Compare >
1023 bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const
1025 atomic_node_ptr* pHead = const_cast<atomic_node_ptr*>( &refHead );
1026 node_type * pPrev = nullptr;
1029 node_type * pCur = pHead->load( memory_model::memory_order_relaxed );
1031 if ( pCur == nullptr ) {
1036 pos.pFound = nullptr;
1040 value_type * pVal = pos.guard.protect( pCur->data );
1043 int nCmp = cmp( *pVal, val );
1054 pHead = &( pCur->next );
1061 static node_type * alloc_node( value_type * pVal )
1063 return cxx_node_allocator().New( pVal );
1066 static void delete_node( node_type * pNode )
1068 cxx_node_allocator().Delete( pNode );
1071 static void retire_data( value_type * pVal )
1073 assert( pVal != nullptr );
1074 gc::template retire<disposer>( pVal );
1079 node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed );
1081 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed );
1083 retire_data( pVal );
1084 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1085 delete_node( pNode );
1090 static bool link_node( value_type * pVal, position& pos )
1093 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
1095 value_type * p = nullptr;
1096 return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed );
1099 // insert new node between pos.pPrev and pos.pCur
1100 node_type * pNode = alloc_node( pVal );
1101 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1103 if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
1106 delete_node( pNode );
1110 node_type * pNode = alloc_node( pVal );
1111 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1112 if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) )
1115 delete_node( pNode );
1120 static bool unlink_node( position& pos )
1122 assert( pos.pCur != nullptr );
1123 assert( pos.pFound != nullptr );
1125 if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1126 retire_data( pos.pFound );
1134 }} // namespace cds::intrusive
1136 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H