2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 #ifdef CDS_DOXYGEN_INVOKED
162 typedef typename ordered_list::stat stat; ///< Internal statistics
163 /// Guarded pointer - a result of \p get() and \p extract() functions
164 typedef typename ordered_list::guarded_ptr guarded_ptr;
167 /// Hash functor for \ref key_type and all its derivatives that you use
168 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
169 typedef typename traits::item_counter item_counter; ///< Item counter type
171 // GC and OrderedList::gc must be the same
172 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
174 // atomicity::empty_item_counter is not allowed as a item counter
175 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
176 "atomicity::empty_item_counter is not allowed as a item counter");
178 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
181 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
183 typedef typename ordered_list::template rebind_traits<
184 cds::opt::item_counter< cds::atomicity::empty_item_counter >
185 , cds::opt::stat< typename bucket_stat::wrapped_stat >
186 >::type internal_bucket_type;
188 typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
189 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
190 typedef typename bucket_stat::stat stat;
195 const size_t m_nHashBitmask;
196 internal_bucket_type* m_Buckets; ///< bucket table
197 item_counter m_ItemCounter; ///< Item counter
198 hash m_HashFunctor; ///< Hash functor
199 stat m_Stat; ///< Internal statistics
205 template <bool IsConst>
206 class iterator_type: protected cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
208 typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class;
209 friend class MichaelHashMap;
212 typedef typename base_class::bucket_ptr bucket_ptr;
213 typedef typename base_class::list_iterator list_iterator;
216 /// Value pointer type (const for const_iterator)
217 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
218 /// Value reference type (const for const_iterator)
219 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
221 /// Key-value pair pointer type (const for const_iterator)
222 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
223 /// Key-value pair reference type (const for const_iterator)
224 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
227 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
228 : base_class( it, pFirst, pLast )
238 iterator_type( const iterator_type& src )
242 /// Dereference operator
243 pair_ptr operator ->() const
245 assert( base_class::m_pCurBucket != nullptr );
246 return base_class::m_itList.operator ->();
249 /// Dereference operator
250 pair_ref operator *() const
252 assert( base_class::m_pCurBucket != nullptr );
253 return base_class::m_itList.operator *();
257 iterator_type& operator ++()
259 base_class::operator++();
263 /// Assignment operator
264 iterator_type& operator = (const iterator_type& src)
266 base_class::operator =(src);
270 /// Returns current bucket (debug function)
271 bucket_ptr bucket() const
273 return base_class::bucket();
276 /// Equality operator
278 bool operator ==(iterator_type<C> const& i ) const
280 return base_class::operator ==( i );
282 /// Equality operator
284 bool operator !=(iterator_type<C> const& i ) const
286 return !( *this == i );
292 ///@name Forward iterators (only for debugging purpose)
296 The forward iterator for Michael's map has some features:
297 - it has no post-increment operator
298 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
299 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
300 may be thrown if the limit of guard count per thread is exceeded.
301 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
303 Iterator thread safety depends on type of \p OrderedList:
304 - for \p MichaelKVList and \p LazyKVList: iterator guarantees safety even if you delete the item that iterator points to
305 because that item is guarded by hazard pointer.
306 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the map.
307 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
308 Use this iterator on the concurrent container for debugging purpose only.
309 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
311 The iterator interface:
315 // Default constructor
319 iterator( iterator const& src );
321 // Dereference operator
322 value_type * operator ->() const;
324 // Dereference operator
325 value_type& operator *() const;
327 // Preincrement operator
328 iterator& operator ++();
330 // Assignment operator
331 iterator& operator = (iterator const& src);
333 // Equality operators
334 bool operator ==(iterator const& i ) const;
335 bool operator !=(iterator const& i ) const;
339 @note The iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
341 typedef iterator_type< false > iterator;
343 /// Const forward iterator
344 typedef iterator_type< true > const_iterator;
346 /// Returns a forward iterator addressing the first element in a map
348 For empty map \code begin() == end() \endcode
352 return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
355 /// Returns an iterator that addresses the location succeeding the last element in a map
357 Do not use the value returned by <tt>end</tt> function to access any item.
358 The returned value can be used only to control reaching the end of the map.
359 For empty map \code begin() == end() \endcode
363 return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
366 /// Returns a forward const iterator addressing the first element in a map
367 const_iterator begin() const
369 return get_const_begin();
371 /// Returns a forward const iterator addressing the first element in a map
372 const_iterator cbegin() const
374 return get_const_begin();
377 /// Returns an const iterator that addresses the location succeeding the last element in a map
378 const_iterator end() const
380 return get_const_end();
382 /// Returns an const iterator that addresses the location succeeding the last element in a map
383 const_iterator cend() const
385 return get_const_end();
390 /// Initializes the map
391 /** @anchor cds_nonintrusive_MichaelHashMap_hp_ctor
392 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
393 when you create an object.
394 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
395 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
396 Note, that many popular STL hash map implementation uses load factor 1.
398 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
401 size_t nMaxItemCount, ///< estimation of max item count in the hash map
402 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
404 : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
405 , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
407 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
408 construct_bucket<bucket_stat>( it );
411 /// Clears hash map and destroys it
416 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
417 it->~internal_bucket_type();
418 bucket_table_allocator().deallocate( m_Buckets, bucket_count());
421 /// Inserts new node with key and default value
423 The function creates a node with \p key and default value, and then inserts the node created into the map.
426 - The \p key_type should be constructible from value of type \p K.
427 In trivial case, \p K is equal to \p key_type.
428 - The \p mapped_type should be default-constructible.
430 Returns \p true if inserting successful, \p false otherwise.
432 template <typename K>
433 bool insert( K&& key )
435 const bool bRet = bucket( key ).insert( std::forward<K>( key ));
443 The function creates a node with copy of \p val value
444 and then inserts the node created into the map.
447 - The \p key_type should be constructible from \p key of type \p K.
448 - The \p mapped_type should be constructible from \p val of type \p V.
450 Returns \p true if \p val is inserted into the map, \p false otherwise.
452 template <typename K, typename V>
453 bool insert( K&& key, V&& val )
455 const bool bRet = bucket( key ).insert( std::forward<K>( key ), std::forward<V>( val ));
461 /// Inserts new node and initialize it by a functor
463 This function inserts new node with key \p key and if inserting is successful then it calls
464 \p func functor with signature
467 void operator()( value_type& item );
471 The argument \p item of user-defined functor \p func is the reference
472 to the map's item inserted:
473 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
474 - <tt>item.second</tt> is a reference to item's value that may be changed.
476 The user-defined functor is called only if inserting is successful.
478 The \p key_type should be constructible from value of type \p K.
480 The function allows to split creating of new item into two part:
481 - create item from \p key;
482 - insert new item into the map;
483 - if inserting is successful, initialize the value of item by calling \p func functor
485 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
486 it is preferable that the initialization should be completed only if inserting is successful.
488 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
489 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
492 template <typename K, typename Func>
493 bool insert_with( K&& key, Func func )
495 const bool bRet = bucket( key ).insert_with( std::forward<K>( key ), func );
501 /// Updates data by \p key
503 The operation performs inserting or replacing the element with lock-free manner.
505 If the \p key not found in the map, then the new item created from \p key
506 will be inserted into the map iff \p bAllowInsert is \p true.
507 (note that in this case the \ref key_type should be constructible from type \p K).
508 Otherwise, if \p key is found, the functor \p func is called with item found.
510 The functor \p func signature depends on \p OrderedList:
512 <b>for \p MichaelKVList, \p LazyKVList</b>
515 void operator()( bool bNew, value_type& item );
519 - \p bNew - \p true if the item has been inserted, \p false otherwise
520 - \p item - the item found or inserted
522 The functor may change any fields of the \p item.second that is \p mapped_type.
524 <b>for \p IterableKVList</b>
526 void func( value_type& val, value_type * old );
529 - \p val - a new data constructed from \p key
530 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
532 The functor may change non-key fields of \p val; however, \p func must guarantee
533 that during changing no any other modifications could be made on this item by concurrent threads.
535 @return <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
536 \p second is true if new item has been added or \p false if the item with \p key
539 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
540 as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
541 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
544 template <typename K, typename Func >
545 std::pair<bool, bool> update( K&& key, Func func, bool bAllowInsert = true )
547 std::pair<bool, bool> bRet = bucket( key ).update( std::forward<K>( key ), func, bAllowInsert );
548 if ( bRet.first && bRet.second )
553 template <typename K, typename Func>
554 CDS_DEPRECATED("ensure() is deprecated, use update()")
555 std::pair<bool, bool> ensure( K const& key, Func func )
557 std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
558 if ( bRet.first && bRet.second )
564 /// Inserts or updates the node (only for \p IterableKVList)
566 The operation performs inserting or changing data with lock-free manner.
568 If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
569 Otherwise, the current element is changed to \p val, the old element will be retired later.
571 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
572 \p second is \p true if \p val has been added or \p false if the item with that key
575 template <typename Q, typename V>
576 #ifdef CDS_DOXYGEN_INVOKED
577 std::pair<bool, bool>
579 typename std::enable_if<
580 std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
581 std::pair<bool, bool>
584 upsert( Q&& key, V&& val, bool bAllowInsert = true )
586 std::pair<bool, bool> bRet = bucket( val ).upsert( std::forward<Q>( key ), std::forward<V>( val ), bAllowInsert );
592 /// For key \p key inserts data of type \p mapped_type created from \p args
594 \p key_type should be constructible from type \p K
596 Returns \p true if inserting successful, \p false otherwise.
598 template <typename K, typename... Args>
599 bool emplace( K&& key, Args&&... args )
601 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
607 /// Deletes \p key from the map
608 /** \anchor cds_nonintrusive_MichaelMap_erase_val
610 Return \p true if \p key is found and deleted, \p false otherwise
612 template <typename K>
613 bool erase( K const& key )
615 const bool bRet = bucket( key ).erase( key );
621 /// Deletes the item from the map using \p pred predicate for searching
623 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
624 but \p pred is used for key comparing.
625 \p Less functor has the interface like \p std::less.
626 \p Less must imply the same element order as the comparator used for building the map.
628 template <typename K, typename Less>
629 bool erase_with( K const& key, Less pred )
631 const bool bRet = bucket( key ).erase_with( key, pred );
637 /// Deletes \p key from the map
638 /** \anchor cds_nonintrusive_MichaelMap_erase_func
640 The function searches an item with key \p key, calls \p f functor
641 and deletes the item. If \p key is not found, the functor is not called.
643 The functor \p Func interface:
646 void operator()(value_type& item) { ... }
650 Return \p true if key is found and deleted, \p false otherwise
652 template <typename K, typename Func>
653 bool erase( K const& key, Func f )
655 const bool bRet = bucket( key ).erase( key, f );
661 /// Deletes the item from the map using \p pred predicate for searching
663 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
664 but \p pred is used for key comparing.
665 \p Less functor has the interface like \p std::less.
666 \p Less must imply the same element order as the comparator used for building the map.
668 template <typename K, typename Less, typename Func>
669 bool erase_with( K const& key, Less pred, Func f )
671 const bool bRet = bucket( key ).erase_with( key, pred, f );
677 /// Deletes the item pointed by iterator \p iter (only for \p IterableList based map)
679 Returns \p true if the operation is successful, \p false otherwise.
680 The function can return \p false if the node the iterator points to has already been deleted
683 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
685 @note \p %erase_at() is supported only for \p %MichaelHashMap based on \p IterableList.
687 #ifdef CDS_DOXYGEN_INVOKED
688 bool erase_at( iterator const& iter )
690 template <typename Iterator>
691 typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
692 erase_at( Iterator const& iter )
695 assert( iter != end() );
696 assert( iter.bucket() != nullptr );
698 if ( iter.bucket()->erase_at( iter.underlying_iterator())) {
705 /// Extracts the item with specified \p key
706 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
707 The function searches an item with key equal to \p key,
708 unlinks it from the map, and returns it as \p guarded_ptr.
709 If \p key is not found the function returns an empty guarded pointer.
711 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
713 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
714 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
718 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
722 michael_map::guarded_ptr gp( theMap.extract( 5 ));
727 // Destructor of gp releases internal HP guard
731 template <typename K>
732 guarded_ptr extract( K const& key )
734 guarded_ptr gp( bucket( key ).extract( key ));
740 /// Extracts the item using compare functor \p pred
742 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
743 but \p pred predicate is used for key comparing.
745 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
747 \p pred must imply the same element order as the comparator used for building the map.
749 template <typename K, typename Less>
750 guarded_ptr extract_with( K const& key, Less pred )
752 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
758 /// Finds the key \p key
759 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
761 The function searches the item with key equal to \p key and calls the functor \p f for item found.
762 The interface of \p Func functor is:
765 void operator()( value_type& item );
768 where \p item is the item found.
770 The functor may change \p item.second. Note that the functor is only guarantee
771 that \p item cannot be disposed during functor is executing.
772 The functor does not serialize simultaneous access to the map's \p item. If such access is
773 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
775 The function returns \p true if \p key is found, \p false otherwise.
777 template <typename K, typename Func>
778 bool find( K const& key, Func f )
780 return bucket( key ).find( key, f );
783 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
785 If \p key is not found the function returns \p end().
787 @note This function is supported only for map based on \p IterableList
789 template <typename K>
790 #ifdef CDS_DOXYGEN_INVOKED
793 typename std::enable_if< std::is_same<K,K>::value && is_iterable_list< ordered_list >::value, iterator >::type
797 auto& b = bucket( key );
798 auto it = b.find( key );
801 return iterator( it, &b, bucket_end());
805 /// Finds the key \p val using \p pred predicate for searching
807 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
808 but \p pred is used for key comparing.
809 \p Less functor has the interface like \p std::less.
810 \p Less must imply the same element order as the comparator used for building the map.
812 template <typename K, typename Less, typename Func>
813 bool find_with( K const& key, Less pred, Func f )
815 return bucket( key ).find_with( key, pred, f );
818 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
820 The function is an analog of \p find(K&) but \p pred is used for key comparing.
821 \p Less functor has the interface like \p std::less.
822 \p pred must imply the same element order as the comparator used for building the set.
824 If \p key is not found the function returns \p end().
826 @note This function is supported only for map based on \p IterableList
828 template <typename K, typename Less>
829 #ifdef CDS_DOXYGEN_INVOKED
832 typename std::enable_if< std::is_same<K, K>::value && is_iterable_list< ordered_list >::value, iterator >::type
834 find_with( K const& key, Less pred )
836 auto& b = bucket( key );
837 auto it = b.find_with( key, pred );
840 return iterator( it, &b, bucket_end());
843 /// Checks whether the map contains \p key
845 The function searches the item with key equal to \p key
846 and returns \p true if it is found, and \p false otherwise.
848 template <typename K>
849 bool contains( K const& key )
851 return bucket( key ).contains( key );
854 /// Checks whether the map contains \p key using \p pred predicate for searching
856 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
857 \p Less functor has the interface like \p std::less.
858 \p Less must imply the same element order as the comparator used for building the map.
860 template <typename K, typename Less>
861 bool contains( K const& key, Less pred )
863 return bucket( key ).contains( key, pred );
866 /// Finds \p key and return the item found
867 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
868 The function searches the item with key equal to \p key
869 and returns the guarded pointer to the item found.
870 If \p key is not found the function returns an empty guarded pointer,
872 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
876 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
880 michael_map::guarded_ptr gp( theMap.get( 5 ));
885 // Destructor of guarded_ptr releases internal HP guard
889 Note the compare functor specified for \p OrderedList template parameter
890 should accept a parameter of type \p K that can be not the same as \p key_type.
892 template <typename K>
893 guarded_ptr get( K const& key )
895 return bucket( key ).get( key );
898 /// Finds \p key and return the item found
900 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
901 but \p pred is used for comparing the keys.
903 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
905 \p pred must imply the same element order as the comparator used for building the map.
907 template <typename K, typename Less>
908 guarded_ptr get_with( K const& key, Less pred )
910 return bucket( key ).get_with( key, pred );
913 /// Clears the map (not atomic)
916 for ( size_t i = 0; i < bucket_count(); ++i )
917 m_Buckets[i].clear();
918 m_ItemCounter.reset();
921 /// Checks if the map is empty
923 Emptiness is checked by item counting: if item count is zero then the map is empty.
924 Thus, the correct item counting is an important part of the map implementation.
931 /// Returns item count in the map
934 return m_ItemCounter;
937 /// Returns the size of hash table
939 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
940 the value returned is an constant depending on object initialization parameters;
941 see \p MichaelHashMap::MichaelHashMap for explanation.
943 size_t bucket_count() const
945 return m_nHashBitmask + 1;
948 /// Returns const reference to internal statistics
949 stat const& statistics() const
956 /// Calculates hash value of \p key
957 template <typename Q>
958 size_t hash_value( Q const& key ) const
960 return m_HashFunctor( key ) & m_nHashBitmask;
963 /// Returns the bucket (ordered list) for \p key
964 template <typename Q>
965 internal_bucket_type& bucket( Q const& key )
967 return m_Buckets[hash_value( key )];
973 internal_bucket_type* bucket_begin() const
978 internal_bucket_type* bucket_end() const
980 return m_Buckets + bucket_count();
983 const_iterator get_const_begin() const
985 return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end());
987 const_iterator get_const_end() const
989 return const_iterator( (bucket_end() - 1)->cend(), bucket_end() - 1, bucket_end());
992 template <typename Stat>
993 typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
995 new (bucket) internal_bucket_type;
998 template <typename Stat>
999 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
1001 new (bucket) internal_bucket_type( m_Stat );
1005 }} // namespace cds::container
1007 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H