3 #ifndef __CDS_CONTAINER_IMPL_MICHAEL_KVLIST_H
4 #define __CDS_CONTAINER_IMPL_MICHAEL_KVLIST_H
7 #include <functional> // ref
8 #include <cds/container/details/guarded_ptr_cast.h>
10 namespace cds { namespace container {
12 /// Michael's ordered list (key-value pair)
13 /** @ingroup cds_nonintrusive_list
14 \anchor cds_nonintrusive_MichaelKVList_gc
16 This is key-value variation of non-intrusive MichaelList.
17 Like standard container, this implementation split a value stored into two part -
18 constant key and alterable value.
20 Usually, ordered single-linked list is used as a building block for the hash table implementation.
21 The complexity of searching is <tt>O(N)</tt>.
24 - \p GC - garbage collector used
25 - \p Key - key type of an item stored in the list. It should be copy-constructible
26 - \p Value - value type stored in a list
27 - \p Traits - type traits, default is michael_list::type_traits
29 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
30 argument. For example, the following traits-based declaration of gc::HP Michael's list
32 #include <cds/container/michael_kvlist_hp.h>
33 // Declare comparator for the item
35 int operator ()( int i1, int i2 )
41 // Declare type_traits
42 struct my_traits: public cds::container::michael_list::type_traits
44 typedef my_compare compare;
47 // Declare traits-based list
48 typedef cds::container::MichaelKVList< cds::gc::HP, int, int, my_traits > traits_based_list;
51 is equivalent for the following option-based list
53 #include <cds/container/michael_kvlist_hp.h>
55 // my_compare is the same
57 // Declare option-based list
58 typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
59 typename cds::container::michael_list::make_traits<
60 cds::container::opt::compare< my_compare > // item comparator option
65 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
66 - opt::compare - key comparison functor. No default functor is provided.
67 If the option is not specified, the opt::less is used.
68 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
69 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
70 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
71 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
72 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
73 or opt::v::sequential_consistent (sequentially consisnent memory model).
76 There are different specializations of this template for each garbage collecting schema used.
77 You should include appropriate .h-file depending on GC you are using:
78 - for gc::HP: \code #include <cds/container/michael_kvlist_hp.h> \endcode
79 - for gc::DHP: \code #include <cds/container/michael_kvlist_dhp.h> \endcode
80 - for \ref cds_urcu_desc "RCU": \code #include <cds/container/michael_kvlist_rcu.h> \endcode
81 - for gc::nogc: \code #include <cds/container/michael_kvlist_nogc.h> \endcode
87 #ifdef CDS_DOXYGEN_INVOKED
88 typename Traits = michael_list::type_traits
94 #ifdef CDS_DOXYGEN_INVOKED
95 protected intrusive::MichaelList< GC, implementation_defined, Traits >
97 protected details::make_michael_kvlist< GC, Key, Value, Traits >::type
101 typedef details::make_michael_kvlist< GC, 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
125 typedef typename base_class::value_type node_type;
126 typedef typename options::cxx_allocator cxx_allocator;
127 typedef typename options::node_deallocator node_deallocator;
128 typedef typename options::type_traits::compare intrusive_key_comparator;
130 typedef typename base_class::atomic_node_ptr head_type;
135 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_map<node_type, value_type> > guarded_ptr;
139 template <typename K>
140 static node_type * alloc_node(const K& key)
142 return cxx_allocator().New( key );
145 template <typename K, typename V>
146 static node_type * alloc_node( const K& key, const V& val )
148 return cxx_allocator().New( key, val );
151 template <typename K, typename... Args>
152 static node_type * alloc_node( K&& key, Args&&... args )
154 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
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_pHead;
175 head_type const& head() const
177 return base_class::m_pHead;
183 template <bool IsConst>
184 class iterator_type: protected base_class::template iterator_type<IsConst>
186 typedef typename base_class::template iterator_type<IsConst> iterator_base;
188 iterator_type( head_type const& pNode )
189 : iterator_base( pNode )
192 friend class MichaelKVList;
195 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
196 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
198 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
199 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
204 iterator_type( iterator_type const& src )
205 : iterator_base( src )
208 key_type const& key() const
210 typename iterator_base::value_ptr p = iterator_base::operator ->();
211 assert( p != nullptr );
212 return p->m_Data.first;
215 pair_ptr operator ->() const
217 typename iterator_base::value_ptr p = iterator_base::operator ->();
218 return p ? &(p->m_Data) : nullptr;
221 pair_ref operator *() const
223 typename iterator_base::value_ref p = iterator_base::operator *();
227 value_ref val() const
229 typename iterator_base::value_ptr p = iterator_base::operator ->();
230 assert( p != nullptr );
231 return p->m_Data.second;
235 iterator_type& operator ++()
237 iterator_base::operator ++();
242 bool operator ==(iterator_type<C> const& i ) const
244 return iterator_base::operator ==(i);
247 bool operator !=(iterator_type<C> const& i ) const
249 return iterator_base::operator !=(i);
257 The forward iterator for Michael's list has some features:
258 - it has no post-increment operator
259 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
260 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
261 may be thrown if a limit of guard count per thread is exceeded.
262 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
263 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
264 deleting operations it is no guarantee that you iterate all item in the list.
266 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
267 for debug purpose only.
269 The iterator interface to access item data:
270 - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
271 - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
272 - <tt> const key_type& key() </tt> - returns a key reference for iterator
273 - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
275 For both functions the iterator should not be equal to <tt> end() </tt>
277 typedef iterator_type<false> iterator;
279 /// Const forward iterator
281 For iterator's features and requirements see \ref iterator
283 typedef iterator_type<true> const_iterator;
285 /// Returns a forward iterator addressing the first element in a list
287 For empty list \code begin() == end() \endcode
291 return iterator( head() );
294 /// Returns an iterator that addresses the location succeeding the last element in a list
296 Do not use the value returned by <tt>end</tt> function to access any item.
297 Internally, <tt>end</tt> returning value equals to \p nullptr.
299 The returned value can be used only to control reaching the end of the list.
300 For empty list \code begin() == end() \endcode
307 /// Returns a forward const iterator addressing the first element in a list
309 const_iterator begin() const
311 return const_iterator( head() );
313 const_iterator cbegin()
315 return const_iterator( head() );
319 /// Returns an const iterator that addresses the location succeeding the last element in a list
321 const_iterator end() const
323 return const_iterator();
325 const_iterator cend()
327 return const_iterator();
332 /// Default constructor
334 Initializes empty list
348 /// Inserts new node with key and default value
350 The function creates a node with \p key and default value, and then inserts the node created into the list.
353 - The \ref key_type should be constructible from value of type \p K.
354 In trivial case, \p K is equal to \ref key_type.
355 - The \ref mapped_type should be default-constructible.
357 Returns \p true if inserting successful, \p false otherwise.
359 template <typename K>
360 bool insert( const K& key )
362 return insert_at( head(), key );
365 /// Inserts new node with a key and a value
367 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
370 - The \ref key_type should be constructible from \p key of type \p K.
371 - The \ref mapped_type should be constructible from \p val of type \p V.
373 Returns \p true if inserting successful, \p false otherwise.
375 template <typename K, typename V>
376 bool insert( const K& key, const V& val )
378 // We cannot use insert with functor here
379 // because we cannot lock inserted node for updating
380 // Therefore, we use separate function
381 return insert_at( head(), key, val );
384 /// Inserts new node and initialize it by a functor
386 This function inserts new node with key \p key and if inserting is successful then it calls
387 \p func functor with signature
390 void operator()( value_type& item );
394 The argument \p item of user-defined functor \p func is the reference
395 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
396 User-defined functor \p func should guarantee that during changing item's value no any other changes
397 could be made on this list's item by concurrent threads.
398 The user-defined functor can be passed by reference using \p std::ref
399 and it is called only if inserting is successful.
401 The key_type should be constructible from value of type \p K.
403 The function allows to split creating of new item into two part:
404 - create item from \p key;
405 - insert new item into the list;
406 - if inserting is successful, initialize the value of item by calling \p func functor
408 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
409 it is preferable that the initialization should be completed only if inserting is successful.
411 template <typename K, typename Func>
412 bool insert_key( const K& key, Func func )
414 return insert_key_at( head(), key, func );
417 /// Ensures that the \p key exists in the list
419 The operation performs inserting or changing data with lock-free manner.
421 If the \p key not found in the list, then the new item created from \p key
422 is inserted into the list (note that in this case the \ref key_type should be
423 copy-constructible from type \p K).
424 Otherwise, the functor \p func is called with item found.
425 The functor \p Func may be a function with signature:
427 void func( bool bNew, value_type& item );
432 void operator()( bool bNew, value_type& item );
437 - \p bNew - \p true if the item has been inserted, \p false otherwise
438 - \p item - item of the list
440 The functor may change any fields of the \p item.second that is \ref mapped_type;
441 however, \p func must guarantee that during changing no any other modifications
442 could be made on this item by concurrent threads.
444 You may pass \p func argument by reference using \p std::ref
446 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
447 \p second is true if new item has been added or \p false if the item with \p key
448 already is in the list.
450 template <typename K, typename Func>
451 std::pair<bool, bool> ensure( const K& key, Func f )
453 return ensure_at( head(), key, f );
456 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
458 Returns \p true if inserting successful, \p false otherwise.
460 template <typename K, typename... Args>
461 bool emplace( K&& key, Args&&... args )
463 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
466 /// Deletes \p key from the list
467 /** \anchor cds_nonintrusive_MichaelKVList_hp_erase_val
469 Returns \p true if \p key is found and has been deleted, \p false otherwise
471 template <typename K>
472 bool erase( K const& key )
474 return erase_at( head(), key, intrusive_key_comparator() );
477 /// Deletes the item from the list using \p pred predicate for searching
479 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_erase_val "erase(K const&)"
480 but \p pred is used for key comparing.
481 \p Less functor has the interface like \p std::less.
482 \p pred must imply the same element order as the comparator used for building the list.
484 template <typename K, typename Less>
485 bool erase_with( K const& key, Less pred )
487 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
490 /// Deletes \p key from the list
491 /** \anchor cds_nonintrusive_MichaelKVList_hp_erase_func
492 The function searches an item with key \p key, calls \p f functor
493 and deletes the item. If \p key is not found, the functor is not called.
495 The functor \p Func interface:
498 void operator()(value_type& val) { ... }
501 The functor may be passed by reference with <tt>boost:ref</tt>
503 Return \p true if key is found and deleted, \p false otherwise
507 template <typename K, typename Func>
508 bool erase( K const& key, Func f )
510 return erase_at( head(), key, intrusive_key_comparator(), f );
513 /// Deletes the item from the list using \p pred predicate for searching
515 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_erase_func "erase(K const&, Func)"
516 but \p pred is used for key comparing.
517 \p Less functor has the interface like \p std::less.
518 \p pred must imply the same element order as the comparator used for building the list.
520 template <typename K, typename Less, typename Func>
521 bool erase_with( K const& key, Less pred, Func f )
523 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
526 /// Extracts the item from the list with specified \p key
527 /** \anchor cds_nonintrusive_MichaelKVList_hp_extract
528 The function searches an item with key equal to \p key,
529 unlinks it from the list, and returns it in \p dest parameter.
530 If the item with key equal to \p key is not found the function returns \p false.
532 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
534 The \ref disposer specified in \p Traits class template parameter is called automatically
535 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
536 will be destroyed or released.
537 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
541 typedef cds::container::MichaelKVList< cds::gc::HP, int, foo, my_traits > ord_list;
545 ord_list::guarded_ptr gp;
546 theList.extract( gp, 5 );
550 // Destructor of gp releases internal HP guard
554 template <typename K>
555 bool extract( guarded_ptr& dest, K const& key )
557 return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
560 /// Extracts the item from the list with comparing functor \p pred
562 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_extract "extract(guarded_ptr&, K const&)"
563 but \p pred predicate is used for key comparing.
565 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
567 \p pred must imply the same element order as the comparator used for building the list.
569 template <typename K, typename Less>
570 bool extract_with( guarded_ptr& dest, K const& key, Less pred )
572 return extract_at( head(), dest.guard(), key, typename options::template less_wrapper<Less>::type() );
575 /// Finds the key \p key
576 /** \anchor cds_nonintrusive_MichaelKVList_hp_find_val
577 The function searches the item with key equal to \p key
578 and returns \p true if it is found, and \p false otherwise
580 template <typename Q>
581 bool find( Q const& key )
583 return find_at( head(), key, intrusive_key_comparator() );
586 /// Finds the key \p val using \p pred predicate for searching
588 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_find_val "find(Q const&)"
589 but \p pred is used for key comparing.
590 \p Less functor has the interface like \p std::less.
591 \p pred must imply the same element order as the comparator used for building the list.
593 template <typename Q, typename Less>
594 bool find_with( Q const& key, Less pred )
596 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
599 /// Finds the key \p key and performs an action with it
600 /** \anchor cds_nonintrusive_MichaelKVList_hp_find_func
601 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
602 The interface of \p Func functor is:
605 void operator()( value_type& item );
608 where \p item is the item found.
610 You may pass \p f argument by reference using \p std::ref
612 The functor may change <tt>item.second</tt> that is reference to value of node.
613 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
614 The function does not serialize simultaneous access to the list \p item. If such access is
615 possible you must provide your own synchronization schema to exclude unsafe item modifications.
617 The function returns \p true if \p key is found, \p false otherwise.
619 template <typename Q, typename Func>
620 bool find( Q const& key, Func f )
622 return find_at( head(), key, intrusive_key_comparator(), f );
625 /// Finds the key \p val using \p pred predicate for searching
627 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_find_func "find(Q&, Func)"
628 but \p pred is used for key comparing.
629 \p Less functor has the interface like \p std::less.
630 \p pred must imply the same element order as the comparator used for building the list.
632 template <typename Q, typename Less, typename Func>
633 bool find_with( Q const& key, Less pred, Func f )
635 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
638 /// Finds the \p key and return the item found
639 /** \anchor cds_nonintrusive_MichaelKVList_hp_get
640 The function searches the item with key equal to \p key
641 and assigns the item found to guarded pointer \p ptr.
642 The function returns \p true if \p key is found, and \p false otherwise.
643 If \p key is not found the \p ptr parameter is not changed.
645 The \ref disposer specified in \p Traits class template parameter is called
646 by garbage collector \p GC automatically when returned \ref guarded_ptr object
647 will be destroyed or released.
648 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
652 typedef cds::container::MichaelKVList< cds::gc::HP, int, foo, my_traits > ord_list;
656 ord_list::guarded_ptr gp;
657 if ( theList.get( gp, 5 )) {
661 // Destructor of guarded_ptr releases internal HP guard
665 Note the compare functor specified for class \p Traits template parameter
666 should accept a parameter of type \p K that can be not the same as \p key_type.
668 template <typename K>
669 bool get( guarded_ptr& ptr, K const& key )
671 return get_at( head(), ptr.guard(), key, intrusive_key_comparator() );
674 /// Finds the \p key and return the item found
676 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_get "get( guarded_ptr& ptr, K const&)"
677 but \p pred is used for comparing the keys.
679 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
681 \p pred must imply the same element order as the comparator used for building the list.
683 template <typename K, typename Less>
684 bool get_with( guarded_ptr& ptr, K const& key, Less pred )
686 return get_at( head(), ptr.guard(), key, typename options::template less_wrapper<Less>::type() );
689 /// Checks if the list is empty
692 return base_class::empty();
695 /// Returns list's item count
697 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
698 this function always returns 0.
700 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
701 is empty. To check list emptyness use \ref empty() method.
705 return base_class::size();
710 Post-condition: the list is empty
719 bool insert_node_at( head_type& refHead, node_type * pNode )
721 assert( pNode != nullptr );
722 scoped_node_ptr p( pNode );
723 if ( base_class::insert_at( refHead, *pNode )) {
730 template <typename K>
731 bool insert_at( head_type& refHead, const K& key )
733 return insert_node_at( refHead, alloc_node( key ));
736 template <typename K, typename V>
737 bool insert_at( head_type& refHead, const K& key, const V& val )
739 return insert_node_at( refHead, alloc_node( key, val ));
742 template <typename K, typename Func>
743 bool insert_key_at( head_type& refHead, const K& key, Func f )
745 scoped_node_ptr pNode( alloc_node( key ));
747 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
754 template <typename K, typename... Args>
755 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
757 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
760 template <typename K, typename Func>
761 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
763 scoped_node_ptr pNode( alloc_node( key ));
765 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
766 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
767 if ( ret.first && ret.second )
773 template <typename K, typename Compare>
774 bool erase_at( head_type& refHead, K const& key, Compare cmp )
776 return base_class::erase_at( refHead, key, cmp );
779 template <typename K, typename Compare, typename Func>
780 bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
782 return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
784 template <typename K, typename Compare>
785 bool extract_at( head_type& refHead, typename gc::Guard& dest, K const& key, Compare cmp )
787 return base_class::extract_at( refHead, dest, key, cmp );
790 template <typename K, typename Compare>
791 bool find_at( head_type& refHead, K const& key, Compare cmp )
793 return base_class::find_at( refHead, key, cmp );
796 template <typename K, typename Compare, typename Func>
797 bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
799 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
802 template <typename K, typename Compare>
803 bool get_at( head_type& refHead, typename gc::Guard& guard, K const& key, Compare cmp )
805 return base_class::get_at( refHead, guard, key, cmp );
811 }} // namespace cds::container
813 #endif // #ifndef __CDS_CONTAINER_IMPL_MICHAEL_KVLIST_H