3 #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H
4 #define __CDS_CONTAINER_LAZY_KVLIST_RCU_H
7 #include <functional> // ref
8 #include <cds/container/details/lazy_list_base.h>
9 #include <cds/intrusive/lazy_list_rcu.h>
10 #include <cds/container/details/make_lazy_kvlist.h>
12 namespace cds { namespace container {
14 /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
15 /** @ingroup cds_nonintrusive_list
16 \anchor cds_nonintrusive_LazyKVList_rcu
18 This is key-value variation of non-intrusive LazyList.
19 Like standard container, this implementation split a value stored into two part -
20 constant key and alterable value.
22 Usually, ordered single-linked list is used as a building block for the hash table implementation.
23 The complexity of searching is <tt>O(N)</tt>.
26 - \p RCU - one of \ref cds_urcu_gc "RCU type"
27 - \p Key - key type of an item stored in the list. It should be copy-constructible
28 - \p Value - value type stored in the list
29 - \p Traits - type traits, default is lazy_list::type_traits
31 It is possible to declare option-based list with cds::container::lazy_list::make_traits metafunction istead of \p Traits template
32 argument. For example, the following traits-based declaration of gc::HP lazy list
33 @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
34 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
36 #include <cds/urcu/general_threaded.h>
37 #include <cds/container/lazy_kvlist_rcu.h>
38 // Declare comparator for the item
40 int operator ()( int i1, int i2 )
46 // Declare type_traits
47 struct my_traits: public cds::container::lazy_list::type_traits
49 typedef my_compare compare;
52 // Declare traits-based list
53 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits > traits_based_list;
56 is equivalent for the following option-based list
58 #include <cds/urcu/general_threaded.h>
59 #include <cds/container/lazy_kvlist_rcu.h>
61 // my_compare is the same
63 // Declare option-based list
64 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
65 typename cds::container::lazy_list::make_traits<
66 cds::container::opt::compare< my_compare > // item comparator option
71 Template argument list \p Options of cds::container::lazy_list::make_traits metafunction are:
72 - opt::compare - key comparison functor. No default functor is provided.
73 If the option is not specified, the opt::less is used.
74 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
75 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
76 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
77 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
78 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
79 or opt::v::sequential_consistent (sequentially consisnent memory model).
80 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
86 #ifdef CDS_DOXYGEN_INVOKED
87 typename Traits = lazy_list::type_traits
92 class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
93 #ifdef CDS_DOXYGEN_INVOKED
94 protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
96 protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
100 typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
101 typedef typename options::type base_class;
105 #ifdef CDS_DOXYGEN_INVOKED
106 typedef Key key_type ; ///< Key type
107 typedef Value mapped_type ; ///< Type of value stored in the list
108 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
110 typedef typename options::key_type key_type;
111 typedef typename options::value_type mapped_type;
112 typedef typename options::pair_type value_type;
115 typedef typename base_class::gc gc ; ///< Garbage collector used
116 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
117 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
118 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
119 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
120 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
121 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
123 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
124 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
128 typedef typename base_class::value_type node_type;
129 typedef typename options::cxx_allocator cxx_allocator;
130 typedef typename options::node_deallocator node_deallocator;
131 typedef typename options::type_traits::compare intrusive_key_comparator;
133 typedef typename base_class::node_type head_type;
137 /// pointer to extracted node
138 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
139 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
144 template <typename K>
145 static node_type * alloc_node(const K& key)
147 return cxx_allocator().New( key );
150 template <typename K, typename V>
151 static node_type * alloc_node( const K& key, const V& val )
153 return cxx_allocator().New( key, val );
156 template <typename... Args>
157 static node_type * alloc_node( Args&&... args )
159 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
162 static void free_node( node_type * pNode )
164 cxx_allocator().Delete( pNode );
167 struct node_disposer {
168 void operator()( node_type * pNode )
173 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
177 return base_class::m_Head;
180 head_type& head() const
182 return const_cast<head_type&>( base_class::m_Head );
187 return base_class::m_Tail;
190 head_type& tail() const
192 return const_cast<head_type&>( base_class::m_Tail );
199 template <bool IsConst>
200 class iterator_type: protected base_class::template iterator_type<IsConst>
202 typedef typename base_class::template iterator_type<IsConst> iterator_base;
204 iterator_type( head_type const& pNode )
205 : iterator_base( const_cast<head_type *>(&pNode) )
207 iterator_type( head_type const * pNode )
208 : iterator_base( const_cast<head_type *>(pNode) )
211 friend class LazyKVList;
214 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
215 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
217 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
218 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
223 iterator_type( iterator_type const& src )
224 : iterator_base( src )
227 key_type const& key() const
229 typename iterator_base::value_ptr p = iterator_base::operator ->();
230 assert( p != nullptr );
231 return p->m_Data.first;
234 value_ref val() const
236 typename iterator_base::value_ptr p = iterator_base::operator ->();
237 assert( p != nullptr );
238 return p->m_Data.second;
241 pair_ptr operator ->() const
243 typename iterator_base::value_ptr p = iterator_base::operator ->();
244 return p ? &(p->m_Data) : nullptr;
247 pair_ref operator *() const
249 typename iterator_base::value_ref p = iterator_base::operator *();
254 iterator_type& operator ++()
256 iterator_base::operator ++();
261 bool operator ==(iterator_type<C> const& i ) const
263 return iterator_base::operator ==(i);
266 bool operator !=(iterator_type<C> const& i ) const
268 return iterator_base::operator !=(i);
275 typedef iterator_type<false> iterator;
277 /// Const forward iterator
278 typedef iterator_type<true> const_iterator;
280 /// Returns a forward iterator addressing the first element in a list
282 For empty list \code begin() == end() \endcode
286 iterator it( head() );
287 ++it ; // skip dummy head
291 /// Returns an iterator that addresses the location succeeding the last element in a list
293 Do not use the value returned by <tt>end</tt> function to access any item.
294 Internally, <tt>end</tt> returning value pointing to dummy tail node.
296 The returned value can be used only to control reaching the end of the list.
297 For empty list \code begin() == end() \endcode
301 return iterator( tail() );
304 /// Returns a forward const iterator addressing the first element in a list
306 const_iterator begin() const
308 const_iterator it( head() );
309 ++it; // skip dummy head
312 const_iterator cbegin()
314 const_iterator it( head() );
315 ++it; // skip dummy head
320 /// Returns an const iterator that addresses the location succeeding the last element in a list
322 const_iterator end() const
324 return const_iterator( tail());
326 const_iterator cend()
328 return const_iterator( tail());
333 /// Default constructor
335 Initializes empty list
349 /// Inserts new node with key and default value
351 The function creates a node with \p key and default value, and then inserts the node created into the list.
354 - The \ref key_type should be constructible from value of type \p K.
355 In trivial case, \p K is equal to \ref key_type.
356 - The \ref mapped_type should be default-constructible.
358 The function makes RCU lock internally.
360 Returns \p true if inserting successful, \p false otherwise.
362 template <typename K>
363 bool insert( const K& key )
365 return insert_at( head(), key );
368 /// Inserts new node with a key and a value
370 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
373 - The \ref key_type should be constructible from \p key of type \p K.
374 - The \ref mapped_type should be constructible from \p val of type \p V.
376 The function makes RCU lock internally.
378 Returns \p true if inserting successful, \p false otherwise.
380 template <typename K, typename V>
381 bool insert( const K& key, const V& val )
383 return insert_at( head(), key, val );
386 /// Inserts new node and initializes it by a functor
388 This function inserts new node with key \p key and if inserting is successful then it calls
389 \p func functor with signature
392 void operator()( value_type& item );
396 The argument \p item of user-defined functor \p func is the reference
397 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
398 User-defined functor \p func should guarantee that during changing item's value no any other changes
399 could be made on this list's item by concurrent threads.
400 The user-defined functor can be passed by reference using \p std::ref
401 and it is called only if inserting is successful.
403 The key_type should be constructible from value of type \p K.
405 The function allows to split creating of new item into two part:
406 - create item from \p key;
407 - insert new item into the list;
408 - if inserting is successful, initialize the value of item by calling \p func functor
410 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
411 it is preferable that the initialization should be completed only if inserting is successful.
413 The function makes RCU lock internally.
415 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
417 template <typename K, typename Func>
418 bool insert_key( const K& key, Func func )
420 return insert_key_at( head(), key, func );
423 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
425 Returns \p true if inserting successful, \p false otherwise.
427 The function makes RCU lock internally.
429 template <typename... Args>
430 bool emplace( Args&&... args )
432 return emplace_at( head(), std::forward<Args>(args)... );
435 /// Ensures that the \p key exists in the list
437 The operation performs inserting or changing data with lock-free manner.
439 If the \p key not found in the list, then the new item created from \p key
440 is inserted into the list (note that in this case the \ref key_type should be
441 copy-constructible from type \p K).
442 Otherwise, the functor \p func is called with item found.
443 The functor \p Func may be a function with signature:
445 void func( bool bNew, value_type& item );
450 void operator()( bool bNew, value_type& item );
455 - \p bNew - \p true if the item has been inserted, \p false otherwise
456 - \p item - item of the list
458 The functor may change any fields of the \p item.second that is \ref mapped_type;
459 however, \p func must guarantee that during changing no any other modifications
460 could be made on this item by concurrent threads.
462 The function makes RCU lock internally.
464 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
465 \p second is true if new item has been added or \p false if the item with \p key
466 already is in the list.
468 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
470 template <typename K, typename Func>
471 std::pair<bool, bool> ensure( const K& key, Func f )
473 return ensure_at( head(), key, f );
476 /// Deletes \p key from the list
477 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
479 RCU \p synchronize method can be called. RCU should not be locked.
481 Returns \p true if \p key is found and has been deleted, \p false otherwise
483 template <typename K>
484 bool erase( K const& key )
486 return erase_at( head(), key, intrusive_key_comparator() );
489 /// Deletes the item from the list using \p pred predicate for searching
491 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
492 but \p pred is used for key comparing.
493 \p Less functor has the interface like \p std::less.
494 \p pred must imply the same element order as the comparator used for building the list.
496 template <typename K, typename Less>
497 bool erase_with( K const& key, Less pred )
499 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
502 /// Deletes \p key from the list
503 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
504 The function searches an item with key \p key, calls \p f functor
505 and deletes the item. If \p key is not found, the functor is not called.
507 The functor \p Func interface:
510 void operator()(value_type& val) { ... }
513 The functor may be passed by reference with <tt>boost:ref</tt>
515 RCU \p synchronize method can be called. RCU should not be locked.
517 Returns \p true if key is found and deleted, \p false otherwise
519 template <typename K, typename Func>
520 bool erase( K const& key, Func f )
522 return erase_at( head(), key, intrusive_key_comparator(), f );
525 /// Deletes the item from the list using \p pred predicate for searching
527 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
528 but \p pred is used for key comparing.
529 \p Less functor has the interface like \p std::less.
530 \p pred must imply the same element order as the comparator used for building the list.
532 template <typename K, typename Less, typename Func>
533 bool erase_with( K const& key, Less pred, Func f )
535 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
538 /// Extracts an item from the list
540 @anchor cds_nonintrusive_LazyKVList_rcu_extract
541 The function searches an item with key equal to \p key in the list,
542 unlinks it from the list, and returns pointer to an item found in \p dest argument.
543 If \p key is not found the function returns \p false.
545 @note The function does NOT call RCU read-side lock or synchronization,
546 and does NOT dispose the item found. It just excludes the item from the list
547 and returns a pointer to item found.
548 You should lock RCU before calling this function.
551 #include <cds/urcu/general_buffered.h>
552 #include <cds/container/lazy_kvlist_rcu.h>
554 typedef cds::urcu::gc< general_buffered<> > rcu;
555 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
557 rcu_lazy_list theList;
560 rcu_lazy_list::exempt_ptr p;
562 // first, we should lock RCU
563 rcu_lazy_list::rcu_lock sl;
565 // Now, you can apply extract function
566 // Note that you must not delete the item found inside the RCU lock
567 if ( theList.extract( p, 10 )) {
568 // do something with p
572 // Outside RCU lock section we may safely release extracted pointer.
573 // release() passes the pointer to RCU reclamation cycle.
577 template <typename K>
578 bool extract( exempt_ptr& dest, K const& key )
580 dest = extract_at( head(), key, intrusive_key_comparator() );
581 return !dest.empty();
584 /// Extracts an item from the list using \p pred predicate for searching
586 This function is the analog for \ref cds_nonintrusive_LazyKVList_rcu_extract "extract(exempt_ptr&, K const&)".
587 The \p pred is a predicate used for key comparing.
588 \p Less has the interface like \p std::less.
589 \p pred must imply the same element order as \ref key_comparator.
591 template <typename K, typename Less>
592 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
594 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
595 return !dest.empty();
598 /// Finds the key \p key
599 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
600 The function searches the item with key equal to \p key
601 and returns \p true if it is found, and \p false otherwise
603 The function applies RCU lock internally.
605 template <typename Q>
606 bool find( Q const& key ) const
608 return find_at( head(), key, intrusive_key_comparator() );
611 /// Finds the key \p val using \p pred predicate for searching
613 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
614 but \p pred is used for key comparing.
615 \p Less functor has the interface like \p std::less.
616 \p pred must imply the same element order as the comparator used for building the list.
618 template <typename Q, typename Less>
619 bool find_with( Q const& key, Less pred ) const
621 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
624 /// Finds the key \p key and performs an action with it
625 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
626 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
627 The interface of \p Func functor is:
630 void operator()( value_type& item );
633 where \p item is the item found.
635 You may pass \p f argument by reference using \p std::ref.
637 The functor may change <tt>item.second</tt> that is reference to value of node.
638 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
639 The function does not serialize simultaneous access to the list \p item. If such access is
640 possible you must provide your own synchronization schema to exclude unsafe item modifications.
642 The function applies RCU lock internally.
644 The function returns \p true if \p key is found, \p false otherwise.
646 template <typename Q, typename Func>
647 bool find( Q const& key, Func f ) const
649 return find_at( head(), key, intrusive_key_comparator(), f );
652 /// Finds the key \p val using \p pred predicate for searching
654 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
655 but \p pred is used for key comparing.
656 \p Less functor has the interface like \p std::less.
657 \p pred must imply the same element order as the comparator used for building the list.
659 template <typename Q, typename Less, typename Func>
660 bool find_with( Q const& key, Less pred, Func f ) const
662 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
665 /// Finds \p key and return the item found
666 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
667 The function searches the item with \p key and returns the pointer to item found.
668 If \p key is not found it returns \p nullptr.
670 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
672 RCU should be locked before call of this function.
673 Returned item is valid only while RCU is locked:
675 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
680 ord_list::rcu_lock lock;
682 ord_list::value_type * pVal = theList.get( 5 );
687 // Unlock RCU by rcu_lock destructor
688 // pVal can be freed at any time after RCU has been unlocked
692 template <typename K>
693 value_type * get( K const& key ) const
695 return get_at( head(), key, intrusive_key_comparator());
698 /// Finds \p key and return the item found
700 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
701 but \p pred is used for comparing the keys.
703 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
705 \p pred must imply the same element order as the comparator used for building the list.
707 template <typename K, typename Less>
708 value_type * get_with( K const& key, Less pred ) const
710 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
713 /// Checks if the list is empty
716 return base_class::empty();
719 /// Returns list's item count
721 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
722 this function always returns 0.
724 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
725 is empty. To check list emptyness use \ref empty() method.
729 return base_class::size();
734 Post-condition: the list is empty
743 bool insert_node_at( head_type& refHead, node_type * pNode )
745 assert( pNode != nullptr );
746 scoped_node_ptr p( pNode );
748 if ( base_class::insert_at( &refHead, *p )) {
756 template <typename K>
757 bool insert_at( head_type& refHead, const K& key )
759 return insert_node_at( refHead, alloc_node( key ));
762 template <typename K, typename V>
763 bool insert_at( head_type& refHead, const K& key, const V& val )
765 return insert_node_at( refHead, alloc_node( key, val ));
768 template <typename K, typename Func>
769 bool insert_key_at( head_type& refHead, const K& key, Func f )
771 scoped_node_ptr pNode( alloc_node( key ));
773 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
780 template <typename... Args>
781 bool emplace_at( head_type& refHead, Args&&... args )
783 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
786 template <typename K, typename Compare>
787 bool erase_at( head_type& refHead, K const& key, Compare cmp )
789 return base_class::erase_at( &refHead, key, cmp );
792 template <typename K, typename Compare, typename Func>
793 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
795 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
798 template <typename K, typename Func>
799 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
801 scoped_node_ptr pNode( alloc_node( key ));
803 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
804 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
805 if ( ret.first && ret.second )
811 template <typename K, typename Compare>
812 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
814 return base_class::extract_at( &refHead, key, cmp );
817 template <typename K, typename Compare>
818 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
820 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
823 template <typename K, typename Compare, typename Func>
824 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
826 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
829 template <typename K, typename Compare>
830 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
832 node_type * pNode = base_class::get_at( &refHead, val, cmp );
833 return pNode ? &pNode->m_Data : nullptr;
839 }} // namespace cds::container
841 #endif // #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H