1 | /* |
2 | * Copyright (c) 2016-2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | /** |
30 | * \file |
31 | * \brief Hashing utility functions. |
32 | */ |
33 | |
34 | #ifndef UTIL_HASH_H |
35 | #define UTIL_HASH_H |
36 | |
37 | #include <functional> |
38 | #include <string> |
39 | #include <type_traits> |
40 | #include <utility> |
41 | |
42 | namespace ue2 { |
43 | |
44 | namespace hash_detail { |
45 | |
46 | inline |
47 | void hash_combine_impl(size_t &seed, size_t value) { |
48 | // Note: constants explicitly truncated on 32-bit platforms. |
49 | const size_t a = (size_t)0x0b4e0ef37bc32127ULL; |
50 | const size_t b = (size_t)0x318f07b0c8eb9be9ULL; |
51 | seed ^= value * a; |
52 | seed += b; |
53 | } |
54 | |
55 | /** \brief Helper that determines whether std::begin() exists for T. */ |
56 | template<typename T> |
57 | struct is_container_check { |
58 | private: |
59 | template<typename C> |
60 | static auto has_begin_function(const C &obj) -> decltype(std::begin(obj)) { |
61 | return std::begin(obj); |
62 | } |
63 | static void has_begin_function(...) { |
64 | return; |
65 | } |
66 | using has_begin_type = decltype(has_begin_function(std::declval<T>())); |
67 | |
68 | public: |
69 | static const bool value = !std::is_void<has_begin_type>::value; |
70 | }; |
71 | |
72 | /** \brief Type trait to enable on whether T is a container. */ |
73 | template<typename T> |
74 | struct is_container |
75 | : public ::std::integral_constant<bool, is_container_check<T>::value> {}; |
76 | |
77 | /** \brief Helper that determines whether T::hash() exists. */ |
78 | template<typename T> |
79 | struct has_hash_member_check { |
80 | private: |
81 | template<typename C> |
82 | static auto has_hash_member_function(const C &obj) -> decltype(obj.hash()) { |
83 | return obj.hash(); |
84 | } |
85 | static void has_hash_member_function(...) { |
86 | return; |
87 | } |
88 | using has_hash = decltype(has_hash_member_function(std::declval<T>())); |
89 | |
90 | public: |
91 | static const bool value = !std::is_void<has_hash>::value; |
92 | }; |
93 | |
94 | /** \brief Type trait to enable on whether T::hash() exists. */ |
95 | template<typename T> |
96 | struct has_hash_member |
97 | : public ::std::integral_constant<bool, has_hash_member_check<T>::value> {}; |
98 | |
99 | /** \brief Default hash: falls back to std::hash. */ |
100 | template<typename T, typename Enable = void> |
101 | struct ue2_hash { |
102 | using decayed_type = typename std::decay<T>::type; |
103 | size_t operator()(const T &obj) const { |
104 | return std::hash<decayed_type>()(obj); |
105 | } |
106 | }; |
107 | |
108 | /** \brief Hash for std::pair. */ |
109 | template<typename A, typename B> |
110 | struct ue2_hash<std::pair<A, B>, void> { |
111 | size_t operator()(const std::pair<A, B> &p) const { |
112 | size_t v = 0; |
113 | hash_combine_impl(v, ue2_hash<A>()(p.first)); |
114 | hash_combine_impl(v, ue2_hash<B>()(p.second)); |
115 | return v; |
116 | } |
117 | }; |
118 | |
119 | /** \brief Hash for any type that has a hash() member function. */ |
120 | template<typename T> |
121 | struct ue2_hash<T, typename std::enable_if<has_hash_member<T>::value>::type> { |
122 | size_t operator()(const T &obj) const { |
123 | return obj.hash(); |
124 | } |
125 | }; |
126 | |
127 | /** |
128 | * \brief Hash for any container type that supports std::begin(). |
129 | * |
130 | * We exempt std::string as std::hash<std:string> is provided and quicker. |
131 | */ |
132 | template<typename T> |
133 | struct ue2_hash<T, typename std::enable_if< |
134 | is_container<T>::value && |
135 | !std::is_same<typename std::decay<T>::type, std::string>::value && |
136 | !has_hash_member<T>::value>::type> { |
137 | size_t operator()(const T &obj) const { |
138 | size_t v = 0; |
139 | for (const auto &elem : obj) { |
140 | using element_type = typename std::decay<decltype(elem)>::type; |
141 | hash_combine_impl(v, ue2_hash<element_type>()(elem)); |
142 | } |
143 | return v; |
144 | } |
145 | }; |
146 | |
147 | /** \brief Hash for enum types. */ |
148 | template<typename T> |
149 | struct ue2_hash<T, typename std::enable_if<std::is_enum<T>::value>::type> { |
150 | size_t operator()(const T &obj) const { |
151 | using utype = typename std::underlying_type<T>::type; |
152 | return ue2_hash<utype>()(static_cast<utype>(obj)); |
153 | } |
154 | }; |
155 | |
156 | template<typename T> |
157 | void hash_combine(size_t &seed, const T &obj) { |
158 | hash_combine_impl(seed, ue2_hash<T>()(obj)); |
159 | } |
160 | |
161 | template<typename T> |
162 | void hash_build(size_t &v, const T &obj) { |
163 | hash_combine(v, obj); |
164 | } |
165 | |
166 | template<typename T, typename... Args> |
167 | void hash_build(size_t &v, const T &obj, Args&&... args) { |
168 | hash_build(v, obj); |
169 | hash_build(v, args...); // recursive |
170 | } |
171 | |
172 | } // namespace hash_detail |
173 | |
174 | using hash_detail::hash_combine; |
175 | |
176 | /** |
177 | * \brief Hasher for general use. |
178 | * |
179 | * Provides operators for most standard containers and falls back to |
180 | * std::hash<T>. |
181 | */ |
182 | struct ue2_hasher { |
183 | template<typename T> |
184 | size_t operator()(const T &obj) const { |
185 | return hash_detail::ue2_hash<T>()(obj); |
186 | } |
187 | }; |
188 | |
189 | /** |
190 | * \brief Computes the combined hash of all its arguments. |
191 | * |
192 | * Simply use: |
193 | * |
194 | * size_t hash = hash_all(a, b, c, d); |
195 | * |
196 | * Where a, b, c and d are hashable. |
197 | */ |
198 | template<typename... Args> |
199 | size_t hash_all(Args&&... args) { |
200 | size_t v = 0; |
201 | hash_detail::hash_build(v, args...); |
202 | return v; |
203 | } |
204 | |
205 | } // namespace ue2 |
206 | |
207 | #endif // UTIL_HASH_H |
208 | |