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 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
177 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
179 typedef typename ordered_list::template rebind_traits<
180 cds::opt::item_counter< cds::atomicity::empty_item_counter >
181 , cds::opt::stat< typename bucket_stat::wrapped_stat >
182 >::type internal_bucket_type;
184 typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
185 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
186 typedef typename bucket_stat::stat stat;
191 const size_t m_nHashBitmask;
192 internal_bucket_type* m_Buckets; ///< bucket table
193 hash m_HashFunctor; ///< Hash functor
194 item_counter m_ItemCounter; ///< Item counter
195 stat m_Stat; ///< Internal statistics
201 template <bool IsConst>
202 class iterator_type: protected cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
204 typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class;
205 friend class MichaelHashMap;
208 typedef typename base_class::bucket_ptr bucket_ptr;
209 typedef typename base_class::list_iterator list_iterator;
212 /// Value pointer type (const for const_iterator)
213 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
214 /// Value reference type (const for const_iterator)
215 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
217 /// Key-value pair pointer type (const for const_iterator)
218 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
219 /// Key-value pair reference type (const for const_iterator)
220 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
223 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
224 : base_class( it, pFirst, pLast )
234 iterator_type( const iterator_type& src )
238 /// Dereference operator
239 pair_ptr operator ->() const
241 assert( base_class::m_pCurBucket != nullptr );
242 return base_class::m_itList.operator ->();
245 /// Dereference operator
246 pair_ref operator *() const
248 assert( base_class::m_pCurBucket != nullptr );
249 return base_class::m_itList.operator *();
253 iterator_type& operator ++()
255 base_class::operator++();
259 /// Assignment operator
260 iterator_type& operator = (const iterator_type& src)
262 base_class::operator =(src);
266 /// Returns current bucket (debug function)
267 bucket_ptr bucket() const
269 return base_class::bucket();
272 /// Equality operator
274 bool operator ==(iterator_type<C> const& i ) const
276 return base_class::operator ==( i );
278 /// Equality operator
280 bool operator !=(iterator_type<C> const& i ) const
282 return !( *this == i );
288 ///@name Forward iterators (only for debugging purpose)
292 The forward iterator for Michael's map has some features:
293 - it has no post-increment operator
294 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
295 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
296 may be thrown if the limit of guard count per thread is exceeded.
297 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
299 Iterator thread safety depends on type of \p OrderedList:
300 - for \p MichaelKVList and \p LazyKVList: iterator guarantees safety even if you delete the item that iterator points to
301 because that item is guarded by hazard pointer.
302 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the map.
303 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
304 Use this iterator on the concurrent container for debugging purpose only.
305 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
307 The iterator interface:
311 // Default constructor
315 iterator( iterator const& src );
317 // Dereference operator
318 value_type * operator ->() const;
320 // Dereference operator
321 value_type& operator *() const;
323 // Preincrement operator
324 iterator& operator ++();
326 // Assignment operator
327 iterator& operator = (iterator const& src);
329 // Equality operators
330 bool operator ==(iterator const& i ) const;
331 bool operator !=(iterator const& i ) const;
335 @note The iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
337 typedef iterator_type< false > iterator;
339 /// Const forward iterator
340 typedef iterator_type< true > const_iterator;
342 /// Returns a forward iterator addressing the first element in a map
344 For empty map \code begin() == end() \endcode
348 return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
351 /// Returns an iterator that addresses the location succeeding the last element in a map
353 Do not use the value returned by <tt>end</tt> function to access any item.
354 The returned value can be used only to control reaching the end of the map.
355 For empty map \code begin() == end() \endcode
359 return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
362 /// Returns a forward const iterator addressing the first element in a map
363 const_iterator begin() const
365 return get_const_begin();
367 /// Returns a forward const iterator addressing the first element in a map
368 const_iterator cbegin() const
370 return get_const_begin();
373 /// Returns an const iterator that addresses the location succeeding the last element in a map
374 const_iterator end() const
376 return get_const_end();
378 /// Returns an const iterator that addresses the location succeeding the last element in a map
379 const_iterator cend() const
381 return get_const_end();
386 /// Initializes the map
387 /** @anchor cds_nonintrusive_MichaelHashMap_hp_ctor
388 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
389 when you create an object.
390 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
391 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
392 Note, that many popular STL hash map implementation uses load factor 1.
394 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
397 size_t nMaxItemCount, ///< estimation of max item count in the hash map
398 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
400 : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
401 , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
403 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
404 construct_bucket<bucket_stat>( it );
407 /// Clears hash map and destroys it
412 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
413 it->~internal_bucket_type();
414 bucket_table_allocator().deallocate( m_Buckets, bucket_count());
417 /// Inserts new node with key and default value
419 The function creates a node with \p key and default value, and then inserts the node created into the map.
422 - The \p key_type should be constructible from value of type \p K.
423 In trivial case, \p K is equal to \p key_type.
424 - The \p mapped_type should be default-constructible.
426 Returns \p true if inserting successful, \p false otherwise.
428 template <typename K>
429 bool insert( K&& key )
431 const bool bRet = bucket( key ).insert( std::forward<K>( key ));
439 The function creates a node with copy of \p val value
440 and then inserts the node created into the map.
443 - The \p key_type should be constructible from \p key of type \p K.
444 - The \p mapped_type should be constructible from \p val of type \p V.
446 Returns \p true if \p val is inserted into the map, \p false otherwise.
448 template <typename K, typename V>
449 bool insert( K&& key, V&& val )
451 const bool bRet = bucket( key ).insert( std::forward<K>( key ), std::forward<V>( val ));
457 /// Inserts new node and initialize it by a functor
459 This function inserts new node with key \p key and if inserting is successful then it calls
460 \p func functor with signature
463 void operator()( value_type& item );
467 The argument \p item of user-defined functor \p func is the reference
468 to the map's item inserted:
469 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
470 - <tt>item.second</tt> is a reference to item's value that may be changed.
472 The user-defined functor is called only if inserting is successful.
474 The \p key_type should be constructible from value of type \p K.
476 The function allows to split creating of new item into two part:
477 - create item from \p key;
478 - insert new item into the map;
479 - if inserting is successful, initialize the value of item by calling \p func functor
481 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
482 it is preferable that the initialization should be completed only if inserting is successful.
484 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
485 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
488 template <typename K, typename Func>
489 bool insert_with( K&& key, Func func )
491 const bool bRet = bucket( key ).insert_with( std::forward<K>( key ), func );
497 /// Updates data by \p key
499 The operation performs inserting or replacing the element with lock-free manner.
501 If the \p key not found in the map, then the new item created from \p key
502 will be inserted into the map iff \p bAllowInsert is \p true.
503 (note that in this case the \ref key_type should be constructible from type \p K).
504 Otherwise, if \p key is found, the functor \p func is called with item found.
506 The functor \p func signature depends on \p OrderedList:
508 <b>for \p MichaelKVList, \p LazyKVList</b>
511 void operator()( bool bNew, value_type& item );
515 - \p bNew - \p true if the item has been inserted, \p false otherwise
516 - \p item - the item found or inserted
518 The functor may change any fields of the \p item.second that is \p mapped_type.
520 <b>for \p IterableKVList</b>
522 void func( value_type& val, value_type * old );
525 - \p val - a new data constructed from \p key
526 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
528 The functor may change non-key fields of \p val; however, \p func must guarantee
529 that during changing no any other modifications could be made on this item by concurrent threads.
531 @return <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
532 \p second is true if new item has been added or \p false if the item with \p key
535 @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
536 as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
537 \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
540 template <typename K, typename Func >
541 std::pair<bool, bool> update( K&& key, Func func, bool bAllowInsert = true )
543 std::pair<bool, bool> bRet = bucket( key ).update( std::forward<K>( key ), func, bAllowInsert );
544 if ( bRet.first && bRet.second )
549 template <typename K, typename Func>
550 CDS_DEPRECATED("ensure() is deprecated, use update()")
551 std::pair<bool, bool> ensure( K const& key, Func func )
553 std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
554 if ( bRet.first && bRet.second )
560 /// Inserts or updates the node (only for \p IterableKVList)
562 The operation performs inserting or changing data with lock-free manner.
564 If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
565 Otherwise, the current element is changed to \p val, the old element will be retired later.
567 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
568 \p second is \p true if \p val has been added or \p false if the item with that key
571 template <typename Q, typename V>
572 #ifdef CDS_DOXYGEN_INVOKED
573 std::pair<bool, bool>
575 typename std::enable_if<
576 std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
577 std::pair<bool, bool>
580 upsert( Q&& key, V&& val, bool bAllowInsert = true )
582 std::pair<bool, bool> bRet = bucket( val ).upsert( std::forward<Q>( key ), std::forward<V>( val ), bAllowInsert );
588 /// For key \p key inserts data of type \p mapped_type created from \p args
590 \p key_type should be constructible from type \p K
592 Returns \p true if inserting successful, \p false otherwise.
594 template <typename K, typename... Args>
595 bool emplace( K&& key, Args&&... args )
597 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
603 /// Deletes \p key from the map
604 /** \anchor cds_nonintrusive_MichaelMap_erase_val
606 Return \p true if \p key is found and deleted, \p false otherwise
608 template <typename K>
609 bool erase( K const& key )
611 const bool bRet = bucket( key ).erase( key );
617 /// Deletes the item from the map using \p pred predicate for searching
619 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
620 but \p pred is used for key comparing.
621 \p Less functor has the interface like \p std::less.
622 \p Less must imply the same element order as the comparator used for building the map.
624 template <typename K, typename Less>
625 bool erase_with( K const& key, Less pred )
627 const bool bRet = bucket( key ).erase_with( key, pred );
633 /// Deletes \p key from the map
634 /** \anchor cds_nonintrusive_MichaelMap_erase_func
636 The function searches an item with key \p key, calls \p f functor
637 and deletes the item. If \p key is not found, the functor is not called.
639 The functor \p Func interface:
642 void operator()(value_type& item) { ... }
646 Return \p true if key is found and deleted, \p false otherwise
648 template <typename K, typename Func>
649 bool erase( K const& key, Func f )
651 const bool bRet = bucket( key ).erase( key, f );
657 /// Deletes the item from the map using \p pred predicate for searching
659 The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
660 but \p pred is used for key comparing.
661 \p Less functor has the interface like \p std::less.
662 \p Less must imply the same element order as the comparator used for building the map.
664 template <typename K, typename Less, typename Func>
665 bool erase_with( K const& key, Less pred, Func f )
667 const bool bRet = bucket( key ).erase_with( key, pred, f );
673 /// Deletes the item pointed by iterator \p iter (only for \p IterableList based map)
675 Returns \p true if the operation is successful, \p false otherwise.
676 The function can return \p false if the node the iterator points to has already been deleted
679 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
681 @note \p %erase_at() is supported only for \p %MichaelHashMap based on \p IterableList.
683 #ifdef CDS_DOXYGEN_INVOKED
684 bool erase_at( iterator const& iter )
686 template <typename Iterator>
687 typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
688 erase_at( Iterator const& iter )
691 assert( iter != end());
692 assert( iter.bucket() != nullptr );
694 if ( iter.bucket()->erase_at( iter.underlying_iterator())) {
701 /// Extracts the item with specified \p key
702 /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
703 The function searches an item with key equal to \p key,
704 unlinks it from the map, and returns it as \p guarded_ptr.
705 If \p key is not found the function returns an empty guarded pointer.
707 Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
709 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
710 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
714 typedef cds::container::MichaelHashMap< your_template_args > michael_map;
718 michael_map::guarded_ptr gp( theMap.extract( 5 ));
723 // Destructor of gp releases internal HP guard
727 template <typename K>
728 guarded_ptr extract( K const& key )
730 guarded_ptr gp( bucket( key ).extract( key ));
736 /// Extracts the item using compare functor \p pred
738 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
739 but \p pred predicate is used for key comparing.
741 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
743 \p pred must imply the same element order as the comparator used for building the map.
745 template <typename K, typename Less>
746 guarded_ptr extract_with( K const& key, Less pred )
748 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
754 /// Finds the key \p key
755 /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
757 The function searches the item with key equal to \p key and calls the functor \p f for item found.
758 The interface of \p Func functor is:
761 void operator()( value_type& item );
764 where \p item is the item found.
766 The functor may change \p item.second. Note that the functor is only guarantee
767 that \p item cannot be disposed during functor is executing.
768 The functor does not serialize simultaneous access to the map's \p item. If such access is
769 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
771 The function returns \p true if \p key is found, \p false otherwise.
773 template <typename K, typename Func>
774 bool find( K const& key, Func f )
776 return bucket( key ).find( key, f );
779 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
781 If \p key is not found the function returns \p end().
783 @note This function is supported only for map based on \p IterableList
785 template <typename K>
786 #ifdef CDS_DOXYGEN_INVOKED
789 typename std::enable_if< std::is_same<K,K>::value && is_iterable_list< ordered_list >::value, iterator >::type
793 auto& b = bucket( key );
794 auto it = b.find( key );
797 return iterator( it, &b, bucket_end());
801 /// Finds the key \p val using \p pred predicate for searching
803 The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
804 but \p pred is used for key comparing.
805 \p Less functor has the interface like \p std::less.
806 \p Less must imply the same element order as the comparator used for building the map.
808 template <typename K, typename Less, typename Func>
809 bool find_with( K const& key, Less pred, Func f )
811 return bucket( key ).find_with( key, pred, f );
814 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
816 The function is an analog of \p find(K&) but \p pred is used for key comparing.
817 \p Less functor has the interface like \p std::less.
818 \p pred must imply the same element order as the comparator used for building the set.
820 If \p key is not found the function returns \p end().
822 @note This function is supported only for map based on \p IterableList
824 template <typename K, typename Less>
825 #ifdef CDS_DOXYGEN_INVOKED
828 typename std::enable_if< std::is_same<K, K>::value && is_iterable_list< ordered_list >::value, iterator >::type
830 find_with( K const& key, Less pred )
832 auto& b = bucket( key );
833 auto it = b.find_with( key, pred );
836 return iterator( it, &b, bucket_end());
839 /// Checks whether the map contains \p key
841 The function searches the item with key equal to \p key
842 and returns \p true if it is found, and \p false otherwise.
844 template <typename K>
845 bool contains( K const& key )
847 return bucket( key ).contains( key );
850 /// Checks whether the map contains \p key using \p pred predicate for searching
852 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
853 \p Less functor has the interface like \p std::less.
854 \p Less must imply the same element order as the comparator used for building the map.
856 template <typename K, typename Less>
857 bool contains( K const& key, Less pred )
859 return bucket( key ).contains( key, pred );
862 /// Finds \p key and return the item found
863 /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
864 The function searches the item with key equal to \p key
865 and returns the guarded pointer to the item found.
866 If \p key is not found the function returns an empty guarded pointer,
868 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
872 typedef cds::container::MichaeHashMap< your_template_params > michael_map;
876 michael_map::guarded_ptr gp( theMap.get( 5 ));
881 // Destructor of guarded_ptr releases internal HP guard
885 Note the compare functor specified for \p OrderedList template parameter
886 should accept a parameter of type \p K that can be not the same as \p key_type.
888 template <typename K>
889 guarded_ptr get( K const& key )
891 return bucket( key ).get( key );
894 /// Finds \p key and return the item found
896 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
897 but \p pred is used for comparing the keys.
899 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
901 \p pred must imply the same element order as the comparator used for building the map.
903 template <typename K, typename Less>
904 guarded_ptr get_with( K const& key, Less pred )
906 return bucket( key ).get_with( key, pred );
909 /// Clears the map (not atomic)
912 for ( size_t i = 0; i < bucket_count(); ++i )
913 m_Buckets[i].clear();
914 m_ItemCounter.reset();
917 /// Checks if the map is empty
919 @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
920 the function always returns \p true.
927 /// Returns item count in the map
929 If you use \p atomicity::empty_item_counter in \p traits::item_counter,
930 the function always returns 0.
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* b )
995 new (b) internal_bucket_type;
998 template <typename Stat>
999 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* b )
1001 new (b) internal_bucket_type( m_Stat );
1005 }} // namespace cds::container
1007 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H