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;
77 /// Type of \p get() member function return value
78 typedef typename bucket_type::raw_ptr raw_ptr;
81 typedef cds::container::michael_map::implementation_tag implementation_tag;
85 item_counter m_ItemCounter; ///< Item counter
86 hash m_HashFunctor; ///< Hash functor
87 bucket_type * m_Buckets; ///< bucket table
91 const size_t m_nHashBitmask;
96 /// Calculates hash value of \p key
98 size_t hash_value( Q const& key ) const
100 return m_HashFunctor( key ) & m_nHashBitmask;
103 /// Returns the bucket (ordered list) for \p key
104 template <typename Q>
105 bucket_type& bucket( Q const& key )
107 return m_Buckets[ hash_value( key ) ];
109 template <typename Q>
110 bucket_type const& bucket( Q const& key ) const
112 return m_Buckets[ hash_value( key ) ];
118 \p IsConst - constness boolean flag
120 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has the following features:
121 - it has no post-increment operator, only pre-increment
122 - it iterates items in unordered fashion
123 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
124 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
125 deleting operations it is no guarantee that you iterate all item in the map.
127 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
128 for debug purpose only.
130 template <bool IsConst>
131 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
134 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
135 friend class MichaelHashMap;
140 //typedef typename base_class::bucket_type bucket_type;
141 typedef typename base_class::bucket_ptr bucket_ptr;
142 typedef typename base_class::list_iterator list_iterator;
144 //typedef typename bucket_type::key_type key_type;
148 /// Value pointer type (const for const_iterator)
149 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
150 /// Value reference type (const for const_iterator)
151 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
153 /// Key-value pair pointer type (const for const_iterator)
154 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
155 /// Key-value pair reference type (const for const_iterator)
156 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
160 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
161 : base_class( it, pFirst, pLast )
172 iterator_type( const iterator_type& src )
176 /// Dereference operator
177 pair_ptr operator ->() const
179 assert( base_class::m_pCurBucket != nullptr );
180 return base_class::m_itList.operator ->();
183 /// Dereference operator
184 pair_ref operator *() const
186 assert( base_class::m_pCurBucket != nullptr );
187 return base_class::m_itList.operator *();
191 iterator_type& operator ++()
193 base_class::operator++();
197 /// Assignment operator
198 iterator_type& operator = (const iterator_type& src)
200 base_class::operator =(src);
204 /// Returns current bucket (debug function)
205 bucket_ptr bucket() const
207 return base_class::bucket();
210 /// Equality operator
212 bool operator ==(iterator_type<C> const& i )
214 return base_class::operator ==( i );
216 /// Equality operator
218 bool operator !=(iterator_type<C> const& i )
220 return !( *this == i );
226 typedef iterator_type< false > iterator;
228 /// Const forward iterator
229 typedef iterator_type< true > const_iterator;
231 /// Returns a forward iterator addressing the first element in a map
233 For empty map \code begin() == end() \endcode
237 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
240 /// Returns an iterator that addresses the location succeeding the last element in a map
242 Do not use the value returned by <tt>end</tt> function to access any item.
243 The returned value can be used only to control reaching the end of the map.
244 For empty map \code begin() == end() \endcode
248 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
251 /// Returns a forward const iterator addressing the first element in a map
253 const_iterator begin() const
255 return get_const_begin();
257 const_iterator cbegin() const
259 return get_const_begin();
263 /// Returns an const iterator that addresses the location succeeding the last element in a map
265 const_iterator end() const
267 return get_const_end();
269 const_iterator cend() const
271 return get_const_end();
277 const_iterator get_const_begin() const
279 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
281 const_iterator get_const_end() const
283 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
288 /// Initializes the map
290 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
291 when you create an object.
292 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
293 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
294 Note, that many popular STL hash map implementation uses load factor 1.
296 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
299 size_t nMaxItemCount, ///< estimation of max item count in the hash map
300 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
301 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
303 // GC and OrderedList::gc must be the same
304 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
306 // atomicity::empty_item_counter is not allowed as a item counter
307 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
308 "cds::atomicity::empty_item_counter is not allowed as a item counter");
310 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
313 /// Clears hash map and destroys it
317 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
320 /// Inserts new node with key and default value
322 The function creates a node with \p key and default value, and then inserts the node created into the map.
325 - The \p key_type should be constructible from value of type \p K.
326 In trivial case, \p K is equal to \ref key_type.
327 - The \p mapped_type should be default-constructible.
329 The function applies RCU lock internally.
331 Returns \p true if inserting successful, \p false otherwise.
333 template <typename K>
334 bool insert( const K& key )
336 const bool bRet = bucket( key ).insert( key );
344 The function creates a node with copy of \p val value
345 and then inserts the node created into the map.
348 - The \p key_type should be constructible from \p key of type \p K.
349 - The \p mapped_type should be constructible from \p val of type \p V.
351 The function applies RCU lock internally.
353 Returns \p true if \p val is inserted into the map, \p false otherwise.
355 template <typename K, typename V>
356 bool insert( K const& key, V const& val )
358 const bool bRet = bucket( key ).insert( key, val );
364 /// Inserts new node and initialize it by a functor
366 This function inserts new node with key \p key and if inserting is successful then it calls
367 \p func functor with signature
370 void operator()( value_type& item );
374 The argument \p item of user-defined functor \p func is the reference
375 to the map's item inserted:
376 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
377 - <tt>item.second</tt> is a reference to item's value that may be changed.
379 The user-defined functor is called only if inserting is successful.
381 The key_type should be constructible from value of type \p K.
383 The function allows to split creating of new item into two part:
384 - create item from \p key;
385 - insert new item into the map;
386 - if inserting is successful, initialize the value of item by calling \p func functor
388 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
389 it is preferable that the initialization should be completed only if inserting is successful.
391 The function applies RCU lock internally.
393 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
394 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
397 template <typename K, typename Func>
398 bool insert_with( const K& key, Func func )
400 const bool bRet = bucket( key ).insert_with( key, func );
407 /// Ensures that the \p key exists in the map
409 The operation performs inserting or changing data with lock-free manner.
411 If the \p key not found in the map, then the new item created from \p key
412 is inserted into the map (note that in this case the \ref key_type should be
413 constructible from type \p K).
414 Otherwise, the functor \p func is called with item found.
415 The functor \p Func may be a function with signature:
417 void func( bool bNew, value_type& item );
422 void operator()( bool bNew, value_type& item );
427 - \p bNew - \p true if the item has been inserted, \p false otherwise
428 - \p item - item of the list
430 The functor may change any fields of the \p item.second that is \ref mapped_type.
432 The function applies RCU lock internally.
434 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
435 \p second is true if new item has been added or \p false if the item with \p key
436 already is in the list.
438 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
439 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
442 template <typename K, typename Func>
443 std::pair<bool, bool> ensure( K const& key, Func func )
445 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
446 if ( bRet.first && bRet.second )
451 /// For key \p key inserts data of type \p mapped_type created from \p args
453 \p key_type should be constructible from type \p K
455 Returns \p true if inserting successful, \p false otherwise.
457 template <typename K, typename... Args>
458 bool emplace( K&& key, Args&&... args )
460 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
466 /// Deletes \p key from the map
467 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_val
469 RCU \p synchronize method can be called. RCU should not be locked.
471 Return \p true if \p key is found and deleted, \p false otherwise
473 template <typename K>
474 bool erase( const K& key )
476 const bool bRet = bucket( key ).erase( key );
482 /// Deletes the item from the map using \p pred predicate for searching
484 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_val "erase(K const&)"
485 but \p pred is used for key comparing.
486 \p Less predicate has the interface like \p std::less.
487 \p Less must imply the same element order as the comparator used for building the map.
489 template <typename K, typename Less>
490 bool erase_with( const K& key, Less pred )
492 const bool bRet = bucket( key ).erase_with( key, pred );
498 /// Deletes \p key from the map
499 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_func
501 The function searches an item with key \p key, calls \p f functor
502 and deletes the item. If \p key is not found, the functor is not called.
504 The functor \p Func interface:
507 void operator()(value_type& item) { ... }
511 RCU \p synchronize method can be called. RCU should not be locked.
513 Return \p true if key is found and deleted, \p false otherwise
515 template <typename K, typename Func>
516 bool erase( const K& key, Func f )
518 const bool bRet = bucket( key ).erase( key, f );
524 /// Deletes the item from the map using \p pred predicate for searching
526 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_func "erase(K const&, Func)"
527 but \p pred is used for key comparing.
528 \p Less functor has the interface like \p std::less.
529 \p Less must imply the same element order as the comparator used for building the map.
531 template <typename K, typename Less, typename Func>
532 bool erase_with( const K& key, Less pred, Func f )
534 const bool bRet = bucket( key ).erase_with( key, pred, f );
540 /// Extracts an item from the map
541 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_extract
542 The function searches an item with key equal to \p key,
543 unlinks it from the map, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
544 If the item is not found the function return an empty \p exempt_ptr.
546 The function just excludes the key from the map and returns a pointer to item found.
547 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
548 - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
549 - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
550 See ordered list implementation for details.
553 #include <cds/urcu/general_buffered.h>
554 #include <cds/container/michael_kvlist_rcu.h>
555 #include <cds/container/michael_map_rcu.h>
557 typedef cds::urcu::gc< general_buffered<> > rcu;
558 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
559 typedef cds::container::MichaelHashMap< rcu, rcu_michael_list, foo_traits > rcu_michael_map;
561 rcu_michael_map theMap;
564 rcu_michael_map::exempt_ptr p;
566 // For MichaelList we should not lock RCU
568 // Note that you must not delete the item found inside the RCU lock
569 p = theMap.extract( 10 );
571 // do something with p
575 // We may safely release p here
576 // release() passes the pointer to RCU reclamation cycle
580 template <typename K>
581 exempt_ptr extract( K const& key )
583 exempt_ptr p = bucket( key ).extract( key );
589 /// Extracts an item from the map using \p pred predicate for searching
591 The function is an analog of \p extract(K const&) 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 map.
595 template <typename K, typename Less>
596 exempt_ptr extract_with( K const& key, Less pred )
598 exempt_ptr p = bucket( key ).extract_with( key, pred );
604 /// Finds the key \p key
605 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_cfunc
607 The function searches the item with key equal to \p key and calls the functor \p f for item found.
608 The interface of \p Func functor is:
611 void operator()( value_type& item );
614 where \p item is the item found.
616 The functor may change \p item.second. Note that the functor is only guarantee
617 that \p item cannot be disposed during functor is executing.
618 The functor does not serialize simultaneous access to the map's \p item. If such access is
619 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
621 The function applies RCU lock internally.
623 The function returns \p true if \p key is found, \p false otherwise.
625 template <typename K, typename Func>
626 bool find( K const& key, Func f )
628 return bucket( key ).find( key, f );
631 /// Finds the key \p val using \p pred predicate for searching
633 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_cfunc "find(K const&, Func)"
634 but \p pred is used for key comparing.
635 \p Less functor has the interface like \p std::less.
636 \p Less must imply the same element order as the comparator used for building the map.
638 template <typename K, typename Less, typename Func>
639 bool find_with( K const& key, Less pred, Func f )
641 return bucket( key ).find_with( key, pred, f );
644 /// Finds the key \p key
645 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_val
647 The function searches the item with key equal to \p key
648 and returns \p true if it is found, and \p false otherwise.
650 The function applies RCU lock internally.
652 template <typename K>
653 bool find( K const& key )
655 return bucket( key ).find( key );
658 /// Finds the key \p val using \p pred predicate for searching
660 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_val "find(K const&)"
661 but \p pred is used for key comparing.
662 \p Less functor has the interface like \p std::less.
663 \p Less must imply the same element order as the comparator used for building the map.
665 template <typename K, typename Less>
666 bool find_with( K const& key, Less pred )
668 return bucket( key ).find_with( key, pred );
671 /// Finds \p key and return the item found
672 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get
673 The function searches the item with key equal to \p key and returns the pointer to item found.
674 If \p key is not found it returns \p nullptr.
675 Note the type of returned value depends on underlying \p bucket_type.
676 For details, see documentation of ordered list you use.
678 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
680 RCU should be locked before call of this function.
681 Returned item is valid only while RCU is locked:
683 typedef cds::container::MichaelHashMap< your_template_parameters > hash_map;
686 typename hash_map::raw_ptr gp;
689 hash_map::rcu_lock lock;
691 gp = theMap.get( 5 );
696 // Unlock RCU by rcu_lock destructor
697 // gp can be reclaimed at any time after RCU has been unlocked
701 template <typename K>
702 raw_ptr get( K const& key )
704 return bucket( key ).get( key );
707 /// Finds \p key and return the item found
709 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_get "get(K const&)"
710 but \p pred is used for comparing the keys.
712 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
714 \p pred must imply the same element order as the comparator used for building the map.
716 template <typename K, typename Less>
717 raw_ptr get_with( K const& key, Less pred )
719 return bucket( key ).get_with( key, pred );
722 /// Clears the map (not atomic)
724 The function erases all items from the map.
726 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
727 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
728 <tt> empty() </tt> may return \p true but the map may contain item(s).
729 Therefore, \p clear may be used only for debugging purposes.
731 RCU \p synchronize method can be called. RCU should not be locked.
735 for ( size_t i = 0; i < bucket_count(); ++i )
736 m_Buckets[i].clear();
737 m_ItemCounter.reset();
740 /// Checks if the map is empty
742 Emptiness is checked by item counting: if item count is zero then the map is empty.
743 Thus, the correct item counting is an important part of the map implementation.
750 /// Returns item count in the map
753 return m_ItemCounter;
756 /// Returns the size of hash table
758 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
759 the value returned is an constant depending on object initialization parameters;
760 see \p MichaelHashMap::MichaelHashMap for explanation.
762 size_t bucket_count() const
764 return m_nHashBitmask + 1;
767 }} // namespace cds::container
769 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H