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 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>
111 - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
116 #ifdef CDS_DOXYGEN_INVOKED
117 ,class Traits = iterable_list::traits
123 #ifndef CDS_DOXYGEN_INVOKED
124 : public iterable_list_tag
128 typedef T value_type; ///< type of value stored in the list
129 typedef Traits traits; ///< Traits template parameter
131 typedef iterable_list::node< value_type > node_type; ///< node type
133 # ifdef CDS_DOXYGEN_INVOKED
134 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
136 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
139 typedef typename traits::disposer disposer; ///< disposer for \p value_type
141 typedef GC gc; ///< Garbage collector
142 typedef typename traits::back_off back_off; ///< back-off strategy
143 typedef typename traits::item_counter item_counter; ///< Item counting policy used
144 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
145 typedef typename traits::node_allocator node_allocator; ///< Node allocator
146 typedef typename traits::stat stat; ///< Internal statistics
148 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
150 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 3; ///< Count of hazard pointer required for the algorithm
153 // Rebind traits (split-list support)
154 template <typename... Options>
155 struct rebind_traits {
156 typedef IterableList<
159 , typename cds::opt::make_options< traits, Options...>::type
164 template <typename Stat>
165 using select_stat_wrapper = iterable_list::select_stat_wrapper< Stat >;
170 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
171 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
172 typedef typename node_type::marked_data_ptr marked_data_ptr;
177 item_counter m_ItemCounter; ///< Item counter
178 mutable stat m_Stat; ///< Internal statistics
180 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
182 /// Position pointer for item search
184 node_type const* pHead;
185 node_type * pPrev; ///< Previous node
186 node_type * pCur; ///< Current node
188 value_type * pFound; ///< Value of \p pCur->data, valid only if data found
190 typename gc::Guard guard; ///< guard for \p pFound
193 struct insert_position: public position
195 value_type * pPrevVal; ///< Value of \p pPrev->data, can be \p nullptr
196 typename gc::Guard prevGuard; ///< guard for \p pPrevVal
202 template <bool IsConst>
205 friend class IterableList;
208 node_type const* m_pNode;
209 typename gc::Guard m_Guard; // data guard
213 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 ))
216 if ( m_Guard.protect( p->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
222 explicit iterator_type( node_type const* pNode )
225 if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
229 iterator_type( node_type const* pNode, value_type* pVal )
233 assert( pVal != nullptr );
234 m_Guard.assign( pVal );
239 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
240 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
246 iterator_type( iterator_type const& src )
247 : m_pNode( src.m_pNode )
249 m_Guard.copy( src.m_Guard );
252 value_ptr operator ->() const
254 return m_Guard.template get<value_type>();
257 value_ref operator *() const
259 assert( m_Guard.get_native() != nullptr );
260 return *m_Guard.template get<value_type>();
264 iterator_type& operator ++()
270 iterator_type& operator = (iterator_type const& src)
272 m_pNode = src.m_pNode;
273 m_Guard.copy( src.m_Guard );
278 bool operator ==(iterator_type<C> const& i ) const
280 return m_pNode == i.m_pNode;
283 bool operator !=(iterator_type<C> const& i ) const
285 return !( *this == i );
291 ///@name Thread-safe forward iterators
295 The forward iterator for iterable list has some features:
296 - it has no post-increment operator
297 - to protect the value, the iterator contains a GC-specific guard.
298 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
299 may be thrown if the limit of guard count per thread is exceeded.
300 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
301 - Iterator is thread-safe: even if the element the iterator points to is removed, the iterator stays valid because
302 it contains the guard keeping the value from to be recycled.
304 The iterator interface:
308 // Default constructor
312 iterator( iterator const& src );
314 // Dereference operator
315 value_type * operator ->() const;
317 // Dereference operator
318 value_type& operator *() const;
320 // Preincrement operator
321 iterator& operator ++();
323 // Assignment operator
324 iterator& operator = (iterator const& src);
326 // Equality operators
327 bool operator ==(iterator const& i ) const;
328 bool operator !=(iterator const& i ) const;
332 @note For two iterators pointed to the same element the value can be different;
336 assert( &(*it1) == &(*it2));
338 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
339 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
340 Other iterator can observe modified value of the element.
342 typedef iterator_type<false> iterator;
343 /// Const forward iterator
345 For iterator's features and requirements see \ref iterator
347 typedef iterator_type<true> const_iterator;
349 /// Returns a forward iterator addressing the first element in a list
351 For empty list \code begin() == end() \endcode
355 return iterator( &m_Head );
358 /// Returns an iterator that addresses the location succeeding the last element in a list
360 Do not use the value returned by <tt>end</tt> function to access any item.
361 Internally, <tt>end</tt> returning value equals to \p nullptr.
363 The returned value can be used only to control reaching the end of the list.
364 For empty list <tt>begin() == end()</tt>
368 return iterator( &m_Tail );
371 /// Returns a forward const iterator addressing the first element in a list
372 const_iterator cbegin() const
374 return const_iterator( &m_Head );
377 /// Returns a forward const iterator addressing the first element in a list
378 const_iterator begin() const
380 return const_iterator( &m_Head );
383 /// Returns an const iterator that addresses the location succeeding the last element in a list
384 const_iterator end() const
386 return const_iterator( &m_Tail );
389 /// Returns an const iterator that addresses the location succeeding the last element in a list
390 const_iterator cend() const
392 return const_iterator( &m_Tail );
397 /// Default constructor initializes empty list
404 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
405 explicit IterableList( Stat& st )
412 /// Destroys the list object
420 The function inserts \p val into the list if the list does not contain
421 an item with key equal to \p val.
423 Returns \p true if \p val has been linked to the list, \p false otherwise.
425 bool insert( value_type& val )
427 return insert_at( &m_Head, val );
432 This function is intended for derived non-intrusive containers.
434 The function allows to split new item creating into two part:
435 - create item with key only
436 - insert new item into the list
437 - if inserting is success, calls \p f functor to initialize value-field of \p val.
439 The functor signature is:
441 void func( value_type& val );
443 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
444 \p val no any other changes could be made on this list's item by concurrent threads.
445 The user-defined functor is called only if the inserting is success.
447 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
449 template <typename Func>
450 bool insert( value_type& val, Func f )
452 return insert_at( &m_Head, val, f );
457 The operation performs inserting or changing data with lock-free manner.
459 If the item \p val is not found in the list, then \p val is inserted
460 iff \p bInsert is \p true.
461 Otherwise, the current element is changed to \p val, the element will be retired later
462 by call \p Traits::disposer.
463 The functor \p func is called after inserting or replacing, it signature is:
465 void func( value_type& val, value_type * old );
468 - \p val - argument \p val passed into the \p %update() function
469 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
471 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
472 \p second is \p true if \p val has been added or \p false if the item with that key
475 template <typename Func>
476 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
478 return update_at( &m_Head, val, func, bInsert );
483 The operation performs inserting or updating data with lock-free manner.
485 If the item \p val is not found in the list, then \p val is inserted
486 iff \p bInsert is \p true.
487 Otherwise, the current element is changed to \p val, the old element will be retired later
488 by call \p Traits::disposer.
490 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
491 \p second is \p true if \p val has been added or \p false if the item with that key
494 std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
496 return upsert_at( &m_Head, val, bInsert );
499 /// Unlinks the item \p val from the list
501 The function searches the item \p val in the list and unlinks it from the list
502 if it is found and it is equal to \p val.
504 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
505 and deletes the item found. \p %unlink() finds an item by key and deletes it
506 only if \p val is an item of the list, i.e. the pointer to item found
507 is equal to <tt> &val </tt>.
509 \p disposer specified in \p Traits is called for deleted item.
511 The function returns \p true if success and \p false otherwise.
513 bool unlink( value_type& val )
515 return unlink_at( &m_Head, val );
518 /// Deletes the item from the list
519 /** \anchor cds_intrusive_IterableList_hp_erase_val
520 The function searches an item with key equal to \p key in the list,
521 unlinks it from the list, and returns \p true.
522 If \p key is not found the function return \p false.
524 \p disposer specified in \p Traits is called for deleted item.
526 template <typename Q>
527 bool erase( Q const& key )
529 return erase_at( &m_Head, key, key_comparator());
532 /// Deletes the item from the list using \p pred predicate for searching
534 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
535 but \p pred is used for key comparing.
536 \p Less functor has the interface like \p std::less.
537 \p pred must imply the same element order as the comparator used for building the list.
539 \p disposer specified in \p Traits is called for deleted item.
541 template <typename Q, typename Less>
542 bool erase_with( Q const& key, Less pred )
545 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
548 /// Deletes the item from the list
549 /** \anchor cds_intrusive_IterableList_hp_erase_func
550 The function searches an item with key equal to \p key in the list,
551 call \p func functor with item found, unlinks it from the list, and returns \p true.
552 The \p Func interface is
555 void operator()( value_type const& item );
558 If \p key is not found the function return \p false, \p func is not called.
560 \p disposer specified in \p Traits is called for deleted item.
562 template <typename Q, typename Func>
563 bool erase( Q const& key, Func func )
565 return erase_at( &m_Head, key, key_comparator(), func );
568 /// Deletes the item from the list using \p pred predicate for searching
570 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
571 but \p pred is used for key comparing.
572 \p Less functor has the interface like \p std::less.
573 \p pred must imply the same element order as the comparator used for building the list.
575 \p disposer specified in \p Traits is called for deleted item.
577 template <typename Q, typename Less, typename Func>
578 bool erase_with( Q const& key, Less pred, Func f )
581 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
584 /// Extracts the item from the list with specified \p key
585 /** \anchor cds_intrusive_IterableList_hp_extract
586 The function searches an item with key equal to \p key,
587 unlinks it from the list, and returns it as \p guarded_ptr.
588 If \p key is not found returns an empty guarded pointer.
590 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
592 The \ref disposer specified in \p Traits class template parameter is called automatically
593 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
594 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
598 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
602 ord_list::guarded_ptr gp( theList.extract( 5 ));
607 // Destructor of gp releases internal HP guard
611 template <typename Q>
612 guarded_ptr extract( Q const& key )
614 return extract_at( &m_Head, key, key_comparator());
617 /// Extracts the item using compare functor \p pred
619 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
620 but \p pred predicate is used for key comparing.
622 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
624 \p pred must imply the same element order as the comparator used for building the list.
626 template <typename Q, typename Less>
627 guarded_ptr extract_with( Q const& key, Less pred )
630 return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
633 /// Finds \p key in the list
634 /** \anchor cds_intrusive_IterableList_hp_find_func
635 The function searches the item with key equal to \p key and calls the functor \p f for item found.
636 The interface of \p Func functor is:
639 void operator()( value_type& item, Q& key );
642 where \p item is the item found, \p key is the \p %find() function argument.
644 The functor may change non-key fields of \p item. Note that the function is only guarantee
645 that \p item cannot be disposed during functor is executing.
646 The function does not serialize simultaneous access to the \p item. If such access is
647 possible you must provide your own synchronization schema to keep out unsafe item modifications.
649 The function returns \p true if \p val is found, \p false otherwise.
651 template <typename Q, typename Func>
652 bool find( Q& key, Func f ) const
654 return find_at( &m_Head, key, key_comparator(), f );
657 template <typename Q, typename Func>
658 bool find( Q const& key, Func f ) const
660 return find_at( &m_Head, key, key_comparator(), f );
664 /// Finds \p key in the list and returns iterator pointed to the item found
666 If \p key is not found the function returns \p end().
668 template <typename Q>
669 iterator find( Q const& key ) const
671 return find_iterator_at( &m_Head, key, key_comparator());
674 /// Finds the \p key using \p pred predicate for searching
676 The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
677 but \p pred is used for key comparing.
678 \p Less functor has the interface like \p std::less.
679 \p pred must imply the same element order as the comparator used for building the list.
681 template <typename Q, typename Less, typename Func>
682 bool find_with( Q& key, Less pred, Func f ) const
685 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
688 template <typename Q, typename Less, typename Func>
689 bool find_with( Q const& key, Less pred, Func f ) const
692 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
696 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
698 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
699 \p Less functor has the interface like \p std::less.
700 \p pred must imply the same element order as the comparator used for building the list.
702 If \p key is not found the function returns \p end().
704 template <typename Q, typename Less>
705 iterator find_with( Q const& key, Less pred ) const
708 return find_iterator_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
711 /// Checks whether the list contains \p key
713 The function searches the item with key equal to \p key
714 and returns \p true if it is found, and \p false otherwise.
716 template <typename Q>
717 bool contains( Q const& key ) const
719 return find_at( &m_Head, key, key_comparator());
722 /// Checks whether the list contains \p key using \p pred predicate for searching
724 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
725 \p Less functor has the interface like \p std::less.
726 \p Less must imply the same element order as the comparator used for building the list.
728 template <typename Q, typename Less>
729 bool contains( Q const& key, Less pred ) const
732 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
735 /// Finds the \p key and return the item found
736 /** \anchor cds_intrusive_IterableList_hp_get
737 The function searches the item with key equal to \p key
738 and returns it as \p guarded_ptr.
739 If \p key is not found the function returns an empty guarded pointer.
741 The \ref disposer specified in \p Traits class template parameter is called
742 by garbage collector \p GC automatically when returned \ref guarded_ptr object
743 will be destroyed or released.
744 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
748 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
752 ord_list::guarded_ptr gp(theList.get( 5 ));
757 // Destructor of guarded_ptr releases internal HP guard
761 Note the compare functor specified for \p Traits template parameter
762 should accept a parameter of type \p Q that can be not the same as \p value_type.
764 template <typename Q>
765 guarded_ptr get( Q const& key ) const
767 return get_at( &m_Head, key, key_comparator());
770 /// Finds the \p key and return the item found
772 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
773 but \p pred is used for comparing the keys.
775 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
777 \p pred must imply the same element order as the comparator used for building the list.
779 template <typename Q, typename Less>
780 guarded_ptr get_with( Q const& key, Less pred ) const
783 return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
786 /// Clears the list (thread safe, not atomic)
791 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 )) {
793 pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr();
796 if ( cds_likely( unlink_data( pos ))) {
801 pos.pPrev = pos.pCur;
805 /// Checks if the list is empty
807 Emptiness is checked by item counting: if item count is zero then the set is empty.
808 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
816 /// Returns list's item count
818 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
819 this function always returns 0.
823 return m_ItemCounter.value();
826 /// Returns const reference to internal statistics
827 stat const& statistics() const
835 // split-list support
836 bool insert_aux_node( node_type * pNode )
838 return insert_aux_node( &m_Head, pNode );
841 // split-list support
842 bool insert_aux_node( node_type* pHead, node_type * pNode )
844 assert( pNode != nullptr );
845 assert( pNode->data.load( memory_model::memory_order_relaxed ) != nullptr );
850 if ( inserting_search( pHead, *pNode->data.load(memory_model::memory_order_relaxed).ptr(), pos, key_comparator()) ) {
851 m_Stat.onInsertFailed();
855 if ( link_aux_node( pNode, pos )) {
857 m_Stat.onInsertSuccess();
861 m_Stat.onInsertRetry();
865 bool insert_at( node_type* pHead, value_type& val )
870 if ( inserting_search( pHead, val, pos, key_comparator())) {
871 m_Stat.onInsertFailed();
875 if ( link_data( &val, pos )) {
877 m_Stat.onInsertSuccess();
881 m_Stat.onInsertRetry();
885 template <typename Func>
886 bool insert_at( node_type* pHead, value_type& val, Func f )
890 typename gc::Guard guard;
891 guard.assign( &val );
894 if ( inserting_search( pHead, val, pos, key_comparator()) ) {
895 m_Stat.onInsertFailed();
899 if ( link_data( &val, pos )) {
902 m_Stat.onInsertSuccess();
906 m_Stat.onInsertRetry();
910 template <typename Func>
911 std::pair<bool, bool> update_at( node_type* pHead, value_type& val, Func func, bool bInsert )
915 typename gc::Guard guard;
916 guard.assign( &val );
919 if ( inserting_search( pHead, val, pos, key_comparator()) ) {
920 // try to replace pCur->data with val
921 assert( pos.pFound != nullptr );
922 assert( key_comparator()(*pos.pFound, val) == 0 );
924 marked_data_ptr pFound( pos.pFound );
925 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ),
926 memory_model::memory_order_release, atomics::memory_order_relaxed )))
928 if ( pos.pFound != &val ) {
929 retire_data( pos.pFound );
930 func( val, pos.pFound );
932 m_Stat.onUpdateExisting();
933 return std::make_pair( true, false );
938 m_Stat.onUpdateFailed();
939 return std::make_pair( false, false );
942 if ( link_data( &val, pos )) {
943 func( val, static_cast<value_type*>( nullptr ));
945 m_Stat.onUpdateNew();
946 return std::make_pair( true, true );
950 m_Stat.onUpdateRetry();
954 std::pair<bool, bool> upsert_at( node_type* pHead, value_type& val, bool bInsert )
956 return update_at( pHead, val, []( value_type&, value_type* ) {}, bInsert );
959 bool unlink_at( node_type* pHead, value_type& val )
964 while ( search( pHead, val, pos, key_comparator())) {
965 if ( pos.pFound == &val ) {
966 if ( unlink_data( pos )) {
968 m_Stat.onEraseSuccess();
977 m_Stat.onEraseRetry();
980 m_Stat.onEraseFailed();
984 template <typename Q, typename Compare, typename Func>
985 bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos )
988 while ( search( pHead, val, pos, cmp )) {
989 if ( unlink_data( pos )) {
992 m_Stat.onEraseSuccess();
998 m_Stat.onEraseRetry();
1001 m_Stat.onEraseFailed();
1005 template <typename Q, typename Compare, typename Func>
1006 bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f )
1009 return erase_at( pHead, val, cmp, f, pos );
1012 template <typename Q, typename Compare>
1013 bool erase_at( node_type* pHead, Q const& val, Compare cmp )
1016 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1019 template <typename Q, typename Compare>
1020 guarded_ptr extract_at( node_type* pHead, Q const& val, Compare cmp )
1024 while ( search( pHead, val, pos, cmp )) {
1025 if ( unlink_data( pos )) {
1027 m_Stat.onEraseSuccess();
1028 assert( pos.pFound != nullptr );
1029 return guarded_ptr( std::move( pos.guard ));
1034 m_Stat.onEraseRetry();
1037 m_Stat.onEraseFailed();
1038 return guarded_ptr();
1041 template <typename Q, typename Compare>
1042 bool find_at( node_type const* pHead, Q const& val, Compare cmp ) const
1045 if ( search( pHead, val, pos, cmp )) {
1046 m_Stat.onFindSuccess();
1050 m_Stat.onFindFailed();
1054 template <typename Q, typename Compare, typename Func>
1055 bool find_at( node_type const* pHead, Q& val, Compare cmp, Func f ) const
1058 if ( search( pHead, val, pos, cmp )) {
1059 assert( pos.pFound != nullptr );
1060 f( *pos.pFound, val );
1061 m_Stat.onFindSuccess();
1065 m_Stat.onFindFailed();
1069 template <typename Q, typename Compare>
1070 iterator find_iterator_at( node_type const* pHead, Q const& val, Compare cmp ) const
1073 if ( search( pHead, val, pos, cmp )) {
1074 assert( pos.pCur != nullptr );
1075 assert( pos.pFound != nullptr );
1076 m_Stat.onFindSuccess();
1077 return iterator( pos.pCur, pos.pFound );
1080 m_Stat.onFindFailed();
1081 return iterator( &m_Tail );
1084 template <typename Q, typename Compare>
1085 guarded_ptr get_at( node_type const* pHead, Q const& val, Compare cmp ) const
1088 if ( search( pHead, val, pos, cmp )) {
1089 m_Stat.onFindSuccess();
1090 return guarded_ptr( std::move( pos.guard ));
1093 m_Stat.onFindFailed();
1094 return guarded_ptr();
1102 node_type const* head() const
1110 template <typename Q, typename Compare >
1111 bool search( node_type const* pHead, Q const& val, position& pos, Compare cmp ) const
1114 node_type* pPrev = const_cast<node_type*>( pHead );
1117 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1119 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1123 pos.pFound = nullptr;
1127 value_type * pVal = pos.guard.protect( pCur->data,
1128 []( marked_data_ptr p ) -> value_type*
1134 int const nCmp = cmp( *pVal, val );
1147 template <typename Q, typename Compare >
1148 bool inserting_search( node_type const* pHead, Q const& val, insert_position& pos, Compare cmp ) const
1151 node_type* pPrev = const_cast<node_type*>(pHead);
1152 value_type* pPrevVal = pPrev->data.load( memory_model::memory_order_relaxed ).ptr();
1155 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1157 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1161 pos.pFound = nullptr;
1162 pos.pPrevVal = pPrevVal;
1166 value_type * pVal = pos.guard.protect( pCur->data,
1167 []( marked_data_ptr p ) -> value_type*
1173 int const nCmp = cmp( *pVal, val );
1178 pos.pPrevVal = pPrevVal;
1185 pos.prevGuard.copy( pos.guard );
1189 // split-list support
1190 template <typename Predicate>
1191 void destroy( Predicate pred )
1193 node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1194 while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
1195 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1196 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1197 bool const is_regular_node = !pVal || pred( pVal );
1198 if ( is_regular_node ) {
1200 retire_data( pVal );
1201 delete_node( pNode );
1206 m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1214 m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1215 // end-of-list mark: node.next == node
1216 m_Tail.next.store( &m_Tail, memory_model::memory_order_release );
1219 node_type * alloc_node( value_type * pVal )
1221 m_Stat.onNodeCreated();
1222 return cxx_node_allocator().New( pVal );
1225 void delete_node( node_type * pNode )
1227 m_Stat.onNodeRemoved();
1228 cxx_node_allocator().Delete( pNode );
1231 static void retire_data( value_type * pVal )
1233 assert( pVal != nullptr );
1234 gc::template retire<disposer>( pVal );
1239 node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1240 while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
1241 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1243 retire_data( pVal );
1244 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1245 delete_node( pNode );
1250 bool link_data( value_type * pVal, insert_position& pos )
1252 assert( pos.pPrev != nullptr );
1253 assert( pos.pCur != nullptr );
1255 // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1256 // if current thread will be preempted and another thread will delete pos.pCur data
1257 // and then set it to another.
1258 // To prevent this we mark pos.pCur data as undeletable by setting LSB
1259 marked_data_ptr valCur( pos.pFound );
1260 if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1261 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1262 m_Stat.onNodeMarkFailed();
1266 marked_data_ptr valPrev( pos.pPrevVal );
1267 if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1268 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 );
1278 m_Stat.onNodeSeqBreak();
1282 if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr )
1286 // Set pos.pPrev data if it is null
1288 bool result = pos.pPrev->data.compare_exchange_strong( valPrev, marked_data_ptr( pVal ),
1289 memory_model::memory_order_release, atomics::memory_order_relaxed );
1291 // Clears data marks
1292 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1295 m_Stat.onReuseNode();
1300 // insert new node between pos.pPrev and pos.pCur
1301 node_type * pNode = alloc_node( pVal );
1302 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1304 bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1306 // Clears data marks
1307 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1308 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1311 m_Stat.onNewNodeCreated();
1315 delete_node( pNode );
1321 // split-list support
1322 bool link_aux_node( node_type * pNode, insert_position& pos )
1324 assert( pos.pPrev != nullptr );
1325 assert( pos.pCur != nullptr );
1327 // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1328 // if current thread will be preempted and another thread will delete pos.pCur data
1329 // and then set it to another.
1330 // To prevent this we mark pos.pCur data as undeletable by setting LSB
1331 marked_data_ptr valCur( pos.pFound );
1332 if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1333 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1334 m_Stat.onNodeMarkFailed();
1338 marked_data_ptr valPrev( pos.pPrevVal );
1339 if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1340 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1341 m_Stat.onNodeMarkFailed();
1345 // checks if link pPrev -> pCur is broken
1346 if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
1347 // sequence pPrev - pCur is broken
1348 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1349 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1350 m_Stat.onNodeSeqBreak();
1354 // insert new node between pos.pPrev and pos.pCur
1355 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1357 bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1359 // Clears data marks
1360 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1361 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1366 static bool unlink_data( position& pos )
1368 assert( pos.pCur != nullptr );
1369 assert( pos.pFound != nullptr );
1371 marked_data_ptr val( pos.pFound );
1372 if ( pos.pCur->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1373 retire_data( pos.pFound );
1380 }} // namespace cds::intrusive
1382 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H