3 #ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H
4 #define CDSLIB_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 typedef cds::container::michael_map::implementation_tag implementation_tag;
186 item_counter m_ItemCounter; ///< Item counter
187 hash m_HashFunctor; ///< Hash functor
188 bucket_type * m_Buckets; ///< bucket table
192 const size_t m_nHashBitmask;
197 /// Calculates hash value of \p key
198 template <typename Q>
199 size_t hash_value( Q const& key ) const
201 return m_HashFunctor( key ) & m_nHashBitmask;
204 /// Returns the bucket (ordered list) for \p key
205 template <typename Q>
206 bucket_type& bucket( Q const& key )
208 return m_Buckets[ hash_value( key ) ];
215 template <bool IsConst>
216 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
218 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
219 friend class MichaelHashMap;
222 typedef typename base_class::bucket_ptr bucket_ptr;
223 typedef typename base_class::list_iterator list_iterator;
226 /// Value pointer type (const for const_iterator)
227 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
228 /// Value reference type (const for const_iterator)
229 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
231 /// Key-value pair pointer type (const for const_iterator)
232 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
233 /// Key-value pair reference type (const for const_iterator)
234 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
237 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
238 : base_class( it, pFirst, pLast )
248 iterator_type( const iterator_type& src )
252 /// Dereference operator
253 pair_ptr operator ->() const
255 assert( base_class::m_pCurBucket != nullptr );
256 return base_class::m_itList.operator ->();
259 /// Dereference operator
260 pair_ref operator *() const
262 assert( base_class::m_pCurBucket != nullptr );
263 return base_class::m_itList.operator *();
267 iterator_type& operator ++()
269 base_class::operator++();
273 /// Assignment operator
274 iterator_type& operator = (const iterator_type& src)
276 base_class::operator =(src);
280 /// Returns current bucket (debug function)
281 bucket_ptr bucket() const
283 return base_class::bucket();
286 /// Equality operator
288 bool operator ==(iterator_type<C> const& i )
290 return base_class::operator ==( i );
292 /// Equality operator
294 bool operator !=(iterator_type<C> const& i )
296 return !( *this == i );
303 typedef iterator_type< false > iterator;
305 /// Const forward iterator
306 typedef iterator_type< true > const_iterator;
308 /// Returns a forward iterator addressing the first element in a map
310 For empty map \code begin() == end() \endcode
314 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
317 /// Returns an iterator that addresses the location succeeding the last element in a map
319 Do not use the value returned by <tt>end</tt> function to access any item.
320 The returned value can be used only to control reaching the end of the map.
321 For empty map \code begin() == end() \endcode
325 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
328 /// Returns a forward const iterator addressing the first element in a map
330 const_iterator begin() const
332 return get_const_begin();
334 const_iterator cbegin() const
336 return get_const_begin();
340 /// Returns an const iterator that addresses the location succeeding the last element in a map
342 const_iterator end() const
344 return get_const_end();
346 const_iterator cend() const
348 return get_const_end();
354 const_iterator get_const_begin() const
356 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
358 const_iterator get_const_end() const
360 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
365 /// Initializes the map
366 /** @anchor cds_nonintrusive_MichaelHashMap_hp_ctor
367 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
368 when you create an object.
369 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
370 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
371 Note, that many popular STL hash map implementation uses load factor 1.
373 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
376 size_t nMaxItemCount, ///< estimation of max item count in the hash map
377 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
378 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
380 // GC and OrderedList::gc must be the same
381 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
383 // atomicity::empty_item_counter is not allowed as a item counter
384 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
385 "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 The user-defined functor is called only if inserting is successful.
454 The \p key_type should be constructible from value of type \p K.
456 The function allows to split creating of new item into two part:
457 - create item from \p key;
458 - insert new item into the map;
459 - if inserting is successful, initialize the value of item by calling \p func functor
461 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
462 it is preferable that the initialization should be completed only if inserting is successful.
464 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
465 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
468 template <typename K, typename Func>
469 bool insert_with( const K& key, Func func )
471 const bool bRet = bucket( key ).insert_with( key, func );
478 /// Ensures that the \p key exists in the map
480 The operation performs inserting or changing data with lock-free manner.
482 If the \p key not found in the map, then the new item created from \p key
483 is inserted into the map (note that in this case the \p key_type should be
484 constructible from type \p K).
485 Otherwise, the functor \p func is called with item found.
486 The functor \p Func may signature is:
489 void operator()( bool bNew, value_type& item );
494 - \p bNew - \p true if the item has been inserted, \p false otherwise
495 - \p item - item of the list
497 The functor may change any fields of the \p item.second that is \p mapped_type.
499 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
500 \p second is true if new item has been added or \p false if the item with \p key
501 already is in the list.
503 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
504 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
507 template <typename K, typename Func>
508 std::pair<bool, bool> ensure( K const& key, Func func )
510 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
511 if ( bRet.first && bRet.second )
516 /// For key \p key inserts data of type \p mapped_type created from \p args
518 \p key_type should be constructible from type \p K
520 Returns \p true if inserting successful, \p false otherwise.
522 template <typename K, typename... Args>
523 bool emplace( K&& key, Args&&... args )
525 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
531 /// Deletes \p key from the map
532 /** \anchor cds_nonintrusive_MichaelMap_erase_val
534 Return \p true if \p key is found and deleted, \p false otherwise
536 template <typename K>
537 bool erase( K const& key )
539 const bool bRet = bucket( key ).erase( key );
545 /// Deletes the item from the map using \p pred predicate for searching
547 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
548 but \p pred is used for key comparing.
549 \p Less functor has the interface like \p std::less.
550 \p Less must imply the same element order as the comparator used for building the map.
552 template <typename K, typename Less>
553 bool erase_with( K const& key, Less pred )
555 const bool bRet = bucket( key ).erase_with( key, pred );
561 /// Deletes \p key from the map
562 /** \anchor cds_nonintrusive_MichaelMap_erase_func
564 The function searches an item with key \p key, calls \p f functor
565 and deletes the item. If \p key is not found, the functor is not called.
567 The functor \p Func interface:
570 void operator()(value_type& item) { ... }
574 Return \p true if key is found and deleted, \p false otherwise
576 template <typename K, typename Func>
577 bool erase( K const& key, Func f )
579 const bool bRet = bucket( key ).erase( key, f );
585 /// Deletes the item from the map using \p pred predicate for searching
587 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
588 but \p pred is used for key comparing.
589 \p Less functor has the interface like \p std::less.
590 \p Less must imply the same element order as the comparator used for building the map.
592 template <typename K, typename Less, typename Func>
593 bool erase_with( K const& key, Less pred, Func f )
595 const bool bRet = bucket( key ).erase_with( key, pred, f );
601 /// Extracts the item with specified \p key
602 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
603 The function searches an item with key equal to \p key,
604 unlinks it from the set, and returns it as \p guarded_ptr.
605 If \p key is not found the function returns an empty guarded pointer.
607 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
609 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
610 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
614 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
618 michael_map::guarded_ptr gp( theMap.extract( 5 ));
623 // Destructor of gp releases internal HP guard
627 template <typename K>
628 guarded_ptr extract( K const& key )
630 guarded_ptr gp( bucket( key ).extract( key ));
636 /// Extracts the item using compare functor \p pred
638 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
639 but \p pred predicate is used for key comparing.
641 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
643 \p pred must imply the same element order as the comparator used for building the map.
645 template <typename K, typename Less>
646 guarded_ptr extract_with( K const& key, Less pred )
648 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
654 /// Finds the key \p key
655 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
657 The function searches the item with key equal to \p key and calls the functor \p f for item found.
658 The interface of \p Func functor is:
661 void operator()( value_type& item );
664 where \p item is the item found.
666 The functor may change \p item.second. Note that the functor is only guarantee
667 that \p item cannot be disposed during functor is executing.
668 The functor does not serialize simultaneous access to the map's \p item. If such access is
669 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
671 The function returns \p true if \p key is found, \p false otherwise.
673 template <typename K, typename Func>
674 bool find( K const& key, Func f )
676 return bucket( key ).find( key, f );
679 /// Finds the key \p val using \p pred predicate for searching
681 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
682 but \p pred is used for key comparing.
683 \p Less functor has the interface like \p std::less.
684 \p Less must imply the same element order as the comparator used for building the map.
686 template <typename K, typename Less, typename Func>
687 bool find_with( K const& key, Less pred, Func f )
689 return bucket( key ).find_with( key, pred, f );
692 /// Finds the key \p key
693 /** \anchor cds_nonintrusive_MichaelMap_find_val
694 The function searches the item with key equal to \p key
695 and returns \p true if it is found, and \p false otherwise.
697 template <typename K>
698 bool find( K const& key )
700 return bucket( key ).find( key );
703 /// Finds the key \p val using \p pred predicate for searching
705 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_val "find(K const&)"
706 but \p pred is used for key comparing.
707 \p Less functor has the interface like \p std::less.
708 \p Less must imply the same element order as the comparator used for building the map.
710 template <typename K, typename Less>
711 bool find_with( K const& key, Less pred )
713 return bucket( key ).find_with( key, pred );
716 /// Finds \p key and return the item found
717 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
718 The function searches the item with key equal to \p key
719 and returns the guarded pointer to the item found.
720 If \p key is not found the function returns an empty guarded pointer,
722 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
726 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
730 michael_map::guarded_ptr gp( theMap.get( 5 ));
735 // Destructor of guarded_ptr releases internal HP guard
739 Note the compare functor specified for \p OrderedList template parameter
740 should accept a parameter of type \p K that can be not the same as \p key_type.
742 template <typename K>
743 guarded_ptr get( K const& key )
745 return bucket( key ).get( key );
748 /// Finds \p key and return the item found
750 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
751 but \p pred is used for comparing the keys.
753 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
755 \p pred must imply the same element order as the comparator used for building the map.
757 template <typename K, typename Less>
758 guarded_ptr get_with( K const& key, Less pred )
760 return bucket( key ).get_with( key, pred );
763 /// Clears the map (not atomic)
766 for ( size_t i = 0; i < bucket_count(); ++i )
767 m_Buckets[i].clear();
768 m_ItemCounter.reset();
771 /// Checks if the map is empty
773 Emptiness is checked by item counting: if item count is zero then the map is empty.
774 Thus, the correct item counting is an important part of the map implementation.
781 /// Returns item count in the map
784 return m_ItemCounter;
787 /// Returns the size of hash table
789 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
790 the value returned is an constant depending on object initialization parameters;
791 see \p MichaelHashMap::MichaelHashMap for explanation.
793 size_t bucket_count() const
795 return m_nHashBitmask + 1;
798 }} // namespace cds::container
800 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H