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 );
232 pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed );
233 pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
236 void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
238 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
239 assert( pCur != &m_Tail );
241 node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
242 pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
243 pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
249 /// pointer to extracted node
250 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >;
251 /// Type of \p get() member function return value
252 typedef value_type * raw_ptr;
256 template <bool IsConst>
259 friend class LazyList;
262 value_type * m_pNode;
266 assert( m_pNode != nullptr );
268 node_type * pNode = node_traits::to_node_ptr( m_pNode );
269 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
270 if ( pNext != nullptr )
271 m_pNode = node_traits::to_value_ptr( pNext );
276 if ( m_pNode != nullptr ) {
277 node_type * pNode = node_traits::to_node_ptr( m_pNode );
279 // Dummy tail node could not be marked
280 while ( pNode->is_marked())
281 pNode = pNode->m_pNext.load(memory_model::memory_order_acquire).ptr();
283 if ( pNode != node_traits::to_node_ptr( m_pNode ))
284 m_pNode = node_traits::to_value_ptr( pNode );
288 iterator_type( node_type * pNode )
290 m_pNode = node_traits::to_value_ptr( pNode );
295 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
296 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
302 iterator_type( iterator_type const& src )
303 : m_pNode( src.m_pNode )
306 value_ptr operator ->() const
311 value_ref operator *() const
313 assert( m_pNode != nullptr );
318 iterator_type& operator ++()
326 iterator_type operator ++(int)
328 iterator_type i(*this);
334 iterator_type& operator = (iterator_type const& src)
336 m_pNode = src.m_pNode;
341 bool operator ==(iterator_type<C> const& i ) const
343 return m_pNode == i.m_pNode;
346 bool operator !=(iterator_type<C> const& i ) const
348 return m_pNode != i.m_pNode;
355 typedef iterator_type<false> iterator;
356 /// Const forward iterator
357 typedef iterator_type<true> const_iterator;
359 /// Returns a forward iterator addressing the first element in a list
361 For empty list \code begin() == end() \endcode
365 iterator it( &m_Head );
366 ++it ; // skip dummy head
370 /// Returns an iterator that addresses the location succeeding the last element in a list
372 Do not use the value returned by <tt>end</tt> function to access any item.
374 The returned value can be used only to control reaching the end of the list.
375 For empty list \code begin() == end() \endcode
379 return iterator( &m_Tail );
382 /// Returns a forward const iterator addressing the first element in a list
384 const_iterator begin() const
386 return get_const_begin();
388 const_iterator cbegin() const
390 return get_const_begin();
394 /// Returns an const iterator that addresses the location succeeding the last element in a list
396 const_iterator end() const
398 return get_const_end();
400 const_iterator cend() const
402 return get_const_end();
408 const_iterator get_const_begin() const
410 const_iterator it( const_cast<node_type *>( &m_Head ));
411 ++it ; // skip dummy head
414 const_iterator get_const_end() const
416 return const_iterator( const_cast<node_type *>( &m_Tail ));
421 /// Default constructor initializes empty list
424 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
425 m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
428 /// Destroys the list object
433 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail );
434 m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
439 The function inserts \p val in the list if the list does not contain
440 an item with key equal to \p val.
442 Returns \p true if \p val is linked into the list, \p false otherwise.
444 bool insert( value_type& val )
446 return insert_at( &m_Head, val );
451 This function is intended for derived non-intrusive containers.
453 The function allows to split new item creating into two part:
454 - create item with key only
455 - insert new item into the list
456 - if inserting is success, calls \p f functor to initialize value-field of \p val.
458 The functor signature is:
460 void func( value_type& val );
462 where \p val is the item inserted.
463 While the functor \p f is working the item \p val is locked.
464 The user-defined functor is called only if the inserting is success.
466 template <typename Func>
467 bool insert( value_type& val, Func f )
469 return insert_at( &m_Head, val, f );
474 The operation performs inserting or changing data with lock-free manner.
476 If the item \p val not found in the list, then \p val is inserted into the list
477 iff \p bAllowInsert is \p true.
478 Otherwise, the functor \p func is called with item found.
479 The functor signature is:
482 void operator()( bool bNew, value_type& item, value_type& val );
486 - \p bNew - \p true if the item has been inserted, \p false otherwise
487 - \p item - item of the list
488 - \p val - argument \p val passed into the \p update() function
489 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
490 refer to the same thing.
492 The functor may change non-key fields of the \p item.
493 While the functor \p f is calling the item \p item is locked.
495 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
496 \p second is \p true if new item has been added or \p false if the item with \p key
497 already is in the list.
499 The function makes RCU lock internally.
501 template <typename Func>
502 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
504 return update_at( &m_Head, val, func, bAllowInsert );
507 template <typename Func>
508 CDS_DEPRECATED("ensure() is deprecated, use update()")
509 std::pair<bool, bool> ensure( value_type& val, Func func )
511 return update( val, func, true );
515 /// Unlinks the item \p val from the list
517 The function searches the item \p val in the list and unlink it from the list
518 if it is found and it is equal to \p val.
520 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
521 and deletes the item found. \p %unlink() finds an item by key and deletes it
522 only if \p val is an item of that list, i.e. the pointer to item found
523 is equal to <tt> &val </tt>.
525 The function returns \p true if success and \p false otherwise.
527 RCU \p synchronize method can be called. The RCU should not be locked.
528 Note that depending on RCU type used the \ref disposer call can be deferred.
530 \p disposer specified in \p Traits is called for unlinked item.
532 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
533 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
535 bool unlink( value_type& val )
537 return unlink_at( &m_Head, val );
540 /// Deletes the item from the list
541 /** \anchor cds_intrusive_LazyList_rcu_find_erase
542 The function searches an item with key equal to \p key in the list,
543 unlinks it from the list, and returns \p true.
544 If the item with the key equal to \p key is not found the function return \p false.
546 RCU \p synchronize method can be called. The RCU should not be locked.
547 Note that depending on RCU type used the \ref disposer call can be deferred.
549 \p disposer specified in \p Traits is called for deleted item.
551 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
552 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
554 template <typename Q>
555 bool erase( Q const& key )
557 return erase_at( &m_Head, key, key_comparator());
560 /// Deletes the item from the list using \p pred predicate for searching
562 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
563 but \p pred is used for key comparing.
564 \p Less functor has the interface like \p std::less.
565 \p pred must imply the same element order as the comparator used for building the list.
567 \p disposer specified in \p Traits is called for deleted item.
569 template <typename Q, typename Less>
570 bool erase_with( Q const& key, Less pred )
573 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
576 /// Deletes the item from the list
577 /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
578 The function searches an item with key equal to \p key in the list,
579 call \p func functor with item found, unlinks it from the list, and returns \p true.
580 The \p Func interface is
583 void operator()( value_type const& item );
587 If the item with the key equal to \p key is not found the function return \p false.
589 RCU \p synchronize method can be called. The RCU should not be locked.
590 Note that depending on RCU type used the \ref disposer call can be deferred.
592 \p disposer specified in \p Traits is called for deleted item.
594 The function can throw \ref cds_urcu_rcu_deadlock "cds::urcu::rcu_deadlock" exception if deadlock is encountered and
595 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
597 template <typename Q, typename Func>
598 bool erase( Q const& key, Func func )
600 return erase_at( &m_Head, key, key_comparator(), func );
603 /// Deletes the item from the list using \p pred predicate for searching
605 The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
606 but \p pred is used for key comparing.
607 \p Less functor has the interface like \p std::less.
608 \p pred must imply the same element order as the comparator used for building the list.
610 \p disposer specified in \p Traits is called for deleted item.
612 template <typename Q, typename Less, typename Func>
613 bool erase_with( Q const& key, Less pred, Func func )
616 return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
619 /// Extracts an item from the list
621 \anchor cds_intrusive_LazyList_rcu_extract
622 The function searches an item with key equal to \p key in the list,
623 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
624 If the item is not found the function returns empty \p exempt_ptr.
626 @note The function does NOT call RCU read-side lock or synchronization,
627 and does NOT dispose the item found. It just unlinks the item from the list
628 and returns a pointer to it.
629 You should manually lock RCU before calling this function, and you should manually synchronize RCU
630 outside the RCU lock region before reusing returned pointer.
633 #include <cds/urcu/general_buffered.h>
634 #include <cds/intrusive/lazy_list_rcu.h>
636 typedef cds::urcu::gc< general_buffered<> > rcu;
637 typedef cds::intrusive::LazyList< rcu, Foo > rcu_lazy_list;
639 rcu_lazy_list theList;
642 rcu_lazy_list::exempt_ptr p1;
644 // first, we should lock RCU
647 // Now, you can apply extract function
648 // Note that you must not delete the item found inside the RCU lock
649 p1 = theList.extract( 10 )
651 // do something with p1
656 // We may safely release p1 here
657 // release() passes the pointer to RCU reclamation cycle:
658 // it invokes RCU retire_ptr function with the disposer you provided for the list.
662 template <typename Q>
663 exempt_ptr extract( Q const& key )
665 return exempt_ptr( extract_at( &m_Head, key, key_comparator()));
668 /// Extracts an item from the list using \p pred predicate for searching
670 This function is the analog for \p extract(Q const&).
672 The \p pred is a predicate used for key comparing.
673 \p Less has the interface like \p std::less.
674 \p pred must imply the same element order as \ref key_comparator.
676 template <typename Q, typename Less>
677 exempt_ptr extract_with( Q const& key, Less pred )
680 return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>()));
683 /// Finds the key \p key
684 /** \anchor cds_intrusive_LazyList_rcu_find_func
685 The function searches the item with key equal to \p key
686 and calls the functor \p f for item found.
687 The interface of \p Func functor is:
690 void operator()( value_type& item, Q& key );
693 where \p item is the item found, \p key is the <tt>find</tt> function argument.
695 The functor may change non-key fields of \p item.
696 While the functor \p f is calling the item found \p item is locked.
698 The function returns \p true if \p key is found, \p false otherwise.
700 template <typename Q, typename Func>
701 bool find( Q& key, Func f ) const
703 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator(), f );
706 template <typename Q, typename Func>
707 bool find( Q const& key, Func f ) const
709 return find_at( const_cast<node_type *>(&m_Head), key, key_comparator(), f );
713 /// Finds the key \p key using \p pred predicate for searching
715 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
716 \p Less functor has the interface like \p std::less.
717 \p pred must imply the same element order as the comparator used for building the list.
719 template <typename Q, typename Less, typename Func>
720 bool find_with( Q& key, Less pred, Func f ) const
723 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>(), f );
726 template <typename Q, typename Less, typename Func>
727 bool find_with( Q const& key, Less pred, Func f ) const
730 return find_at( const_cast<node_type *>(&m_Head), key, cds::opt::details::make_comparator_from_less<Less>(), f );
734 /// Checks whether the list contains \p key
736 The function searches the item with key equal to \p key
737 and returns \p true if it is found, and \p false otherwise.
739 template <typename Q>
740 bool contains( Q const& key ) const
742 return find_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
745 template <typename Q>
746 CDS_DEPRECATED("deprecated, use contains()")
747 bool find( Q const& key ) const
749 return contains( key );
753 /// Checks whether the map contains \p key using \p pred predicate for searching
755 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
756 \p Less functor has the interface like \p std::less.
757 \p Less must imply the same element order as the comparator used for building the list.
759 template <typename Q, typename Less>
760 bool contains( Q const& key, Less pred ) const
763 return find_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
766 template <typename Q, typename Less>
767 CDS_DEPRECATED("deprecated, use contains()")
768 bool find_with( Q const& key, Less pred ) const
770 return contains( key, pred );
774 /// Finds the key \p key and return the item found
775 /** \anchor cds_intrusive_LazyList_rcu_get
776 The function searches the item with key equal to \p key and returns the pointer to item found.
777 If \p key is not found it returns \p nullptr.
779 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
781 RCU should be locked before call of this function.
782 Returned item is valid only while RCU is locked:
784 typedef cds::intrusive::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
789 typename ord_list::rcu_lock lock;
791 foo * pVal = theList.get( 5 );
796 // Unlock RCU by rcu_lock destructor
797 // pVal can be retired by disposer at any time after RCU has been unlocked
801 template <typename Q>
802 value_type * get( Q const& key ) const
804 return get_at( const_cast<node_type *>( &m_Head ), key, key_comparator());
807 /// Finds the key \p key and return the item found
809 The function is an analog of \ref cds_intrusive_LazyList_rcu_get "get(Q const&)"
810 but \p pred is used for comparing the keys.
812 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
814 \p pred must imply the same element order as the comparator used for building the list.
816 template <typename Q, typename Less>
817 value_type * get_with( Q const& key, Less pred ) const
820 return get_at( const_cast<node_type *>( &m_Head ), key, cds::opt::details::make_comparator_from_less<Less>());
823 /// Clears the list using default disposer
825 The function clears the list using default (provided in class template) disposer functor.
827 RCU \p synchronize method can be called.
828 Note that depending on RCU type used the \ref disposer call can be deferred.
830 The function can throw \p cds::urcu::rcu_deadlock exception if deadlock is encountered and
831 deadlock checking policy is \p opt::v::rcu_throw_deadlock.
836 deadlock_policy::check();
842 pHead = m_Head.m_pNext.load(memory_model::memory_order_acquire).ptr();
843 if ( pHead == &m_Tail )
846 m_Head.m_Lock.lock();
847 pHead->m_Lock.lock();
849 if ( m_Head.m_pNext.load(memory_model::memory_order_relaxed).all() == pHead )
850 unlink_node( &m_Head, pHead, &m_Head );
852 pHead->m_Lock.unlock();
853 m_Head.m_Lock.unlock();
857 dispose_node( pHead );
862 /// Checks if the list is empty
865 return m_Head.m_pNext.load(memory_model::memory_order_relaxed).ptr() == &m_Tail;
868 /// Returns list's item count
870 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
871 this function always returns 0.
873 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
874 is empty. To check list emptyness use \ref empty() method.
878 return m_ItemCounter.value();
883 // split-list support
884 bool insert_aux_node( node_type * pNode )
886 return insert_aux_node( &m_Head, pNode );
889 // split-list support
890 bool insert_aux_node( node_type * pHead, node_type * pNode )
892 assert( pHead != nullptr );
893 assert( pNode != nullptr );
895 // Hack: convert node_type to value_type.
896 // Actually, an auxiliary node should not be converted to value_type
897 // We assume that comparator can correctly distinguish aux and regular node.
898 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
901 bool insert_at( node_type * pHead, value_type& val )
904 return insert_at_locked( pHead, val );
907 template <typename Func>
908 bool insert_at( node_type * pHead, value_type& val, Func f )
910 link_checker::is_empty( node_traits::to_node_ptr( val ));
916 search( pHead, val, pos );
918 scoped_position_lock sl( pos );
919 if ( validate( pos.pPred, pos.pCur )) {
920 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
921 // failed: key already in list
926 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
934 iterator insert_at_( node_type * pHead, value_type& val )
937 if ( insert_at_locked( pHead, val ))
938 return iterator( node_traits::to_node_ptr( val ));
943 template <typename Func>
944 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
947 return update_at_locked( pHead, val, func, bAllowInsert );
950 template <typename Func>
951 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
954 std::pair<iterator, bool> ret = update_at_locked( pHead, val, func, bAllowInsert );
955 return std::make_pair( ret.first != end(), ret.second );
958 bool unlink_at( node_type * pHead, value_type& val )
962 deadlock_policy::check();
968 search( pHead, val, pos );
970 scoped_position_lock alp( pos );
971 if ( validate( pos.pPred, pos.pCur )) {
972 if ( pos.pCur != &m_Tail
973 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
974 && node_traits::to_value_ptr( pos.pCur ) == &val )
977 unlink_node( pos.pPred, pos.pCur, pHead );
989 dispose_node( pos.pCur );
997 template <typename Q, typename Compare, typename Func>
998 bool erase_at( node_type * const pHead, Q const& val, Compare cmp, Func f, position& pos )
1000 deadlock_policy::check();
1006 search( pHead, val, pos, cmp );
1008 scoped_position_lock alp( pos );
1009 if ( validate( pos.pPred, pos.pCur )) {
1010 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1012 unlink_node( pos.pPred, pos.pCur, pHead );
1013 f( *node_traits::to_value_ptr( *pos.pCur ));
1024 if ( nResult > 0 ) {
1025 dispose_node( pos.pCur );
1033 template <typename Q, typename Compare, typename Func>
1034 bool erase_at( node_type * pHead, Q const& val, Compare cmp, Func f )
1037 return erase_at( pHead, val, cmp, f, pos );
1040 template <typename Q, typename Compare>
1041 bool erase_at( node_type * pHead, Q const& val, Compare cmp )
1044 return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1047 template <typename Q, typename Compare>
1048 value_type * extract_at( node_type * const pHead, Q const& val, Compare cmp )
1051 assert( gc::is_locked()) ; // RCU must be locked
1054 search( pHead, val, pos, cmp );
1057 scoped_position_lock alp( pos );
1058 if ( validate( pos.pPred, pos.pCur )) {
1059 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1061 unlink_node( pos.pPred, pos.pCur, pHead );
1073 return node_traits::to_value_ptr( pos.pCur );
1079 template <typename Q, typename Compare, typename Func>
1080 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) const
1085 search( pHead, val, pos, cmp );
1086 if ( pos.pCur != &m_Tail ) {
1087 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1088 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1090 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1097 template <typename Q, typename Compare>
1098 bool find_at( node_type * pHead, Q& val, Compare cmp ) const
1101 return find_at_( pHead, val, cmp ) != end();
1104 template <typename Q, typename Compare>
1105 const_iterator find_at_( node_type * pHead, Q& val, Compare cmp ) const
1107 assert( gc::is_locked());
1111 search( pHead, val, pos, cmp );
1112 if ( pos.pCur != &m_Tail ) {
1113 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1114 return const_iterator( pos.pCur );
1119 template <typename Q, typename Compare>
1120 value_type * get_at( node_type * pHead, Q const& val, Compare cmp ) const
1122 value_type * pFound = nullptr;
1123 return find_at( pHead, val, cmp, [&pFound](value_type& found, Q const& ) { pFound = &found; } )
1131 template <typename Q>
1132 void search( node_type * const pHead, Q const& key, position& pos ) const
1134 search( pHead, key, pos, key_comparator());
1137 template <typename Q, typename Compare>
1138 void search( node_type * const pHead, Q const& key, position& pos, Compare cmp ) const
1140 // RCU should be locked
1141 assert( gc::is_locked());
1143 node_type const* pTail = &m_Tail;
1145 marked_node_ptr pCur(pHead);
1146 marked_node_ptr pPrev(pHead);
1148 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) < 0 )) {
1150 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
1152 pPrev = pCur = pHead;
1155 pos.pCur = pCur.ptr();
1156 pos.pPred = pPrev.ptr();
1159 static bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1161 // RCU lock should be locked
1162 assert( gc::is_locked());
1164 return !pPred->is_marked()
1165 && !pCur->is_marked()
1166 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1173 bool insert_at_locked( node_type * pHead, value_type& val )
1175 // RCU lock should be locked
1176 assert( gc::is_locked());
1178 link_checker::is_empty( node_traits::to_node_ptr( val ));
1183 search( pHead, val, pos );
1185 scoped_position_lock alp( pos );
1186 if ( validate( pos.pPred, pos.pCur )) {
1187 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1188 // failed: key already in list
1192 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1200 template <typename Func>
1201 std::pair<iterator, bool> update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1203 // RCU lock should be locked
1204 assert( gc::is_locked());
1210 search( pHead, val, pos );
1212 scoped_position_lock alp( pos );
1213 if ( validate( pos.pPred, pos.pCur )) {
1214 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1215 // key already in the list
1217 func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
1218 return std::make_pair( iterator( pos.pCur ), false );
1222 if ( !bAllowInsert )
1223 return std::make_pair( end(), false );
1225 link_checker::is_empty( node_traits::to_node_ptr( val ));
1227 func( true, val, val );
1228 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1230 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
1239 }} // namespace cds::intrusive
1241 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H