3 #ifndef CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H
4 #define CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H
6 #include <cds/container/details/michael_map_base.h>
7 #include <cds/details/allocator.h>
9 namespace cds { namespace container {
11 /// Michael's hash map (template specialization for \ref cds_urcu_desc "RCU")
12 /** @ingroup cds_nonintrusive_map
13 \anchor cds_nonintrusive_MichaelHashMap_rcu
16 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
18 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
19 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
20 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
21 However, each bucket may contain unbounded number of items.
23 Template parameters are:
24 - \p RCU - one of \ref cds_urcu_gc "RCU type"
25 - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, \p MichaelKVList.
26 The ordered list implementation specifies the \p Key and \p Value types stored in the hash-map, the reclamation
27 schema \p GC used by hash-map, the comparison functor for the type \p Key and other features specific for
29 - \p Traits - map traits, default is \p michael_map::traits.
30 Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction
32 Many of the class function take a key argument of type \p K that in general is not \p key_type.
33 \p key_type and an argument of template type \p K must meet the following requirements:
34 - \p key_type should be constructible from value of type \p K;
35 - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
36 <tt> hash( key_type(key) ) == hash( key ) </tt>
37 - values of type \p key_type and \p K should be comparable
41 The tips about how to use Michael's map see \ref cds_nonintrusive_MichaelHashMap_how_touse "MichaelHashMap".
42 Remember, that you should include RCU-related header file (for example, <tt>cds/urcu/general_buffered.h</tt>)
43 before including <tt>cds/container/michael_map_rcu.h</tt>.
48 #ifdef CDS_DOXYGEN_INVOKED
49 class Traits = michael_map::traits
54 class MichaelHashMap< cds::urcu::gc< RCU >, OrderedList, Traits >
57 typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector
58 typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
59 typedef Traits traits; ///< Map traits
61 typedef typename bucket_type::key_type key_type ; ///< key type
62 typedef typename bucket_type::mapped_type mapped_type ; ///< value type
63 typedef typename bucket_type::value_type value_type ; ///< key/value pair stored in the list
64 typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor
66 /// Hash functor for \ref key_type and all its derivatives that you use
67 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
68 typedef typename traits::item_counter item_counter; ///< Item counter type
70 /// Bucket table allocator
71 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
73 typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock
74 typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
75 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
76 static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
79 typedef cds::container::michael_map::implementation_tag implementation_tag;
83 item_counter m_ItemCounter; ///< Item counter
84 hash m_HashFunctor; ///< Hash functor
85 bucket_type * m_Buckets; ///< bucket table
89 const size_t m_nHashBitmask;
94 /// Calculates hash value of \p key
96 size_t hash_value( Q const& key ) const
98 return m_HashFunctor( key ) & m_nHashBitmask;
101 /// Returns the bucket (ordered list) for \p key
102 template <typename Q>
103 bucket_type& bucket( Q const& key )
105 return m_Buckets[ hash_value( key ) ];
107 template <typename Q>
108 bucket_type const& bucket( Q const& key ) const
110 return m_Buckets[ hash_value( key ) ];
116 \p IsConst - constness boolean flag
118 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has the following features:
119 - it has no post-increment operator, only pre-increment
120 - it iterates items in unordered fashion
121 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
122 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
123 deleting operations it is no guarantee that you iterate all item in the map.
125 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
126 for debug purpose only.
128 template <bool IsConst>
129 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
132 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
133 friend class MichaelHashMap;
138 //typedef typename base_class::bucket_type bucket_type;
139 typedef typename base_class::bucket_ptr bucket_ptr;
140 typedef typename base_class::list_iterator list_iterator;
142 //typedef typename bucket_type::key_type key_type;
146 /// Value pointer type (const for const_iterator)
147 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
148 /// Value reference type (const for const_iterator)
149 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
151 /// Key-value pair pointer type (const for const_iterator)
152 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
153 /// Key-value pair reference type (const for const_iterator)
154 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
158 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
159 : base_class( it, pFirst, pLast )
170 iterator_type( const iterator_type& src )
174 /// Dereference operator
175 pair_ptr operator ->() const
177 assert( base_class::m_pCurBucket != nullptr );
178 return base_class::m_itList.operator ->();
181 /// Dereference operator
182 pair_ref operator *() const
184 assert( base_class::m_pCurBucket != nullptr );
185 return base_class::m_itList.operator *();
189 iterator_type& operator ++()
191 base_class::operator++();
195 /// Assignment operator
196 iterator_type& operator = (const iterator_type& src)
198 base_class::operator =(src);
202 /// Returns current bucket (debug function)
203 bucket_ptr bucket() const
205 return base_class::bucket();
208 /// Equality operator
210 bool operator ==(iterator_type<C> const& i )
212 return base_class::operator ==( i );
214 /// Equality operator
216 bool operator !=(iterator_type<C> const& i )
218 return !( *this == i );
224 typedef iterator_type< false > iterator;
226 /// Const forward iterator
227 typedef iterator_type< true > const_iterator;
229 /// Returns a forward iterator addressing the first element in a map
231 For empty map \code begin() == end() \endcode
235 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
238 /// Returns an iterator that addresses the location succeeding the last element in a map
240 Do not use the value returned by <tt>end</tt> function to access any item.
241 The returned value can be used only to control reaching the end of the map.
242 For empty map \code begin() == end() \endcode
246 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
249 /// Returns a forward const iterator addressing the first element in a map
251 const_iterator begin() const
253 return get_const_begin();
255 const_iterator cbegin() const
257 return get_const_begin();
261 /// Returns an const iterator that addresses the location succeeding the last element in a map
263 const_iterator end() const
265 return get_const_end();
267 const_iterator cend() const
269 return get_const_end();
275 const_iterator get_const_begin() const
277 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
279 const_iterator get_const_end() const
281 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
286 /// Initializes the map
287 /** @copydetails cds_nonintrusive_MichaelHashMap_hp_ctor
290 size_t nMaxItemCount, ///< estimation of max item count in the hash map
291 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
292 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
294 // GC and OrderedList::gc must be the same
295 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
297 // atomicity::empty_item_counter is not allowed as a item counter
298 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
299 "cds::atomicity::empty_item_counter is not allowed as a item counter");
301 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
304 /// Clears hash map and destroys it
308 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
311 /// Inserts new node with key and default value
313 The function creates a node with \p key and default value, and then inserts the node created into the map.
316 - The \p key_type should be constructible from value of type \p K.
317 In trivial case, \p K is equal to \ref key_type.
318 - The \p mapped_type should be default-constructible.
320 The function applies RCU lock internally.
322 Returns \p true if inserting successful, \p false otherwise.
324 template <typename K>
325 bool insert( const K& key )
327 const bool bRet = bucket( key ).insert( key );
335 The function creates a node with copy of \p val value
336 and then inserts the node created into the map.
339 - The \p key_type should be constructible from \p key of type \p K.
340 - The \p mapped_type should be constructible from \p val of type \p V.
342 The function applies RCU lock internally.
344 Returns \p true if \p val is inserted into the map, \p false otherwise.
346 template <typename K, typename V>
347 bool insert( K const& key, V const& val )
349 const bool bRet = bucket( key ).insert( key, val );
355 /// Inserts new node and initialize it by a functor
357 This function inserts new node with key \p key and if inserting is successful then it calls
358 \p func functor with signature
361 void operator()( value_type& item );
365 The argument \p item of user-defined functor \p func is the reference
366 to the map's item inserted:
367 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
368 - <tt>item.second</tt> is a reference to item's value that may be changed.
370 The user-defined functor is called only if inserting is successful.
372 The key_type should be constructible from value of type \p K.
374 The function allows to split creating of new item into two part:
375 - create item from \p key;
376 - insert new item into the map;
377 - if inserting is successful, initialize the value of item by calling \p func functor
379 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
380 it is preferable that the initialization should be completed only if inserting is successful.
382 The function applies RCU lock internally.
384 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
385 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
388 template <typename K, typename Func>
389 bool insert_with( const K& key, Func func )
391 const bool bRet = bucket( key ).insert_with( key, func );
398 /// Ensures that the \p key exists in the map
400 The operation performs inserting or changing data with lock-free manner.
402 If the \p key not found in the map, then the new item created from \p key
403 is inserted into the map (note that in this case the \ref key_type should be
404 constructible from type \p K).
405 Otherwise, the functor \p func is called with item found.
406 The functor \p Func may be a function with signature:
408 void func( bool bNew, value_type& item );
413 void operator()( bool bNew, value_type& item );
418 - \p bNew - \p true if the item has been inserted, \p false otherwise
419 - \p item - item of the list
421 The functor may change any fields of the \p item.second that is \ref mapped_type.
423 The function applies RCU lock internally.
425 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
426 \p second is true if new item has been added or \p false if the item with \p key
427 already is in the list.
429 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
430 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
433 template <typename K, typename Func>
434 std::pair<bool, bool> ensure( K const& key, Func func )
436 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
437 if ( bRet.first && bRet.second )
442 /// For key \p key inserts data of type \p mapped_type created from \p args
444 \p key_type should be constructible from type \p K
446 Returns \p true if inserting successful, \p false otherwise.
448 template <typename K, typename... Args>
449 bool emplace( K&& key, Args&&... args )
451 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
457 /// Deletes \p key from the map
458 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_val
460 RCU \p synchronize method can be called. RCU should not be locked.
462 Return \p true if \p key is found and deleted, \p false otherwise
464 template <typename K>
465 bool erase( const K& key )
467 const bool bRet = bucket( key ).erase( key );
473 /// Deletes the item from the map using \p pred predicate for searching
475 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_val "erase(K const&)"
476 but \p pred is used for key comparing.
477 \p Less predicate has the interface like \p std::less.
478 \p Less must imply the same element order as the comparator used for building the map.
480 template <typename K, typename Less>
481 bool erase_with( const K& key, Less pred )
483 const bool bRet = bucket( key ).erase_with( key, pred );
489 /// Deletes \p key from the map
490 /** \anchor cds_nonintrusive_MichaelMap_rcu_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& item) { ... }
502 RCU \p synchronize method can be called. RCU should not be locked.
504 Return \p true if key is found and deleted, \p false otherwise
506 template <typename K, typename Func>
507 bool erase( const K& key, Func f )
509 const bool bRet = bucket( key ).erase( key, f );
515 /// Deletes the item from the map using \p pred predicate for searching
517 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_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 Less must imply the same element order as the comparator used for building the map.
522 template <typename K, typename Less, typename Func>
523 bool erase_with( const K& key, Less pred, Func f )
525 const bool bRet = bucket( key ).erase_with( key, pred, f );
531 /// Extracts an item from the map
532 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_extract
533 The function searches an item with key equal to \p key,
534 unlinks it from the map, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
535 If the item is not found the function return an empty \p exempt_ptr.
537 @note The function does NOT call RCU read-side lock or synchronization,
538 and does NOT dispose the item found. It just excludes the item from the map
539 and returns a pointer to item found.
540 You should lock RCU before calling of the function, and you should synchronize RCU
541 outside the RCU lock to free extracted item
544 #include <cds/urcu/general_buffered.h>
545 #include <cds/container/michael_kvlist_rcu.h>
546 #include <cds/container/michael_map_rcu.h>
548 typedef cds::urcu::gc< general_buffered<> > rcu;
549 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
550 typedef cds::container::MichaelHashMap< rcu, rcu_michael_list, foo_traits > rcu_michael_map;
552 rcu_michael_map theMap;
555 rcu_michael_map::exempt_ptr p;
557 // first, we should lock RCU
558 rcu_michael_map::rcu_lock lock;
560 // Now, you can apply extract function
561 // Note that you must not delete the item found inside the RCU lock
562 p = theMap.extract( 10 );
564 // do something with p
569 // We may safely release p here
570 // release() passes the pointer to RCU reclamation cycle
574 template <typename K>
575 exempt_ptr extract( K const& key )
577 exempt_ptr p = bucket( key ).extract( key );
583 /// Extracts an item from the map using \p pred predicate for searching
585 The function is an analog of \p extract(K const&) but \p pred is used for key comparing.
586 \p Less functor has the interface like \p std::less.
587 \p pred must imply the same element order as the comparator used for building the map.
589 template <typename K, typename Less>
590 exempt_ptr extract_with( K const& key, Less pred )
592 exempt_ptr p = bucket( key ).extract_with( key, pred );
598 /// Finds the key \p key
599 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_cfunc
601 The function searches the item with key equal to \p key and calls the functor \p f for 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 The functor may change \p item.second. Note that the functor is only guarantee
611 that \p item cannot be disposed during functor is executing.
612 The functor does not serialize simultaneous access to the map's \p item. If such access is
613 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
615 The function applies RCU lock internally.
617 The function returns \p true if \p key is found, \p false otherwise.
619 template <typename K, typename Func>
620 bool find( K const& key, Func f ) const
622 return bucket( key ).find( key, f );
625 /// Finds the key \p val using \p pred predicate for searching
627 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_cfunc "find(K const&, Func)"
628 but \p pred is used for key comparing.
629 \p Less functor has the interface like \p std::less.
630 \p Less must imply the same element order as the comparator used for building the map.
632 template <typename K, typename Less, typename Func>
633 bool find_with( K const& key, Less pred, Func f ) const
635 return bucket( key ).find_with( key, pred, f );
638 /// Finds the key \p key
639 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_val
641 The function searches the item with key equal to \p key
642 and returns \p true if it is found, and \p false otherwise.
644 The function applies RCU lock internally.
646 template <typename K>
647 bool find( K const& key ) const
649 return bucket( key ).find( key );
652 /// Finds the key \p val using \p pred predicate for searching
654 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_val "find(K const&)"
655 but \p pred is used for key comparing.
656 \p Less functor has the interface like \p std::less.
657 \p Less must imply the same element order as the comparator used for building the map.
659 template <typename K, typename Less>
660 bool find_with( K const& key, Less pred ) const
662 return bucket( key ).find_with( key, pred );
665 /// Finds \p key and return the item found
666 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get
667 The function searches the item with key equal to \p key and returns the pointer to item found.
668 If \p key is not found it returns \p nullptr.
670 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
672 RCU should be locked before call of this function.
673 Returned item is valid only while RCU is locked:
675 typedef cds::container::MichaelHashMap< your_template_parameters > hash_map;
680 hash_map::rcu_lock lock;
682 hash_map::value_type * = theMap.get( 5 );
687 // Unlock RCU by rcu_lock destructor
688 // pVal can be freed at any time after RCU has been unlocked
692 template <typename K>
693 value_type * get( K const& key ) const
695 return bucket( key ).get( key );
698 /// Finds \p key and return the item found
700 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_get "get(K const&)"
701 but \p pred is used for comparing the keys.
703 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
705 \p pred must imply the same element order as the comparator used for building the map.
707 template <typename K, typename Less>
708 value_type * get_with( K const& key, Less pred ) const
710 return bucket( key ).get_with( key, pred );
713 /// Clears the map (not atomic)
715 The function erases all items from the map.
717 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
718 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
719 <tt> empty() </tt> may return \p true but the map may contain item(s).
720 Therefore, \p clear may be used only for debugging purposes.
722 RCU \p synchronize method can be called. RCU should not be locked.
726 for ( size_t i = 0; i < bucket_count(); ++i )
727 m_Buckets[i].clear();
728 m_ItemCounter.reset();
731 /// Checks if the map is empty
733 Emptiness is checked by item counting: if item count is zero then the map is empty.
734 Thus, the correct item counting is an important part of the map implementation.
741 /// Returns item count in the map
744 return m_ItemCounter;
747 /// Returns the size of hash table
749 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
750 the value returned is an constant depending on object initialization parameters;
751 see \p MichaelHashMap::MichaelHashMap for explanation.
753 size_t bucket_count() const
755 return m_nHashBitmask + 1;
758 }} // namespace cds::container
760 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H