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_LAZY_LIST_RCU_H
32 #define CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H
34 #include <mutex> // unique_lock
35 #include <cds/intrusive/details/lazy_list_base.h>
36 #include <cds/urcu/details/check_deadlock.h>
37 #include <cds/details/binary_functor_wrapper.h>
38 #include <cds/urcu/exempt_ptr.h>
40 namespace cds { namespace intrusive {
42 /// Lazy list node for \ref cds_urcu_desc "RCU"
45 - Tag - a tag used to distinguish between different implementation
47 template <class RCU, typename Lock, typename Tag>
48 struct node<cds::urcu::gc<RCU>, Lock, Tag>
50 typedef cds::urcu::gc<RCU> gc ; ///< RCU schema
51 typedef Lock lock_type ; ///< Lock type
52 typedef Tag tag ; ///< tag
54 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
55 typedef atomics::atomic<marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
57 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the list
58 mutable lock_type m_Lock ; ///< Node lock
60 /// Checks if node is marked
61 bool is_marked() const
63 return m_pNext.load(atomics::memory_order_relaxed).bits() != 0;
71 /// Clears internal fields
74 m_pNext.store( marked_ptr(), atomics::memory_order_release );
77 } // namespace lazy_list
80 /// Lazy ordered single-linked list (template specialization for \ref cds_urcu_desc "RCU")
81 /** @ingroup cds_intrusive_list
82 \anchor cds_intrusive_LazyList_rcu
84 Usually, ordered single-linked list is used as a building block for the hash table implementation.
85 The complexity of searching is <tt>O(N)</tt>.
88 - \p RCU - one of \ref cds_urcu_gc "RCU type"
89 - \p T - type to be stored in the list
90 - \p Traits - type traits. See \p lazy_list::traits for explanation.
91 It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction instead of \p Traits template
95 Before including <tt><cds/intrusive/lazy_list_rcu.h></tt> you should include appropriate RCU header file,
96 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
97 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
99 #include <cds/urcu/general_buffered.h>
100 #include <cds/intrusive/lazy_list_rcu.h>
102 // Now, you can declare lazy list for type Foo and default traits:
103 typedef cds::intrusive::LazyList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_lazy_list;
110 #ifdef CDS_DOXYGEN_INVOKED
111 ,class Traits = lazy_list::traits
116 class LazyList<cds::urcu::gc<RCU>, T, Traits>
119 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
120 typedef T value_type; ///< type of value stored in the list
121 typedef Traits traits; ///< Traits template parameter
123 typedef typename traits::hook hook; ///< hook type
124 typedef typename hook::node_type node_type; ///< node type
126 # ifdef CDS_DOXYGEN_INVOKED
127 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
129 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
132 typedef typename traits::disposer disposer; ///< disposer used
133 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
134 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
136 typedef typename traits::back_off back_off; ///< back-off strategy (not used)
137 typedef typename traits::item_counter item_counter; ///< Item counting policy used
138 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
139 typedef typename traits::stat stat; ///< Internal statistics
140 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
142 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
143 static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
145 static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
148 // Rebind traits (split-list support)
149 template <typename... Options>
150 struct rebind_traits {
154 , typename cds::opt::make_options< traits, Options...>::type
159 template <typename Stat>
160 using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >;
164 node_type m_Head; ///< List head (dummy node)
165 node_type m_Tail; ///< List tail (dummy node)
166 item_counter m_ItemCounter; ///< Item counter
167 mutable stat m_Stat; ///< Internal statistics
170 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
171 typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
173 /// Position pointer for item search
175 node_type * pPred; ///< Previous node
176 node_type * pCur; ///< Current node
178 /// Locks nodes \p pPred and \p pCur
181 pPred->m_Lock.lock();
185 /// Unlocks nodes \p pPred and \p pCur
188 pCur->m_Lock.unlock();
189 pPred->m_Lock.unlock();
193 typedef std::unique_lock< position > scoped_position_lock;
195 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> deadlock_policy;
197 struct clear_and_dispose {
198 void operator()( value_type * p )
200 assert( p != nullptr );
201 clear_links( node_traits::to_node_ptr(p));
208 /// pointer to extracted node
209 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
210 /// Type of \p get() member function return value
211 typedef value_type * raw_ptr;
215 template <bool IsConst>
218 friend class LazyList;
221 value_type * m_pNode;
225 assert( m_pNode != nullptr );
227 node_type * pNode = node_traits::to_node_ptr( m_pNode );
228 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
229 if ( pNext != nullptr )
230 m_pNode = node_traits::to_value_ptr( pNext );
235 if ( m_pNode != nullptr ) {
236 node_type * pNode = node_traits::to_node_ptr( m_pNode );
238 // Dummy tail node could not be marked
239 while ( pNode->is_marked())
240 pNode = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
242 if ( pNode != node_traits::to_node_ptr( m_pNode ))
243 m_pNode = node_traits::to_value_ptr( pNode );
247 iterator_type( node_type * pNode )
249 m_pNode = node_traits::to_value_ptr( pNode );
254 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
255 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
261 iterator_type( iterator_type const& src )
262 : m_pNode( src.m_pNode )
265 value_ptr operator ->() const
270 value_ref operator *() const
272 assert( m_pNode != nullptr );
277 iterator_type& operator ++()
285 iterator_type operator ++(int)
287 iterator_type i(*this);
293 iterator_type& operator = (iterator_type const& src)
295 m_pNode = src.m_pNode;
300 bool operator ==(iterator_type<C> const& i ) const
302 return m_pNode == i.m_pNode;
305 bool operator !=(iterator_type<C> const& i ) const
307 return m_pNode != i.m_pNode;
313 ///@name Forward iterators (thread-safe only under RCU lock)
317 You may safely use iterators in multi-threaded environment only under RCU lock.
318 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
320 typedef iterator_type<false> iterator;
322 /// Const forward iterator
323 typedef iterator_type<true> const_iterator;
325 /// Returns a forward iterator addressing the first element in a list
327 For empty list \code begin() == end() \endcode
331 iterator it( &m_Head );
332 ++it ; // skip dummy head
336 /// Returns an iterator that addresses the location succeeding the last element in a list
338 Do not use the value returned by <tt>end</tt> function to access any item.
340 The returned value can be used only to control reaching the end of the list.
341 For empty list \code begin() == end() \endcode
345 return iterator( &m_Tail );
348 /// Returns a forward const iterator addressing the first element in a list
349 const_iterator begin() const
351 return get_const_begin();
354 /// Returns a forward const iterator addressing the first element in a list
355 const_iterator cbegin() const
357 return get_const_begin();
360 /// Returns an const iterator that addresses the location succeeding the last element in a list
361 const_iterator end() const
363 return get_const_end();
366 /// Returns an const iterator that addresses the location succeeding the last element in a list
367 const_iterator cend() const
369 return get_const_end();
374 /// Default constructor initializes empty list
377 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
381 template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
382 explicit LazyList( Stat& st )
385 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
389 /// Destroys the list object
394 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
395 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
400 The function inserts \p val in the list if the list does not contain
401 an item with key equal to \p val.
403 Returns \p true if \p val is linked into the list, \p false otherwise.
405 bool insert( value_type& val )
407 return insert_at( &m_Head, val );
412 This function is intended for derived non-intrusive containers.
414 The function allows to split new item creating into two part:
415 - create item with key only
416 - insert new item into the list
417 - if inserting is success, calls \p f functor to initialize value-field of \p val.
419 The functor signature is:
421 void func( value_type& val );
423 where \p val is the item inserted.
424 While the functor \p f is working the item \p val is locked.
425 The user-defined functor is called only if the inserting is success.
427 template <typename Func>
428 bool insert( value_type& val, Func f )
430 return insert_at( &m_Head, val, f );
435 The operation performs inserting or changing data with lock-free manner.
437 If the item \p val not found in the list, then \p val is inserted into the list
438 iff \p bAllowInsert is \p true.
439 Otherwise, the functor \p func is called with item found.
440 The functor signature is:
443 void operator()( bool bNew, value_type& item, value_type& val );
447 - \p bNew - \p true if the item has been inserted, \p false otherwise
448 - \p item - item of the list
449 - \p val - argument \p val passed into the \p update() function
450 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
451 refer to the same thing.
453 The functor may change non-key fields of the \p item.
454 While the functor \p f is calling the item \p item is locked.
456 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
457 \p second is \p true if new item has been added or \p false if the item with \p key
458 already is in the list.
460 The function makes RCU lock internally.
462 template <typename Func>
463 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
465 return update_at( &m_Head, val, func, bAllowInsert );
468 template <typename Func>
469 CDS_DEPRECATED("ensure() is deprecated, use update()")
470 std::pair<bool, bool> ensure( value_type& val, Func func )
472 return update( val, func, true );
476 /// Unlinks the item \p val from the list
478 The function searches the item \p val in the list and unlink it from the list
479 if it is found and it is equal to \p val.
481 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
482 and deletes the item found. \p %unlink() finds an item by key and deletes it
483 only if \p val is an item of that list, i.e. the pointer to item found
484 is equal to <tt> &val </tt>.
486 The function returns \p true if success and \p false otherwise.
488 RCU \p synchronize method can be called. The RCU should not be locked.
489 Note that depending on RCU type used the \ref disposer call can be deferred.
491 \p disposer specified in \p Traits is called for unlinked item.
493 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
494 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
496 bool unlink( value_type& val )
498 return unlink_at( &m_Head, val );
501 /// Deletes the item from the list
503 The function searches an item with key equal to \p key in the list,
504 unlinks it from the list, and returns \p true.
505 If the item with the key equal to \p key is not found the function return \p false.
507 RCU \p synchronize method can be called. The RCU should not be locked.
508 Note that depending on RCU type used the \ref disposer call can be deferred.
510 \p disposer specified in \p Traits is called for deleted item.
512 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
513 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
515 template <typename Q>
516 bool erase( Q const& key )
518 return erase_at( &m_Head, key, key_comparator());
521 /// Deletes the item from the list using \p pred predicate for searching
523 The function is an analog of \p erase(Q const&)
524 but \p pred is used for key comparing.
525 \p Less functor has the interface like \p std::less.
526 \p pred must imply the same element order as the comparator used for building the list.
528 \p disposer specified in \p Traits is called for deleted item.
530 template <typename Q, typename Less>
531 bool erase_with( Q const& key, Less pred )
534 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
537 /// Deletes the item from the list
539 The function searches an item with key equal to \p key in the list,
540 call \p func functor with item found, unlinks it from the list, and returns \p true.
541 The \p Func interface is
544 void operator()( value_type const& item );
548 If the item with the key equal to \p key is not found the function return \p false.
550 RCU \p synchronize method can be called. The RCU should not be locked.
551 Note that depending on RCU type used the \ref disposer call can be deferred.
553 \p disposer specified in \p Traits is called for deleted item.
555 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
556 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
558 template <typename Q, typename Func>
559 bool erase( Q const& key, Func func )
561 return erase_at( &m_Head, key, key_comparator(), func );
564 /// Deletes the item from the list using \p pred predicate for searching
566 The function is an analog of \p erase(Q const&, Func)
567 but \p pred is used for key comparing.
568 \p Less functor has the interface like \p std::less.
569 \p pred must imply the same element order as the comparator used for building the list.
571 \p disposer specified in \p Traits is called for deleted item.
573 template <typename Q, typename Less, typename Func>
574 bool erase_with( Q const& key, Less pred, Func func )
577 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
580 /// Extracts an item from the list
582 The function searches an item with key equal to \p key in the list,
583 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
584 If the item is not found the function returns empty \p exempt_ptr.
586 @note The function does NOT call RCU read-side lock or synchronization,
587 and does NOT dispose the item found. It just unlinks the item from the list
588 and returns a pointer to it.
589 You should manually lock RCU before calling this function, and you should manually release
590 the returned exempt pointer outside the RCU lock region before reusing returned pointer.
593 #include <cds/urcu/general_buffered.h>
594 #include <cds/intrusive/lazy_list_rcu.h>
596 typedef cds::urcu::gc< general_buffered<> > rcu;
597 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
599 rcu_lazy_list theList;
602 rcu_lazy_list::exempt_ptr p1;
604 // first, we should lock RCU
607 // Now, you can apply extract function
608 // Note that you must not delete the item found inside the RCU lock
609 p1 = theList.extract( 10 )
611 // do something with p1
616 // We may safely release p1 here
617 // release() passes the pointer to RCU reclamation cycle:
618 // it invokes RCU retire_ptr function with the disposer you provided for the list.
622 template <typename Q>
623 exempt_ptr extract( Q const& key )
625 return exempt_ptr( extract_at( &m_Head, key, key_comparator()));
628 /// Extracts an item from the list using \p pred predicate for searching
630 This function is the analog for \p extract(Q const&).
632 The \p pred is a predicate used for key comparing.
633 \p Less has the interface like \p std::less.
634 \p pred must imply the same element order as \ref key_comparator.
636 template <typename Q, typename Less>
637 exempt_ptr extract_with( Q const& key, Less pred )
640 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>()));
643 /// Finds the key \p key
645 The function searches the item with key equal to \p key
646 and calls the functor \p f for item found.
647 The interface of \p Func functor is:
650 void operator()( value_type& item, Q& key );
653 where \p item is the item found, \p key is the <tt>find</tt> function argument.
655 The functor may change non-key fields of \p item.
656 While the functor \p f is calling the item found \p item is locked.
658 The function returns \p true if \p key is found, \p false otherwise.
660 template <typename Q, typename Func>
661 bool find( Q& key, Func f ) const
663 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
666 template <typename Q, typename Func>
667 bool find( Q const& key, Func f ) const
669 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
673 /// Finds the key \p key using \p pred predicate for searching
675 The function is an analog of \p find( Q&, Func ) but \p pred is used for key comparing.
676 \p Less functor has the interface like \p std::less.
677 \p pred must imply the same element order as the comparator used for building the list.
679 template <typename Q, typename Less, typename Func>
680 bool find_with( Q& key, Less pred, Func f ) const
683 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
686 template <typename Q, typename Less, typename Func>
687 bool find_with( Q const& key, Less pred, Func f ) const
690 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
694 /// Checks whether the list contains \p key
696 The function searches the item with key equal to \p key
697 and returns \p true if it is found, and \p false otherwise.
699 template <typename Q>
700 bool contains( Q const& key ) const
702 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
705 template <typename Q>
706 CDS_DEPRECATED("deprecated, use contains()")
707 bool find( Q const& key ) const
709 return contains( key );
713 /// Checks whether the map contains \p key using \p pred predicate for searching
715 The function is an analog of \p contains( Q const& ) but \p pred is used for key comparing.
716 \p Less functor has the interface like \p std::less.
717 \p Less must imply the same element order as the comparator used for building the list.
719 template <typename Q, typename Less>
720 bool contains( Q const& key, Less pred ) const
723 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
726 template <typename Q, typename Less>
727 CDS_DEPRECATED("deprecated, use contains()")
728 bool find_with( Q const& key, Less pred ) const
730 return contains( key, pred );
734 /// Finds the key \p key and return the item found
735 /** \anchor cds_intrusive_LazyList_rcu_get
736 The function searches the item with key equal to \p key and returns the pointer to item found.
737 If \p key is not found it returns \p nullptr.
739 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
741 RCU should be locked before call of this function.
742 Returned item is valid only while RCU is locked:
744 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
749 typename ord_list::rcu_lock lock;
751 foo * pVal = theList.get( 5 );
756 // Unlock RCU by rcu_lock destructor
757 // pVal can be retired by disposer at any time after RCU has been unlocked
761 template <typename Q>
762 value_type * get( Q const& key ) const
764 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
767 /// Finds the key \p key and return the item found
769 The function is an analog of \ref cds_intrusive_LazyList_rcu_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 value_type * get_with( Q const& key, Less pred ) const
780 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
783 /// Clears the list using default disposer
785 The function clears the list using default (provided in class template) disposer functor.
787 RCU \p synchronize method can be called.
788 Note that depending on RCU type used the \ref disposer call can be deferred.
790 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
791 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
796 deadlock_policy::check();
802 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
803 if ( pHead == &m_Tail )
806 m_Head.m_Lock.lock();
807 pHead->m_Lock.lock();
809 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
810 unlink_node( &m_Head, pHead, &m_Head );
812 pHead->m_Lock.unlock();
813 m_Head.m_Lock.unlock();
817 dispose_node( pHead );
822 /// Checks if the list is empty
825 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
828 /// Returns list's item count
830 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
831 this function always returns 0.
833 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
834 is empty. To check list emptiness use \ref empty() method.
838 return m_ItemCounter.value();
841 /// Returns const reference to internal statistics
842 stat const& statistics() const
849 static void clear_links( node_type * pNode )
851 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
854 static void dispose_node( node_type * pNode )
857 assert( !gc::is_locked());
859 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ));
862 static void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
864 assert( pPred->m_pNext.load( memory_model::memory_order_relaxed ).ptr() == pCur );
865 link_checker::is_empty( pNode );
867 pNode->m_pNext.store( marked_node_ptr( pCur ), memory_model::memory_order_relaxed );
868 pPred->m_pNext.store( marked_node_ptr( pNode ), memory_model::memory_order_release );
871 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
873 assert( pPred->m_pNext.load( memory_model::memory_order_relaxed ).ptr() == pCur );
874 assert( pCur != &m_Tail );
876 node_type * pNext = pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr();
877 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
878 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release ); // physically deleting
881 // split-list support
882 bool insert_aux_node( node_type * pNode )
884 return insert_aux_node( &m_Head, pNode );
887 // split-list support
888 bool insert_aux_node( node_type * pHead, node_type * pNode )
890 assert( pHead != nullptr );
891 assert( pNode != nullptr );
893 // Hack: convert node_type to value_type.
894 // Actually, an auxiliary node should not be converted to value_type
895 // We assume that comparator can correctly distinguish aux and regular node.
896 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
899 bool insert_at( node_type * pHead, value_type& val )
902 return insert_at_locked( pHead, val );
905 template <typename Func>
906 bool insert_at( node_type * pHead, value_type& val, Func f )
913 search( pHead, val, pos );
915 scoped_position_lock sl( pos );
916 if ( validate( pos.pPred, pos.pCur )) {
917 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
918 // failed: key already in list
919 m_Stat.onInsertFailed();
924 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
929 m_Stat.onInsertRetry();
933 m_Stat.onInsertSuccess();
937 iterator insert_at_( node_type * pHead, value_type& val )
940 if ( insert_at_locked( pHead, val ))
941 return iterator( node_traits::to_node_ptr( val ));
946 template <typename Func>
947 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
950 return update_at_locked( pHead, val, func, bAllowInsert );
953 template <typename Func>
954 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
957 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
958 return std::make_pair( ret.first != end(), ret.second );
961 bool unlink_at( node_type * pHead, value_type& val )
965 deadlock_policy::check();
971 search( pHead, val, pos );
973 scoped_position_lock alp( pos );
974 if ( validate( pos.pPred, pos.pCur )) {
975 if ( pos.pCur != &m_Tail
976 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
977 && node_traits::to_value_ptr( pos.pCur ) == &val )
980 unlink_node( pos.pPred, pos.pCur, pHead );
992 dispose_node( pos.pCur );
993 m_Stat.onEraseSuccess();
997 m_Stat.onEraseFailed();
1001 m_Stat.onEraseRetry();
1005 template <typename Q, typename Compare, typename Func>
1006 bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
1008 deadlock_policy::check();
1014 search( pHead, val, pos, cmp );
1016 scoped_position_lock alp( pos );
1017 if ( validate( pos.pPred, pos.pCur )) {
1018 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1020 unlink_node( pos.pPred, pos.pCur, pHead );
1021 f( *node_traits::to_value_ptr( *pos.pCur ));
1031 if ( nResult > 0 ) {
1033 dispose_node( pos.pCur );
1034 m_Stat.onEraseSuccess();
1038 m_Stat.onEraseFailed();
1042 m_Stat.onEraseRetry();
1046 template <typename Q, typename Compare, typename Func>
1047 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1050 return erase_at( pHead, val, cmp, f, pos );
1053 template <typename Q, typename Compare>
1054 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1057 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1060 template <typename Q, typename Compare>
1061 value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1064 assert( gc::is_locked()) ; // RCU must be locked
1067 search( pHead, val, pos, cmp );
1070 scoped_position_lock alp( pos );
1071 if ( validate( pos.pPred, pos.pCur )) {
1072 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1074 unlink_node( pos.pPred, pos.pCur, pHead );
1084 if ( nResult > 0 ) {
1086 m_Stat.onEraseSuccess();
1087 return node_traits::to_value_ptr( pos.pCur );
1090 m_Stat.onEraseFailed();
1094 m_Stat.onEraseRetry();
1098 template <typename Q, typename Compare, typename Func>
1099 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1104 search( pHead, val, pos, cmp );
1105 if ( pos.pCur != &m_Tail ) {
1106 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1107 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1108 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1109 m_Stat.onFindSuccess();
1114 m_Stat.onFindFailed();
1118 template <typename Q, typename Compare>
1119 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1122 return find_at_( pHead, val, cmp ) != end();
1125 template <typename Q, typename Compare>
1126 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1128 assert( gc::is_locked());
1132 search( pHead, val, pos, cmp );
1133 if ( pos.pCur != &m_Tail ) {
1134 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1135 m_Stat.onFindSuccess();
1136 return const_iterator( pos.pCur );
1140 m_Stat.onFindFailed();
1144 template <typename Q, typename Compare>
1145 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1147 value_type * pFound = nullptr;
1148 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1156 template <typename Q>
1157 void search( node_type * const pHead, Q const& key, position& pos ) const
1159 search( pHead, key, pos, key_comparator());
1162 template <typename Q, typename Compare>
1163 void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1165 // RCU should be locked
1166 assert( gc::is_locked());
1168 node_type const* pTail = &m_Tail;
1170 marked_node_ptr pCur(pHead);
1171 marked_node_ptr pPrev(pHead);
1173 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1175 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1177 pPrev = pCur = pHead;
1180 pos.pCur = pCur.ptr();
1181 pos.pPred = pPrev.ptr();
1184 bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1186 if ( validate_link( pPred, pCur )) {
1187 m_Stat.onValidationSuccess();
1191 m_Stat.onValidationFailed();
1195 static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1197 // RCU lock should be locked
1198 assert( gc::is_locked());
1200 return !pPred->is_marked()
1201 && !pCur->is_marked()
1202 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1209 bool insert_at_locked( node_type * pHead, value_type& val )
1211 // RCU lock should be locked
1212 assert( gc::is_locked());
1218 search( pHead, val, pos );
1220 scoped_position_lock alp( pos );
1221 if ( validate( pos.pPred, pos.pCur )) {
1222 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1223 // failed: key already in list
1224 m_Stat.onInsertFailed();
1228 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1233 m_Stat.onInsertRetry();
1237 m_Stat.onInsertSuccess();
1242 template <typename Func>
1243 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1245 // RCU lock should be locked
1246 assert( gc::is_locked());
1252 search( pHead, val, pos );
1254 scoped_position_lock alp( pos );
1255 if ( validate( pos.pPred, pos.pCur )) {
1256 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1257 // key already in the list
1259 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1260 m_Stat.onUpdateExisting();
1261 return std::make_pair( iterator( pos.pCur ), false );
1265 if ( !bAllowInsert ) {
1266 m_Stat.onUpdateFailed();
1267 return std::make_pair( end(), false );
1270 func( true, val, val );
1271 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1277 m_Stat.onUpdateRetry();
1281 m_Stat.onUpdateNew();
1282 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1288 const_iterator get_const_begin() const
1290 const_iterator it( const_cast<node_type *>(&m_Head));
1291 ++it; // skip dummy head
1294 const_iterator get_const_end() const
1296 return const_iterator( const_cast<node_type *>(&m_Tail));
1301 }} // namespace cds::intrusive
1303 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H