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
125 typedef T value_type; ///< type of value stored in the list
126 typedef Traits traits; ///< Traits template parameter
128 typedef iterable_list::node< value_type > node_type; ///< node type
130 # ifdef CDS_DOXYGEN_INVOKED
131 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
133 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
136 typedef typename traits::disposer disposer; ///< disposer for \p value_type
138 typedef GC gc; ///< Garbage collector
139 typedef typename traits::back_off back_off; ///< back-off strategy
140 typedef typename traits::item_counter item_counter; ///< Item counting policy used
141 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
142 typedef typename traits::node_allocator node_allocator; ///< Node allocator
143 typedef typename traits::stat stat; ///< Internal statistics
145 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
147 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 3; ///< Count of hazard pointer required for the algorithm
150 // Rebind traits (split-list support)
151 template <typename... Options>
152 struct rebind_traits {
153 typedef IterableList<
156 , typename cds::opt::make_options< traits, Options...>::type
161 template <typename Stat>
162 using select_stat_wrapper = iterable_list::select_stat_wrapper< Stat >;
167 typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
168 typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
169 typedef typename node_type::marked_data_ptr marked_data_ptr;
174 item_counter m_ItemCounter; ///< Item counter
175 mutable stat m_Stat; ///< Internal statistics
177 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
179 /// Position pointer for item search
181 node_type const* pHead;
182 node_type * pPrev; ///< Previous node
183 node_type * pCur; ///< Current node
185 value_type * pFound; ///< Value of \p pCur->data, valid only if data found
187 typename gc::Guard guard; ///< guard for \p pFound
190 struct insert_position: public position
192 value_type * pPrevVal; ///< Value of \p pPrev->data, can be \p nullptr
193 typename gc::Guard prevGuard; ///< guard for \p pPrevVal
199 template <bool IsConst>
202 friend class IterableList;
205 node_type const* m_pNode;
206 typename gc::Guard m_Guard; // data guard
210 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 ))
213 if ( m_Guard.protect( p->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
219 explicit iterator_type( node_type const* pNode )
222 if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
226 iterator_type( node_type const* pNode, value_type* pVal )
230 assert( pVal != nullptr );
231 m_Guard.assign( pVal );
236 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
237 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
243 iterator_type( iterator_type const& src )
244 : m_pNode( src.m_pNode )
246 m_Guard.copy( src.m_Guard );
249 value_ptr operator ->() const
251 return m_Guard.template get<value_type>();
254 value_ref operator *() const
256 assert( m_Guard.get_native() != nullptr );
257 return *m_Guard.template get<value_type>();
261 iterator_type& operator ++()
267 iterator_type& operator = (iterator_type const& src)
269 m_pNode = src.m_pNode;
270 m_Guard.copy( src.m_Guard );
275 bool operator ==(iterator_type<C> const& i ) const
277 return m_pNode == i.m_pNode;
280 bool operator !=(iterator_type<C> const& i ) const
282 return !( *this == i );
288 ///@name Thread-safe forward iterators
292 The forward iterator for iterable list has some features:
293 - it has no post-increment operator
294 - to protect the value, the iterator contains a GC-specific guard.
295 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
296 may be thrown if the limit of guard count per thread is exceeded.
297 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
298 - Iterator is thread-safe: even if the element the iterator points to is removed, the iterator stays valid because
299 it contains the guard keeping the value from to be recycled.
301 The iterator interface:
305 // Default constructor
309 iterator( iterator const& src );
311 // Dereference operator
312 value_type * operator ->() const;
314 // Dereference operator
315 value_type& operator *() const;
317 // Preincrement operator
318 iterator& operator ++();
320 // Assignment operator
321 iterator& operator = (iterator const& src);
323 // Equality operators
324 bool operator ==(iterator const& i ) const;
325 bool operator !=(iterator const& i ) const;
329 @note For two iterators pointed to the same element the value can be different;
333 assert( &(*it1) == &(*it2) );
335 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
336 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
337 Other iterator can observe modified value of the element.
339 typedef iterator_type<false> iterator;
340 /// Const forward iterator
342 For iterator's features and requirements see \ref iterator
344 typedef iterator_type<true> const_iterator;
346 /// Returns a forward iterator addressing the first element in a list
348 For empty list \code begin() == end() \endcode
352 return iterator( &m_Head );
355 /// Returns an iterator that addresses the location succeeding the last element in a list
357 Do not use the value returned by <tt>end</tt> function to access any item.
358 Internally, <tt>end</tt> returning value equals to \p nullptr.
360 The returned value can be used only to control reaching the end of the list.
361 For empty list <tt>begin() == end()</tt>
365 return iterator( &m_Tail );
368 /// Returns a forward const iterator addressing the first element in a list
369 const_iterator cbegin() const
371 return const_iterator( &m_Head );
374 /// Returns a forward const iterator addressing the first element in a list
375 const_iterator begin() const
377 return const_iterator( &m_Head );
380 /// Returns an const iterator that addresses the location succeeding the last element in a list
381 const_iterator end() const
383 return const_iterator( &m_Tail );
386 /// Returns an const iterator that addresses the location succeeding the last element in a list
387 const_iterator cend() const
389 return const_iterator( &m_Tail );
394 /// Default constructor initializes empty list
401 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
402 explicit IterableList( Stat& st )
409 /// Destroys the list object
417 The function inserts \p val into the list if the list does not contain
418 an item with key equal to \p val.
420 Returns \p true if \p val has been linked to the list, \p false otherwise.
422 bool insert( value_type& val )
424 return insert_at( &m_Head, val );
429 This function is intended for derived non-intrusive containers.
431 The function allows to split new item creating into two part:
432 - create item with key only
433 - insert new item into the list
434 - if inserting is success, calls \p f functor to initialize value-field of \p val.
436 The functor signature is:
438 void func( value_type& val );
440 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
441 \p val no any other changes could be made on this list's item by concurrent threads.
442 The user-defined functor is called only if the inserting is success.
444 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
446 template <typename Func>
447 bool insert( value_type& val, Func f )
449 return insert_at( &m_Head, val, f );
454 The operation performs inserting or changing data with lock-free manner.
456 If the item \p val is not found in the list, then \p val is inserted
457 iff \p bInsert is \p true.
458 Otherwise, the current element is changed to \p val, the element will be retired later
459 by call \p Traits::disposer.
460 The functor \p func is called after inserting or replacing, it signature is:
462 void func( value_type& val, value_type * old );
465 - \p val - argument \p val passed into the \p %update() function
466 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
468 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
469 \p second is \p true if \p val has been added or \p false if the item with that key
472 template <typename Func>
473 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
475 return update_at( &m_Head, val, func, bInsert );
480 The operation performs inserting or updating data with lock-free manner.
482 If the item \p val is not found in the list, then \p val is inserted
483 iff \p bInsert is \p true.
484 Otherwise, the current element is changed to \p val, the old element will be retired later
485 by call \p Traits::disposer.
487 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
488 \p second is \p true if \p val has been added or \p false if the item with that key
491 std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
493 return update_at( &m_Head, val, []( value_type&, value_type* ) {}, bInsert );
496 /// Unlinks the item \p val from the list
498 The function searches the item \p val in the list and unlinks it from the list
499 if it is found and it is equal to \p val.
501 Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
502 and deletes the item found. \p %unlink() finds an item by key and deletes it
503 only if \p val is an item of the list, i.e. the pointer to item found
504 is equal to <tt> &val </tt>.
506 \p disposer specified in \p Traits is called for deleted item.
508 The function returns \p true if success and \p false otherwise.
510 bool unlink( value_type& val )
512 return unlink_at( &m_Head, val );
515 /// Deletes the item from the list
516 /** \anchor cds_intrusive_IterableList_hp_erase_val
517 The function searches an item with key equal to \p key in the list,
518 unlinks it from the list, and returns \p true.
519 If \p key is not found the function return \p false.
521 \p disposer specified in \p Traits is called for deleted item.
523 template <typename Q>
524 bool erase( Q const& key )
526 return erase_at( &m_Head, key, key_comparator());
529 /// Deletes the item from the list using \p pred predicate for searching
531 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
532 but \p pred is used for key comparing.
533 \p Less functor has the interface like \p std::less.
534 \p pred must imply the same element order as the comparator used for building the list.
536 \p disposer specified in \p Traits is called for deleted item.
538 template <typename Q, typename Less>
539 bool erase_with( Q const& key, Less pred )
542 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
545 /// Deletes the item from the list
546 /** \anchor cds_intrusive_IterableList_hp_erase_func
547 The function searches an item with key equal to \p key in the list,
548 call \p func functor with item found, unlinks it from the list, and returns \p true.
549 The \p Func interface is
552 void operator()( value_type const& item );
555 If \p key is not found the function return \p false, \p func is not called.
557 \p disposer specified in \p Traits is called for deleted item.
559 template <typename Q, typename Func>
560 bool erase( Q const& key, Func func )
562 return erase_at( &m_Head, key, key_comparator(), func );
565 /// Deletes the item from the list using \p pred predicate for searching
567 The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
568 but \p pred is used for key comparing.
569 \p Less functor has the interface like \p std::less.
570 \p pred must imply the same element order as the comparator used for building the list.
572 \p disposer specified in \p Traits is called for deleted item.
574 template <typename Q, typename Less, typename Func>
575 bool erase_with( Q const& key, Less pred, Func f )
578 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
581 /// Extracts the item from the list with specified \p key
582 /** \anchor cds_intrusive_IterableList_hp_extract
583 The function searches an item with key equal to \p key,
584 unlinks it from the list, and returns it as \p guarded_ptr.
585 If \p key is not found returns an empty guarded pointer.
587 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
589 The \ref disposer specified in \p Traits class template parameter is called automatically
590 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
591 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
595 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
599 ord_list::guarded_ptr gp( theList.extract( 5 ));
604 // Destructor of gp releases internal HP guard
608 template <typename Q>
609 guarded_ptr extract( Q const& key )
611 return extract_at( &m_Head, key, key_comparator());
614 /// Extracts the item using compare functor \p pred
616 The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
617 but \p pred predicate is used for key comparing.
619 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
621 \p pred must imply the same element order as the comparator used for building the list.
623 template <typename Q, typename Less>
624 guarded_ptr extract_with( Q const& key, Less pred )
627 return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
630 /// Finds \p key in the list
631 /** \anchor cds_intrusive_IterableList_hp_find_func
632 The function searches the item with key equal to \p key and calls the functor \p f for item found.
633 The interface of \p Func functor is:
636 void operator()( value_type& item, Q& key );
639 where \p item is the item found, \p key is the \p %find() function argument.
641 The functor may change non-key fields of \p item. Note that the function is only guarantee
642 that \p item cannot be disposed during functor is executing.
643 The function does not serialize simultaneous access to the \p item. If such access is
644 possible you must provide your own synchronization schema to keep out unsafe item modifications.
646 The function returns \p true if \p val is found, \p false otherwise.
648 template <typename Q, typename Func>
649 bool find( Q& key, Func f ) const
651 return find_at( &m_Head, key, key_comparator(), f );
654 template <typename Q, typename Func>
655 bool find( Q const& key, Func f ) const
657 return find_at( &m_Head, key, key_comparator(), f );
661 /// Finds \p key in the list and returns iterator pointed to the item found
663 If \p key is not found the function returns \p end().
665 template <typename Q>
666 iterator find( Q const& key ) const
668 return find_iterator_at( &m_Head, key, key_comparator());
671 /// Finds the \p key using \p pred predicate for searching
673 The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
674 but \p pred is used for key comparing.
675 \p Less functor has the interface like \p std::less.
676 \p pred must imply the same element order as the comparator used for building the list.
678 template <typename Q, typename Less, typename Func>
679 bool find_with( Q& key, Less pred, Func f ) const
682 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
685 template <typename Q, typename Less, typename Func>
686 bool find_with( Q const& key, Less pred, Func f ) const
689 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
693 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
695 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
696 \p Less functor has the interface like \p std::less.
697 \p pred must imply the same element order as the comparator used for building the list.
699 If \p key is not found the function returns \p end().
701 template <typename Q, typename Less>
702 iterator find_with( Q const& key, Less pred ) const
705 return find_iterator_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
708 /// Checks whether the list contains \p key
710 The function searches the item with key equal to \p key
711 and returns \p true if it is found, and \p false otherwise.
713 template <typename Q>
714 bool contains( Q const& key ) const
716 return find_at( &m_Head, key, key_comparator());
719 /// Checks whether the list contains \p key using \p pred predicate for searching
721 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
722 \p Less functor has the interface like \p std::less.
723 \p Less must imply the same element order as the comparator used for building the list.
725 template <typename Q, typename Less>
726 bool contains( Q const& key, Less pred ) const
729 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
732 /// Finds the \p key and return the item found
733 /** \anchor cds_intrusive_IterableList_hp_get
734 The function searches the item with key equal to \p key
735 and returns it as \p guarded_ptr.
736 If \p key is not found the function returns an empty guarded pointer.
738 The \ref disposer specified in \p Traits class template parameter is called
739 by garbage collector \p GC automatically when returned \ref guarded_ptr object
740 will be destroyed or released.
741 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
745 typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list;
749 ord_list::guarded_ptr gp(theList.get( 5 ));
754 // Destructor of guarded_ptr releases internal HP guard
758 Note the compare functor specified for \p Traits template parameter
759 should accept a parameter of type \p Q that can be not the same as \p value_type.
761 template <typename Q>
762 guarded_ptr get( Q const& key ) const
764 return get_at( &m_Head, key, key_comparator());
767 /// Finds the \p key and return the item found
769 The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
770 but \p pred is used for comparing the keys.
772 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
774 \p pred must imply the same element order as the comparator used for building the list.
776 template <typename Q, typename Less>
777 guarded_ptr get_with( Q const& key, Less pred ) const
780 return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
783 /// Clears the list (thread safe, not atomic)
788 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 )) {
790 pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr();
793 if ( cds_likely( unlink_data( pos ))) {
798 pos.pPrev = pos.pCur;
802 /// Checks if the list is empty
804 Emptiness is checked by item counting: if item count is zero then the set is empty.
805 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
813 /// Returns list's item count
815 The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
816 this function always returns 0.
820 return m_ItemCounter.value();
823 /// Returns const reference to internal statistics
824 stat const& statistics() const
832 // split-list support
833 bool insert_aux_node( node_type * pNode )
835 return insert_aux_node( &m_Head, pNode );
838 // split-list support
839 bool insert_aux_node( node_type* pHead, node_type * pNode )
841 assert( pNode != nullptr );
843 // Hack: convert node_type to value_type.
844 // In principle, auxiliary node can be non-reducible to value_type
845 // We assume that comparator can correctly distinguish aux and regular node.
846 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
850 bool insert_at( node_type* pHead, value_type& val )
855 if ( inserting_search( pHead, val, pos, key_comparator() )) {
856 m_Stat.onInsertFailed();
860 if ( link_data( &val, pos ) ) {
862 m_Stat.onInsertSuccess();
866 m_Stat.onInsertRetry();
870 template <typename Func>
871 bool insert_at( node_type* pHead, value_type& val, Func f )
875 typename gc::Guard guard;
876 guard.assign( &val );
879 if ( inserting_search( pHead, val, pos, key_comparator() ) ) {
880 m_Stat.onInsertFailed();
884 if ( link_data( &val, pos ) ) {
887 m_Stat.onInsertSuccess();
891 m_Stat.onInsertRetry();
895 template <typename Func>
896 std::pair<bool, bool> update_at( node_type* pHead, value_type& val, Func func, bool bInsert )
900 typename gc::Guard guard;
901 guard.assign( &val );
904 if ( inserting_search( pHead, val, pos, key_comparator() ) ) {
905 // try to replace pCur->data with val
906 assert( pos.pFound != nullptr );
907 assert( key_comparator()(*pos.pFound, val) == 0 );
909 marked_data_ptr pFound( pos.pFound );
910 if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ),
911 memory_model::memory_order_release, atomics::memory_order_relaxed )))
913 if ( pos.pFound != &val ) {
914 retire_data( pos.pFound );
915 func( val, pos.pFound );
917 m_Stat.onUpdateExisting();
918 return std::make_pair( true, false );
923 m_Stat.onUpdateFailed();
924 return std::make_pair( false, false );
927 if ( link_data( &val, pos )) {
928 func( val, static_cast<value_type*>( nullptr ));
930 m_Stat.onUpdateNew();
931 return std::make_pair( true, true );
935 m_Stat.onUpdateRetry();
939 bool unlink_at( node_type* pHead, value_type& val )
944 while ( search( pHead, val, pos, key_comparator())) {
945 if ( pos.pFound == &val ) {
946 if ( unlink_data( pos )) {
948 m_Stat.onEraseSuccess();
957 m_Stat.onEraseRetry();
960 m_Stat.onEraseFailed();
964 template <typename Q, typename Compare, typename Func>
965 bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos )
968 while ( search( pHead, val, pos, cmp )) {
969 if ( unlink_data( pos )) {
972 m_Stat.onEraseSuccess();
978 m_Stat.onEraseRetry();
981 m_Stat.onEraseFailed();
985 template <typename Q, typename Compare, typename Func>
986 bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f )
989 return erase_at( pHead, val, cmp, f, pos );
992 template <typename Q, typename Compare>
993 bool erase_at( node_type* pHead, Q const& val, Compare cmp )
996 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
999 template <typename Q, typename Compare>
1000 guarded_ptr extract_at( node_type* pHead, Q const& val, Compare cmp )
1004 while ( search( pHead, val, pos, cmp )) {
1005 if ( unlink_data( pos )) {
1007 m_Stat.onEraseSuccess();
1008 assert( pos.pFound != nullptr );
1009 return guarded_ptr( std::move( pos.guard ));
1014 m_Stat.onEraseRetry();
1017 m_Stat.onEraseFailed();
1018 return guarded_ptr();
1021 template <typename Q, typename Compare>
1022 bool find_at( node_type const* pHead, Q const& val, Compare cmp ) const
1025 if ( search( pHead, val, pos, cmp ) ) {
1026 m_Stat.onFindSuccess();
1030 m_Stat.onFindFailed();
1034 template <typename Q, typename Compare, typename Func>
1035 bool find_at( node_type const* pHead, Q& val, Compare cmp, Func f ) const
1038 if ( search( pHead, val, pos, cmp )) {
1039 assert( pos.pFound != nullptr );
1040 f( *pos.pFound, val );
1041 m_Stat.onFindSuccess();
1045 m_Stat.onFindFailed();
1049 template <typename Q, typename Compare>
1050 iterator find_iterator_at( node_type const* pHead, Q const& val, Compare cmp ) const
1053 if ( search( pHead, val, pos, cmp )) {
1054 assert( pos.pCur != nullptr );
1055 assert( pos.pFound != nullptr );
1056 m_Stat.onFindSuccess();
1057 return iterator( pos.pCur, pos.pFound );
1060 m_Stat.onFindFailed();
1061 return iterator( &m_Tail );
1064 template <typename Q, typename Compare>
1065 guarded_ptr get_at( node_type const* pHead, Q const& val, Compare cmp ) const
1068 if ( search( pHead, val, pos, cmp )) {
1069 m_Stat.onFindSuccess();
1070 return guarded_ptr( std::move( pos.guard ));
1073 m_Stat.onFindFailed();
1074 return guarded_ptr();
1082 node_type const* head() const
1090 template <typename Q, typename Compare >
1091 bool search( node_type const* pHead, Q const& val, position& pos, Compare cmp ) const
1094 node_type* pPrev = const_cast<node_type*>( pHead );
1097 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1099 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1103 pos.pFound = nullptr;
1107 value_type * pVal = pos.guard.protect( pCur->data,
1108 []( marked_data_ptr p ) -> value_type*
1114 int const nCmp = cmp( *pVal, val );
1127 template <typename Q, typename Compare >
1128 bool inserting_search( node_type const* pHead, Q const& val, insert_position& pos, Compare cmp ) const
1131 node_type* pPrev = const_cast<node_type*>(pHead);
1132 value_type* pPrevVal = nullptr;
1135 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1137 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1141 pos.pFound = nullptr;
1142 pos.pPrevVal = pPrevVal;
1146 value_type * pVal = pos.guard.protect( pCur->data,
1147 []( marked_data_ptr p ) -> value_type*
1153 int const nCmp = cmp( *pVal, val );
1158 pos.pPrevVal = pPrevVal;
1165 pos.prevGuard.copy( pos.guard );
1175 m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1176 // end-of-list mark: node.next == node
1177 m_Tail.next.store( &m_Tail, memory_model::memory_order_release );
1180 node_type * alloc_node( value_type * pVal )
1182 m_Stat.onNodeCreated();
1183 return cxx_node_allocator().New( pVal );
1186 void delete_node( node_type * pNode )
1188 m_Stat.onNodeRemoved();
1189 cxx_node_allocator().Delete( pNode );
1192 static void retire_data( value_type * pVal )
1194 assert( pVal != nullptr );
1195 gc::template retire<disposer>( pVal );
1200 node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1201 while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
1202 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1204 retire_data( pVal );
1205 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1206 delete_node( pNode );
1211 bool link_data( value_type * pVal, insert_position& pos )
1213 assert( pos.pPrev != nullptr );
1214 assert( pos.pCur != nullptr );
1216 // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1217 // if current thread will be preempted and another thread will delete pos.pCur data
1218 // and then set it to another.
1219 // To prevent this we mark pos.pCur data as undeletable by setting LSB
1220 marked_data_ptr valCur( pos.pFound );
1221 if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1222 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1223 m_Stat.onNodeMarkFailed();
1227 marked_data_ptr valPrev( pos.pPrevVal );
1228 if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1229 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1230 m_Stat.onNodeMarkFailed();
1234 // checks if link pPrev -> pCur is broken
1235 if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
1236 // sequence pPrev - pCur is broken
1237 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1238 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1239 m_Stat.onNodeSeqBreak();
1243 if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr )
1247 // Set pos.pPrev data if it is null
1249 bool result = pos.pPrev->data.compare_exchange_strong( valPrev, marked_data_ptr( pVal ),
1250 memory_model::memory_order_release, atomics::memory_order_relaxed );
1252 // Clears data marks
1253 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1256 m_Stat.onReuseNode();
1261 // insert new node between pos.pPrev and pos.pCur
1262 node_type * pNode = alloc_node( pVal );
1263 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1265 bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1267 // Clears data marks
1268 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1269 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1272 m_Stat.onNewNodeCreated();
1276 delete_node( pNode );
1282 static bool unlink_data( position& pos )
1284 assert( pos.pCur != nullptr );
1285 assert( pos.pFound != nullptr );
1287 marked_data_ptr val( pos.pFound );
1288 if ( pos.pCur->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1289 retire_data( pos.pFound );
1296 }} // namespace cds::intrusive
1298 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H