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_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 bucket_type; ///< type of ordered list used as a bucket implementation
62 typedef Traits traits; ///< Map traits
64 typedef typename bucket_type::key_type key_type; ///< key type
65 typedef typename bucket_type::mapped_type mapped_type; ///< type of value to be stored in the map
66 typedef typename bucket_type::value_type value_type; ///< Pair used as the some functor's argument
68 typedef typename bucket_type::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
74 /// Bucket table allocator
75 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
79 typedef typename bucket_type::iterator bucket_iterator;
80 typedef typename bucket_type::const_iterator bucket_const_iterator;
84 item_counter m_ItemCounter; ///< Item counter
85 hash m_HashFunctor; ///< Hash functor
86 bucket_type * m_Buckets; ///< bucket table
90 const size_t m_nHashBitmask;
95 /// Calculates hash value of \p key
97 size_t hash_value( K const & key ) const
99 return m_HashFunctor( key ) & m_nHashBitmask;
102 /// Returns the bucket (ordered list) for \p key
103 template <typename K>
104 bucket_type& bucket( K const& key )
106 return m_Buckets[ hash_value( key ) ];
112 template <bool IsConst>
113 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
115 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
116 friend class MichaelHashMap;
119 typedef typename base_class::bucket_ptr bucket_ptr;
120 typedef typename base_class::list_iterator list_iterator;
123 /// Value pointer type (const for const_iterator)
124 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
125 /// Value reference type (const for const_iterator)
126 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
128 /// Key-value pair pointer type (const for const_iterator)
129 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
130 /// Key-value pair reference type (const for const_iterator)
131 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
134 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
135 : base_class( it, pFirst, pLast )
145 iterator_type( const iterator_type& src )
149 /// Dereference operator
150 pair_ptr operator ->() const
152 assert( base_class::m_pCurBucket != nullptr );
153 return base_class::m_itList.operator ->();
156 /// Dereference operator
157 pair_ref operator *() const
159 assert( base_class::m_pCurBucket != nullptr );
160 return base_class::m_itList.operator *();
164 iterator_type& operator ++()
166 base_class::operator++();
170 /// Assignment operator
171 iterator_type& operator = (const iterator_type& src)
173 base_class::operator =(src);
177 /// Returns current bucket (debug function)
178 bucket_ptr bucket() const
180 return base_class::bucket();
183 /// Equality operator
185 bool operator ==(iterator_type<C> const& i ) const
187 return base_class::operator ==( i );
189 /// Equality operator
191 bool operator !=(iterator_type<C> const& i ) const
193 return !( *this == i );
199 ///@name Forward iterators
203 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has some features:
204 - it has no post-increment operator
205 - it iterates items in unordered fashion
207 The iterator interface:
211 // Default constructor
215 iterator( iterator const& src );
217 // Dereference operator
218 value_type * operator ->() const;
220 // Dereference operator
221 value_type& operator *() const;
223 // Preincrement operator
224 iterator& operator ++();
226 // Assignment operator
227 iterator& operator = (iterator const& src);
229 // Equality operators
230 bool operator ==(iterator const& i ) const;
231 bool operator !=(iterator const& i ) const;
235 typedef iterator_type< false > iterator;
237 /// Const forward iterator
238 typedef iterator_type< true > const_iterator;
240 /// Returns a forward iterator addressing the first element in a set
242 For empty set \code begin() == end() \endcode
246 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
249 /// Returns an iterator that addresses the location succeeding the last element in a set
251 Do not use the value returned by <tt>end</tt> function to access any item.
252 The returned value can be used only to control reaching the end of the set.
253 For empty set \code begin() == end() \endcode
257 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
260 /// Returns a forward const iterator addressing the first element in a set
261 const_iterator begin() const
263 return get_const_begin();
266 /// Returns a forward const iterator addressing the first element in a set
267 const_iterator cbegin() const
269 return get_const_begin();
272 /// Returns an const iterator that addresses the location succeeding the last element in a set
273 const_iterator end() const
275 return get_const_end();
278 /// Returns an const iterator that addresses the location succeeding the last element in a set
279 const_iterator cend() const
281 return get_const_end();
287 const_iterator get_const_begin() const
289 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
291 const_iterator get_const_end() const
293 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
298 /// Initialize the map
300 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
301 when you create an object.
302 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
303 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
304 Note, that many popular STL hash map implementation uses load factor 1.
306 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
309 size_t nMaxItemCount, ///< estimation of max item count in the hash set
310 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
311 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
313 // GC and OrderedList::gc must be the same
314 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
316 // atomicity::empty_item_counter is not allowed as a item counter
317 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
318 "cds::atomicity::empty_item_counter is not allowed as a item counter");
320 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
323 /// Clears hash set and destroys it
327 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
330 /// Inserts new node with key and default value
332 The function creates a node with \p key and default value, and then inserts the node created into the map.
335 - The \ref key_type should be constructible from value of type \p K.
336 In trivial case, \p K is equal to \ref key_type.
337 - The \ref mapped_type should be default-constructible.
339 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
341 template <typename K>
342 iterator insert( const K& key )
344 bucket_type& refBucket = bucket( key );
345 bucket_iterator it = refBucket.insert( key );
347 if ( it != refBucket.end() ) {
349 return iterator( it, &refBucket, m_Buckets + bucket_count() );
357 The function creates a node with copy of \p val value
358 and then inserts the node created into the map.
361 - The \ref key_type should be constructible from \p key of type \p K.
362 - The \ref mapped_type should be constructible from \p val of type \p V.
364 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
366 template <typename K, typename V>
367 iterator insert( K const& key, V const& val )
369 bucket_type& refBucket = bucket( key );
370 bucket_iterator it = refBucket.insert( key, val );
372 if ( it != refBucket.end() ) {
374 return iterator( it, &refBucket, m_Buckets + bucket_count() );
380 /// Inserts new node and initialize it by a functor
382 This function inserts new node with key \p key and if inserting is successful then it calls
383 \p func functor with signature
386 void operator()( value_type& item );
390 The argument \p item of user-defined functor \p func is the reference
391 to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
393 The user-defined functor it is called only if the inserting is successful.
394 The \p key_type should be constructible from value of type \p K.
396 The function allows to split creating of new item into two part:
397 - create item from \p key;
398 - insert new item into the map;
399 - if inserting is successful, initialize the value of item by calling \p f functor
401 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
402 it is preferable that the initialization should be completed only if inserting is successful.
404 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
406 @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
407 \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
410 template <typename K, typename Func>
411 iterator insert_with( const K& key, Func func )
413 bucket_type& refBucket = bucket( key );
414 bucket_iterator it = refBucket.insert_with( key, func );
416 if ( it != refBucket.end() ) {
418 return iterator( it, &refBucket, m_Buckets + bucket_count() );
424 /// For key \p key inserts data of type \p mapped_type created from \p args
426 \p key_type should be constructible from type \p K
428 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
430 template <typename K, typename... Args>
431 iterator emplace( K&& key, Args&&... args )
433 bucket_type& refBucket = bucket( key );
434 bucket_iterator it = refBucket.emplace( std::forward<K>(key), std::forward<Args>(args)... );
436 if ( it != refBucket.end() ) {
438 return iterator( it, &refBucket, m_Buckets + bucket_count() );
446 If \p key is not in the map and \p bAllowInsert is \p true, the function inserts a new item.
447 Otherwise, the function returns an iterator pointing to the item found.
449 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
450 item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
452 \p second is true if new item has been added or \p false if the item
453 already is in the map.
455 @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
456 \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
459 template <typename K>
460 std::pair<iterator, bool> update( const K& key, bool bAllowInsert = true )
462 bucket_type& refBucket = bucket( key );
463 std::pair<bucket_iterator, bool> ret = refBucket.update( key, bAllowInsert );
467 else if ( ret.first == refBucket.end() )
468 return std::make_pair( end(), false );
469 return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
472 template <typename K>
473 CDS_DEPRECATED("ensure() is deprecated, use update()")
474 std::pair<iterator, bool> ensure( K const& key )
476 return update( key, true );
480 /// Checks whether the map contains \p key
482 The function searches the item with key equal to \p key
483 and returns an iterator pointed to item found and \ref end() otherwise
485 template <typename K>
486 iterator contains( K const& key )
488 bucket_type& refBucket = bucket( key );
489 bucket_iterator it = refBucket.contains( key );
491 if ( it != refBucket.end() )
492 return iterator( it, &refBucket, m_Buckets + bucket_count() );
497 template <typename K>
498 CDS_DEPRECATED("deprecated, use contains()")
499 iterator find( K const& key )
501 return contains( key );
505 /// Checks whether the map contains \p key using \p pred predicate for searching
507 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
508 \p Less functor has the interface like \p std::less.
509 \p pred must imply the same element order as the comparator used for building the map.
510 Hash functor specified in \p Traits should accept parameters of type \p K.
512 template <typename K, typename Less>
513 iterator contains( K const& key, Less pred )
515 bucket_type& refBucket = bucket( key );
516 bucket_iterator it = refBucket.contains( key, pred );
518 if ( it != refBucket.end() )
519 return iterator( it, &refBucket, m_Buckets + bucket_count() );
524 template <typename K, typename Less>
525 CDS_DEPRECATED("deprecated, use contains()")
526 iterator find_with( K const& key, Less pred )
528 return contains( key, pred );
532 /// Clears the map (not atomic)
535 for ( size_t i = 0; i < bucket_count(); ++i )
536 m_Buckets[i].clear();
537 m_ItemCounter.reset();
540 /// Checks whether the map is empty
542 Emptiness is checked by item counting: if item count is zero then the map is empty.
543 Thus, the correct item counting feature is an important part of Michael's map implementation.
550 /// Returns item count in the map
553 return m_ItemCounter;
556 /// Returns the size of hash table
558 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
559 the value returned is an constant depending on object initialization parameters;
560 see \p MichaelHashMap::MichaelHashMap for explanation.
562 size_t bucket_count() const
564 return m_nHashBitmask + 1;
567 }} // namespace cds::container
569 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_NOGC_H