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 >;
163 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
164 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
166 atomic_node_ptr m_pHead; ///< Head pointer
167 item_counter m_ItemCounter; ///< Item counter
168 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;
194 typename gc::Guard m_Guard; // for m_pVal
199 m_pNode = m_pNode->next.load( memory_model::memory_order_relaxed );
202 m_pVal = m_Guard.protect( m_pNode->data );
208 explicit iterator_type( atomic_node_ptr const& pNode )
209 : m_pNode( pNode.load( memory_model::memory_order_relaxed ))
213 m_pVal = m_Guard.protect( m_pNode->data );
219 iterator_type( node_type* pNode, value_type* pVal )
224 assert( pVal != nullptr );
225 m_Guard.assign( pVal );
230 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
231 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
238 iterator_type( iterator_type const& src )
239 : m_pNode( src.m_pNode )
240 , m_pVal( src.m_pVal )
242 m_Guard.assign( m_pVal );
245 value_ptr operator ->() const
250 value_ref operator *() const
252 assert( m_pVal != nullptr );
257 iterator_type& operator ++()
263 iterator_type& operator = (iterator_type const& src)
265 m_pNode = src.m_pNode;
267 m_Guard.assign( m_pVal );
272 bool operator ==(iterator_type<C> const& i ) const
274 return m_pNode == i.m_pNode;
277 bool operator !=(iterator_type<C> const& i ) const
279 return m_pNode != i.m_pNode;
285 ///@name Thread-safe forward iterators
289 The forward iterator for iterable list has some features:
290 - it has no post-increment operator
291 - to protect the value, the iterator contains a GC-specific guard.
292 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
293 may be thrown if the limit of guard count per thread is exceeded.
294 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
295 - Iterator is thread-safe: even if the element the iterator points to is removed, the iterator stays valid because
296 it contains the guard keeping the value from to be recycled.
298 The iterator interface:
302 // Default constructor
306 iterator( iterator const& src );
308 // Dereference operator
309 value_type * operator ->() const;
311 // Dereference operator
312 value_type& operator *() const;
314 // Preincrement operator
315 iterator& operator ++();
317 // Assignment operator
318 iterator& operator = (iterator const& src);
320 // Equality operators
321 bool operator ==(iterator const& i ) const;
322 bool operator !=(iterator const& i ) const;
326 @note For two iterators pointed to the same element the value can be different;
330 assert( &(*it1) == &(*it2) );
332 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
333 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
334 Other iterator can observe modified value of the element.
336 typedef iterator_type<false> iterator;
337 /// Const forward iterator
339 For iterator's features and requirements see \ref iterator
341 typedef iterator_type<true> const_iterator;
343 /// Returns a forward iterator addressing the first element in a list
345 For empty list \code begin() == end() \endcode
349 return iterator( m_pHead );
352 /// Returns an iterator that addresses the location succeeding the last element in a list
354 Do not use the value returned by <tt>end</tt> function to access any item.
355 Internally, <tt>end</tt> returning value equals to \p nullptr.
357 The returned value can be used only to control reaching the end of the list.
358 For empty list <tt>begin() == end()</tt>
365 /// Returns a forward const iterator addressing the first element in a list
366 const_iterator cbegin() const
368 return const_iterator( m_pHead );
371 /// Returns a forward const iterator addressing the first element in a list
372 const_iterator begin() const
374 return const_iterator( m_pHead );
377 /// Returns an const iterator that addresses the location succeeding the last element in a list
378 const_iterator end() const
380 return const_iterator();
383 /// Returns an const iterator that addresses the location succeeding the last element in a list
384 const_iterator cend() const
386 return const_iterator();
391 /// Default constructor initializes empty list
397 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
398 explicit IterableList( Stat& st )
404 /// Destroys the list object
412 The function inserts \p val into the list if the list does not contain
413 an item with key equal to \p val.
415 Returns \p true if \p val has been linked to the list, \p false otherwise.
417 bool insert( value_type& val )
419 return insert_at( m_pHead, val );
424 This function is intended for derived non-intrusive containers.
426 The function allows to split new item creating into two part:
427 - create item with key only
428 - insert new item into the list
429 - if inserting is success, calls \p f functor to initialize value-field of \p val.
431 The functor signature is:
433 void func( value_type& val );
435 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
436 \p val no any other changes could be made on this list's item by concurrent threads.
437 The user-defined functor is called only if the inserting is success.
439 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
441 template <typename Func>
442 bool insert( value_type& val, Func f )
444 return insert_at( m_pHead, val, f );
449 The operation performs inserting or changing data with lock-free manner.
451 If the item \p val is not found in the list, then \p val is inserted
452 iff \p bInsert is \p true.
453 Otherwise, the current element is changed to \p val, the element will be retired later
454 by call \p Traits::disposer.
455 The functor \p func is called after inserting or replacing, it signature is:
457 void func( value_type& val, value_type * old );
460 - \p val - argument \p val passed into the \p %update() function
461 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
463 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
464 \p second is \p true if \p val has been added or \p false if the item with that key
467 template <typename Func>
468 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
470 return update_at( m_pHead, val, func, bInsert );
475 The operation performs inserting or updating data with lock-free manner.
477 If the item \p val is not found in the list, then \p val is inserted
478 iff \p bInsert is \p true.
479 Otherwise, the current element is changed to \p val, the old element will be retired later
480 by call \p Traits::disposer.
482 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
483 \p second is \p true if \p val has been added or \p false if the item with that key
486 std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
488 return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
491 /// Unlinks the item \p val from the list
493 The function searches the item \p val in the list and unlinks it from the list
494 if it is found and it is equal to \p val.
496 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
497 and deletes the item found. \p %unlink() finds an item by key and deletes it
498 only if \p val is an item of the list, i.e. the pointer to item found
499 is equal to <tt> &val </tt>.
501 \p disposer specified in \p Traits is called for deleted item.
503 The function returns \p true if success and \p false otherwise.
505 bool unlink( value_type& val )
507 return unlink_at( m_pHead, val );
510 /// Deletes the item from the list
511 /** \anchor cds_intrusive_IterableList_hp_erase_val
512 The function searches an item with key equal to \p key in the list,
513 unlinks it from the list, and returns \p true.
514 If \p key is not found the function return \p false.
516 \p disposer specified in \p Traits is called for deleted item.
518 template <typename Q>
519 bool erase( Q const& key )
521 return erase_at( m_pHead, key, key_comparator());
524 /// Deletes the item from the list using \p pred predicate for searching
526 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
527 but \p pred is used for key comparing.
528 \p Less functor has the interface like \p std::less.
529 \p pred must imply the same element order as the comparator used for building the list.
531 \p disposer specified in \p Traits is called for deleted item.
533 template <typename Q, typename Less>
534 bool erase_with( Q const& key, Less pred )
537 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
540 /// Deletes the item from the list
541 /** \anchor cds_intrusive_IterableList_hp_erase_func
542 The function searches an item with key equal to \p key in the list,
543 call \p func functor with item found, unlinks it from the list, and returns \p true.
544 The \p Func interface is
547 void operator()( value_type const& item );
550 If \p key is not found the function return \p false, \p func is not called.
552 \p disposer specified in \p Traits is called for deleted item.
554 template <typename Q, typename Func>
555 bool erase( Q const& key, Func func )
557 return erase_at( m_pHead, key, key_comparator(), func );
560 /// Deletes the item from the list using \p pred predicate for searching
562 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
563 but \p pred is used for key comparing.
564 \p Less functor has the interface like \p std::less.
565 \p pred must imply the same element order as the comparator used for building the list.
567 \p disposer specified in \p Traits is called for deleted item.
569 template <typename Q, typename Less, typename Func>
570 bool erase_with( Q const& key, Less pred, Func f )
573 return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
576 /// Extracts the item from the list with specified \p key
577 /** \anchor cds_intrusive_IterableList_hp_extract
578 The function searches an item with key equal to \p key,
579 unlinks it from the list, and returns it as \p guarded_ptr.
580 If \p key is not found returns an empty guarded pointer.
582 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
584 The \ref disposer specified in \p Traits class template parameter is called automatically
585 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
586 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
590 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
594 ord_list::guarded_ptr gp(theList.extract( 5 ));
599 // Destructor of gp releases internal HP guard
603 template <typename Q>
604 guarded_ptr extract( Q const& key )
607 extract_at( m_pHead, gp.guard(), key, key_comparator());
611 /// Extracts the item using compare functor \p pred
613 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
614 but \p pred predicate is used for key comparing.
616 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
618 \p pred must imply the same element order as the comparator used for building the list.
620 template <typename Q, typename Less>
621 guarded_ptr extract_with( Q const& key, Less pred )
625 extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
629 /// Finds \p key in the list
630 /** \anchor cds_intrusive_IterableList_hp_find_func
631 The function searches the item with key equal to \p key and calls the functor \p f for item found.
632 The interface of \p Func functor is:
635 void operator()( value_type& item, Q& key );
638 where \p item is the item found, \p key is the \p %find() function argument.
640 The functor may change non-key fields of \p item. Note that the function is only guarantee
641 that \p item cannot be disposed during functor is executing.
642 The function does not serialize simultaneous access to the \p item. If such access is
643 possible you must provide your own synchronization schema to keep out unsafe item modifications.
645 The function returns \p true if \p val is found, \p false otherwise.
647 template <typename Q, typename Func>
648 bool find( Q& key, Func f ) const
650 return find_at( m_pHead, key, key_comparator(), f );
653 template <typename Q, typename Func>
654 bool find( Q const& key, Func f ) const
656 return find_at( m_pHead, key, key_comparator(), f );
660 /// Finds \p key in the list and returns iterator pointed to the item found
662 If \p key is not found the function returns \p end().
664 template <typename Q>
665 iterator find( Q& key ) const
667 return find_iterator_at( m_pHead, key, key_comparator());
670 template <typename Q>
671 iterator find( Q const& key ) const
673 return find_iterator_at( m_pHead, key, key_comparator() );
677 /// Finds the \p key using \p pred predicate for searching
679 The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
680 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 template <typename Q, typename Less, typename Func>
685 bool find_with( Q& key, Less pred, Func f ) const
688 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
691 template <typename Q, typename Less, typename Func>
692 bool find_with( Q const& key, Less pred, Func f ) const
695 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
699 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
701 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
702 \p Less functor has the interface like \p std::less.
703 \p pred must imply the same element order as the comparator used for building the list.
705 If \p key is not found the function returns \p end().
707 template <typename Q, typename Less>
708 iterator find_with( Q& key, Less pred ) const
711 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
714 template <typename Q, typename Less>
715 iterator find_with( Q const& key, Less pred ) const
718 return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
722 /// Checks whether the list contains \p key
724 The function searches the item with key equal to \p key
725 and returns \p true if it is found, and \p false otherwise.
727 template <typename Q>
728 bool contains( Q const& key ) const
730 return find_at( m_pHead, key, key_comparator());
733 /// Checks whether the list contains \p key using \p pred predicate for searching
735 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
736 \p Less functor has the interface like \p std::less.
737 \p Less must imply the same element order as the comparator used for building the list.
739 template <typename Q, typename Less>
740 bool contains( Q const& key, Less pred ) const
743 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
746 /// Finds the \p key and return the item found
747 /** \anchor cds_intrusive_IterableList_hp_get
748 The function searches the item with key equal to \p key
749 and returns it as \p guarded_ptr.
750 If \p key is not found the function returns an empty guarded pointer.
752 The \ref disposer specified in \p Traits class template parameter is called
753 by garbage collector \p GC automatically when returned \ref guarded_ptr object
754 will be destroyed or released.
755 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
759 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
763 ord_list::guarded_ptr gp(theList.get( 5 ));
768 // Destructor of guarded_ptr releases internal HP guard
772 Note the compare functor specified for \p Traits template parameter
773 should accept a parameter of type \p Q that can be not the same as \p value_type.
775 template <typename Q>
776 guarded_ptr get( Q const& key ) const
779 get_at( m_pHead, gp.guard(), key, key_comparator());
783 /// Finds the \p key and return the item found
785 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
786 but \p pred is used for comparing the keys.
788 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
790 \p pred must imply the same element order as the comparator used for building the list.
792 template <typename Q, typename Less>
793 guarded_ptr get_with( Q const& key, Less pred ) const
797 get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
801 /// Clears the list (thread safe, not atomic)
805 for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
807 pos.pFound = pos.guard.protect( pos.pCur->data );
810 if ( cds_likely( unlink_node( pos ))) {
818 /// Checks if the list is empty
820 Emptiness is checked by item counting: if item count is zero then the set is empty.
821 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
829 /// Returns list's item count
831 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
832 this function always returns 0.
836 return m_ItemCounter.value();
839 /// Returns const reference to internal statistics
840 stat const& statistics() const
848 // split-list support
849 bool insert_aux_node( node_type * pNode )
851 return insert_aux_node( m_pHead, pNode );
854 // split-list support
855 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
857 assert( pNode != nullptr );
859 // Hack: convert node_type to value_type.
860 // In principle, auxiliary node can be non-reducible to value_type
861 // We assume that comparator can correctly distinguish aux and regular node.
862 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
866 bool insert_at( atomic_node_ptr& refHead, value_type& val )
871 if ( search( refHead, val, pos, key_comparator() )) {
872 m_Stat.onInsertFailed();
876 if ( link_node( &val, pos ) ) {
878 m_Stat.onInsertSuccess();
882 m_Stat.onInsertRetry();
886 template <typename Func>
887 bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
891 typename gc::Guard guard;
892 guard.assign( &val );
895 if ( search( refHead, val, pos, key_comparator() ) ) {
896 m_Stat.onInsertFailed();
900 if ( link_node( &val, pos ) ) {
903 m_Stat.onInsertSuccess();
907 m_Stat.onInsertRetry();
911 template <typename Func>
912 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
916 typename gc::Guard guard;
917 guard.assign( &val );
920 if ( search( refHead, val, pos, key_comparator() ) ) {
921 // try to replace pCur->data with val
922 assert( pos.pFound != nullptr );
923 assert( key_comparator()(*pos.pFound, val) == 0 );
925 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
926 if ( pos.pFound != &val ) {
927 retire_data( pos.pFound );
928 func( val, pos.pFound );
930 m_Stat.onUpdateExisting();
931 return std::make_pair( true, false );
936 m_Stat.onUpdateFailed();
937 return std::make_pair( false, false );
940 if ( link_node( &val, pos )) {
941 func( val, static_cast<value_type*>( nullptr ));
943 m_Stat.onUpdateNew();
944 return std::make_pair( true, true );
948 m_Stat.onUpdateRetry();
952 bool unlink_at( atomic_node_ptr& refHead, value_type& val )
957 while ( search( refHead, val, pos, key_comparator())) {
958 if ( pos.pFound == &val ) {
959 if ( unlink_node( pos )) {
961 m_Stat.onEraseSuccess();
970 m_Stat.onEraseRetry();
973 m_Stat.onEraseFailed();
977 template <typename Q, typename Compare, typename Func>
978 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
981 while ( search( refHead, val, pos, cmp )) {
982 if ( unlink_node( pos )) {
985 m_Stat.onEraseSuccess();
991 m_Stat.onEraseRetry();
994 m_Stat.onEraseFailed();
998 template <typename Q, typename Compare, typename Func>
999 bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1002 return erase_at( refHead, val, cmp, f, pos );
1005 template <typename Q, typename Compare>
1006 bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1009 return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1012 template <typename Q, typename Compare>
1013 bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1017 while ( search( refHead, val, pos, cmp )) {
1018 if ( unlink_node( pos )) {
1019 dest.set( pos.pFound );
1021 m_Stat.onEraseSuccess();
1027 m_Stat.onEraseRetry();
1030 m_Stat.onEraseFailed();
1034 template <typename Q, typename Compare>
1035 bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1038 if ( search( refHead, val, pos, cmp ) ) {
1039 m_Stat.onFindSuccess();
1043 m_Stat.onFindFailed();
1047 template <typename Q, typename Compare, typename Func>
1048 bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const
1051 if ( search( refHead, val, pos, cmp )) {
1052 assert( pos.pFound != nullptr );
1053 f( *pos.pFound, val );
1054 m_Stat.onFindSuccess();
1058 m_Stat.onFindFailed();
1062 template <typename Q, typename Compare>
1063 iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1066 if ( search( refHead, val, pos, cmp )) {
1067 assert( pos.pCur != nullptr );
1068 assert( pos.pFound != nullptr );
1069 m_Stat.onFindSuccess();
1070 return iterator( pos.pCur, pos.pFound );
1073 m_Stat.onFindFailed();
1077 template <typename Q, typename Compare>
1078 bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const
1081 if ( search( refHead, val, pos, cmp )) {
1082 guard.set( pos.pFound );
1083 m_Stat.onFindSuccess();
1087 m_Stat.onFindFailed();
1095 template <typename Q, typename Compare >
1096 bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const
1098 atomic_node_ptr* pHead = const_cast<atomic_node_ptr*>( &refHead );
1099 node_type * pPrev = nullptr;
1102 node_type * pCur = pHead->load( memory_model::memory_order_relaxed );
1104 if ( pCur == nullptr ) {
1109 pos.pFound = nullptr;
1113 value_type * pVal = pos.guard.protect( pCur->data );
1116 int nCmp = cmp( *pVal, val );
1127 pHead = &( pCur->next );
1134 node_type * alloc_node( value_type * pVal )
1136 m_Stat.onNodeCreated();
1137 return cxx_node_allocator().New( pVal );
1140 void delete_node( node_type * pNode )
1142 m_Stat.onNodeRemoved();
1143 cxx_node_allocator().Delete( pNode );
1146 static void retire_data( value_type * pVal )
1148 assert( pVal != nullptr );
1149 gc::template retire<disposer>( pVal );
1154 node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed );
1156 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed );
1158 retire_data( pVal );
1159 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1160 delete_node( pNode );
1165 bool link_node( value_type * pVal, position& pos )
1168 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
1170 value_type * p = nullptr;
1171 return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed );
1174 // insert new node between pos.pPrev and pos.pCur
1175 node_type * pNode = alloc_node( pVal );
1176 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1178 if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
1181 delete_node( pNode );
1185 node_type * pNode = alloc_node( pVal );
1186 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1187 if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) )
1190 delete_node( pNode );
1195 static bool unlink_node( position& pos )
1197 assert( pos.pCur != nullptr );
1198 assert( pos.pFound != nullptr );
1200 if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1201 retire_data( pos.pFound );
1209 }} // namespace cds::intrusive
1211 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H