3 #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
4 #define __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
6 #include <cds/container/michael_list_base.h>
7 #include <cds/intrusive/michael_list_rcu.h>
8 #include <cds/container/details/make_michael_kvlist.h>
10 #include <cds/details/functor_wrapper.h>
11 #include <cds/details/std/memory.h>
13 namespace cds { namespace container {
15 /// Michael's ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
16 /** @ingroup cds_nonintrusive_list
17 \anchor cds_nonintrusive_MichaelKVList_rcu
19 This is key-value variation of non-intrusive \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
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 a list
30 - \p Traits - type traits, default is michael_list::type_traits
32 @note Before including <tt><cds/container/michael_kvlist_rcu.h></tt> you should include appropriate RCU header file,
33 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
35 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
36 argument. For example, the following traits-based declaration of Michael's list
38 #include <cds/urcu/general_buffered.h>
39 #include <cds/container/michael_kvlist_rcu.h>
40 // Declare comparator for the item
42 int operator ()( int i1, int i2 )
48 // Declare type_traits
49 struct my_traits: public cds::container::michael_list::type_traits
51 typedef my_compare compare;
54 // Declare traits-based list
55 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int, my_traits > traits_based_list;
58 is equivalent for the following option-based list
60 #include <cds/urcu/general_buffered.h>
61 #include <cds/container/michael_kvlist_rcu.h>
63 // my_compare is the same
65 // Declare option-based list
66 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int,
67 typename cds::container::michael_list::make_traits<
68 cds::container::opt::compare< my_compare > // item comparator option
73 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
74 - opt::compare - key comparison functor. No default functor is provided.
75 If the option is not specified, the opt::less is used.
76 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
77 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
78 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
79 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
80 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
81 or opt::v::sequential_consistent (sequentially consisnent memory model).
82 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
88 #ifdef CDS_DOXYGEN_INVOKED
89 typename Traits = michael_list::type_traits
94 class MichaelKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
95 #ifdef CDS_DOXYGEN_INVOKED
96 protected intrusive::MichaelList< cds::urcu::gc<RCU>, implementation_defined, Traits >
98 protected details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
102 typedef details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
103 typedef typename options::type base_class;
107 #ifdef CDS_DOXYGEN_INVOKED
108 typedef Key key_type ; ///< Key type
109 typedef Value mapped_type ; ///< Type of value stored in the list
110 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
112 typedef typename options::key_type key_type;
113 typedef typename options::value_type mapped_type;
114 typedef typename options::pair_type value_type;
117 typedef typename base_class::gc gc ; ///< Garbage collector used
118 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
119 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
120 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
121 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
122 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
123 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
125 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
126 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
130 typedef typename base_class::value_type node_type;
131 typedef typename options::cxx_allocator cxx_allocator;
132 typedef typename options::node_deallocator node_deallocator;
133 typedef typename options::type_traits::compare intrusive_key_comparator;
135 typedef typename base_class::atomic_node_ptr head_type;
139 /// pointer to extracted node
140 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
141 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
146 # ifndef CDS_CXX11_LAMBDA_SUPPORT
147 template <typename Func>
148 class insert_functor: protected cds::details::functor_wrapper<Func>
150 typedef cds::details::functor_wrapper<Func> base_class;
152 insert_functor ( Func f )
156 void operator()( node_type& node )
158 base_class::get()( node.m_Data );
162 template <typename Func>
163 class ensure_functor: protected cds::details::functor_wrapper<Func>
165 typedef cds::details::functor_wrapper<Func> base_class;
167 ensure_functor( Func f )
171 void operator ()( bool bNew, node_type& node, node_type& )
173 base_class::get()( bNew, node.m_Data );
177 template <typename Func>
178 class find_functor: protected cds::details::functor_wrapper<Func>
180 typedef cds::details::functor_wrapper<Func> base_class;
182 find_functor( Func f )
186 template <typename Q>
187 void operator ()( node_type& node, Q& )
189 base_class::get()( node.m_Data );
193 struct empty_find_functor
195 template <typename Q>
196 void operator ()( node_type& node, Q& val ) const
200 template <typename Func>
205 erase_functor( Func f )
209 void operator ()( node_type const & node )
211 cds::unref(m_func)( const_cast<value_type&>(node.m_Data) );
214 # endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
219 template <typename K>
220 static node_type * alloc_node(const K& key)
222 return cxx_allocator().New( key );
225 template <typename K, typename V>
226 static node_type * alloc_node( const K& key, const V& val )
228 return cxx_allocator().New( key, val );
231 # ifdef CDS_EMPLACE_SUPPORT
232 template <typename K, typename... Args>
233 static node_type * alloc_node( K&& key, Args&&... args )
235 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
239 static void free_node( node_type * pNode )
241 cxx_allocator().Delete( pNode );
244 struct node_disposer {
245 void operator()( node_type * pNode )
250 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
254 return base_class::m_pHead;
257 head_type& head() const
259 return const_cast<head_type&>( base_class::m_pHead );
265 template <bool IsConst>
266 class iterator_type: protected base_class::template iterator_type<IsConst>
268 typedef typename base_class::template iterator_type<IsConst> iterator_base;
270 iterator_type( head_type const& pNode )
271 : iterator_base( pNode )
274 friend class MichaelKVList;
277 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
278 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
280 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
281 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
286 iterator_type( iterator_type const& src )
287 : iterator_base( src )
290 key_type const& key() const
292 typename iterator_base::value_ptr p = iterator_base::operator ->();
293 assert( p != nullptr );
294 return p->m_Data.first;
297 pair_ptr operator ->() const
299 typename iterator_base::value_ptr p = iterator_base::operator ->();
300 return p ? &(p->m_Data) : nullptr;
303 pair_ref operator *() const
305 typename iterator_base::value_ref p = iterator_base::operator *();
309 value_ref val() const
311 typename iterator_base::value_ptr p = iterator_base::operator ->();
312 assert( p != nullptr );
313 return p->m_Data.second;
317 iterator_type& operator ++()
319 iterator_base::operator ++();
324 bool operator ==(iterator_type<C> const& i ) const
326 return iterator_base::operator ==(i);
329 bool operator !=(iterator_type<C> const& i ) const
331 return iterator_base::operator !=(i);
338 typedef iterator_type<false> iterator;
340 /// Const forward iterator
341 typedef iterator_type<true> const_iterator;
343 /// Returns a forward iterator addressing the first element in a list
345 For empty list \code begin() == end() \endcode
349 return iterator( head() );
352 /// Returns an iterator that addresses the location succeeding the last element in a list
354 Do not use the value returned by <tt>end</tt> function to access any item.
355 Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
357 The returned value can be used only to control reaching the end of the list.
358 For empty list \code begin() == end() \endcode
365 /// Returns a forward const iterator addressing the first element in a list
367 const_iterator begin() const
369 return const_iterator( head() );
371 const_iterator cbegin()
373 return const_iterator( head() );
377 /// Returns an const iterator that addresses the location succeeding the last element in a list
379 const_iterator end() const
381 return const_iterator();
383 const_iterator cend()
385 return const_iterator();
390 /// Default constructor
392 Initializes empty list
406 /// Inserts new node with key and default value
408 The function creates a node with \p key and default value, and then inserts the node created into the list.
411 - The \ref key_type should be constructible from value of type \p K.
412 In trivial case, \p K is equal to \ref key_type.
413 - The \ref mapped_type should be default-constructible.
415 The function makes RCU lock internally.
417 Returns \p true if inserting successful, \p false otherwise.
419 template <typename K>
420 bool insert( const K& key )
422 return insert_at( head(), key );
425 /// Inserts new node with a key and a value
427 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
430 - The \ref key_type should be constructible from \p key of type \p K.
431 - The \ref mapped_type should be constructible from \p val of type \p V.
433 The function makes RCU lock internally.
435 Returns \p true if inserting successful, \p false otherwise.
437 template <typename K, typename V>
438 bool insert( const K& key, const V& val )
440 return insert_at( head(), key, val );
443 /// Inserts new node and initialize it by a functor
445 This function inserts new node with key \p key and if inserting is successful then it calls
446 \p func functor with signature
449 void operator()( value_type& item );
453 The argument \p item of user-defined functor \p func is the reference
454 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
455 User-defined functor \p func should guarantee that during changing item's value no any other changes
456 could be made on this list's item by concurrent threads.
457 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
458 and it is called only if inserting is successful.
460 The key_type should be constructible from value of type \p K.
462 The function allows to split creating of new item into two part:
463 - create item from \p key;
464 - insert new item into the list;
465 - if inserting is successful, initialize the value of item by calling \p func functor
467 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
468 it is preferable that the initialization should be completed only if inserting is successful.
470 The function makes RCU lock internally.
472 template <typename K, typename Func>
473 bool insert_key( const K& key, Func func )
475 return insert_key_at( head(), key, func );
478 /// Ensures that the \p key exists in the list
480 The operation performs inserting or changing data with lock-free manner.
482 If the \p key not found in the list, then the new item created from \p key
483 is inserted into the list (note that in this case the \ref key_type should be
484 copy-constructible from type \p K).
485 Otherwise, the functor \p func is called with item found.
486 The functor \p Func may be a function with signature:
488 void func( bool bNew, value_type& item );
493 void operator()( bool bNew, value_type& item );
498 - \p bNew - \p true if the item has been inserted, \p false otherwise
499 - \p item - item of the list
501 The functor may change any fields of the \p item.second that is \ref mapped_type;
502 however, \p func must guarantee that during changing no any other modifications
503 could be made on this item by concurrent threads.
505 You may pass \p func argument by reference using <tt>boost::ref</tt>.
507 The function makes RCU lock internally.
509 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
510 \p second is true if new item has been added or \p false if the item with \p key
511 already is in the list.
513 template <typename K, typename Func>
514 std::pair<bool, bool> ensure( const K& key, Func f )
516 return ensure_at( head(), key, f );
519 # ifdef CDS_EMPLACE_SUPPORT
520 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
522 Returns \p true if inserting successful, \p false otherwise.
524 The function makes RCU lock internally.
526 @note This function is available only for compiler that supports
527 variadic template and move semantics
529 template <typename K, typename... Args>
530 bool emplace( K&& key, Args&&... args )
532 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
536 /// Deletes \p key from the list
537 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase
539 RCU \p synchronize method can be called. RCU should not be locked.
541 Returns \p true if \p key is found and has been deleted, \p false otherwise
543 template <typename K>
544 bool erase( K const& key )
546 return erase_at( head(), key, intrusive_key_comparator() );
549 /// Deletes the item from the list using \p pred predicate for searching
551 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase "erase(K const&)"
552 but \p pred is used for key comparing.
553 \p Less functor has the interface like \p std::less.
554 \p pred must imply the same element order as the comparator used for building the list.
556 template <typename K, typename Less>
557 bool erase_with( K const& key, Less pred )
559 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
562 /// Deletes \p key from the list
563 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase_func
564 The function searches an item with key \p key, calls \p f functor
565 and deletes the item. If \p key is not found, the functor is not called.
567 The functor \p Func interface:
570 void operator()(value_type& val) { ... }
573 The functor may be passed by reference with <tt>boost:ref</tt>
575 RCU \p synchronize method can be called. RCU should not be locked.
577 Return \p true if key is found and deleted, \p false otherwise
581 template <typename K, typename Func>
582 bool erase( K const& key, Func f )
584 return erase_at( head(), key, intrusive_key_comparator(), f );
587 /// Deletes the item from the list using \p pred predicate for searching
589 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase_func "erase(K const&, Func)"
590 but \p pred is used for key comparing.
591 \p Less functor has the interface like \p std::less.
592 \p pred must imply the same element order as the comparator used for building the list.
594 template <typename K, typename Less, typename Func>
595 bool erase_with( K const& key, Less pred, Func f )
597 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
600 /// Extracts an item from the list
602 @anchor cds_nonintrusive_MichaelKVList_rcu_extract
603 The function searches an item with key equal to \p key in the list,
604 unlinks it from the list, and returns pointer to an item found in \p dest argument.
605 If \p key is not found the function returns \p false.
607 @note The function does NOT call RCU read-side lock or synchronization,
608 and does NOT dispose the item found. It just excludes the item from the list
609 and returns a pointer to item found.
610 You should lock RCU before calling this function.
613 #include <cds/urcu/general_buffered.h>
614 #include <cds/container/michael_kvlist_rcu.h>
616 typedef cds::urcu::gc< general_buffered<> > rcu;
617 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
619 rcu_michael_list theList;
622 rcu_michael_list::exempt_ptr p;
624 // first, we should lock RCU
625 rcu_michael_list::rcu_lock sl;
627 // Now, you can apply extract function
628 // Note that you must not delete the item found inside the RCU lock
629 if ( theList.extract( p, 10 )) {
630 // do something with p
634 // Outside RCU lock section we may safely release extracted pointer.
635 // release() passes the pointer to RCU reclamation cycle.
639 template <typename K>
640 bool extract( exempt_ptr& dest, K const& key )
642 dest = extract_at( head(), key, intrusive_key_comparator() );
643 return !dest.empty();
646 /// Extracts an item from the list using \p pred predicate for searching
648 This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, K const&)".
649 The \p pred is a predicate used for key comparing.
650 \p Less has the interface like \p std::less.
651 \p pred must imply the same element order as \ref key_comparator.
653 template <typename K, typename Less>
654 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
656 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
657 return !dest.empty();
660 /// Finds the key \p key
661 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_val
663 The function searches the item with key equal to \p key
664 and returns \p true if it is found, and \p false otherwise
666 The function makes RCU lock internally.
668 template <typename Q>
669 bool find( Q const& key ) const
671 return find_at( head(), key, intrusive_key_comparator() );
674 /// Finds the key \p val using \p pred predicate for searching
676 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_val "find(Q const&)"
677 but \p pred is used for key comparing.
678 \p Less functor has the interface like \p std::less.
679 \p pred must imply the same element order as the comparator used for building the list.
681 template <typename Q, typename Less>
682 bool find_with( Q const& key, Less pred ) const
684 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
687 /// Finds the key \p key and performs an action with it
688 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_func
689 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
690 The interface of \p Func functor is:
693 void operator()( value_type& item );
696 where \p item is the item found.
698 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
700 The functor may change <tt>item.second</tt> that is reference to value of node.
701 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
702 The function does not serialize simultaneous access to the list \p item. If such access is
703 possible you must provide your own synchronization schema to exclude unsafe item modifications.
705 The function makes RCU lock internally.
707 The function returns \p true if \p key is found, \p false otherwise.
709 template <typename Q, typename Func>
710 bool find( Q const& key, Func f ) const
712 return find_at( head(), key, intrusive_key_comparator(), f );
715 /// Finds the key \p val using \p pred predicate for searching
717 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_func "find(Q const&, Func)"
718 but \p pred is used for key comparing.
719 \p Less functor has the interface like \p std::less.
720 \p pred must imply the same element order as the comparator used for building the list.
722 template <typename Q, typename Less, typename Func>
723 bool find_with( Q const& key, Less pred, Func f ) const
725 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
728 /// Finds \p key and return the item found
729 /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
730 The function searches the item with \p key and returns the pointer to item found.
731 If \p key is not found it returns \p NULL.
733 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
735 RCU should be locked before call of this function.
736 Returned item is valid only while RCU is locked:
738 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
743 ord_list::rcu_lock lock;
745 ord_list::value_type * pVal = theList.get( 5 );
750 // Unlock RCU by rcu_lock destructor
751 // pVal can be freed at any time after RCU has been unlocked
755 template <typename K>
756 value_type * get( K const& key ) const
758 return get_at( head(), key, intrusive_key_comparator());
761 /// Finds \p key and return the item found
763 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_get "get(K const&)"
764 but \p pred is used for comparing the keys.
766 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
768 \p pred must imply the same element order as the comparator used for building the list.
770 template <typename K, typename Less>
771 value_type * get_with( K const& key, Less pred ) const
773 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
776 /// Checks if the list is empty
779 return base_class::empty();
782 /// Returns list's item count
784 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
785 this function always returns 0.
787 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
788 is empty. To check list emptyness use \ref empty() method.
792 return base_class::size();
797 Post-condition: the list is empty
806 bool insert_node_at( head_type& refHead, node_type * pNode )
808 assert( pNode != nullptr );
809 scoped_node_ptr p( pNode );
810 if ( base_class::insert_at( refHead, *pNode )) {
817 template <typename K>
818 bool insert_at( head_type& refHead, const K& key )
820 return insert_node_at( refHead, alloc_node( key ));
823 template <typename K, typename V>
824 bool insert_at( head_type& refHead, const K& key, const V& val )
826 return insert_node_at( refHead, alloc_node( key, val ));
829 template <typename K, typename Func>
830 bool insert_key_at( head_type& refHead, const K& key, Func f )
832 scoped_node_ptr pNode( alloc_node( key ));
834 # ifdef CDS_CXX11_LAMBDA_SUPPORT
835 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node.m_Data ); }))
837 insert_functor<Func> wrapper( f );
838 if ( base_class::insert_at( refHead, *pNode, cds::ref(wrapper) ))
847 # ifdef CDS_EMPLACE_SUPPORT
848 template <typename K, typename... Args>
849 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
851 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
855 template <typename K, typename Func>
856 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
858 scoped_node_ptr pNode( alloc_node( key ));
860 # ifdef CDS_CXX11_LAMBDA_SUPPORT
861 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
862 [&f]( bool bNew, node_type& node, node_type& ){ cds::unref(f)( bNew, node.m_Data ); });
864 ensure_functor<Func> wrapper( f );
865 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, cds::ref(wrapper));
867 if ( ret.first && ret.second )
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 Compare>
891 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
893 return base_class::extract_at( refHead, key, cmp );
896 template <typename K, typename Compare>
897 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
899 # ifdef CDS_CXX11_LAMBDA_SUPPORT
900 return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
902 return base_class::find_at( refHead, key, cmp, empty_find_functor() );
906 template <typename K, typename Compare, typename Func>
907 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
909 # ifdef CDS_CXX11_LAMBDA_SUPPORT
910 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ cds::unref(f)( node.m_Data ); });
912 find_functor<Func> wrapper( f );
913 return base_class::find_at( refHead, key, cmp, cds::ref(wrapper) );
917 template <typename K, typename Compare>
918 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
920 node_type * pNode = base_class::get_at( refHead, val, cmp );
921 return pNode ? &pNode->m_Data : nullptr;
927 }} // namespace cds::container
929 #endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H