3 #ifndef __CDS_CONTAINER_MICHAEL_MAP_H
4 #define __CDS_CONTAINER_MICHAEL_MAP_H
6 #include <cds/container/michael_map_base.h>
7 #include <cds/details/allocator.h>
9 namespace cds { namespace container {
11 /// Michael's hash map
12 /** @ingroup cds_nonintrusive_map
13 \anchor cds_nonintrusive_MichaelHashMap_hp
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 GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
25 from the \p libcds library.
26 Note the \p GC must be the same as the GC used for \p OrderedList
27 - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, MichaelKVList
28 or LazyKVList. The ordered list implementation specifies the \p Key and \p Value types stored in the hash-map,
29 the reclamation schema \p GC used by hash-map, the comparison functor for the type \p Key and other features
30 specific for the ordered list.
31 - \p Traits - type traits. See michael_map::type_traits for explanation.
33 Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction
34 (this metafunction is a synonym for michael_set::make_traits).
35 For \p michael_map::make_traits the following option may be used:
36 - opt::hash - mandatory option, specifies hash functor.
37 - opt::item_counter - optional, specifies item counting policy. See michael_map::type_traits for explanation.
38 - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
40 Many of the class function take a key argument of type \p K that in general is not \ref key_type.
41 \p key_type and an argument of template type \p K must meet the following requirements:
42 - \p key_type should be constructible from value of type \p K;
43 - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
44 <tt> hash( key_type(key) ) == hash( key ) </tt>
45 - values of type \p key_type and \p K should be comparable
47 There are the specializations:
48 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/michael_map_rcu.h</tt>,
49 see \ref cds_nonintrusive_MichaelHashMap_rcu "MichaelHashMap<RCU>".
50 - for \ref cds::gc::nogc declared in <tt>cds/container/michael_map_nogc.h</tt>,
51 see \ref cds_nonintrusive_MichaelHashMap_nogc "MichaelHashMap<gc::nogc>".
55 The class supports a forward iterator (\ref iterator and \ref const_iterator).
56 The iteration is unordered.
57 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
58 so, the element cannot be reclaimed while the iterator object is alive.
59 However, passing an iterator object between threads is dangerous.
61 \warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
62 all elements in the set: any concurrent deletion can exclude the element
63 pointed by the iterator from the set, and your iteration can be terminated
64 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
66 Remember, each iterator object requires an additional hazard pointer, that may be
67 a limited resource for \p GC like as gc::HP and gc::HRC (for gc::PTB the count of
70 The iterator class supports the following minimalistic interface:
77 iterator( iterator const& s);
79 value_type * operator ->() const;
80 value_type& operator *() const;
83 iterator& operator ++();
86 iterator& operator = (const iterator& src);
88 bool operator ==(iterator const& i ) const;
89 bool operator !=(iterator const& i ) const;
92 Note, the iterator object returned by \ref end, \p cend member functions points to \p NULL and should not be dereferenced.
94 \anchor cds_nonintrusive_MichaelHashMap_how_touse
97 Suppose, you want to make \p int to \p int map for Hazard Pointer garbage collector. You should
98 choose suitable ordered list class that will be used as a bucket for the map; it may be MichaelKVList.
100 #include <cds/container/michael_kvlist_hp.h> // MichaelKVList for gc::HP
101 #include <cds/container/michael_map.h> // MIchaelHashMap
103 // List traits based on std::less predicate
104 struct list_traits: public cds::container::michael_list::type_traits
106 typedef std::less<int> less;
110 typedef cds::container::MichaelKVList< cds::gc::HP, int, int, list_traits> int2int_list;
113 struct map_traits: public cds::container::michael_map::type_traits
116 size_t operator()( int i ) const
118 return cds::opt::v::hash<int>()( i );
124 typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list, map_traits > int2int_map;
126 // Now you can use int2int_map class
132 theMap.insert( 100 );
137 You may use option-based declaration:
139 #include <cds/container/michael_kvlist_hp.h> // MichaelKVList for gc::HP
140 #include <cds/container/michael_map.h> // MIchaelHashMap
143 typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
144 typename cds::container::michael_list::make_traits<
145 cds::container::opt::less< std::less<int> > // item comparator option
150 typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list,
151 cds::container::michael_map::make_traits<
152 cc::opt::hash< cds::opt::v::hash<int> >
160 #ifdef CDS_DOXYGEN_INVOKED
161 class Traits = michael_map::type_traits
169 typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation
170 typedef Traits options ; ///< Traits template parameters
172 typedef typename bucket_type::key_type key_type ; ///< key type
173 typedef typename bucket_type::mapped_type mapped_type ; ///< value type
174 typedef typename bucket_type::value_type value_type ; ///< key/value pair stored in the map
176 typedef GC gc ; ///< Garbage collector
177 typedef typename bucket_type::key_comparator key_comparator ; ///< key compare functor
179 /// Hash functor for \ref key_type and all its derivatives that you use
180 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
181 typedef typename options::item_counter item_counter ; ///< Item counter type
183 /// Bucket table allocator
184 typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
185 typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
188 item_counter m_ItemCounter ; ///< Item counter
189 hash m_HashFunctor ; ///< Hash functor
191 bucket_type * m_Buckets ; ///< bucket table
195 const size_t m_nHashBitmask;
199 /// Calculates hash value of \p key
200 template <typename Q>
201 size_t hash_value( Q const& key ) const
203 return m_HashFunctor( key ) & m_nHashBitmask;
206 /// Returns the bucket (ordered list) for \p key
207 template <typename Q>
208 bucket_type& bucket( Q const& key )
210 return m_Buckets[ hash_value( key ) ];
216 template <bool IsConst>
217 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
219 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
220 friend class MichaelHashMap;
223 typedef typename base_class::bucket_ptr bucket_ptr;
224 typedef typename base_class::list_iterator list_iterator;
227 /// Value pointer type (const for const_iterator)
228 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
229 /// Value reference type (const for const_iterator)
230 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
232 /// Key-value pair pointer type (const for const_iterator)
233 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
234 /// Key-value pair reference type (const for const_iterator)
235 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
238 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
239 : base_class( it, pFirst, pLast )
249 iterator_type( const iterator_type& src )
253 /// Dereference operator
254 pair_ptr operator ->() const
256 assert( base_class::m_pCurBucket != null_ptr<bucket_ptr>() );
257 return base_class::m_itList.operator ->();
260 /// Dereference operator
261 pair_ref operator *() const
263 assert( base_class::m_pCurBucket != null_ptr<bucket_ptr>() );
264 return base_class::m_itList.operator *();
268 iterator_type& operator ++()
270 base_class::operator++();
274 /// Assignment operator
275 iterator_type& operator = (const iterator_type& src)
277 base_class::operator =(src);
281 /// Returns current bucket (debug function)
282 bucket_ptr bucket() const
284 return base_class::bucket();
287 /// Equality operator
289 bool operator ==(iterator_type<C> const& i )
291 return base_class::operator ==( i );
293 /// Equality operator
295 bool operator !=(iterator_type<C> const& i )
297 return !( *this == i );
304 typedef iterator_type< false > iterator;
306 /// Const forward iterator
307 typedef iterator_type< true > const_iterator;
309 /// Returns a forward iterator addressing the first element in a map
311 For empty map \code begin() == end() \endcode
315 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
318 /// Returns an iterator that addresses the location succeeding the last element in a map
320 Do not use the value returned by <tt>end</tt> function to access any item.
321 The returned value can be used only to control reaching the end of the map.
322 For empty map \code begin() == end() \endcode
326 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
329 /// Returns a forward const iterator addressing the first element in a map
331 const_iterator begin() const
333 return get_const_begin();
335 const_iterator cbegin()
337 return get_const_begin();
341 /// Returns an const iterator that addresses the location succeeding the last element in a map
343 const_iterator end() const
345 return get_const_end();
347 const_iterator cend()
349 return get_const_end();
355 const_iterator get_const_begin() const
357 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
359 const_iterator get_const_end() const
361 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
366 /// Initializes the map
368 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
369 when you create an object.
370 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
371 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
372 Note, that many popular STL hash map implementation uses load factor 1.
374 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
377 size_t nMaxItemCount, ///< estimation of max item count in the hash map
378 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
379 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
381 // GC and OrderedList::gc must be the same
382 static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
384 // atomicity::empty_item_counter is not allowed as a item counter
385 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
387 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
390 /// Clears hash map and destroys it
394 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
397 /// Inserts new node with key and default value
399 The function creates a node with \p key and default value, and then inserts the node created into the map.
402 - The \p key_type should be constructible from value of type \p K.
403 In trivial case, \p K is equal to \p key_type.
404 - The \p mapped_type should be default-constructible.
406 Returns \p true if inserting successful, \p false otherwise.
408 template <typename K>
409 bool insert( const K& key )
411 const bool bRet = bucket( key ).insert( key );
419 The function creates a node with copy of \p val value
420 and then inserts the node created into the map.
423 - The \p key_type should be constructible from \p key of type \p K.
424 - The \p mapped_type should be constructible from \p val of type \p V.
426 Returns \p true if \p val is inserted into the map, \p false otherwise.
428 template <typename K, typename V>
429 bool insert( K const& key, V const& val )
431 const bool bRet = bucket( key ).insert( key, val );
437 /// Inserts new node and initialize it by a functor
439 This function inserts new node with key \p key and if inserting is successful then it calls
440 \p func functor with signature
443 void operator()( value_type& item );
447 The argument \p item of user-defined functor \p func is the reference
448 to the map's item inserted:
449 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
450 - <tt>item.second</tt> is a reference to item's value that may be changed.
452 User-defined functor \p func should guarantee that during changing item's value no any other changes
453 could be made on this map's item by concurrent threads.
454 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
455 and it is called only if inserting is successful.
457 The key_type should be constructible from value of type \p K.
459 The function allows to split creating of new item into two part:
460 - create item from \p key;
461 - insert new item into the map;
462 - if inserting is successful, initialize the value of item by calling \p func functor
464 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
465 it is preferable that the initialization should be completed only if inserting is successful.
467 template <typename K, typename Func>
468 bool insert_key( const K& key, Func func )
470 const bool bRet = bucket( key ).insert_key( key, func );
477 /// Ensures that the \p key exists in the map
479 The operation performs inserting or changing data with lock-free manner.
481 If the \p key not found in the map, then the new item created from \p key
482 is inserted into the map (note that in this case the \p key_type should be
483 constructible from type \p K).
484 Otherwise, the functor \p func is called with item found.
485 The functor \p Func may be a function with signature:
487 void func( bool bNew, value_type& item );
492 void operator()( bool bNew, value_type& item );
497 - \p bNew - \p true if the item has been inserted, \p false otherwise
498 - \p item - item of the list
500 The functor may change any fields of the \p item.second that is \p mapped_type;
501 however, \p func must guarantee that during changing no any other modifications
502 could be made on this item by concurrent threads.
504 You may pass \p func argument by reference using <tt>boost::ref</tt>.
506 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
507 \p second is true if new item has been added or \p false if the item with \p key
508 already is in the list.
510 template <typename K, typename Func>
511 std::pair<bool, bool> ensure( K const& key, Func func )
513 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
514 if ( bRet.first && bRet.second )
519 # ifdef CDS_EMPLACE_SUPPORT
520 /// For key \p key inserts data of type \p mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
522 \p key_type should be constructible from type \p K
524 Returns \p true if inserting successful, \p false otherwise.
526 This function is available only for compiler that supports
527 variadic template and move semantics
529 template <typename K, typename... Args>
530 bool emplace( K&& key, Args&&... args )
532 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
539 /// Deletes \p key from the map
540 /** \anchor cds_nonintrusive_MichaelMap_erase_val
542 Return \p true if \p key is found and deleted, \p false otherwise
544 template <typename K>
545 bool erase( K const& key )
547 const bool bRet = bucket( key ).erase( key );
553 /// Deletes the item from the map using \p pred predicate for searching
555 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
556 but \p pred is used for key comparing.
557 \p Less functor has the interface like \p std::less.
558 \p Less must imply the same element order as the comparator used for building the map.
560 template <typename K, typename Less>
561 bool erase_with( K const& key, Less pred )
563 const bool bRet = bucket( key ).erase_with( key, pred );
569 /// Deletes \p key from the map
570 /** \anchor cds_nonintrusive_MichaelMap_erase_func
572 The function searches an item with key \p key, calls \p f functor
573 and deletes the item. If \p key is not found, the functor is not called.
575 The functor \p Func interface:
578 void operator()(value_type& item) { ... }
581 The functor may be passed by reference using <tt>boost:ref</tt>
583 Return \p true if key is found and deleted, \p false otherwise
585 template <typename K, typename Func>
586 bool erase( K const& key, Func f )
588 const bool bRet = bucket( key ).erase( key, f );
594 /// Deletes the item from the map using \p pred predicate for searching
596 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
597 but \p pred is used for key comparing.
598 \p Less functor has the interface like \p std::less.
599 \p Less must imply the same element order as the comparator used for building the map.
601 template <typename K, typename Less, typename Func>
602 bool erase_with( K const& key, Less pred, Func f )
604 const bool bRet = bucket( key ).erase_with( key, pred, f );
610 /// Extracts the item with specified \p key
611 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
612 The function searches an item with key equal to \p key,
613 unlinks it from the set, and returns it in \p dest parameter.
614 If the item with key equal to \p key is not found the function returns \p false.
616 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
618 The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
619 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
623 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
627 michael_map::guarded_ptr gp;
628 theMap.extract( gp, 5 );
632 // Destructor of gp releases internal HP guard
636 template <typename K>
637 bool extract( guarded_ptr& dest, K const& key )
639 const bool bRet = bucket( key ).extract( dest, key );
645 /// Extracts the item using compare functor \p pred
647 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(guarded_ptr&, K const&)"
648 but \p pred predicate is used for key comparing.
650 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
652 \p pred must imply the same element order as the comparator used for building the map.
654 template <typename K, typename Less>
655 bool extract_with( guarded_ptr& dest, K const& key, Less pred )
657 const bool bRet = bucket( key ).extract_with( dest, key, pred );
663 /// Finds the key \p key
664 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
666 The function searches the item with key equal to \p key and calls the functor \p f for item found.
667 The interface of \p Func functor is:
670 void operator()( value_type& item );
673 where \p item is the item found.
675 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
677 The functor may change \p item.second. Note that the functor is only guarantee
678 that \p item cannot be disposed during functor is executing.
679 The functor does not serialize simultaneous access to the map's \p item. If such access is
680 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
682 The function returns \p true if \p key is found, \p false otherwise.
684 template <typename K, typename Func>
685 bool find( K const& key, Func f )
687 return bucket( key ).find( key, f );
690 /// Finds the key \p val using \p pred predicate for searching
692 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
693 but \p pred is used for key comparing.
694 \p Less functor has the interface like \p std::less.
695 \p Less must imply the same element order as the comparator used for building the map.
697 template <typename K, typename Less, typename Func>
698 bool find_with( K const& key, Less pred, Func f )
700 return bucket( key ).find_with( key, pred, f );
703 /// Finds the key \p key
704 /** \anchor cds_nonintrusive_MichaelMap_find_val
705 The function searches the item with key equal to \p key
706 and returns \p true if it is found, and \p false otherwise.
708 template <typename K>
709 bool find( K const& key )
711 return bucket( key ).find( key );
714 /// Finds the key \p val using \p pred predicate for searching
716 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_val "find(K const&)"
717 but \p pred is used for key comparing.
718 \p Less functor has the interface like \p std::less.
719 \p Less must imply the same element order as the comparator used for building the map.
721 template <typename K, typename Less>
722 bool find_with( K const& key, Less pred )
724 return bucket( key ).find_with( key, pred );
727 /// Finds \p key and return the item found
728 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
729 The function searches the item with key equal to \p key
730 and assigns the item found to guarded pointer \p ptr.
731 The function returns \p true if \p key is found, and \p false otherwise.
732 If \p key is not found the \p ptr parameter is not changed.
734 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
738 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
742 michael_map::guarded_ptr gp;
743 if ( theMap.get( gp, 5 )) {
747 // Destructor of guarded_ptr releases internal HP guard
751 Note the compare functor specified for \p OrderedList template parameter
752 should accept a parameter of type \p K that can be not the same as \p key_type.
754 template <typename K>
755 bool get( guarded_ptr& ptr, K const& key )
757 return bucket( key ).get( ptr, key );
760 /// Finds \p key and return the item found
762 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( guarded_ptr& ptr, K const&)"
763 but \p pred is used for comparing the keys.
765 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
767 \p pred must imply the same element order as the comparator used for building the map.
769 template <typename K, typename Less>
770 bool get_with( guarded_ptr& ptr, K const& key, Less pred )
772 return bucket( key ).get_with( ptr, key, pred );
775 /// Clears the map (non-atomic)
777 The function erases all items from the map.
779 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
780 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
781 <tt> empty() </tt> may return \p true but the map may contain item(s).
782 Therefore, \p clear may be used only for debugging purposes.
786 for ( size_t i = 0; i < bucket_count(); ++i )
787 m_Buckets[i].clear();
788 m_ItemCounter.reset();
791 /// Checks if the map is empty
793 Emptiness is checked by item counting: if item count is zero then the map is empty.
794 Thus, the correct item counting is an important part of the map implementation.
801 /// Returns item count in the map
804 return m_ItemCounter;
807 /// Returns the size of hash table
809 Since MichaelHashMap cannot dynamically extend the hash table size,
810 the value returned is an constant depending on object initialization parameters;
811 see MichaelHashMap::MichaelHashMap for explanation.
813 size_t bucket_count() const
815 return m_nHashBitmask + 1;
818 }} // namespace cds::container
820 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_H