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 );
477 /// Updates data by \p key
479 The operation performs inserting or replacing the element with lock-free manner.
481 If the \p key not found in the map, then the new item created from \p key
482 will be inserted into the map iff \p bAllowInsert is \p true.
483 (note that in this case the \ref key_type should be constructible from type \p K).
484 Otherwise, if \p key is found, the functor \p func is called with item found.
486 The functor \p Func signature is:
489 void operator()( bool bNew, value_type& item );
493 - \p bNew - \p true if the item has been inserted, \p false otherwise
494 - \p item - the item found or inserted
496 The functor may change any fields of the \p item.second that is \p mapped_type.
498 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
499 \p second is true if new item has been added or \p false if the item with \p key
502 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
503 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
506 template <typename K, typename Func >
507 std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
509 std::pair<bool, bool> bRet = bucket( key ).update( key, func, bAllowInsert );
510 if ( bRet.first && bRet.second )
516 template <typename K, typename Func>
517 std::pair<bool, bool> ensure( K const& key, Func func )
519 std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
520 if ( bRet.first && bRet.second )
526 /// For key \p key inserts data of type \p mapped_type created from \p args
528 \p key_type should be constructible from type \p K
530 Returns \p true if inserting successful, \p false otherwise.
532 template <typename K, typename... Args>
533 bool emplace( K&& key, Args&&... args )
535 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
541 /// Deletes \p key from the map
542 /** \anchor cds_nonintrusive_MichaelMap_erase_val
544 Return \p true if \p key is found and deleted, \p false otherwise
546 template <typename K>
547 bool erase( K const& key )
549 const bool bRet = bucket( key ).erase( key );
555 /// Deletes the item from the map using \p pred predicate for searching
557 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
558 but \p pred is used for key comparing.
559 \p Less functor has the interface like \p std::less.
560 \p Less must imply the same element order as the comparator used for building the map.
562 template <typename K, typename Less>
563 bool erase_with( K const& key, Less pred )
565 const bool bRet = bucket( key ).erase_with( key, pred );
571 /// Deletes \p key from the map
572 /** \anchor cds_nonintrusive_MichaelMap_erase_func
574 The function searches an item with key \p key, calls \p f functor
575 and deletes the item. If \p key is not found, the functor is not called.
577 The functor \p Func interface:
580 void operator()(value_type& item) { ... }
584 Return \p true if key is found and deleted, \p false otherwise
586 template <typename K, typename Func>
587 bool erase( K const& key, Func f )
589 const bool bRet = bucket( key ).erase( key, f );
595 /// Deletes the item from the map using \p pred predicate for searching
597 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
598 but \p pred is used for key comparing.
599 \p Less functor has the interface like \p std::less.
600 \p Less must imply the same element order as the comparator used for building the map.
602 template <typename K, typename Less, typename Func>
603 bool erase_with( K const& key, Less pred, Func f )
605 const bool bRet = bucket( key ).erase_with( key, pred, f );
611 /// Extracts the item with specified \p key
612 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
613 The function searches an item with key equal to \p key,
614 unlinks it from the set, and returns it as \p guarded_ptr.
615 If \p key is not found the function returns an empty guarded pointer.
617 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
619 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
620 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
624 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
628 michael_map::guarded_ptr gp( theMap.extract( 5 ));
633 // Destructor of gp releases internal HP guard
637 template <typename K>
638 guarded_ptr extract( K const& key )
640 guarded_ptr gp( bucket( key ).extract( key ));
646 /// Extracts the item using compare functor \p pred
648 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
649 but \p pred predicate is used for key comparing.
651 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
653 \p pred must imply the same element order as the comparator used for building the map.
655 template <typename K, typename Less>
656 guarded_ptr extract_with( K const& key, Less pred )
658 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
664 /// Finds the key \p key
665 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
667 The function searches the item with key equal to \p key and calls the functor \p f for item found.
668 The interface of \p Func functor is:
671 void operator()( value_type& item );
674 where \p item is the item found.
676 The functor may change \p item.second. Note that the functor is only guarantee
677 that \p item cannot be disposed during functor is executing.
678 The functor does not serialize simultaneous access to the map's \p item. If such access is
679 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
681 The function returns \p true if \p key is found, \p false otherwise.
683 template <typename K, typename Func>
684 bool find( K const& key, Func f )
686 return bucket( key ).find( key, f );
689 /// Finds the key \p val using \p pred predicate for searching
691 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
692 but \p pred is used for key comparing.
693 \p Less functor has the interface like \p std::less.
694 \p Less must imply the same element order as the comparator used for building the map.
696 template <typename K, typename Less, typename Func>
697 bool find_with( K const& key, Less pred, Func f )
699 return bucket( key ).find_with( key, pred, f );
702 /// Checks whether the map contains \p key
704 The function searches the item with key equal to \p key
705 and returns \p true if it is found, and \p false otherwise.
707 template <typename K>
708 bool contains( K const& key )
710 return bucket( key ).contains( key );
714 template <typename K>
715 bool find( K const& key )
717 return bucket( key ).contains( key );
721 /// Checks whether the map contains \p key using \p pred predicate for searching
723 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
724 \p Less functor has the interface like \p std::less.
725 \p Less must imply the same element order as the comparator used for building the map.
727 template <typename K, typename Less>
728 bool contains( K const& key, Less pred )
730 return bucket( key ).contains( key, pred );
734 template <typename K, typename Less>
735 bool find_with( K const& key, Less pred )
737 return bucket( key ).contains( key, pred );
741 /// Finds \p key and return the item found
742 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
743 The function searches the item with key equal to \p key
744 and returns the guarded pointer to the item found.
745 If \p key is not found the function returns an empty guarded pointer,
747 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
751 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
755 michael_map::guarded_ptr gp( theMap.get( 5 ));
760 // Destructor of guarded_ptr releases internal HP guard
764 Note the compare functor specified for \p OrderedList template parameter
765 should accept a parameter of type \p K that can be not the same as \p key_type.
767 template <typename K>
768 guarded_ptr get( K const& key )
770 return bucket( key ).get( key );
773 /// Finds \p key and return the item found
775 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
776 but \p pred is used for comparing the keys.
778 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
780 \p pred must imply the same element order as the comparator used for building the map.
782 template <typename K, typename Less>
783 guarded_ptr get_with( K const& key, Less pred )
785 return bucket( key ).get_with( key, pred );
788 /// Clears the map (not atomic)
791 for ( size_t i = 0; i < bucket_count(); ++i )
792 m_Buckets[i].clear();
793 m_ItemCounter.reset();
796 /// Checks if the map is empty
798 Emptiness is checked by item counting: if item count is zero then the map is empty.
799 Thus, the correct item counting is an important part of the map implementation.
806 /// Returns item count in the map
809 return m_ItemCounter;
812 /// Returns the size of hash table
814 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
815 the value returned is an constant depending on object initialization parameters;
816 see \p MichaelHashMap::MichaelHashMap for explanation.
818 size_t bucket_count() const
820 return m_nHashBitmask + 1;
823 }} // namespace cds::container
825 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H