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_LAZY_KVLIST_RCU_H
32 #define CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H
35 #include <cds/container/details/lazy_list_base.h>
36 #include <cds/intrusive/lazy_list_rcu.h>
37 #include <cds/container/details/make_lazy_kvlist.h>
39 namespace cds { namespace container {
41 /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
42 /** @ingroup cds_nonintrusive_list
43 \anchor cds_nonintrusive_LazyKVList_rcu
45 This is key-value variation of non-intrusive \p %LazyList.
46 Like standard container, this implementation split a value stored into two part -
47 constant key and alterable value.
49 Usually, ordered single-linked list is used as a building block for the hash table implementation.
50 The complexity of searching is <tt>O(N)</tt>.
53 - \p RCU - one of \ref cds_urcu_gc "RCU type"
54 - \p Key - key type of an item to be stored in the list. It should be copy-constructible
55 - \p Value - value type to be stored in the list
56 - \p Traits - type traits, default is \p lazy_list::traits
57 It is possible to declare option-based list with \p lazy_list::make_traits metafunction istead of \p Traits template
58 argument. For example, the following traits-based declaration of \p gc::HP lazy list
60 #include <cds/urcu/general_threaded.h>
61 #include <cds/container/lazy_kvlist_rcu.h>
62 // Declare comparator for the item
64 int operator ()( int i1, int i2 )
71 struct my_traits: public cds::container::lazy_list::traits
73 typedef my_compare compare;
76 // Declare traits-based list
77 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits > traits_based_list;
79 is equal to the following option-based list
81 #include <cds/urcu/general_threaded.h>
82 #include <cds/container/lazy_kvlist_rcu.h>
84 // my_compare is the same
86 // Declare option-based list
87 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
88 typename cds::container::lazy_list::make_traits<
89 cds::container::opt::compare< my_compare > // item comparator option
94 @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
95 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
101 #ifdef CDS_DOXYGEN_INVOKED
102 typename Traits = lazy_list::traits
107 class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
108 #ifdef CDS_DOXYGEN_INVOKED
109 protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
111 protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
115 typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > maker;
116 typedef typename maker::type base_class;
120 typedef cds::urcu::gc<RCU> gc; ///< Garbage collector
121 #ifdef CDS_DOXYGEN_INVOKED
122 typedef Key key_type ; ///< Key type
123 typedef Value mapped_type ; ///< Type of value stored in the list
124 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
126 typedef typename maker::key_type key_type;
127 typedef typename maker::mapped_type mapped_type;
128 typedef typename maker::value_type value_type;
130 typedef typename base_class::back_off back_off; ///< Back-off strategy used
131 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
132 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
133 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
134 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
135 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
137 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
138 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
142 typedef typename base_class::value_type node_type;
143 typedef typename maker::cxx_allocator cxx_allocator;
144 typedef typename maker::node_deallocator node_deallocator;
145 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
147 typedef typename base_class::node_type head_type;
151 /// pointer to extracted node
152 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer,
153 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
155 /// Type of \p get() member function return value
156 typedef value_type * raw_ptr;
160 template <typename K>
161 static node_type * alloc_node(const K& key)
163 return cxx_allocator().New( key );
166 template <typename K, typename V>
167 static node_type * alloc_node( const K& key, const V& val )
169 return cxx_allocator().New( key, val );
172 template <typename... Args>
173 static node_type * alloc_node( Args&&... args )
175 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
178 static void free_node( node_type * pNode )
180 cxx_allocator().Delete( pNode );
183 struct node_disposer {
184 void operator()( node_type * pNode )
189 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
193 return base_class::m_Head;
196 head_type& head() const
198 return const_cast<head_type&>( base_class::m_Head );
203 return base_class::m_Tail;
206 head_type& tail() const
208 return const_cast<head_type&>( base_class::m_Tail );
215 template <bool IsConst>
216 class iterator_type: protected base_class::template iterator_type<IsConst>
218 typedef typename base_class::template iterator_type<IsConst> iterator_base;
220 iterator_type( head_type const& pNode )
221 : iterator_base( const_cast<head_type *>(&pNode) )
223 iterator_type( head_type const * pNode )
224 : iterator_base( const_cast<head_type *>(pNode) )
227 friend class LazyKVList;
230 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
231 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
233 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
234 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
239 iterator_type( iterator_type const& src )
240 : iterator_base( src )
243 key_type const& key() const
245 typename iterator_base::value_ptr p = iterator_base::operator ->();
246 assert( p != nullptr );
247 return p->m_Data.first;
250 value_ref val() const
252 typename iterator_base::value_ptr p = iterator_base::operator ->();
253 assert( p != nullptr );
254 return p->m_Data.second;
257 pair_ptr operator ->() const
259 typename iterator_base::value_ptr p = iterator_base::operator ->();
260 return p ? &(p->m_Data) : nullptr;
263 pair_ref operator *() const
265 typename iterator_base::value_ref p = iterator_base::operator *();
270 iterator_type& operator ++()
272 iterator_base::operator ++();
277 bool operator ==(iterator_type<C> const& i ) const
279 return iterator_base::operator ==(i);
282 bool operator !=(iterator_type<C> const& i ) const
284 return iterator_base::operator !=(i);
290 ///@name Forward iterators
294 You may safely use iterators in multi-threaded environment only under external RCU lock.
295 Otherwise, a program crash is possible if another thread deletes the item the iterator points to.
297 typedef iterator_type<false> iterator;
299 /// Const forward iterator
300 typedef iterator_type<true> const_iterator;
302 /// Returns a forward iterator addressing the first element in a list
304 For empty list \code begin() == end() \endcode
308 iterator it( head() );
309 ++it ; // skip dummy head
313 /// Returns an iterator that addresses the location succeeding the last element in a list
315 Do not use the value returned by <tt>end</tt> function to access any item.
316 Internally, <tt>end</tt> returning value pointing to dummy tail node.
318 The returned value can be used only to control reaching the end of the list.
319 For empty list \code begin() == end() \endcode
323 return iterator( tail() );
326 /// Returns a forward const iterator addressing the first element in a list
327 const_iterator begin() const
329 const_iterator it( head() );
330 ++it; // skip dummy head
334 /// Returns a forward const iterator addressing the first element in a list
335 const_iterator cbegin() const
337 const_iterator it( head() );
338 ++it; // skip dummy head
342 /// Returns an const iterator that addresses the location succeeding the last element in a list
343 const_iterator end() const
345 return const_iterator( tail());
348 /// Returns an const iterator that addresses the location succeeding the last element in a list
349 const_iterator cend() const
351 return const_iterator( tail());
356 /// Default constructor
360 /// Destructor clears the list
366 /// Inserts new node with key and default value
368 The function creates a node with \p key and default value, and then inserts the node created into the list.
371 - The \ref key_type should be constructible from value of type \p K.
372 In trivial case, \p K is equal to \p key_type.
373 - The \ref mapped_type should be default-constructible.
375 The function makes RCU lock internally.
377 Returns \p true if inserting successful, \p false otherwise.
379 template <typename K>
380 bool insert( const K& key )
382 return insert_at( head(), key );
385 /// Inserts new node with a key and a value
387 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
390 - The \p key_type should be constructible from \p key of type \p K.
391 - The \p mapped_type should be constructible from \p val of type \p V.
393 The function makes RCU lock internally.
395 Returns \p true if inserting successful, \p false otherwise.
397 template <typename K, typename V>
398 bool insert( const K& key, const V& val )
400 return insert_at( head(), key, val );
403 /// Inserts new node and initializes it by a functor
405 This function inserts new node with key \p key and if inserting is successful then it calls
406 \p func functor with signature
409 void operator()( value_type& item );
413 The argument \p item of user-defined functor \p func is the reference
414 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
415 The user-defined functor is called only if inserting is successful.
417 The key_type should be constructible from value of type \p K.
419 The function allows to split creating of new item into two part:
420 - create item from \p key;
421 - insert new item into the list;
422 - if inserting is successful, initialize the value of item by calling \p func functor
424 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
425 it is preferable that the initialization should be completed only if inserting is successful.
427 The function makes RCU lock internally.
429 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
431 template <typename K, typename Func>
432 bool insert_with( const K& key, Func func )
434 return insert_with_at( head(), key, func );
437 /// Inserts data of type \p mapped_type constructed from \p args
439 Returns \p true if inserting successful, \p false otherwise.
441 The function makes RCU lock internally.
443 template <typename... Args>
444 bool emplace( Args&&... args )
446 return emplace_at( head(), std::forward<Args>(args)... );
449 /// Updates data by \p key
451 The operation performs inserting or replacing the element with lock-free manner.
453 If the \p key not found in the list, then the new item created from \p key
454 will be inserted iff \p bAllowInsert is \p true.
455 (note that in this case the \ref key_type should be constructible from type \p K).
456 Otherwise, if \p key is found, the functor \p func is called with item found.
458 The functor \p Func signature is:
461 void operator()( bool bNew, value_type& item );
465 - \p bNew - \p true if the item has been inserted, \p false otherwise
466 - \p item - the item found or inserted
468 The functor may change any fields of the \p item.second of \p mapped_type;
469 during \p func call \p item is locked so it is safe to modify the item in
470 multi-threaded environment.
472 The function applies RCU lock internally.
474 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
475 \p second is true if new item has been added or \p false if the item with \p key
478 template <typename K, typename Func>
479 std::pair<bool, bool> update( const K& key, Func func, bool bAllowInsert = true )
481 return update_at( head(), key, func, bAllowInsert );
484 template <typename K, typename Func>
485 CDS_DEPRECATED("ensure() is deprecated, use update()")
486 std::pair<bool, bool> ensure( const K& key, Func f )
488 return update( key, f, true );
492 /// Deletes \p key from the list
493 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
495 RCU \p synchronize method can be called. RCU should not be locked.
497 Returns \p true if \p key is found and has been deleted, \p false otherwise
499 template <typename K>
500 bool erase( K const& key )
502 return erase_at( head(), key, intrusive_key_comparator() );
505 /// Deletes the item from the list using \p pred predicate for searching
507 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
508 but \p pred is used for key comparing.
509 \p Less functor has the interface like \p std::less.
510 \p pred must imply the same element order as the comparator used for building the list.
512 template <typename K, typename Less>
513 bool erase_with( K const& key, Less pred )
516 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
519 /// Deletes \p key from the list
520 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
521 The function searches an item with key \p key, calls \p f functor
522 and deletes the item. If \p key is not found, the functor is not called.
524 The functor \p Func interface:
527 void operator()(value_type& val) { ... }
531 RCU \p synchronize method can be called. RCU should not be locked.
533 Returns \p true if key is found and deleted, \p false otherwise
535 template <typename K, typename Func>
536 bool erase( K const& key, Func f )
538 return erase_at( head(), key, intrusive_key_comparator(), f );
541 /// Deletes the item from the list using \p pred predicate for searching
543 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
544 but \p pred is used for key comparing.
545 \p Less functor has the interface like \p std::less.
546 \p pred must imply the same element order as the comparator used for building the list.
548 template <typename K, typename Less, typename Func>
549 bool erase_with( K const& key, Less pred, Func f )
552 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
555 /// Extracts an item from the list
557 @anchor cds_nonintrusive_LazyKVList_rcu_extract
558 The function searches an item with key equal to \p key in the list,
559 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
560 If \p key is not found the function returns an empty \p exempt_ptr.
562 @note The function does NOT call RCU read-side lock or synchronization,
563 and does NOT dispose the item found. It just excludes the item from the list
564 and returns a pointer to item found.
565 You should manually lock RCU before calling this function.
568 #include <cds/urcu/general_buffered.h>
569 #include <cds/container/lazy_kvlist_rcu.h>
571 typedef cds::urcu::gc< general_buffered<> > rcu;
572 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
574 rcu_lazy_list theList;
577 rcu_lazy_list::exempt_ptr p;
579 // first, we should lock RCU
580 rcu_lazy_list::rcu_lock sl;
582 // Now, you can apply extract function
583 // Note that you must not delete the item found inside the RCU lock
584 p = theList.extract( 10 );
586 // do something with p
590 // Outside RCU lock section we may safely release extracted pointer.
591 // release() passes the pointer to RCU reclamation cycle.
595 template <typename K>
596 exempt_ptr extract( K const& key )
598 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator()));
601 /// Extracts an item from the list using \p pred predicate for searching
603 This function is the analog for \p extract(K const&).
604 The \p pred is a predicate used for key comparing.
605 \p Less has the interface like \p std::less.
606 \p pred must imply the same element order as \ref key_comparator.
608 template <typename K, typename Less>
609 exempt_ptr extract_with( K const& key, Less pred )
612 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
615 /// Checks whether the list contains \p key
617 The function searches the item with key equal to \p key
618 and returns \p true if it is found, and \p false otherwise.
620 The function applies RCU lock internally.
622 template <typename Q>
623 bool contains( Q const& key ) const
625 return find_at( head(), key, intrusive_key_comparator() );
628 template <typename Q>
629 CDS_DEPRECATED("deprecated, use contains()")
630 bool find( Q const& key ) const
632 return contains( key );
636 /// Checks whether the map contains \p key using \p pred predicate for searching
638 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
639 \p Less functor has the interface like \p std::less.
640 \p Less must imply the same element order as the comparator used for building the list.
642 The function applies RCU lock internally.
644 template <typename Q, typename Less>
645 bool contains( Q const& key, Less pred ) const
648 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
651 template <typename Q, typename Less>
652 CDS_DEPRECATED("deprecated, use contains()")
653 bool find_with( Q const& key, Less pred ) const
655 return contains( key, pred );
659 /// Finds the key \p key and performs an action with it
660 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
661 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
662 The interface of \p Func functor is:
665 void operator()( value_type& item );
668 where \p item is the item found.
670 The functor may change <tt>item.second</tt> that is reference to value of node.
671 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
672 The function does not serialize simultaneous access to the list \p item. If such access is
673 possible you must provide your own synchronization schema to exclude unsafe item modifications.
675 The function applies RCU lock internally.
677 The function returns \p true if \p key is found, \p false otherwise.
679 template <typename Q, typename Func>
680 bool find( Q const& key, Func f ) const
682 return find_at( head(), key, intrusive_key_comparator(), f );
685 /// Finds the key \p val using \p pred predicate for searching
687 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
688 but \p pred is used for key comparing.
689 \p Less functor has the interface like \p std::less.
690 \p pred must imply the same element order as the comparator used for building the list.
692 template <typename Q, typename Less, typename Func>
693 bool find_with( Q const& key, Less pred, Func f ) const
696 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
699 /// Finds \p key and return the item found
700 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
701 The function searches the item with \p key and returns the pointer to item found.
702 If \p key is not found it returns \p nullptr.
704 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
706 RCU should be locked before call of this function.
707 Returned item is valid only while RCU is locked:
709 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
714 ord_list::rcu_lock lock;
716 ord_list::value_type * pVal = theList.get( 5 );
721 // Unlock RCU by rcu_lock destructor
722 // pVal can be freed at any time after RCU has been unlocked
726 template <typename K>
727 value_type * get( K const& key ) const
729 return get_at( head(), key, intrusive_key_comparator());
732 /// Finds \p key and return the item found
734 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
735 but \p pred is used for comparing the keys.
737 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
739 \p pred must imply the same element order as the comparator used for building the list.
741 template <typename K, typename Less>
742 value_type * get_with( K const& key, Less pred ) const
745 return get_at( head(), key, typename maker::template less_wrapper<Less>::type());
748 /// Checks if the list is empty
751 return base_class::empty();
754 /// Returns list's item count
756 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
757 this function always returns 0.
759 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
760 is empty. To check list emptyness use \ref empty() method.
764 return base_class::size();
775 bool insert_node_at( head_type& refHead, node_type * pNode )
777 assert( pNode != nullptr );
778 scoped_node_ptr p( pNode );
780 if ( base_class::insert_at( &refHead, *p )) {
788 template <typename K>
789 bool insert_at( head_type& refHead, const K& key )
791 return insert_node_at( refHead, alloc_node( key ));
794 template <typename K, typename V>
795 bool insert_at( head_type& refHead, const K& key, const V& val )
797 return insert_node_at( refHead, alloc_node( key, val ));
800 template <typename K, typename Func>
801 bool insert_with_at( head_type& refHead, const K& key, Func f )
803 scoped_node_ptr pNode( alloc_node( key ));
805 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
812 template <typename... Args>
813 bool emplace_at( head_type& refHead, Args&&... args )
815 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
818 template <typename K, typename Compare>
819 bool erase_at( head_type& refHead, K const& key, Compare cmp )
821 return base_class::erase_at( &refHead, key, cmp );
824 template <typename K, typename Compare, typename Func>
825 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
827 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
830 template <typename K, typename Func>
831 std::pair<bool, bool> update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert )
833 scoped_node_ptr pNode( alloc_node( key ));
835 std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
836 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); },
838 if ( ret.first && ret.second )
844 template <typename K, typename Compare>
845 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
847 return base_class::extract_at( &refHead, key, cmp );
850 template <typename K, typename Compare>
851 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
853 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
856 template <typename K, typename Compare, typename Func>
857 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
859 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
862 template <typename K, typename Compare>
863 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
865 node_type * pNode = base_class::get_at( &refHead, val, cmp );
866 return pNode ? &pNode->m_Data : nullptr;
872 }} // namespace cds::container
874 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H