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>
12 namespace cds { namespace container {
14 /// Michael's ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
15 /** @ingroup cds_nonintrusive_list
16 \anchor cds_nonintrusive_MichaelKVList_rcu
18 This is key-value variation of non-intrusive \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
19 Like standard container, this implementation split a value stored into two part -
20 constant key and alterable value.
22 Usually, ordered single-linked list is used as a building block for the hash table implementation.
23 The complexity of searching is <tt>O(N)</tt>.
26 - \p RCU - one of \ref cds_urcu_gc "RCU type"
27 - \p Key - key type of an item stored in the list. It should be copy-constructible
28 - \p Value - value type stored in a list
29 - \p Traits - type traits, default is michael_list::type_traits
31 @note Before including <tt><cds/container/michael_kvlist_rcu.h></tt> you should include appropriate RCU header file,
32 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
34 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
35 argument. For example, the following traits-based declaration of Michael's list
37 #include <cds/urcu/general_buffered.h>
38 #include <cds/container/michael_kvlist_rcu.h>
39 // Declare comparator for the item
41 int operator ()( int i1, int i2 )
47 // Declare type_traits
48 struct my_traits: public cds::container::michael_list::type_traits
50 typedef my_compare compare;
53 // Declare traits-based list
54 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int, my_traits > traits_based_list;
57 is equivalent for the following option-based list
59 #include <cds/urcu/general_buffered.h>
60 #include <cds/container/michael_kvlist_rcu.h>
62 // my_compare is the same
64 // Declare option-based list
65 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, int,
66 typename cds::container::michael_list::make_traits<
67 cds::container::opt::compare< my_compare > // item comparator option
72 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
73 - opt::compare - key comparison functor. No default functor is provided.
74 If the option is not specified, the opt::less is used.
75 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
76 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
77 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
78 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
79 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
80 or opt::v::sequential_consistent (sequentially consisnent memory model).
81 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
87 #ifdef CDS_DOXYGEN_INVOKED
88 typename Traits = michael_list::type_traits
93 class MichaelKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
94 #ifdef CDS_DOXYGEN_INVOKED
95 protected intrusive::MichaelList< cds::urcu::gc<RCU>, implementation_defined, Traits >
97 protected details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
101 typedef details::make_michael_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
102 typedef typename options::type base_class;
106 #ifdef CDS_DOXYGEN_INVOKED
107 typedef Key key_type ; ///< Key type
108 typedef Value mapped_type ; ///< Type of value stored in the list
109 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
111 typedef typename options::key_type key_type;
112 typedef typename options::value_type mapped_type;
113 typedef typename options::pair_type value_type;
116 typedef typename base_class::gc gc ; ///< Garbage collector used
117 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
118 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
119 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
120 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
121 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
124 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
125 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
129 typedef typename base_class::value_type node_type;
130 typedef typename options::cxx_allocator cxx_allocator;
131 typedef typename options::node_deallocator node_deallocator;
132 typedef typename options::type_traits::compare intrusive_key_comparator;
134 typedef typename base_class::atomic_node_ptr head_type;
138 /// pointer to extracted node
139 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
140 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
145 template <typename K>
146 static node_type * alloc_node(const K& key)
148 return cxx_allocator().New( key );
151 template <typename K, typename V>
152 static node_type * alloc_node( const K& key, const V& val )
154 return cxx_allocator().New( key, val );
157 template <typename K, typename... Args>
158 static node_type * alloc_node( K&& key, Args&&... args )
160 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
163 static void free_node( node_type * pNode )
165 cxx_allocator().Delete( pNode );
168 struct node_disposer {
169 void operator()( node_type * pNode )
174 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
178 return base_class::m_pHead;
181 head_type& head() const
183 return const_cast<head_type&>( base_class::m_pHead );
189 template <bool IsConst>
190 class iterator_type: protected base_class::template iterator_type<IsConst>
192 typedef typename base_class::template iterator_type<IsConst> iterator_base;
194 iterator_type( head_type const& pNode )
195 : iterator_base( pNode )
198 friend class MichaelKVList;
201 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
202 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
204 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
205 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
210 iterator_type( iterator_type const& src )
211 : iterator_base( src )
214 key_type const& key() const
216 typename iterator_base::value_ptr p = iterator_base::operator ->();
217 assert( p != nullptr );
218 return p->m_Data.first;
221 pair_ptr operator ->() const
223 typename iterator_base::value_ptr p = iterator_base::operator ->();
224 return p ? &(p->m_Data) : nullptr;
227 pair_ref operator *() const
229 typename iterator_base::value_ref p = iterator_base::operator *();
233 value_ref val() const
235 typename iterator_base::value_ptr p = iterator_base::operator ->();
236 assert( p != nullptr );
237 return p->m_Data.second;
241 iterator_type& operator ++()
243 iterator_base::operator ++();
248 bool operator ==(iterator_type<C> const& i ) const
250 return iterator_base::operator ==(i);
253 bool operator !=(iterator_type<C> const& i ) const
255 return iterator_base::operator !=(i);
262 typedef iterator_type<false> iterator;
264 /// Const forward iterator
265 typedef iterator_type<true> const_iterator;
267 /// Returns a forward iterator addressing the first element in a list
269 For empty list \code begin() == end() \endcode
273 return iterator( head() );
276 /// Returns an iterator that addresses the location succeeding the last element in a list
278 Do not use the value returned by <tt>end</tt> function to access any item.
279 Internally, <tt>end</tt> returning value equals to \p nullptr.
281 The returned value can be used only to control reaching the end of the list.
282 For empty list \code begin() == end() \endcode
289 /// Returns a forward const iterator addressing the first element in a list
291 const_iterator begin() const
293 return const_iterator( head() );
295 const_iterator cbegin()
297 return const_iterator( head() );
301 /// Returns an const iterator that addresses the location succeeding the last element in a list
303 const_iterator end() const
305 return const_iterator();
307 const_iterator cend()
309 return const_iterator();
314 /// Default constructor
316 Initializes empty list
330 /// Inserts new node with key and default value
332 The function creates a node with \p key and default value, and then inserts the node created into the list.
335 - The \ref key_type should be constructible from value of type \p K.
336 In trivial case, \p K is equal to \ref key_type.
337 - The \ref mapped_type should be default-constructible.
339 The function makes RCU lock internally.
341 Returns \p true if inserting successful, \p false otherwise.
343 template <typename K>
344 bool insert( const K& key )
346 return insert_at( head(), key );
349 /// Inserts new node with a key and a value
351 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
354 - The \ref key_type should be constructible from \p key of type \p K.
355 - The \ref mapped_type should be constructible from \p val of type \p V.
357 The function makes RCU lock internally.
359 Returns \p true if inserting successful, \p false otherwise.
361 template <typename K, typename V>
362 bool insert( const K& key, const V& val )
364 return insert_at( head(), key, val );
367 /// Inserts new node and initialize it by a functor
369 This function inserts new node with key \p key and if inserting is successful then it calls
370 \p func functor with signature
373 void operator()( value_type& item );
377 The argument \p item of user-defined functor \p func is the reference
378 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
379 User-defined functor \p func should guarantee that during changing item's value no any other changes
380 could be made on this list's item by concurrent threads.
381 The user-defined functor can be passed by reference using \p std::ref
382 and it is called only if inserting is successful.
384 The key_type should be constructible from value of type \p K.
386 The function allows to split creating of new item into two part:
387 - create item from \p key;
388 - insert new item into the list;
389 - if inserting is successful, initialize the value of item by calling \p func functor
391 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
392 it is preferable that the initialization should be completed only if inserting is successful.
394 The function makes RCU lock internally.
396 template <typename K, typename Func>
397 bool insert_key( const K& key, Func func )
399 return insert_key_at( head(), key, func );
402 /// Ensures that the \p key exists in the list
404 The operation performs inserting or changing data with lock-free manner.
406 If the \p key not found in the list, then the new item created from \p key
407 is inserted into the list (note that in this case the \ref key_type should be
408 copy-constructible from type \p K).
409 Otherwise, the functor \p func is called with item found.
410 The functor \p Func may be a function with signature:
412 void func( bool bNew, value_type& item );
417 void operator()( bool bNew, value_type& item );
422 - \p bNew - \p true if the item has been inserted, \p false otherwise
423 - \p item - item of the list
425 The functor may change any fields of the \p item.second that is \ref mapped_type;
426 however, \p func must guarantee that during changing no any other modifications
427 could be made on this item by concurrent threads.
429 You may pass \p func argument by reference using \p std::ref
431 The function makes RCU lock internally.
433 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
434 \p second is true if new item has been added or \p false if the item with \p key
435 already is in the list.
437 template <typename K, typename Func>
438 std::pair<bool, bool> ensure( const K& key, Func f )
440 return ensure_at( head(), key, f );
443 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
445 Returns \p true if inserting successful, \p false otherwise.
447 The function makes RCU lock internally.
449 template <typename K, typename... Args>
450 bool emplace( K&& key, Args&&... args )
452 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
455 /// Deletes \p key from the list
456 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase
458 RCU \p synchronize method can be called. RCU should not be locked.
460 Returns \p true if \p key is found and has been deleted, \p false otherwise
462 template <typename K>
463 bool erase( K const& key )
465 return erase_at( head(), key, intrusive_key_comparator() );
468 /// Deletes the item from the list using \p pred predicate for searching
470 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase "erase(K const&)"
471 but \p pred is used for key comparing.
472 \p Less functor has the interface like \p std::less.
473 \p pred must imply the same element order as the comparator used for building the list.
475 template <typename K, typename Less>
476 bool erase_with( K const& key, Less pred )
478 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
481 /// Deletes \p key from the list
482 /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase_func
483 The function searches an item with key \p key, calls \p f functor
484 and deletes the item. If \p key is not found, the functor is not called.
486 The functor \p Func interface:
489 void operator()(value_type& val) { ... }
492 The functor may be passed by reference with <tt>boost:ref</tt>
494 RCU \p synchronize method can be called. RCU should not be locked.
496 Return \p true if key is found and deleted, \p false otherwise
500 template <typename K, typename Func>
501 bool erase( K const& key, Func f )
503 return erase_at( head(), key, intrusive_key_comparator(), f );
506 /// Deletes the item from the list using \p pred predicate for searching
508 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase_func "erase(K const&, Func)"
509 but \p pred is used for key comparing.
510 \p Less functor has the interface like \p std::less.
511 \p pred must imply the same element order as the comparator used for building the list.
513 template <typename K, typename Less, typename Func>
514 bool erase_with( K const& key, Less pred, Func f )
516 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
519 /// Extracts an item from the list
521 @anchor cds_nonintrusive_MichaelKVList_rcu_extract
522 The function searches an item with key equal to \p key in the list,
523 unlinks it from the list, and returns pointer to an item found in \p dest argument.
524 If \p key is not found the function returns \p false.
526 @note The function does NOT call RCU read-side lock or synchronization,
527 and does NOT dispose the item found. It just excludes the item from the list
528 and returns a pointer to item found.
529 You should lock RCU before calling this function.
532 #include <cds/urcu/general_buffered.h>
533 #include <cds/container/michael_kvlist_rcu.h>
535 typedef cds::urcu::gc< general_buffered<> > rcu;
536 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
538 rcu_michael_list theList;
541 rcu_michael_list::exempt_ptr p;
543 // first, we should lock RCU
544 rcu_michael_list::rcu_lock sl;
546 // Now, you can apply extract function
547 // Note that you must not delete the item found inside the RCU lock
548 if ( theList.extract( p, 10 )) {
549 // do something with p
553 // Outside RCU lock section we may safely release extracted pointer.
554 // release() passes the pointer to RCU reclamation cycle.
558 template <typename K>
559 bool extract( exempt_ptr& dest, K const& key )
561 dest = extract_at( head(), key, intrusive_key_comparator() );
562 return !dest.empty();
565 /// Extracts an item from the list using \p pred predicate for searching
567 This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, K const&)".
568 The \p pred is a predicate used for key comparing.
569 \p Less has the interface like \p std::less.
570 \p pred must imply the same element order as \ref key_comparator.
572 template <typename K, typename Less>
573 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
575 dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
576 return !dest.empty();
579 /// Finds the key \p key
580 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_val
582 The function searches the item with key equal to \p key
583 and returns \p true if it is found, and \p false otherwise
585 The function makes RCU lock internally.
587 template <typename Q>
588 bool find( Q const& key ) const
590 return find_at( head(), key, intrusive_key_comparator() );
593 /// Finds the key \p val using \p pred predicate for searching
595 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_val "find(Q const&)"
596 but \p pred is used for key comparing.
597 \p Less functor has the interface like \p std::less.
598 \p pred must imply the same element order as the comparator used for building the list.
600 template <typename Q, typename Less>
601 bool find_with( Q const& key, Less pred ) const
603 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
606 /// Finds the key \p key and performs an action with it
607 /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_func
608 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
609 The interface of \p Func functor is:
612 void operator()( value_type& item );
615 where \p item is the item found.
617 You may pass \p f argument by reference using \p std::ref.
619 The functor may change <tt>item.second</tt> that is reference to value of node.
620 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
621 The function does not serialize simultaneous access to the list \p item. If such access is
622 possible you must provide your own synchronization schema to exclude unsafe item modifications.
624 The function makes RCU lock internally.
626 The function returns \p true if \p key is found, \p false otherwise.
628 template <typename Q, typename Func>
629 bool find( Q const& key, Func f ) const
631 return find_at( head(), key, intrusive_key_comparator(), f );
634 /// Finds the key \p val using \p pred predicate for searching
636 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_func "find(Q const&, Func)"
637 but \p pred is used for key comparing.
638 \p Less functor has the interface like \p std::less.
639 \p pred must imply the same element order as the comparator used for building the list.
641 template <typename Q, typename Less, typename Func>
642 bool find_with( Q const& key, Less pred, Func f ) const
644 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
647 /// Finds \p key and return the item found
648 /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
649 The function searches the item with \p key and returns the pointer to item found.
650 If \p key is not found it returns \p nullptr.
652 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
654 RCU should be locked before call of this function.
655 Returned item is valid only while RCU is locked:
657 typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
662 ord_list::rcu_lock lock;
664 ord_list::value_type * pVal = theList.get( 5 );
669 // Unlock RCU by rcu_lock destructor
670 // pVal can be freed at any time after RCU has been unlocked
674 template <typename K>
675 value_type * get( K const& key ) const
677 return get_at( head(), key, intrusive_key_comparator());
680 /// Finds \p key and return the item found
682 The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_get "get(K const&)"
683 but \p pred is used for comparing the keys.
685 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
687 \p pred must imply the same element order as the comparator used for building the list.
689 template <typename K, typename Less>
690 value_type * get_with( K const& key, Less pred ) const
692 return get_at( head(), key, typename options::template less_wrapper<Less>::type());
695 /// Checks if the list is empty
698 return base_class::empty();
701 /// Returns list's item count
703 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
704 this function always returns 0.
706 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
707 is empty. To check list emptyness use \ref empty() method.
711 return base_class::size();
716 Post-condition: the list is empty
725 bool insert_node_at( head_type& refHead, node_type * pNode )
727 assert( pNode != nullptr );
728 scoped_node_ptr p( pNode );
729 if ( base_class::insert_at( refHead, *pNode )) {
736 template <typename K>
737 bool insert_at( head_type& refHead, const K& key )
739 return insert_node_at( refHead, alloc_node( key ));
742 template <typename K, typename V>
743 bool insert_at( head_type& refHead, const K& key, const V& val )
745 return insert_node_at( refHead, alloc_node( key, val ));
748 template <typename K, typename Func>
749 bool insert_key_at( head_type& refHead, const K& key, Func f )
751 scoped_node_ptr pNode( alloc_node( key ));
753 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
760 template <typename K, typename... Args>
761 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
763 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
766 template <typename K, typename Func>
767 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
769 scoped_node_ptr pNode( alloc_node( key ));
771 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
772 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
773 if ( ret.first && ret.second )
779 template <typename K, typename Compare>
780 bool erase_at( head_type& refHead, K const& key, Compare cmp )
782 return base_class::erase_at( refHead, key, cmp );
785 template <typename K, typename Compare, typename Func>
786 bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
788 return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
791 template <typename K, typename Compare>
792 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
794 return base_class::extract_at( refHead, key, cmp );
797 template <typename K, typename Compare>
798 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
800 return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
803 template <typename K, typename Compare, typename Func>
804 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
806 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
809 template <typename K, typename Compare>
810 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
812 node_type * pNode = base_class::get_at( refHead, val, cmp );
813 return pNode ? &pNode->m_Data : nullptr;
819 }} // namespace cds::container
821 #endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H