3 #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H
4 #define __CDS_CONTAINER_LAZY_KVLIST_RCU_H
6 #include <cds/container/lazy_list_base.h>
7 #include <cds/intrusive/lazy_list_rcu.h>
8 #include <cds/container/details/make_lazy_kvlist.h>
10 #include <cds/details/functor_wrapper.h>
11 #include <cds/details/std/memory.h>
13 namespace cds { namespace container {
15 /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
16 /** @ingroup cds_nonintrusive_list
17 \anchor cds_nonintrusive_LazyKVList_rcu
19 This is key-value variation of non-intrusive LazyList.
20 Like standard container, this implementation split a value stored into two part -
21 constant key and alterable value.
23 Usually, ordered single-linked list is used as a building block for the hash table implementation.
24 The complexity of searching is <tt>O(N)</tt>.
27 - \p RCU - one of \ref cds_urcu_gc "RCU type"
28 - \p Key - key type of an item stored in the list. It should be copy-constructible
29 - \p Value - value type stored in the list
30 - \p Traits - type traits, default is lazy_list::type_traits
32 It is possible to declare option-based list with cds::container::lazy_list::make_traits metafunction istead of \p Traits template
33 argument. For example, the following traits-based declaration of gc::HP lazy list
34 @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
35 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
37 #include <cds/urcu/general_threaded.h>
38 #include <cds/container/lazy_kvlist_rcu.h>
39 // Declare comparator for the item
41 int operator ()( int i1, int i2 )
47 // Declare type_traits
48 struct my_traits: public cds::container::lazy_list::type_traits
50 typedef my_compare compare;
53 // Declare traits-based list
54 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits > traits_based_list;
57 is equivalent for the following option-based list
59 #include <cds/urcu/general_threaded.h>
60 #include <cds/container/lazy_kvlist_rcu.h>
62 // my_compare is the same
64 // Declare option-based list
65 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
66 typename cds::container::lazy_list::make_traits<
67 cds::container::opt::compare< my_compare > // item comparator option
72 Template argument list \p Options of cds::container::lazy_list::make_traits metafunction are:
73 - opt::compare - key comparison functor. No default functor is provided.
74 If the option is not specified, the opt::less is used.
75 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
76 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
77 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
78 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
79 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
80 or opt::v::sequential_consistent (sequentially consisnent memory model).
81 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
87 #ifdef CDS_DOXYGEN_INVOKED
88 typename Traits = lazy_list::type_traits
93 class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
94 #ifdef CDS_DOXYGEN_INVOKED
95 protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
97 protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
101 typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
102 typedef typename options::type base_class;
106 #ifdef CDS_DOXYGEN_INVOKED
107 typedef Key key_type ; ///< Key type
108 typedef Value mapped_type ; ///< Type of value stored in the list
109 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
111 typedef typename options::key_type key_type;
112 typedef typename options::value_type mapped_type;
113 typedef typename options::pair_type value_type;
116 typedef typename base_class::gc gc ; ///< Garbage collector used
117 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
118 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
119 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
120 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
121 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
124 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
125 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
129 typedef typename base_class::value_type node_type;
130 typedef typename options::cxx_allocator cxx_allocator;
131 typedef typename options::node_deallocator node_deallocator;
132 typedef typename options::type_traits::compare intrusive_key_comparator;
134 typedef typename base_class::node_type head_type;
138 /// pointer to extracted node
139 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
140 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
145 # ifndef CDS_CXX11_LAMBDA_SUPPORT
146 template <typename Func>
147 class insert_functor: protected cds::details::functor_wrapper<Func>
149 typedef cds::details::functor_wrapper<Func> base_class;
151 insert_functor ( Func f )
155 void operator()( node_type& node )
157 base_class::get()( node.m_Data );
161 template <typename Func>
162 class ensure_functor: protected cds::details::functor_wrapper<Func>
164 typedef cds::details::functor_wrapper<Func> base_class;
166 ensure_functor( Func f )
170 void operator ()( bool bNew, node_type& node, node_type& )
172 base_class::get()( bNew, node.m_Data );
176 template <typename Func>
177 class find_functor: protected cds::details::functor_wrapper<Func>
179 typedef cds::details::functor_wrapper<Func> base_class;
181 find_functor( Func f )
185 template <typename Q>
186 void operator ()( node_type& node, Q& )
188 base_class::get()( node.m_Data );
192 struct empty_find_functor
194 template <typename Q>
195 void operator ()( node_type& node, Q& val ) const
199 template <typename Func>
204 erase_functor( Func f )
208 void operator ()( node_type const & node )
210 cds::unref(m_func)( const_cast<value_type&>(node.m_Data) );
213 # endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
218 template <typename K>
219 static node_type * alloc_node(const K& key)
221 return cxx_allocator().New( key );
224 template <typename K, typename V>
225 static node_type * alloc_node( const K& key, const V& val )
227 return cxx_allocator().New( key, val );
230 #ifdef CDS_EMPLACE_SUPPORT
231 template <typename... Args>
232 static node_type * alloc_node( Args&&... args )
234 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
238 static void free_node( node_type * pNode )
240 cxx_allocator().Delete( pNode );
243 struct node_disposer {
244 void operator()( node_type * pNode )
249 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
253 return base_class::m_Head;
256 head_type& head() const
258 return const_cast<head_type&>( base_class::m_Head );
263 return base_class::m_Tail;
266 head_type& tail() const
268 return const_cast<head_type&>( base_class::m_Tail );
275 template <bool IsConst>
276 class iterator_type: protected base_class::template iterator_type<IsConst>
278 typedef typename base_class::template iterator_type<IsConst> iterator_base;
280 iterator_type( head_type const& pNode )
281 : iterator_base( const_cast<head_type *>(&pNode) )
283 iterator_type( head_type const * pNode )
284 : iterator_base( const_cast<head_type *>(pNode) )
287 friend class LazyKVList;
290 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
291 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
293 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
294 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
299 iterator_type( iterator_type const& src )
300 : iterator_base( src )
303 key_type const& key() const
305 typename iterator_base::value_ptr p = iterator_base::operator ->();
306 assert( p != nullptr );
307 return p->m_Data.first;
310 value_ref val() const
312 typename iterator_base::value_ptr p = iterator_base::operator ->();
313 assert( p != nullptr );
314 return p->m_Data.second;
317 pair_ptr operator ->() const
319 typename iterator_base::value_ptr p = iterator_base::operator ->();
320 return p ? &(p->m_Data) : nullptr;
323 pair_ref operator *() const
325 typename iterator_base::value_ref p = iterator_base::operator *();
330 iterator_type& operator ++()
332 iterator_base::operator ++();
337 bool operator ==(iterator_type<C> const& i ) const
339 return iterator_base::operator ==(i);
342 bool operator !=(iterator_type<C> const& i ) const
344 return iterator_base::operator !=(i);
351 typedef iterator_type<false> iterator;
353 /// Const forward iterator
354 typedef iterator_type<true> const_iterator;
356 /// Returns a forward iterator addressing the first element in a list
358 For empty list \code begin() == end() \endcode
362 iterator it( head() );
363 ++it ; // skip dummy head
367 /// Returns an iterator that addresses the location succeeding the last element in a list
369 Do not use the value returned by <tt>end</tt> function to access any item.
370 Internally, <tt>end</tt> returning value pointing to dummy tail node.
372 The returned value can be used only to control reaching the end of the list.
373 For empty list \code begin() == end() \endcode
377 return iterator( tail() );
380 /// Returns a forward const iterator addressing the first element in a list
382 const_iterator begin() const
384 const_iterator it( head() );
385 ++it; // skip dummy head
388 const_iterator cbegin()
390 const_iterator it( head() );
391 ++it; // skip dummy head
396 /// Returns an const iterator that addresses the location succeeding the last element in a list
398 const_iterator end() const
400 return const_iterator( tail());
402 const_iterator cend()
404 return const_iterator( tail());
409 /// Default constructor
411 Initializes empty list
425 /// Inserts new node with key and default value
427 The function creates a node with \p key and default value, and then inserts the node created into the list.
430 - The \ref key_type should be constructible from value of type \p K.
431 In trivial case, \p K is equal to \ref key_type.
432 - The \ref mapped_type should be default-constructible.
434 The function makes RCU lock internally.
436 Returns \p true if inserting successful, \p false otherwise.
438 template <typename K>
439 bool insert( const K& key )
441 return insert_at( head(), key );
444 /// Inserts new node with a key and a value
446 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
449 - The \ref key_type should be constructible from \p key of type \p K.
450 - The \ref mapped_type should be constructible from \p val of type \p V.
452 The function makes RCU lock internally.
454 Returns \p true if inserting successful, \p false otherwise.
456 template <typename K, typename V>
457 bool insert( const K& key, const V& val )
459 return insert_at( head(), key, val );
462 /// Inserts new node and initializes it by a functor
464 This function inserts new node with key \p key and if inserting is successful then it calls
465 \p func functor with signature
468 void operator()( value_type& item );
472 The argument \p item of user-defined functor \p func is the reference
473 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
474 User-defined functor \p func should guarantee that during changing item's value no any other changes
475 could be made on this list's item by concurrent threads.
476 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
477 and it is called only if inserting is successful.
479 The key_type should be constructible from value of type \p K.
481 The function allows to split creating of new item into two part:
482 - create item from \p key;
483 - insert new item into the list;
484 - if inserting is successful, initialize the value of item by calling \p func functor
486 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
487 it is preferable that the initialization should be completed only if inserting is successful.
489 The function makes RCU lock internally.
491 template <typename K, typename Func>
492 bool insert_key( const K& key, Func func )
494 return insert_key_at( head(), key, func );
497 # ifdef CDS_EMPLACE_SUPPORT
498 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
500 Returns \p true if inserting successful, \p false otherwise.
502 The function makes RCU lock internally.
504 @note This function is available only for compiler that supports
505 variadic template and move semantics
507 template <typename... Args>
508 bool emplace( Args&&... args )
510 return emplace_at( head(), std::forward<Args>(args)... );
514 /// Ensures that the \p key exists in the list
516 The operation performs inserting or changing data with lock-free manner.
518 If the \p key not found in the list, then the new item created from \p key
519 is inserted into the list (note that in this case the \ref key_type should be
520 copy-constructible from type \p K).
521 Otherwise, the functor \p func is called with item found.
522 The functor \p Func may be a function with signature:
524 void func( bool bNew, value_type& item );
529 void operator()( bool bNew, value_type& item );
534 - \p bNew - \p true if the item has been inserted, \p false otherwise
535 - \p item - item of the list
537 The functor may change any fields of the \p item.second that is \ref mapped_type;
538 however, \p func must guarantee that during changing no any other modifications
539 could be made on this item by concurrent threads.
541 You may pass \p func argument by reference using <tt>boost::ref</tt>.
543 The function makes RCU lock internally.
545 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
546 \p second is true if new item has been added or \p false if the item with \p key
547 already is in the list.
549 template <typename K, typename Func>
550 std::pair<bool, bool> ensure( const K& key, Func f )
552 return ensure_at( head(), key, f );
555 /// Deletes \p key from the list
556 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
558 RCU \p synchronize method can be called. RCU should not be locked.
560 Returns \p true if \p key is found and has been deleted, \p false otherwise
562 template <typename K>
563 bool erase( K const& key )
565 return erase_at( head(), key, intrusive_key_comparator() );
568 /// Deletes the item from the list using \p pred predicate for searching
570 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
571 but \p pred is used for key comparing.
572 \p Less functor has the interface like \p std::less.
573 \p pred must imply the same element order as the comparator used for building the list.
575 template <typename K, typename Less>
576 bool erase_with( K const& key, Less pred )
578 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
581 /// Deletes \p key from the list
582 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
583 The function searches an item with key \p key, calls \p f functor
584 and deletes the item. If \p key is not found, the functor is not called.
586 The functor \p Func interface:
589 void operator()(value_type& val) { ... }
592 The functor may be passed by reference with <tt>boost:ref</tt>
594 RCU \p synchronize method can be called. RCU should not be locked.
596 Returns \p true if key is found and deleted, \p false otherwise
598 template <typename K, typename Func>
599 bool erase( K const& key, Func f )
601 return erase_at( head(), key, intrusive_key_comparator(), f );
604 /// Deletes the item from the list using \p pred predicate for searching
606 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
607 but \p pred is used for key comparing.
608 \p Less functor has the interface like \p std::less.
609 \p pred must imply the same element order as the comparator used for building the list.
611 template <typename K, typename Less, typename Func>
612 bool erase_with( K const& key, Less pred, Func f )
614 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
617 /// Extracts an item from the list
619 @anchor cds_nonintrusive_LazyKVList_rcu_extract
620 The function searches an item with key equal to \p key in the list,
621 unlinks it from the list, and returns pointer to an item found in \p dest argument.
622 If \p key is not found the function returns \p false.
624 @note The function does NOT call RCU read-side lock or synchronization,
625 and does NOT dispose the item found. It just excludes the item from the list
626 and returns a pointer to item found.
627 You should lock RCU before calling this function.
630 #include <cds/urcu/general_buffered.h>
631 #include <cds/container/lazy_kvlist_rcu.h>
633 typedef cds::urcu::gc< general_buffered<> > rcu;
634 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
636 rcu_lazy_list theList;
639 rcu_lazy_list::exempt_ptr p;
641 // first, we should lock RCU
642 rcu_lazy_list::rcu_lock sl;
644 // Now, you can apply extract function
645 // Note that you must not delete the item found inside the RCU lock
646 if ( theList.extract( p, 10 )) {
647 // do something with p
651 // Outside RCU lock section we may safely release extracted pointer.
652 // release() passes the pointer to RCU reclamation cycle.
656 template <typename K>
657 bool extract( exempt_ptr& dest, K const& key )
659 dest = extract_at( head(), key, intrusive_key_comparator() );
660 return !dest.empty();
663 /// Extracts an item from the list using \p pred predicate for searching
665 This function is the analog for \ref cds_nonintrusive_LazyKVList_rcu_extract "extract(exempt_ptr&, K const&)".
666 The \p pred is a predicate used for key comparing.
667 \p Less has the interface like \p std::less.
668 \p pred must imply the same element order as \ref key_comparator.
670 template <typename K, typename Less>
671 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
673 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
674 return !dest.empty();
677 /// Finds the key \p key
678 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
679 The function searches the item with key equal to \p key
680 and returns \p true if it is found, and \p false otherwise
682 The function applies RCU lock internally.
684 template <typename Q>
685 bool find( Q const& key ) const
687 return find_at( head(), key, intrusive_key_comparator() );
690 /// Finds the key \p val using \p pred predicate for searching
692 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
693 but \p pred is used for key comparing.
694 \p Less functor has the interface like \p std::less.
695 \p pred must imply the same element order as the comparator used for building the list.
697 template <typename Q, typename Less>
698 bool find_with( Q const& key, Less pred ) const
700 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
703 /// Finds the key \p key and performs an action with it
704 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
705 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
706 The interface of \p Func functor is:
709 void operator()( value_type& item );
712 where \p item is the item found.
714 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
716 The functor may change <tt>item.second</tt> that is reference to value of node.
717 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
718 The function does not serialize simultaneous access to the list \p item. If such access is
719 possible you must provide your own synchronization schema to exclude unsafe item modifications.
721 The function applies RCU lock internally.
723 The function returns \p true if \p key is found, \p false otherwise.
725 template <typename Q, typename Func>
726 bool find( Q const& key, Func f ) const
728 return find_at( head(), key, intrusive_key_comparator(), f );
731 /// Finds the key \p val using \p pred predicate for searching
733 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
734 but \p pred is used for key comparing.
735 \p Less functor has the interface like \p std::less.
736 \p pred must imply the same element order as the comparator used for building the list.
738 template <typename Q, typename Less, typename Func>
739 bool find_with( Q const& key, Less pred, Func f ) const
741 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
744 /// Finds \p key and return the item found
745 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
746 The function searches the item with \p key and returns the pointer to item found.
747 If \p key is not found it returns \p NULL.
749 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
751 RCU should be locked before call of this function.
752 Returned item is valid only while RCU is locked:
754 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
759 ord_list::rcu_lock lock;
761 ord_list::value_type * pVal = theList.get( 5 );
766 // Unlock RCU by rcu_lock destructor
767 // pVal can be freed at any time after RCU has been unlocked
771 template <typename K>
772 value_type * get( K const& key ) const
774 return get_at( head(), key, intrusive_key_comparator());
777 /// Finds \p key and return the item found
779 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
780 but \p pred is used for comparing the keys.
782 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
784 \p pred must imply the same element order as the comparator used for building the list.
786 template <typename K, typename Less>
787 value_type * get_with( K const& key, Less pred ) const
789 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
792 /// Checks if the list is empty
795 return base_class::empty();
798 /// Returns list's item count
800 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
801 this function always returns 0.
803 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
804 is empty. To check list emptyness use \ref empty() method.
808 return base_class::size();
813 Post-condition: the list is empty
822 bool insert_node_at( head_type& refHead, node_type * pNode )
824 assert( pNode != nullptr );
825 scoped_node_ptr p( pNode );
827 if ( base_class::insert_at( &refHead, *p )) {
835 template <typename K>
836 bool insert_at( head_type& refHead, const K& key )
838 return insert_node_at( refHead, alloc_node( key ));
841 template <typename K, typename V>
842 bool insert_at( head_type& refHead, const K& key, const V& val )
844 return insert_node_at( refHead, alloc_node( key, val ));
847 template <typename K, typename Func>
848 bool insert_key_at( head_type& refHead, const K& key, Func f )
850 scoped_node_ptr pNode( alloc_node( key ));
852 # ifdef CDS_CXX11_LAMBDA_SUPPORT
853 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node.m_Data ); } ))
855 insert_functor<Func> wrapper( f );
856 if ( base_class::insert_at( &refHead, *pNode, cds::ref(wrapper) ))
865 # ifdef CDS_EMPLACE_SUPPORT
866 template <typename... Args>
867 bool emplace_at( head_type& refHead, Args&&... args )
869 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
873 template <typename K, typename Compare>
874 bool erase_at( head_type& refHead, K const& key, Compare cmp )
876 return base_class::erase_at( &refHead, key, cmp );
879 template <typename K, typename Compare, typename Func>
880 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
882 # ifdef CDS_CXX11_LAMBDA_SUPPORT
883 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){cds::unref(f)( const_cast<value_type&>(node.m_Data)); });
885 erase_functor<Func> wrapper( f );
886 return base_class::erase_at( &refHead, key, cmp, cds::ref(wrapper) );
890 template <typename K, typename Func>
891 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
893 scoped_node_ptr pNode( alloc_node( key ));
895 # ifdef CDS_CXX11_LAMBDA_SUPPORT
896 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
897 [&f]( bool bNew, node_type& node, node_type& ){ cds::unref(f)( bNew, node.m_Data ); });
899 ensure_functor<Func> wrapper( f );
900 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, cds::ref(wrapper));
902 if ( ret.first && ret.second )
908 template <typename K, typename Compare>
909 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
911 return base_class::extract_at( &refHead, key, cmp );
914 template <typename K, typename Compare>
915 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
917 # ifdef CDS_CXX11_LAMBDA_SUPPORT
918 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
920 return base_class::find_at( &refHead, key, cmp, empty_find_functor() );
924 template <typename K, typename Compare, typename Func>
925 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
927 # ifdef CDS_CXX11_LAMBDA_SUPPORT
928 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ cds::unref(f)( node.m_Data ); });
930 find_functor<Func> wrapper( f );
931 return base_class::find_at( &refHead, key, cmp, cds::ref(wrapper) );
935 template <typename K, typename Compare>
936 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
938 node_type * pNode = base_class::get_at( &refHead, val, cmp );
939 return pNode ? &pNode->m_Data : nullptr;
945 }} // namespace cds::container
947 #endif // #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H