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_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 >;
64 /// Hash splitter option
66 @copydetails cds::container::feldman_hashmap::traits::hash_splitter
68 template <typename Splitter>
69 using hash_splitter = cds::intrusive::feldman_hashset::hash_splitter< Splitter >;
72 /// \p FeldmanHashMap traits
75 /// Hash functor, default is \p opt::none
77 \p FeldmanHashMap may use any hash functor converting a key to
78 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
79 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
80 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
81 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
83 If you use a fixed-sized key you can use it directly instead of a hash.
84 In such case \p %traits::hash should be specified as \p opt::none.
85 However, if you want to use the hash values or if your key type is not fixed-sized
86 you must specify a proper hash functor in your traits.
88 fixed-sized key - IP4 address map
97 int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
99 return memcmp( &lhs, &rhs, sizeof(lhs));
103 // Value - statistics for the IP address
109 // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
110 struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
112 typedef ip4_cmp compare;
115 // IP4 address - statistics map
116 typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
119 variable-size key requires a hash functor: URL map
121 // Value - statistics for the URL
127 // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
128 // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
129 struct url_map_traits: public cds::container::multilevl_hashmap::traits
131 typedef std::hash<std::string> hash;
134 // URL statistics map
135 typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
138 typedef opt::none hash;
140 /// The size of hash value in bytes
142 By default, the size of hash value is <tt>sizeof( hash_type )</tt>
143 where \p hash_type is type of \p hash() result or <tt>sizeof( key )</tt> if you use fixed-sized key.
145 Sometimes that size is wrong, for example, for that 6-byte key:
152 static_assert( sizeof( key_type ) == 6, "Key type size mismatch" );
154 Here <tt>sizeof( key_type ) == 8</tt> so \p static_assert will be thrown.
156 For that case you can specify \p hash_size explicitly.
158 Value \p 0 means auto-calculated <tt>sizeof( key_type )</tt>.
160 static CDS_CONSTEXPR size_t const hash_size = 0;
164 @copydetails cds::intrusive::feldman_hashset::traits::hash_splitter
166 typedef cds::opt::none hash_splitter;
168 /// Hash comparing functor
170 @copydetails cds::intrusive::feldman_hashset::traits::compare
172 typedef cds::opt::none compare;
174 /// Specifies binary predicate used for hash compare.
176 @copydetails cds::intrusive::feldman_hashset::traits::less
178 typedef cds::opt::none less;
182 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
184 typedef cds::atomicity::item_counter item_counter;
188 Default is \ref CDS_DEFAULT_ALLOCATOR
190 typedef CDS_DEFAULT_ALLOCATOR allocator;
192 /// Array node allocator
194 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
196 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
198 /// C++ memory ordering model
200 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
202 typedef cds::opt::v::relaxed_ordering memory_model;
204 /// Back-off strategy
205 typedef cds::backoff::Default back_off;
207 /// Internal statistics
209 @copydetails cds::intrusive::feldman_hashset::traits::stat
211 typedef empty_stat stat;
213 /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
215 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
217 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
220 /// Metafunction converting option list to \p feldman_hashmap::traits
222 Supported \p Options are:
223 - \p opt::hash - a hash functor, default is \p std::hash
224 @copydetails traits::hash
225 - \p feldman_hashmap::hash_size - the size of hash value in bytes.
226 @copydetails traits::hash_size
227 - \p opt::allocator - item allocator
228 @copydetails traits::allocator
229 - \p opt::node_allocator - array node allocator.
230 @copydetails traits::node_allocator
231 - \p opt::compare - hash comparison functor. No default functor is provided.
232 If the option is not specified, the \p opt::less is used.
233 - \p opt::less - specifies binary predicate used for hash comparison.
234 @copydetails cds::container::feldman_hashmap::traits::less
235 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
236 - \p opt::item_counter - the type of item counting feature.
237 @copydetails cds::container::feldman_hashmap::traits::item_counter
238 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
239 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
240 - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
241 To enable it use \p feldman_hashmap::stat
242 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
243 Default is \p opt::v::rcu_throw_deadlock
245 template <typename... Options>
248 # ifdef CDS_DOXYGEN_INVOKED
249 typedef implementation_defined type ; ///< Metafunction result
251 typedef typename cds::opt::make_options<
252 typename cds::opt::find_type_traits< traits, Options... >::type
257 } // namespace feldman_hashmap
260 // Forward declaration
261 template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
262 class FeldmanHashMap;
268 template <typename Key, typename Value, typename Hash>
271 typedef Key key_type;
272 typedef Value mapped_type;
275 typedef typename std::decay<
276 typename std::remove_reference<
277 decltype(hasher()(std::declval<key_type>()))
283 std::pair< key_type const, mapped_type> m_Value;
284 hash_type const m_hash;
286 node_type() = delete;
287 node_type(node_type const&) = delete;
289 template <typename Q>
290 node_type(hasher& h, Q const& key)
291 : m_Value( std::move( std::make_pair( key_type( key ), mapped_type())))
292 , m_hash( h( m_Value.first ))
295 template <typename Q, typename U >
296 node_type(hasher& h, Q const& key, U const& val)
297 : m_Value( std::move( std::make_pair( key_type( key ), mapped_type(val))))
298 , m_hash( h( m_Value.first ))
301 template <typename Q, typename... Args>
302 node_type(hasher& h, Q&& key, Args&&... args)
303 : m_Value( std::move(std::make_pair( key_type( std::forward<Q>(key)), std::move( mapped_type(std::forward<Args>(args)...)))))
304 , m_hash( h( m_Value.first ))
310 hash_type const& operator()(node_type const& node) const
317 template <typename Key, typename Value>
318 struct hash_selector<Key, Value, opt::none>
320 typedef Key key_type;
321 typedef Value mapped_type;
324 key_type const& operator()(key_type const& k) const
329 typedef key_type hash_type;
333 std::pair< key_type const, mapped_type> m_Value;
335 node_type() = delete;
336 node_type(node_type const&) = delete;
338 template <typename Q, typename... Args>
339 node_type( hasher /*h*/, Q&& key, Args&&... args )
340 : m_Value( std::make_pair( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>(args)...)))
346 hash_type const& operator()(node_type const& node) const
348 return node.m_Value.first;
353 template <typename GC, typename Key, typename T, typename Traits>
354 struct make_feldman_hashmap
357 typedef Key key_type;
358 typedef T mapped_type;
359 typedef Traits original_traits;
362 typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
363 typedef typename select::hasher hasher;
364 typedef typename select::hash_type hash_type;
365 typedef typename select::node_type node_type;
367 typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
371 void operator()( node_type * p ) const
373 cxx_node_allocator().Delete( p );
377 struct intrusive_traits: public original_traits
379 typedef typename select::hash_accessor hash_accessor;
380 typedef node_disposer disposer;
383 // Metafunction result
384 typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
386 } // namespace details
389 }} // namespace cds::container
391 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H