1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#pragma once
#include "StarBytes.hpp"
namespace Star {
// To avoid having to specialize std::hash in the std namespace, which is
// slightly annoying, Star type wrappers use Star::hash, which just defaults to
// std::hash. Star::hash also enables template specialization with a dummy
// Enable parameter.
template <typename T, typename Enable = void>
struct hash : public std::hash<T> {};
inline void hashCombine(size_t& hash, size_t comb) {
hash ^= comb * 2654435761 + 0x9e3779b9 + (hash << 6) + (hash >> 2);
}
// Paul Larson hashing algorithm, very very *cheap* hashing function.
class PLHasher {
public:
PLHasher(size_t initial = 0)
: m_hash(initial) {}
template <typename T>
void put(T b) {
m_hash = m_hash * 101 + (size_t)b;
}
size_t hash() const {
return m_hash;
}
private:
size_t m_hash;
};
template <typename first_t, typename second_t>
class hash<std::pair<first_t, second_t>> {
private:
Star::hash<first_t> firstHasher;
Star::hash<second_t> secondHasher;
public:
size_t operator()(std::pair<first_t, second_t> const& a) const {
size_t hashval = firstHasher(a.first);
hashCombine(hashval, secondHasher(a.second));
return hashval;
}
};
template <typename... TTypes>
class hash<std::tuple<TTypes...>> {
private:
typedef std::tuple<TTypes...> Tuple;
template <size_t N>
size_t operator()(Tuple const&) const {
return 0;
}
template <size_t N, typename THead, typename... TTail>
size_t operator()(Tuple const& value) const {
size_t hash = Star::hash<THead>()(std::get<N - sizeof...(TTail) - 1>(value));
hashCombine(hash, operator()<N, TTail...>(value));
return hash;
}
public:
size_t operator()(Tuple const& value) const {
return operator()<sizeof...(TTypes), TTypes...>(value);
}
};
template <typename EnumType>
struct hash<EnumType, typename std::enable_if<std::is_enum<EnumType>::value>::type> {
private:
typedef typename std::underlying_type<EnumType>::type UnderlyingType;
public:
size_t operator()(EnumType e) const {
return std::hash<UnderlyingType>()((UnderlyingType)e);
}
};
template <typename T>
size_t hashOf(T const& t) {
return Star::hash<T>()(t);
}
template <typename T1, typename T2, typename... TL>
size_t hashOf(T1 const& t1, T2 const& t2, TL const&... rest) {
size_t hash = hashOf(t1);
hashCombine(hash, hashOf(t2, rest...));
return hash;
};
}
|