3 #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H
4 #define CDSLIB_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 namespace cds { namespace container {
13 /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
14 /** @ingroup cds_nonintrusive_list
15 \anchor cds_nonintrusive_LazyKVList_rcu
17 This is key-value variation of non-intrusive \p %LazyList.
18 Like standard container, this implementation split a value stored into two part -
19 constant key and alterable value.
21 Usually, ordered single-linked list is used as a building block for the hash table implementation.
22 The complexity of searching is <tt>O(N)</tt>.
25 - \p RCU - one of \ref cds_urcu_gc "RCU type"
26 - \p Key - key type of an item to be stored in the list. It should be copy-constructible
27 - \p Value - value type to be stored in the list
28 - \p Traits - type traits, default is \p lazy_list::traits
29 It is possible to declare option-based list with \p lazy_list::make_traits metafunction istead of \p Traits template
30 argument. For example, the following traits-based declaration of \p gc::HP lazy list
32 #include <cds/urcu/general_threaded.h>
33 #include <cds/container/lazy_kvlist_rcu.h>
34 // Declare comparator for the item
36 int operator ()( int i1, int i2 )
43 struct my_traits: public cds::container::lazy_list::traits
45 typedef my_compare compare;
48 // Declare traits-based list
49 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits > traits_based_list;
51 is equal to the following option-based list
53 #include <cds/urcu/general_threaded.h>
54 #include <cds/container/lazy_kvlist_rcu.h>
56 // my_compare is the same
58 // Declare option-based list
59 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
60 typename cds::container::lazy_list::make_traits<
61 cds::container::opt::compare< my_compare > // item comparator option
66 @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
67 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
73 #ifdef CDS_DOXYGEN_INVOKED
74 typename Traits = lazy_list::traits
79 class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
80 #ifdef CDS_DOXYGEN_INVOKED
81 protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
83 protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
87 typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > maker;
88 typedef typename maker::type base_class;
92 typedef cds::urcu::gc<RCU> gc; ///< Garbage collector
93 #ifdef CDS_DOXYGEN_INVOKED
94 typedef Key key_type ; ///< Key type
95 typedef Value mapped_type ; ///< Type of value stored in the list
96 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
98 typedef typename maker::key_type key_type;
99 typedef typename maker::mapped_type mapped_type;
100 typedef typename maker::value_type value_type;
102 typedef typename base_class::back_off back_off; ///< Back-off strategy used
103 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
104 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
105 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
106 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
107 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
109 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
110 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
114 typedef typename base_class::value_type node_type;
115 typedef typename maker::cxx_allocator cxx_allocator;
116 typedef typename maker::node_deallocator node_deallocator;
117 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
119 typedef typename base_class::node_type head_type;
123 /// pointer to extracted node
124 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer,
125 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
127 /// Type of \p get() member function return value
128 typedef value_type * raw_ptr;
132 template <typename K>
133 static node_type * alloc_node(const K& key)
135 return cxx_allocator().New( key );
138 template <typename K, typename V>
139 static node_type * alloc_node( const K& key, const V& val )
141 return cxx_allocator().New( key, val );
144 template <typename... Args>
145 static node_type * alloc_node( Args&&... args )
147 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
150 static void free_node( node_type * pNode )
152 cxx_allocator().Delete( pNode );
155 struct node_disposer {
156 void operator()( node_type * pNode )
161 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
165 return base_class::m_Head;
168 head_type& head() const
170 return const_cast<head_type&>( base_class::m_Head );
175 return base_class::m_Tail;
178 head_type& tail() const
180 return const_cast<head_type&>( base_class::m_Tail );
187 template <bool IsConst>
188 class iterator_type: protected base_class::template iterator_type<IsConst>
190 typedef typename base_class::template iterator_type<IsConst> iterator_base;
192 iterator_type( head_type const& pNode )
193 : iterator_base( const_cast<head_type *>(&pNode) )
195 iterator_type( head_type const * pNode )
196 : iterator_base( const_cast<head_type *>(pNode) )
199 friend class LazyKVList;
202 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
203 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
205 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
206 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
211 iterator_type( iterator_type const& src )
212 : iterator_base( src )
215 key_type const& key() const
217 typename iterator_base::value_ptr p = iterator_base::operator ->();
218 assert( p != nullptr );
219 return p->m_Data.first;
222 value_ref val() const
224 typename iterator_base::value_ptr p = iterator_base::operator ->();
225 assert( p != nullptr );
226 return p->m_Data.second;
229 pair_ptr operator ->() const
231 typename iterator_base::value_ptr p = iterator_base::operator ->();
232 return p ? &(p->m_Data) : nullptr;
235 pair_ref operator *() const
237 typename iterator_base::value_ref p = iterator_base::operator *();
242 iterator_type& operator ++()
244 iterator_base::operator ++();
249 bool operator ==(iterator_type<C> const& i ) const
251 return iterator_base::operator ==(i);
254 bool operator !=(iterator_type<C> const& i ) const
256 return iterator_base::operator !=(i);
263 typedef iterator_type<false> iterator;
265 /// Const forward iterator
266 typedef iterator_type<true> const_iterator;
268 /// Returns a forward iterator addressing the first element in a list
270 For empty list \code begin() == end() \endcode
274 iterator it( head() );
275 ++it ; // skip dummy head
279 /// Returns an iterator that addresses the location succeeding the last element in a list
281 Do not use the value returned by <tt>end</tt> function to access any item.
282 Internally, <tt>end</tt> returning value pointing to dummy tail node.
284 The returned value can be used only to control reaching the end of the list.
285 For empty list \code begin() == end() \endcode
289 return iterator( tail() );
292 /// Returns a forward const iterator addressing the first element in a list
294 const_iterator begin() const
296 const_iterator it( head() );
297 ++it; // skip dummy head
300 const_iterator cbegin() const
302 const_iterator it( head() );
303 ++it; // skip dummy head
308 /// Returns an const iterator that addresses the location succeeding the last element in a list
310 const_iterator end() const
312 return const_iterator( tail());
314 const_iterator cend() const
316 return const_iterator( tail());
321 /// Default constructor
325 /// Destructor clears the list
331 /// Inserts new node with key and default value
333 The function creates a node with \p key and default value, and then inserts the node created into the list.
336 - The \ref key_type should be constructible from value of type \p K.
337 In trivial case, \p K is equal to \p key_type.
338 - The \ref mapped_type should be default-constructible.
340 The function makes RCU lock internally.
342 Returns \p true if inserting successful, \p false otherwise.
344 template <typename K>
345 bool insert( const K& key )
347 return insert_at( head(), key );
350 /// Inserts new node with a key and a value
352 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
355 - The \p key_type should be constructible from \p key of type \p K.
356 - The \p mapped_type should be constructible from \p val of type \p V.
358 The function makes RCU lock internally.
360 Returns \p true if inserting successful, \p false otherwise.
362 template <typename K, typename V>
363 bool insert( const K& key, const V& val )
365 return insert_at( head(), key, val );
368 /// Inserts new node and initializes it by a functor
370 This function inserts new node with key \p key and if inserting is successful then it calls
371 \p func functor with signature
374 void operator()( value_type& item );
378 The argument \p item of user-defined functor \p func is the reference
379 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
380 The user-defined functor is called only if inserting is successful.
382 The key_type should be constructible from value of type \p K.
384 The function allows to split creating of new item into two part:
385 - create item from \p key;
386 - insert new item into the list;
387 - if inserting is successful, initialize the value of item by calling \p func functor
389 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
390 it is preferable that the initialization should be completed only if inserting is successful.
392 The function makes RCU lock internally.
394 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
396 template <typename K, typename Func>
397 bool insert_with( const K& key, Func func )
399 return insert_with_at( head(), key, func );
402 /// Inserts data of type \p mapped_type constructed from \p args
404 Returns \p true if inserting successful, \p false otherwise.
406 The function makes RCU lock internally.
408 template <typename... Args>
409 bool emplace( Args&&... args )
411 return emplace_at( head(), std::forward<Args>(args)... );
414 /// Updates data by \p key
416 The operation performs inserting or replacing the element with lock-free manner.
418 If the \p key not found in the list, then the new item created from \p key
419 will be inserted iff \p bAllowInsert is \p true.
420 (note that in this case the \ref key_type should be constructible from type \p K).
421 Otherwise, if \p key is found, the functor \p func is called with item found.
423 The functor \p Func signature is:
426 void operator()( bool bNew, value_type& item );
430 - \p bNew - \p true if the item has been inserted, \p false otherwise
431 - \p item - the item found or inserted
433 The functor may change any fields of the \p item.second of \p mapped_type;
434 during \p func call \p item is locked so it is safe to modify the item in
435 multi-threaded environment.
437 The function applies RCU lock internally.
439 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
440 \p second is true if new item has been added or \p false if the item with \p key
443 template <typename K, typename Func>
444 std::pair<bool, bool> update( const K& key, Func func, bool bAllowInsert = true )
446 return update_at( head(), key, func, bAllowInsert );
450 template <typename K, typename Func>
451 std::pair<bool, bool> ensure( const K& key, Func f )
453 return update( head(), key, f, true );
457 /// Deletes \p key from the list
458 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
460 RCU \p synchronize method can be called. RCU should not be locked.
462 Returns \p true if \p key is found and has been deleted, \p false otherwise
464 template <typename K>
465 bool erase( K const& key )
467 return erase_at( head(), key, intrusive_key_comparator() );
470 /// Deletes the item from the list using \p pred predicate for searching
472 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
473 but \p pred is used for key comparing.
474 \p Less functor has the interface like \p std::less.
475 \p pred must imply the same element order as the comparator used for building the list.
477 template <typename K, typename Less>
478 bool erase_with( K const& key, Less pred )
481 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
484 /// Deletes \p key from the list
485 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
486 The function searches an item with key \p key, calls \p f functor
487 and deletes the item. If \p key is not found, the functor is not called.
489 The functor \p Func interface:
492 void operator()(value_type& val) { ... }
496 RCU \p synchronize method can be called. RCU should not be locked.
498 Returns \p true if key is found and deleted, \p false otherwise
500 template <typename K, typename Func>
501 bool erase( K const& key, Func f )
503 return erase_at( head(), key, intrusive_key_comparator(), f );
506 /// Deletes the item from the list using \p pred predicate for searching
508 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
509 but \p pred is used for key comparing.
510 \p Less functor has the interface like \p std::less.
511 \p pred must imply the same element order as the comparator used for building the list.
513 template <typename K, typename Less, typename Func>
514 bool erase_with( K const& key, Less pred, Func f )
517 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
520 /// Extracts an item from the list
522 @anchor cds_nonintrusive_LazyKVList_rcu_extract
523 The function searches an item with key equal to \p key in the list,
524 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
525 If \p key is not found the function returns an empty \p exempt_ptr.
527 @note The function does NOT call RCU read-side lock or synchronization,
528 and does NOT dispose the item found. It just excludes the item from the list
529 and returns a pointer to item found.
530 You should manually lock RCU before calling this function.
533 #include <cds/urcu/general_buffered.h>
534 #include <cds/container/lazy_kvlist_rcu.h>
536 typedef cds::urcu::gc< general_buffered<> > rcu;
537 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
539 rcu_lazy_list theList;
542 rcu_lazy_list::exempt_ptr p;
544 // first, we should lock RCU
545 rcu_lazy_list::rcu_lock sl;
547 // Now, you can apply extract function
548 // Note that you must not delete the item found inside the RCU lock
549 p = theList.extract( 10 );
551 // do something with p
555 // Outside RCU lock section we may safely release extracted pointer.
556 // release() passes the pointer to RCU reclamation cycle.
560 template <typename K>
561 exempt_ptr extract( K const& key )
563 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator()));
566 /// Extracts an item from the list using \p pred predicate for searching
568 This function is the analog for \p extract(K const&).
569 The \p pred is a predicate used for key comparing.
570 \p Less has the interface like \p std::less.
571 \p pred must imply the same element order as \ref key_comparator.
573 template <typename K, typename Less>
574 exempt_ptr extract_with( K const& key, Less pred )
577 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
580 /// Checks whether the list contains \p key
582 The function searches the item with key equal to \p key
583 and returns \p true if it is found, and \p false otherwise.
585 The function applies RCU lock internally.
587 template <typename Q>
588 bool contains( Q const& key ) const
590 return find_at( head(), key, intrusive_key_comparator() );
594 template <typename Q>
595 bool find( Q const& key ) const
597 return contains( key );
601 /// Checks whether the map contains \p key using \p pred predicate for searching
603 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
604 \p Less functor has the interface like \p std::less.
605 \p Less must imply the same element order as the comparator used for building the list.
607 The function applies RCU lock internally.
609 template <typename Q, typename Less>
610 bool contains( Q const& key, Less pred ) const
613 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
617 template <typename Q, typename Less>
618 bool find_with( Q const& key, Less pred ) const
620 return contains( key, pred );
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 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
661 return find_at( head(), key, typename maker::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
710 return get_at( head(), key, typename maker::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 @note 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();
740 bool insert_node_at( head_type& refHead, node_type * pNode )
742 assert( pNode != nullptr );
743 scoped_node_ptr p( pNode );
745 if ( base_class::insert_at( &refHead, *p )) {
753 template <typename K>
754 bool insert_at( head_type& refHead, const K& key )
756 return insert_node_at( refHead, alloc_node( key ));
759 template <typename K, typename V>
760 bool insert_at( head_type& refHead, const K& key, const V& val )
762 return insert_node_at( refHead, alloc_node( key, val ));
765 template <typename K, typename Func>
766 bool insert_with_at( head_type& refHead, const K& key, Func f )
768 scoped_node_ptr pNode( alloc_node( key ));
770 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
777 template <typename... Args>
778 bool emplace_at( head_type& refHead, Args&&... args )
780 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
783 template <typename K, typename Compare>
784 bool erase_at( head_type& refHead, K const& key, Compare cmp )
786 return base_class::erase_at( &refHead, key, cmp );
789 template <typename K, typename Compare, typename Func>
790 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
792 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
795 template <typename K, typename Func>
796 std::pair<bool, bool> update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert )
798 scoped_node_ptr pNode( alloc_node( key ));
800 std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
801 [&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 CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H