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 Iterable list is suitable for almost append-only hash table because the list doesn't delete
49 its internal node when erasing a key but it is marked them as empty to be reused in the future.
50 However, plenty of empty nodes degrades performance.
51 Separation of internal nodes and user data implies the need for an allocator for internal node
52 so the iterable list is not fully intrusive. Nevertheless, if you need thread-safe iterator,
53 the iterable list is good choice.
55 The complexity of searching is <tt>O(N)</tt>.
58 - \p GC - Garbage collector used.
59 - \p T - type to be stored in the list.
60 - \p Traits - type traits, default is \p iterable_list::traits. It is possible to declare option-based
61 list with \p cds::intrusive::iterable_list::make_traits metafunction:
62 For example, the following traits-based declaration of \p gc::HP iterable list
64 #include <cds/intrusive/iterable_list_hp.h>
65 // Declare item stored in your list
72 // Declare comparator for the item
74 int operator()( foo const& i1, foo const& i2 ) const
76 return i1.nKey - i2.nKey;
81 struct my_traits: public cds::intrusive::iterable_list::traits
83 typedef my_compare compare;
87 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > list_type;
89 is equivalent for the following option-based list
91 #include <cds/intrusive/iterable_list_hp.h>
93 // foo struct and my_compare are the same
95 // Declare option-based list
96 typedef cds::intrusive::IterableList< cds::gc::HP, foo,
97 typename cds::intrusive::iterable_list::make_traits<
98 cds::intrusive::opt::compare< my_compare > // item comparator option
104 There are different specializations of this template for each garbage collecting schema.
105 You should select GC you want and include appropriate .h-file:
106 - for \p gc::HP: <tt> <cds/intrusive/iterable_list_hp.h> </tt>
107 - for \p gc::DHP: <tt> <cds/intrusive/iterable_list_dhp.h> </tt>
108 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
113 #ifdef CDS_DOXYGEN_INVOKED
114 ,class Traits = iterable_list::traits
122 typedef T value_type; ///< type of value stored in the list
123 typedef Traits traits; ///< Traits template parameter
125 typedef iterable_list::node< value_type > node_type; ///< node type
127 # ifdef CDS_DOXYGEN_INVOKED
128 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
130 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
133 typedef typename traits::disposer disposer; ///< disposer for \p value_type
135 typedef GC gc; ///< Garbage collector
136 typedef typename traits::back_off back_off; ///< back-off strategy
137 typedef typename traits::item_counter item_counter; ///< Item counting policy used
138 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
139 typedef typename traits::node_allocator node_allocator; ///< Node allocator
140 typedef typename traits::stat stat; ///< Internal statistics
142 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
144 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
147 // Rebind traits (split-list support)
148 template <typename... Options>
149 struct rebind_traits {
150 typedef IterableList<
153 , typename cds::opt::make_options< traits, Options...>::type
159 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
160 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
162 atomic_node_ptr m_pHead; ///< Head pointer
163 item_counter m_ItemCounter; ///< Item counter
164 mutable stat m_Stat; ///< Internal statistics
167 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
169 /// Position pointer for item search
171 atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead)
172 node_type * pPrev; ///< Previous node
173 node_type * pCur; ///< Current node
175 value_type * pFound; ///< Value of \p pCur->data, valid only if data found
176 typename gc::Guard guard; ///< guard for \p pFound
182 template <bool IsConst>
185 friend class IterableList;
190 typename gc::Guard m_Guard; // for m_pVal
195 m_pNode = m_pNode->next.load( memory_model::memory_order_relaxed );
198 m_pVal = m_Guard.protect( m_pNode->data );
204 explicit iterator_type( atomic_node_ptr const& pNode )
205 : m_pNode( pNode.load( memory_model::memory_order_relaxed ))
209 m_pVal = m_Guard.protect( m_pNode->data );
215 iterator_type( node_type* pNode, value_type* pVal )
220 assert( pVal != nullptr );
221 m_Guard.assign( pVal );
226 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
227 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
234 iterator_type( iterator_type const& src )
235 : m_pNode( src.m_pNode )
236 , m_pVal( src.m_pVal )
238 m_Guard.assign( m_pVal );
241 value_ptr operator ->() const
246 value_ref operator *() const
248 assert( m_pVal != nullptr );
253 iterator_type& operator ++()
259 iterator_type& operator = (iterator_type const& src)
261 m_pNode = src.m_pNode;
263 m_Guard.assign( m_pVal );
268 bool operator ==(iterator_type<C> const& i ) const
270 return m_pNode == i.m_pNode;
273 bool operator !=(iterator_type<C> const& i ) const
275 return m_pNode != i.m_pNode;
281 ///@name Thread-safe forward iterators
285 The forward iterator for iterable list has some features:
286 - it has no post-increment operator
287 - to protect the value, the iterator contains a GC-specific guard.
288 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
289 may be thrown if the limit of guard count per thread is exceeded.
290 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
291 - Iterator is thread-safe: event if the element the iterator points to is removed, the iterator stays valid because
292 it contains the guard keeping the value from to be recycled.
294 The iterator interface:
298 // Default constructor
302 iterator( iterator const& src );
304 // Dereference operator
305 value_type * operator ->() const;
307 // Dereference operator
308 value_type& operator *() const;
310 // Preincrement operator
311 iterator& operator ++();
313 // Assignment operator
314 iterator& operator = (iterator const& src);
316 // Equality operators
317 bool operator ==(iterator const& i ) const;
318 bool operator !=(iterator const& i ) const;
322 @note For two iterators pointed to the same element the value can be different;
326 assert( &(*it1) == &(*it2) );
328 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
329 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
330 Other iterator can observe modified value of the element.
332 typedef iterator_type<false> iterator;
333 /// Const forward iterator
335 For iterator's features and requirements see \ref iterator
337 typedef iterator_type<true> const_iterator;
339 /// Returns a forward iterator addressing the first element in a list
341 For empty list \code begin() == end() \endcode
345 return iterator( m_pHead );
348 /// Returns an iterator that addresses the location succeeding the last element in a list
350 Do not use the value returned by <tt>end</tt> function to access any item.
351 Internally, <tt>end</tt> returning value equals to \p nullptr.
353 The returned value can be used only to control reaching the end of the list.
354 For empty list <tt>begin() == end()</tt>
361 /// Returns a forward const iterator addressing the first element in a list
362 const_iterator cbegin() const
364 return const_iterator( m_pHead );
367 /// Returns a forward const iterator addressing the first element in a list
368 const_iterator begin() const
370 return const_iterator( m_pHead );
373 /// Returns an const iterator that addresses the location succeeding the last element in a list
374 const_iterator end() const
376 return const_iterator();
379 /// Returns an const iterator that addresses the location succeeding the last element in a list
380 const_iterator cend() const
382 return const_iterator();
387 /// Default constructor initializes empty list
393 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
394 explicit IterableList( Stat& st )
400 /// Destroys the list object
408 The function inserts \p val into the list if the list does not contain
409 an item with key equal to \p val.
411 Returns \p true if \p val has been linked to the list, \p false otherwise.
413 bool insert( value_type& val )
415 return insert_at( m_pHead, val );
420 This function is intended for derived non-intrusive containers.
422 The function allows to split new item creating into two part:
423 - create item with key only
424 - insert new item into the list
425 - if inserting is success, calls \p f functor to initialize value-field of \p val.
427 The functor signature is:
429 void func( value_type& val );
431 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
432 \p val no any other changes could be made on this list's item by concurrent threads.
433 The user-defined functor is called only if the inserting is success.
435 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
437 template <typename Func>
438 bool insert( value_type& val, Func f )
440 return insert_at( m_pHead, val, f );
445 The operation performs inserting or changing data with lock-free manner.
447 If the item \p val is not found in the list, then \p val is inserted
448 iff \p bInsert is \p true.
449 Otherwise, the current element is changed to \p val, the element will be retired later
450 by call \p Traits::disposer.
451 The functor \p func is called after inserting or replacing, it signature is:
453 void func( value_type& val, value_type * old );
456 - \p val - argument \p val passed into the \p %update() function
457 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
459 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
460 \p second is \p true if \p val has been added or \p false if the item with that key
463 template <typename Func>
464 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
466 return update_at( m_pHead, val, func, bInsert );
471 The operation performs inserting or changing data with lock-free manner.
473 If the item \p val is not found in the list, then \p val is inserted
474 iff \p bInsert is \p true.
475 Otherwise, the current element is changed to \p val, the old element will be retired later
476 by call \p Traits::disposer.
478 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
479 \p second is \p true if \p val has been added or \p false if the item with that key
482 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
484 return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
487 /// Unlinks the item \p val from the list
489 The function searches the item \p val in the list and unlinks it from the list
490 if it is found and it is equal to \p val.
492 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
493 and deletes the item found. \p %unlink() finds an item by key and deletes it
494 only if \p val is an item of the list, i.e. the pointer to item found
495 is equal to <tt> &val </tt>.
497 \p disposer specified in \p Traits is called for deleted item.
499 The function returns \p true if success and \p false otherwise.
501 bool unlink( value_type& val )
503 return unlink_at( m_pHead, val );
506 /// Deletes the item from the list
507 /** \anchor cds_intrusive_IterableList_hp_erase_val
508 The function searches an item with key equal to \p key in the list,
509 unlinks it from the list, and returns \p true.
510 If \p key is not found the function return \p false.
512 \p disposer specified in \p Traits is called for deleted item.
514 template <typename Q>
515 bool erase( Q const& key )
517 return erase_at( m_pHead, key, key_comparator());
520 /// Deletes the item from the list using \p pred predicate for searching
522 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
523 but \p pred is used for key comparing.
524 \p Less functor has the interface like \p std::less.
525 \p pred must imply the same element order as the comparator used for building the list.
527 \p disposer specified in \p Traits is called for deleted item.
529 template <typename Q, typename Less>
530 bool erase_with( Q const& key, Less pred )
533 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
536 /// Deletes the item from the list
537 /** \anchor cds_intrusive_IterableList_hp_erase_func
538 The function searches an item with key equal to \p key in the list,
539 call \p func functor with item found, unlinks it from the list, and returns \p true.
540 The \p Func interface is
543 void operator()( value_type const& item );
546 If \p key is not found the function return \p false, \p func is not called.
548 \p disposer specified in \p Traits is called for deleted item.
550 template <typename Q, typename Func>
551 bool erase( Q const& key, Func func )
553 return erase_at( m_pHead, key, key_comparator(), func );
556 /// Deletes the item from the list using \p pred predicate for searching
558 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
559 but \p pred is used for key comparing.
560 \p Less functor has the interface like \p std::less.
561 \p pred must imply the same element order as the comparator used for building the list.
563 \p disposer specified in \p Traits is called for deleted item.
565 template <typename Q, typename Less, typename Func>
566 bool erase_with( Q const& key, Less pred, Func f )
569 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
572 /// Extracts the item from the list with specified \p key
573 /** \anchor cds_intrusive_IterableList_hp_extract
574 The function searches an item with key equal to \p key,
575 unlinks it from the list, and returns it as \p guarded_ptr.
576 If \p key is not found returns an empty guarded pointer.
578 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
580 The \ref disposer specified in \p Traits class template parameter is called automatically
581 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
582 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
586 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
590 ord_list::guarded_ptr gp(theList.extract( 5 ));
595 // Destructor of gp releases internal HP guard
599 template <typename Q>
600 guarded_ptr extract( Q const& key )
603 extract_at( m_pHead, gp.guard(), key, key_comparator());
607 /// Extracts the item using compare functor \p pred
609 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
610 but \p pred predicate is used for key comparing.
612 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
614 \p pred must imply the same element order as the comparator used for building the list.
616 template <typename Q, typename Less>
617 guarded_ptr extract_with( Q const& key, Less pred )
621 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
625 /// Finds \p key in the list
626 /** \anchor cds_intrusive_IterableList_hp_find_func
627 The function searches the item with key equal to \p key and calls the functor \p f for item found.
628 The interface of \p Func functor is:
631 void operator()( value_type& item, Q& key );
634 where \p item is the item found, \p key is the \p %find() function argument.
636 The functor may change non-key fields of \p item. Note that the function is only guarantee
637 that \p item cannot be disposed during functor is executing.
638 The function does not serialize simultaneous access to the \p item. If such access is
639 possible you must provide your own synchronization schema to keep out unsafe item modifications.
641 The function returns \p true if \p val is found, \p false otherwise.
643 template <typename Q, typename Func>
644 bool find( Q& key, Func f ) const
646 return find_at( m_pHead, key, key_comparator(), f );
649 template <typename Q, typename Func>
650 bool find( Q const& key, Func f ) const
652 return find_at( m_pHead, key, key_comparator(), f );
656 /// Finds \p key in the list and returns iterator pointed to the item found
658 If \p key is not found the function returns \p end().
660 template <typename Q>
661 iterator find( Q& key ) const
663 return find_iterator_at( m_pHead, key, key_comparator());
666 template <typename Q>
667 iterator find( Q const& key ) const
669 return find_iterator_at( m_pHead, key, key_comparator() );
673 /// Finds the \p key using \p pred predicate for searching
675 The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
676 but \p pred is used for key comparing.
677 \p Less functor has the interface like \p std::less.
678 \p pred must imply the same element order as the comparator used for building the list.
680 template <typename Q, typename Less, typename Func>
681 bool find_with( Q& key, Less pred, Func f ) const
684 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
687 template <typename Q, typename Less, typename Func>
688 bool find_with( Q const& key, Less pred, Func f ) const
691 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
695 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
697 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
698 \p Less functor has the interface like \p std::less.
699 \p pred must imply the same element order as the comparator used for building the list.
701 If \p key is not found the function returns \p end().
703 template <typename Q, typename Less>
704 iterator find_with( Q& key, Less pred ) const
707 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
710 template <typename Q, typename Less>
711 iterator find_with( Q const& key, Less pred ) const
714 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
718 /// Checks whether the list contains \p key
720 The function searches the item with key equal to \p key
721 and returns \p true if it is found, and \p false otherwise.
723 template <typename Q>
724 bool contains( Q const& key ) const
726 return find_at( m_pHead, key, key_comparator());
729 /// Checks whether the list contains \p key using \p pred predicate for searching
731 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
732 \p Less functor has the interface like \p std::less.
733 \p Less must imply the same element order as the comparator used for building the list.
735 template <typename Q, typename Less>
736 bool contains( Q const& key, Less pred ) const
739 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
742 /// Finds the \p key and return the item found
743 /** \anchor cds_intrusive_IterableList_hp_get
744 The function searches the item with key equal to \p key
745 and returns it as \p guarded_ptr.
746 If \p key is not found the function returns an empty guarded pointer.
748 The \ref disposer specified in \p Traits class template parameter is called
749 by garbage collector \p GC automatically when returned \ref guarded_ptr object
750 will be destroyed or released.
751 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
755 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
759 ord_list::guarded_ptr gp(theList.get( 5 ));
764 // Destructor of guarded_ptr releases internal HP guard
768 Note the compare functor specified for \p Traits template parameter
769 should accept a parameter of type \p Q that can be not the same as \p value_type.
771 template <typename Q>
772 guarded_ptr get( Q const& key ) const
775 get_at( m_pHead, gp.guard(), key, key_comparator());
779 /// Finds the \p key and return the item found
781 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
782 but \p pred is used for comparing the keys.
784 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
786 \p pred must imply the same element order as the comparator used for building the list.
788 template <typename Q, typename Less>
789 guarded_ptr get_with( Q const& key, Less pred ) const
793 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
797 /// Clears the list (thread safe, not atomic)
801 for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
803 pos.pFound = pos.guard.protect( pos.pCur->data );
806 if ( cds_likely( unlink_node( pos ))) {
814 /// Checks if the list is empty
816 Emptiness is checked by item counting: if item count is zero then the set is empty.
817 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
825 /// Returns list's item count
827 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
828 this function always returns 0.
832 return m_ItemCounter.value();
838 // split-list support
839 bool insert_aux_node( node_type * pNode )
841 return insert_aux_node( m_pHead, pNode );
844 // split-list support
845 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
847 assert( pNode != nullptr );
849 // Hack: convert node_type to value_type.
850 // In principle, auxiliary node can be non-reducible to value_type
851 // We assume that comparator can correctly distinguish aux and regular node.
852 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
856 bool insert_at( atomic_node_ptr& refHead, value_type& val )
861 if ( search( refHead, val, pos, key_comparator() )) {
862 m_Stat.onInsertFailed();
866 if ( link_node( &val, pos ) ) {
868 m_Stat.onInsertSuccess();
872 m_Stat.onInsertRetry();
876 template <typename Func>
877 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
881 typename gc::Guard guard;
882 guard.assign( &val );
885 if ( search( refHead, val, pos, key_comparator() ) ) {
886 m_Stat.onInsertFailed();
890 if ( link_node( &val, pos ) ) {
893 m_Stat.onInsertSuccess();
897 m_Stat.onInsertRetry();
901 template <typename Func>
902 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
906 typename gc::Guard guard;
907 guard.assign( &val );
910 if ( search( refHead, val, pos, key_comparator() ) ) {
911 // try to replace pCur->data with val
912 assert( pos.pFound != nullptr );
913 assert( key_comparator()(*pos.pFound, val) == 0 );
915 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
916 if ( pos.pFound != &val ) {
917 retire_data( pos.pFound );
918 func( val, pos.pFound );
920 m_Stat.onUpdateExisting();
921 return std::make_pair( true, false );
926 m_Stat.onUpdateFailed();
927 return std::make_pair( false, false );
930 if ( link_node( &val, pos )) {
931 func( val, static_cast<value_type*>( nullptr ));
933 m_Stat.onUpdateNew();
934 return std::make_pair( true, true );
938 m_Stat.onUpdateRetry();
942 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
947 while ( search( refHead, val, pos, key_comparator())) {
948 if ( pos.pFound == &val ) {
949 if ( unlink_node( pos )) {
951 m_Stat.onEraseSuccess();
960 m_Stat.onEraseRetry();
963 m_Stat.onEraseFailed();
967 template <typename Q, typename Compare, typename Func>
968 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
971 while ( search( refHead, val, pos, cmp )) {
972 if ( unlink_node( pos )) {
975 m_Stat.onEraseSuccess();
981 m_Stat.onEraseRetry();
984 m_Stat.onEraseFailed();
988 template <typename Q, typename Compare, typename Func>
989 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
992 return erase_at( refHead, val, cmp, f, pos );
995 template <typename Q, typename Compare>
996 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
999 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1002 template <typename Q, typename Compare>
1003 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1007 while ( search( refHead, val, pos, cmp )) {
1008 if ( unlink_node( pos )) {
1009 dest.set( pos.pFound );
1011 m_Stat.onEraseSuccess();
1017 m_Stat.onEraseRetry();
1020 m_Stat.onEraseFailed();
1024 template <typename Q, typename Compare>
1025 bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1028 if ( search( refHead, val, pos, cmp ) ) {
1029 m_Stat.onFindSuccess();
1033 m_Stat.onFindFailed();
1037 template <typename Q, typename Compare, typename Func>
1038 bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const
1041 if ( search( refHead, val, pos, cmp )) {
1042 assert( pos.pFound != nullptr );
1043 f( *pos.pFound, val );
1044 m_Stat.onFindSuccess();
1048 m_Stat.onFindFailed();
1052 template <typename Q, typename Compare>
1053 iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1056 if ( search( refHead, val, pos, cmp )) {
1057 assert( pos.pCur != nullptr );
1058 assert( pos.pFound != nullptr );
1059 m_Stat.onFindSuccess();
1060 return iterator( pos.pCur, pos.pFound );
1063 m_Stat.onFindFailed();
1067 template <typename Q, typename Compare>
1068 bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const
1071 if ( search( refHead, val, pos, cmp )) {
1072 guard.set( pos.pFound );
1073 m_Stat.onFindSuccess();
1077 m_Stat.onFindFailed();
1085 template <typename Q, typename Compare >
1086 bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const
1088 atomic_node_ptr* pHead = const_cast<atomic_node_ptr*>( &refHead );
1089 node_type * pPrev = nullptr;
1092 node_type * pCur = pHead->load( memory_model::memory_order_relaxed );
1094 if ( pCur == nullptr ) {
1099 pos.pFound = nullptr;
1103 value_type * pVal = pos.guard.protect( pCur->data );
1106 int nCmp = cmp( *pVal, val );
1117 pHead = &( pCur->next );
1124 node_type * alloc_node( value_type * pVal )
1126 m_Stat.onNodeCreated();
1127 return cxx_node_allocator().New( pVal );
1130 void delete_node( node_type * pNode )
1132 m_Stat.onNodeRemoved();
1133 cxx_node_allocator().Delete( pNode );
1136 static void retire_data( value_type * pVal )
1138 assert( pVal != nullptr );
1139 gc::template retire<disposer>( pVal );
1144 node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed );
1146 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed );
1148 retire_data( pVal );
1149 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1150 delete_node( pNode );
1155 bool link_node( value_type * pVal, position& pos )
1158 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
1160 value_type * p = nullptr;
1161 return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed );
1164 // insert new node between pos.pPrev and pos.pCur
1165 node_type * pNode = alloc_node( pVal );
1166 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1168 if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
1171 delete_node( pNode );
1175 node_type * pNode = alloc_node( pVal );
1176 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1177 if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) )
1180 delete_node( pNode );
1185 static bool unlink_node( position& pos )
1187 assert( pos.pCur != nullptr );
1188 assert( pos.pFound != nullptr );
1190 if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1191 retire_data( pos.pFound );
1199 }} // namespace cds::intrusive
1201 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H