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 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_with( const K& key, Func func )
467 const bool bRet = bucket( key ).insert_with( key, func );
473 /// Updates data by \p key
475 The operation performs inserting or replacing the element with lock-free manner.
477 If the \p key not found in the map, then the new item created from \p key
478 will be inserted into the map iff \p bAllowInsert is \p true.
479 (note that in this case the \ref key_type should be constructible from type \p K).
480 Otherwise, if \p key is found, the functor \p func is called with item found.
482 The functor \p Func signature is:
485 void operator()( bool bNew, value_type& item );
489 - \p bNew - \p true if the item has been inserted, \p false otherwise
490 - \p item - the item found or inserted
492 The functor may change any fields of the \p item.second that is \p mapped_type.
494 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
495 \p second is true if new item has been added or \p false if the item with \p key
498 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
499 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
502 template <typename K, typename Func >
503 std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
505 std::pair<bool, bool> bRet = bucket( key ).update( key, func, bAllowInsert );
506 if ( bRet.first && bRet.second )
511 template <typename K, typename Func>
512 CDS_DEPRECATED("ensure() is deprecated, use update()")
513 std::pair<bool, bool> ensure( K const& key, Func func )
515 std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
516 if ( bRet.first && bRet.second )
522 /// For key \p key inserts data of type \p mapped_type created from \p args
524 \p key_type should be constructible from type \p K
526 Returns \p true if inserting successful, \p false otherwise.
528 template <typename K, typename... Args>
529 bool emplace( K&& key, Args&&... args )
531 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
537 /// Deletes \p key from the map
538 /** \anchor cds_nonintrusive_MichaelMap_erase_val
540 Return \p true if \p key is found and deleted, \p false otherwise
542 template <typename K>
543 bool erase( K const& key )
545 const bool bRet = bucket( key ).erase( key );
551 /// Deletes the item from the map using \p pred predicate for searching
553 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
554 but \p pred is used for key comparing.
555 \p Less functor has the interface like \p std::less.
556 \p Less must imply the same element order as the comparator used for building the map.
558 template <typename K, typename Less>
559 bool erase_with( K const& key, Less pred )
561 const bool bRet = bucket( key ).erase_with( key, pred );
567 /// Deletes \p key from the map
568 /** \anchor cds_nonintrusive_MichaelMap_erase_func
570 The function searches an item with key \p key, calls \p f functor
571 and deletes the item. If \p key is not found, the functor is not called.
573 The functor \p Func interface:
576 void operator()(value_type& item) { ... }
580 Return \p true if key is found and deleted, \p false otherwise
582 template <typename K, typename Func>
583 bool erase( K const& key, Func f )
585 const bool bRet = bucket( key ).erase( key, f );
591 /// Deletes the item from the map using \p pred predicate for searching
593 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
594 but \p pred is used for key comparing.
595 \p Less functor has the interface like \p std::less.
596 \p Less must imply the same element order as the comparator used for building the map.
598 template <typename K, typename Less, typename Func>
599 bool erase_with( K const& key, Less pred, Func f )
601 const bool bRet = bucket( key ).erase_with( key, pred, f );
607 /// Extracts the item with specified \p key
608 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
609 The function searches an item with key equal to \p key,
610 unlinks it from the set, and returns it as \p guarded_ptr.
611 If \p key is not found the function returns an empty guarded pointer.
613 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
615 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
616 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
620 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
624 michael_map::guarded_ptr gp( theMap.extract( 5 ));
629 // Destructor of gp releases internal HP guard
633 template <typename K>
634 guarded_ptr extract( K const& key )
636 guarded_ptr gp( bucket( key ).extract( key ));
642 /// Extracts the item using compare functor \p pred
644 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
645 but \p pred predicate is used for key comparing.
647 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
649 \p pred must imply the same element order as the comparator used for building the map.
651 template <typename K, typename Less>
652 guarded_ptr extract_with( K const& key, Less pred )
654 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
660 /// Finds the key \p key
661 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
663 The function searches the item with key equal to \p key and calls the functor \p f for item found.
664 The interface of \p Func functor is:
667 void operator()( value_type& item );
670 where \p item is the item found.
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 /// Checks whether the map contains \p key
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 contains( K const& key )
706 return bucket( key ).contains( key );
709 template <typename K>
710 CDS_DEPRECATED("deprecated, use contains()")
711 bool find( K const& key )
713 return bucket( key ).contains( key );
717 /// Checks whether the map contains \p key using \p pred predicate for searching
719 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
720 \p Less functor has the interface like \p std::less.
721 \p Less must imply the same element order as the comparator used for building the map.
723 template <typename K, typename Less>
724 bool contains( K const& key, Less pred )
726 return bucket( key ).contains( key, pred );
729 template <typename K, typename Less>
730 CDS_DEPRECATED("deprecated, use contains()")
731 bool find_with( K const& key, Less pred )
733 return bucket( key ).contains( key, pred );
737 /// Finds \p key and return the item found
738 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
739 The function searches the item with key equal to \p key
740 and returns the guarded pointer to the item found.
741 If \p key is not found the function returns an empty guarded pointer,
743 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
747 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
751 michael_map::guarded_ptr gp( theMap.get( 5 ));
756 // Destructor of guarded_ptr releases internal HP guard
760 Note the compare functor specified for \p OrderedList template parameter
761 should accept a parameter of type \p K that can be not the same as \p key_type.
763 template <typename K>
764 guarded_ptr get( K const& key )
766 return bucket( key ).get( key );
769 /// Finds \p key and return the item found
771 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
772 but \p pred is used for comparing the keys.
774 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
776 \p pred must imply the same element order as the comparator used for building the map.
778 template <typename K, typename Less>
779 guarded_ptr get_with( K const& key, Less pred )
781 return bucket( key ).get_with( key, pred );
784 /// Clears the map (not atomic)
787 for ( size_t i = 0; i < bucket_count(); ++i )
788 m_Buckets[i].clear();
789 m_ItemCounter.reset();
792 /// Checks if the map is empty
794 Emptiness is checked by item counting: if item count is zero then the map is empty.
795 Thus, the correct item counting is an important part of the map implementation.
802 /// Returns item count in the map
805 return m_ItemCounter;
808 /// Returns the size of hash table
810 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
811 the value returned is an constant depending on object initialization parameters;
812 see \p MichaelHashMap::MichaelHashMap for explanation.
814 size_t bucket_count() const
816 return m_nHashBitmask + 1;
819 }} // namespace cds::container
821 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H