3 #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
4 #define __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
7 #include <functional> // ref
8 #include <cds/container/details/michael_list_base.h>
9 #include <cds/intrusive/michael_list_rcu.h>
10 #include <cds/container/details/make_michael_kvlist.h>
11 #include <cds/details/functor_wrapper.h>
13 namespace cds { namespace container {
15 /// Michael's ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
16 /** @ingroup cds_nonintrusive_list
17 \anchor cds_nonintrusive_MichaelKVList_rcu
19 This is key-value variation of non-intrusive \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
20 Like standard container, this implementation split a value stored into two part -
21 constant key and alterable value.
23 Usually, ordered single-linked list is used as a building block for the hash table implementation.
24 The complexity of searching is <tt>O(N)</tt>.
27 - \p RCU - one of \ref cds_urcu_gc "RCU type"
28 - \p Key - key type of an item stored in the list. It should be copy-constructible
29 - \p Value - value type stored in a list
30 - \p Traits - type traits, default is michael_list::type_traits
32 @note Before including <tt><cds/container/michael_kvlist_rcu.h></tt> you should include appropriate RCU header file,
33 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
35 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
36 argument. For example, the following traits-based declaration of Michael's list
38 #include <cds/urcu/general_buffered.h>
39 #include <cds/container/michael_kvlist_rcu.h>
40 // Declare comparator for the item
42 int operator ()( int i1, int i2 )
48 // Declare type_traits
49 struct my_traits: public cds::container::michael_list::type_traits
51 typedef my_compare compare;
54 // Declare traits-based list
55 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int, my_traits > traits_based_list;
58 is equivalent for the following option-based list
60 #include <cds/urcu/general_buffered.h>
61 #include <cds/container/michael_kvlist_rcu.h>
63 // my_compare is the same
65 // Declare option-based list
66 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int,
67 typename cds::container::michael_list::make_traits<
68 cds::container::opt::compare< my_compare > // item comparator option
73 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
74 - opt::compare - key comparison functor. No default functor is provided.
75 If the option is not specified, the opt::less is used.
76 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
77 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
78 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
79 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
80 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
81 or opt::v::sequential_consistent (sequentially consisnent memory model).
82 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
88 #ifdef CDS_DOXYGEN_INVOKED
89 typename Traits = michael_list::type_traits
94 class MichaelKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
95 #ifdef CDS_DOXYGEN_INVOKED
96 protected intrusive::MichaelList< cds::urcu::gc<RCU>, implementation_defined, Traits >
98 protected details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
102 typedef details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
103 typedef typename options::type base_class;
107 #ifdef CDS_DOXYGEN_INVOKED
108 typedef Key key_type ; ///< Key type
109 typedef Value mapped_type ; ///< Type of value stored in the list
110 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
112 typedef typename options::key_type key_type;
113 typedef typename options::value_type mapped_type;
114 typedef typename options::pair_type value_type;
117 typedef typename base_class::gc gc ; ///< Garbage collector used
118 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
119 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
120 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
121 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
122 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
123 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
125 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
126 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
130 typedef typename base_class::value_type node_type;
131 typedef typename options::cxx_allocator cxx_allocator;
132 typedef typename options::node_deallocator node_deallocator;
133 typedef typename options::type_traits::compare intrusive_key_comparator;
135 typedef typename base_class::atomic_node_ptr head_type;
139 /// pointer to extracted node
140 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
141 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
146 template <typename K>
147 static node_type * alloc_node(const K& key)
149 return cxx_allocator().New( key );
152 template <typename K, typename V>
153 static node_type * alloc_node( const K& key, const V& val )
155 return cxx_allocator().New( key, val );
158 template <typename K, typename... Args>
159 static node_type * alloc_node( K&& key, Args&&... args )
161 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
164 static void free_node( node_type * pNode )
166 cxx_allocator().Delete( pNode );
169 struct node_disposer {
170 void operator()( node_type * pNode )
175 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
179 return base_class::m_pHead;
182 head_type& head() const
184 return const_cast<head_type&>( base_class::m_pHead );
190 template <bool IsConst>
191 class iterator_type: protected base_class::template iterator_type<IsConst>
193 typedef typename base_class::template iterator_type<IsConst> iterator_base;
195 iterator_type( head_type const& pNode )
196 : iterator_base( pNode )
199 friend class MichaelKVList;
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 pair_ptr operator ->() const
224 typename iterator_base::value_ptr p = iterator_base::operator ->();
225 return p ? &(p->m_Data) : nullptr;
228 pair_ref operator *() const
230 typename iterator_base::value_ref p = iterator_base::operator *();
234 value_ref val() const
236 typename iterator_base::value_ptr p = iterator_base::operator ->();
237 assert( p != nullptr );
238 return p->m_Data.second;
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 return iterator( 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 equals to \p nullptr.
282 The returned value can be used only to control reaching the end of the list.
283 For empty list \code begin() == end() \endcode
290 /// Returns a forward const iterator addressing the first element in a list
292 const_iterator begin() const
294 return const_iterator( head() );
296 const_iterator cbegin()
298 return const_iterator( head() );
302 /// Returns an const iterator that addresses the location succeeding the last element in a list
304 const_iterator end() const
306 return const_iterator();
308 const_iterator cend()
310 return const_iterator();
315 /// Default constructor
317 Initializes empty 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 \ref 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 \ref key_type should be constructible from \p key of type \p K.
356 - The \ref 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 initialize 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 User-defined functor \p func should guarantee that during changing item's value no any other changes
381 could be made on this list's item by concurrent threads.
382 The user-defined functor can be passed by reference using \p std::ref
383 and it is called only if inserting is successful.
385 The key_type should be constructible from value of type \p K.
387 The function allows to split creating of new item into two part:
388 - create item from \p key;
389 - insert new item into the list;
390 - if inserting is successful, initialize the value of item by calling \p func functor
392 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
393 it is preferable that the initialization should be completed only if inserting is successful.
395 The function makes RCU lock internally.
397 template <typename K, typename Func>
398 bool insert_key( const K& key, Func func )
400 return insert_key_at( head(), key, func );
403 /// Ensures that the \p key exists in the list
405 The operation performs inserting or changing data with lock-free manner.
407 If the \p key not found in the list, then the new item created from \p key
408 is inserted into the list (note that in this case the \ref key_type should be
409 copy-constructible from type \p K).
410 Otherwise, the functor \p func is called with item found.
411 The functor \p Func may be a function with signature:
413 void func( bool bNew, value_type& item );
418 void operator()( bool bNew, value_type& item );
423 - \p bNew - \p true if the item has been inserted, \p false otherwise
424 - \p item - item of the list
426 The functor may change any fields of the \p item.second that is \ref mapped_type;
427 however, \p func must guarantee that during changing no any other modifications
428 could be made on this item by concurrent threads.
430 You may pass \p func argument by reference using \p std::ref
432 The function makes RCU lock internally.
434 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
435 \p second is true if new item has been added or \p false if the item with \p key
436 already is in the list.
438 template <typename K, typename Func>
439 std::pair<bool, bool> ensure( const K& key, Func f )
441 return ensure_at( head(), key, f );
444 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
446 Returns \p true if inserting successful, \p false otherwise.
448 The function makes RCU lock internally.
450 template <typename K, typename... Args>
451 bool emplace( K&& key, Args&&... args )
453 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
456 /// Deletes \p key from the list
457 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase
459 RCU \p synchronize method can be called. RCU should not be locked.
461 Returns \p true if \p key is found and has been deleted, \p false otherwise
463 template <typename K>
464 bool erase( K const& key )
466 return erase_at( head(), key, intrusive_key_comparator() );
469 /// Deletes the item from the list using \p pred predicate for searching
471 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase "erase(K const&)"
472 but \p pred is used for key comparing.
473 \p Less functor has the interface like \p std::less.
474 \p pred must imply the same element order as the comparator used for building the list.
476 template <typename K, typename Less>
477 bool erase_with( K const& key, Less pred )
479 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
482 /// Deletes \p key from the list
483 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase_func
484 The function searches an item with key \p key, calls \p f functor
485 and deletes the item. If \p key is not found, the functor is not called.
487 The functor \p Func interface:
490 void operator()(value_type& val) { ... }
493 The functor may be passed by reference with <tt>boost:ref</tt>
495 RCU \p synchronize method can be called. RCU should not be locked.
497 Return \p true if key is found and deleted, \p false otherwise
501 template <typename K, typename Func>
502 bool erase( K const& key, Func f )
504 return erase_at( head(), key, intrusive_key_comparator(), f );
507 /// Deletes the item from the list using \p pred predicate for searching
509 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase_func "erase(K const&, Func)"
510 but \p pred is used for key comparing.
511 \p Less functor has the interface like \p std::less.
512 \p pred must imply the same element order as the comparator used for building the list.
514 template <typename K, typename Less, typename Func>
515 bool erase_with( K const& key, Less pred, Func f )
517 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
520 /// Extracts an item from the list
522 @anchor cds_nonintrusive_MichaelKVList_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 pointer to an item found in \p dest argument.
525 If \p key is not found the function returns \p false.
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 lock RCU before calling this function.
533 #include <cds/urcu/general_buffered.h>
534 #include <cds/container/michael_kvlist_rcu.h>
536 typedef cds::urcu::gc< general_buffered<> > rcu;
537 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
539 rcu_michael_list theList;
542 rcu_michael_list::exempt_ptr p;
544 // first, we should lock RCU
545 rcu_michael_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 if ( theList.extract( p, 10 )) {
550 // do something with p
554 // Outside RCU lock section we may safely release extracted pointer.
555 // release() passes the pointer to RCU reclamation cycle.
559 template <typename K>
560 bool extract( exempt_ptr& dest, K const& key )
562 dest = extract_at( head(), key, intrusive_key_comparator() );
563 return !dest.empty();
566 /// Extracts an item from the list using \p pred predicate for searching
568 This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, 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 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
576 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
577 return !dest.empty();
580 /// Finds the key \p key
581 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_val
583 The function searches the item with key equal to \p key
584 and returns \p true if it is found, and \p false otherwise
586 The function makes RCU lock internally.
588 template <typename Q>
589 bool find( Q const& key ) const
591 return find_at( head(), key, intrusive_key_comparator() );
594 /// Finds the key \p val using \p pred predicate for searching
596 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_val "find(Q const&)"
597 but \p pred is used for key comparing.
598 \p Less functor has the interface like \p std::less.
599 \p pred must imply the same element order as the comparator used for building the list.
601 template <typename Q, typename Less>
602 bool find_with( Q const& key, Less pred ) const
604 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
607 /// Finds the key \p key and performs an action with it
608 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_func
609 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
610 The interface of \p Func functor is:
613 void operator()( value_type& item );
616 where \p item is the item found.
618 You may pass \p f argument by reference using \p std::ref.
620 The functor may change <tt>item.second</tt> that is reference to value of node.
621 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
622 The function does not serialize simultaneous access to the list \p item. If such access is
623 possible you must provide your own synchronization schema to exclude unsafe item modifications.
625 The function makes RCU lock internally.
627 The function returns \p true if \p key is found, \p false otherwise.
629 template <typename Q, typename Func>
630 bool find( Q const& key, Func f ) const
632 return find_at( head(), key, intrusive_key_comparator(), f );
635 /// Finds the key \p val using \p pred predicate for searching
637 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_func "find(Q const&, Func)"
638 but \p pred is used for key comparing.
639 \p Less functor has the interface like \p std::less.
640 \p pred must imply the same element order as the comparator used for building the list.
642 template <typename Q, typename Less, typename Func>
643 bool find_with( Q const& key, Less pred, Func f ) const
645 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
648 /// Finds \p key and return the item found
649 /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
650 The function searches the item with \p key and returns the pointer to item found.
651 If \p key is not found it returns \p nullptr.
653 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
655 RCU should be locked before call of this function.
656 Returned item is valid only while RCU is locked:
658 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
663 ord_list::rcu_lock lock;
665 ord_list::value_type * pVal = theList.get( 5 );
670 // Unlock RCU by rcu_lock destructor
671 // pVal can be freed at any time after RCU has been unlocked
675 template <typename K>
676 value_type * get( K const& key ) const
678 return get_at( head(), key, intrusive_key_comparator());
681 /// Finds \p key and return the item found
683 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_get "get(K const&)"
684 but \p pred is used for comparing the keys.
686 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
688 \p pred must imply the same element order as the comparator used for building the list.
690 template <typename K, typename Less>
691 value_type * get_with( K const& key, Less pred ) const
693 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
696 /// Checks if the list is empty
699 return base_class::empty();
702 /// Returns list's item count
704 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
705 this function always returns 0.
707 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
708 is empty. To check list emptyness use \ref empty() method.
712 return base_class::size();
717 Post-condition: the list is empty
726 bool insert_node_at( head_type& refHead, node_type * pNode )
728 assert( pNode != nullptr );
729 scoped_node_ptr p( pNode );
730 if ( base_class::insert_at( refHead, *pNode )) {
737 template <typename K>
738 bool insert_at( head_type& refHead, const K& key )
740 return insert_node_at( refHead, alloc_node( key ));
743 template <typename K, typename V>
744 bool insert_at( head_type& refHead, const K& key, const V& val )
746 return insert_node_at( refHead, alloc_node( key, val ));
749 template <typename K, typename Func>
750 bool insert_key_at( head_type& refHead, const K& key, Func f )
752 scoped_node_ptr pNode( alloc_node( key ));
754 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
761 template <typename K, typename... Args>
762 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
764 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
767 template <typename K, typename Func>
768 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
770 scoped_node_ptr pNode( alloc_node( key ));
772 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
773 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
774 if ( ret.first && ret.second )
780 template <typename K, typename Compare>
781 bool erase_at( head_type& refHead, K const& key, Compare cmp )
783 return base_class::erase_at( refHead, key, cmp );
786 template <typename K, typename Compare, typename Func>
787 bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
789 return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
792 template <typename K, typename Compare>
793 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
795 return base_class::extract_at( refHead, key, cmp );
798 template <typename K, typename Compare>
799 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
801 return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
804 template <typename K, typename Compare, typename Func>
805 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
807 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
810 template <typename K, typename Compare>
811 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
813 node_type * pNode = base_class::get_at( refHead, val, cmp );
814 return pNode ? &pNode->m_Data : nullptr;
820 }} // namespace cds::container
822 #endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H