3 #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
4 #define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
6 #include <cds/intrusive/details/feldman_hashset_base.h>
7 #include <cds/container/details/base.h>
8 #include <cds/opt/hash.h>
10 namespace cds { namespace container {
11 /// \p FeldmanHashMap related definitions
12 /** @ingroup cds_nonintrusive_helper
14 namespace feldman_hashmap {
15 /// \p FeldmanHashMap internal statistics, see cds::intrusive::feldman_hashset::stat
16 template <typename EventCounter = cds::atomicity::event_counter>
17 using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
19 /// \p FeldmanHashMap empty internal statistics
20 typedef cds::intrusive::feldman_hashset::empty_stat empty_stat;
22 /// Bit-wise memcmp-based comparator for hash value \p T
24 using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
26 /// \p FeldmanHashMap level statistics
27 typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
29 /// \p FeldmanHashMap traits
32 /// Hash functor, default is \p opt::none
34 \p FeldmanHashMap may use any hash functor converting a key to
35 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
36 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
37 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
38 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
40 If you use a fixed-sized key you may use it directly instead of a hash.
41 In such case \p %traits::hash should be specified as \p opt::none.
42 However, if you want to use the hash values or if your key type is not fixed-sized
43 you must specify a proper hash functor in your traits.
45 fixed-sized key - IP4 address map
54 int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
56 return memcmp( &lhs, &rhs, sizeof(lhs));
60 // Value - statistics for the IP address
66 // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
67 struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
69 typedef ip4_cmp compare;
72 // IP4 address - statistics map
73 typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
76 variable-size key requires a hash functor: URL map
78 // Value - statistics for the URL
84 // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
85 // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
86 struct url_map_traits: public cds::container::multilevl_hashmap::traits
88 typedef std::hash<std::string> hash;
92 typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
95 typedef opt::none hash;
97 /// Hash comparing functor
99 @copydetails cds::intrusive::feldman_hashset::traits::compare
101 typedef cds::opt::none compare;
103 /// Specifies binary predicate used for hash compare.
105 @copydetails cds::intrusive::feldman_hashset::traits::less
107 typedef cds::opt::none less;
111 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
113 typedef cds::atomicity::item_counter item_counter;
117 Default is \ref CDS_DEFAULT_ALLOCATOR
119 typedef CDS_DEFAULT_ALLOCATOR allocator;
121 /// Array node allocator
123 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
125 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
127 /// C++ memory ordering model
129 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
131 typedef cds::opt::v::relaxed_ordering memory_model;
133 /// Back-off strategy
134 typedef cds::backoff::Default back_off;
136 /// Internal statistics
138 @copydetails cds::intrusive::feldman_hashset::traits::stat
140 typedef empty_stat stat;
142 /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
144 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
146 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
149 /// Metafunction converting option list to \p feldman_hashmap::traits
151 Supported \p Options are:
152 - \p opt::hash - a hash functor, default is \p std::hash
153 @copydetails traits::hash
154 - \p opt::allocator - item allocator
155 @copydetails traits::allocator
156 - \p opt::node_allocator - array node allocator.
157 @copydetails traits::node_allocator
158 - \p opt::compare - hash comparison functor. No default functor is provided.
159 If the option is not specified, the \p opt::less is used.
160 - \p opt::less - specifies binary predicate used for hash comparison.
161 @copydetails cds::container::feldman_hashmap::traits::less
162 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
163 - \p opt::item_counter - the type of item counting feature.
164 @copydetails cds::container::feldman_hashmap::traits::item_counter
165 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
166 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
167 - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
168 To enable it use \p feldman_hashmap::stat
169 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
170 Default is \p opt::v::rcu_throw_deadlock
172 template <typename... Options>
175 # ifdef CDS_DOXYGEN_INVOKED
176 typedef implementation_defined type ; ///< Metafunction result
178 typedef typename cds::opt::make_options<
179 typename cds::opt::find_type_traits< traits, Options... >::type
184 } // namespace feldman_hashmap
187 // Forward declaration
188 template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
189 class FeldmanHashMap;
195 template <typename Key, typename Value, typename Hash>
198 typedef Key key_type;
199 typedef Value mapped_type;
202 typedef typename std::decay<
203 typename std::remove_reference<
204 decltype(hasher()(std::declval<key_type>()))
210 std::pair< key_type const, mapped_type> m_Value;
211 hash_type const m_hash;
213 node_type() = delete;
214 node_type(node_type const&) = delete;
216 template <typename Q>
217 node_type(hasher& h, Q const& key)
218 : m_Value(std::move(std::make_pair(key, mapped_type())))
219 , m_hash(h(m_Value.first))
222 template <typename Q, typename U >
223 node_type(hasher& h, Q const& key, U const& val)
224 : m_Value(std::move(std::make_pair(key, mapped_type(val))))
225 , m_hash(h(m_Value.first))
228 template <typename Q, typename... Args>
229 node_type(hasher& h, Q&& key, Args&&... args)
230 : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
231 , m_hash(h(m_Value.first))
237 hash_type const& operator()(node_type const& node) const
244 template <typename Key, typename Value>
245 struct hash_selector<Key, Value, opt::none>
247 typedef Key key_type;
248 typedef Value mapped_type;
251 key_type const& operator()(key_type const& k) const
256 typedef key_type hash_type;
260 std::pair< key_type const, mapped_type> m_Value;
262 node_type() = delete;
263 node_type(node_type const&) = delete;
265 template <typename Q>
266 node_type(hasher /*h*/, Q const& key)
267 : m_Value(std::move(std::make_pair(key, mapped_type())))
270 template <typename Q, typename U >
271 node_type(hasher /*h*/, Q const& key, U const& val)
272 : m_Value(std::move(std::make_pair(key, mapped_type(val))))
275 template <typename Q, typename... Args>
276 node_type(hasher /*h*/, Q&& key, Args&&... args)
277 : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
283 hash_type const& operator()(node_type const& node) const
285 return node.m_Value.first;
290 template <typename GC, typename Key, typename T, typename Traits>
291 struct make_feldman_hashmap
294 typedef Key key_type;
295 typedef T mapped_type;
296 typedef Traits original_traits;
299 typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
300 typedef typename select::hasher hasher;
301 typedef typename select::hash_type hash_type;
302 typedef typename select::node_type node_type;
304 typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
308 void operator()( node_type * p ) const
310 cxx_node_allocator().Delete( p );
314 struct intrusive_traits: public original_traits
316 typedef typename select::hash_accessor hash_accessor;
317 typedef node_disposer disposer;
320 // Metafunction result
321 typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
323 } // namespace details
326 }} // namespace cds::container
328 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H