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
159 template <typename Stat>
160 using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >;
165 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
166 typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
170 node_type m_Head; ///< List head (dummy node)
171 node_type m_Tail; ///< List tail (dummy node)
172 item_counter m_ItemCounter; ///< Item counter
173 mutable stat m_Stat; ///< Internal statistics
177 /// Position pointer for item search
179 node_type * pPred; ///< Previous node
180 node_type * pCur; ///< Current node
182 /// Locks nodes \p pPred and \p pCur
185 pPred->m_Lock.lock();
189 /// Unlocks nodes \p pPred and \p pCur
192 pCur->m_Lock.unlock();
193 pPred->m_Lock.unlock();
197 typedef std::unique_lock< position > scoped_position_lock;
199 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> deadlock_policy;
204 static void clear_links( node_type * pNode )
206 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
209 struct clear_and_dispose {
210 void operator()( value_type * p )
212 assert( p != nullptr );
213 clear_links( node_traits::to_node_ptr(p));
218 static void dispose_node( node_type * pNode )
221 assert( !gc::is_locked());
223 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ));
226 static void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
228 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
229 link_checker::is_empty( pNode );
231 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed );
232 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
235 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
237 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
238 assert( pCur != &m_Tail );
240 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
241 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
242 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
248 /// pointer to extracted node
249 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
250 /// Type of \p get() member function return value
251 typedef value_type * raw_ptr;
255 template <bool IsConst>
258 friend class LazyList;
261 value_type * m_pNode;
265 assert( m_pNode != nullptr );
267 node_type * pNode = node_traits::to_node_ptr( m_pNode );
268 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
269 if ( pNext != nullptr )
270 m_pNode = node_traits::to_value_ptr( pNext );
275 if ( m_pNode != nullptr ) {
276 node_type * pNode = node_traits::to_node_ptr( m_pNode );
278 // Dummy tail node could not be marked
279 while ( pNode->is_marked())
280 pNode = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
282 if ( pNode != node_traits::to_node_ptr( m_pNode ))
283 m_pNode = node_traits::to_value_ptr( pNode );
287 iterator_type( node_type * pNode )
289 m_pNode = node_traits::to_value_ptr( pNode );
294 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
295 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
301 iterator_type( iterator_type const& src )
302 : m_pNode( src.m_pNode )
305 value_ptr operator ->() const
310 value_ref operator *() const
312 assert( m_pNode != nullptr );
317 iterator_type& operator ++()
325 iterator_type operator ++(int)
327 iterator_type i(*this);
333 iterator_type& operator = (iterator_type const& src)
335 m_pNode = src.m_pNode;
340 bool operator ==(iterator_type<C> const& i ) const
342 return m_pNode == i.m_pNode;
345 bool operator !=(iterator_type<C> const& i ) const
347 return m_pNode != i.m_pNode;
353 ///@name Forward iterators (thread-safe only under RCU lock)
357 You may safely use iterators in multi-threaded environment only under RCU lock.
358 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
360 typedef iterator_type<false> iterator;
362 /// Const forward iterator
363 typedef iterator_type<true> const_iterator;
365 /// Returns a forward iterator addressing the first element in a list
367 For empty list \code begin() == end() \endcode
371 iterator it( &m_Head );
372 ++it ; // skip dummy head
376 /// Returns an iterator that addresses the location succeeding the last element in a list
378 Do not use the value returned by <tt>end</tt> function to access any item.
380 The returned value can be used only to control reaching the end of the list.
381 For empty list \code begin() == end() \endcode
385 return iterator( &m_Tail );
388 /// Returns a forward const iterator addressing the first element in a list
389 const_iterator begin() const
391 return get_const_begin();
394 /// Returns a forward const iterator addressing the first element in a list
395 const_iterator cbegin() const
397 return get_const_begin();
400 /// Returns an const iterator that addresses the location succeeding the last element in a list
401 const_iterator end() const
403 return get_const_end();
406 /// Returns an const iterator that addresses the location succeeding the last element in a list
407 const_iterator cend() const
409 return get_const_end();
415 const_iterator get_const_begin() const
417 const_iterator it( const_cast<node_type *>( &m_Head ));
418 ++it ; // skip dummy head
421 const_iterator get_const_end() const
423 return const_iterator( const_cast<node_type *>( &m_Tail ));
428 /// Default constructor initializes empty list
431 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
435 template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
436 explicit LazyList( Stat& st )
439 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
443 /// Destroys the list object
448 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
449 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
454 The function inserts \p val in the list if the list does not contain
455 an item with key equal to \p val.
457 Returns \p true if \p val is linked into the list, \p false otherwise.
459 bool insert( value_type& val )
461 return insert_at( &m_Head, val );
466 This function is intended for derived non-intrusive containers.
468 The function allows to split new item creating into two part:
469 - create item with key only
470 - insert new item into the list
471 - if inserting is success, calls \p f functor to initialize value-field of \p val.
473 The functor signature is:
475 void func( value_type& val );
477 where \p val is the item inserted.
478 While the functor \p f is working the item \p val is locked.
479 The user-defined functor is called only if the inserting is success.
481 template <typename Func>
482 bool insert( value_type& val, Func f )
484 return insert_at( &m_Head, val, f );
489 The operation performs inserting or changing data with lock-free manner.
491 If the item \p val not found in the list, then \p val is inserted into the list
492 iff \p bAllowInsert is \p true.
493 Otherwise, the functor \p func is called with item found.
494 The functor signature is:
497 void operator()( bool bNew, value_type& item, value_type& val );
501 - \p bNew - \p true if the item has been inserted, \p false otherwise
502 - \p item - item of the list
503 - \p val - argument \p val passed into the \p update() function
504 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
505 refer to the same thing.
507 The functor may change non-key fields of the \p item.
508 While the functor \p f is calling the item \p item is locked.
510 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
511 \p second is \p true if new item has been added or \p false if the item with \p key
512 already is in the list.
514 The function makes RCU lock internally.
516 template <typename Func>
517 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
519 return update_at( &m_Head, val, func, bAllowInsert );
522 template <typename Func>
523 CDS_DEPRECATED("ensure() is deprecated, use update()")
524 std::pair<bool, bool> ensure( value_type& val, Func func )
526 return update( val, func, true );
530 /// Unlinks the item \p val from the list
532 The function searches the item \p val in the list and unlink it from the list
533 if it is found and it is equal to \p val.
535 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
536 and deletes the item found. \p %unlink() finds an item by key and deletes it
537 only if \p val is an item of that list, i.e. the pointer to item found
538 is equal to <tt> &val </tt>.
540 The function returns \p true if success and \p false otherwise.
542 RCU \p synchronize method can be called. The RCU should not be locked.
543 Note that depending on RCU type used the \ref disposer call can be deferred.
545 \p disposer specified in \p Traits is called for unlinked item.
547 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
548 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
550 bool unlink( value_type& val )
552 return unlink_at( &m_Head, val );
555 /// Deletes the item from the list
557 The function searches an item with key equal to \p key in the list,
558 unlinks it from the list, and returns \p true.
559 If the item with the key equal to \p key is not found the function return \p false.
561 RCU \p synchronize method can be called. The RCU should not be locked.
562 Note that depending on RCU type used the \ref disposer call can be deferred.
564 \p disposer specified in \p Traits is called for deleted item.
566 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
567 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
569 template <typename Q>
570 bool erase( Q const& key )
572 return erase_at( &m_Head, key, key_comparator());
575 /// Deletes the item from the list using \p pred predicate for searching
577 The function is an analog of \p erase(Q const&)
578 but \p pred is used for key comparing.
579 \p Less functor has the interface like \p std::less.
580 \p pred must imply the same element order as the comparator used for building the list.
582 \p disposer specified in \p Traits is called for deleted item.
584 template <typename Q, typename Less>
585 bool erase_with( Q const& key, Less pred )
588 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
591 /// Deletes the item from the list
593 The function searches an item with key equal to \p key in the list,
594 call \p func functor with item found, unlinks it from the list, and returns \p true.
595 The \p Func interface is
598 void operator()( value_type const& item );
602 If the item with the key equal to \p key is not found the function return \p false.
604 RCU \p synchronize method can be called. The RCU should not be locked.
605 Note that depending on RCU type used the \ref disposer call can be deferred.
607 \p disposer specified in \p Traits is called for deleted item.
609 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
610 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
612 template <typename Q, typename Func>
613 bool erase( Q const& key, Func func )
615 return erase_at( &m_Head, key, key_comparator(), func );
618 /// Deletes the item from the list using \p pred predicate for searching
620 The function is an analog of \p erase(Q const&, Func)
621 but \p pred is used for key comparing.
622 \p Less functor has the interface like \p std::less.
623 \p pred must imply the same element order as the comparator used for building the list.
625 \p disposer specified in \p Traits is called for deleted item.
627 template <typename Q, typename Less, typename Func>
628 bool erase_with( Q const& key, Less pred, Func func )
631 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
634 /// Extracts an item from the list
636 The function searches an item with key equal to \p key in the list,
637 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
638 If the item is not found the function returns empty \p exempt_ptr.
640 @note The function does NOT call RCU read-side lock or synchronization,
641 and does NOT dispose the item found. It just unlinks the item from the list
642 and returns a pointer to it.
643 You should manually lock RCU before calling this function, and you should manually release
644 the returned exempt pointer outside the RCU lock region before reusing returned pointer.
647 #include <cds/urcu/general_buffered.h>
648 #include <cds/intrusive/lazy_list_rcu.h>
650 typedef cds::urcu::gc< general_buffered<> > rcu;
651 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
653 rcu_lazy_list theList;
656 rcu_lazy_list::exempt_ptr p1;
658 // first, we should lock RCU
661 // Now, you can apply extract function
662 // Note that you must not delete the item found inside the RCU lock
663 p1 = theList.extract( 10 )
665 // do something with p1
670 // We may safely release p1 here
671 // release() passes the pointer to RCU reclamation cycle:
672 // it invokes RCU retire_ptr function with the disposer you provided for the list.
676 template <typename Q>
677 exempt_ptr extract( Q const& key )
679 return exempt_ptr( extract_at( &m_Head, key, key_comparator()));
682 /// Extracts an item from the list using \p pred predicate for searching
684 This function is the analog for \p extract(Q const&).
686 The \p pred is a predicate used for key comparing.
687 \p Less has the interface like \p std::less.
688 \p pred must imply the same element order as \ref key_comparator.
690 template <typename Q, typename Less>
691 exempt_ptr extract_with( Q const& key, Less pred )
694 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>()));
697 /// Finds the key \p key
699 The function searches the item with key equal to \p key
700 and calls the functor \p f for item found.
701 The interface of \p Func functor is:
704 void operator()( value_type& item, Q& key );
707 where \p item is the item found, \p key is the <tt>find</tt> function argument.
709 The functor may change non-key fields of \p item.
710 While the functor \p f is calling the item found \p item is locked.
712 The function returns \p true if \p key is found, \p false otherwise.
714 template <typename Q, typename Func>
715 bool find( Q& key, Func f ) const
717 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
720 template <typename Q, typename Func>
721 bool find( Q const& key, Func f ) const
723 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
727 /// Finds the key \p key using \p pred predicate for searching
729 The function is an analog of \p find( Q&, Func ) but \p pred is used for key comparing.
730 \p Less functor has the interface like \p std::less.
731 \p pred must imply the same element order as the comparator used for building the list.
733 template <typename Q, typename Less, typename Func>
734 bool find_with( Q& key, Less pred, Func f ) const
737 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
740 template <typename Q, typename Less, typename Func>
741 bool find_with( Q const& key, Less pred, Func f ) const
744 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
748 /// Checks whether the list contains \p key
750 The function searches the item with key equal to \p key
751 and returns \p true if it is found, and \p false otherwise.
753 template <typename Q>
754 bool contains( Q const& key ) const
756 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
759 template <typename Q>
760 CDS_DEPRECATED("deprecated, use contains()")
761 bool find( Q const& key ) const
763 return contains( key );
767 /// Checks whether the map contains \p key using \p pred predicate for searching
769 The function is an analog of \p contains( Q const& ) but \p pred is used for key comparing.
770 \p Less functor has the interface like \p std::less.
771 \p Less must imply the same element order as the comparator used for building the list.
773 template <typename Q, typename Less>
774 bool contains( Q const& key, Less pred ) const
777 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
780 template <typename Q, typename Less>
781 CDS_DEPRECATED("deprecated, use contains()")
782 bool find_with( Q const& key, Less pred ) const
784 return contains( key, pred );
788 /// Finds the key \p key and return the item found
789 /** \anchor cds_intrusive_LazyList_rcu_get
790 The function searches the item with key equal to \p key and returns the pointer to item found.
791 If \p key is not found it returns \p nullptr.
793 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
795 RCU should be locked before call of this function.
796 Returned item is valid only while RCU is locked:
798 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
803 typename ord_list::rcu_lock lock;
805 foo * pVal = theList.get( 5 );
810 // Unlock RCU by rcu_lock destructor
811 // pVal can be retired by disposer at any time after RCU has been unlocked
815 template <typename Q>
816 value_type * get( Q const& key ) const
818 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
821 /// Finds the key \p key and return the item found
823 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
824 but \p pred is used for comparing the keys.
826 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
828 \p pred must imply the same element order as the comparator used for building the list.
830 template <typename Q, typename Less>
831 value_type * get_with( Q const& key, Less pred ) const
834 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
837 /// Clears the list using default disposer
839 The function clears the list using default (provided in class template) disposer functor.
841 RCU \p synchronize method can be called.
842 Note that depending on RCU type used the \ref disposer call can be deferred.
844 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
845 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
850 deadlock_policy::check();
856 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
857 if ( pHead == &m_Tail )
860 m_Head.m_Lock.lock();
861 pHead->m_Lock.lock();
863 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
864 unlink_node( &m_Head, pHead, &m_Head );
866 pHead->m_Lock.unlock();
867 m_Head.m_Lock.unlock();
871 dispose_node( pHead );
876 /// Checks if the list is empty
879 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
882 /// Returns list's item count
884 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
885 this function always returns 0.
887 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
888 is empty. To check list emptiness use \ref empty() method.
892 return m_ItemCounter.value();
895 /// Returns const reference to internal statistics
896 stat const& statistics() const
903 // split-list support
904 bool insert_aux_node( node_type * pNode )
906 return insert_aux_node( &m_Head, pNode );
909 // split-list support
910 bool insert_aux_node( node_type * pHead, node_type * pNode )
912 assert( pHead != nullptr );
913 assert( pNode != nullptr );
915 // Hack: convert node_type to value_type.
916 // Actually, an auxiliary node should not be converted to value_type
917 // We assume that comparator can correctly distinguish aux and regular node.
918 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
921 bool insert_at( node_type * pHead, value_type& val )
924 return insert_at_locked( pHead, val );
927 template <typename Func>
928 bool insert_at( node_type * pHead, value_type& val, Func f )
935 search( pHead, val, pos );
937 scoped_position_lock sl( pos );
938 if ( validate( pos.pPred, pos.pCur )) {
939 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
940 // failed: key already in list
941 m_Stat.onInsertFailed();
946 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
951 m_Stat.onInsertRetry();
955 m_Stat.onInsertSuccess();
959 iterator insert_at_( node_type * pHead, value_type& val )
962 if ( insert_at_locked( pHead, val ))
963 return iterator( node_traits::to_node_ptr( val ));
968 template <typename Func>
969 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
972 return update_at_locked( pHead, val, func, bAllowInsert );
975 template <typename Func>
976 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
979 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
980 return std::make_pair( ret.first != end(), ret.second );
983 bool unlink_at( node_type * pHead, value_type& val )
987 deadlock_policy::check();
993 search( pHead, val, pos );
995 scoped_position_lock alp( pos );
996 if ( validate( pos.pPred, pos.pCur )) {
997 if ( pos.pCur != &m_Tail
998 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
999 && node_traits::to_value_ptr( pos.pCur ) == &val )
1002 unlink_node( pos.pPred, pos.pCur, pHead );
1012 if ( nResult > 0 ) {
1014 dispose_node( pos.pCur );
1015 m_Stat.onEraseSuccess();
1019 m_Stat.onEraseFailed();
1023 m_Stat.onEraseRetry();
1027 template <typename Q, typename Compare, typename Func>
1028 bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
1030 deadlock_policy::check();
1036 search( pHead, val, pos, cmp );
1038 scoped_position_lock alp( pos );
1039 if ( validate( pos.pPred, pos.pCur )) {
1040 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1042 unlink_node( pos.pPred, pos.pCur, pHead );
1043 f( *node_traits::to_value_ptr( *pos.pCur ));
1053 if ( nResult > 0 ) {
1055 dispose_node( pos.pCur );
1056 m_Stat.onEraseSuccess();
1060 m_Stat.onEraseFailed();
1064 m_Stat.onEraseRetry();
1068 template <typename Q, typename Compare, typename Func>
1069 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1072 return erase_at( pHead, val, cmp, f, pos );
1075 template <typename Q, typename Compare>
1076 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1079 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1082 template <typename Q, typename Compare>
1083 value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1086 assert( gc::is_locked()) ; // RCU must be locked
1089 search( pHead, val, pos, cmp );
1092 scoped_position_lock alp( pos );
1093 if ( validate( pos.pPred, pos.pCur )) {
1094 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1096 unlink_node( pos.pPred, pos.pCur, pHead );
1106 if ( nResult > 0 ) {
1108 m_Stat.onEraseSuccess();
1109 return node_traits::to_value_ptr( pos.pCur );
1112 m_Stat.onEraseFailed();
1116 m_Stat.onEraseRetry();
1120 template <typename Q, typename Compare, typename Func>
1121 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1126 search( pHead, val, pos, cmp );
1127 if ( pos.pCur != &m_Tail ) {
1128 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1129 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1130 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1131 m_Stat.onFindSuccess();
1136 m_Stat.onFindFailed();
1140 template <typename Q, typename Compare>
1141 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1144 return find_at_( pHead, val, cmp ) != end();
1147 template <typename Q, typename Compare>
1148 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1150 assert( gc::is_locked());
1154 search( pHead, val, pos, cmp );
1155 if ( pos.pCur != &m_Tail ) {
1156 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1157 m_Stat.onFindSuccess();
1158 return const_iterator( pos.pCur );
1162 m_Stat.onFindFailed();
1166 template <typename Q, typename Compare>
1167 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1169 value_type * pFound = nullptr;
1170 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1178 template <typename Q>
1179 void search( node_type * const pHead, Q const& key, position& pos ) const
1181 search( pHead, key, pos, key_comparator());
1184 template <typename Q, typename Compare>
1185 void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1187 // RCU should be locked
1188 assert( gc::is_locked());
1190 node_type const* pTail = &m_Tail;
1192 marked_node_ptr pCur(pHead);
1193 marked_node_ptr pPrev(pHead);
1195 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1197 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1199 pPrev = pCur = pHead;
1202 pos.pCur = pCur.ptr();
1203 pos.pPred = pPrev.ptr();
1206 bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1208 if ( validate_link( pPred, pCur ) ) {
1209 m_Stat.onValidationSuccess();
1213 m_Stat.onValidationFailed();
1217 static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1219 // RCU lock should be locked
1220 assert( gc::is_locked());
1222 return !pPred->is_marked()
1223 && !pCur->is_marked()
1224 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1231 bool insert_at_locked( node_type * pHead, value_type& val )
1233 // RCU lock should be locked
1234 assert( gc::is_locked());
1240 search( pHead, val, pos );
1242 scoped_position_lock alp( pos );
1243 if ( validate( pos.pPred, pos.pCur )) {
1244 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1245 // failed: key already in list
1246 m_Stat.onInsertFailed();
1250 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1255 m_Stat.onInsertRetry();
1259 m_Stat.onInsertSuccess();
1264 template <typename Func>
1265 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1267 // RCU lock should be locked
1268 assert( gc::is_locked());
1274 search( pHead, val, pos );
1276 scoped_position_lock alp( pos );
1277 if ( validate( pos.pPred, pos.pCur )) {
1278 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1279 // key already in the list
1281 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1282 m_Stat.onUpdateExisting();
1283 return std::make_pair( iterator( pos.pCur ), false );
1287 if ( !bAllowInsert ) {
1288 m_Stat.onUpdateFailed();
1289 return std::make_pair( end(), false );
1292 func( true, val, val );
1293 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1299 m_Stat.onUpdateRetry();
1303 m_Stat.onUpdateNew();
1304 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1309 }} // namespace cds::intrusive
1311 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H