3 #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H
4 #define __CDS_CONTAINER_LAZY_KVLIST_RCU_H
7 #include <cds/container/details/lazy_list_base.h>
8 #include <cds/intrusive/lazy_list_rcu.h>
9 #include <cds/container/details/make_lazy_kvlist.h>
11 #include <cds/details/functor_wrapper.h>
13 namespace cds { namespace container {
15 /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
16 /** @ingroup cds_nonintrusive_list
17 \anchor cds_nonintrusive_LazyKVList_rcu
19 This is key-value variation of non-intrusive LazyList.
20 Like standard container, this implementation split a value stored into two part -
21 constant key and alterable value.
23 Usually, ordered single-linked list is used as a building block for the hash table implementation.
24 The complexity of searching is <tt>O(N)</tt>.
27 - \p RCU - one of \ref cds_urcu_gc "RCU type"
28 - \p Key - key type of an item stored in the list. It should be copy-constructible
29 - \p Value - value type stored in the list
30 - \p Traits - type traits, default is lazy_list::type_traits
32 It is possible to declare option-based list with cds::container::lazy_list::make_traits metafunction istead of \p Traits template
33 argument. For example, the following traits-based declaration of gc::HP lazy list
34 @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
35 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
37 #include <cds/urcu/general_threaded.h>
38 #include <cds/container/lazy_kvlist_rcu.h>
39 // Declare comparator for the item
41 int operator ()( int i1, int i2 )
47 // Declare type_traits
48 struct my_traits: public cds::container::lazy_list::type_traits
50 typedef my_compare compare;
53 // Declare traits-based list
54 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits > traits_based_list;
57 is equivalent for the following option-based list
59 #include <cds/urcu/general_threaded.h>
60 #include <cds/container/lazy_kvlist_rcu.h>
62 // my_compare is the same
64 // Declare option-based list
65 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
66 typename cds::container::lazy_list::make_traits<
67 cds::container::opt::compare< my_compare > // item comparator option
72 Template argument list \p Options of cds::container::lazy_list::make_traits metafunction are:
73 - opt::compare - key comparison functor. No default functor is provided.
74 If the option is not specified, the opt::less is used.
75 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
76 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
77 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
78 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
79 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
80 or opt::v::sequential_consistent (sequentially consisnent memory model).
81 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
87 #ifdef CDS_DOXYGEN_INVOKED
88 typename Traits = lazy_list::type_traits
93 class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
94 #ifdef CDS_DOXYGEN_INVOKED
95 protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
97 protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
101 typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
102 typedef typename options::type base_class;
106 #ifdef CDS_DOXYGEN_INVOKED
107 typedef Key key_type ; ///< Key type
108 typedef Value mapped_type ; ///< Type of value stored in the list
109 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
111 typedef typename options::key_type key_type;
112 typedef typename options::value_type mapped_type;
113 typedef typename options::pair_type value_type;
116 typedef typename base_class::gc gc ; ///< Garbage collector used
117 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
118 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
119 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
120 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
121 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
124 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
125 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
129 typedef typename base_class::value_type node_type;
130 typedef typename options::cxx_allocator cxx_allocator;
131 typedef typename options::node_deallocator node_deallocator;
132 typedef typename options::type_traits::compare intrusive_key_comparator;
134 typedef typename base_class::node_type head_type;
138 /// pointer to extracted node
139 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
140 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
145 template <typename K>
146 static node_type * alloc_node(const K& key)
148 return cxx_allocator().New( key );
151 template <typename K, typename V>
152 static node_type * alloc_node( const K& key, const V& val )
154 return cxx_allocator().New( key, val );
157 template <typename... Args>
158 static node_type * alloc_node( Args&&... args )
160 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
163 static void free_node( node_type * pNode )
165 cxx_allocator().Delete( pNode );
168 struct node_disposer {
169 void operator()( node_type * pNode )
174 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
178 return base_class::m_Head;
181 head_type& head() const
183 return const_cast<head_type&>( base_class::m_Head );
188 return base_class::m_Tail;
191 head_type& tail() const
193 return const_cast<head_type&>( base_class::m_Tail );
200 template <bool IsConst>
201 class iterator_type: protected base_class::template iterator_type<IsConst>
203 typedef typename base_class::template iterator_type<IsConst> iterator_base;
205 iterator_type( head_type const& pNode )
206 : iterator_base( const_cast<head_type *>(&pNode) )
208 iterator_type( head_type const * pNode )
209 : iterator_base( const_cast<head_type *>(pNode) )
212 friend class LazyKVList;
215 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
216 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
218 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
219 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
224 iterator_type( iterator_type const& src )
225 : iterator_base( src )
228 key_type const& key() const
230 typename iterator_base::value_ptr p = iterator_base::operator ->();
231 assert( p != nullptr );
232 return p->m_Data.first;
235 value_ref val() const
237 typename iterator_base::value_ptr p = iterator_base::operator ->();
238 assert( p != nullptr );
239 return p->m_Data.second;
242 pair_ptr operator ->() const
244 typename iterator_base::value_ptr p = iterator_base::operator ->();
245 return p ? &(p->m_Data) : nullptr;
248 pair_ref operator *() const
250 typename iterator_base::value_ref p = iterator_base::operator *();
255 iterator_type& operator ++()
257 iterator_base::operator ++();
262 bool operator ==(iterator_type<C> const& i ) const
264 return iterator_base::operator ==(i);
267 bool operator !=(iterator_type<C> const& i ) const
269 return iterator_base::operator !=(i);
276 typedef iterator_type<false> iterator;
278 /// Const forward iterator
279 typedef iterator_type<true> const_iterator;
281 /// Returns a forward iterator addressing the first element in a list
283 For empty list \code begin() == end() \endcode
287 iterator it( head() );
288 ++it ; // skip dummy head
292 /// Returns an iterator that addresses the location succeeding the last element in a list
294 Do not use the value returned by <tt>end</tt> function to access any item.
295 Internally, <tt>end</tt> returning value pointing to dummy tail node.
297 The returned value can be used only to control reaching the end of the list.
298 For empty list \code begin() == end() \endcode
302 return iterator( tail() );
305 /// Returns a forward const iterator addressing the first element in a list
307 const_iterator begin() const
309 const_iterator it( head() );
310 ++it; // skip dummy head
313 const_iterator cbegin()
315 const_iterator it( head() );
316 ++it; // skip dummy head
321 /// Returns an const iterator that addresses the location succeeding the last element in a list
323 const_iterator end() const
325 return const_iterator( tail());
327 const_iterator cend()
329 return const_iterator( tail());
334 /// Default constructor
336 Initializes empty list
350 /// Inserts new node with key and default value
352 The function creates a node with \p key and default value, and then inserts the node created into the list.
355 - The \ref key_type should be constructible from value of type \p K.
356 In trivial case, \p K is equal to \ref key_type.
357 - The \ref mapped_type should be default-constructible.
359 The function makes RCU lock internally.
361 Returns \p true if inserting successful, \p false otherwise.
363 template <typename K>
364 bool insert( const K& key )
366 return insert_at( head(), key );
369 /// Inserts new node with a key and a value
371 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
374 - The \ref key_type should be constructible from \p key of type \p K.
375 - The \ref mapped_type should be constructible from \p val of type \p V.
377 The function makes RCU lock internally.
379 Returns \p true if inserting successful, \p false otherwise.
381 template <typename K, typename V>
382 bool insert( const K& key, const V& val )
384 return insert_at( head(), key, val );
387 /// Inserts new node and initializes it by a functor
389 This function inserts new node with key \p key and if inserting is successful then it calls
390 \p func functor with signature
393 void operator()( value_type& item );
397 The argument \p item of user-defined functor \p func is the reference
398 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
399 User-defined functor \p func should guarantee that during changing item's value no any other changes
400 could be made on this list's item by concurrent threads.
401 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
402 and it is called only if inserting is successful.
404 The key_type should be constructible from value of type \p K.
406 The function allows to split creating of new item into two part:
407 - create item from \p key;
408 - insert new item into the list;
409 - if inserting is successful, initialize the value of item by calling \p func functor
411 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
412 it is preferable that the initialization should be completed only if inserting is successful.
414 The function makes RCU lock internally.
416 template <typename K, typename Func>
417 bool insert_key( const K& key, Func func )
419 return insert_key_at( head(), key, func );
422 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
424 Returns \p true if inserting successful, \p false otherwise.
426 The function makes RCU lock internally.
428 template <typename... Args>
429 bool emplace( Args&&... args )
431 return emplace_at( head(), std::forward<Args>(args)... );
434 /// Ensures that the \p key exists in the list
436 The operation performs inserting or changing data with lock-free manner.
438 If the \p key not found in the list, then the new item created from \p key
439 is inserted into the list (note that in this case the \ref key_type should be
440 copy-constructible from type \p K).
441 Otherwise, the functor \p func is called with item found.
442 The functor \p Func may be a function with signature:
444 void func( bool bNew, value_type& item );
449 void operator()( bool bNew, value_type& item );
454 - \p bNew - \p true if the item has been inserted, \p false otherwise
455 - \p item - item of the list
457 The functor may change any fields of the \p item.second that is \ref mapped_type;
458 however, \p func must guarantee that during changing no any other modifications
459 could be made on this item by concurrent threads.
461 You may pass \p func argument by reference using <tt>boost::ref</tt>.
463 The function makes RCU lock internally.
465 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
466 \p second is true if new item has been added or \p false if the item with \p key
467 already is in the list.
469 template <typename K, typename Func>
470 std::pair<bool, bool> ensure( const K& key, Func f )
472 return ensure_at( head(), key, f );
475 /// Deletes \p key from the list
476 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
478 RCU \p synchronize method can be called. RCU should not be locked.
480 Returns \p true if \p key is found and has been deleted, \p false otherwise
482 template <typename K>
483 bool erase( K const& key )
485 return erase_at( head(), key, intrusive_key_comparator() );
488 /// Deletes the item from the list using \p pred predicate for searching
490 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
491 but \p pred is used for key comparing.
492 \p Less functor has the interface like \p std::less.
493 \p pred must imply the same element order as the comparator used for building the list.
495 template <typename K, typename Less>
496 bool erase_with( K const& key, Less pred )
498 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
501 /// Deletes \p key from the list
502 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
503 The function searches an item with key \p key, calls \p f functor
504 and deletes the item. If \p key is not found, the functor is not called.
506 The functor \p Func interface:
509 void operator()(value_type& val) { ... }
512 The functor may be passed by reference with <tt>boost:ref</tt>
514 RCU \p synchronize method can be called. RCU should not be locked.
516 Returns \p true if key is found and deleted, \p false otherwise
518 template <typename K, typename Func>
519 bool erase( K const& key, Func f )
521 return erase_at( head(), key, intrusive_key_comparator(), f );
524 /// Deletes the item from the list using \p pred predicate for searching
526 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
527 but \p pred is used for key comparing.
528 \p Less functor has the interface like \p std::less.
529 \p pred must imply the same element order as the comparator used for building the list.
531 template <typename K, typename Less, typename Func>
532 bool erase_with( K const& key, Less pred, Func f )
534 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
537 /// Extracts an item from the list
539 @anchor cds_nonintrusive_LazyKVList_rcu_extract
540 The function searches an item with key equal to \p key in the list,
541 unlinks it from the list, and returns pointer to an item found in \p dest argument.
542 If \p key is not found the function returns \p false.
544 @note The function does NOT call RCU read-side lock or synchronization,
545 and does NOT dispose the item found. It just excludes the item from the list
546 and returns a pointer to item found.
547 You should lock RCU before calling this function.
550 #include <cds/urcu/general_buffered.h>
551 #include <cds/container/lazy_kvlist_rcu.h>
553 typedef cds::urcu::gc< general_buffered<> > rcu;
554 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
556 rcu_lazy_list theList;
559 rcu_lazy_list::exempt_ptr p;
561 // first, we should lock RCU
562 rcu_lazy_list::rcu_lock sl;
564 // Now, you can apply extract function
565 // Note that you must not delete the item found inside the RCU lock
566 if ( theList.extract( p, 10 )) {
567 // do something with p
571 // Outside RCU lock section we may safely release extracted pointer.
572 // release() passes the pointer to RCU reclamation cycle.
576 template <typename K>
577 bool extract( exempt_ptr& dest, K const& key )
579 dest = extract_at( head(), key, intrusive_key_comparator() );
580 return !dest.empty();
583 /// Extracts an item from the list using \p pred predicate for searching
585 This function is the analog for \ref cds_nonintrusive_LazyKVList_rcu_extract "extract(exempt_ptr&, K const&)".
586 The \p pred is a predicate used for key comparing.
587 \p Less has the interface like \p std::less.
588 \p pred must imply the same element order as \ref key_comparator.
590 template <typename K, typename Less>
591 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
593 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
594 return !dest.empty();
597 /// Finds the key \p key
598 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
599 The function searches the item with key equal to \p key
600 and returns \p true if it is found, and \p false otherwise
602 The function applies RCU lock internally.
604 template <typename Q>
605 bool find( Q const& key ) const
607 return find_at( head(), key, intrusive_key_comparator() );
610 /// Finds the key \p val using \p pred predicate for searching
612 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
613 but \p pred is used for key comparing.
614 \p Less functor has the interface like \p std::less.
615 \p pred must imply the same element order as the comparator used for building the list.
617 template <typename Q, typename Less>
618 bool find_with( Q const& key, Less pred ) const
620 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
623 /// Finds the key \p key and performs an action with it
624 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
625 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
626 The interface of \p Func functor is:
629 void operator()( value_type& item );
632 where \p item is the item found.
634 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
636 The functor may change <tt>item.second</tt> that is reference to value of node.
637 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
638 The function does not serialize simultaneous access to the list \p item. If such access is
639 possible you must provide your own synchronization schema to exclude unsafe item modifications.
641 The function applies RCU lock internally.
643 The function returns \p true if \p key is found, \p false otherwise.
645 template <typename Q, typename Func>
646 bool find( Q const& key, Func f ) const
648 return find_at( head(), key, intrusive_key_comparator(), f );
651 /// Finds the key \p val using \p pred predicate for searching
653 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
654 but \p pred is used for key comparing.
655 \p Less functor has the interface like \p std::less.
656 \p pred must imply the same element order as the comparator used for building the list.
658 template <typename Q, typename Less, typename Func>
659 bool find_with( Q const& key, Less pred, Func f ) const
661 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
664 /// Finds \p key and return the item found
665 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
666 The function searches the item with \p key and returns the pointer to item found.
667 If \p key is not found it returns \p nullptr.
669 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
671 RCU should be locked before call of this function.
672 Returned item is valid only while RCU is locked:
674 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
679 ord_list::rcu_lock lock;
681 ord_list::value_type * pVal = theList.get( 5 );
686 // Unlock RCU by rcu_lock destructor
687 // pVal can be freed at any time after RCU has been unlocked
691 template <typename K>
692 value_type * get( K const& key ) const
694 return get_at( head(), key, intrusive_key_comparator());
697 /// Finds \p key and return the item found
699 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
700 but \p pred is used for comparing the keys.
702 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
704 \p pred must imply the same element order as the comparator used for building the list.
706 template <typename K, typename Less>
707 value_type * get_with( K const& key, Less pred ) const
709 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
712 /// Checks if the list is empty
715 return base_class::empty();
718 /// Returns list's item count
720 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
721 this function always returns 0.
723 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
724 is empty. To check list emptyness use \ref empty() method.
728 return base_class::size();
733 Post-condition: the list is empty
742 bool insert_node_at( head_type& refHead, node_type * pNode )
744 assert( pNode != nullptr );
745 scoped_node_ptr p( pNode );
747 if ( base_class::insert_at( &refHead, *p )) {
755 template <typename K>
756 bool insert_at( head_type& refHead, const K& key )
758 return insert_node_at( refHead, alloc_node( key ));
761 template <typename K, typename V>
762 bool insert_at( head_type& refHead, const K& key, const V& val )
764 return insert_node_at( refHead, alloc_node( key, val ));
767 template <typename K, typename Func>
768 bool insert_key_at( head_type& refHead, const K& key, Func f )
770 scoped_node_ptr pNode( alloc_node( key ));
772 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node.m_Data ); } )) {
779 template <typename... Args>
780 bool emplace_at( head_type& refHead, Args&&... args )
782 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
785 template <typename K, typename Compare>
786 bool erase_at( head_type& refHead, K const& key, Compare cmp )
788 return base_class::erase_at( &refHead, key, cmp );
791 template <typename K, typename Compare, typename Func>
792 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
794 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){cds::unref(f)( const_cast<value_type&>(node.m_Data)); });
797 template <typename K, typename Func>
798 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
800 scoped_node_ptr pNode( alloc_node( key ));
802 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
803 [&f]( bool bNew, node_type& node, node_type& ){ cds::unref(f)( bNew, node.m_Data ); });
804 if ( ret.first && ret.second )
810 template <typename K, typename Compare>
811 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
813 return base_class::extract_at( &refHead, key, cmp );
816 template <typename K, typename Compare>
817 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
819 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
822 template <typename K, typename Compare, typename Func>
823 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
825 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ cds::unref(f)( node.m_Data ); });
828 template <typename K, typename Compare>
829 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
831 node_type * pNode = base_class::get_at( &refHead, val, cmp );
832 return pNode ? &pNode->m_Data : nullptr;
838 }} // namespace cds::container
840 #endif // #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H