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
42namespace ue2 {
43
44namespace hash_detail {
45
46inline
47void 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. */
56template<typename T>
57struct is_container_check {
58private:
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
68public:
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. */
73template<typename T>
74struct is_container
75 : public ::std::integral_constant<bool, is_container_check<T>::value> {};
76
77/** \brief Helper that determines whether T::hash() exists. */
78template<typename T>
79struct has_hash_member_check {
80private:
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
90public:
91 static const bool value = !std::is_void<has_hash>::value;
92};
93
94/** \brief Type trait to enable on whether T::hash() exists. */
95template<typename T>
96struct 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. */
100template<typename T, typename Enable = void>
101struct 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. */
109template<typename A, typename B>
110struct 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. */
120template<typename T>
121struct 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 */
132template<typename T>
133struct 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. */
148template<typename T>
149struct 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
156template<typename T>
157void hash_combine(size_t &seed, const T &obj) {
158 hash_combine_impl(seed, ue2_hash<T>()(obj));
159}
160
161template<typename T>
162void hash_build(size_t &v, const T &obj) {
163 hash_combine(v, obj);
164}
165
166template<typename T, typename... Args>
167void 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
174using 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 */
182struct 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 */
198template<typename... Args>
199size_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