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 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
134 node_type * p = cxx_allocator().New( key );
135 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
139 template <typename K, typename V>
140 static node_type * alloc_node( const K& key, const V& val )
142 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
143 node_type * p = cxx_allocator().New( key, val );
144 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
148 template <typename... Args>
149 static node_type * alloc_node( Args&&... args )
151 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
152 node_type * p = cxx_allocator().MoveNew( std::forward<Args>(args)... );
153 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
157 static void free_node( node_type * pNode )
159 cxx_allocator().Delete( pNode );
162 struct node_disposer {
163 void operator()( node_type * pNode )
168 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
172 return base_class::m_Head;
175 head_type& head() const
177 return const_cast<head_type&>( base_class::m_Head );
182 return base_class::m_Tail;
185 head_type& tail() const
187 return const_cast<head_type&>( base_class::m_Tail );
194 template <bool IsConst>
195 class iterator_type: protected base_class::template iterator_type<IsConst>
197 typedef typename base_class::template iterator_type<IsConst> iterator_base;
199 iterator_type( head_type const& pNode )
200 : iterator_base( const_cast<head_type *>(&pNode) )
202 iterator_type( head_type const * pNode )
203 : iterator_base( const_cast<head_type *>(pNode) )
206 friend class LazyKVList;
209 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
210 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
212 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
213 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
218 iterator_type( iterator_type const& src )
219 : iterator_base( src )
222 key_type const& key() const
224 typename iterator_base::value_ptr p = iterator_base::operator ->();
225 assert( p != nullptr );
226 return p->m_Data.first;
229 value_ref val() const
231 typename iterator_base::value_ptr p = iterator_base::operator ->();
232 assert( p != nullptr );
233 return p->m_Data.second;
236 pair_ptr operator ->() const
238 typename iterator_base::value_ptr p = iterator_base::operator ->();
239 return p ? &(p->m_Data) : nullptr;
242 pair_ref operator *() const
244 typename iterator_base::value_ref p = iterator_base::operator *();
249 iterator_type& operator ++()
251 iterator_base::operator ++();
256 bool operator ==(iterator_type<C> const& i ) const
258 return iterator_base::operator ==(i);
261 bool operator !=(iterator_type<C> const& i ) const
263 return iterator_base::operator !=(i);
270 typedef iterator_type<false> iterator;
272 /// Const forward iterator
273 typedef iterator_type<true> const_iterator;
275 /// Returns a forward iterator addressing the first element in a list
277 For empty list \code begin() == end() \endcode
281 iterator it( head() );
282 ++it ; // skip dummy head
286 /// Returns an iterator that addresses the location succeeding the last element in a list
288 Do not use the value returned by <tt>end</tt> function to access any item.
289 Internally, <tt>end</tt> returning value pointing to dummy tail node.
291 The returned value can be used only to control reaching the end of the list.
292 For empty list \code begin() == end() \endcode
296 return iterator( tail() );
299 /// Returns a forward const iterator addressing the first element in a list
301 const_iterator begin() const
303 const_iterator it( head() );
304 ++it; // skip dummy head
307 const_iterator cbegin() const
309 const_iterator it( head() );
310 ++it; // skip dummy head
315 /// Returns an const iterator that addresses the location succeeding the last element in a list
317 const_iterator end() const
319 return const_iterator( tail());
321 const_iterator cend() const
323 return const_iterator( tail());
328 /// Default constructor
332 /// Destructor clears the list
338 /// Inserts new node with key and default value
340 The function creates a node with \p key and default value, and then inserts the node created into the list.
343 - The \ref key_type should be constructible from value of type \p K.
344 In trivial case, \p K is equal to \p key_type.
345 - The \ref mapped_type should be default-constructible.
347 The function makes RCU lock internally.
349 Returns \p true if inserting successful, \p false otherwise.
351 template <typename K>
352 bool insert( const K& key )
354 return insert_at( head(), key );
357 /// Inserts new node with a key and a value
359 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
362 - The \p key_type should be constructible from \p key of type \p K.
363 - The \p mapped_type should be constructible from \p val of type \p V.
365 The function makes RCU lock internally.
367 Returns \p true if inserting successful, \p false otherwise.
369 template <typename K, typename V>
370 bool insert( const K& key, const V& val )
372 return insert_at( head(), key, val );
375 /// Inserts new node and initializes it by a functor
377 This function inserts new node with key \p key and if inserting is successful then it calls
378 \p func functor with signature
381 void operator()( value_type& item );
385 The argument \p item of user-defined functor \p func is the reference
386 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
387 The user-defined functor is called only if inserting is successful.
389 The key_type should be constructible from value of type \p K.
391 The function allows to split creating of new item into two part:
392 - create item from \p key;
393 - insert new item into the list;
394 - if inserting is successful, initialize the value of item by calling \p func functor
396 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
397 it is preferable that the initialization should be completed only if inserting is successful.
399 The function makes RCU lock internally.
401 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
403 template <typename K, typename Func>
404 bool insert_with( const K& key, Func func )
406 return insert_with_at( head(), key, func );
409 /// Inserts data of type \p mapped_type constructed from \p args
411 Returns \p true if inserting successful, \p false otherwise.
413 The function makes RCU lock internally.
415 template <typename... Args>
416 bool emplace( Args&&... args )
418 return emplace_at( head(), std::forward<Args>(args)... );
421 /// Ensures that the \p key exists in the list
423 The operation performs inserting or changing data with lock-free manner.
425 If the \p key not found in the list, then the new item created from \p key
426 is inserted into the list (note that in this case the \ref key_type should be
427 copy-constructible from type \p K).
428 Otherwise, the functor \p func is called with item found.
429 The functor \p Func may be a function with signature:
431 void func( bool bNew, value_type& item );
436 void operator()( bool bNew, value_type& item );
441 - \p bNew - \p true if the item has been inserted, \p false otherwise
442 - \p item - item of the list
444 The functor may change any fields of the \p item.second of type \p mapped_type.
446 The function makes RCU lock internally.
448 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
449 \p second is true if new item has been added or \p false if the item with \p key
450 already is in the list.
452 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
454 template <typename K, typename Func>
455 std::pair<bool, bool> ensure( const K& key, Func f )
457 return ensure_at( head(), key, f );
460 /// Deletes \p key from the list
461 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
463 RCU \p synchronize method can be called. RCU should not be locked.
465 Returns \p true if \p key is found and has been deleted, \p false otherwise
467 template <typename K>
468 bool erase( K const& key )
470 return erase_at( head(), key, intrusive_key_comparator() );
473 /// Deletes the item from the list using \p pred predicate for searching
475 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
476 but \p pred is used for key comparing.
477 \p Less functor has the interface like \p std::less.
478 \p pred must imply the same element order as the comparator used for building the list.
480 template <typename K, typename Less>
481 bool erase_with( K const& key, Less pred )
484 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
487 /// Deletes \p key from the list
488 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
489 The function searches an item with key \p key, calls \p f functor
490 and deletes the item. If \p key is not found, the functor is not called.
492 The functor \p Func interface:
495 void operator()(value_type& val) { ... }
499 RCU \p synchronize method can be called. RCU should not be locked.
501 Returns \p true if key is found and deleted, \p false otherwise
503 template <typename K, typename Func>
504 bool erase( K const& key, Func f )
506 return erase_at( head(), key, intrusive_key_comparator(), f );
509 /// Deletes the item from the list using \p pred predicate for searching
511 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
512 but \p pred is used for key comparing.
513 \p Less functor has the interface like \p std::less.
514 \p pred must imply the same element order as the comparator used for building the list.
516 template <typename K, typename Less, typename Func>
517 bool erase_with( K const& key, Less pred, Func f )
520 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
523 /// Extracts an item from the list
525 @anchor cds_nonintrusive_LazyKVList_rcu_extract
526 The function searches an item with key equal to \p key in the list,
527 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
528 If \p key is not found the function returns an empty \p exempt_ptr.
530 @note The function does NOT call RCU read-side lock or synchronization,
531 and does NOT dispose the item found. It just excludes the item from the list
532 and returns a pointer to item found.
533 You should manually lock RCU before calling this function.
536 #include <cds/urcu/general_buffered.h>
537 #include <cds/container/lazy_kvlist_rcu.h>
539 typedef cds::urcu::gc< general_buffered<> > rcu;
540 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
542 rcu_lazy_list theList;
545 rcu_lazy_list::exempt_ptr p;
547 // first, we should lock RCU
548 rcu_lazy_list::rcu_lock sl;
550 // Now, you can apply extract function
551 // Note that you must not delete the item found inside the RCU lock
552 p = theList.extract( 10 );
554 // do something with p
558 // Outside RCU lock section we may safely release extracted pointer.
559 // release() passes the pointer to RCU reclamation cycle.
563 template <typename K>
564 exempt_ptr extract( K const& key )
566 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator()));
569 /// Extracts an item from the list using \p pred predicate for searching
571 This function is the analog for \p extract(K const&).
572 The \p pred is a predicate used for key comparing.
573 \p Less has the interface like \p std::less.
574 \p pred must imply the same element order as \ref key_comparator.
576 template <typename K, typename Less>
577 exempt_ptr extract_with( K const& key, Less pred )
580 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
583 /// Finds the key \p key
584 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
585 The function searches the item with key equal to \p key
586 and returns \p true if it is found, and \p false otherwise
588 The function applies RCU lock internally.
590 template <typename Q>
591 bool find( Q const& key ) const
593 return find_at( head(), key, intrusive_key_comparator() );
596 /// Finds the key \p val using \p pred predicate for searching
598 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
599 but \p pred is used for key comparing.
600 \p Less functor has the interface like \p std::less.
601 \p pred must imply the same element order as the comparator used for building the list.
603 template <typename Q, typename Less>
604 bool find_with( Q const& key, Less pred ) const
607 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
610 /// Finds the key \p key and performs an action with it
611 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
612 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
613 The interface of \p Func functor is:
616 void operator()( value_type& item );
619 where \p item is the item found.
621 The functor may change <tt>item.second</tt> that is reference to value of node.
622 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
623 The function does not serialize simultaneous access to the list \p item. If such access is
624 possible you must provide your own synchronization schema to exclude unsafe item modifications.
626 The function applies RCU lock internally.
628 The function returns \p true if \p key is found, \p false otherwise.
630 template <typename Q, typename Func>
631 bool find( Q const& key, Func f ) const
633 return find_at( head(), key, intrusive_key_comparator(), f );
636 /// Finds the key \p val using \p pred predicate for searching
638 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
639 but \p pred is used for key comparing.
640 \p Less functor has the interface like \p std::less.
641 \p pred must imply the same element order as the comparator used for building the list.
643 template <typename Q, typename Less, typename Func>
644 bool find_with( Q const& key, Less pred, Func f ) const
647 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
650 /// Finds \p key and return the item found
651 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
652 The function searches the item with \p key and returns the pointer to item found.
653 If \p key is not found it returns \p nullptr.
655 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
657 RCU should be locked before call of this function.
658 Returned item is valid only while RCU is locked:
660 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
665 ord_list::rcu_lock lock;
667 ord_list::value_type * pVal = theList.get( 5 );
672 // Unlock RCU by rcu_lock destructor
673 // pVal can be freed at any time after RCU has been unlocked
677 template <typename K>
678 value_type * get( K const& key ) const
680 return get_at( head(), key, intrusive_key_comparator());
683 /// Finds \p key and return the item found
685 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
686 but \p pred is used for comparing the keys.
688 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
690 \p pred must imply the same element order as the comparator used for building the list.
692 template <typename K, typename Less>
693 value_type * get_with( K const& key, Less pred ) const
696 return get_at( head(), key, typename maker::template less_wrapper<Less>::type());
699 /// Checks if the list is empty
702 return base_class::empty();
705 /// Returns list's item count
707 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
708 this function always returns 0.
710 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
711 is empty. To check list emptyness use \ref empty() method.
715 return base_class::size();
726 bool insert_node_at( head_type& refHead, node_type * pNode )
728 assert( pNode != nullptr );
729 scoped_node_ptr p( pNode );
731 if ( base_class::insert_at( &refHead, *p )) {
739 template <typename K>
740 bool insert_at( head_type& refHead, const K& key )
742 return insert_node_at( refHead, alloc_node( key ));
745 template <typename K, typename V>
746 bool insert_at( head_type& refHead, const K& key, const V& val )
748 return insert_node_at( refHead, alloc_node( key, val ));
751 template <typename K, typename Func>
752 bool insert_with_at( head_type& refHead, const K& key, Func f )
754 scoped_node_ptr pNode( alloc_node( key ));
756 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
763 template <typename... Args>
764 bool emplace_at( head_type& refHead, Args&&... args )
766 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
769 template <typename K, typename Compare>
770 bool erase_at( head_type& refHead, K const& key, Compare cmp )
772 return base_class::erase_at( &refHead, key, cmp );
775 template <typename K, typename Compare, typename Func>
776 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
778 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
781 template <typename K, typename Func>
782 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
784 scoped_node_ptr pNode( alloc_node( key ));
786 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
787 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
788 if ( ret.first && ret.second )
794 template <typename K, typename Compare>
795 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
797 return base_class::extract_at( &refHead, key, cmp );
800 template <typename K, typename Compare>
801 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
803 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
806 template <typename K, typename Compare, typename Func>
807 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
809 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
812 template <typename K, typename Compare>
813 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
815 node_type * pNode = base_class::get_at( &refHead, val, cmp );
816 return pNode ? &pNode->m_Data : nullptr;
822 }} // namespace cds::container
824 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H