Line data Source code
1 : // Author(s): Maurice Laveaux.
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 :
10 : #ifndef MCRL2_ATERMPP_DETAIL_ATERM_HASH_H_
11 : #define MCRL2_ATERMPP_DETAIL_ATERM_HASH_H_
12 :
13 : #include "mcrl2/atermpp/detail/aterm_appl.h"
14 : #include "mcrl2/atermpp/detail/aterm_int.h"
15 : #include "mcrl2/atermpp/detail/function_symbol_hash.h"
16 : #include "mcrl2/utilities/hash_utility.h"
17 : #include "mcrl2/utilities/detail/memory_utility.h"
18 :
19 : #include <cstdint>
20 : #include <functional>
21 :
22 : namespace std
23 : {
24 :
25 : /// \brief specialization of the standard std::hash function.
26 : template<>
27 : struct hash<atermpp::detail::_aterm*>
28 : {
29 404478197 : std::size_t operator()(const atermpp::detail::_aterm* term) const
30 : {
31 : // All terms are 8 bytes aligned which means that the three lowest significant
32 : // bits of their pointers are always 0. However, their smallest size is 16 bytes so
33 : // the lowest 4 bits do not carry much information.
34 404478197 : return reinterpret_cast<std::uintptr_t>(term) >> 4;
35 : }
36 : };
37 :
38 : /// \brief specialization of the standard std::hash function.
39 : template<>
40 : struct hash<atermpp::unprotected_aterm>
41 : {
42 363968005 : std::size_t operator()(const atermpp::unprotected_aterm& term) const
43 : {
44 : const std::hash<atermpp::detail::_aterm*> hasher;
45 363968005 : return hasher(atermpp::detail::address(term));
46 : }
47 : };
48 :
49 : /// \brief specialization of the standard std::hash function.
50 : template<>
51 : struct hash<atermpp::aterm>
52 : {
53 40510192 : std::size_t operator()(const atermpp::aterm& t) const
54 : {
55 : const std::hash<atermpp::detail::_aterm*> aterm_hasher;
56 40510192 : return aterm_hasher(atermpp::detail::address(t));
57 : }
58 : };
59 :
60 : } // namespace std
61 :
62 : namespace atermpp
63 : {
64 : namespace detail
65 : {
66 :
67 : /// \brief Indicates that the number of arguments is not known at compile time.
68 : constexpr std::size_t DynamicNumberOfArguments = std::numeric_limits<std::size_t>::max();
69 :
70 : /// \brief Computes the hash of the given term.
71 : /// \details Can be optimized with loop unrolling when template parameter N is provided.
72 : /// However, this assumes that every passed to term has arity equal to N.
73 : template<std::size_t N = DynamicNumberOfArguments>
74 : struct aterm_hasher
75 : {
76 : using is_transparent = void;
77 :
78 : std::size_t operator()(const _aterm& term) const noexcept;
79 : std::size_t operator()(const function_symbol& symbol) const noexcept;
80 : std::size_t operator()(const function_symbol& symbol, unprotected_aterm arguments[]) const noexcept;
81 :
82 : template<typename ForwardIterator,
83 : typename std::enable_if<mcrl2::utilities::is_iterator<ForwardIterator>::value, void>::type* = nullptr>
84 : std::size_t operator()(const function_symbol& symbol, ForwardIterator begin, ForwardIterator end) const noexcept;
85 : };
86 :
87 : /// \brief Computes the hash of the given term.
88 : /// \details This version only works whenever N is a compile time constant.
89 : template<std::size_t N = 0>
90 : struct aterm_hasher_finite : public aterm_hasher<N>
91 : {
92 : using is_transparent = void;
93 :
94 : using aterm_hasher<N>::operator();
95 : std::size_t operator()(const function_symbol& symbol, std::array<unprotected_aterm, N> key) const noexcept;
96 :
97 : template<typename ...Args>
98 : std::size_t operator()(const function_symbol& symbol, const Args&... args) const noexcept;
99 : };
100 :
101 : /// \brief Computes the hash of the integral term arguments.
102 : struct aterm_int_hasher
103 : {
104 : using is_transparent = void;
105 :
106 : inline std::size_t operator()(const _aterm_int& term) const noexcept;
107 : inline std::size_t operator()(std::size_t value) const noexcept;
108 : };
109 :
110 : /// \brief Returns true iff first and second are value-equivalent.
111 : /// \details Can be optimized with loop unrolling when template parameter N is provided.
112 : /// However, this assumes that every passed to term has arity equal to N.
113 : template<std::size_t N = DynamicNumberOfArguments>
114 : struct aterm_equals
115 : {
116 : using is_transparent = void;
117 :
118 : bool operator()(const _aterm& first, const _aterm& second) const noexcept;
119 : bool operator()(const _aterm& term, const function_symbol& symbol) const noexcept;
120 : bool operator()(const _aterm& term, const function_symbol& symbol, unprotected_aterm arguments[]) const noexcept;
121 :
122 : template<typename ForwardIterator,
123 : typename std::enable_if<mcrl2::utilities::is_iterator<ForwardIterator>::value>::type* = nullptr>
124 : bool operator()(const _aterm& term, const function_symbol& symbol, ForwardIterator begin, ForwardIterator end) const noexcept;
125 : };
126 :
127 : template<std::size_t N>
128 : struct aterm_equals_finite : public aterm_equals<N>
129 : {
130 : using aterm_equals<N>::operator();
131 : bool operator()(const _aterm& term, const function_symbol& symbol, std::array<unprotected_aterm, N> key) const noexcept;
132 :
133 : template<typename ...Args>
134 : bool operator()(const _aterm& term, const function_symbol& symbol, const Args&... args) const noexcept;
135 : };
136 :
137 : /// \brief Returns true iff the given term(s) or value are equivalent.
138 : struct aterm_int_equals
139 : {
140 : using is_transparent = void;
141 :
142 : inline bool operator()(const _aterm_int& first, const _aterm_int& second) const noexcept;
143 : inline bool operator()(const _aterm_int& term, std::size_t value) const noexcept;
144 : };
145 :
146 : /// \brief Auxiliary function to combine hnr with aterms.
147 : inline
148 363968005 : std::size_t combine(const std::size_t hnr, const unprotected_aterm& term)
149 : {
150 : const std::hash<unprotected_aterm> hasher;
151 363968005 : return mcrl2::utilities::detail::hash_combine_cheap(hnr, hasher(term));
152 : }
153 :
154 : /// Implementation
155 :
156 : template<std::size_t N>
157 238908 : std::size_t aterm_hasher<N>::operator()(const _aterm& term) const noexcept
158 : {
159 238908 : const function_symbol& f = term.function();
160 238908 : std::size_t hnr = operator()(f);
161 :
162 : // The arity is defined by the function symbol iff N is unchanged and the arity is N otherwise.
163 238908 : const std::size_t arity = (N == DynamicNumberOfArguments) ? f.arity() : N;
164 :
165 : // This is a function application with arguments, hash each argument and combine the result.
166 238908 : const _aterm_appl<>& term_appl = static_cast<const _aterm_appl<>&>(term);
167 733567 : for (std::size_t i = 0; i < arity; ++i)
168 : {
169 494659 : hnr = combine(hnr, term_appl.arg(i));
170 : }
171 :
172 238908 : return hnr;
173 : }
174 : template<std::size_t N>
175 160349360 : std::size_t aterm_hasher<N>::operator()(const function_symbol& symbol) const noexcept
176 : {
177 : const std::hash<function_symbol> function_hasher;
178 160349360 : return function_hasher(symbol);
179 : }
180 :
181 : template<std::size_t N>
182 : std::size_t aterm_hasher<N>::operator()(const function_symbol& symbol, unprotected_aterm arguments[]) const noexcept
183 : {
184 : // The arity is defined by the function symbol iff N is unchanged and the arity is N otherwise.
185 : const std::size_t arity = (N == DynamicNumberOfArguments) ? symbol.arity() : N;
186 :
187 : // This is a function application with arguments, hash each argument and combine the result.
188 : std::size_t hnr = operator()(symbol);
189 : for (std::size_t i = 0; i < arity; ++i)
190 : {
191 : hnr = combine(hnr, arguments[i]);
192 : }
193 :
194 : return hnr;
195 : }
196 :
197 : template<std::size_t N>
198 : template<typename ForwardIterator,
199 : typename std::enable_if<mcrl2::utilities::is_iterator<ForwardIterator>::value, void>::type*>
200 27854526 : inline std::size_t aterm_hasher<N>::operator()(const function_symbol& symbol, ForwardIterator it, ForwardIterator end) const noexcept
201 : {
202 : // The end is only used for debugging to ensure that the arity and std::distance(it, end) match.
203 27854526 : mcrl2::utilities::mcrl2_unused(end);
204 :
205 : // The arity is defined by the function symbol iff N is unchanged and the arity is N otherwise.
206 27854526 : const std::size_t arity = (N == DynamicNumberOfArguments) ? symbol.arity() : N;
207 :
208 : // This is a function application with arguments, hash each argument and combine the result.
209 27854526 : std::size_t hnr = operator()(symbol);
210 89736366 : for (std::size_t i = 0; i < arity; ++i)
211 : {
212 61881840 : assert(it != end);
213 61881840 : hnr = combine(hnr, *it);
214 61881840 : ++it;
215 : }
216 :
217 27854526 : assert(it == end);
218 27854526 : return hnr;
219 : }
220 :
221 : template<std::size_t N>
222 10064337 : std::size_t aterm_hasher_finite<N>::operator()(const function_symbol& symbol, std::array<unprotected_aterm, N> arguments) const noexcept
223 : {
224 10064337 : std::size_t hnr = operator()(symbol);
225 :
226 : // This is a function application with arguments, hash each argument and combine the result.
227 37907190 : for (std::size_t i = 0; i < N; ++i)
228 : {
229 27842853 : hnr = combine(hnr, arguments[i]);
230 : }
231 :
232 10064337 : return hnr;
233 : }
234 :
235 : template<std::size_t I = 0, typename... Tp,
236 : typename std::enable_if<I == sizeof...(Tp), void>::type* = nullptr>
237 121003423 : std::size_t combine_args(std::size_t seed, const Tp&...)
238 : {
239 121003423 : return seed;
240 : }
241 :
242 : template<std::size_t I = 0, typename... Tp,
243 : typename std::enable_if<I < sizeof...(Tp), void>::type* = nullptr>
244 273748653 : std::size_t combine_args(std::size_t seed, const Tp&... t)
245 : {
246 273748653 : return combine_args<I+1>(combine(seed, std::get<I>(std::forward_as_tuple(t...))), t...);
247 : }
248 :
249 : template<std::size_t N>
250 : template<typename ...Args>
251 121003423 : std::size_t aterm_hasher_finite<N>::operator()(const function_symbol& symbol, const Args&... args) const noexcept
252 : {
253 121003423 : std::size_t hnr = operator()(symbol);
254 :
255 : // This is a function application with arguments, hash each argument and combine the result.
256 121003423 : return combine_args(hnr, args...);
257 : }
258 :
259 0 : std::size_t aterm_int_hasher::operator()(const _aterm_int& term) const noexcept
260 : {
261 0 : return term.value();
262 : }
263 :
264 19731852 : std::size_t aterm_int_hasher::operator()(std::size_t value) const noexcept
265 : {
266 19731852 : return value;
267 : }
268 :
269 : template<std::size_t N>
270 : bool aterm_equals<N>::operator()(const _aterm& first, const _aterm& second) const noexcept
271 : {
272 : if (&first == &second)
273 : {
274 : // If the pointers are equal they match by definition
275 : return true;
276 : }
277 :
278 : // The arity is defined by the function symbol iff N is unchanged and the arity is N otherwise.
279 : const std::size_t arity = (N == DynamicNumberOfArguments) ? first.function().arity() : N;
280 :
281 : // Check whether the remaining arguments match
282 : for (std::size_t i = 0; i < arity; ++i)
283 : {
284 : if (static_cast<const _term_appl&>(first).arg(i)
285 : != static_cast<const _term_appl&>(second).arg(i))
286 : {
287 : return false;
288 : }
289 : }
290 :
291 : return first.function() == second.function();
292 : }
293 :
294 : template<std::size_t N>
295 1153885 : bool aterm_equals<N>::operator()(const _aterm& term, const function_symbol& symbol) const noexcept
296 : {
297 1153885 : return term.function() == symbol;
298 : }
299 :
300 : template<std::size_t N>
301 : bool aterm_equals<N>::operator()(const _aterm& term, const function_symbol& symbol, unprotected_aterm arguments[]) const noexcept
302 : {
303 : // Each argument should be equal.
304 : for (std::size_t i = 0; i < symbol.arity(); ++i)
305 : {
306 : if (static_cast<const _term_appl&>(term).arg(i) != arguments[i])
307 : {
308 : return false;
309 : }
310 : }
311 :
312 : return term.function() == symbol;
313 : }
314 :
315 : template<std::size_t N>
316 : template<typename ForwardIterator,
317 : typename std::enable_if<mcrl2::utilities::is_iterator<ForwardIterator>::value>::type*>
318 40051719 : inline bool aterm_equals<N>::operator()(const _aterm& term, const function_symbol& symbol, ForwardIterator it, ForwardIterator end) const noexcept
319 : {
320 : // The end is only used for debugging to ensure that the arity and std::distance(it, end) match.
321 40051719 : mcrl2::utilities::mcrl2_unused(end);
322 :
323 40051719 : const std::size_t arity = (N == DynamicNumberOfArguments) ? symbol.arity() : N;
324 :
325 : // Each argument should be equal.
326 101731825 : for (std::size_t i = 0; i < arity; ++i)
327 : {
328 73999490 : assert(it != end);
329 73999490 : if (static_cast<const _term_appl&>(term).arg(i) != (*it))
330 : {
331 12319384 : return false;
332 : }
333 61680106 : ++it;
334 : }
335 :
336 27732335 : assert(it == end);
337 27732335 : return term.function() == symbol;
338 : }
339 :
340 : template<std::size_t N>
341 11840716 : bool aterm_equals_finite<N>::operator()(const _aterm& term, const function_symbol& symbol, std::array<unprotected_aterm, N> arguments) const noexcept
342 : {
343 : // Each argument should be equal.
344 39668554 : for (std::size_t i = 0; i < N; ++i)
345 : {
346 29650529 : if (static_cast<const _aterm_appl<N>&>(term).arg(i) != arguments[i])
347 : {
348 1822691 : return false;
349 : }
350 : }
351 :
352 10018025 : return term.function() == symbol;
353 : }
354 :
355 : template<std::size_t I = 0,
356 : typename... Tp,
357 : typename std::enable_if<I == sizeof...(Tp), void>::type* = nullptr>
358 120171518 : bool equal_args(const _aterm_appl<8>&, const Tp&...)
359 : {
360 120171518 : return true;
361 : }
362 :
363 : template<std::size_t I = 0,
364 : typename... Tp,
365 : typename std::enable_if<I < sizeof...(Tp), void>::type* = nullptr>
366 291015700 : bool equal_args(const _aterm_appl<8>& term, const Tp&... t)
367 : {
368 291015700 : return term.arg(I) == std::get<I>(std::forward_as_tuple(t...)) && equal_args<I+1>(term, t...);
369 : }
370 :
371 : template<std::size_t N>
372 : template<typename ...Args>
373 156559445 : bool aterm_equals_finite<N>::operator()(const _aterm& term, const function_symbol& symbol, const Args&... args) const noexcept
374 : {
375 156559445 : return term.function() == symbol && equal_args(static_cast<const _aterm_appl<8>&>(term), args...);
376 : }
377 :
378 : bool aterm_int_equals::operator()(const _aterm_int& first, const _aterm_int& second) const noexcept
379 : {
380 : return (first.value() == second.value());
381 : }
382 :
383 19688948 : bool aterm_int_equals::operator()(const _aterm_int& term, std::size_t value) const noexcept
384 : {
385 19688948 : return (term.value() == value);
386 : }
387 :
388 : } // namespace detail
389 : } // namespace atermpp
390 :
391 : #endif // MCRL2_ATERMPP_DETAIL_ATERM_HASH_H_
|
