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_MICHAEL_KVLIST_RCU_H
32 #define CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H
35 #include <functional> // ref
36 #include <cds/container/details/michael_list_base.h>
37 #include <cds/intrusive/michael_list_rcu.h>
38 #include <cds/container/details/make_michael_kvlist.h>
40 namespace cds { namespace container {
42 /// Michael's ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
43 /** @ingroup cds_nonintrusive_list
44 \anchor cds_nonintrusive_MichaelKVList_rcu
46 This is key-value variation of non-intrusive \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
47 Like standard container, this implementation split a value stored into two part -
48 constant key and alterable value.
50 Usually, ordered single-linked list is used as a building block for the hash table implementation.
51 The complexity of searching is <tt>O(N)</tt>.
54 - \p RCU - one of \ref cds_urcu_gc "RCU type"
55 - \p Key - key type of an item stored in the list. It should be copy-constructible
56 - \p Value - value type stored in a list
57 - \p Traits - type traits, default is \p michael_list::traits
59 @note Before including <tt><cds/container/michael_kvlist_rcu.h></tt> you should include appropriate RCU header file,
60 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
62 It is possible to declare option-based list using \p cds::container::michael_list::make_traits metafunction istead of \p Traits template
63 argument. For example, the following traits-based declaration of Michael's list
65 #include <cds/urcu/general_buffered.h>
66 #include <cds/container/michael_kvlist_rcu.h>
67 // Declare comparator for the item
69 int operator ()( int i1, int i2 )
76 struct my_traits: public cds::container::michael_list::traits
78 typedef my_compare compare;
81 // Declare traits-based list
82 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int, my_traits > traits_based_list;
85 is equivalent for the following option-based list
87 #include <cds/urcu/general_buffered.h>
88 #include <cds/container/michael_kvlist_rcu.h>
90 // my_compare is the same
92 // Declare option-based list
93 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int,
94 typename cds::container::michael_list::make_traits<
95 cds::container::opt::compare< my_compare > // item comparator option
104 #ifdef CDS_DOXYGEN_INVOKED
105 typename Traits = michael_list::traits
110 class MichaelKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
111 #ifdef CDS_DOXYGEN_INVOKED
112 protected intrusive::MichaelList< cds::urcu::gc<RCU>, implementation_defined, Traits >
114 protected details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
118 typedef details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > maker;
119 typedef typename maker::type base_class;
123 typedef cds::urcu::gc<RCU> gc; ///< Garbage collector
125 #ifdef CDS_DOXYGEN_INVOKED
126 typedef Key key_type; ///< Key type
127 typedef Value mapped_type; ///< Type of value stored in the list
128 typedef std::pair<key_type const, mapped_type> value_type; ///< key/value pair stored in the list
130 typedef typename maker::key_type key_type;
131 typedef typename maker::value_type mapped_type;
132 typedef typename maker::pair_type value_type;
134 typedef Traits traits; ///< List traits
136 typedef typename base_class::back_off back_off; ///< Back-off strategy
137 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
138 typedef typename base_class::item_counter item_counter; ///< Item counting policy
139 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
140 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p michael_list::traits::memory_model
141 typedef typename base_class::stat stat; ///< Internal statistics
142 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
144 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
145 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking
149 typedef typename base_class::value_type node_type;
150 typedef typename maker::cxx_allocator cxx_allocator;
151 typedef typename maker::node_deallocator node_deallocator;
152 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
154 typedef typename base_class::atomic_node_ptr head_type;
158 /// pointer to extracted node
159 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer,
160 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
165 struct raw_ptr_converter
167 value_type * operator()( node_type * p ) const
169 return p ? &p->m_Data : nullptr;
172 value_type& operator()( node_type& n ) const
177 value_type const& operator()( node_type const& n ) const
185 /// Result of \p get(), \p get_with() functions - pointer to the node found
186 typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr;
190 template <typename K>
191 static node_type * alloc_node(const K& key)
193 return cxx_allocator().New( key );
196 template <typename K, typename V>
197 static node_type * alloc_node( const K& key, const V& val )
199 return cxx_allocator().New( key, val );
202 template <typename K, typename... Args>
203 static node_type * alloc_node( K&& key, Args&&... args )
205 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
208 static void free_node( node_type * pNode )
210 cxx_allocator().Delete( pNode );
213 struct node_disposer {
214 void operator()( node_type * pNode )
219 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
223 return base_class::m_pHead;
226 head_type& head() const
228 return const_cast<head_type&>( base_class::m_pHead );
234 template <bool IsConst>
235 class iterator_type: protected base_class::template iterator_type<IsConst>
237 typedef typename base_class::template iterator_type<IsConst> iterator_base;
239 iterator_type( head_type const& pNode )
240 : iterator_base( pNode )
243 friend class MichaelKVList;
246 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
247 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
249 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
250 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
255 iterator_type( iterator_type const& src )
256 : iterator_base( src )
259 key_type const& key() const
261 typename iterator_base::value_ptr p = iterator_base::operator ->();
262 assert( p != nullptr );
263 return p->m_Data.first;
266 pair_ptr operator ->() const
268 typename iterator_base::value_ptr p = iterator_base::operator ->();
269 return p ? &(p->m_Data) : nullptr;
272 pair_ref operator *() const
274 typename iterator_base::value_ref p = iterator_base::operator *();
278 value_ref val() const
280 typename iterator_base::value_ptr p = iterator_base::operator ->();
281 assert( p != nullptr );
282 return p->m_Data.second;
286 iterator_type& operator ++()
288 iterator_base::operator ++();
293 bool operator ==(iterator_type<C> const& i ) const
295 return iterator_base::operator ==(i);
298 bool operator !=(iterator_type<C> const& i ) const
300 return iterator_base::operator !=(i);
306 ///@name Forward iterators
310 You may safely use iterators in multi-threaded environment only under external RCU lock.
311 Otherwise, a program crash is possible if another thread deletes the item the iterator points to.
313 typedef iterator_type<false> iterator;
315 /// Const forward iterator
316 typedef iterator_type<true> const_iterator;
318 /// Returns a forward iterator addressing the first element in a list
320 For empty list \code begin() == end() \endcode
324 return iterator( head() );
327 /// Returns an iterator that addresses the location succeeding the last element in a list
329 Do not use the value returned by <tt>end</tt> function to access any item.
330 Internally, <tt>end</tt> returning value equals to \p nullptr.
332 The returned value can be used only to control reaching the end of the list.
333 For empty list \code begin() == end() \endcode
340 /// Returns a forward const iterator addressing the first element in a list
341 const_iterator begin() const
343 return const_iterator( head() );
345 /// Returns a forward const iterator addressing the first element in a list
346 const_iterator cbegin() const
348 return const_iterator( head() );
351 /// Returns an const iterator that addresses the location succeeding the last element in a list
352 const_iterator end() const
354 return const_iterator();
356 /// Returns an const iterator that addresses the location succeeding the last element in a list
357 const_iterator cend() const
359 return const_iterator();
364 /// Default constructor
366 Initializes empty list
372 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
373 explicit MichaelKVList( Stat& st )
387 /// Inserts new node with key and default value
389 The function creates a node with \p key and default value, and then inserts the node created into the list.
392 - The \ref key_type should be constructible from value of type \p K.
393 In trivial case, \p K is equal to \ref key_type.
394 - The \ref mapped_type should be default-constructible.
396 The function applies RCU lock internally.
398 Returns \p true if inserting successful, \p false otherwise.
400 template <typename K>
401 bool insert( const K& key )
403 return insert_at( head(), key );
406 /// Inserts new node with a key and a value
408 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
411 - The \ref key_type should be constructible from \p key of type \p K.
412 - The \ref mapped_type should be constructible from \p val of type \p V.
414 The function applies RCU lock internally.
416 Returns \p true if inserting successful, \p false otherwise.
418 template <typename K, typename V>
419 bool insert( const K& key, const V& val )
421 return insert_at( head(), key, val );
424 /// Inserts new node and initialize it by a functor
426 This function inserts new node with key \p key and if inserting is successful then it calls
427 \p func functor with signature
430 void operator()( value_type& item );
434 The argument \p item of user-defined functor \p func is the reference
435 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
436 User-defined functor \p func should guarantee that during changing item's value no any other changes
437 could be made on this list's item by concurrent threads.
439 The key_type should be constructible from value of type \p K.
441 The function allows to split creating of new item into two part:
442 - create item from \p key;
443 - insert new item into the list;
444 - if inserting is successful, initialize the value of item by calling \p func functor
446 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
447 it is preferable that the initialization should be completed only if inserting is successful.
449 The function applies RCU lock internally.
451 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
453 template <typename K, typename Func>
454 bool insert_with( const K& key, Func func )
456 return insert_with_at( head(), key, func );
459 /// Updates an element with given \p key
461 The operation performs inserting or changing data with lock-free manner.
463 If the \p key not found in the list, then the new item created from \p key
464 is inserted into the list (note that in this case the \ref key_type should be
465 copy-constructible from type \p K).
466 Otherwise, the functor \p func is called with item found.
467 The functor \p Func may be a function with signature:
469 void func( bool bNew, value_type& item );
474 void operator()( bool bNew, value_type& item );
479 - \p bNew - \p true if the item has been inserted, \p false otherwise
480 - \p item - item of the list
482 The functor may change any fields of the \p item.second that is \ref mapped_type;
483 however, \p func must guarantee that during changing no any other modifications
484 could be made on this item by concurrent threads.
486 The function applies RCU lock internally.
488 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
489 \p second is true if new item has been added or \p false if the item with \p key
490 already is in the list.
492 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
494 /// Updates data by \p key
496 The operation performs inserting or replacing the element with lock-free manner.
498 If the \p key not found in the list, then the new item created from \p key
499 will be inserted iff \p bAllowInsert is \p true.
500 (note that in this case the \ref key_type should be constructible from type \p K).
501 Otherwise, if \p key is found, the functor \p func is called with item found.
503 The functor \p Func signature is:
506 void operator()( bool bNew, value_type& item );
510 - \p bNew - \p true if the item has been inserted, \p false otherwise
511 - \p item - the item found or inserted
513 The functor may change any fields of the \p item.second that is \ref mapped_type;
514 however, \p func must guarantee that during changing no any other modifications
515 could be made on this item by concurrent threads.
517 The function applies RCU lock internally.
519 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
520 \p second is true if new item has been added or \p false if the item with \p key
523 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
525 template <typename K, typename Func>
526 std::pair<bool, bool> update( const K& key, Func func, bool bAllowInsert = true )
528 return update_at( head(), key, func, bAllowInsert );
531 template <typename K, typename Func>
532 CDS_DEPRECATED("ensure() is deprecated, use update()")
533 std::pair<bool, bool> ensure( const K& key, Func f )
535 return update( key, f, true );
539 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
541 Returns \p true if inserting successful, \p false otherwise.
543 The function applies RCU lock internally.
545 template <typename K, typename... Args>
546 bool emplace( K&& key, Args&&... args )
548 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
551 /// Deletes \p key from the list
552 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase
554 RCU \p synchronize method can be called. RCU should not be locked.
556 Returns \p true if \p key is found and has been deleted, \p false otherwise
558 template <typename K>
559 bool erase( K const& key )
561 return erase_at( head(), key, intrusive_key_comparator() );
564 /// Deletes the item from the list using \p pred predicate for searching
566 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase "erase(K const&)"
567 but \p pred is used for key comparing.
568 \p Less functor has the interface like \p std::less.
569 \p pred must imply the same element order as the comparator used for building the list.
571 template <typename K, typename Less>
572 bool erase_with( K const& key, Less pred )
575 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
578 /// Deletes \p key from the list
579 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase_func
580 The function searches an item with key \p key, calls \p f functor
581 and deletes the item. If \p key is not found, the functor is not called.
583 The functor \p Func interface:
586 void operator()(value_type& val) { ... }
590 RCU \p synchronize method can be called. RCU should not be locked.
592 Return \p true if key is found and deleted, \p false otherwise
596 template <typename K, typename Func>
597 bool erase( K const& key, Func f )
599 return erase_at( head(), key, intrusive_key_comparator(), f );
602 /// Deletes the item from the list using \p pred predicate for searching
604 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase_func "erase(K const&, Func)"
605 but \p pred is used for key comparing.
606 \p Less functor has the interface like \p std::less.
607 \p pred must imply the same element order as the comparator used for building the list.
609 template <typename K, typename Less, typename Func>
610 bool erase_with( K const& key, Less pred, Func f )
613 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
616 /// Extracts an item from the list
618 @anchor cds_nonintrusive_MichaelKVList_rcu_extract
619 The function searches an item with key equal to \p key in the list,
620 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
621 If \p key is not found the function returns an empty \p exempt_ptr.
623 @note The function does NOT dispose the item found.
624 It just excludes the item from the list and returns a pointer to item found.
625 You shouldn't lock RCU before calling this function.
628 #include <cds/urcu/general_buffered.h>
629 #include <cds/container/michael_kvlist_rcu.h>
631 typedef cds::urcu::gc< general_buffered<> > rcu;
632 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
634 rcu_michael_list theList;
637 rcu_michael_list::exempt_ptr p;
639 // The RCU should NOT be locked when extract() is called!
640 assert( !rcu::is_locked() );
643 p = theList.extract( 10 );
645 // do something with p
649 // we may safely release extracted pointer here.
650 // release() passes the pointer to RCU reclamation cycle.
654 template <typename K>
655 exempt_ptr extract( K const& key )
657 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator() ));
660 /// Extracts an item from the list using \p pred predicate for searching
662 This function is the analog for \p extract(K const&).
663 The \p pred is a predicate used for key comparing.
664 \p Less has the interface like \p std::less.
665 \p pred must imply the same element order as \ref key_comparator.
667 template <typename K, typename Less>
668 exempt_ptr extract_with( K const& key, Less pred )
671 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
674 /// Checks whether the list contains \p key
676 The function searches the item with key equal to \p key
677 and returns \p true if it is found, and \p false otherwise.
679 The function applies RCU lock internally.
681 template <typename Q>
682 bool contains( Q const& key )
684 return find_at( head(), key, intrusive_key_comparator() );
687 template <typename Q>
688 CDS_DEPRECATED("deprecated, use contains()")
689 bool find( Q const& key )
691 return contains( key );
695 /// Checks whether the map contains \p key using \p pred predicate for searching
697 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
698 \p Less functor has the interface like \p std::less.
699 \p Less must imply the same element order as the comparator used for building the list.
701 The function applies RCU lock internally.
703 template <typename Q, typename Less>
704 bool contains( Q const& key, Less pred )
707 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
710 template <typename Q, typename Less>
711 CDS_DEPRECATED("deprecated, use contains()")
712 bool find_with( Q const& key, Less pred )
714 return contains( key, pred );
718 /// Finds \p key and performs an action with it
719 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_func
720 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
721 The interface of \p Func functor is:
724 void operator()( value_type& item );
727 where \p item is the item found.
729 The functor may change <tt>item.second</tt> that is reference to value of node.
730 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
731 The function does not serialize simultaneous access to the list \p item. If such access is
732 possible you must provide your own synchronization schema to exclude unsafe item modifications.
734 The function makes RCU lock internally.
736 The function returns \p true if \p key is found, \p false otherwise.
738 template <typename Q, typename Func>
739 bool find( Q const& key, Func f )
741 return find_at( head(), key, intrusive_key_comparator(), f );
744 /// Finds the key \p val using \p pred predicate for searching
746 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_func "find(Q const&, Func)"
747 but \p pred is used for key comparing.
748 \p Less functor has the interface like \p std::less.
749 \p pred must imply the same element order as the comparator used for building the list.
751 template <typename Q, typename Less, typename Func>
752 bool find_with( Q const& key, Less pred, Func f )
755 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
758 /// Finds \p key and return the item found
759 /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
760 The function searches the item with \p key and returns the pointer to item found.
761 If \p key is not found it returns an empty \p raw_ptr object.
763 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
765 RCU should be locked before call of this function.
766 Returned item is valid only while RCU is locked:
768 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
771 tyename ord_list::raw_ptr rp;
774 ord_list::rcu_lock lock;
776 rp = theList.get( 5 );
781 // Unlock RCU by rcu_lock destructor
783 // rp can be released at any time after RCU has been unlocked
787 template <typename K>
788 raw_ptr get( K const& key )
790 return get_at( head(), key, intrusive_key_comparator());
793 /// Finds \p key and return the item found
795 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_get "get(K const&)"
796 but \p pred is used for comparing the keys.
798 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
800 \p pred must imply the same element order as the comparator used for building the list.
802 template <typename K, typename Less>
803 raw_ptr get_with( K const& key, Less pred )
806 return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
809 /// Checks if the list is empty
812 return base_class::empty();
815 /// Returns list's item count
817 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
818 this function always returns 0.
820 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
821 is empty. To check list emptyness use \p empty() method.
825 return base_class::size();
828 /// Returns const reference to internal statistics
829 stat const& statistics() const
831 return base_class::statistics();
836 Post-condition: the list is empty
845 bool insert_node_at( head_type& refHead, node_type * pNode )
847 assert( pNode != nullptr );
848 scoped_node_ptr p( pNode );
849 if ( base_class::insert_at( refHead, *pNode )) {
856 template <typename K>
857 bool insert_at( head_type& refHead, const K& key )
859 return insert_node_at( refHead, alloc_node( key ));
862 template <typename K, typename V>
863 bool insert_at( head_type& refHead, const K& key, const V& val )
865 return insert_node_at( refHead, alloc_node( key, val ));
868 template <typename K, typename Func>
869 bool insert_with_at( head_type& refHead, const K& key, Func f )
871 scoped_node_ptr pNode( alloc_node( key ));
873 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
880 template <typename K, typename... Args>
881 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
883 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
886 template <typename K, typename Func>
887 std::pair<bool, bool> update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert )
889 scoped_node_ptr pNode( alloc_node( key ));
891 std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
892 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); },
894 if ( ret.first && ret.second )
900 template <typename K, typename Compare>
901 bool erase_at( head_type& refHead, K const& key, Compare cmp )
903 return base_class::erase_at( refHead, key, cmp );
906 template <typename K, typename Compare, typename Func>
907 bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
909 return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
912 template <typename K, typename Compare>
913 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
915 return base_class::extract_at( refHead, key, cmp );
918 template <typename K, typename Compare>
919 bool find_at( head_type& refHead, K const& key, Compare cmp )
921 return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
924 template <typename K, typename Compare, typename Func>
925 bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
927 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
930 template <typename K, typename Compare>
931 raw_ptr get_at( head_type& refHead, K const& val, Compare cmp )
933 return raw_ptr( base_class::get_at( refHead, val, cmp ));
939 }} // namespace cds::container
941 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H