2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 non-blocking list implementation supports thread-safe iterators;
44 searching and removing are lock-free, inserting is non-blocking because it
45 uses a light-weight synchronization based on marked pointers.
47 Unlike \p cds::intrusive::MichaelList the iterable list does not require
48 any hook in \p T to be stored in the list.
50 Usually, ordered single-linked list is used as a building block for the hash table implementation.
51 Iterable list is suitable for almost append-only hash table because the list doesn't delete
52 its internal node when erasing a key but it is marked them as empty to be reused in the future.
53 However, plenty of empty nodes degrades performance.
54 Separation of internal nodes and user data implies the need for an allocator for internal node
55 so the iterable list is not fully intrusive. Nevertheless, if you need thread-safe iterator,
56 the iterable list is good choice.
58 The complexity of searching is <tt>O(N)</tt>.
61 - \p GC - Garbage collector used.
62 - \p T - type to be stored in the list.
63 - \p Traits - type traits, default is \p iterable_list::traits. It is possible to declare option-based
64 list with \p cds::intrusive::iterable_list::make_traits metafunction:
65 For example, the following traits-based declaration of \p gc::HP iterable list
67 #include <cds/intrusive/iterable_list_hp.h>
68 // Declare item stored in your list
75 // Declare comparator for the item
77 int operator()( foo const& i1, foo const& i2 ) const
79 return i1.nKey - i2.nKey;
84 struct my_traits: public cds::intrusive::iterable_list::traits
86 typedef my_compare compare;
90 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > list_type;
92 is equivalent for the following option-based list
94 #include <cds/intrusive/iterable_list_hp.h>
96 // foo struct and my_compare are the same
98 // Declare option-based list
99 typedef cds::intrusive::IterableList< cds::gc::HP, foo,
100 typename cds::intrusive::iterable_list::make_traits<
101 cds::intrusive::opt::compare< my_compare > // item comparator option
107 There are different specializations of this template for each garbage collecting schema.
108 You should select GC you want and include appropriate .h-file:
109 - for \p gc::HP: <tt> <cds/intrusive/iterable_list_hp.h> </tt>
110 - for \p gc::DHP: <tt> <cds/intrusive/iterable_list_dhp.h> </tt>
115 #ifdef CDS_DOXYGEN_INVOKED
116 ,class Traits = iterable_list::traits
122 #ifndef CDS_DOXYGEN_INVOKED
123 : public iterable_list_tag
127 typedef T value_type; ///< type of value stored in the list
128 typedef Traits traits; ///< Traits template parameter
130 typedef iterable_list::node< value_type > node_type; ///< node type
132 # ifdef CDS_DOXYGEN_INVOKED
133 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
135 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
138 typedef typename traits::disposer disposer; ///< disposer for \p value_type
140 typedef GC gc; ///< Garbage collector
141 typedef typename traits::back_off back_off; ///< back-off strategy
142 typedef typename traits::item_counter item_counter; ///< Item counting policy used
143 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
144 typedef typename traits::node_allocator node_allocator; ///< Node allocator
145 typedef typename traits::stat stat; ///< Internal statistics
147 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
149 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
152 // Rebind traits (split-list support)
153 template <typename... Options>
154 struct rebind_traits {
155 typedef IterableList<
158 , typename cds::opt::make_options< traits, Options...>::type
163 template <typename Stat>
164 using select_stat_wrapper = iterable_list::select_stat_wrapper< Stat >;
169 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
170 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
171 typedef typename node_type::marked_data_ptr marked_data_ptr;
176 item_counter m_ItemCounter; ///< Item counter
177 mutable stat m_Stat; ///< Internal statistics
179 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
181 /// Position pointer for item search
183 node_type const* pHead;
184 node_type * pPrev; ///< Previous node
185 node_type * pCur; ///< Current node
187 value_type * pFound; ///< Value of \p pCur->data, valid only if data found
189 typename gc::Guard guard; ///< guard for \p pFound
192 struct insert_position: public position
194 value_type * pPrevVal; ///< Value of \p pPrev->data, can be \p nullptr
195 typename gc::Guard prevGuard; ///< guard for \p pPrevVal
201 template <bool IsConst>
204 friend class IterableList;
207 node_type const* m_pNode;
208 typename gc::Guard m_Guard; // data guard
212 for ( node_type* p = m_pNode->next.load( memory_model::memory_order_relaxed ); p != m_pNode; p = p->next.load( memory_model::memory_order_relaxed ))
215 if ( m_Guard.protect( p->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
221 explicit iterator_type( node_type const* pNode )
224 if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
228 iterator_type( node_type const* pNode, value_type* pVal )
232 assert( pVal != nullptr );
233 m_Guard.assign( pVal );
238 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
239 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
245 iterator_type( iterator_type const& src )
246 : m_pNode( src.m_pNode )
248 m_Guard.copy( src.m_Guard );
251 value_ptr operator ->() const
253 return m_Guard.template get<value_type>();
256 value_ref operator *() const
258 assert( m_Guard.get_native() != nullptr );
259 return *m_Guard.template get<value_type>();
263 iterator_type& operator ++()
269 iterator_type& operator = (iterator_type const& src)
271 m_pNode = src.m_pNode;
272 m_Guard.copy( src.m_Guard );
277 bool operator ==(iterator_type<C> const& i ) const
279 return m_pNode == i.m_pNode;
282 bool operator !=(iterator_type<C> const& i ) const
284 return !( *this == i );
290 ///@name Thread-safe forward iterators
294 The forward iterator for iterable list has some features:
295 - it has no post-increment operator
296 - to protect the value, the iterator contains a GC-specific guard.
297 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
298 may be thrown if the limit of guard count per thread is exceeded.
299 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
300 - Iterator is thread-safe: even if the element the iterator points to is removed, the iterator stays valid because
301 it contains the guard keeping the value from to be recycled.
303 The iterator interface:
307 // Default constructor
311 iterator( iterator const& src );
313 // Dereference operator
314 value_type * operator ->() const;
316 // Dereference operator
317 value_type& operator *() const;
319 // Preincrement operator
320 iterator& operator ++();
322 // Assignment operator
323 iterator& operator = (iterator const& src);
325 // Equality operators
326 bool operator ==(iterator const& i ) const;
327 bool operator !=(iterator const& i ) const;
331 @note For two iterators pointed to the same element the value can be different;
335 assert( &(*it1) == &(*it2));
337 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
338 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
339 Other iterator can observe modified value of the element.
341 typedef iterator_type<false> iterator;
342 /// Const forward iterator
344 For iterator's features and requirements see \ref iterator
346 typedef iterator_type<true> const_iterator;
348 /// Returns a forward iterator addressing the first element in a list
350 For empty list \code begin() == end() \endcode
354 return iterator( &m_Head );
357 /// Returns an iterator that addresses the location succeeding the last element in a list
359 Do not use the value returned by <tt>end</tt> function to access any item.
360 Internally, <tt>end</tt> returning value equals to \p nullptr.
362 The returned value can be used only to control reaching the end of the list.
363 For empty list <tt>begin() == end()</tt>
367 return iterator( &m_Tail );
370 /// Returns a forward const iterator addressing the first element in a list
371 const_iterator cbegin() const
373 return const_iterator( &m_Head );
376 /// Returns a forward const iterator addressing the first element in a list
377 const_iterator begin() const
379 return const_iterator( &m_Head );
382 /// Returns an const iterator that addresses the location succeeding the last element in a list
383 const_iterator end() const
385 return const_iterator( &m_Tail );
388 /// Returns an const iterator that addresses the location succeeding the last element in a list
389 const_iterator cend() const
391 return const_iterator( &m_Tail );
396 /// Default constructor initializes empty list
403 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
404 explicit IterableList( Stat& st )
411 /// Destroys the list object
419 The function inserts \p val into the list if the list does not contain
420 an item with key equal to \p val.
422 Returns \p true if \p val has been linked to the list, \p false otherwise.
424 bool insert( value_type& val )
426 return insert_at( &m_Head, val );
431 This function is intended for derived non-intrusive containers.
433 The function allows to split new item creating into two part:
434 - create item with key only
435 - insert new item into the list
436 - if inserting is success, calls \p f functor to initialize value-field of \p val.
438 The functor signature is:
440 void func( value_type& val );
442 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
443 \p val no any other changes could be made on this list's item by concurrent threads.
444 The user-defined functor is called only if the inserting is success.
446 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
448 template <typename Func>
449 bool insert( value_type& val, Func f )
451 return insert_at( &m_Head, val, f );
456 The operation performs inserting or changing data with lock-free manner.
458 If the item \p val is not found in the list, then \p val is inserted
459 iff \p bInsert is \p true.
460 Otherwise, the current element is changed to \p val, the element will be retired later
461 by call \p Traits::disposer.
462 The functor \p func is called after inserting or replacing, it signature is:
464 void func( value_type& val, value_type * old );
467 - \p val - argument \p val passed into the \p %update() function
468 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
470 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
471 \p second is \p true if \p val has been added or \p false if the item with that key
474 template <typename Func>
475 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
477 return update_at( &m_Head, val, func, bInsert );
482 The operation performs inserting or updating data with lock-free manner.
484 If the item \p val is not found in the list, then \p val is inserted
485 iff \p bInsert is \p true.
486 Otherwise, the current element is changed to \p val, the old element will be retired later
487 by call \p Traits::disposer.
489 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
490 \p second is \p true if \p val has been added or \p false if the item with that key
493 std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
495 return upsert_at( &m_Head, val, bInsert );
498 /// Unlinks the item \p val from the list
500 The function searches the item \p val in the list and unlinks it from the list
501 if it is found and it is equal to \p val.
503 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
504 and deletes the item found. \p %unlink() finds an item by key and deletes it
505 only if \p val is an item of the list, i.e. the pointer to item found
506 is equal to <tt> &val </tt>.
508 \p disposer specified in \p Traits is called for deleted item.
510 The function returns \p true if success and \p false otherwise.
512 bool unlink( value_type& val )
514 return unlink_at( &m_Head, val );
517 /// Deletes the item from the list
518 /** \anchor cds_intrusive_IterableList_hp_erase_val
519 The function searches an item with key equal to \p key in the list,
520 unlinks it from the list, and returns \p true.
521 If \p key is not found the function return \p false.
523 \p disposer specified in \p Traits is called for deleted item.
525 template <typename Q>
526 bool erase( Q const& key )
528 return erase_at( &m_Head, key, key_comparator());
531 /// Deletes the item from the list using \p pred predicate for searching
533 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
534 but \p pred is used for key comparing.
535 \p Less functor has the interface like \p std::less.
536 \p pred must imply the same element order as the comparator used for building the list.
538 \p disposer specified in \p Traits is called for deleted item.
540 template <typename Q, typename Less>
541 bool erase_with( Q const& key, Less pred )
544 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
547 /// Deletes the item from the list
548 /** \anchor cds_intrusive_IterableList_hp_erase_func
549 The function searches an item with key equal to \p key in the list,
550 call \p func functor with item found, unlinks it from the list, and returns \p true.
551 The \p Func interface is
554 void operator()( value_type const& item );
557 If \p key is not found the function return \p false, \p func is not called.
559 \p disposer specified in \p Traits is called for deleted item.
561 template <typename Q, typename Func>
562 bool erase( Q const& key, Func func )
564 return erase_at( &m_Head, key, key_comparator(), func );
567 /// Deletes the item from the list using \p pred predicate for searching
569 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
570 but \p pred is used for key comparing.
571 \p Less functor has the interface like \p std::less.
572 \p pred must imply the same element order as the comparator used for building the list.
574 \p disposer specified in \p Traits is called for deleted item.
576 template <typename Q, typename Less, typename Func>
577 bool erase_with( Q const& key, Less pred, Func f )
580 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
583 /// Extracts the item from the list with specified \p key
584 /** \anchor cds_intrusive_IterableList_hp_extract
585 The function searches an item with key equal to \p key,
586 unlinks it from the list, and returns it as \p guarded_ptr.
587 If \p key is not found returns an empty guarded pointer.
589 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
591 The \ref disposer specified in \p Traits class template parameter is called automatically
592 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
593 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
597 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
601 ord_list::guarded_ptr gp( theList.extract( 5 ));
606 // Destructor of gp releases internal HP guard
610 template <typename Q>
611 guarded_ptr extract( Q const& key )
613 return extract_at( &m_Head, key, key_comparator());
616 /// Extracts the item using compare functor \p pred
618 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
619 but \p pred predicate is used for key comparing.
621 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
623 \p pred must imply the same element order as the comparator used for building the list.
625 template <typename Q, typename Less>
626 guarded_ptr extract_with( Q const& key, Less pred )
629 return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
632 /// Finds \p key in the list
633 /** \anchor cds_intrusive_IterableList_hp_find_func
634 The function searches the item with key equal to \p key and calls the functor \p f for item found.
635 The interface of \p Func functor is:
638 void operator()( value_type& item, Q& key );
641 where \p item is the item found, \p key is the \p %find() function argument.
643 The functor may change non-key fields of \p item. Note that the function is only guarantee
644 that \p item cannot be disposed during functor is executing.
645 The function does not serialize simultaneous access to the \p item. If such access is
646 possible you must provide your own synchronization schema to keep out unsafe item modifications.
648 The function returns \p true if \p val is found, \p false otherwise.
650 template <typename Q, typename Func>
651 bool find( Q& key, Func f ) const
653 return find_at( &m_Head, key, key_comparator(), f );
656 template <typename Q, typename Func>
657 bool find( Q const& key, Func f ) const
659 return find_at( &m_Head, key, key_comparator(), f );
663 /// Finds \p key in the list and returns iterator pointed to the item found
665 If \p key is not found the function returns \p end().
667 template <typename Q>
668 iterator find( Q const& key ) const
670 return find_iterator_at( &m_Head, 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_Head, 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_Head, 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 const& key, Less pred ) const
707 return find_iterator_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
710 /// Checks whether the list contains \p key
712 The function searches the item with key equal to \p key
713 and returns \p true if it is found, and \p false otherwise.
715 template <typename Q>
716 bool contains( Q const& key ) const
718 return find_at( &m_Head, key, key_comparator());
721 /// Checks whether the list contains \p key using \p pred predicate for searching
723 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
724 \p Less functor has the interface like \p std::less.
725 \p Less must imply the same element order as the comparator used for building the list.
727 template <typename Q, typename Less>
728 bool contains( Q const& key, Less pred ) const
731 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
734 /// Finds the \p key and return the item found
735 /** \anchor cds_intrusive_IterableList_hp_get
736 The function searches the item with key equal to \p key
737 and returns it as \p guarded_ptr.
738 If \p key is not found the function returns an empty guarded pointer.
740 The \ref disposer specified in \p Traits class template parameter is called
741 by garbage collector \p GC automatically when returned \ref guarded_ptr object
742 will be destroyed or released.
743 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
747 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
751 ord_list::guarded_ptr gp(theList.get( 5 ));
756 // Destructor of guarded_ptr releases internal HP guard
760 Note the compare functor specified for \p Traits template parameter
761 should accept a parameter of type \p Q that can be not the same as \p value_type.
763 template <typename Q>
764 guarded_ptr get( Q const& key ) const
766 return get_at( &m_Head, key, key_comparator());
769 /// Finds the \p key and return the item found
771 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
772 but \p pred is used for comparing the keys.
774 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
776 \p pred must imply the same element order as the comparator used for building the list.
778 template <typename Q, typename Less>
779 guarded_ptr get_with( Q const& key, Less pred ) const
782 return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
785 /// Clears the list (thread safe, not atomic)
790 for ( pos.pCur = m_Head.next.load( memory_model::memory_order_relaxed ); pos.pCur != pos.pPrev; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
792 pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr();
795 if ( cds_likely( unlink_data( pos ))) {
800 pos.pPrev = pos.pCur;
804 /// Checks if the list is empty
806 Emptiness is checked by item counting: if item count is zero then the set is empty.
807 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
815 /// Returns list's item count
817 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
818 this function always returns 0.
822 return m_ItemCounter.value();
825 /// Returns const reference to internal statistics
826 stat const& statistics() const
834 // split-list support
835 bool insert_aux_node( node_type * pNode )
837 return insert_aux_node( &m_Head, pNode );
840 // split-list support
841 bool insert_aux_node( node_type* pHead, node_type * pNode )
843 assert( pNode != nullptr );
844 assert( pNode->data.load( memory_model::memory_order_relaxed ) != nullptr );
849 if ( inserting_search( pHead, *pNode->data.load(memory_model::memory_order_relaxed).ptr(), pos, key_comparator())) {
850 m_Stat.onInsertFailed();
854 if ( link_aux_node( pNode, pos, pHead )) {
856 m_Stat.onInsertSuccess();
860 m_Stat.onInsertRetry();
864 bool insert_at( node_type* pHead, value_type& val )
869 if ( inserting_search( pHead, val, pos, key_comparator())) {
870 m_Stat.onInsertFailed();
874 if ( link_data( &val, pos, pHead )) {
876 m_Stat.onInsertSuccess();
880 m_Stat.onInsertRetry();
884 template <typename Func>
885 bool insert_at( node_type* pHead, value_type& val, Func f )
889 typename gc::Guard guard;
890 guard.assign( &val );
893 if ( inserting_search( pHead, val, pos, key_comparator())) {
894 m_Stat.onInsertFailed();
898 if ( link_data( &val, pos, pHead )) {
901 m_Stat.onInsertSuccess();
905 m_Stat.onInsertRetry();
909 template <typename Func>
910 std::pair<bool, bool> update_at( node_type* pHead, value_type& val, Func func, bool bInsert )
914 typename gc::Guard guard;
915 guard.assign( &val );
918 if ( inserting_search( pHead, val, pos, key_comparator())) {
919 // try to replace pCur->data with val
920 assert( pos.pFound != nullptr );
921 assert( key_comparator()(*pos.pFound, val) == 0 );
923 marked_data_ptr pFound( pos.pFound );
924 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ),
925 memory_model::memory_order_release, atomics::memory_order_relaxed )))
927 if ( pos.pFound != &val ) {
928 retire_data( pos.pFound );
929 func( val, pos.pFound );
931 m_Stat.onUpdateExisting();
932 return std::make_pair( true, false );
937 m_Stat.onUpdateFailed();
938 return std::make_pair( false, false );
941 if ( link_data( &val, pos, pHead )) {
942 func( val, static_cast<value_type*>( nullptr ));
944 m_Stat.onUpdateNew();
945 return std::make_pair( true, true );
949 m_Stat.onUpdateRetry();
953 std::pair<bool, bool> upsert_at( node_type* pHead, value_type& val, bool bInsert )
955 return update_at( pHead, val, []( value_type&, value_type* ) {}, bInsert );
958 bool unlink_at( node_type* pHead, value_type& val )
963 while ( search( pHead, val, pos, key_comparator())) {
964 if ( pos.pFound == &val ) {
965 if ( unlink_data( pos )) {
967 m_Stat.onEraseSuccess();
976 m_Stat.onEraseRetry();
979 m_Stat.onEraseFailed();
983 template <typename Q, typename Compare, typename Func>
984 bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos )
987 while ( search( pHead, val, pos, cmp )) {
988 if ( unlink_data( pos )) {
991 m_Stat.onEraseSuccess();
997 m_Stat.onEraseRetry();
1000 m_Stat.onEraseFailed();
1004 template <typename Q, typename Compare, typename Func>
1005 bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f )
1008 return erase_at( pHead, val, cmp, f, pos );
1011 template <typename Q, typename Compare>
1012 bool erase_at( node_type* pHead, Q const& val, Compare cmp )
1015 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1018 template <typename Q, typename Compare>
1019 guarded_ptr extract_at( node_type* pHead, Q const& val, Compare cmp )
1023 while ( search( pHead, val, pos, cmp )) {
1024 if ( unlink_data( pos )) {
1026 m_Stat.onEraseSuccess();
1027 assert( pos.pFound != nullptr );
1028 return guarded_ptr( std::move( pos.guard ));
1033 m_Stat.onEraseRetry();
1036 m_Stat.onEraseFailed();
1037 return guarded_ptr();
1040 template <typename Q, typename Compare>
1041 bool find_at( node_type const* pHead, Q const& val, Compare cmp ) const
1044 if ( search( pHead, val, pos, cmp )) {
1045 m_Stat.onFindSuccess();
1049 m_Stat.onFindFailed();
1053 template <typename Q, typename Compare, typename Func>
1054 bool find_at( node_type const* pHead, Q& val, Compare cmp, Func f ) const
1057 if ( search( pHead, val, pos, cmp )) {
1058 assert( pos.pFound != nullptr );
1059 f( *pos.pFound, val );
1060 m_Stat.onFindSuccess();
1064 m_Stat.onFindFailed();
1068 template <typename Q, typename Compare>
1069 iterator find_iterator_at( node_type const* pHead, Q const& val, Compare cmp ) const
1072 if ( search( pHead, val, pos, cmp )) {
1073 assert( pos.pCur != nullptr );
1074 assert( pos.pFound != nullptr );
1075 m_Stat.onFindSuccess();
1076 return iterator( pos.pCur, pos.pFound );
1079 m_Stat.onFindFailed();
1080 return iterator( &m_Tail );
1083 template <typename Q, typename Compare>
1084 guarded_ptr get_at( node_type const* pHead, Q const& val, Compare cmp ) const
1087 if ( search( pHead, val, pos, cmp )) {
1088 m_Stat.onFindSuccess();
1089 return guarded_ptr( std::move( pos.guard ));
1092 m_Stat.onFindFailed();
1093 return guarded_ptr();
1101 node_type const* head() const
1109 template <typename Q, typename Compare >
1110 bool search( node_type const* pHead, Q const& val, position& pos, Compare cmp ) const
1113 node_type* pPrev = const_cast<node_type*>( pHead );
1116 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1118 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1122 pos.pFound = nullptr;
1126 value_type * pVal = pos.guard.protect( pCur->data,
1127 []( marked_data_ptr p ) -> value_type*
1133 int const nCmp = cmp( *pVal, val );
1146 template <typename Q, typename Compare >
1147 bool inserting_search( node_type const* pHead, Q const& val, insert_position& pos, Compare cmp ) const
1150 node_type* pPrev = const_cast<node_type*>(pHead);
1151 value_type* pPrevVal = pPrev->data.load( memory_model::memory_order_relaxed ).ptr();
1154 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1156 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1160 pos.pFound = nullptr;
1161 pos.pPrevVal = pPrevVal;
1165 value_type * pVal = pos.guard.protect( pCur->data,
1166 []( marked_data_ptr p ) -> value_type*
1172 int const nCmp = cmp( *pVal, val );
1177 pos.pPrevVal = pPrevVal;
1184 pos.prevGuard.copy( pos.guard );
1188 // split-list support
1189 template <typename Predicate>
1190 void destroy( Predicate pred )
1192 node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1193 while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
1194 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1195 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1196 bool const is_regular_node = !pVal || pred( pVal );
1197 if ( is_regular_node ) {
1199 retire_data( pVal );
1200 delete_node( pNode );
1205 m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1213 m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1214 // end-of-list mark: node.next == node
1215 m_Tail.next.store( &m_Tail, memory_model::memory_order_release );
1218 node_type * alloc_node( value_type * pVal )
1220 m_Stat.onNodeCreated();
1221 return cxx_node_allocator().New( pVal );
1224 void delete_node( node_type * pNode )
1226 m_Stat.onNodeRemoved();
1227 cxx_node_allocator().Delete( pNode );
1230 static void retire_data( value_type * pVal )
1232 assert( pVal != nullptr );
1233 gc::template retire<disposer>( pVal );
1238 node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1239 while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
1240 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1242 retire_data( pVal );
1243 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1244 delete_node( pNode );
1249 bool link_data( value_type* pVal, insert_position& pos, node_type* pHead )
1251 assert( pos.pPrev != nullptr );
1252 assert( pos.pCur != nullptr );
1254 // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1255 // if current thread will be preempted and another thread will delete pos.pCur data
1256 // and then set it to another.
1257 // To prevent this we mark pos.pCur data as undeletable by setting LSB
1258 marked_data_ptr valCur( pos.pFound );
1259 if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1260 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1261 m_Stat.onNodeMarkFailed();
1265 marked_data_ptr valPrev( pos.pPrevVal );
1266 if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1267 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1269 m_Stat.onNodeMarkFailed();
1273 // checks if link pPrev -> pCur is broken
1274 if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
1275 // sequence pPrev - pCur is broken
1276 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1277 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1279 m_Stat.onNodeSeqBreak();
1283 if ( pos.pPrevVal == nullptr ) {
1284 // Check ABA-problem for prev
1285 // There is a possibility that the current thread was preempted
1286 // on entry of this function. Other threads can link data to prev
1287 // and then remove it. As a result, the order of items may be changed
1288 if ( find_prev( pHead, *pVal ) != pos.pPrev ) {
1289 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1290 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1292 m_Stat.onNullPrevABA();
1297 if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr ) {
1300 // Set pos.pPrev data if it is null
1302 bool result = pos.pPrev->data.compare_exchange_strong( valPrev, marked_data_ptr( pVal ),
1303 memory_model::memory_order_release, atomics::memory_order_relaxed );
1305 // Clears data marks
1306 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1309 m_Stat.onReuseNode();
1314 // insert new node between pos.pPrev and pos.pCur
1315 node_type * pNode = alloc_node( pVal );
1316 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1318 bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1320 // Clears data marks
1321 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1322 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1325 m_Stat.onNewNodeCreated();
1329 delete_node( pNode );
1335 // split-list support
1336 bool link_aux_node( node_type * pNode, insert_position& pos, node_type* pHead )
1338 assert( pos.pPrev != nullptr );
1339 assert( pos.pCur != nullptr );
1341 // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1342 // if current thread will be preempted and another thread will delete pos.pCur data
1343 // and then set it to another.
1344 // To prevent this we mark pos.pCur data as undeletable by setting LSB
1345 marked_data_ptr valCur( pos.pFound );
1346 if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1347 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1348 m_Stat.onNodeMarkFailed();
1352 marked_data_ptr valPrev( pos.pPrevVal );
1353 if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1354 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1355 m_Stat.onNodeMarkFailed();
1359 // checks if link pPrev -> pCur is broken
1360 if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
1361 // sequence pPrev - pCur is broken
1362 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1363 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1364 m_Stat.onNodeSeqBreak();
1368 if ( pos.pPrevVal == nullptr ) {
1369 // Check ABA-problem for prev
1370 // There is a possibility that the current thread was preempted
1371 // on entry of this function. Other threads can insert (link) an item to prev
1372 // and then remove it. As a result, the order of items may be changed
1373 if ( find_prev( pHead, *pNode->data.load( memory_model::memory_order_relaxed ).ptr()) != pos.pPrev ) {
1374 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1375 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1377 m_Stat.onNullPrevABA();
1382 // insert new node between pos.pPrev and pos.pCur
1383 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1385 bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1387 // Clears data marks
1388 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1389 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1394 static bool unlink_data( position& pos )
1396 assert( pos.pCur != nullptr );
1397 assert( pos.pFound != nullptr );
1399 marked_data_ptr val( pos.pFound );
1400 if ( pos.pCur->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1401 retire_data( pos.pFound );
1407 template <typename Q>
1408 node_type* find_prev( node_type const* pHead, Q const& val ) const
1410 node_type* pPrev = const_cast<node_type*>(pHead);
1411 typename gc::Guard guard;
1415 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1417 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1422 value_type * pVal = guard.protect( pCur->data,
1423 []( marked_data_ptr p ) -> value_type*
1428 if ( pVal && cmp( *pVal, val ) >= 0 )
1436 }} // namespace cds::intrusive
1438 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H