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>
130 template <typename K>
131 static node_type * alloc_node(const K& key)
133 return cxx_allocator().New( key );
136 template <typename K, typename V>
137 static node_type * alloc_node( const K& key, const V& val )
139 return cxx_allocator().New( key, val );
142 template <typename... Args>
143 static node_type * alloc_node( Args&&... args )
145 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
148 static void free_node( node_type * pNode )
150 cxx_allocator().Delete( pNode );
153 struct node_disposer {
154 void operator()( node_type * pNode )
159 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
163 return base_class::m_Head;
166 head_type& head() const
168 return const_cast<head_type&>( base_class::m_Head );
173 return base_class::m_Tail;
176 head_type& tail() const
178 return const_cast<head_type&>( base_class::m_Tail );
185 template <bool IsConst>
186 class iterator_type: protected base_class::template iterator_type<IsConst>
188 typedef typename base_class::template iterator_type<IsConst> iterator_base;
190 iterator_type( head_type const& pNode )
191 : iterator_base( const_cast<head_type *>(&pNode) )
193 iterator_type( head_type const * pNode )
194 : iterator_base( const_cast<head_type *>(pNode) )
197 friend class LazyKVList;
200 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
201 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
203 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
204 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
209 iterator_type( iterator_type const& src )
210 : iterator_base( src )
213 key_type const& key() const
215 typename iterator_base::value_ptr p = iterator_base::operator ->();
216 assert( p != nullptr );
217 return p->m_Data.first;
220 value_ref val() const
222 typename iterator_base::value_ptr p = iterator_base::operator ->();
223 assert( p != nullptr );
224 return p->m_Data.second;
227 pair_ptr operator ->() const
229 typename iterator_base::value_ptr p = iterator_base::operator ->();
230 return p ? &(p->m_Data) : nullptr;
233 pair_ref operator *() const
235 typename iterator_base::value_ref p = iterator_base::operator *();
240 iterator_type& operator ++()
242 iterator_base::operator ++();
247 bool operator ==(iterator_type<C> const& i ) const
249 return iterator_base::operator ==(i);
252 bool operator !=(iterator_type<C> const& i ) const
254 return iterator_base::operator !=(i);
261 typedef iterator_type<false> iterator;
263 /// Const forward iterator
264 typedef iterator_type<true> const_iterator;
266 /// Returns a forward iterator addressing the first element in a list
268 For empty list \code begin() == end() \endcode
272 iterator it( head() );
273 ++it ; // skip dummy head
277 /// Returns an iterator that addresses the location succeeding the last element in a list
279 Do not use the value returned by <tt>end</tt> function to access any item.
280 Internally, <tt>end</tt> returning value pointing to dummy tail node.
282 The returned value can be used only to control reaching the end of the list.
283 For empty list \code begin() == end() \endcode
287 return iterator( tail() );
290 /// Returns a forward const iterator addressing the first element in a list
292 const_iterator begin() const
294 const_iterator it( head() );
295 ++it; // skip dummy head
298 const_iterator cbegin() const
300 const_iterator it( head() );
301 ++it; // skip dummy head
306 /// Returns an const iterator that addresses the location succeeding the last element in a list
308 const_iterator end() const
310 return const_iterator( tail());
312 const_iterator cend() const
314 return const_iterator( tail());
319 /// Default constructor
323 /// Destructor clears the list
329 /// Inserts new node with key and default value
331 The function creates a node with \p key and default value, and then inserts the node created into the list.
334 - The \ref key_type should be constructible from value of type \p K.
335 In trivial case, \p K is equal to \p key_type.
336 - The \ref mapped_type should be default-constructible.
338 The function makes RCU lock internally.
340 Returns \p true if inserting successful, \p false otherwise.
342 template <typename K>
343 bool insert( const K& key )
345 return insert_at( head(), key );
348 /// Inserts new node with a key and a value
350 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
353 - The \p key_type should be constructible from \p key of type \p K.
354 - The \p mapped_type should be constructible from \p val of type \p V.
356 The function makes RCU lock internally.
358 Returns \p true if inserting successful, \p false otherwise.
360 template <typename K, typename V>
361 bool insert( const K& key, const V& val )
363 return insert_at( head(), key, val );
366 /// Inserts new node and initializes it by a functor
368 This function inserts new node with key \p key and if inserting is successful then it calls
369 \p func functor with signature
372 void operator()( value_type& item );
376 The argument \p item of user-defined functor \p func is the reference
377 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
378 The user-defined functor is called only if inserting is successful.
380 The key_type should be constructible from value of type \p K.
382 The function allows to split creating of new item into two part:
383 - create item from \p key;
384 - insert new item into the list;
385 - if inserting is successful, initialize the value of item by calling \p func functor
387 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
388 it is preferable that the initialization should be completed only if inserting is successful.
390 The function makes RCU lock internally.
392 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
394 template <typename K, typename Func>
395 bool insert_with( const K& key, Func func )
397 return insert_with_at( head(), key, func );
400 /// Inserts data of type \p mapped_type constructed from \p args
402 Returns \p true if inserting successful, \p false otherwise.
404 The function makes RCU lock internally.
406 template <typename... Args>
407 bool emplace( Args&&... args )
409 return emplace_at( head(), std::forward<Args>(args)... );
412 /// Ensures that the \p key exists in the list
414 The operation performs inserting or changing data with lock-free manner.
416 If the \p key not found in the list, then the new item created from \p key
417 is inserted into the list (note that in this case the \ref key_type should be
418 copy-constructible from type \p K).
419 Otherwise, the functor \p func is called with item found.
420 The functor \p Func may be a function with signature:
422 void func( bool bNew, value_type& item );
427 void operator()( bool bNew, value_type& item );
432 - \p bNew - \p true if the item has been inserted, \p false otherwise
433 - \p item - item of the list
435 The functor may change any fields of the \p item.second of type \p mapped_type.
437 The function makes 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
441 already is in the list.
443 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
445 template <typename K, typename Func>
446 std::pair<bool, bool> ensure( const K& key, Func f )
448 return ensure_at( head(), key, f );
451 /// Deletes \p key from the list
452 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
454 RCU \p synchronize method can be called. RCU should not be locked.
456 Returns \p true if \p key is found and has been deleted, \p false otherwise
458 template <typename K>
459 bool erase( K const& key )
461 return erase_at( head(), key, intrusive_key_comparator() );
464 /// Deletes the item from the list using \p pred predicate for searching
466 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
467 but \p pred is used for key comparing.
468 \p Less functor has the interface like \p std::less.
469 \p pred must imply the same element order as the comparator used for building the list.
471 template <typename K, typename Less>
472 bool erase_with( K const& key, Less pred )
475 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
478 /// Deletes \p key from the list
479 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
480 The function searches an item with key \p key, calls \p f functor
481 and deletes the item. If \p key is not found, the functor is not called.
483 The functor \p Func interface:
486 void operator()(value_type& val) { ... }
490 RCU \p synchronize method can be called. RCU should not be locked.
492 Returns \p true if key is found and deleted, \p false otherwise
494 template <typename K, typename Func>
495 bool erase( K const& key, Func f )
497 return erase_at( head(), key, intrusive_key_comparator(), f );
500 /// Deletes the item from the list using \p pred predicate for searching
502 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
503 but \p pred is used for key comparing.
504 \p Less functor has the interface like \p std::less.
505 \p pred must imply the same element order as the comparator used for building the list.
507 template <typename K, typename Less, typename Func>
508 bool erase_with( K const& key, Less pred, Func f )
511 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
514 /// Extracts an item from the list
516 @anchor cds_nonintrusive_LazyKVList_rcu_extract
517 The function searches an item with key equal to \p key in the list,
518 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
519 If \p key is not found the function returns an empty \p exempt_ptr.
521 @note The function does NOT call RCU read-side lock or synchronization,
522 and does NOT dispose the item found. It just excludes the item from the list
523 and returns a pointer to item found.
524 You should manually lock RCU before calling this function.
527 #include <cds/urcu/general_buffered.h>
528 #include <cds/container/lazy_kvlist_rcu.h>
530 typedef cds::urcu::gc< general_buffered<> > rcu;
531 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
533 rcu_lazy_list theList;
536 rcu_lazy_list::exempt_ptr p;
538 // first, we should lock RCU
539 rcu_lazy_list::rcu_lock sl;
541 // Now, you can apply extract function
542 // Note that you must not delete the item found inside the RCU lock
543 p = theList.extract( 10 );
545 // do something with p
549 // Outside RCU lock section we may safely release extracted pointer.
550 // release() passes the pointer to RCU reclamation cycle.
554 template <typename K>
555 exempt_ptr extract( K const& key )
557 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator()));
560 /// Extracts an item from the list using \p pred predicate for searching
562 This function is the analog for \p extract(K const&).
563 The \p pred is a predicate used for key comparing.
564 \p Less has the interface like \p std::less.
565 \p pred must imply the same element order as \ref key_comparator.
567 template <typename K, typename Less>
568 exempt_ptr extract_with( K const& key, Less pred )
571 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
574 /// Finds the key \p key
575 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
576 The function searches the item with key equal to \p key
577 and returns \p true if it is found, and \p false otherwise
579 The function applies RCU lock internally.
581 template <typename Q>
582 bool find( Q const& key ) const
584 return find_at( head(), key, intrusive_key_comparator() );
587 /// Finds the key \p val using \p pred predicate for searching
589 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
590 but \p pred is used for key comparing.
591 \p Less functor has the interface like \p std::less.
592 \p pred must imply the same element order as the comparator used for building the list.
594 template <typename Q, typename Less>
595 bool find_with( Q const& key, Less pred ) const
598 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
601 /// Finds the key \p key and performs an action with it
602 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
603 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
604 The interface of \p Func functor is:
607 void operator()( value_type& item );
610 where \p item is the item found.
612 The functor may change <tt>item.second</tt> that is reference to value of node.
613 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
614 The function does not serialize simultaneous access to the list \p item. If such access is
615 possible you must provide your own synchronization schema to exclude unsafe item modifications.
617 The function applies RCU lock internally.
619 The function returns \p true if \p key is found, \p false otherwise.
621 template <typename Q, typename Func>
622 bool find( Q const& key, Func f ) const
624 return find_at( head(), key, intrusive_key_comparator(), f );
627 /// Finds the key \p val using \p pred predicate for searching
629 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
630 but \p pred is used for key comparing.
631 \p Less functor has the interface like \p std::less.
632 \p pred must imply the same element order as the comparator used for building the list.
634 template <typename Q, typename Less, typename Func>
635 bool find_with( Q const& key, Less pred, Func f ) const
638 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
641 /// Finds \p key and return the item found
642 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
643 The function searches the item with \p key and returns the pointer to item found.
644 If \p key is not found it returns \p nullptr.
646 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
648 RCU should be locked before call of this function.
649 Returned item is valid only while RCU is locked:
651 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
656 ord_list::rcu_lock lock;
658 ord_list::value_type * pVal = theList.get( 5 );
663 // Unlock RCU by rcu_lock destructor
664 // pVal can be freed at any time after RCU has been unlocked
668 template <typename K>
669 value_type * get( K const& key ) const
671 return get_at( head(), key, intrusive_key_comparator());
674 /// Finds \p key and return the item found
676 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
677 but \p pred is used for comparing the keys.
679 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
681 \p pred must imply the same element order as the comparator used for building the list.
683 template <typename K, typename Less>
684 value_type * get_with( K const& key, Less pred ) const
687 return get_at( head(), key, typename maker::template less_wrapper<Less>::type());
690 /// Checks if the list is empty
693 return base_class::empty();
696 /// Returns list's item count
698 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
699 this function always returns 0.
701 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
702 is empty. To check list emptyness use \ref empty() method.
706 return base_class::size();
717 bool insert_node_at( head_type& refHead, node_type * pNode )
719 assert( pNode != nullptr );
720 scoped_node_ptr p( pNode );
722 if ( base_class::insert_at( &refHead, *p )) {
730 template <typename K>
731 bool insert_at( head_type& refHead, const K& key )
733 return insert_node_at( refHead, alloc_node( key ));
736 template <typename K, typename V>
737 bool insert_at( head_type& refHead, const K& key, const V& val )
739 return insert_node_at( refHead, alloc_node( key, val ));
742 template <typename K, typename Func>
743 bool insert_with_at( head_type& refHead, const K& key, Func f )
745 scoped_node_ptr pNode( alloc_node( key ));
747 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
754 template <typename... Args>
755 bool emplace_at( head_type& refHead, Args&&... args )
757 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
760 template <typename K, typename Compare>
761 bool erase_at( head_type& refHead, K const& key, Compare cmp )
763 return base_class::erase_at( &refHead, key, cmp );
766 template <typename K, typename Compare, typename Func>
767 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
769 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
772 template <typename K, typename Func>
773 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
775 scoped_node_ptr pNode( alloc_node( key ));
777 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
778 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
779 if ( ret.first && ret.second )
785 template <typename K, typename Compare>
786 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
788 return base_class::extract_at( &refHead, key, cmp );
791 template <typename K, typename Compare>
792 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
794 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
797 template <typename K, typename Compare, typename Func>
798 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
800 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
803 template <typename K, typename Compare>
804 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
806 node_type * pNode = base_class::get_at( &refHead, val, cmp );
807 return pNode ? &pNode->m_Data : nullptr;
813 }} // namespace cds::container
815 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H