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_CONTAINER_IMPL_MICHAEL_KVLIST_H
32 #define CDSLIB_CONTAINER_IMPL_MICHAEL_KVLIST_H
35 #include <cds/container/details/guarded_ptr_cast.h>
37 namespace cds { namespace container {
39 /// Michael's ordered list for key-value pair
40 /** @ingroup cds_nonintrusive_list
41 \anchor cds_nonintrusive_MichaelKVList_gc
43 This is key-value variation of non-intrusive MichaelList.
44 Like standard container, this implementation split a value stored into two part -
45 constant key and alterable value.
47 Usually, ordered single-linked list is used as a building block for the hash table implementation.
48 The complexity of searching is <tt>O(N)</tt> where \p N is the item count in the list, not in the
52 - \p GC - garbage collector used
53 - \p Key - key type of an item stored in the list. It should be copy-constructible
54 - \p Value - value type stored in a list
55 - \p Traits - type traits, default is \p michael_list::traits
57 It is possible to declare option-based list with \p cds::container::michael_list::make_traits metafunction instead of \p Traits template
58 argument. For example, the following traits-based declaration of \p gc::HP Michael's list
60 #include <cds/container/michael_kvlist_hp.h>
61 // Declare comparator for the item
63 int operator ()( int i1, int i2 )
70 struct my_traits: public cds::container::michael_list::traits
72 typedef my_compare compare;
75 // Declare traits-based list
76 typedef cds::container::MichaelKVList< cds::gc::HP, int, int, my_traits > traits_based_list;
78 is equivalent for the following option-based list
80 #include <cds/container/michael_kvlist_hp.h>
82 // my_compare is the same
84 // Declare option-based list
85 typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
86 typename cds::container::michael_list::make_traits<
87 cds::container::opt::compare< my_compare > // item comparator option
93 There are different specializations of this template for each garbage collecting schema used.
94 You should include appropriate .h-file depending on GC you are using:
95 - for gc::HP: \code #include <cds/container/michael_kvlist_hp.h> \endcode
96 - for gc::DHP: \code #include <cds/container/michael_kvlist_dhp.h> \endcode
97 - for \ref cds_urcu_desc "RCU": \code #include <cds/container/michael_kvlist_rcu.h> \endcode
98 - for gc::nogc: \code #include <cds/container/michael_kvlist_nogc.h> \endcode
104 #ifdef CDS_DOXYGEN_INVOKED
105 typename Traits = michael_list::traits
111 #ifdef CDS_DOXYGEN_INVOKED
112 protected intrusive::MichaelList< GC, implementation_defined, Traits >
114 protected details::make_michael_kvlist< GC, Key, Value, Traits >::type
118 typedef details::make_michael_kvlist< GC, Key, Value, Traits > maker;
119 typedef typename maker::type base_class;
123 #ifdef CDS_DOXYGEN_INVOKED
124 typedef Key key_type ; ///< Key type
125 typedef Value mapped_type ; ///< Type of value stored in the list
126 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
128 typedef typename maker::key_type key_type;
129 typedef typename maker::value_type mapped_type;
130 typedef typename maker::pair_type value_type;
133 typedef typename base_class::gc gc; ///< Garbage collector used
134 typedef Traits traits; ///< List traits
135 typedef typename base_class::back_off back_off; ///< Back-off strategy used
136 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
137 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
138 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
139 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
140 typedef typename base_class::stat stat; ///< Internal statistics
142 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
145 // Rebind traits (split-list support)
146 template <typename... Options>
147 struct rebind_traits {
148 typedef MichaelKVList<
150 , key_type, mapped_type
151 , typename cds::opt::make_options< traits, Options...>::type
156 template <typename Stat>
157 using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
162 typedef typename base_class::value_type node_type;
163 typedef typename maker::cxx_allocator cxx_allocator;
164 typedef typename maker::node_deallocator node_deallocator;
165 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
167 typedef typename base_class::atomic_node_ptr head_type;
172 typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_map<node_type, value_type> > guarded_ptr;
176 template <typename K>
177 static node_type * alloc_node(const K& key)
179 return cxx_allocator().New( key );
182 template <typename K, typename V>
183 static node_type * alloc_node( const K& key, const V& val )
185 return cxx_allocator().New( key, val );
188 template <typename K, typename... Args>
189 static node_type * alloc_node( K&& key, Args&&... args )
191 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
194 static void free_node( node_type * pNode )
196 cxx_allocator().Delete( pNode );
199 struct node_disposer {
200 void operator()( node_type * pNode )
205 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
209 return base_class::m_pHead;
212 head_type const& head() const
214 return base_class::m_pHead;
220 template <bool IsConst>
221 class iterator_type: protected base_class::template iterator_type<IsConst>
223 typedef typename base_class::template iterator_type<IsConst> iterator_base;
225 iterator_type( head_type const& pNode )
226 : iterator_base( pNode )
229 friend class MichaelKVList;
232 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
233 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
235 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
236 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
241 iterator_type( iterator_type const& src )
242 : iterator_base( src )
245 key_type const& key() const
247 typename iterator_base::value_ptr p = iterator_base::operator ->();
248 assert( p != nullptr );
249 return p->m_Data.first;
252 pair_ptr operator ->() const
254 typename iterator_base::value_ptr p = iterator_base::operator ->();
255 return p ? &(p->m_Data) : nullptr;
258 pair_ref operator *() const
260 typename iterator_base::value_ref p = iterator_base::operator *();
264 value_ref val() const
266 typename iterator_base::value_ptr p = iterator_base::operator ->();
267 assert( p != nullptr );
268 return p->m_Data.second;
272 iterator_type& operator ++()
274 iterator_base::operator ++();
279 bool operator ==(iterator_type<C> const& i ) const
281 return iterator_base::operator ==(i);
284 bool operator !=(iterator_type<C> const& i ) const
286 return iterator_base::operator !=(i);
294 The forward iterator for Michael's list has some features:
295 - it has no post-increment operator
296 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
297 For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
298 may be thrown if a limit of guard count per thread is exceeded.
299 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
300 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
301 deleting operations it is no guarantee that you iterate all item in the list.
303 @warning Use this iterator on the concurrent container for debugging purpose only.
305 The iterator interface to access item data:
306 - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
307 - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
308 - <tt> const key_type& key() </tt> - returns a key reference for iterator
309 - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
311 For both functions the iterator should not be equal to <tt> end() </tt>
313 typedef iterator_type<false> iterator;
315 /// Const forward iterator
317 For iterator's features and requirements see \ref iterator
319 typedef iterator_type<true> const_iterator;
321 ///@name Forward iterators (only for debugging purpose)
323 /// Returns a forward iterator addressing the first element in a list
325 For empty list \code begin() == end() \endcode
329 return iterator( head() );
332 /// Returns an iterator that addresses the location succeeding the last element in a list
334 Do not use the value returned by <tt>end</tt> function to access any item.
335 Internally, <tt>end</tt> returning value equals to \p nullptr.
337 The returned value can be used only to control reaching the end of the list.
338 For empty list \code begin() == end() \endcode
345 /// Returns a forward const iterator addressing the first element in a list
346 const_iterator begin() const
348 return const_iterator( head() );
351 /// Returns a forward const iterator addressing the first element in a list
352 const_iterator cbegin() const
354 return const_iterator( head() );
357 /// Returns an const iterator that addresses the location succeeding the last element in a list
358 const_iterator end() const
360 return const_iterator();
363 /// Returns an const iterator that addresses the location succeeding the last element in a list
364 const_iterator cend() const
366 return const_iterator();
371 /// Default constructor
373 Initializes empty list
379 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
380 explicit MichaelKVList( Stat& st )
394 /// Inserts new node with key and default value
396 The function creates a node with \p key and default value, and then inserts the node created into the list.
399 - The \p key_type should be constructible from value of type \p K.
400 In trivial case, \p K is equal to \p key_type.
401 - The \p mapped_type should be default-constructible.
403 Returns \p true if inserting successful, \p false otherwise.
405 template <typename K>
406 bool insert( K&& key )
408 return insert_at( head(), std::forward<K>( key ));
411 /// Inserts new node with a key and a value
413 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
416 - The \p key_type should be constructible from \p key of type \p K.
417 - The \p mapped_type should be constructible from \p val of type \p V.
419 Returns \p true if inserting successful, \p false otherwise.
421 template <typename K, typename V>
422 bool insert( K&& key, V&& val )
424 // We cannot use insert with functor here
425 // because we cannot lock inserted node for updating
426 // Therefore, we use separate function
427 return insert_at( head(), std::forward<K>( key ), std::forward<V>( val ));
430 /// Inserts new node and initialize it by a functor
432 This function inserts new node with key \p key and if inserting is successful then it calls
433 \p func functor with signature
436 void operator()( value_type& item );
440 The argument \p item of user-defined functor \p func is the reference
441 to the item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
442 User-defined functor \p func should guarantee that during changing item's value no any other changes
443 could be made on this list's item by concurrent threads.
444 The user-defined functor is called only if inserting is successful.
446 The \p key_type should be constructible from value of type \p K.
448 The function allows to split creating of new item into two part:
449 - create a new item from \p key;
450 - insert the new item into the list;
451 - if inserting is successful, initialize the value of item by calling \p func functor
453 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
454 it is preferable that the initialization should be completed only if inserting is successful.
456 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
458 template <typename K, typename Func>
459 bool insert_with( K&& key, Func func )
461 return insert_with_at( head(), std::forward<K>( key ), func );
464 /// Updates data by \p key
466 The operation performs inserting or replacing the element with lock-free manner.
468 If the \p key not found in the list, then the new item created from \p key
469 will be inserted iff \p bAllowInsert is \p true.
470 (note that in this case the \ref key_type should be constructible from type \p K).
471 Otherwise, if \p key is found, the functor \p func is called with item found.
473 The functor \p Func signature is:
476 void operator()( bool bNew, value_type& item );
480 - \p bNew - \p true if the item has been inserted, \p false otherwise
481 - \p item - the item found or inserted
483 The functor may change any fields of the \p item.second of \p mapped_type;
484 however, \p func must guarantee that during changing no any other modifications
485 could be made on this item by concurrent threads.
487 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
488 \p second is true if new item has been added or \p false if the item with \p key
491 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
493 template <typename K, typename Func>
494 std::pair<bool, bool> update( K&& key, Func f, bool bAllowInsert = true )
496 return update_at( head(), std::forward<K>( key ), f, bAllowInsert );
499 template <typename K, typename Func>
500 CDS_DEPRECATED("ensure() is deprecated, use update()")
501 std::pair<bool, bool> ensure( K const& key, Func f )
503 return update( key, f, true );
507 /// Inserts a new node using move semantics
509 \p key_type field of new item is constructed from \p key argument,
510 \p mapped_type field is done from \p args.
512 Returns \p true if inserting successful, \p false otherwise.
514 template <typename K, typename... Args>
515 bool emplace( K&& key, Args&&... args )
517 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
520 /// Deletes \p key from the list
521 /** \anchor cds_nonintrusive_MichaelKVList_hp_erase_val
523 Returns \p true if \p key is found and has been deleted, \p false otherwise
525 template <typename K>
526 bool erase( K const& key )
528 return erase_at( head(), key, intrusive_key_comparator() );
531 /// Deletes the item from the list using \p pred predicate for searching
533 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_erase_val "erase(K const&)"
534 but \p pred is used for key comparing.
535 \p Less functor has the interface like \p std::less.
536 \p pred must imply the same element order as the comparator used for building the list.
538 template <typename K, typename Less>
539 bool erase_with( K const& key, Less pred )
542 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
545 /// Deletes \p key from the list
546 /** \anchor cds_nonintrusive_MichaelKVList_hp_erase_func
547 The function searches an item with key \p key, calls \p f functor
548 and deletes the item. If \p key is not found, the functor is not called.
550 The functor \p Func interface:
553 void operator()(value_type& val) { ... }
557 Return \p true if key is found and deleted, \p false otherwise
561 template <typename K, typename Func>
562 bool erase( K const& key, Func f )
564 return erase_at( head(), key, intrusive_key_comparator(), f );
567 /// Deletes the item from the list using \p pred predicate for searching
569 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_erase_func "erase(K const&, Func)"
570 but \p pred is used for key comparing.
571 \p Less functor has the interface like \p std::less.
572 \p pred must imply the same element order as the comparator used for building the list.
574 template <typename K, typename Less, typename Func>
575 bool erase_with( K const& key, Less pred, Func f )
578 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
581 /// Extracts the item from the list with specified \p key
582 /** \anchor cds_nonintrusive_MichaelKVList_hp_extract
583 The function searches an item with key equal to \p key,
584 unlinks it from the list, and returns it as \p guarded_ptr.
585 If \p key is not found the function returns an empty guarded pointer.
587 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
589 The \p disposer specified in \p Traits class template parameter is called automatically
590 by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
591 will be destroyed or released.
592 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
596 typedef cds::container::MichaelKVList< cds::gc::HP, int, foo, my_traits > ord_list;
600 ord_list::guarded_ptr gp(theList.extract( 5 ));
605 // Destructor of gp releases internal HP guard
609 template <typename K>
610 guarded_ptr extract( K const& key )
612 return extract_at( head(), key, intrusive_key_comparator() );
615 /// Extracts the item from the list with comparing functor \p pred
617 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_extract "extract(K const&)"
618 but \p pred predicate is used for key comparing.
620 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
622 \p pred must imply the same element order as the comparator used for building the list.
624 template <typename K, typename Less>
625 guarded_ptr extract_with( K const& key, Less pred )
628 return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
631 /// Checks whether the list contains \p key
633 The function searches the item with key equal to \p key
634 and returns \p true if it is found, and \p false otherwise.
636 template <typename Q>
637 bool contains( Q const& key )
639 return find_at( head(), key, intrusive_key_comparator() );
642 template <typename Q>
643 CDS_DEPRECATED("deprecated, use contains()")
644 bool find( Q const& key )
646 return contains( key );
650 /// Checks whether the map contains \p key using \p pred predicate for searching
652 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
653 \p Less functor has the interface like \p std::less.
654 \p Less must imply the same element order as the comparator used for building the list.
656 template <typename Q, typename Less>
657 bool contains( Q const& key, Less pred )
660 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
663 template <typename Q, typename Less>
664 CDS_DEPRECATED("deprecated, use contains()")
665 bool find_with( Q const& key, Less pred )
668 return contains( key, pred );
672 /// Finds the key \p key and performs an action with it
673 /** \anchor cds_nonintrusive_MichaelKVList_hp_find_func
674 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
675 The interface of \p Func functor is:
678 void operator()( value_type& item );
681 where \p item is the item found.
683 The functor may change <tt>item.second</tt> that is reference to value of node.
684 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
685 The function does not serialize simultaneous access to the list \p item. If such access is
686 possible you must provide your own synchronization schema to exclude unsafe item modifications.
688 The function returns \p true if \p key is found, \p false otherwise.
690 template <typename Q, typename Func>
691 bool find( Q const& key, Func f )
693 return find_at( head(), key, intrusive_key_comparator(), f );
696 /// Finds the key \p val using \p pred predicate for searching
698 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_find_func "find(Q&, Func)"
699 but \p pred is used for key comparing.
700 \p Less functor has the interface like \p std::less.
701 \p pred must imply the same element order as the comparator used for building the list.
703 template <typename Q, typename Less, typename Func>
704 bool find_with( Q const& key, Less pred, Func f )
707 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
710 /// Finds the \p key and return the item found
711 /** \anchor cds_nonintrusive_MichaelKVList_hp_get
712 The function searches the item with key equal to \p key
713 and returns it as \p guarded_ptr.
714 If \p key is not found the function returns an empty guarded pointer.
716 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
720 typedef cds::container::MichaelKVList< cds::gc::HP, int, foo, my_traits > ord_list;
724 ord_list::guarded_ptr gp(theList.get( 5 ));
729 // Destructor of guarded_ptr releases internal HP guard
733 Note the compare functor specified for class \p Traits template parameter
734 should accept a parameter of type \p K that can be not the same as \p key_type.
736 template <typename K>
737 guarded_ptr get( K const& key )
739 return get_at( head(), key, intrusive_key_comparator() );
742 /// Finds the \p key and return the item found
744 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_get "get( guarded_ptr& ptr, K const&)"
745 but \p pred is used for comparing the keys.
747 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
749 \p pred must imply the same element order as the comparator used for building the list.
751 template <typename K, typename Less>
752 guarded_ptr get_with( K const& key, Less pred )
755 return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
758 /// Checks if the list is empty
761 return base_class::empty();
764 /// Returns list's item count
766 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
767 this function always returns 0.
769 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
770 is empty. To check list emptyness use \p empty() method.
774 return base_class::size();
783 /// Returns const reference to internal statistics
784 stat const& statistics() const
786 return base_class::statistics();
791 bool insert_node_at( head_type& refHead, node_type * pNode )
793 assert( pNode != nullptr );
794 scoped_node_ptr p( pNode );
795 if ( base_class::insert_at( refHead, *pNode )) {
802 template <typename K>
803 bool insert_at( head_type& refHead, K&& key )
805 return insert_node_at( refHead, alloc_node( std::forward<K>( key )));
808 template <typename K, typename V>
809 bool insert_at( head_type& refHead, K&& key, V&& val )
811 return insert_node_at( refHead, alloc_node( std::forward<K>( key ), std::forward<V>( val )));
814 template <typename K, typename Func>
815 bool insert_with_at( head_type& refHead, K&& key, Func f )
817 scoped_node_ptr pNode( alloc_node( std::forward<K>( key )));
819 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
826 template <typename K, typename... Args>
827 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
829 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
832 template <typename K, typename Func>
833 std::pair<bool, bool> update_at( head_type& refHead, K&& key, Func f, bool bAllowInsert )
835 scoped_node_ptr pNode( alloc_node( std::forward<K>( key )));
837 std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
838 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); },
840 if ( ret.first && ret.second )
846 template <typename K, typename Compare>
847 bool erase_at( head_type& refHead, K const& key, Compare cmp )
849 return base_class::erase_at( refHead, key, cmp );
852 template <typename K, typename Compare, typename Func>
853 bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
855 return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
857 template <typename K, typename Compare>
858 guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp )
860 return base_class::extract_at( refHead, key, cmp );
863 template <typename K, typename Compare>
864 bool find_at( head_type& refHead, K const& key, Compare cmp )
866 return base_class::find_at( refHead, key, cmp );
869 template <typename K, typename Compare, typename Func>
870 bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
872 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
875 template <typename K, typename Compare>
876 guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp )
878 return base_class::get_at( refHead, key, cmp );
884 }} // namespace cds::container
886 #endif // #ifndef CDSLIB_CONTAINER_IMPL_MICHAEL_KVLIST_H