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.
92 It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
93 argument. Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are:
94 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
95 If the option is not specified, <tt>lazy_list::base_hook<></tt> is used.
96 - opt::compare - key comparison functor. No default functor is provided.
97 If the option is not specified, the opt::less is used.
98 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
99 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
100 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer
101 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
102 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
103 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
104 or opt::v::sequential_consistent (sequentially consisnent memory model).
107 Before including <tt><cds/intrusive/lazy_list_rcu.h></tt> you should include appropriate RCU header file,
108 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
109 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
111 #include <cds/urcu/general_buffered.h>
112 #include <cds/intrusive/lazy_list_rcu.h>
114 // Now, you can declare lazy list for type Foo and default traits:
115 typedef cds::intrusive::LazyList<cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_lazy_list;
122 #ifdef CDS_DOXYGEN_INVOKED
123 ,class Traits = lazy_list::traits
128 class LazyList<cds::urcu::gc<RCU>, T, Traits>
131 typedef cds::urcu::gc<RCU> gc; ///< RCU schema
132 typedef T value_type; ///< type of value stored in the list
133 typedef Traits traits; ///< Traits template parameter
135 typedef typename traits::hook hook; ///< hook type
136 typedef typename hook::node_type node_type; ///< node type
138 # ifdef CDS_DOXYGEN_INVOKED
139 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
141 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
144 typedef typename traits::disposer disposer; ///< disposer used
145 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
146 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
148 typedef typename traits::back_off back_off; ///< back-off strategy (not used)
149 typedef typename traits::item_counter item_counter; ///< Item counting policy used
150 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
151 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
153 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
154 static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
157 // Rebind traits (split-list support)
158 template <typename... Options>
159 struct rebind_traits {
163 , typename cds::opt::make_options< traits, Options...>::type
169 typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
170 typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
173 node_type m_Head; ///< List head (dummy node)
174 node_type m_Tail; ///< List tail (dummy node)
175 item_counter m_ItemCounter; ///< Item counter
179 /// Position pointer for item search
181 node_type * pPred; ///< Previous node
182 node_type * pCur; ///< Current node
184 /// Locks nodes \p pPred and \p pCur
187 pPred->m_Lock.lock();
191 /// Unlocks nodes \p pPred and \p pCur
194 pCur->m_Lock.unlock();
195 pPred->m_Lock.unlock();
199 typedef std::unique_lock< position > scoped_position_lock;
201 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> deadlock_policy;
206 static void clear_links( node_type * pNode )
208 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
211 struct clear_and_dispose {
212 void operator()( value_type * p )
214 assert( p != nullptr );
215 clear_links( node_traits::to_node_ptr(p));
220 static void dispose_node( node_type * pNode )
223 assert( !gc::is_locked());
225 gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ));
228 static void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
230 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
231 link_checker::is_empty( pNode );
233 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed );
234 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
237 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
239 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
240 assert( pCur != &m_Tail );
242 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
243 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
244 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
250 /// pointer to extracted node
251 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
252 /// Type of \p get() member function return value
253 typedef value_type * raw_ptr;
257 template <bool IsConst>
260 friend class LazyList;
263 value_type * m_pNode;
267 assert( m_pNode != nullptr );
269 node_type * pNode = node_traits::to_node_ptr( m_pNode );
270 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
271 if ( pNext != nullptr )
272 m_pNode = node_traits::to_value_ptr( pNext );
277 if ( m_pNode != nullptr ) {
278 node_type * pNode = node_traits::to_node_ptr( m_pNode );
280 // Dummy tail node could not be marked
281 while ( pNode->is_marked())
282 pNode = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
284 if ( pNode != node_traits::to_node_ptr( m_pNode ))
285 m_pNode = node_traits::to_value_ptr( pNode );
289 iterator_type( node_type * pNode )
291 m_pNode = node_traits::to_value_ptr( pNode );
296 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
297 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
303 iterator_type( iterator_type const& src )
304 : m_pNode( src.m_pNode )
307 value_ptr operator ->() const
312 value_ref operator *() const
314 assert( m_pNode != nullptr );
319 iterator_type& operator ++()
327 iterator_type operator ++(int)
329 iterator_type i(*this);
335 iterator_type& operator = (iterator_type const& src)
337 m_pNode = src.m_pNode;
342 bool operator ==(iterator_type<C> const& i ) const
344 return m_pNode == i.m_pNode;
347 bool operator !=(iterator_type<C> const& i ) const
349 return m_pNode != i.m_pNode;
355 ///@name Forward iterators (thread-safe only under RCU lock)
359 You may safely use iterators in multi-threaded environment only under RCU lock.
360 Otherwise, a crash is possible if another thread deletes the item the iterator points to.
362 typedef iterator_type<false> iterator;
364 /// Const forward iterator
365 typedef iterator_type<true> const_iterator;
367 /// Returns a forward iterator addressing the first element in a list
369 For empty list \code begin() == end() \endcode
373 iterator it( &m_Head );
374 ++it ; // skip dummy head
378 /// Returns an iterator that addresses the location succeeding the last element in a list
380 Do not use the value returned by <tt>end</tt> function to access any item.
382 The returned value can be used only to control reaching the end of the list.
383 For empty list \code begin() == end() \endcode
387 return iterator( &m_Tail );
390 /// Returns a forward const iterator addressing the first element in a list
391 const_iterator begin() const
393 return get_const_begin();
396 /// Returns a forward const iterator addressing the first element in a list
397 const_iterator cbegin() const
399 return get_const_begin();
402 /// Returns an const iterator that addresses the location succeeding the last element in a list
403 const_iterator end() const
405 return get_const_end();
408 /// Returns an const iterator that addresses the location succeeding the last element in a list
409 const_iterator cend() const
411 return get_const_end();
417 const_iterator get_const_begin() const
419 const_iterator it( const_cast<node_type *>( &m_Head ));
420 ++it ; // skip dummy head
423 const_iterator get_const_end() const
425 return const_iterator( const_cast<node_type *>( &m_Tail ));
430 /// Default constructor initializes empty list
433 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
434 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
437 /// Destroys the list object
442 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
443 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
448 The function inserts \p val in the list if the list does not contain
449 an item with key equal to \p val.
451 Returns \p true if \p val is linked into the list, \p false otherwise.
453 bool insert( value_type& val )
455 return insert_at( &m_Head, val );
460 This function is intended for derived non-intrusive containers.
462 The function allows to split new item creating into two part:
463 - create item with key only
464 - insert new item into the list
465 - if inserting is success, calls \p f functor to initialize value-field of \p val.
467 The functor signature is:
469 void func( value_type& val );
471 where \p val is the item inserted.
472 While the functor \p f is working the item \p val is locked.
473 The user-defined functor is called only if the inserting is success.
475 template <typename Func>
476 bool insert( value_type& val, Func f )
478 return insert_at( &m_Head, val, f );
483 The operation performs inserting or changing data with lock-free manner.
485 If the item \p val not found in the list, then \p val is inserted into the list
486 iff \p bAllowInsert is \p true.
487 Otherwise, the functor \p func is called with item found.
488 The functor signature is:
491 void operator()( bool bNew, value_type& item, value_type& val );
495 - \p bNew - \p true if the item has been inserted, \p false otherwise
496 - \p item - item of the list
497 - \p val - argument \p val passed into the \p update() function
498 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
499 refer to the same thing.
501 The functor may change non-key fields of the \p item.
502 While the functor \p f is calling the item \p item is locked.
504 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
505 \p second is \p true if new item has been added or \p false if the item with \p key
506 already is in the list.
508 The function makes RCU lock internally.
510 template <typename Func>
511 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
513 return update_at( &m_Head, val, func, bAllowInsert );
516 template <typename Func>
517 CDS_DEPRECATED("ensure() is deprecated, use update()")
518 std::pair<bool, bool> ensure( value_type& val, Func func )
520 return update( val, func, true );
524 /// Unlinks the item \p val from the list
526 The function searches the item \p val in the list and unlink it from the list
527 if it is found and it is equal to \p val.
529 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
530 and deletes the item found. \p %unlink() finds an item by key and deletes it
531 only if \p val is an item of that list, i.e. the pointer to item found
532 is equal to <tt> &val </tt>.
534 The function returns \p true if success and \p false otherwise.
536 RCU \p synchronize method can be called. The RCU should not be locked.
537 Note that depending on RCU type used the \ref disposer call can be deferred.
539 \p disposer specified in \p Traits is called for unlinked item.
541 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
542 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
544 bool unlink( value_type& val )
546 return unlink_at( &m_Head, val );
549 /// Deletes the item from the list
551 The function searches an item with key equal to \p key in the list,
552 unlinks it from the list, and returns \p true.
553 If the item with the key equal to \p key is not found the function return \p false.
555 RCU \p synchronize method can be called. The RCU should not be locked.
556 Note that depending on RCU type used the \ref disposer call can be deferred.
558 \p disposer specified in \p Traits is called for deleted item.
560 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
561 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
563 template <typename Q>
564 bool erase( Q const& key )
566 return erase_at( &m_Head, key, key_comparator());
569 /// Deletes the item from the list using \p pred predicate for searching
571 The function is an analog of \p erase(Q const&)
572 but \p pred is used for key comparing.
573 \p Less functor has the interface like \p std::less.
574 \p pred must imply the same element order as the comparator used for building the list.
576 \p disposer specified in \p Traits is called for deleted item.
578 template <typename Q, typename Less>
579 bool erase_with( Q const& key, Less pred )
582 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
585 /// Deletes the item from the list
587 The function searches an item with key equal to \p key in the list,
588 call \p func functor with item found, unlinks it from the list, and returns \p true.
589 The \p Func interface is
592 void operator()( value_type const& item );
596 If the item with the key equal to \p key is not found the function return \p false.
598 RCU \p synchronize method can be called. The RCU should not be locked.
599 Note that depending on RCU type used the \ref disposer call can be deferred.
601 \p disposer specified in \p Traits is called for deleted item.
603 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
604 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
606 template <typename Q, typename Func>
607 bool erase( Q const& key, Func func )
609 return erase_at( &m_Head, key, key_comparator(), func );
612 /// Deletes the item from the list using \p pred predicate for searching
614 The function is an analog of \p erase(Q const&, Func)
615 but \p pred is used for key comparing.
616 \p Less functor has the interface like \p std::less.
617 \p pred must imply the same element order as the comparator used for building the list.
619 \p disposer specified in \p Traits is called for deleted item.
621 template <typename Q, typename Less, typename Func>
622 bool erase_with( Q const& key, Less pred, Func func )
625 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
628 /// Extracts an item from the list
630 The function searches an item with key equal to \p key in the list,
631 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
632 If the item is not found the function returns empty \p exempt_ptr.
634 @note The function does NOT call RCU read-side lock or synchronization,
635 and does NOT dispose the item found. It just unlinks the item from the list
636 and returns a pointer to it.
637 You should manually lock RCU before calling this function, and you should manually release
638 the returned exempt pointer outside the RCU lock region before reusing returned pointer.
641 #include <cds/urcu/general_buffered.h>
642 #include <cds/intrusive/lazy_list_rcu.h>
644 typedef cds::urcu::gc< general_buffered<> > rcu;
645 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
647 rcu_lazy_list theList;
650 rcu_lazy_list::exempt_ptr p1;
652 // first, we should lock RCU
655 // Now, you can apply extract function
656 // Note that you must not delete the item found inside the RCU lock
657 p1 = theList.extract( 10 )
659 // do something with p1
664 // We may safely release p1 here
665 // release() passes the pointer to RCU reclamation cycle:
666 // it invokes RCU retire_ptr function with the disposer you provided for the list.
670 template <typename Q>
671 exempt_ptr extract( Q const& key )
673 return exempt_ptr( extract_at( &m_Head, key, key_comparator()));
676 /// Extracts an item from the list using \p pred predicate for searching
678 This function is the analog for \p extract(Q const&).
680 The \p pred is a predicate used for key comparing.
681 \p Less has the interface like \p std::less.
682 \p pred must imply the same element order as \ref key_comparator.
684 template <typename Q, typename Less>
685 exempt_ptr extract_with( Q const& key, Less pred )
688 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>()));
691 /// Finds the key \p key
693 The function searches the item with key equal to \p key
694 and calls the functor \p f for item found.
695 The interface of \p Func functor is:
698 void operator()( value_type& item, Q& key );
701 where \p item is the item found, \p key is the <tt>find</tt> function argument.
703 The functor may change non-key fields of \p item.
704 While the functor \p f is calling the item found \p item is locked.
706 The function returns \p true if \p key is found, \p false otherwise.
708 template <typename Q, typename Func>
709 bool find( Q& key, Func f ) const
711 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
714 template <typename Q, typename Func>
715 bool find( Q const& key, Func f ) const
717 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
721 /// Finds the key \p key using \p pred predicate for searching
723 The function is an analog of \p find( Q&, Func ) but \p pred is used for key comparing.
724 \p Less functor has the interface like \p std::less.
725 \p pred must imply the same element order as the comparator used for building the list.
727 template <typename Q, typename Less, typename Func>
728 bool find_with( Q& key, Less pred, Func f ) const
731 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
734 template <typename Q, typename Less, typename Func>
735 bool find_with( Q const& key, Less pred, Func f ) const
738 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
742 /// Checks whether the list contains \p key
744 The function searches the item with key equal to \p key
745 and returns \p true if it is found, and \p false otherwise.
747 template <typename Q>
748 bool contains( Q const& key ) const
750 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
753 template <typename Q>
754 CDS_DEPRECATED("deprecated, use contains()")
755 bool find( Q const& key ) const
757 return contains( key );
761 /// Checks whether the map contains \p key using \p pred predicate for searching
763 The function is an analog of \p contains( Q const& ) but \p pred is used for key comparing.
764 \p Less functor has the interface like \p std::less.
765 \p Less must imply the same element order as the comparator used for building the list.
767 template <typename Q, typename Less>
768 bool contains( Q const& key, Less pred ) const
771 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
774 template <typename Q, typename Less>
775 CDS_DEPRECATED("deprecated, use contains()")
776 bool find_with( Q const& key, Less pred ) const
778 return contains( key, pred );
782 /// Finds the key \p key and return the item found
783 /** \anchor cds_intrusive_LazyList_rcu_get
784 The function searches the item with key equal to \p key and returns the pointer to item found.
785 If \p key is not found it returns \p nullptr.
787 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
789 RCU should be locked before call of this function.
790 Returned item is valid only while RCU is locked:
792 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
797 typename ord_list::rcu_lock lock;
799 foo * pVal = theList.get( 5 );
804 // Unlock RCU by rcu_lock destructor
805 // pVal can be retired by disposer at any time after RCU has been unlocked
809 template <typename Q>
810 value_type * get( Q const& key ) const
812 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
815 /// Finds the key \p key and return the item found
817 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
818 but \p pred is used for comparing the keys.
820 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
822 \p pred must imply the same element order as the comparator used for building the list.
824 template <typename Q, typename Less>
825 value_type * get_with( Q const& key, Less pred ) const
828 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
831 /// Clears the list using default disposer
833 The function clears the list using default (provided in class template) disposer functor.
835 RCU \p synchronize method can be called.
836 Note that depending on RCU type used the \ref disposer call can be deferred.
838 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
839 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
844 deadlock_policy::check();
850 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
851 if ( pHead == &m_Tail )
854 m_Head.m_Lock.lock();
855 pHead->m_Lock.lock();
857 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
858 unlink_node( &m_Head, pHead, &m_Head );
860 pHead->m_Lock.unlock();
861 m_Head.m_Lock.unlock();
865 dispose_node( pHead );
870 /// Checks if the list is empty
873 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
876 /// Returns list's item count
878 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
879 this function always returns 0.
881 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
882 is empty. To check list emptyness use \ref empty() method.
886 return m_ItemCounter.value();
891 // split-list support
892 bool insert_aux_node( node_type * pNode )
894 return insert_aux_node( &m_Head, pNode );
897 // split-list support
898 bool insert_aux_node( node_type * pHead, node_type * pNode )
900 assert( pHead != nullptr );
901 assert( pNode != nullptr );
903 // Hack: convert node_type to value_type.
904 // Actually, an auxiliary node should not be converted to value_type
905 // We assume that comparator can correctly distinguish aux and regular node.
906 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
909 bool insert_at( node_type * pHead, value_type& val )
912 return insert_at_locked( pHead, val );
915 template <typename Func>
916 bool insert_at( node_type * pHead, value_type& val, Func f )
923 search( pHead, val, pos );
925 scoped_position_lock sl( pos );
926 if ( validate( pos.pPred, pos.pCur )) {
927 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
928 // failed: key already in list
933 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
941 iterator insert_at_( node_type * pHead, value_type& val )
944 if ( insert_at_locked( pHead, val ))
945 return iterator( node_traits::to_node_ptr( val ));
950 template <typename Func>
951 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
954 return update_at_locked( pHead, val, func, bAllowInsert );
957 template <typename Func>
958 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
961 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
962 return std::make_pair( ret.first != end(), ret.second );
965 bool unlink_at( node_type * pHead, value_type& val )
969 deadlock_policy::check();
975 search( pHead, val, pos );
977 scoped_position_lock alp( pos );
978 if ( validate( pos.pPred, pos.pCur )) {
979 if ( pos.pCur != &m_Tail
980 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
981 && node_traits::to_value_ptr( pos.pCur ) == &val )
984 unlink_node( pos.pPred, pos.pCur, pHead );
996 dispose_node( pos.pCur );
1004 template <typename Q, typename Compare, typename Func>
1005 bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
1007 deadlock_policy::check();
1013 search( pHead, val, pos, cmp );
1015 scoped_position_lock alp( pos );
1016 if ( validate( pos.pPred, pos.pCur )) {
1017 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1019 unlink_node( pos.pPred, pos.pCur, pHead );
1020 f( *node_traits::to_value_ptr( *pos.pCur ));
1031 if ( nResult > 0 ) {
1032 dispose_node( pos.pCur );
1040 template <typename Q, typename Compare, typename Func>
1041 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1044 return erase_at( pHead, val, cmp, f, pos );
1047 template <typename Q, typename Compare>
1048 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1051 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1054 template <typename Q, typename Compare>
1055 value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1058 assert( gc::is_locked()) ; // RCU must be locked
1061 search( pHead, val, pos, cmp );
1064 scoped_position_lock alp( pos );
1065 if ( validate( pos.pPred, pos.pCur )) {
1066 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1068 unlink_node( pos.pPred, pos.pCur, pHead );
1080 return node_traits::to_value_ptr( pos.pCur );
1086 template <typename Q, typename Compare, typename Func>
1087 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1092 search( pHead, val, pos, cmp );
1093 if ( pos.pCur != &m_Tail ) {
1094 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1095 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1097 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1104 template <typename Q, typename Compare>
1105 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1108 return find_at_( pHead, val, cmp ) != end();
1111 template <typename Q, typename Compare>
1112 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1114 assert( gc::is_locked());
1118 search( pHead, val, pos, cmp );
1119 if ( pos.pCur != &m_Tail ) {
1120 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1121 return const_iterator( pos.pCur );
1126 template <typename Q, typename Compare>
1127 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1129 value_type * pFound = nullptr;
1130 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1138 template <typename Q>
1139 void search( node_type * const pHead, Q const& key, position& pos ) const
1141 search( pHead, key, pos, key_comparator());
1144 template <typename Q, typename Compare>
1145 void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1147 // RCU should be locked
1148 assert( gc::is_locked());
1150 node_type const* pTail = &m_Tail;
1152 marked_node_ptr pCur(pHead);
1153 marked_node_ptr pPrev(pHead);
1155 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1157 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1159 pPrev = pCur = pHead;
1162 pos.pCur = pCur.ptr();
1163 pos.pPred = pPrev.ptr();
1166 static bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1168 // RCU lock should be locked
1169 assert( gc::is_locked());
1171 return !pPred->is_marked()
1172 && !pCur->is_marked()
1173 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1180 bool insert_at_locked( node_type * pHead, value_type& val )
1182 // RCU lock should be locked
1183 assert( gc::is_locked());
1189 search( pHead, val, pos );
1191 scoped_position_lock alp( pos );
1192 if ( validate( pos.pPred, pos.pCur )) {
1193 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1194 // failed: key already in list
1198 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1206 template <typename Func>
1207 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1209 // RCU lock should be locked
1210 assert( gc::is_locked());
1216 search( pHead, val, pos );
1218 scoped_position_lock alp( pos );
1219 if ( validate( pos.pPred, pos.pCur )) {
1220 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1221 // key already in the list
1223 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1224 return std::make_pair( iterator( pos.pCur ), false );
1228 if ( !bAllowInsert )
1229 return std::make_pair( end(), false );
1231 func( true, val, val );
1232 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1234 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1243 }} // namespace cds::intrusive
1245 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H