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>.
153 static CDS_CONSTEXPR size_t const hash_size = 0;
155 /// Hash comparing functor
157 @copydetails cds::intrusive::feldman_hashset::traits::compare
159 typedef cds::opt::none compare;
161 /// Specifies binary predicate used for hash compare.
163 @copydetails cds::intrusive::feldman_hashset::traits::less
165 typedef cds::opt::none less;
169 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
171 typedef cds::atomicity::item_counter item_counter;
175 Default is \ref CDS_DEFAULT_ALLOCATOR
177 typedef CDS_DEFAULT_ALLOCATOR allocator;
179 /// Array node allocator
181 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
183 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
185 /// C++ memory ordering model
187 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
189 typedef cds::opt::v::relaxed_ordering memory_model;
191 /// Back-off strategy
192 typedef cds::backoff::Default back_off;
194 /// Internal statistics
196 @copydetails cds::intrusive::feldman_hashset::traits::stat
198 typedef empty_stat stat;
200 /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
202 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
204 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
207 /// Metafunction converting option list to \p feldman_hashmap::traits
209 Supported \p Options are:
210 - \p opt::hash - a hash functor, default is \p std::hash
211 @copydetails traits::hash
212 - \p feldman_hashmap::hash_size - the size of hash value in bytes.
213 @copydetails traits::hash_size
214 - \p opt::allocator - item allocator
215 @copydetails traits::allocator
216 - \p opt::node_allocator - array node allocator.
217 @copydetails traits::node_allocator
218 - \p opt::compare - hash comparison functor. No default functor is provided.
219 If the option is not specified, the \p opt::less is used.
220 - \p opt::less - specifies binary predicate used for hash comparison.
221 @copydetails cds::container::feldman_hashmap::traits::less
222 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
223 - \p opt::item_counter - the type of item counting feature.
224 @copydetails cds::container::feldman_hashmap::traits::item_counter
225 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
226 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
227 - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
228 To enable it use \p feldman_hashmap::stat
229 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
230 Default is \p opt::v::rcu_throw_deadlock
232 template <typename... Options>
235 # ifdef CDS_DOXYGEN_INVOKED
236 typedef implementation_defined type ; ///< Metafunction result
238 typedef typename cds::opt::make_options<
239 typename cds::opt::find_type_traits< traits, Options... >::type
244 } // namespace feldman_hashmap
247 // Forward declaration
248 template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
249 class FeldmanHashMap;
255 template <typename Key, typename Value, typename Hash>
258 typedef Key key_type;
259 typedef Value mapped_type;
262 typedef typename std::decay<
263 typename std::remove_reference<
264 decltype(hasher()(std::declval<key_type>()))
270 std::pair< key_type const, mapped_type> m_Value;
271 hash_type const m_hash;
273 node_type() = delete;
274 node_type(node_type const&) = delete;
276 template <typename Q>
277 node_type(hasher& h, Q const& key)
278 : m_Value( std::move( std::make_pair( key_type( key ), mapped_type())))
279 , m_hash( h( m_Value.first ))
282 template <typename Q, typename U >
283 node_type(hasher& h, Q const& key, U const& val)
284 : m_Value( std::move( std::make_pair( key_type( key ), mapped_type(val))))
285 , m_hash( h( m_Value.first ))
288 template <typename Q, typename... Args>
289 node_type(hasher& h, Q&& key, Args&&... args)
290 : m_Value( std::move(std::make_pair( key_type( std::forward<Q>(key)), std::move( mapped_type(std::forward<Args>(args)...)))))
291 , m_hash( h( m_Value.first ))
297 hash_type const& operator()(node_type const& node) const
304 template <typename Key, typename Value>
305 struct hash_selector<Key, Value, opt::none>
307 typedef Key key_type;
308 typedef Value mapped_type;
311 key_type const& operator()(key_type const& k) const
316 typedef key_type hash_type;
320 std::pair< key_type const, mapped_type> m_Value;
322 node_type() = delete;
323 node_type(node_type const&) = delete;
325 template <typename Q, typename... Args>
326 node_type( hasher /*h*/, Q&& key, Args&&... args )
327 : m_Value( std::make_pair( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>(args)...)))
333 hash_type const& operator()(node_type const& node) const
335 return node.m_Value.first;
340 template <typename GC, typename Key, typename T, typename Traits>
341 struct make_feldman_hashmap
344 typedef Key key_type;
345 typedef T mapped_type;
346 typedef Traits original_traits;
349 typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
350 typedef typename select::hasher hasher;
351 typedef typename select::hash_type hash_type;
352 typedef typename select::node_type node_type;
354 typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
358 void operator()( node_type * p ) const
360 cxx_node_allocator().Delete( p );
364 struct intrusive_traits: public original_traits
366 typedef typename select::hash_accessor hash_accessor;
367 typedef node_disposer disposer;
370 // Metafunction result
371 typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
373 } // namespace details
376 }} // namespace cds::container
378 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H