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_NOGC_H
32 #define CDSLIB_CONTAINER_MICHAEL_MAP_NOGC_H
34 #include <cds/container/details/michael_map_base.h>
35 #include <cds/gc/nogc.h>
36 #include <cds/details/allocator.h>
38 namespace cds { namespace container {
40 /// Michael's hash map (template specialization for \p cds::gc::nogc)
41 /** @ingroup cds_nonintrusive_map
42 \anchor cds_nonintrusive_MichaelHashMap_nogc
44 This specialization is so-called append-only when no item
45 reclamation may be performed. The class does not support deleting of map item.
47 See @ref cds_nonintrusive_MichaelHashMap_hp "MichaelHashMap" for description of template parameters.
51 #ifdef CDS_DOXYGEN_INVOKED
52 class Traits = michael_map::traits
57 class MichaelHashMap<cds::gc::nogc, OrderedList, Traits>
60 typedef cds::gc::nogc gc; ///< No garbage collector
61 typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
62 typedef Traits traits; ///< Map traits
64 typedef typename ordered_list::key_type key_type; ///< key type
65 typedef typename ordered_list::mapped_type mapped_type; ///< type of value to be stored in the map
66 typedef typename ordered_list::value_type value_type; ///< Pair used as the some functor's argument
68 typedef typename ordered_list::key_comparator key_comparator; ///< key comparing functor
70 /// Hash functor for \ref key_type and all its derivatives that you use
71 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
72 typedef typename traits::item_counter item_counter; ///< Item counter type
73 typedef typename traits::allocator allocator; ///< Bucket table allocator
75 #ifdef CDS_DOXYGEN_INVOKED
76 typedef typename ordered_list::stat stat; ///< Internal statistics
79 // GC and OrderedList::gc must be the same
80 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
84 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
86 typedef typename ordered_list::template rebind_traits<
87 cds::opt::item_counter< cds::atomicity::empty_item_counter >
88 , cds::opt::stat< typename bucket_stat::wrapped_stat >
89 >::type internal_bucket_type;
91 /// Bucket table allocator
92 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
94 typedef typename internal_bucket_type::iterator bucket_iterator;
95 typedef typename internal_bucket_type::const_iterator bucket_const_iterator;
100 typedef typename bucket_stat::stat stat;
105 const size_t m_nHashBitmask;
106 hash m_HashFunctor; ///< Hash functor
107 internal_bucket_type* m_Buckets; ///< bucket table
108 item_counter m_ItemCounter; ///< Item counter
109 stat m_Stat; ///< Internal statistics
114 template <bool IsConst>
115 class iterator_type: private cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
117 typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class;
118 friend class MichaelHashMap;
121 typedef typename base_class::bucket_ptr bucket_ptr;
122 typedef typename base_class::list_iterator list_iterator;
125 /// Value pointer type (const for const_iterator)
126 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
127 /// Value reference type (const for const_iterator)
128 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
130 /// Key-value pair pointer type (const for const_iterator)
131 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
132 /// Key-value pair reference type (const for const_iterator)
133 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
136 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
137 : base_class( it, pFirst, pLast )
147 iterator_type( const iterator_type& src )
151 /// Dereference operator
152 pair_ptr operator ->() const
154 assert( base_class::m_pCurBucket != nullptr );
155 return base_class::m_itList.operator ->();
158 /// Dereference operator
159 pair_ref operator *() const
161 assert( base_class::m_pCurBucket != nullptr );
162 return base_class::m_itList.operator *();
166 iterator_type& operator ++()
168 base_class::operator++();
172 /// Assignment operator
173 iterator_type& operator = (const iterator_type& src)
175 base_class::operator =(src);
179 /// Returns current bucket (debug function)
180 bucket_ptr bucket() const
182 return base_class::bucket();
185 /// Equality operator
187 bool operator ==(iterator_type<C> const& i ) const
189 return base_class::operator ==( i );
191 /// Equality operator
193 bool operator !=(iterator_type<C> const& i ) const
195 return !( *this == i );
201 ///@name Forward iterators
205 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has some features:
206 - it has no post-increment operator
207 - it iterates items in unordered fashion
209 The iterator interface:
213 // Default constructor
217 iterator( iterator const& src );
219 // Dereference operator
220 value_type * operator ->() const;
222 // Dereference operator
223 value_type& operator *() const;
225 // Preincrement operator
226 iterator& operator ++();
228 // Assignment operator
229 iterator& operator = (iterator const& src);
231 // Equality operators
232 bool operator ==(iterator const& i ) const;
233 bool operator !=(iterator const& i ) const;
237 typedef iterator_type< false > iterator;
239 /// Const forward iterator
240 typedef iterator_type< true > const_iterator;
242 /// Returns a forward iterator addressing the first element in a set
244 For empty set \code begin() == end() \endcode
248 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count());
251 /// Returns an iterator that addresses the location succeeding the last element in a set
253 Do not use the value returned by <tt>end</tt> function to access any item.
254 The returned value can be used only to control reaching the end of the set.
255 For empty set \code begin() == end() \endcode
259 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count());
262 /// Returns a forward const iterator addressing the first element in a set
263 const_iterator begin() const
265 return get_const_begin();
268 /// Returns a forward const iterator addressing the first element in a set
269 const_iterator cbegin() const
271 return get_const_begin();
274 /// Returns an const iterator that addresses the location succeeding the last element in a set
275 const_iterator end() const
277 return get_const_end();
280 /// Returns an const iterator that addresses the location succeeding the last element in a set
281 const_iterator cend() const
283 return get_const_end();
288 /// Initialize the map
290 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
291 when you create an object.
292 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
293 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
294 Note, that many popular STL hash map implementation uses load factor 1.
296 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
299 size_t nMaxItemCount, ///< estimation of max item count in the hash set
300 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
301 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
302 , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
304 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
305 construct_bucket<bucket_stat>( it );
308 /// Clears hash set and destroys it
312 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
313 it->~internal_bucket_type();
314 bucket_table_allocator().deallocate( m_Buckets, bucket_count());
317 /// Inserts new node with key and default value
319 The function creates a node with \p key and default value, and then inserts the node created into the map.
322 - The \ref key_type should be constructible from value of type \p K.
323 In trivial case, \p K is equal to \ref key_type.
324 - The \ref mapped_type should be default-constructible.
326 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
328 template <typename K>
329 iterator insert( const K& key )
331 internal_bucket_type& refBucket = bucket( key );
332 bucket_iterator it = refBucket.insert( key );
334 if ( it != refBucket.end()) {
336 return iterator( it, &refBucket, m_Buckets + bucket_count());
344 The function creates a node with copy of \p val value
345 and then inserts the node created into the map.
348 - The \ref key_type should be constructible from \p key of type \p K.
349 - The \ref mapped_type should be constructible from \p val of type \p V.
351 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
353 template <typename K, typename V>
354 iterator insert( K const& key, V const& val )
356 internal_bucket_type& refBucket = bucket( key );
357 bucket_iterator it = refBucket.insert( key, val );
359 if ( it != refBucket.end()) {
361 return iterator( it, &refBucket, m_Buckets + bucket_count());
367 /// Inserts new node and initialize it by a functor
369 This function inserts new node with key \p key and if inserting is successful then it calls
370 \p func functor with signature
373 void operator()( value_type& item );
377 The argument \p item of user-defined functor \p func is the reference
378 to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
380 The user-defined functor it is called only if the inserting is successful.
381 The \p key_type should be constructible from value of type \p K.
383 The function allows to split creating of new item into two part:
384 - create item from \p key;
385 - insert new item into the map;
386 - if inserting is successful, initialize the value of item by calling \p f functor
388 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
389 it is preferable that the initialization should be completed only if inserting is successful.
391 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
393 @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
394 \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
397 template <typename K, typename Func>
398 iterator insert_with( const K& key, Func func )
400 internal_bucket_type& refBucket = bucket( key );
401 bucket_iterator it = refBucket.insert_with( key, func );
403 if ( it != refBucket.end()) {
405 return iterator( it, &refBucket, m_Buckets + bucket_count());
411 /// For key \p key inserts data of type \p mapped_type created from \p args
413 \p key_type should be constructible from type \p K
415 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
417 template <typename K, typename... Args>
418 iterator emplace( K&& key, Args&&... args )
420 internal_bucket_type& refBucket = bucket( key );
421 bucket_iterator it = refBucket.emplace( std::forward<K>(key), std::forward<Args>(args)... );
423 if ( it != refBucket.end()) {
425 return iterator( it, &refBucket, m_Buckets + bucket_count());
433 If \p key is not in the map and \p bAllowInsert is \p true, the function inserts a new item.
434 Otherwise, the function returns an iterator pointing to the item found.
436 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
437 item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
439 \p second is true if new item has been added or \p false if the item
440 already is in the map.
442 @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
443 \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
446 template <typename K>
447 std::pair<iterator, bool> update( const K& key, bool bAllowInsert = true )
449 internal_bucket_type& refBucket = bucket( key );
450 std::pair<bucket_iterator, bool> ret = refBucket.update( key, bAllowInsert );
454 else if ( ret.first == refBucket.end())
455 return std::make_pair( end(), false );
456 return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count()), ret.second );
459 template <typename K>
460 CDS_DEPRECATED("ensure() is deprecated, use update()")
461 std::pair<iterator, bool> ensure( K const& key )
463 return update( key, true );
467 /// Checks whether the map contains \p key
469 The function searches the item with key equal to \p key
470 and returns an iterator pointed to item found and \ref end() otherwise
472 template <typename K>
473 iterator contains( K const& key )
475 internal_bucket_type& refBucket = bucket( key );
476 bucket_iterator it = refBucket.contains( key );
478 if ( it != refBucket.end())
479 return iterator( it, &refBucket, m_Buckets + bucket_count());
484 template <typename K>
485 CDS_DEPRECATED("deprecated, use contains()")
486 iterator find( K const& key )
488 return contains( key );
492 /// Checks whether the map contains \p key using \p pred predicate for searching
494 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
495 \p Less functor has the interface like \p std::less.
496 \p pred must imply the same element order as the comparator used for building the map.
497 Hash functor specified in \p Traits should accept parameters of type \p K.
499 template <typename K, typename Less>
500 iterator contains( K const& key, Less pred )
502 internal_bucket_type& refBucket = bucket( key );
503 bucket_iterator it = refBucket.contains( key, pred );
505 if ( it != refBucket.end())
506 return iterator( it, &refBucket, m_Buckets + bucket_count());
511 template <typename K, typename Less>
512 CDS_DEPRECATED("deprecated, use contains()")
513 iterator find_with( K const& key, Less pred )
515 return contains( key, pred );
519 /// Clears the map (not atomic)
522 for ( size_t i = 0; i < bucket_count(); ++i )
523 m_Buckets[i].clear();
524 m_ItemCounter.reset();
527 /// Checks whether the map is empty
529 @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
530 the function always returns \p true.
537 /// Returns item count in the map
539 If you use \p atomicity::empty_item_counter in \p traits::item_counter,
540 the function always returns 0.
544 return m_ItemCounter;
547 /// Returns const reference to internal statistics
548 stat const& statistics() const
553 /// Returns the size of hash table
555 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
556 the value returned is an constant depending on object initialization parameters;
557 see \p MichaelHashMap::MichaelHashMap for explanation.
559 size_t bucket_count() const
561 return m_nHashBitmask + 1;
566 /// Calculates hash value of \p key
567 template <typename K>
568 size_t hash_value( K const & key ) const
570 return m_HashFunctor( key ) & m_nHashBitmask;
573 /// Returns the bucket (ordered list) for \p key
574 template <typename K>
575 internal_bucket_type& bucket( K const& key )
577 return m_Buckets[hash_value( key )];
583 const_iterator get_const_begin() const
585 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count());
587 const_iterator get_const_end() const
589 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count());
592 template <typename Stat>
593 typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
595 new (bucket) internal_bucket_type;
598 template <typename Stat>
599 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
601 new (bucket) internal_bucket_type( m_Stat );
605 }} // namespace cds::container
607 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_NOGC_H