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_DETAILS_FELDMAN_HASHMAP_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
34 #include <cds/intrusive/details/feldman_hashset_base.h>
35 #include <cds/container/details/base.h>
36 #include <cds/opt/hash.h>
38 namespace cds { namespace container {
39 /// \p FeldmanHashMap related definitions
40 /** @ingroup cds_nonintrusive_helper
42 namespace feldman_hashmap {
43 /// \p FeldmanHashMap internal statistics, see cds::intrusive::feldman_hashset::stat
44 template <typename EventCounter = cds::atomicity::event_counter>
45 using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
47 /// \p FeldmanHashMap empty internal statistics
48 typedef cds::intrusive::feldman_hashset::empty_stat empty_stat;
50 /// Bit-wise memcmp-based comparator for hash value \p T
52 using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
54 /// \p FeldmanHashMap level statistics
55 typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
59 @copydetails cds::container::feldman_hashmap::traits::hash_size
61 template <size_t Size>
62 using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >;
65 /// \p FeldmanHashMap traits
68 /// Hash functor, default is \p opt::none
70 \p FeldmanHashMap may use any hash functor converting a key to
71 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
72 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
73 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
74 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
76 If you use a fixed-sized key you can use it directly instead of a hash.
77 In such case \p %traits::hash should be specified as \p opt::none.
78 However, if you want to use the hash values or if your key type is not fixed-sized
79 you must specify a proper hash functor in your traits.
81 fixed-sized key - IP4 address map
90 int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
92 return memcmp( &lhs, &rhs, sizeof(lhs));
96 // Value - statistics for the IP address
102 // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
103 struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
105 typedef ip4_cmp compare;
108 // IP4 address - statistics map
109 typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
112 variable-size key requires a hash functor: URL map
114 // Value - statistics for the URL
120 // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
121 // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
122 struct url_map_traits: public cds::container::multilevl_hashmap::traits
124 typedef std::hash<std::string> hash;
127 // URL statistics map
128 typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
131 typedef opt::none hash;
133 /// The size of hash value in bytes
135 By default, the size of hash value is <tt>sizeof( hash_type )</tt>
136 where \p hash_type is type of \p hash() result or <tt>sizeof( key )</tt> if you use fixed-sized key.
138 Sometimes that size is wrong, for example, for that 6-byte key:
145 static_assert( sizeof( key_type ) == 6, "Key type size mismatch" );
147 Here <tt>sizeof( key_type ) == 8</tt> so \p static_assert will be thrown.
149 For that case you can specify \p hash_size explicitly.
151 Value \p 0 means auto-calculated <tt>sizeof( key_type )</tt>.
157 /// Hash comparing functor
159 @copydetails cds::intrusive::feldman_hashset::traits::compare
161 typedef cds::opt::none compare;
163 /// Specifies binary predicate used for hash compare.
165 @copydetails cds::intrusive::feldman_hashset::traits::less
167 typedef cds::opt::none less;
171 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
173 typedef cds::atomicity::item_counter item_counter;
177 Default is \ref CDS_DEFAULT_ALLOCATOR
179 typedef CDS_DEFAULT_ALLOCATOR allocator;
181 /// Array node allocator
183 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
185 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
187 /// C++ memory ordering model
189 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
191 typedef cds::opt::v::relaxed_ordering memory_model;
193 /// Back-off strategy
194 typedef cds::backoff::Default back_off;
196 /// Internal statistics
198 @copydetails cds::intrusive::feldman_hashset::traits::stat
200 typedef empty_stat stat;
202 /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
204 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
206 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
209 /// Metafunction converting option list to \p feldman_hashmap::traits
211 Supported \p Options are:
212 - \p opt::hash - a hash functor, default is \p std::hash
213 @copydetails traits::hash
214 - \p feldman_hashmap::hash_size - the size of hash value in bytes.
215 @copydetails traits::hash_size
216 - \p opt::allocator - item allocator
217 @copydetails traits::allocator
218 - \p opt::node_allocator - array node allocator.
219 @copydetails traits::node_allocator
220 - \p opt::compare - hash comparison functor. No default functor is provided.
221 If the option is not specified, the \p opt::less is used.
222 - \p opt::less - specifies binary predicate used for hash comparison.
223 @copydetails cds::container::feldman_hashmap::traits::less
224 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
225 - \p opt::item_counter - the type of item counting feature.
226 @copydetails cds::container::feldman_hashmap::traits::item_counter
227 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
228 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
229 - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
230 To enable it use \p feldman_hashmap::stat
231 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
232 Default is \p opt::v::rcu_throw_deadlock
234 template <typename... Options>
237 # ifdef CDS_DOXYGEN_INVOKED
238 typedef implementation_defined type ; ///< Metafunction result
240 typedef typename cds::opt::make_options<
241 typename cds::opt::find_type_traits< traits, Options... >::type
246 } // namespace feldman_hashmap
249 // Forward declaration
250 template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
251 class FeldmanHashMap;
257 template <typename Key, typename Value, typename Hash>
260 typedef Key key_type;
261 typedef Value mapped_type;
264 typedef typename std::decay<
265 typename std::remove_reference<
266 decltype(hasher()(std::declval<key_type>()))
272 std::pair< key_type const, mapped_type> m_Value;
273 hash_type const m_hash;
275 node_type() = delete;
276 node_type(node_type const&) = delete;
278 template <typename Q>
279 node_type(hasher& h, Q const& key)
280 : m_Value(std::move(std::make_pair(key, mapped_type())))
281 , m_hash(h(m_Value.first))
284 template <typename Q, typename U >
285 node_type(hasher& h, Q const& key, U const& val)
286 : m_Value(std::move(std::make_pair(key, mapped_type(val))))
287 , m_hash(h(m_Value.first))
290 template <typename Q, typename... Args>
291 node_type(hasher& h, Q&& key, Args&&... args)
292 : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
293 , m_hash(h(m_Value.first))
299 hash_type const& operator()(node_type const& node) const
306 template <typename Key, typename Value>
307 struct hash_selector<Key, Value, opt::none>
309 typedef Key key_type;
310 typedef Value mapped_type;
313 key_type const& operator()(key_type const& k) const
318 typedef key_type hash_type;
322 std::pair< key_type const, mapped_type> m_Value;
324 node_type() = delete;
325 node_type(node_type const&) = delete;
327 template <typename Q, typename... Args>
328 node_type( hasher /*h*/, Q&& key, Args&&... args )
329 : m_Value( std::make_pair( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>(args)...)))
335 hash_type const& operator()(node_type const& node) const
337 return node.m_Value.first;
342 template <typename GC, typename Key, typename T, typename Traits>
343 struct make_feldman_hashmap
346 typedef Key key_type;
347 typedef T mapped_type;
348 typedef Traits original_traits;
351 typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
352 typedef typename select::hasher hasher;
353 typedef typename select::hash_type hash_type;
354 typedef typename select::node_type node_type;
356 typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
360 void operator()( node_type * p ) const
362 cxx_node_allocator().Delete( p );
366 struct intrusive_traits: public original_traits
368 typedef typename select::hash_accessor hash_accessor;
369 typedef node_disposer disposer;
372 // Metafunction result
373 typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
375 } // namespace details
378 }} // namespace cds::container
380 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H