3 #ifndef __CDS_CONTAINER_MICHAEL_MAP_H
4 #define __CDS_CONTAINER_MICHAEL_MAP_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
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 nullptr 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 != nullptr );
257 return base_class::m_itList.operator ->();
260 /// Dereference operator
261 pair_ref operator *() const
263 assert( base_class::m_pCurBucket != nullptr );
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 \p std::ref
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 \p std::ref
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 /// For key \p key inserts data of type \p mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
521 \p key_type should be constructible from type \p K
523 Returns \p true if inserting successful, \p false otherwise.
525 template <typename K, typename... Args>
526 bool emplace( K&& key, Args&&... args )
528 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
534 /// Deletes \p key from the map
535 /** \anchor cds_nonintrusive_MichaelMap_erase_val
537 Return \p true if \p key is found and deleted, \p false otherwise
539 template <typename K>
540 bool erase( K const& key )
542 const bool bRet = bucket( key ).erase( key );
548 /// Deletes the item from the map using \p pred predicate for searching
550 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
551 but \p pred is used for key comparing.
552 \p Less functor has the interface like \p std::less.
553 \p Less must imply the same element order as the comparator used for building the map.
555 template <typename K, typename Less>
556 bool erase_with( K const& key, Less pred )
558 const bool bRet = bucket( key ).erase_with( key, pred );
564 /// Deletes \p key from the map
565 /** \anchor cds_nonintrusive_MichaelMap_erase_func
567 The function searches an item with key \p key, calls \p f functor
568 and deletes the item. If \p key is not found, the functor is not called.
570 The functor \p Func interface:
573 void operator()(value_type& item) { ... }
576 The functor may be passed by reference using <tt>boost:ref</tt>
578 Return \p true if key is found and deleted, \p false otherwise
580 template <typename K, typename Func>
581 bool erase( K const& key, Func f )
583 const bool bRet = bucket( key ).erase( key, f );
589 /// Deletes the item from the map using \p pred predicate for searching
591 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
592 but \p pred is used for key comparing.
593 \p Less functor has the interface like \p std::less.
594 \p Less must imply the same element order as the comparator used for building the map.
596 template <typename K, typename Less, typename Func>
597 bool erase_with( K const& key, Less pred, Func f )
599 const bool bRet = bucket( key ).erase_with( key, pred, f );
605 /// Extracts the item with specified \p key
606 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
607 The function searches an item with key equal to \p key,
608 unlinks it from the set, and returns it in \p dest parameter.
609 If the item with key equal to \p key is not found the function returns \p false.
611 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
613 The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
614 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
618 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
622 michael_map::guarded_ptr gp;
623 theMap.extract( gp, 5 );
627 // Destructor of gp releases internal HP guard
631 template <typename K>
632 bool extract( guarded_ptr& dest, K const& key )
634 const bool bRet = bucket( key ).extract( dest, key );
640 /// Extracts the item using compare functor \p pred
642 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(guarded_ptr&, K const&)"
643 but \p pred predicate is used for key comparing.
645 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
647 \p pred must imply the same element order as the comparator used for building the map.
649 template <typename K, typename Less>
650 bool extract_with( guarded_ptr& dest, K const& key, Less pred )
652 const bool bRet = bucket( key ).extract_with( dest, key, pred );
658 /// Finds the key \p key
659 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
661 The function searches the item with key equal to \p key and calls the functor \p f for item found.
662 The interface of \p Func functor is:
665 void operator()( value_type& item );
668 where \p item is the item found.
670 You may pass \p f argument by reference using \p std::ref.
672 The functor may change \p item.second. Note that the functor is only guarantee
673 that \p item cannot be disposed during functor is executing.
674 The functor does not serialize simultaneous access to the map's \p item. If such access is
675 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
677 The function returns \p true if \p key is found, \p false otherwise.
679 template <typename K, typename Func>
680 bool find( K const& key, Func f )
682 return bucket( key ).find( key, f );
685 /// Finds the key \p val using \p pred predicate for searching
687 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
688 but \p pred is used for key comparing.
689 \p Less functor has the interface like \p std::less.
690 \p Less must imply the same element order as the comparator used for building the map.
692 template <typename K, typename Less, typename Func>
693 bool find_with( K const& key, Less pred, Func f )
695 return bucket( key ).find_with( key, pred, f );
698 /// Finds the key \p key
699 /** \anchor cds_nonintrusive_MichaelMap_find_val
700 The function searches the item with key equal to \p key
701 and returns \p true if it is found, and \p false otherwise.
703 template <typename K>
704 bool find( K const& key )
706 return bucket( key ).find( key );
709 /// Finds the key \p val using \p pred predicate for searching
711 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_val "find(K const&)"
712 but \p pred is used for key comparing.
713 \p Less functor has the interface like \p std::less.
714 \p Less must imply the same element order as the comparator used for building the map.
716 template <typename K, typename Less>
717 bool find_with( K const& key, Less pred )
719 return bucket( key ).find_with( key, pred );
722 /// Finds \p key and return the item found
723 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
724 The function searches the item with key equal to \p key
725 and assigns the item found to guarded pointer \p ptr.
726 The function returns \p true if \p key is found, and \p false otherwise.
727 If \p key is not found the \p ptr parameter is not changed.
729 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
733 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
737 michael_map::guarded_ptr gp;
738 if ( theMap.get( gp, 5 )) {
742 // Destructor of guarded_ptr releases internal HP guard
746 Note the compare functor specified for \p OrderedList template parameter
747 should accept a parameter of type \p K that can be not the same as \p key_type.
749 template <typename K>
750 bool get( guarded_ptr& ptr, K const& key )
752 return bucket( key ).get( ptr, key );
755 /// Finds \p key and return the item found
757 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( guarded_ptr& ptr, K const&)"
758 but \p pred is used for comparing the keys.
760 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
762 \p pred must imply the same element order as the comparator used for building the map.
764 template <typename K, typename Less>
765 bool get_with( guarded_ptr& ptr, K const& key, Less pred )
767 return bucket( key ).get_with( ptr, key, pred );
770 /// Clears the map (non-atomic)
772 The function erases all items from the map.
774 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
775 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
776 <tt> empty() </tt> may return \p true but the map may contain item(s).
777 Therefore, \p clear may be used only for debugging purposes.
781 for ( size_t i = 0; i < bucket_count(); ++i )
782 m_Buckets[i].clear();
783 m_ItemCounter.reset();
786 /// Checks if the map is empty
788 Emptiness is checked by item counting: if item count is zero then the map is empty.
789 Thus, the correct item counting is an important part of the map implementation.
796 /// Returns item count in the map
799 return m_ItemCounter;
802 /// Returns the size of hash table
804 Since MichaelHashMap cannot dynamically extend the hash table size,
805 the value returned is an constant depending on object initialization parameters;
806 see MichaelHashMap::MichaelHashMap for explanation.
808 size_t bucket_count() const
810 return m_nHashBitmask + 1;
813 }} // namespace cds::container
815 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_H