ModErn Text Analysis
META Enumerates Textual Applications
hash.h
Go to the documentation of this file.
1 
10 #ifndef META_HASHING_HASH_H_
11 #define META_HASHING_HASH_H_
12 
13 #include <array>
14 #include <cassert>
15 #include <cstdint>
16 #include <random>
17 
18 #include "hashes/farm_hash.h"
19 #include "hashes/metro_hash.h"
20 #include "hashes/murmur_hash.h"
21 #include "meta/config.h"
22 
23 namespace meta
24 {
25 namespace hashing
26 {
27 
28 template <std::size_t Size = sizeof(std::size_t)>
30 
31 template <>
32 struct default_hasher<4>
33 {
34  using type = murmur_hash<4>;
35 };
36 
37 template <>
38 struct default_hasher<8>
39 {
40  using type = farm_hash_seeded;
41 };
42 
43 namespace detail
44 {
45 template <bool...>
46 struct static_and;
47 
48 template <bool B, bool... Bs>
49 struct static_and<B, Bs...>
50 {
51  const static constexpr bool value = B && static_and<Bs...>::value;
52 };
53 
54 template <>
55 struct static_and<>
56 {
57  const static constexpr bool value = true;
58 };
59 
60 template <std::size_t...>
61 struct static_add;
62 
63 template <std::size_t Size, std::size_t... Sizes>
64 struct static_add<Size, Sizes...>
65 {
66  const static constexpr std::size_t value
67  = Size + static_add<Sizes...>::value;
68 };
69 
70 template <>
71 struct static_add<>
72 {
73  const static constexpr std::size_t value = 0;
74 };
75 }
76 
77 template <class T>
79 {
80  const static constexpr bool value = std::is_integral<T>::value
81  || std::is_enum<T>::value
82  || std::is_pointer<T>::value;
83 };
84 
85 template <class T>
87 {
88 };
89 
90 template <class T>
91 struct is_contiguously_hashable<const volatile T>
92  : public is_contiguously_hashable<T>
93 {
94 };
95 
96 template <class T, std::size_t N>
98 {
99 };
100 
101 template <class T, class U>
102 struct is_contiguously_hashable<std::pair<T, U>>
103 {
104  const static constexpr bool value
107  && sizeof(T) + sizeof(U) == sizeof(std::pair<T, U>);
108 };
109 
110 template <class... Ts>
111 struct is_contiguously_hashable<std::tuple<Ts...>>
112 {
113  const static constexpr bool value
115  && detail::static_add<sizeof(Ts)...>::value
116  == sizeof(std::tuple<Ts...>);
117 };
118 
119 template <class T, std::size_t N>
120 struct is_contiguously_hashable<std::array<T, N>>
121 {
122  const static constexpr bool value
124  && sizeof(T) * N == sizeof(std::array<T, N>);
125 };
126 
127 template <class HashAlgorithm, class T>
128 inline typename std::enable_if<is_contiguously_hashable<T>::value>::type
129 hash_append(HashAlgorithm& h, const T& t)
130 {
131  h(std::addressof(t), sizeof(t));
132 }
133 
134 template <class HashAlgorithm, class T>
135 inline typename std::enable_if<std::is_floating_point<T>::value>::type
136 hash_append(HashAlgorithm& h, T t)
137 {
138  // -0 and 0 are the same, but have different bit patterns, so normalize
139  // to positive zero before hashing
140  if (t == 0)
141  t = 0;
142  h(std::addressof(t), sizeof(t));
143 }
144 
145 template <class HashAlgorithm>
146 inline void hash_append(HashAlgorithm& h, std::nullptr_t)
147 {
148  const void* p = nullptr;
149  h(std::addressof(p), sizeof(p));
150 }
151 
152 // all of these hash_appends below need to be forward declared so they can
153 // find one another in their implementations
154 
155 template <class HashAlgorithm, class T, std::size_t N>
156 typename std::enable_if<!is_contiguously_hashable<T>::value>::type
157 hash_append(HashAlgorithm& h, T (&a)[N]);
158 
159 template <class HashAlgorithm, class T, class U>
160 typename std::enable_if<!is_contiguously_hashable<std::pair<T, U>>::value>::type
161 hash_append(HashAlgorithm& h, const std::pair<T, U>& p);
162 
163 template <class HashAlgorithm, class... Ts>
164 typename std::enable_if<!is_contiguously_hashable<std::tuple<Ts...>>::value>::
165  type
166  hash_append(HashAlgorithm& h, const std::tuple<Ts...>& t);
167 
168 template <class HashAlgorithm, class T, std::size_t N>
169 typename std::enable_if<!is_contiguously_hashable<std::array<T, N>>::value>::
170  type
171  hash_append(HashAlgorithm& h, const std::array<T, N>& a);
172 
173 template <class HashAlgorithm, class Char, class Traits, class Alloc>
174 typename std::enable_if<is_contiguously_hashable<Char>::value>::type
175 hash_append(HashAlgorithm& h, const std::basic_string<Char, Traits, Alloc>& s);
176 
177 template <class HashAlgorithm, class Char, class Traits, class Alloc>
178 typename std::enable_if<!is_contiguously_hashable<Char>::value>::type
179 hash_append(HashAlgorithm& h, const std::basic_string<Char, Traits, Alloc>& s);
180 
181 template <class HashAlgorithm, class T1, class T2, class... Ts>
182 void hash_append(HashAlgorithm& h, const T1& first, const T2& second,
183  const Ts&... ts);
184 
185 template <class HashAlgorithm, class T, class Alloc>
186 typename std::enable_if<is_contiguously_hashable<T>::value>::type
187 hash_append(HashAlgorithm& h, const std::vector<T, Alloc>& v);
188 
189 template <class HashAlgorithm, class T, class Alloc>
190 typename std::enable_if<!is_contiguously_hashable<T>::value>::type
191 hash_append(HashAlgorithm& h, const std::vector<T, Alloc>& v);
192 
193 // begin implementations for hash_append
194 
195 template <class HashAlgorithm, class T, std::size_t N>
196 typename std::enable_if<!is_contiguously_hashable<T>::value>::type
197 hash_append(HashAlgorithm& h, T (&a)[N])
198 {
199  for (const auto& t : a)
200  hash_append(h, t);
201 }
202 
203 template <class HashAlgorithm, class T, class U>
204 typename std::enable_if<!is_contiguously_hashable<std::pair<T, U>>::value>::type
205 hash_append(HashAlgorithm& h, const std::pair<T, U>& p)
206 {
207  hash_append(h, p.first, p.second);
208 }
209 
210 namespace detail
211 {
212 // @see
213 // http://stackoverflow.com/questions/7858817/unpacking-a-tuple-to-call-a-matching-function-pointer
214 template <std::size_t...>
215 struct sequence;
216 
217 template <std::size_t N, std::size_t... S>
218 struct generate : generate<N - 1, N - 1, S...>
219 {
220  // nothing
221 };
222 
223 template <std::size_t... S>
224 struct generate<0, S...>
225 {
226  using type = sequence<S...>;
227 };
228 
229 template <class HashAlgorithm, class... Ts, std::size_t... S>
230 void hash_tuple(HashAlgorithm& h, const std::tuple<Ts...>& t, sequence<S...>)
231 {
232  hash_append(h, std::get<S>(t)...);
233 }
234 }
235 
236 template <class HashAlgorithm, class... Ts>
237 typename std::enable_if<!is_contiguously_hashable<std::tuple<Ts...>>::value>::
238  type
239  hash_append(HashAlgorithm& h, const std::tuple<Ts...>& t)
240 {
241  detail::hash_tuple(h, t, typename detail::generate<sizeof...(Ts)>::type{});
242 }
243 
244 template <class HashAlgorithm, class T, std::size_t N>
245 typename std::enable_if<!is_contiguously_hashable<std::array<T, N>>::value>::
246  type
247  hash_append(HashAlgorithm& h, const std::array<T, N>& a)
248 {
249  for (const auto& t : a)
250  hash_append(h, a);
251 }
252 
253 template <class HashAlgorithm, class Char, class Traits, class Alloc>
254 typename std::enable_if<is_contiguously_hashable<Char>::value>::type
255 hash_append(HashAlgorithm& h, const std::basic_string<Char, Traits, Alloc>& s)
256 {
257  h(s.data(), s.size() * sizeof(Char));
258  hash_append(h, s.size());
259 }
260 
261 template <class HashAlgorithm, class Char, class Traits, class Alloc>
262 typename std::enable_if<!is_contiguously_hashable<Char>::value>::type
263 hash_append(HashAlgorithm& h, const std::basic_string<Char, Traits, Alloc>& s)
264 {
265  for (const auto& c : s)
266  hash_append(h, c);
267  hash_append(h, s.size());
268 }
269 
270 template <class HashAlgorithm, class T, class Alloc>
271 typename std::enable_if<is_contiguously_hashable<T>::value>::type
272 hash_append(HashAlgorithm& h, const std::vector<T, Alloc>& v)
273 {
274  h(v.data(), v.size() * sizeof(T));
275  hash_append(h, v.size());
276 }
277 
278 template <class HashAlgorithm, class T, class Alloc>
279 typename std::enable_if<!is_contiguously_hashable<T>::value>::type
280 hash_append(HashAlgorithm& h, const std::vector<T, Alloc>& v)
281 {
282  for (const auto& val : v)
283  hash_append(h, val);
284  hash_append(h, v.size());
285 }
286 
287 template <class HashAlgorithm, class T1, class T2, class... Ts>
288 void hash_append(HashAlgorithm& h, const T1& first, const T2& second,
289  const Ts&... ts)
290 {
291  hash_append(h, first);
292  hash_append(h, second, ts...);
293 }
294 
295 namespace detail
296 {
297 inline uint64_t get_process_seed()
298 {
299  static uint64_t seed = std::random_device{}();
300  return seed;
301 }
302 }
303 
307 template <class HashAlgorithm = typename default_hasher<>::type,
308  class SeedType = uint64_t>
310 {
311  public:
312  using result_type = typename HashAlgorithm::result_type;
313 
314  seeded_hash(SeedType seed) : seed_{seed}
315  {
316  // nothing
317  }
318 
319  template <class T>
320  result_type operator()(const T& t) const
321  {
322  HashAlgorithm h(seed_);
323  using hashing::hash_append;
324  hash_append(h, t);
325  return static_cast<result_type>(h);
326  }
327 
328  SeedType seed() const
329  {
330  return seed_;
331  }
332 
333  private:
334  SeedType seed_;
335 };
336 
342 template <class HashAlgorithm = typename default_hasher<>::type>
343 struct hash
344 {
345  using result_type = typename HashAlgorithm::result_type;
346 
347  template <class T>
348  result_type operator()(const T& t) const
349  {
350  auto seed = detail::get_process_seed();
351  HashAlgorithm h(seed);
352  using hashing::hash_append;
353  hash_append(h, t);
354  return static_cast<result_type>(h);
355  }
356 };
357 }
358 }
359 #endif
Definition: hash.h:29
A generic, randomly seeded hash function.
Definition: hash.h:343
STL namespace.
Definition: hash.h:215
Definition: hash.h:218
A generic, manually seeded hash function.
Definition: hash.h:309
The ModErn Text Analysis toolkit is a suite of natural language processing, classification, information retrieval, data mining, and other applications of text processing.
Definition: analyzer.h:25
A seeded version of farm_hash.
Definition: farm_hash.h:338
Murmur3Hash for 32-bit outputs.
Definition: murmur_hash.h:69