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
158 template <typename Stat>
159 using select_stat_wrapper = iterable_list::select_stat_wrapper< Stat >;
164 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
165 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
167 atomic_node_ptr m_pHead; ///< Head pointer
168 item_counter m_ItemCounter; ///< Item counter
169 mutable stat m_Stat; ///< Internal statistics
171 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
173 /// Position pointer for item search
175 atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead)
176 node_type * pPrev; ///< Previous node
177 node_type * pCur; ///< Current node
179 value_type * pFound; ///< Value of \p pCur->data, valid only if data found
180 typename gc::Guard guard; ///< guard for \p pFound
186 template <bool IsConst>
189 friend class IterableList;
193 typename gc::Guard m_Guard; // data guard
198 m_pNode = m_pNode->next.load( memory_model::memory_order_acquire );
203 if ( m_Guard.protect( m_pNode->data ))
208 explicit iterator_type( atomic_node_ptr const& pNode )
209 : m_pNode( pNode.load( memory_model::memory_order_acquire ))
212 if ( !m_Guard.protect( m_pNode->data ))
217 iterator_type( node_type* pNode, value_type* pVal )
221 assert( pVal != nullptr );
222 m_Guard.assign( pVal );
227 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
228 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 )
237 m_Guard.copy( src.m_Guard );
240 value_ptr operator ->() const
242 return m_Guard.template get<value_type>();
245 value_ref operator *() const
247 assert( m_Guard.get_native() != nullptr );
248 return *m_Guard.template get<value_type>();
252 iterator_type& operator ++()
258 iterator_type& operator = (iterator_type const& src)
260 m_pNode = src.m_pNode;
261 m_Guard.copy( src.m_Guard );
266 bool operator ==(iterator_type<C> const& i ) const
268 return m_pNode == i.m_pNode;
271 bool operator !=(iterator_type<C> const& i ) const
273 return !( *this == i );
279 ///@name Thread-safe forward iterators
283 The forward iterator for iterable list has some features:
284 - it has no post-increment operator
285 - to protect the value, the iterator contains a GC-specific guard.
286 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
287 may be thrown if the limit of guard count per thread is exceeded.
288 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
289 - Iterator is thread-safe: even if the element the iterator points to is removed, the iterator stays valid because
290 it contains the guard keeping the value from to be recycled.
292 The iterator interface:
296 // Default constructor
300 iterator( iterator const& src );
302 // Dereference operator
303 value_type * operator ->() const;
305 // Dereference operator
306 value_type& operator *() const;
308 // Preincrement operator
309 iterator& operator ++();
311 // Assignment operator
312 iterator& operator = (iterator const& src);
314 // Equality operators
315 bool operator ==(iterator const& i ) const;
316 bool operator !=(iterator const& i ) const;
320 @note For two iterators pointed to the same element the value can be different;
324 assert( &(*it1) == &(*it2) );
326 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
327 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
328 Other iterator can observe modified value of the element.
330 typedef iterator_type<false> iterator;
331 /// Const forward iterator
333 For iterator's features and requirements see \ref iterator
335 typedef iterator_type<true> const_iterator;
337 /// Returns a forward iterator addressing the first element in a list
339 For empty list \code begin() == end() \endcode
343 return iterator( m_pHead );
346 /// Returns an iterator that addresses the location succeeding the last element in a list
348 Do not use the value returned by <tt>end</tt> function to access any item.
349 Internally, <tt>end</tt> returning value equals to \p nullptr.
351 The returned value can be used only to control reaching the end of the list.
352 For empty list <tt>begin() == end()</tt>
359 /// Returns a forward const iterator addressing the first element in a list
360 const_iterator cbegin() const
362 return const_iterator( m_pHead );
365 /// Returns a forward const iterator addressing the first element in a list
366 const_iterator begin() const
368 return const_iterator( m_pHead );
371 /// Returns an const iterator that addresses the location succeeding the last element in a list
372 const_iterator end() const
374 return const_iterator();
377 /// Returns an const iterator that addresses the location succeeding the last element in a list
378 const_iterator cend() const
380 return const_iterator();
385 /// Default constructor initializes empty list
391 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
392 explicit IterableList( Stat& st )
398 /// Destroys the list object
406 The function inserts \p val into the list if the list does not contain
407 an item with key equal to \p val.
409 Returns \p true if \p val has been linked to the list, \p false otherwise.
411 bool insert( value_type& val )
413 return insert_at( m_pHead, val );
418 This function is intended for derived non-intrusive containers.
420 The function allows to split new item creating into two part:
421 - create item with key only
422 - insert new item into the list
423 - if inserting is success, calls \p f functor to initialize value-field of \p val.
425 The functor signature is:
427 void func( value_type& val );
429 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
430 \p val no any other changes could be made on this list's item by concurrent threads.
431 The user-defined functor is called only if the inserting is success.
433 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
435 template <typename Func>
436 bool insert( value_type& val, Func f )
438 return insert_at( m_pHead, val, f );
443 The operation performs inserting or changing data with lock-free manner.
445 If the item \p val is not found in the list, then \p val is inserted
446 iff \p bInsert is \p true.
447 Otherwise, the current element is changed to \p val, the element will be retired later
448 by call \p Traits::disposer.
449 The functor \p func is called after inserting or replacing, it signature is:
451 void func( value_type& val, value_type * old );
454 - \p val - argument \p val passed into the \p %update() function
455 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
457 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
458 \p second is \p true if \p val has been added or \p false if the item with that key
461 template <typename Func>
462 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
464 return update_at( m_pHead, val, func, bInsert );
469 The operation performs inserting or updating data with lock-free manner.
471 If the item \p val is not found in the list, then \p val is inserted
472 iff \p bInsert is \p true.
473 Otherwise, the current element is changed to \p val, the old element will be retired later
474 by call \p Traits::disposer.
476 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
477 \p second is \p true if \p val has been added or \p false if the item with that key
480 std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
482 return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
485 /// Unlinks the item \p val from the list
487 The function searches the item \p val in the list and unlinks it from the list
488 if it is found and it is equal to \p val.
490 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
491 and deletes the item found. \p %unlink() finds an item by key and deletes it
492 only if \p val is an item of the list, i.e. the pointer to item found
493 is equal to <tt> &val </tt>.
495 \p disposer specified in \p Traits is called for deleted item.
497 The function returns \p true if success and \p false otherwise.
499 bool unlink( value_type& val )
501 return unlink_at( m_pHead, val );
504 /// Deletes the item from the list
505 /** \anchor cds_intrusive_IterableList_hp_erase_val
506 The function searches an item with key equal to \p key in the list,
507 unlinks it from the list, and returns \p true.
508 If \p key is not found the function return \p false.
510 \p disposer specified in \p Traits is called for deleted item.
512 template <typename Q>
513 bool erase( Q const& key )
515 return erase_at( m_pHead, key, key_comparator());
518 /// Deletes the item from the list using \p pred predicate for searching
520 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
521 but \p pred is used for key comparing.
522 \p Less functor has the interface like \p std::less.
523 \p pred must imply the same element order as the comparator used for building the list.
525 \p disposer specified in \p Traits is called for deleted item.
527 template <typename Q, typename Less>
528 bool erase_with( Q const& key, Less pred )
531 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
534 /// Deletes the item from the list
535 /** \anchor cds_intrusive_IterableList_hp_erase_func
536 The function searches an item with key equal to \p key in the list,
537 call \p func functor with item found, unlinks it from the list, and returns \p true.
538 The \p Func interface is
541 void operator()( value_type const& item );
544 If \p key is not found the function return \p false, \p func is not called.
546 \p disposer specified in \p Traits is called for deleted item.
548 template <typename Q, typename Func>
549 bool erase( Q const& key, Func func )
551 return erase_at( m_pHead, key, key_comparator(), func );
554 /// Deletes the item from the list using \p pred predicate for searching
556 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
557 but \p pred is used for key comparing.
558 \p Less functor has the interface like \p std::less.
559 \p pred must imply the same element order as the comparator used for building the list.
561 \p disposer specified in \p Traits is called for deleted item.
563 template <typename Q, typename Less, typename Func>
564 bool erase_with( Q const& key, Less pred, Func f )
567 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
570 /// Extracts the item from the list with specified \p key
571 /** \anchor cds_intrusive_IterableList_hp_extract
572 The function searches an item with key equal to \p key,
573 unlinks it from the list, and returns it as \p guarded_ptr.
574 If \p key is not found returns an empty guarded pointer.
576 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
578 The \ref disposer specified in \p Traits class template parameter is called automatically
579 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
580 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
584 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
588 ord_list::guarded_ptr gp( theList.extract( 5 ));
593 // Destructor of gp releases internal HP guard
597 template <typename Q>
598 guarded_ptr extract( Q const& key )
600 return extract_at( m_pHead, key, key_comparator());
603 /// Extracts the item using compare functor \p pred
605 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
606 but \p pred predicate is used for key comparing.
608 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
610 \p pred must imply the same element order as the comparator used for building the list.
612 template <typename Q, typename Less>
613 guarded_ptr extract_with( Q const& key, Less pred )
616 return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
619 /// Finds \p key in the list
620 /** \anchor cds_intrusive_IterableList_hp_find_func
621 The function searches the item with key equal to \p key and calls the functor \p f for item found.
622 The interface of \p Func functor is:
625 void operator()( value_type& item, Q& key );
628 where \p item is the item found, \p key is the \p %find() function argument.
630 The functor may change non-key fields of \p item. Note that the function is only guarantee
631 that \p item cannot be disposed during functor is executing.
632 The function does not serialize simultaneous access to the \p item. If such access is
633 possible you must provide your own synchronization schema to keep out unsafe item modifications.
635 The function returns \p true if \p val is found, \p false otherwise.
637 template <typename Q, typename Func>
638 bool find( Q& key, Func f ) const
640 return find_at( m_pHead, key, key_comparator(), f );
643 template <typename Q, typename Func>
644 bool find( Q const& key, Func f ) const
646 return find_at( m_pHead, key, key_comparator(), f );
650 /// Finds \p key in the list and returns iterator pointed to the item found
652 If \p key is not found the function returns \p end().
654 template <typename Q>
655 iterator find( Q const& key ) const
657 return find_iterator_at( m_pHead, key, key_comparator());
660 /// Finds the \p key using \p pred predicate for searching
662 The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
663 but \p pred is used for key comparing.
664 \p Less functor has the interface like \p std::less.
665 \p pred must imply the same element order as the comparator used for building the list.
667 template <typename Q, typename Less, typename Func>
668 bool find_with( Q& key, Less pred, Func f ) const
671 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
674 template <typename Q, typename Less, typename Func>
675 bool find_with( Q const& key, Less pred, Func f ) const
678 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
682 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
684 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
685 \p Less functor has the interface like \p std::less.
686 \p pred must imply the same element order as the comparator used for building the list.
688 If \p key is not found the function returns \p end().
690 template <typename Q, typename Less>
691 iterator find_with( Q const& key, Less pred ) const
694 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
697 /// Checks whether the list contains \p key
699 The function searches the item with key equal to \p key
700 and returns \p true if it is found, and \p false otherwise.
702 template <typename Q>
703 bool contains( Q const& key ) const
705 return find_at( m_pHead, key, key_comparator());
708 /// Checks whether the list contains \p key using \p pred predicate for searching
710 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
711 \p Less functor has the interface like \p std::less.
712 \p Less must imply the same element order as the comparator used for building the list.
714 template <typename Q, typename Less>
715 bool contains( Q const& key, Less pred ) const
718 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
721 /// Finds the \p key and return the item found
722 /** \anchor cds_intrusive_IterableList_hp_get
723 The function searches the item with key equal to \p key
724 and returns it as \p guarded_ptr.
725 If \p key is not found the function returns an empty guarded pointer.
727 The \ref disposer specified in \p Traits class template parameter is called
728 by garbage collector \p GC automatically when returned \ref guarded_ptr object
729 will be destroyed or released.
730 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
734 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
738 ord_list::guarded_ptr gp(theList.get( 5 ));
743 // Destructor of guarded_ptr releases internal HP guard
747 Note the compare functor specified for \p Traits template parameter
748 should accept a parameter of type \p Q that can be not the same as \p value_type.
750 template <typename Q>
751 guarded_ptr get( Q const& key ) const
753 return get_at( m_pHead, key, key_comparator());
756 /// Finds the \p key and return the item found
758 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
759 but \p pred is used for comparing the keys.
761 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
763 \p pred must imply the same element order as the comparator used for building the list.
765 template <typename Q, typename Less>
766 guarded_ptr get_with( Q const& key, Less pred ) const
769 return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
772 /// Clears the list (thread safe, not atomic)
776 for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
778 pos.pFound = pos.guard.protect( pos.pCur->data );
781 if ( cds_likely( unlink_node( pos ))) {
789 /// Checks if the list is empty
791 Emptiness is checked by item counting: if item count is zero then the set is empty.
792 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
800 /// Returns list's item count
802 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
803 this function always returns 0.
807 return m_ItemCounter.value();
810 /// Returns const reference to internal statistics
811 stat const& statistics() const
819 // split-list support
820 bool insert_aux_node( node_type * pNode )
822 return insert_aux_node( m_pHead, pNode );
825 // split-list support
826 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
828 assert( pNode != nullptr );
830 // Hack: convert node_type to value_type.
831 // In principle, auxiliary node can be non-reducible to value_type
832 // We assume that comparator can correctly distinguish aux and regular node.
833 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
837 bool insert_at( atomic_node_ptr& refHead, value_type& val )
842 if ( search( refHead, val, pos, key_comparator() )) {
843 m_Stat.onInsertFailed();
847 if ( link_node( &val, pos ) ) {
849 m_Stat.onInsertSuccess();
853 m_Stat.onInsertRetry();
857 template <typename Func>
858 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
862 typename gc::Guard guard;
863 guard.assign( &val );
866 if ( search( refHead, val, pos, key_comparator() ) ) {
867 m_Stat.onInsertFailed();
871 if ( link_node( &val, pos ) ) {
874 m_Stat.onInsertSuccess();
878 m_Stat.onInsertRetry();
882 template <typename Func>
883 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
887 typename gc::Guard guard;
888 guard.assign( &val );
891 if ( search( refHead, val, pos, key_comparator() ) ) {
892 // try to replace pCur->data with val
893 assert( pos.pFound != nullptr );
894 assert( key_comparator()(*pos.pFound, val) == 0 );
896 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
897 if ( pos.pFound != &val ) {
898 retire_data( pos.pFound );
899 func( val, pos.pFound );
901 m_Stat.onUpdateExisting();
902 return std::make_pair( true, false );
907 m_Stat.onUpdateFailed();
908 return std::make_pair( false, false );
911 if ( link_node( &val, pos )) {
912 func( val, static_cast<value_type*>( nullptr ));
914 m_Stat.onUpdateNew();
915 return std::make_pair( true, true );
919 m_Stat.onUpdateRetry();
923 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
928 while ( search( refHead, val, pos, key_comparator())) {
929 if ( pos.pFound == &val ) {
930 if ( unlink_node( pos )) {
932 m_Stat.onEraseSuccess();
941 m_Stat.onEraseRetry();
944 m_Stat.onEraseFailed();
948 template <typename Q, typename Compare, typename Func>
949 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
952 while ( search( refHead, val, pos, cmp )) {
953 if ( unlink_node( pos )) {
956 m_Stat.onEraseSuccess();
962 m_Stat.onEraseRetry();
965 m_Stat.onEraseFailed();
969 template <typename Q, typename Compare, typename Func>
970 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
973 return erase_at( refHead, val, cmp, f, pos );
976 template <typename Q, typename Compare>
977 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
980 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
983 template <typename Q, typename Compare>
984 guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
988 while ( search( refHead, val, pos, cmp )) {
989 if ( unlink_node( pos )) {
991 m_Stat.onEraseSuccess();
992 assert( pos.pFound != nullptr );
993 return guarded_ptr( std::move( pos.guard ));
998 m_Stat.onEraseRetry();
1001 m_Stat.onEraseFailed();
1002 return guarded_ptr();
1005 template <typename Q, typename Compare>
1006 bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1009 if ( search( refHead, val, pos, cmp ) ) {
1010 m_Stat.onFindSuccess();
1014 m_Stat.onFindFailed();
1018 template <typename Q, typename Compare, typename Func>
1019 bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const
1022 if ( search( refHead, val, pos, cmp )) {
1023 assert( pos.pFound != nullptr );
1024 f( *pos.pFound, val );
1025 m_Stat.onFindSuccess();
1029 m_Stat.onFindFailed();
1033 template <typename Q, typename Compare>
1034 iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1037 if ( search( refHead, val, pos, cmp )) {
1038 assert( pos.pCur != nullptr );
1039 assert( pos.pFound != nullptr );
1040 m_Stat.onFindSuccess();
1041 return iterator( pos.pCur, pos.pFound );
1044 m_Stat.onFindFailed();
1048 template <typename Q, typename Compare>
1049 guarded_ptr get_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1052 if ( search( refHead, val, pos, cmp )) {
1053 m_Stat.onFindSuccess();
1054 return guarded_ptr( std::move( pos.guard ));
1057 m_Stat.onFindFailed();
1058 return guarded_ptr();
1065 template <typename Q, typename Compare >
1066 bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const
1068 atomic_node_ptr* pHead = const_cast<atomic_node_ptr*>( &refHead );
1069 node_type * pPrev = nullptr;
1072 node_type * pCur = pHead->load( memory_model::memory_order_relaxed );
1074 if ( pCur == nullptr ) {
1079 pos.pFound = nullptr;
1083 value_type * pVal = pos.guard.protect( pCur->data );
1086 int nCmp = cmp( *pVal, val );
1097 pHead = &( pCur->next );
1104 node_type * alloc_node( value_type * pVal )
1106 m_Stat.onNodeCreated();
1107 return cxx_node_allocator().New( pVal );
1110 void delete_node( node_type * pNode )
1112 m_Stat.onNodeRemoved();
1113 cxx_node_allocator().Delete( pNode );
1116 static void retire_data( value_type * pVal )
1118 assert( pVal != nullptr );
1119 gc::template retire<disposer>( pVal );
1124 node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed );
1126 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed );
1128 retire_data( pVal );
1129 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1130 delete_node( pNode );
1135 bool link_node( value_type * pVal, position& pos )
1138 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
1140 value_type * p = nullptr;
1141 return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed );
1144 // insert new node between pos.pPrev and pos.pCur
1145 node_type * pNode = alloc_node( pVal );
1146 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1148 if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
1151 delete_node( pNode );
1155 node_type * pNode = alloc_node( pVal );
1156 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1157 if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) )
1160 delete_node( pNode );
1165 static bool unlink_node( position& pos )
1167 assert( pos.pCur != nullptr );
1168 assert( pos.pFound != nullptr );
1170 if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1171 retire_data( pos.pFound );
1179 }} // namespace cds::intrusive
1181 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H