3 #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_IMPL_H
4 #define __CDS_CONTAINER_MICHAEL_KVLIST_IMPL_H
8 #include <cds/details/functor_wrapper.h>
9 #include <cds/container/details/guarded_ptr_cast.h>
11 namespace cds { namespace container {
13 /// Michael's ordered list (key-value pair)
14 /** @ingroup cds_nonintrusive_list
15 \anchor cds_nonintrusive_MichaelKVList_gc
17 This is key-value variation of non-intrusive MichaelList.
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 GC - garbage collector used
26 - \p Key - key type of an item stored in the list. It should be copy-constructible
27 - \p Value - value type stored in a list
28 - \p Traits - type traits, default is michael_list::type_traits
30 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
31 argument. For example, the following traits-based declaration of gc::HP Michael's list
33 #include <cds/container/michael_kvlist_hp.h>
34 // Declare comparator for the item
36 int operator ()( int i1, int i2 )
42 // Declare type_traits
43 struct my_traits: public cds::container::michael_list::type_traits
45 typedef my_compare compare;
48 // Declare traits-based list
49 typedef cds::container::MichaelKVList< cds::gc::HP, int, int, my_traits > traits_based_list;
52 is equivalent for the following option-based list
54 #include <cds/container/michael_kvlist_hp.h>
56 // my_compare is the same
58 // Declare option-based list
59 typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
60 typename cds::container::michael_list::make_traits<
61 cds::container::opt::compare< my_compare > // item comparator option
66 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
67 - opt::compare - key comparison functor. No default functor is provided.
68 If the option is not specified, the opt::less is used.
69 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
70 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
71 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
72 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
73 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
74 or opt::v::sequential_consistent (sequentially consisnent memory model).
77 There are different specializations of this template for each garbage collecting schema used.
78 You should include appropriate .h-file depending on GC you are using:
79 - for gc::HP: \code #include <cds/container/michael_kvlist_hp.h> \endcode
80 - for gc::PTB: \code #include <cds/container/michael_kvlist_ptb.h> \endcode
81 - for gc::HRC: \code #include <cds/container/michael_kvlist_hrc.h> \endcode
82 - for \ref cds_urcu_desc "RCU": \code #include <cds/container/michael_kvlist_rcu.h> \endcode
83 - for gc::nogc: \code #include <cds/container/michael_kvlist_nogc.h> \endcode
89 #ifdef CDS_DOXYGEN_INVOKED
90 typename Traits = michael_list::type_traits
96 #ifdef CDS_DOXYGEN_INVOKED
97 protected intrusive::MichaelList< GC, implementation_defined, Traits >
99 protected details::make_michael_kvlist< GC, Key, Value, Traits >::type
103 typedef details::make_michael_kvlist< GC, Key, Value, Traits > options;
104 typedef typename options::type base_class;
108 #ifdef CDS_DOXYGEN_INVOKED
109 typedef Key key_type ; ///< Key type
110 typedef Value mapped_type ; ///< Type of value stored in the list
111 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
113 typedef typename options::key_type key_type;
114 typedef typename options::value_type mapped_type;
115 typedef typename options::pair_type value_type;
118 typedef typename base_class::gc gc ; ///< Garbage collector used
119 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
120 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
121 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
122 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
123 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
127 typedef typename base_class::value_type node_type;
128 typedef typename options::cxx_allocator cxx_allocator;
129 typedef typename options::node_deallocator node_deallocator;
130 typedef typename options::type_traits::compare intrusive_key_comparator;
132 typedef typename base_class::atomic_node_ptr head_type;
137 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_map<node_type, value_type> > guarded_ptr;
141 template <typename K>
142 static node_type * alloc_node(const K& key)
144 return cxx_allocator().New( key );
147 template <typename K, typename V>
148 static node_type * alloc_node( const K& key, const V& val )
150 return cxx_allocator().New( key, val );
153 template <typename K, typename... Args>
154 static node_type * alloc_node( K&& key, Args&&... args )
156 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
159 static void free_node( node_type * pNode )
161 cxx_allocator().Delete( pNode );
164 struct node_disposer {
165 void operator()( node_type * pNode )
170 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
174 return base_class::m_pHead;
177 head_type const& head() const
179 return base_class::m_pHead;
185 template <bool IsConst>
186 class iterator_type: protected base_class::template iterator_type<IsConst>
188 typedef typename base_class::template iterator_type<IsConst> iterator_base;
190 iterator_type( head_type const& pNode )
191 : iterator_base( pNode )
194 friend class MichaelKVList;
197 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
198 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
200 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
201 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
206 iterator_type( iterator_type const& src )
207 : iterator_base( src )
210 key_type const& key() const
212 typename iterator_base::value_ptr p = iterator_base::operator ->();
213 assert( p != nullptr );
214 return p->m_Data.first;
217 pair_ptr operator ->() const
219 typename iterator_base::value_ptr p = iterator_base::operator ->();
220 return p ? &(p->m_Data) : nullptr;
223 pair_ref operator *() const
225 typename iterator_base::value_ref p = iterator_base::operator *();
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;
237 iterator_type& operator ++()
239 iterator_base::operator ++();
244 bool operator ==(iterator_type<C> const& i ) const
246 return iterator_base::operator ==(i);
249 bool operator !=(iterator_type<C> const& i ) const
251 return iterator_base::operator !=(i);
259 The forward iterator for Michael's list has some features:
260 - it has no post-increment operator
261 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
262 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
263 may be thrown if a limit of guard count per thread is exceeded.
264 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
265 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
266 deleting operations it is no guarantee that you iterate all item in the list.
268 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
269 for debug purpose only.
271 The iterator interface to access item data:
272 - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
273 - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
274 - <tt> const key_type& key() </tt> - returns a key reference for iterator
275 - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
277 For both functions the iterator should not be equal to <tt> end() </tt>
279 typedef iterator_type<false> iterator;
281 /// Const forward iterator
283 For iterator's features and requirements see \ref iterator
285 typedef iterator_type<true> const_iterator;
287 /// Returns a forward iterator addressing the first element in a list
289 For empty list \code begin() == end() \endcode
293 return iterator( head() );
296 /// Returns an iterator that addresses the location succeeding the last element in a list
298 Do not use the value returned by <tt>end</tt> function to access any item.
299 Internally, <tt>end</tt> returning value equals to \p nullptr.
301 The returned value can be used only to control reaching the end of the list.
302 For empty list \code begin() == end() \endcode
309 /// Returns a forward const iterator addressing the first element in a list
311 const_iterator begin() const
313 return const_iterator( head() );
315 const_iterator cbegin()
317 return const_iterator( head() );
321 /// Returns an const iterator that addresses the location succeeding the last element in a list
323 const_iterator end() const
325 return const_iterator();
327 const_iterator cend()
329 return const_iterator();
334 /// Default constructor
336 Initializes empty list
350 /// Inserts new node with key and default value
352 The function creates a node with \p key and default value, and then inserts the node created into the list.
355 - The \ref key_type should be constructible from value of type \p K.
356 In trivial case, \p K is equal to \ref key_type.
357 - The \ref mapped_type should be default-constructible.
359 Returns \p true if inserting successful, \p false otherwise.
361 template <typename K>
362 bool insert( const K& key )
364 return insert_at( head(), key );
367 /// Inserts new node with a key and a value
369 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
372 - The \ref key_type should be constructible from \p key of type \p K.
373 - The \ref mapped_type should be constructible from \p val of type \p V.
375 Returns \p true if inserting successful, \p false otherwise.
377 template <typename K, typename V>
378 bool insert( const K& key, const V& val )
380 // We cannot use insert with functor here
381 // because we cannot lock inserted node for updating
382 // Therefore, we use separate function
383 return insert_at( head(), key, val );
386 /// Inserts new node and initialize it by a functor
388 This function inserts new node with key \p key and if inserting is successful then it calls
389 \p func functor with signature
392 void operator()( value_type& item );
396 The argument \p item of user-defined functor \p func is the reference
397 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
398 User-defined functor \p func should guarantee that during changing item's value no any other changes
399 could be made on this list's item by concurrent threads.
400 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
401 and it is called only if inserting is successful.
403 The key_type should be constructible from value of type \p K.
405 The function allows to split creating of new item into two part:
406 - create item from \p key;
407 - insert new item into the list;
408 - if inserting is successful, initialize the value of item by calling \p func functor
410 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
411 it is preferable that the initialization should be completed only if inserting is successful.
413 template <typename K, typename Func>
414 bool insert_key( const K& key, Func func )
416 return insert_key_at( head(), key, func );
419 /// Ensures that the \p key exists in the list
421 The operation performs inserting or changing data with lock-free manner.
423 If the \p key not found in the list, then the new item created from \p key
424 is inserted into the list (note that in this case the \ref key_type should be
425 copy-constructible from type \p K).
426 Otherwise, the functor \p func is called with item found.
427 The functor \p Func may be a function with signature:
429 void func( bool bNew, value_type& item );
434 void operator()( bool bNew, value_type& item );
439 - \p bNew - \p true if the item has been inserted, \p false otherwise
440 - \p item - item of the list
442 The functor may change any fields of the \p item.second that is \ref mapped_type;
443 however, \p func must guarantee that during changing no any other modifications
444 could be made on this item by concurrent threads.
446 You may pass \p func argument by reference using <tt>boost::ref</tt>.
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 template <typename K, typename Func>
453 std::pair<bool, bool> ensure( const K& key, Func f )
455 return ensure_at( head(), key, f );
458 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
460 Returns \p true if inserting successful, \p false otherwise.
462 template <typename K, typename... Args>
463 bool emplace( K&& key, Args&&... args )
465 return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
468 /// Deletes \p key from the list
469 /** \anchor cds_nonintrusive_MichaelKVList_hp_erase_val
471 Returns \p true if \p key is found and has been deleted, \p false otherwise
473 template <typename K>
474 bool erase( K const& key )
476 return erase_at( head(), key, intrusive_key_comparator() );
479 /// Deletes the item from the list using \p pred predicate for searching
481 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_erase_val "erase(K const&)"
482 but \p pred is used for key comparing.
483 \p Less functor has the interface like \p std::less.
484 \p pred must imply the same element order as the comparator used for building the list.
486 template <typename K, typename Less>
487 bool erase_with( K const& key, Less pred )
489 return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
492 /// Deletes \p key from the list
493 /** \anchor cds_nonintrusive_MichaelKVList_hp_erase_func
494 The function searches an item with key \p key, calls \p f functor
495 and deletes the item. If \p key is not found, the functor is not called.
497 The functor \p Func interface:
500 void operator()(value_type& val) { ... }
503 The functor may be passed by reference with <tt>boost:ref</tt>
505 Return \p true if key is found and deleted, \p false otherwise
509 template <typename K, typename Func>
510 bool erase( K const& key, Func f )
512 return erase_at( head(), key, intrusive_key_comparator(), f );
515 /// Deletes the item from the list using \p pred predicate for searching
517 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_erase_func "erase(K const&, Func)"
518 but \p pred is used for key comparing.
519 \p Less functor has the interface like \p std::less.
520 \p pred must imply the same element order as the comparator used for building the list.
522 template <typename K, typename Less, typename Func>
523 bool erase_with( K const& key, Less pred, Func f )
525 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
528 /// Extracts the item from the list with specified \p key
529 /** \anchor cds_nonintrusive_MichaelKVList_hp_extract
530 The function searches an item with key equal to \p key,
531 unlinks it from the list, and returns it in \p dest parameter.
532 If the item with key equal to \p key is not found the function returns \p false.
534 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
536 The \ref disposer specified in \p Traits class template parameter is called automatically
537 by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
538 will be destroyed or released.
539 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
543 typedef cds::container::MichaelKVList< cds::gc::HP, int, foo, my_traits > ord_list;
547 ord_list::guarded_ptr gp;
548 theList.extract( gp, 5 );
552 // Destructor of gp releases internal HP guard
556 template <typename K>
557 bool extract( guarded_ptr& dest, K const& key )
559 return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
562 /// Extracts the item from the list with comparing functor \p pred
564 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_extract "extract(guarded_ptr&, K const&)"
565 but \p pred predicate is used for key comparing.
567 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
569 \p pred must imply the same element order as the comparator used for building the list.
571 template <typename K, typename Less>
572 bool extract_with( guarded_ptr& dest, K const& key, Less pred )
574 return extract_at( head(), dest.guard(), key, typename options::template less_wrapper<Less>::type() );
577 /// Finds the key \p key
578 /** \anchor cds_nonintrusive_MichaelKVList_hp_find_val
579 The function searches the item with key equal to \p key
580 and returns \p true if it is found, and \p false otherwise
582 template <typename Q>
583 bool find( Q const& key )
585 return find_at( head(), key, intrusive_key_comparator() );
588 /// Finds the key \p val using \p pred predicate for searching
590 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_find_val "find(Q const&)"
591 but \p pred is used for key comparing.
592 \p Less functor has the interface like \p std::less.
593 \p pred must imply the same element order as the comparator used for building the list.
595 template <typename Q, typename Less>
596 bool find_with( Q const& key, Less pred )
598 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
601 /// Finds the key \p key and performs an action with it
602 /** \anchor cds_nonintrusive_MichaelKVList_hp_find_func
603 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
604 The interface of \p Func functor is:
607 void operator()( value_type& item );
610 where \p item is the item found.
612 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
614 The functor may change <tt>item.second</tt> that is reference to value of node.
615 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
616 The function does not serialize simultaneous access to the list \p item. If such access is
617 possible you must provide your own synchronization schema to exclude unsafe item modifications.
619 The function returns \p true if \p key is found, \p false otherwise.
621 template <typename Q, typename Func>
622 bool find( Q const& key, Func f )
624 return find_at( head(), key, intrusive_key_comparator(), f );
627 /// Finds the key \p val using \p pred predicate for searching
629 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_find_func "find(Q&, Func)"
630 but \p pred is used for key comparing.
631 \p Less functor has the interface like \p std::less.
632 \p pred must imply the same element order as the comparator used for building the list.
634 template <typename Q, typename Less, typename Func>
635 bool find_with( Q const& key, Less pred, Func f )
637 return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
640 /// Finds the \p key and return the item found
641 /** \anchor cds_nonintrusive_MichaelKVList_hp_get
642 The function searches the item with key equal to \p key
643 and assigns the item found to guarded pointer \p ptr.
644 The function returns \p true if \p key is found, and \p false otherwise.
645 If \p key is not found the \p ptr parameter is not changed.
647 The \ref disposer specified in \p Traits class template parameter is called
648 by garbage collector \p GC automatically when returned \ref guarded_ptr object
649 will be destroyed or released.
650 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
654 typedef cds::container::MichaelKVList< cds::gc::HP, int, foo, my_traits > ord_list;
658 ord_list::guarded_ptr gp;
659 if ( theList.get( gp, 5 )) {
663 // Destructor of guarded_ptr releases internal HP guard
667 Note the compare functor specified for class \p Traits template parameter
668 should accept a parameter of type \p K that can be not the same as \p key_type.
670 template <typename K>
671 bool get( guarded_ptr& ptr, K const& key )
673 return get_at( head(), ptr.guard(), key, intrusive_key_comparator() );
676 /// Finds the \p key and return the item found
678 The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_get "get( guarded_ptr& ptr, K const&)"
679 but \p pred is used for comparing the keys.
681 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
683 \p pred must imply the same element order as the comparator used for building the list.
685 template <typename K, typename Less>
686 bool get_with( guarded_ptr& ptr, K const& key, Less pred )
688 return get_at( head(), ptr.guard(), key, typename options::template less_wrapper<Less>::type() );
691 /// Checks if the list is empty
694 return base_class::empty();
697 /// Returns list's item count
699 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
700 this function always returns 0.
702 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
703 is empty. To check list emptyness use \ref empty() method.
707 return base_class::size();
712 Post-condition: the list is empty
721 bool insert_node_at( head_type& refHead, node_type * pNode )
723 assert( pNode != nullptr );
724 scoped_node_ptr p( pNode );
725 if ( base_class::insert_at( refHead, *pNode )) {
732 template <typename K>
733 bool insert_at( head_type& refHead, const K& key )
735 return insert_node_at( refHead, alloc_node( key ));
738 template <typename K, typename V>
739 bool insert_at( head_type& refHead, const K& key, const V& val )
741 return insert_node_at( refHead, alloc_node( key, val ));
744 template <typename K, typename Func>
745 bool insert_key_at( head_type& refHead, const K& key, Func f )
747 scoped_node_ptr pNode( alloc_node( key ));
749 if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node.m_Data ); })) {
756 template <typename K, typename... Args>
757 bool emplace_at( head_type& refHead, K&& key, Args&&... args )
759 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
762 template <typename K, typename Func>
763 std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
765 scoped_node_ptr pNode( alloc_node( key ));
767 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
768 [&f]( bool bNew, node_type& node, node_type& ){ cds::unref(f)( bNew, node.m_Data ); });
769 if ( ret.first && ret.second )
775 template <typename K, typename Compare>
776 bool erase_at( head_type& refHead, K const& key, Compare cmp )
778 return base_class::erase_at( refHead, key, cmp );
781 template <typename K, typename Compare, typename Func>
782 bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
784 return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ cds::unref(f)( const_cast<value_type&>(node.m_Data)); });
786 template <typename K, typename Compare>
787 bool extract_at( head_type& refHead, typename gc::Guard& dest, K const& key, Compare cmp )
789 return base_class::extract_at( refHead, dest, key, cmp );
792 template <typename K, typename Compare>
793 bool find_at( head_type& refHead, K const& key, Compare cmp )
795 return base_class::find_at( refHead, key, cmp );
798 template <typename K, typename Compare, typename Func>
799 bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
801 return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ cds::unref(f)( node.m_Data ); });
804 template <typename K, typename Compare>
805 bool get_at( head_type& refHead, typename gc::Guard& guard, K const& key, Compare cmp )
807 return base_class::get_at( refHead, guard, key, cmp );
813 }} // namespace cds::container
815 #endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_IMPL_H