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_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
161 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
162 typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
166 node_type m_Head; ///< List head (dummy node)
167 node_type m_Tail; ///< List tail (dummy node)
168 item_counter m_ItemCounter; ///< Item counter
169 mutable stat m_Stat; ///< Internal statistics
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;
200 static void clear_links( node_type * pNode )
202 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
205 struct clear_and_dispose {
206 void operator()( value_type * p )
208 assert( p != nullptr );
209 clear_links( node_traits::to_node_ptr(p));
214 static void dispose_node( node_type * pNode )
217 assert( !gc::is_locked());
219 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ));
222 static void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
224 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
225 link_checker::is_empty( pNode );
227 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed );
228 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
231 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
233 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
234 assert( pCur != &m_Tail );
236 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
237 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
238 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
244 /// pointer to extracted node
245 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
246 /// Type of \p get() member function return value
247 typedef value_type * raw_ptr;
251 template <bool IsConst>
254 friend class LazyList;
257 value_type * m_pNode;
261 assert( m_pNode != nullptr );
263 node_type * pNode = node_traits::to_node_ptr( m_pNode );
264 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
265 if ( pNext != nullptr )
266 m_pNode = node_traits::to_value_ptr( pNext );
271 if ( m_pNode != nullptr ) {
272 node_type * pNode = node_traits::to_node_ptr( m_pNode );
274 // Dummy tail node could not be marked
275 while ( pNode->is_marked())
276 pNode = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
278 if ( pNode != node_traits::to_node_ptr( m_pNode ))
279 m_pNode = node_traits::to_value_ptr( pNode );
283 iterator_type( node_type * pNode )
285 m_pNode = node_traits::to_value_ptr( pNode );
290 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
291 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
297 iterator_type( iterator_type const& src )
298 : m_pNode( src.m_pNode )
301 value_ptr operator ->() const
306 value_ref operator *() const
308 assert( m_pNode != nullptr );
313 iterator_type& operator ++()
321 iterator_type operator ++(int)
323 iterator_type i(*this);
329 iterator_type& operator = (iterator_type const& src)
331 m_pNode = src.m_pNode;
336 bool operator ==(iterator_type<C> const& i ) const
338 return m_pNode == i.m_pNode;
341 bool operator !=(iterator_type<C> const& i ) const
343 return m_pNode != i.m_pNode;
349 ///@name Forward iterators (thread-safe only under RCU lock)
353 You may safely use iterators in multi-threaded environment only under RCU lock.
354 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
356 typedef iterator_type<false> iterator;
358 /// Const forward iterator
359 typedef iterator_type<true> const_iterator;
361 /// Returns a forward iterator addressing the first element in a list
363 For empty list \code begin() == end() \endcode
367 iterator it( &m_Head );
368 ++it ; // skip dummy head
372 /// Returns an iterator that addresses the location succeeding the last element in a list
374 Do not use the value returned by <tt>end</tt> function to access any item.
376 The returned value can be used only to control reaching the end of the list.
377 For empty list \code begin() == end() \endcode
381 return iterator( &m_Tail );
384 /// Returns a forward const iterator addressing the first element in a list
385 const_iterator begin() const
387 return get_const_begin();
390 /// Returns a forward const iterator addressing the first element in a list
391 const_iterator cbegin() const
393 return get_const_begin();
396 /// Returns an const iterator that addresses the location succeeding the last element in a list
397 const_iterator end() const
399 return get_const_end();
402 /// Returns an const iterator that addresses the location succeeding the last element in a list
403 const_iterator cend() const
405 return get_const_end();
411 const_iterator get_const_begin() const
413 const_iterator it( const_cast<node_type *>( &m_Head ));
414 ++it ; // skip dummy head
417 const_iterator get_const_end() const
419 return const_iterator( const_cast<node_type *>( &m_Tail ));
424 /// Default constructor initializes empty list
427 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
431 template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
432 explicit LazyList( Stat& st )
435 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
439 /// Destroys the list object
444 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
445 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
450 The function inserts \p val in the list if the list does not contain
451 an item with key equal to \p val.
453 Returns \p true if \p val is linked into the list, \p false otherwise.
455 bool insert( value_type& val )
457 return insert_at( &m_Head, val );
462 This function is intended for derived non-intrusive containers.
464 The function allows to split new item creating into two part:
465 - create item with key only
466 - insert new item into the list
467 - if inserting is success, calls \p f functor to initialize value-field of \p val.
469 The functor signature is:
471 void func( value_type& val );
473 where \p val is the item inserted.
474 While the functor \p f is working the item \p val is locked.
475 The user-defined functor is called only if the inserting is success.
477 template <typename Func>
478 bool insert( value_type& val, Func f )
480 return insert_at( &m_Head, val, f );
485 The operation performs inserting or changing data with lock-free manner.
487 If the item \p val not found in the list, then \p val is inserted into the list
488 iff \p bAllowInsert is \p true.
489 Otherwise, the functor \p func is called with item found.
490 The functor signature is:
493 void operator()( bool bNew, value_type& item, value_type& val );
497 - \p bNew - \p true if the item has been inserted, \p false otherwise
498 - \p item - item of the list
499 - \p val - argument \p val passed into the \p update() function
500 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
501 refer to the same thing.
503 The functor may change non-key fields of the \p item.
504 While the functor \p f is calling the item \p item is locked.
506 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
507 \p second is \p true if new item has been added or \p false if the item with \p key
508 already is in the list.
510 The function makes RCU lock internally.
512 template <typename Func>
513 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
515 return update_at( &m_Head, val, func, bAllowInsert );
518 template <typename Func>
519 CDS_DEPRECATED("ensure() is deprecated, use update()")
520 std::pair<bool, bool> ensure( value_type& val, Func func )
522 return update( val, func, true );
526 /// Unlinks the item \p val from the list
528 The function searches the item \p val in the list and unlink it from the list
529 if it is found and it is equal to \p val.
531 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
532 and deletes the item found. \p %unlink() finds an item by key and deletes it
533 only if \p val is an item of that list, i.e. the pointer to item found
534 is equal to <tt> &val </tt>.
536 The function returns \p true if success and \p false otherwise.
538 RCU \p synchronize method can be called. The RCU should not be locked.
539 Note that depending on RCU type used the \ref disposer call can be deferred.
541 \p disposer specified in \p Traits is called for unlinked item.
543 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
544 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
546 bool unlink( value_type& val )
548 return unlink_at( &m_Head, val );
551 /// Deletes the item from the list
553 The function searches an item with key equal to \p key in the list,
554 unlinks it from the list, and returns \p true.
555 If the item with the key equal to \p key is not found the function return \p false.
557 RCU \p synchronize method can be called. The RCU should not be locked.
558 Note that depending on RCU type used the \ref disposer call can be deferred.
560 \p disposer specified in \p Traits is called for deleted item.
562 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
563 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
565 template <typename Q>
566 bool erase( Q const& key )
568 return erase_at( &m_Head, key, key_comparator());
571 /// Deletes the item from the list using \p pred predicate for searching
573 The function is an analog of \p erase(Q const&)
574 but \p pred is used for key comparing.
575 \p Less functor has the interface like \p std::less.
576 \p pred must imply the same element order as the comparator used for building the list.
578 \p disposer specified in \p Traits is called for deleted item.
580 template <typename Q, typename Less>
581 bool erase_with( Q const& key, Less pred )
584 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
587 /// Deletes the item from the list
589 The function searches an item with key equal to \p key in the list,
590 call \p func functor with item found, unlinks it from the list, and returns \p true.
591 The \p Func interface is
594 void operator()( value_type const& item );
598 If the item with the key equal to \p key is not found the function return \p false.
600 RCU \p synchronize method can be called. The RCU should not be locked.
601 Note that depending on RCU type used the \ref disposer call can be deferred.
603 \p disposer specified in \p Traits is called for deleted item.
605 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
606 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
608 template <typename Q, typename Func>
609 bool erase( Q const& key, Func func )
611 return erase_at( &m_Head, key, key_comparator(), func );
614 /// Deletes the item from the list using \p pred predicate for searching
616 The function is an analog of \p erase(Q const&, Func)
617 but \p pred is used for key comparing.
618 \p Less functor has the interface like \p std::less.
619 \p pred must imply the same element order as the comparator used for building the list.
621 \p disposer specified in \p Traits is called for deleted item.
623 template <typename Q, typename Less, typename Func>
624 bool erase_with( Q const& key, Less pred, Func func )
627 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
630 /// Extracts an item from the list
632 The function searches an item with key equal to \p key in the list,
633 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
634 If the item is not found the function returns empty \p exempt_ptr.
636 @note The function does NOT call RCU read-side lock or synchronization,
637 and does NOT dispose the item found. It just unlinks the item from the list
638 and returns a pointer to it.
639 You should manually lock RCU before calling this function, and you should manually release
640 the returned exempt pointer outside the RCU lock region before reusing returned pointer.
643 #include <cds/urcu/general_buffered.h>
644 #include <cds/intrusive/lazy_list_rcu.h>
646 typedef cds::urcu::gc< general_buffered<> > rcu;
647 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
649 rcu_lazy_list theList;
652 rcu_lazy_list::exempt_ptr p1;
654 // first, we should lock RCU
657 // Now, you can apply extract function
658 // Note that you must not delete the item found inside the RCU lock
659 p1 = theList.extract( 10 )
661 // do something with p1
666 // We may safely release p1 here
667 // release() passes the pointer to RCU reclamation cycle:
668 // it invokes RCU retire_ptr function with the disposer you provided for the list.
672 template <typename Q>
673 exempt_ptr extract( Q const& key )
675 return exempt_ptr( extract_at( &m_Head, key, key_comparator()));
678 /// Extracts an item from the list using \p pred predicate for searching
680 This function is the analog for \p extract(Q const&).
682 The \p pred is a predicate used for key comparing.
683 \p Less has the interface like \p std::less.
684 \p pred must imply the same element order as \ref key_comparator.
686 template <typename Q, typename Less>
687 exempt_ptr extract_with( Q const& key, Less pred )
690 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>()));
693 /// Finds the key \p key
695 The function searches the item with key equal to \p key
696 and calls the functor \p f for item found.
697 The interface of \p Func functor is:
700 void operator()( value_type& item, Q& key );
703 where \p item is the item found, \p key is the <tt>find</tt> function argument.
705 The functor may change non-key fields of \p item.
706 While the functor \p f is calling the item found \p item is locked.
708 The function returns \p true if \p key is found, \p false otherwise.
710 template <typename Q, typename Func>
711 bool find( Q& key, Func f ) const
713 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
716 template <typename Q, typename Func>
717 bool find( Q const& key, Func f ) const
719 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
723 /// Finds the key \p key using \p pred predicate for searching
725 The function is an analog of \p find( Q&, Func ) but \p pred is used for key comparing.
726 \p Less functor has the interface like \p std::less.
727 \p pred must imply the same element order as the comparator used for building the list.
729 template <typename Q, typename Less, typename Func>
730 bool find_with( Q& key, Less pred, Func f ) const
733 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
736 template <typename Q, typename Less, typename Func>
737 bool find_with( Q const& key, Less pred, Func f ) const
740 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
744 /// Checks whether the list contains \p key
746 The function searches the item with key equal to \p key
747 and returns \p true if it is found, and \p false otherwise.
749 template <typename Q>
750 bool contains( Q const& key ) const
752 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
755 template <typename Q>
756 CDS_DEPRECATED("deprecated, use contains()")
757 bool find( Q const& key ) const
759 return contains( key );
763 /// Checks whether the map contains \p key using \p pred predicate for searching
765 The function is an analog of \p contains( Q const& ) but \p pred is used for key comparing.
766 \p Less functor has the interface like \p std::less.
767 \p Less must imply the same element order as the comparator used for building the list.
769 template <typename Q, typename Less>
770 bool contains( Q const& key, Less pred ) const
773 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
776 template <typename Q, typename Less>
777 CDS_DEPRECATED("deprecated, use contains()")
778 bool find_with( Q const& key, Less pred ) const
780 return contains( key, pred );
784 /// Finds the key \p key and return the item found
785 /** \anchor cds_intrusive_LazyList_rcu_get
786 The function searches the item with key equal to \p key and returns the pointer to item found.
787 If \p key is not found it returns \p nullptr.
789 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
791 RCU should be locked before call of this function.
792 Returned item is valid only while RCU is locked:
794 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
799 typename ord_list::rcu_lock lock;
801 foo * pVal = theList.get( 5 );
806 // Unlock RCU by rcu_lock destructor
807 // pVal can be retired by disposer at any time after RCU has been unlocked
811 template <typename Q>
812 value_type * get( Q const& key ) const
814 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
817 /// Finds the key \p key and return the item found
819 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
820 but \p pred is used for comparing the keys.
822 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
824 \p pred must imply the same element order as the comparator used for building the list.
826 template <typename Q, typename Less>
827 value_type * get_with( Q const& key, Less pred ) const
830 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
833 /// Clears the list using default disposer
835 The function clears the list using default (provided in class template) disposer functor.
837 RCU \p synchronize method can be called.
838 Note that depending on RCU type used the \ref disposer call can be deferred.
840 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
841 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
846 deadlock_policy::check();
852 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
853 if ( pHead == &m_Tail )
856 m_Head.m_Lock.lock();
857 pHead->m_Lock.lock();
859 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
860 unlink_node( &m_Head, pHead, &m_Head );
862 pHead->m_Lock.unlock();
863 m_Head.m_Lock.unlock();
867 dispose_node( pHead );
872 /// Checks if the list is empty
875 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
878 /// Returns list's item count
880 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
881 this function always returns 0.
883 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
884 is empty. To check list emptiness use \ref empty() method.
888 return m_ItemCounter.value();
891 /// Returns const reference to internal statistics
892 stat const& statistics() const
899 // split-list support
900 bool insert_aux_node( node_type * pNode )
902 return insert_aux_node( &m_Head, pNode );
905 // split-list support
906 bool insert_aux_node( node_type * pHead, node_type * pNode )
908 assert( pHead != nullptr );
909 assert( pNode != nullptr );
911 // Hack: convert node_type to value_type.
912 // Actually, an auxiliary node should not be converted to value_type
913 // We assume that comparator can correctly distinguish aux and regular node.
914 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
917 bool insert_at( node_type * pHead, value_type& val )
920 return insert_at_locked( pHead, val );
923 template <typename Func>
924 bool insert_at( node_type * pHead, value_type& val, Func f )
931 search( pHead, val, pos );
933 scoped_position_lock sl( pos );
934 if ( validate( pos.pPred, pos.pCur )) {
935 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
936 // failed: key already in list
937 m_Stat.onInsertFailed();
942 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
947 m_Stat.onInsertRetry();
951 m_Stat.onInsertSuccess();
955 iterator insert_at_( node_type * pHead, value_type& val )
958 if ( insert_at_locked( pHead, val ))
959 return iterator( node_traits::to_node_ptr( val ));
964 template <typename Func>
965 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
968 return update_at_locked( pHead, val, func, bAllowInsert );
971 template <typename Func>
972 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
975 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
976 return std::make_pair( ret.first != end(), ret.second );
979 bool unlink_at( node_type * pHead, value_type& val )
983 deadlock_policy::check();
989 search( pHead, val, pos );
991 scoped_position_lock alp( pos );
992 if ( validate( pos.pPred, pos.pCur )) {
993 if ( pos.pCur != &m_Tail
994 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
995 && node_traits::to_value_ptr( pos.pCur ) == &val )
998 unlink_node( pos.pPred, pos.pCur, pHead );
1008 if ( nResult > 0 ) {
1010 dispose_node( pos.pCur );
1011 m_Stat.onEraseSuccess();
1015 m_Stat.onEraseFailed();
1019 m_Stat.onEraseRetry();
1023 template <typename Q, typename Compare, typename Func>
1024 bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
1026 deadlock_policy::check();
1032 search( pHead, val, pos, cmp );
1034 scoped_position_lock alp( pos );
1035 if ( validate( pos.pPred, pos.pCur )) {
1036 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1038 unlink_node( pos.pPred, pos.pCur, pHead );
1039 f( *node_traits::to_value_ptr( *pos.pCur ));
1049 if ( nResult > 0 ) {
1051 dispose_node( pos.pCur );
1052 m_Stat.onEraseSuccess();
1056 m_Stat.onEraseFailed();
1060 m_Stat.onEraseRetry();
1064 template <typename Q, typename Compare, typename Func>
1065 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1068 return erase_at( pHead, val, cmp, f, pos );
1071 template <typename Q, typename Compare>
1072 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1075 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1078 template <typename Q, typename Compare>
1079 value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1082 assert( gc::is_locked()) ; // RCU must be locked
1085 search( pHead, val, pos, cmp );
1088 scoped_position_lock alp( pos );
1089 if ( validate( pos.pPred, pos.pCur )) {
1090 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1092 unlink_node( pos.pPred, pos.pCur, pHead );
1102 if ( nResult > 0 ) {
1104 m_Stat.onEraseSuccess();
1105 return node_traits::to_value_ptr( pos.pCur );
1108 m_Stat.onEraseFailed();
1112 m_Stat.onEraseRetry();
1116 template <typename Q, typename Compare, typename Func>
1117 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1122 search( pHead, val, pos, cmp );
1123 if ( pos.pCur != &m_Tail ) {
1124 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1125 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1126 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1127 m_Stat.onFindSuccess();
1132 m_Stat.onFindFailed();
1136 template <typename Q, typename Compare>
1137 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1140 return find_at_( pHead, val, cmp ) != end();
1143 template <typename Q, typename Compare>
1144 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1146 assert( gc::is_locked());
1150 search( pHead, val, pos, cmp );
1151 if ( pos.pCur != &m_Tail ) {
1152 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1153 m_Stat.onFindSuccess();
1154 return const_iterator( pos.pCur );
1158 m_Stat.onFindFailed();
1162 template <typename Q, typename Compare>
1163 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1165 value_type * pFound = nullptr;
1166 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1174 template <typename Q>
1175 void search( node_type * const pHead, Q const& key, position& pos ) const
1177 search( pHead, key, pos, key_comparator());
1180 template <typename Q, typename Compare>
1181 void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1183 // RCU should be locked
1184 assert( gc::is_locked());
1186 node_type const* pTail = &m_Tail;
1188 marked_node_ptr pCur(pHead);
1189 marked_node_ptr pPrev(pHead);
1191 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1193 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1195 pPrev = pCur = pHead;
1198 pos.pCur = pCur.ptr();
1199 pos.pPred = pPrev.ptr();
1202 bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1204 if ( validate_link( pPred, pCur ) ) {
1205 m_Stat.onValidationSuccess();
1209 m_Stat.onValidationFailed();
1213 static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1215 // RCU lock should be locked
1216 assert( gc::is_locked());
1218 return !pPred->is_marked()
1219 && !pCur->is_marked()
1220 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1227 bool insert_at_locked( node_type * pHead, value_type& val )
1229 // RCU lock should be locked
1230 assert( gc::is_locked());
1236 search( pHead, val, pos );
1238 scoped_position_lock alp( pos );
1239 if ( validate( pos.pPred, pos.pCur )) {
1240 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1241 // failed: key already in list
1242 m_Stat.onInsertFailed();
1246 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1251 m_Stat.onInsertRetry();
1255 m_Stat.onInsertSuccess();
1260 template <typename Func>
1261 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1263 // RCU lock should be locked
1264 assert( gc::is_locked());
1270 search( pHead, val, pos );
1272 scoped_position_lock alp( pos );
1273 if ( validate( pos.pPred, pos.pCur )) {
1274 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1275 // key already in the list
1277 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1278 m_Stat.onUpdateExisting();
1279 return std::make_pair( iterator( pos.pCur ), false );
1283 if ( !bAllowInsert ) {
1284 m_Stat.onUpdateFailed();
1285 return std::make_pair( end(), false );
1288 func( true, val, val );
1289 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1295 m_Stat.onUpdateRetry();
1299 m_Stat.onUpdateNew();
1300 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1305 }} // namespace cds::intrusive
1307 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H