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, \p MichaelKVList
28 or \p 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 - map traits, default is \p michael_map::traits.
32 Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction.
34 Many of the class function take a key argument of type \p K that in general is not \p key_type.
35 \p key_type and an argument of template type \p K must meet the following requirements:
36 - \p key_type should be constructible from value of type \p K;
37 - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
38 <tt> hash( key_type(key) ) == hash( key ) </tt>
39 - values of type \p key_type and \p K should be comparable
41 There are the specializations:
42 - for \ref cds_urcu_desc "RCU" - declared in <tt>cds/container/michael_map_rcu.h</tt>,
43 see \ref cds_nonintrusive_MichaelHashMap_rcu "MichaelHashMap<RCU>".
44 - for \p cds::gc::nogc declared in <tt>cds/container/michael_map_nogc.h</tt>,
45 see \ref cds_nonintrusive_MichaelHashMap_nogc "MichaelHashMap<gc::nogc>".
49 The class supports a forward iterator (\ref iterator and \ref const_iterator).
50 The iteration is unordered.
51 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
52 so, the element cannot be reclaimed while the iterator object is alive.
53 However, passing an iterator object between threads is dangerous.
55 @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
56 all elements in the set: any concurrent deletion can exclude the element
57 pointed by the iterator from the set, and your iteration can be terminated
58 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
60 Remember, each iterator object requires an additional hazard pointer, that may be
61 a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of
64 The iterator class supports the following minimalistic interface:
71 iterator( iterator const& s);
73 value_type * operator ->() const;
74 value_type& operator *() const;
77 iterator& operator ++();
80 iterator& operator = (const iterator& src);
82 bool operator ==(iterator const& i ) const;
83 bool operator !=(iterator const& i ) const;
86 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
88 \anchor cds_nonintrusive_MichaelHashMap_how_touse
91 Suppose, you want to make \p int to \p int map for Hazard Pointer garbage collector. You should
92 choose suitable ordered list class that will be used as a bucket for the map; it may be \p MichaelKVList.
94 #include <cds/container/michael_kvlist_hp.h> // MichaelKVList for gc::HP
95 #include <cds/container/michael_map.h> // MichaelHashMap
97 // List traits based on std::less predicate
98 struct list_traits: public cds::container::michael_list::traits
100 typedef std::less<int> less;
104 typedef cds::container::MichaelKVList< cds::gc::HP, int, int, list_traits> int2int_list;
107 struct map_traits: public cds::container::michael_map::traits
110 size_t operator()( int i ) const
112 return cds::opt::v::hash<int>()( i );
118 typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list, map_traits > int2int_map;
120 // Now you can use int2int_map class
126 theMap.insert( 100 );
131 You may use option-based declaration:
133 #include <cds/container/michael_kvlist_hp.h> // MichaelKVList for gc::HP
134 #include <cds/container/michael_map.h> // MichaelHashMap
137 typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
138 typename cds::container::michael_list::make_traits<
139 cds::container::opt::less< std::less<int> > // item comparator option
144 typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list,
145 cds::container::michael_map::make_traits<
146 cc::opt::hash< cds::opt::v::hash<int> >
154 #ifdef CDS_DOXYGEN_INVOKED
155 class Traits = michael_map::traits
163 typedef GC gc; ///< Garbage collector
164 typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket
165 typedef Traits traits; ///< Map traits
167 typedef typename bucket_type::key_type key_type; ///< key type
168 typedef typename bucket_type::mapped_type mapped_type; ///< value type
169 typedef typename bucket_type::value_type value_type; ///< key/value pair stored in the map
171 typedef typename bucket_type::key_comparator key_comparator; ///< key compare functor
173 /// Hash functor for \ref key_type and all its derivatives that you use
174 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
175 typedef typename traits::item_counter item_counter; ///< Item counter type
177 /// Bucket table allocator
178 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
179 typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
182 item_counter m_ItemCounter; ///< Item counter
183 hash m_HashFunctor; ///< Hash functor
184 bucket_type * m_Buckets; ///< bucket table
188 const size_t m_nHashBitmask;
193 /// Calculates hash value of \p key
194 template <typename Q>
195 size_t hash_value( Q const& key ) const
197 return m_HashFunctor( key ) & m_nHashBitmask;
200 /// Returns the bucket (ordered list) for \p key
201 template <typename Q>
202 bucket_type& bucket( Q const& key )
204 return m_Buckets[ hash_value( key ) ];
211 template <bool IsConst>
212 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
214 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
215 friend class MichaelHashMap;
218 typedef typename base_class::bucket_ptr bucket_ptr;
219 typedef typename base_class::list_iterator list_iterator;
222 /// Value pointer type (const for const_iterator)
223 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
224 /// Value reference type (const for const_iterator)
225 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
227 /// Key-value pair pointer type (const for const_iterator)
228 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
229 /// Key-value pair reference type (const for const_iterator)
230 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
233 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
234 : base_class( it, pFirst, pLast )
244 iterator_type( const iterator_type& src )
248 /// Dereference operator
249 pair_ptr operator ->() const
251 assert( base_class::m_pCurBucket != nullptr );
252 return base_class::m_itList.operator ->();
255 /// Dereference operator
256 pair_ref operator *() const
258 assert( base_class::m_pCurBucket != nullptr );
259 return base_class::m_itList.operator *();
263 iterator_type& operator ++()
265 base_class::operator++();
269 /// Assignment operator
270 iterator_type& operator = (const iterator_type& src)
272 base_class::operator =(src);
276 /// Returns current bucket (debug function)
277 bucket_ptr bucket() const
279 return base_class::bucket();
282 /// Equality operator
284 bool operator ==(iterator_type<C> const& i )
286 return base_class::operator ==( i );
288 /// Equality operator
290 bool operator !=(iterator_type<C> const& i )
292 return !( *this == i );
299 typedef iterator_type< false > iterator;
301 /// Const forward iterator
302 typedef iterator_type< true > const_iterator;
304 /// Returns a forward iterator addressing the first element in a map
306 For empty map \code begin() == end() \endcode
310 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
313 /// Returns an iterator that addresses the location succeeding the last element in a map
315 Do not use the value returned by <tt>end</tt> function to access any item.
316 The returned value can be used only to control reaching the end of the map.
317 For empty map \code begin() == end() \endcode
321 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
324 /// Returns a forward const iterator addressing the first element in a map
326 const_iterator begin() const
328 return get_const_begin();
330 const_iterator cbegin() const
332 return get_const_begin();
336 /// Returns an const iterator that addresses the location succeeding the last element in a map
338 const_iterator end() const
340 return get_const_end();
342 const_iterator cend() const
344 return get_const_end();
350 const_iterator get_const_begin() const
352 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
354 const_iterator get_const_end() const
356 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
361 /// Initializes the map
362 /** @anchor cds_nonintrusive_MichaelHashMap_hp_ctor
363 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
364 when you create an object.
365 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
366 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
367 Note, that many popular STL hash map implementation uses load factor 1.
369 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
372 size_t nMaxItemCount, ///< estimation of max item count in the hash map
373 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
374 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
376 // GC and OrderedList::gc must be the same
377 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
379 // atomicity::empty_item_counter is not allowed as a item counter
380 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
381 "atomicity::empty_item_counter is not allowed as a item counter");
383 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
386 /// Clears hash map and destroys it
390 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
393 /// Inserts new node with key and default value
395 The function creates a node with \p key and default value, and then inserts the node created into the map.
398 - The \p key_type should be constructible from value of type \p K.
399 In trivial case, \p K is equal to \p key_type.
400 - The \p mapped_type should be default-constructible.
402 Returns \p true if inserting successful, \p false otherwise.
404 template <typename K>
405 bool insert( const K& key )
407 const bool bRet = bucket( key ).insert( key );
415 The function creates a node with copy of \p val value
416 and then inserts the node created into the map.
419 - The \p key_type should be constructible from \p key of type \p K.
420 - The \p mapped_type should be constructible from \p val of type \p V.
422 Returns \p true if \p val is inserted into the map, \p false otherwise.
424 template <typename K, typename V>
425 bool insert( K const& key, V const& val )
427 const bool bRet = bucket( key ).insert( key, val );
433 /// Inserts new node and initialize it by a functor
435 This function inserts new node with key \p key and if inserting is successful then it calls
436 \p func functor with signature
439 void operator()( value_type& item );
443 The argument \p item of user-defined functor \p func is the reference
444 to the map's item inserted:
445 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
446 - <tt>item.second</tt> is a reference to item's value that may be changed.
448 The user-defined functor is called only if inserting is successful.
450 The \p key_type should be constructible from value of type \p K.
452 The function allows to split creating of new item into two part:
453 - create item from \p key;
454 - insert new item into the map;
455 - if inserting is successful, initialize the value of item by calling \p func functor
457 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
458 it is preferable that the initialization should be completed only if inserting is successful.
460 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
461 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
464 template <typename K, typename Func>
465 bool insert_key( const K& key, Func func )
467 const bool bRet = bucket( key ).insert_key( key, func );
474 /// Ensures that the \p key exists in the map
476 The operation performs inserting or changing data with lock-free manner.
478 If the \p key not found in the map, then the new item created from \p key
479 is inserted into the map (note that in this case the \p key_type should be
480 constructible from type \p K).
481 Otherwise, the functor \p func is called with item found.
482 The functor \p Func may signature is:
485 void operator()( bool bNew, value_type& item );
490 - \p bNew - \p true if the item has been inserted, \p false otherwise
491 - \p item - item of the list
493 The functor may change any fields of the \p item.second that is \p mapped_type.
495 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
496 \p second is true if new item has been added or \p false if the item with \p key
497 already is in the list.
499 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
500 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
503 template <typename K, typename Func>
504 std::pair<bool, bool> ensure( K const& key, Func func )
506 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
507 if ( bRet.first && bRet.second )
512 /// For key \p key inserts data of type \p mapped_type created from \p args
514 \p key_type should be constructible from type \p K
516 Returns \p true if inserting successful, \p false otherwise.
518 template <typename K, typename... Args>
519 bool emplace( K&& key, Args&&... args )
521 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
527 /// Deletes \p key from the map
528 /** \anchor cds_nonintrusive_MichaelMap_erase_val
530 Return \p true if \p key is found and deleted, \p false otherwise
532 template <typename K>
533 bool erase( K const& key )
535 const bool bRet = bucket( key ).erase( key );
541 /// Deletes the item from the map using \p pred predicate for searching
543 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
544 but \p pred is used for key comparing.
545 \p Less functor has the interface like \p std::less.
546 \p Less must imply the same element order as the comparator used for building the map.
548 template <typename K, typename Less>
549 bool erase_with( K const& key, Less pred )
551 const bool bRet = bucket( key ).erase_with( key, pred );
557 /// Deletes \p key from the map
558 /** \anchor cds_nonintrusive_MichaelMap_erase_func
560 The function searches an item with key \p key, calls \p f functor
561 and deletes the item. If \p key is not found, the functor is not called.
563 The functor \p Func interface:
566 void operator()(value_type& item) { ... }
570 Return \p true if key is found and deleted, \p false otherwise
572 template <typename K, typename Func>
573 bool erase( K const& key, Func f )
575 const bool bRet = bucket( key ).erase( key, f );
581 /// Deletes the item from the map using \p pred predicate for searching
583 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
584 but \p pred is used for key comparing.
585 \p Less functor has the interface like \p std::less.
586 \p Less must imply the same element order as the comparator used for building the map.
588 template <typename K, typename Less, typename Func>
589 bool erase_with( K const& key, Less pred, Func f )
591 const bool bRet = bucket( key ).erase_with( key, pred, f );
597 /// Extracts the item with specified \p key
598 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
599 The function searches an item with key equal to \p key,
600 unlinks it from the set, and returns it as \p guarded_ptr.
601 If \p key is not found the function returns an empty guarded pointer.
603 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
605 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
606 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
610 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
614 michael_map::guarded_ptr gp( theMap.extract( 5 ));
619 // Destructor of gp releases internal HP guard
623 template <typename K>
624 guarded_ptr extract( K const& key )
626 guarded_ptr gp( bucket( key ).extract( key ));
632 /// Extracts the item using compare functor \p pred
634 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
635 but \p pred predicate is used for key comparing.
637 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
639 \p pred must imply the same element order as the comparator used for building the map.
641 template <typename K, typename Less>
642 guarded_ptr extract_with( K const& key, Less pred )
644 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
650 /// Finds the key \p key
651 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
653 The function searches the item with key equal to \p key and calls the functor \p f for item found.
654 The interface of \p Func functor is:
657 void operator()( value_type& item );
660 where \p item is the item found.
662 The functor may change \p item.second. Note that the functor is only guarantee
663 that \p item cannot be disposed during functor is executing.
664 The functor does not serialize simultaneous access to the map's \p item. If such access is
665 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
667 The function returns \p true if \p key is found, \p false otherwise.
669 template <typename K, typename Func>
670 bool find( K const& key, Func f )
672 return bucket( key ).find( key, f );
675 /// Finds the key \p val using \p pred predicate for searching
677 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
678 but \p pred is used for key comparing.
679 \p Less functor has the interface like \p std::less.
680 \p Less must imply the same element order as the comparator used for building the map.
682 template <typename K, typename Less, typename Func>
683 bool find_with( K const& key, Less pred, Func f )
685 return bucket( key ).find_with( key, pred, f );
688 /// Finds the key \p key
689 /** \anchor cds_nonintrusive_MichaelMap_find_val
690 The function searches the item with key equal to \p key
691 and returns \p true if it is found, and \p false otherwise.
693 template <typename K>
694 bool find( K const& key )
696 return bucket( key ).find( key );
699 /// Finds the key \p val using \p pred predicate for searching
701 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_val "find(K const&)"
702 but \p pred is used for key comparing.
703 \p Less functor has the interface like \p std::less.
704 \p Less must imply the same element order as the comparator used for building the map.
706 template <typename K, typename Less>
707 bool find_with( K const& key, Less pred )
709 return bucket( key ).find_with( key, pred );
712 /// Finds \p key and return the item found
713 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
714 The function searches the item with key equal to \p key
715 and returns the guarded pointer to the item found.
716 If \p key is not found the function returns an empty guarded pointer,
718 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
722 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
726 michael_map::guarded_ptr gp( theMap.get( 5 ));
731 // Destructor of guarded_ptr releases internal HP guard
735 Note the compare functor specified for \p OrderedList template parameter
736 should accept a parameter of type \p K that can be not the same as \p key_type.
738 template <typename K>
739 guarded_ptr get( K const& key )
741 return bucket( key ).get( key );
744 /// Finds \p key and return the item found
746 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
747 but \p pred is used for comparing the keys.
749 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
751 \p pred must imply the same element order as the comparator used for building the map.
753 template <typename K, typename Less>
754 guarded_ptr get_with( K const& key, Less pred )
756 return bucket( key ).get_with( key, pred );
759 /// Clears the map (not atomic)
762 for ( size_t i = 0; i < bucket_count(); ++i )
763 m_Buckets[i].clear();
764 m_ItemCounter.reset();
767 /// Checks if the map is empty
769 Emptiness is checked by item counting: if item count is zero then the map is empty.
770 Thus, the correct item counting is an important part of the map implementation.
777 /// Returns item count in the map
780 return m_ItemCounter;
783 /// Returns the size of hash table
785 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
786 the value returned is an constant depending on object initialization parameters;
787 see \p MichaelHashMap::MichaelHashMap for explanation.
789 size_t bucket_count() const
791 return m_nHashBitmask + 1;
794 }} // namespace cds::container
796 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_H