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 * get_result;
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 /// Ensures that the \p key exists in the list
416 The operation performs inserting or changing data with lock-free manner.
418 If the \p key not found in the list, then the new item created from \p key
419 is inserted into the list (note that in this case the \ref key_type should be
420 copy-constructible from type \p K).
421 Otherwise, the functor \p func is called with item found.
422 The functor \p Func may be a function with signature:
424 void func( bool bNew, value_type& item );
429 void operator()( bool bNew, value_type& item );
434 - \p bNew - \p true if the item has been inserted, \p false otherwise
435 - \p item - item of the list
437 The functor may change any fields of the \p item.second of type \p mapped_type.
439 The function makes RCU lock internally.
441 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
442 \p second is true if new item has been added or \p false if the item with \p key
443 already is in the list.
445 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
447 template <typename K, typename Func>
448 std::pair<bool, bool> ensure( const K& key, Func f )
450 return ensure_at( head(), key, f );
453 /// Deletes \p key from the list
454 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
456 RCU \p synchronize method can be called. RCU should not be locked.
458 Returns \p true if \p key is found and has been deleted, \p false otherwise
460 template <typename K>
461 bool erase( K const& key )
463 return erase_at( head(), key, intrusive_key_comparator() );
466 /// Deletes the item from the list using \p pred predicate for searching
468 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
469 but \p pred is used for key comparing.
470 \p Less functor has the interface like \p std::less.
471 \p pred must imply the same element order as the comparator used for building the list.
473 template <typename K, typename Less>
474 bool erase_with( K const& key, Less pred )
477 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
480 /// Deletes \p key from the list
481 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
482 The function searches an item with key \p key, calls \p f functor
483 and deletes the item. If \p key is not found, the functor is not called.
485 The functor \p Func interface:
488 void operator()(value_type& val) { ... }
492 RCU \p synchronize method can be called. RCU should not be locked.
494 Returns \p true if key is found and deleted, \p false otherwise
496 template <typename K, typename Func>
497 bool erase( K const& key, Func f )
499 return erase_at( head(), key, intrusive_key_comparator(), f );
502 /// Deletes the item from the list using \p pred predicate for searching
504 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
505 but \p pred is used for key comparing.
506 \p Less functor has the interface like \p std::less.
507 \p pred must imply the same element order as the comparator used for building the list.
509 template <typename K, typename Less, typename Func>
510 bool erase_with( K const& key, Less pred, Func f )
513 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
516 /// Extracts an item from the list
518 @anchor cds_nonintrusive_LazyKVList_rcu_extract
519 The function searches an item with key equal to \p key in the list,
520 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
521 If \p key is not found the function returns an empty \p exempt_ptr.
523 @note The function does NOT call RCU read-side lock or synchronization,
524 and does NOT dispose the item found. It just excludes the item from the list
525 and returns a pointer to item found.
526 You should manually lock RCU before calling this function.
529 #include <cds/urcu/general_buffered.h>
530 #include <cds/container/lazy_kvlist_rcu.h>
532 typedef cds::urcu::gc< general_buffered<> > rcu;
533 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
535 rcu_lazy_list theList;
538 rcu_lazy_list::exempt_ptr p;
540 // first, we should lock RCU
541 rcu_lazy_list::rcu_lock sl;
543 // Now, you can apply extract function
544 // Note that you must not delete the item found inside the RCU lock
545 p = theList.extract( 10 );
547 // do something with p
551 // Outside RCU lock section we may safely release extracted pointer.
552 // release() passes the pointer to RCU reclamation cycle.
556 template <typename K>
557 exempt_ptr extract( K const& key )
559 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator()));
562 /// Extracts an item from the list using \p pred predicate for searching
564 This function is the analog for \p extract(K const&).
565 The \p pred is a predicate used for key comparing.
566 \p Less has the interface like \p std::less.
567 \p pred must imply the same element order as \ref key_comparator.
569 template <typename K, typename Less>
570 exempt_ptr extract_with( K const& key, Less pred )
573 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
576 /// Finds the key \p key
577 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
578 The function searches the item with key equal to \p key
579 and returns \p true if it is found, and \p false otherwise
581 The function applies RCU lock internally.
583 template <typename Q>
584 bool find( Q const& key ) const
586 return find_at( head(), key, intrusive_key_comparator() );
589 /// Finds the key \p val using \p pred predicate for searching
591 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
592 but \p pred is used for key comparing.
593 \p Less functor has the interface like \p std::less.
594 \p pred must imply the same element order as the comparator used for building the list.
596 template <typename Q, typename Less>
597 bool find_with( Q const& key, Less pred ) const
600 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
603 /// Finds the key \p key and performs an action with it
604 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
605 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
606 The interface of \p Func functor is:
609 void operator()( value_type& item );
612 where \p item is the item found.
614 The functor may change <tt>item.second</tt> that is reference to value of node.
615 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
616 The function does not serialize simultaneous access to the list \p item. If such access is
617 possible you must provide your own synchronization schema to exclude unsafe item modifications.
619 The function applies RCU lock internally.
621 The function returns \p true if \p key is found, \p false otherwise.
623 template <typename Q, typename Func>
624 bool find( Q const& key, Func f ) const
626 return find_at( head(), key, intrusive_key_comparator(), f );
629 /// Finds the key \p val using \p pred predicate for searching
631 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
632 but \p pred is used for key comparing.
633 \p Less functor has the interface like \p std::less.
634 \p pred must imply the same element order as the comparator used for building the list.
636 template <typename Q, typename Less, typename Func>
637 bool find_with( Q const& key, Less pred, Func f ) const
640 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
643 /// Finds \p key and return the item found
644 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
645 The function searches the item with \p key and returns the pointer to item found.
646 If \p key is not found it returns \p nullptr.
648 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
650 RCU should be locked before call of this function.
651 Returned item is valid only while RCU is locked:
653 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
658 ord_list::rcu_lock lock;
660 ord_list::value_type * pVal = theList.get( 5 );
665 // Unlock RCU by rcu_lock destructor
666 // pVal can be freed at any time after RCU has been unlocked
670 template <typename K>
671 value_type * get( K const& key ) const
673 return get_at( head(), key, intrusive_key_comparator());
676 /// Finds \p key and return the item found
678 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
679 but \p pred is used for comparing the keys.
681 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
683 \p pred must imply the same element order as the comparator used for building the list.
685 template <typename K, typename Less>
686 value_type * get_with( K const& key, Less pred ) const
689 return get_at( head(), key, typename maker::template less_wrapper<Less>::type());
692 /// Checks if the list is empty
695 return base_class::empty();
698 /// Returns list's item count
700 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
701 this function always returns 0.
703 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
704 is empty. To check list emptyness use \ref empty() method.
708 return base_class::size();
719 bool insert_node_at( head_type& refHead, node_type * pNode )
721 assert( pNode != nullptr );
722 scoped_node_ptr p( pNode );
724 if ( base_class::insert_at( &refHead, *p )) {
732 template <typename K>
733 bool insert_at( head_type& refHead, const K& key )
735 return insert_node_at( refHead, alloc_node( key ));
738 template <typename K, typename V>
739 bool insert_at( head_type& refHead, const K& key, const V& val )
741 return insert_node_at( refHead, alloc_node( key, val ));
744 template <typename K, typename Func>
745 bool insert_with_at( head_type& refHead, const K& key, Func f )
747 scoped_node_ptr pNode( alloc_node( key ));
749 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
756 template <typename... Args>
757 bool emplace_at( head_type& refHead, Args&&... args )
759 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
762 template <typename K, typename Compare>
763 bool erase_at( head_type& refHead, K const& key, Compare cmp )
765 return base_class::erase_at( &refHead, key, cmp );
768 template <typename K, typename Compare, typename Func>
769 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
771 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
774 template <typename K, typename Func>
775 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
777 scoped_node_ptr pNode( alloc_node( key ));
779 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
780 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
781 if ( ret.first && ret.second )
787 template <typename K, typename Compare>
788 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
790 return base_class::extract_at( &refHead, key, cmp );
793 template <typename K, typename Compare>
794 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
796 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
799 template <typename K, typename Compare, typename Func>
800 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
802 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
805 template <typename K, typename Compare>
806 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
808 node_type * pNode = base_class::get_at( &refHead, val, cmp );
809 return pNode ? &pNode->m_Data : nullptr;
815 }} // namespace cds::container
817 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H