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 template <typename K, typename Func>
416 bool insert_key( const K& key, Func func )
418 return insert_key_at( head(), key, func );
421 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
423 Returns \p true if inserting successful, \p false otherwise.
425 The function makes RCU lock internally.
427 template <typename... Args>
428 bool emplace( Args&&... args )
430 return emplace_at( head(), std::forward<Args>(args)... );
433 /// Ensures that the \p key exists in the list
435 The operation performs inserting or changing data with lock-free manner.
437 If the \p key not found in the list, then the new item created from \p key
438 is inserted into the list (note that in this case the \ref key_type should be
439 copy-constructible from type \p K).
440 Otherwise, the functor \p func is called with item found.
441 The functor \p Func may be a function with signature:
443 void func( bool bNew, value_type& item );
448 void operator()( bool bNew, value_type& item );
453 - \p bNew - \p true if the item has been inserted, \p false otherwise
454 - \p item - item of the list
456 The functor may change any fields of the \p item.second that is \ref mapped_type;
457 however, \p func must guarantee that during changing no any other modifications
458 could be made on this item by concurrent threads.
460 You may pass \p func argument by reference using \p std::ref
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 template <typename K, typename Func>
469 std::pair<bool, bool> ensure( const K& key, Func f )
471 return ensure_at( head(), key, f );
474 /// Deletes \p key from the list
475 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
477 RCU \p synchronize method can be called. RCU should not be locked.
479 Returns \p true if \p key is found and has been deleted, \p false otherwise
481 template <typename K>
482 bool erase( K const& key )
484 return erase_at( head(), key, intrusive_key_comparator() );
487 /// Deletes the item from the list using \p pred predicate for searching
489 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
490 but \p pred is used for key comparing.
491 \p Less functor has the interface like \p std::less.
492 \p pred must imply the same element order as the comparator used for building the list.
494 template <typename K, typename Less>
495 bool erase_with( K const& key, Less pred )
497 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
500 /// Deletes \p key from the list
501 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
502 The function searches an item with key \p key, calls \p f functor
503 and deletes the item. If \p key is not found, the functor is not called.
505 The functor \p Func interface:
508 void operator()(value_type& val) { ... }
511 The functor may be passed by reference with <tt>boost:ref</tt>
513 RCU \p synchronize method can be called. RCU should not be locked.
515 Returns \p true if key is found and deleted, \p false otherwise
517 template <typename K, typename Func>
518 bool erase( K const& key, Func f )
520 return erase_at( head(), key, intrusive_key_comparator(), f );
523 /// Deletes the item from the list using \p pred predicate for searching
525 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
526 but \p pred is used for key comparing.
527 \p Less functor has the interface like \p std::less.
528 \p pred must imply the same element order as the comparator used for building the list.
530 template <typename K, typename Less, typename Func>
531 bool erase_with( K const& key, Less pred, Func f )
533 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
536 /// Extracts an item from the list
538 @anchor cds_nonintrusive_LazyKVList_rcu_extract
539 The function searches an item with key equal to \p key in the list,
540 unlinks it from the list, and returns pointer to an item found in \p dest argument.
541 If \p key is not found the function returns \p false.
543 @note The function does NOT call RCU read-side lock or synchronization,
544 and does NOT dispose the item found. It just excludes the item from the list
545 and returns a pointer to item found.
546 You should lock RCU before calling this function.
549 #include <cds/urcu/general_buffered.h>
550 #include <cds/container/lazy_kvlist_rcu.h>
552 typedef cds::urcu::gc< general_buffered<> > rcu;
553 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
555 rcu_lazy_list theList;
558 rcu_lazy_list::exempt_ptr p;
560 // first, we should lock RCU
561 rcu_lazy_list::rcu_lock sl;
563 // Now, you can apply extract function
564 // Note that you must not delete the item found inside the RCU lock
565 if ( theList.extract( p, 10 )) {
566 // do something with p
570 // Outside RCU lock section we may safely release extracted pointer.
571 // release() passes the pointer to RCU reclamation cycle.
575 template <typename K>
576 bool extract( exempt_ptr& dest, K const& key )
578 dest = extract_at( head(), key, intrusive_key_comparator() );
579 return !dest.empty();
582 /// Extracts an item from the list using \p pred predicate for searching
584 This function is the analog for \ref cds_nonintrusive_LazyKVList_rcu_extract "extract(exempt_ptr&, K const&)".
585 The \p pred is a predicate used for key comparing.
586 \p Less has the interface like \p std::less.
587 \p pred must imply the same element order as \ref key_comparator.
589 template <typename K, typename Less>
590 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
592 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
593 return !dest.empty();
596 /// Finds the key \p key
597 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
598 The function searches the item with key equal to \p key
599 and returns \p true if it is found, and \p false otherwise
601 The function applies RCU lock internally.
603 template <typename Q>
604 bool find( Q const& key ) const
606 return find_at( head(), key, intrusive_key_comparator() );
609 /// Finds the key \p val using \p pred predicate for searching
611 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
612 but \p pred is used for key comparing.
613 \p Less functor has the interface like \p std::less.
614 \p pred must imply the same element order as the comparator used for building the list.
616 template <typename Q, typename Less>
617 bool find_with( Q const& key, Less pred ) const
619 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
622 /// Finds the key \p key and performs an action with it
623 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
624 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
625 The interface of \p Func functor is:
628 void operator()( value_type& item );
631 where \p item is the item found.
633 You may pass \p f argument by reference using \p std::ref.
635 The functor may change <tt>item.second</tt> that is reference to value of node.
636 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
637 The function does not serialize simultaneous access to the list \p item. If such access is
638 possible you must provide your own synchronization schema to exclude unsafe item modifications.
640 The function applies RCU lock internally.
642 The function returns \p true if \p key is found, \p false otherwise.
644 template <typename Q, typename Func>
645 bool find( Q const& key, Func f ) const
647 return find_at( head(), key, intrusive_key_comparator(), f );
650 /// Finds the key \p val using \p pred predicate for searching
652 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
653 but \p pred is used for key comparing.
654 \p Less functor has the interface like \p std::less.
655 \p pred must imply the same element order as the comparator used for building the list.
657 template <typename Q, typename Less, typename Func>
658 bool find_with( Q const& key, Less pred, Func f ) const
660 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
663 /// Finds \p key and return the item found
664 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
665 The function searches the item with \p key and returns the pointer to item found.
666 If \p key is not found it returns \p nullptr.
668 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
670 RCU should be locked before call of this function.
671 Returned item is valid only while RCU is locked:
673 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
678 ord_list::rcu_lock lock;
680 ord_list::value_type * pVal = theList.get( 5 );
685 // Unlock RCU by rcu_lock destructor
686 // pVal can be freed at any time after RCU has been unlocked
690 template <typename K>
691 value_type * get( K const& key ) const
693 return get_at( head(), key, intrusive_key_comparator());
696 /// Finds \p key and return the item found
698 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
699 but \p pred is used for comparing the keys.
701 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
703 \p pred must imply the same element order as the comparator used for building the list.
705 template <typename K, typename Less>
706 value_type * get_with( K const& key, Less pred ) const
708 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
711 /// Checks if the list is empty
714 return base_class::empty();
717 /// Returns list's item count
719 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
720 this function always returns 0.
722 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
723 is empty. To check list emptyness use \ref empty() method.
727 return base_class::size();
732 Post-condition: the list is empty
741 bool insert_node_at( head_type& refHead, node_type * pNode )
743 assert( pNode != nullptr );
744 scoped_node_ptr p( pNode );
746 if ( base_class::insert_at( &refHead, *p )) {
754 template <typename K>
755 bool insert_at( head_type& refHead, const K& key )
757 return insert_node_at( refHead, alloc_node( key ));
760 template <typename K, typename V>
761 bool insert_at( head_type& refHead, const K& key, const V& val )
763 return insert_node_at( refHead, alloc_node( key, val ));
766 template <typename K, typename Func>
767 bool insert_key_at( head_type& refHead, const K& key, Func f )
769 scoped_node_ptr pNode( alloc_node( key ));
771 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
778 template <typename... Args>
779 bool emplace_at( head_type& refHead, Args&&... args )
781 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
784 template <typename K, typename Compare>
785 bool erase_at( head_type& refHead, K const& key, Compare cmp )
787 return base_class::erase_at( &refHead, key, cmp );
790 template <typename K, typename Compare, typename Func>
791 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
793 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
796 template <typename K, typename Func>
797 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
799 scoped_node_ptr pNode( alloc_node( key ));
801 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
802 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
803 if ( ret.first && ret.second )
809 template <typename K, typename Compare>
810 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
812 return base_class::extract_at( &refHead, key, cmp );
815 template <typename K, typename Compare>
816 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
818 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
821 template <typename K, typename Compare, typename Func>
822 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
824 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
827 template <typename K, typename Compare>
828 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
830 node_type * pNode = base_class::get_at( &refHead, val, cmp );
831 return pNode ? &pNode->m_Data : nullptr;
837 }} // namespace cds::container
839 #endif // #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H