2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H
32 #define CDSLIB_CONTAINER_MICHAEL_MAP_H
34 #include <cds/container/details/michael_map_base.h>
35 #include <cds/container/details/iterable_list_base.h>
36 #include <cds/details/allocator.h>
38 namespace cds { namespace container {
40 /// Michael's hash map
41 /** @ingroup cds_nonintrusive_map
42 \anchor cds_nonintrusive_MichaelHashMap_hp
45 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
47 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
48 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
49 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
50 However, each bucket may contain unbounded number of items.
52 Template parameters are:
53 - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
54 from the \p libcds library.
55 Note the \p GC must be the same as the GC used for \p OrderedList
56 - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, \p MichaelKVList,
57 \p LazyKVList, \p IterableKVList. The ordered list implementation specifies the \p Key and \p Value types
58 stored in the hash-map, the reclamation schema \p GC used by hash-map, the comparison functor for the type \p Key
59 and other features specific for the ordered list.
60 - \p Traits - map traits, default is \p michael_map::traits.
61 Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction.
63 Many of the class function take a key argument of type \p K that in general is not \p key_type.
64 \p key_type and an argument of template type \p K must meet the following requirements:
65 - \p key_type should be constructible from value of type \p K;
66 - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
67 <tt> hash( key_type(key) ) == hash( key ) </tt>
68 - values of type \p key_type and \p K should be comparable
70 There are the specializations:
71 - for \ref cds_urcu_desc "RCU" - declared in <tt>cds/container/michael_map_rcu.h</tt>,
72 see \ref cds_nonintrusive_MichaelHashMap_rcu "MichaelHashMap<RCU>".
73 - for \p cds::gc::nogc declared in <tt>cds/container/michael_map_nogc.h</tt>,
74 see \ref cds_nonintrusive_MichaelHashMap_nogc "MichaelHashMap<gc::nogc>".
76 \anchor cds_nonintrusive_MichaelHashMap_how_touse
79 Suppose, you want to make \p int to \p int map for Hazard Pointer garbage collector. You should
80 choose suitable ordered list class that will be used as a bucket for the map; it may be \p MichaelKVList.
82 #include <cds/container/michael_kvlist_hp.h> // MichaelKVList for gc::HP
83 #include <cds/container/michael_map.h> // MichaelHashMap
85 // List traits based on std::less predicate
86 struct list_traits: public cds::container::michael_list::traits
88 typedef std::less<int> less;
92 typedef cds::container::MichaelKVList< cds::gc::HP, int, int, list_traits> int2int_list;
95 struct map_traits: public cds::container::michael_map::traits
98 size_t operator()( int i ) const
100 return cds::opt::v::hash<int>()( i );
106 typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list, map_traits > int2int_map;
108 // Now you can use int2int_map class
114 theMap.insert( 100 );
119 You may use option-based declaration:
121 #include <cds/container/michael_kvlist_hp.h> // MichaelKVList for gc::HP
122 #include <cds/container/michael_map.h> // MichaelHashMap
125 typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
126 typename cds::container::michael_list::make_traits<
127 cds::container::opt::less< std::less<int> > // item comparator option
132 typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list,
133 cds::container::michael_map::make_traits<
134 cc::opt::hash< cds::opt::v::hash<int> >
142 #ifdef CDS_DOXYGEN_INVOKED
143 class Traits = michael_map::traits
151 typedef GC gc; ///< Garbage collector
152 typedef OrderedList ordered_list; ///< type of ordered list to be used as a bucket
153 typedef Traits traits; ///< Map traits
155 typedef typename ordered_list::key_type key_type; ///< key type
156 typedef typename ordered_list::mapped_type mapped_type; ///< value type
157 typedef typename ordered_list::value_type value_type; ///< key/value pair stored in the map
158 typedef typename traits::allocator allocator; ///< Bucket table allocator
160 typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
161 typedef typename ordered_list::stat stat; ///< Internal statistics
163 /// Hash functor for \ref key_type and all its derivatives that you use
164 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
165 typedef typename traits::item_counter item_counter; ///< Item counter type
167 // GC and OrderedList::gc must be the same
168 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
170 // atomicity::empty_item_counter is not allowed as a item counter
171 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
172 "atomicity::empty_item_counter is not allowed as a item counter");
174 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
176 #ifdef CDS_DOXYGEN_INVOKED
177 /// Wrapped internal statistics for \p ordered_list
178 typedef implementatin_specific bucket_stat;
180 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
183 #ifdef CDS_DOXYGEN_INVOKED
184 /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics
185 typedef modified_ordered_list internal_bucket_type;
187 typedef typename ordered_list::template rebind_traits<
188 cds::opt::item_counter< cds::atomicity::empty_item_counter >
189 , cds::opt::stat< typename bucket_stat::wrapped_stat >
190 >::type internal_bucket_type;
193 /// Guarded pointer - a result of \p get() and \p extract() functions
194 typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
197 /// Bucket table allocator
198 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
203 const size_t m_nHashBitmask;
204 internal_bucket_type * m_Buckets; ///< bucket table
205 item_counter m_ItemCounter; ///< Item counter
206 hash m_HashFunctor; ///< Hash functor
207 typename bucket_stat::stat m_Stat; ///< Internal statistics
213 template <bool IsConst>
214 class iterator_type: private cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
216 typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class;
217 friend class MichaelHashMap;
220 typedef typename base_class::bucket_ptr bucket_ptr;
221 typedef typename base_class::list_iterator list_iterator;
224 /// Value pointer type (const for const_iterator)
225 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
226 /// Value reference type (const for const_iterator)
227 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
229 /// Key-value pair pointer type (const for const_iterator)
230 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
231 /// Key-value pair reference type (const for const_iterator)
232 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
235 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
236 : base_class( it, pFirst, pLast )
246 iterator_type( const iterator_type& src )
250 /// Dereference operator
251 pair_ptr operator ->() const
253 assert( base_class::m_pCurBucket != nullptr );
254 return base_class::m_itList.operator ->();
257 /// Dereference operator
258 pair_ref operator *() const
260 assert( base_class::m_pCurBucket != nullptr );
261 return base_class::m_itList.operator *();
265 iterator_type& operator ++()
267 base_class::operator++();
271 /// Assignment operator
272 iterator_type& operator = (const iterator_type& src)
274 base_class::operator =(src);
278 /// Returns current bucket (debug function)
279 bucket_ptr bucket() const
281 return base_class::bucket();
284 /// Equality operator
286 bool operator ==(iterator_type<C> const& i )
288 return base_class::operator ==( i );
290 /// Equality operator
292 bool operator !=(iterator_type<C> const& i )
294 return !( *this == i );
300 ///@name Forward iterators (only for debugging purpose)
304 The forward iterator for Michael's map has some features:
305 - it has no post-increment operator
306 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
307 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
308 may be thrown if the limit of guard count per thread is exceeded.
309 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
311 Iterator thread safety depends on type of \p OrderedList:
312 - for \p MichaelKVList and \p LazyKVList: iterator guarantees safety even if you delete the item that iterator points to
313 because that item is guarded by hazard pointer.
314 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the map.
315 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
316 Use this iterator on the concurrent container for debugging purpose only.
317 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
319 The iterator interface:
323 // Default constructor
327 iterator( iterator const& src );
329 // Dereference operator
330 value_type * operator ->() const;
332 // Dereference operator
333 value_type& operator *() const;
335 // Preincrement operator
336 iterator& operator ++();
338 // Assignment operator
339 iterator& operator = (iterator const& src);
341 // Equality operators
342 bool operator ==(iterator const& i ) const;
343 bool operator !=(iterator const& i ) const;
347 @note The iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
349 typedef iterator_type< false > iterator;
351 /// Const forward iterator
352 typedef iterator_type< true > const_iterator;
354 /// Returns a forward iterator addressing the first element in a map
356 For empty map \code begin() == end() \endcode
360 return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end() );
363 /// Returns an iterator that addresses the location succeeding the last element in a map
365 Do not use the value returned by <tt>end</tt> function to access any item.
366 The returned value can be used only to control reaching the end of the map.
367 For empty map \code begin() == end() \endcode
371 return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end() );
374 /// Returns a forward const iterator addressing the first element in a map
375 const_iterator begin() const
377 return get_const_begin();
379 /// Returns a forward const iterator addressing the first element in a map
380 const_iterator cbegin() const
382 return get_const_begin();
385 /// Returns an const iterator that addresses the location succeeding the last element in a map
386 const_iterator end() const
388 return get_const_end();
390 /// Returns an const iterator that addresses the location succeeding the last element in a map
391 const_iterator cend() const
393 return get_const_end();
398 /// Initializes the map
399 /** @anchor cds_nonintrusive_MichaelHashMap_hp_ctor
400 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
401 when you create an object.
402 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
403 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
404 Note, that many popular STL hash map implementation uses load factor 1.
406 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
409 size_t nMaxItemCount, ///< estimation of max item count in the hash map
410 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
412 : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
413 , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
415 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
416 construct_bucket<bucket_stat>( it );
419 /// Clears hash map and destroys it
424 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
425 it->~internal_bucket_type();
426 bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
429 /// Inserts new node with key and default value
431 The function creates a node with \p key and default value, and then inserts the node created into the map.
434 - The \p key_type should be constructible from value of type \p K.
435 In trivial case, \p K is equal to \p key_type.
436 - The \p mapped_type should be default-constructible.
438 Returns \p true if inserting successful, \p false otherwise.
440 template <typename K>
441 bool insert( K&& key )
443 const bool bRet = bucket( key ).insert( std::forward<K>( key ));
451 The function creates a node with copy of \p val value
452 and then inserts the node created into the map.
455 - The \p key_type should be constructible from \p key of type \p K.
456 - The \p mapped_type should be constructible from \p val of type \p V.
458 Returns \p true if \p val is inserted into the map, \p false otherwise.
460 template <typename K, typename V>
461 bool insert( K&& key, V&& val )
463 const bool bRet = bucket( key ).insert( std::forward<K>( key ), std::forward<V>( val ));
469 /// Inserts new node and initialize it by a functor
471 This function inserts new node with key \p key and if inserting is successful then it calls
472 \p func functor with signature
475 void operator()( value_type& item );
479 The argument \p item of user-defined functor \p func is the reference
480 to the map's item inserted:
481 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
482 - <tt>item.second</tt> is a reference to item's value that may be changed.
484 The user-defined functor is called only if inserting is successful.
486 The \p key_type should be constructible from value of type \p K.
488 The function allows to split creating of new item into two part:
489 - create item from \p key;
490 - insert new item into the map;
491 - if inserting is successful, initialize the value of item by calling \p func functor
493 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
494 it is preferable that the initialization should be completed only if inserting is successful.
496 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
497 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
500 template <typename K, typename Func>
501 bool insert_with( K&& key, Func func )
503 const bool bRet = bucket( key ).insert_with( std::forward<K>( key ), func );
509 /// Updates data by \p key
511 The operation performs inserting or replacing the element with lock-free manner.
513 If the \p key not found in the map, then the new item created from \p key
514 will be inserted into the map iff \p bAllowInsert is \p true.
515 (note that in this case the \ref key_type should be constructible from type \p K).
516 Otherwise, if \p key is found, the functor \p func is called with item found.
518 The functor \p func signature depends of \p OrderedList:
520 <b>for \p MichaelKVList, \p LazyKVList</b>
523 void operator()( bool bNew, value_type& item );
527 - \p bNew - \p true if the item has been inserted, \p false otherwise
528 - \p item - the item found or inserted
530 The functor may change any fields of the \p item.second that is \p mapped_type.
532 <b>for \p IterableKVList</b>
534 void func( value_type& val, value_type * old );
537 - \p val - a new data constructed from \p key
538 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
540 The functor may change non-key fields of \p val; however, \p func must guarantee
541 that during changing no any other modifications could be made on this item by concurrent threads.
543 @return <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
544 \p second is true if new item has been added or \p false if the item with \p key
547 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
548 as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
549 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
552 template <typename K, typename Func >
553 std::pair<bool, bool> update( K&& key, Func func, bool bAllowInsert = true )
555 std::pair<bool, bool> bRet = bucket( key ).update( std::forward<K>( key ), func, bAllowInsert );
556 if ( bRet.first && bRet.second )
561 template <typename K, typename Func>
562 CDS_DEPRECATED("ensure() is deprecated, use update()")
563 std::pair<bool, bool> ensure( K const& key, Func func )
565 std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
566 if ( bRet.first && bRet.second )
572 /// Inserts or updates the node (only for \p IterableKVList)
574 The operation performs inserting or changing data with lock-free manner.
576 If the item \p val is not found in the map, then \p val is inserted iff \p bAllowInsert is \p true.
577 Otherwise, the current element is changed to \p val, the old element will be retired later.
579 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
580 \p second is \p true if \p val has been added or \p false if the item with that key
583 template <typename Q, typename V>
584 #ifdef CDS_DOXYGEN_INVOKED
585 std::pair<bool, bool>
587 typename std::enable_if<
588 std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
589 std::pair<bool, bool>
592 upsert( Q&& key, V&& val, bool bAllowInsert = true )
594 std::pair<bool, bool> bRet = bucket( val ).upsert( std::forward<Q>( key ), std::forward<V>( val ), bAllowInsert );
600 /// For key \p key inserts data of type \p mapped_type created from \p args
602 \p key_type should be constructible from type \p K
604 Returns \p true if inserting successful, \p false otherwise.
606 template <typename K, typename... Args>
607 bool emplace( K&& key, Args&&... args )
609 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
615 /// Deletes \p key from the map
616 /** \anchor cds_nonintrusive_MichaelMap_erase_val
618 Return \p true if \p key is found and deleted, \p false otherwise
620 template <typename K>
621 bool erase( K const& key )
623 const bool bRet = bucket( key ).erase( key );
629 /// Deletes the item from the map using \p pred predicate for searching
631 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
632 but \p pred is used for key comparing.
633 \p Less functor has the interface like \p std::less.
634 \p Less must imply the same element order as the comparator used for building the map.
636 template <typename K, typename Less>
637 bool erase_with( K const& key, Less pred )
639 const bool bRet = bucket( key ).erase_with( key, pred );
645 /// Deletes \p key from the map
646 /** \anchor cds_nonintrusive_MichaelMap_erase_func
648 The function searches an item with key \p key, calls \p f functor
649 and deletes the item. If \p key is not found, the functor is not called.
651 The functor \p Func interface:
654 void operator()(value_type& item) { ... }
658 Return \p true if key is found and deleted, \p false otherwise
660 template <typename K, typename Func>
661 bool erase( K const& key, Func f )
663 const bool bRet = bucket( key ).erase( key, f );
669 /// Deletes the item from the map using \p pred predicate for searching
671 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
672 but \p pred is used for key comparing.
673 \p Less functor has the interface like \p std::less.
674 \p Less must imply the same element order as the comparator used for building the map.
676 template <typename K, typename Less, typename Func>
677 bool erase_with( K const& key, Less pred, Func f )
679 const bool bRet = bucket( key ).erase_with( key, pred, f );
685 /// Extracts the item with specified \p key
686 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
687 The function searches an item with key equal to \p key,
688 unlinks it from the map, and returns it as \p guarded_ptr.
689 If \p key is not found the function returns an empty guarded pointer.
691 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
693 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
694 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
698 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
702 michael_map::guarded_ptr gp( theMap.extract( 5 ));
707 // Destructor of gp releases internal HP guard
711 template <typename K>
712 guarded_ptr extract( K const& key )
714 guarded_ptr gp( bucket( key ).extract( key ));
720 /// Extracts the item using compare functor \p pred
722 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
723 but \p pred predicate is used for key comparing.
725 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
727 \p pred must imply the same element order as the comparator used for building the map.
729 template <typename K, typename Less>
730 guarded_ptr extract_with( K const& key, Less pred )
732 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
738 /// Finds the key \p key
739 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
741 The function searches the item with key equal to \p key and calls the functor \p f for item found.
742 The interface of \p Func functor is:
745 void operator()( value_type& item );
748 where \p item is the item found.
750 The functor may change \p item.second. Note that the functor is only guarantee
751 that \p item cannot be disposed during functor is executing.
752 The functor does not serialize simultaneous access to the map's \p item. If such access is
753 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
755 The function returns \p true if \p key is found, \p false otherwise.
757 template <typename K, typename Func>
758 bool find( K const& key, Func f )
760 return bucket( key ).find( key, f );
763 /// Finds the key \p val using \p pred predicate for searching
765 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
766 but \p pred is used for key comparing.
767 \p Less functor has the interface like \p std::less.
768 \p Less must imply the same element order as the comparator used for building the map.
770 template <typename K, typename Less, typename Func>
771 bool find_with( K const& key, Less pred, Func f )
773 return bucket( key ).find_with( key, pred, f );
776 /// Checks whether the map contains \p key
778 The function searches the item with key equal to \p key
779 and returns \p true if it is found, and \p false otherwise.
781 template <typename K>
782 bool contains( K const& key )
784 return bucket( key ).contains( key );
787 template <typename K>
788 CDS_DEPRECATED("deprecated, use contains()")
789 bool find( K const& key )
791 return bucket( key ).contains( key );
795 /// Checks whether the map contains \p key using \p pred predicate for searching
797 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
798 \p Less functor has the interface like \p std::less.
799 \p Less must imply the same element order as the comparator used for building the map.
801 template <typename K, typename Less>
802 bool contains( K const& key, Less pred )
804 return bucket( key ).contains( key, pred );
807 template <typename K, typename Less>
808 CDS_DEPRECATED("deprecated, use contains()")
809 bool find_with( K const& key, Less pred )
811 return bucket( key ).contains( key, pred );
815 /// Finds \p key and return the item found
816 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
817 The function searches the item with key equal to \p key
818 and returns the guarded pointer to the item found.
819 If \p key is not found the function returns an empty guarded pointer,
821 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
825 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
829 michael_map::guarded_ptr gp( theMap.get( 5 ));
834 // Destructor of guarded_ptr releases internal HP guard
838 Note the compare functor specified for \p OrderedList template parameter
839 should accept a parameter of type \p K that can be not the same as \p key_type.
841 template <typename K>
842 guarded_ptr get( K const& key )
844 return bucket( key ).get( key );
847 /// Finds \p key and return the item found
849 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
850 but \p pred is used for comparing the keys.
852 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
854 \p pred must imply the same element order as the comparator used for building the map.
856 template <typename K, typename Less>
857 guarded_ptr get_with( K const& key, Less pred )
859 return bucket( key ).get_with( key, pred );
862 /// Clears the map (not atomic)
865 for ( size_t i = 0; i < bucket_count(); ++i )
866 m_Buckets[i].clear();
867 m_ItemCounter.reset();
870 /// Checks if the map is empty
872 Emptiness is checked by item counting: if item count is zero then the map is empty.
873 Thus, the correct item counting is an important part of the map implementation.
880 /// Returns item count in the map
883 return m_ItemCounter;
886 /// Returns the size of hash table
888 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
889 the value returned is an constant depending on object initialization parameters;
890 see \p MichaelHashMap::MichaelHashMap for explanation.
892 size_t bucket_count() const
894 return m_nHashBitmask + 1;
897 /// Returns const reference to internal statistics
898 stat const& statistics() const
905 /// Calculates hash value of \p key
906 template <typename Q>
907 size_t hash_value( Q const& key ) const
909 return m_HashFunctor( key ) & m_nHashBitmask;
912 /// Returns the bucket (ordered list) for \p key
913 template <typename Q>
914 internal_bucket_type& bucket( Q const& key )
916 return m_Buckets[hash_value( key )];
922 internal_bucket_type* bucket_begin() const
927 internal_bucket_type* bucket_end() const
929 return m_Buckets + bucket_count();
932 const_iterator get_const_begin() const
934 return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end() );
936 const_iterator get_const_end() const
938 return const_iterator( (bucket_end() - 1)->cend(), bucket_end() - 1, bucket_end() );
941 template <typename Stat>
942 typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
944 new (bucket) internal_bucket_type;
947 template <typename Stat>
948 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
950 new (bucket) internal_bucket_type( m_Stat );
954 }} // namespace cds::container
956 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H