mCRL2
Loading...
Searching...
No Matches
aterm_hash.h
Go to the documentation of this file.
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
18
19#include <cstdint>
20#include <functional>
21
22namespace std
23{
24
26template<>
27struct hash<atermpp::detail::_aterm*>
28{
29 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 return reinterpret_cast<std::uintptr_t>(term) >> 4;
35 }
36};
37
39template<>
40struct hash<atermpp::unprotected_aterm_core>
41{
42 std::size_t operator()(const atermpp::unprotected_aterm_core& term) const
43 {
44 const std::hash<atermpp::detail::_aterm*> hasher;
45 return hasher(atermpp::detail::address(term));
46 }
47};
48
50template<>
51struct hash<atermpp::aterm_core>
52{
53 std::size_t operator()(const atermpp::aterm_core& t) const
54 {
55 const std::hash<atermpp::detail::_aterm*> aterm_hasher;
56 return aterm_hasher(atermpp::detail::address(t));
57 }
58};
59
60} // namespace std
61
62namespace atermpp
63{
64namespace detail
65{
66
68constexpr std::size_t DynamicNumberOfArguments = std::numeric_limits<std::size_t>::max();
69
73template<std::size_t N = DynamicNumberOfArguments>
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_core 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
89template<std::size_t N = 0>
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_core, 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
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
113template<std::size_t N = DynamicNumberOfArguments>
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_core 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
127template<std::size_t N>
129{
130 using aterm_equals<N>::operator();
131 bool operator()(const _aterm& term, const function_symbol& symbol, std::array<unprotected_aterm_core, 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
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
147inline
148std::size_t combine(const std::size_t hnr, const unprotected_aterm_core& term)
149{
150 const std::hash<unprotected_aterm_core> hasher;
151 return mcrl2::utilities::detail::hash_combine_cheap(hnr, hasher(term));
152}
153
155
156template<std::size_t N>
157std::size_t aterm_hasher<N>::operator()(const _aterm& term) const noexcept
158{
159 const function_symbol& f = term.function();
160 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 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 const _aterm_appl<>& term_appl = static_cast<const _aterm_appl<>&>(term);
167 for (std::size_t i = 0; i < arity; ++i)
168 {
169 hnr = combine(hnr, term_appl.arg(i));
170 }
171
172 return hnr;
173}
174template<std::size_t N>
175std::size_t aterm_hasher<N>::operator()(const function_symbol& symbol) const noexcept
176{
177 const std::hash<function_symbol> function_hasher;
178 return function_hasher(symbol);
179}
180
181template<std::size_t N>
182std::size_t aterm_hasher<N>::operator()(const function_symbol& symbol, unprotected_aterm_core 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
197template<std::size_t N>
198template<typename ForwardIterator,
199 typename std::enable_if<mcrl2::utilities::is_iterator<ForwardIterator>::value, void>::type*>
200inline 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.
204
205 // The arity is defined by the function symbol iff N is unchanged and the arity is N otherwise.
206 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 std::size_t hnr = operator()(symbol);
210 for (std::size_t i = 0; i < arity; ++i)
211 {
212 assert(it != end);
213 hnr = combine(hnr, *it);
214 ++it;
215 }
216
217 assert(it == end);
218 return hnr;
219}
220
221template<std::size_t N>
222std::size_t aterm_hasher_finite<N>::operator()(const function_symbol& symbol, std::array<unprotected_aterm_core, N> arguments) const noexcept
223{
224 std::size_t hnr = operator()(symbol);
225
226 // This is a function application with arguments, hash each argument and combine the result.
227 for (std::size_t i = 0; i < N; ++i)
228 {
229 hnr = combine(hnr, arguments[i]);
230 }
231
232 return hnr;
233}
234
235template<std::size_t I = 0, typename... Tp,
236 typename std::enable_if<I == sizeof...(Tp), void>::type* = nullptr>
237std::size_t combine_args(std::size_t seed, const Tp&...)
238{
239 return seed;
240}
241
242template<std::size_t I = 0, typename... Tp,
243 typename std::enable_if<I < sizeof...(Tp), void>::type* = nullptr>
244std::size_t combine_args(std::size_t seed, const Tp&... t)
245{
246 return combine_args<I+1>(combine(seed, std::get<I>(std::forward_as_tuple(t...))), t...);
247}
248
249template<std::size_t N>
250template<typename ...Args>
251std::size_t aterm_hasher_finite<N>::operator()(const function_symbol& symbol, const Args&... args) const noexcept
252{
253 std::size_t hnr = operator()(symbol);
254
255 // This is a function application with arguments, hash each argument and combine the result.
256 return combine_args(hnr, args...);
257}
258
259std::size_t aterm_int_hasher::operator()(const _aterm_int& term) const noexcept
260{
261 return aterm_int_hasher()(term.value());
262}
263
264// The size_t hashfunction below has been taken from a note on stackoverflow
265// by Wolfgang Brehm.
266static inline std::size_t xorshift(const std::size_t n, const std::size_t i)
267{
268 return n^(n>>i);
269}
270
271std::size_t aterm_int_hasher::operator()(std::size_t value) const noexcept
272{
273 const std::size_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
274 const std::size_t c = 17316035218449499591ull;// random odd integer constant;
275 return c*xorshift(p*xorshift(value,32),32);
276}
277
278template<std::size_t N>
279bool aterm_equals<N>::operator()(const _aterm& first, const _aterm& second) const noexcept
280{
281 if (&first == &second)
282 {
283 // If the pointers are equal they match by definition
284 return true;
285 }
286
287 // The arity is defined by the function symbol iff N is unchanged and the arity is N otherwise.
288 const std::size_t arity = (N == DynamicNumberOfArguments) ? first.function().arity() : N;
289
290 // Check whether the remaining arguments match
291 for (std::size_t i = 0; i < arity; ++i)
292 {
293 if (static_cast<const _term_appl&>(first).arg(i)
294 != static_cast<const _term_appl&>(second).arg(i))
295 {
296 return false;
297 }
298 }
299
300 return first.function() == second.function();
301}
302
303template<std::size_t N>
304bool aterm_equals<N>::operator()(const _aterm& term, const function_symbol& symbol) const noexcept
305{
306 return term.function() == symbol;
307}
308
309template<std::size_t N>
310bool aterm_equals<N>::operator()(const _aterm& term, const function_symbol& symbol, unprotected_aterm_core arguments[]) const noexcept
311{
312 // Each argument should be equal.
313 for (std::size_t i = 0; i < symbol.arity(); ++i)
314 {
315 if (static_cast<const _term_appl&>(term).arg(i) != arguments[i])
316 {
317 return false;
318 }
319 }
320
321 return term.function() == symbol;
322}
323
324template<std::size_t N>
325template<typename ForwardIterator,
326 typename std::enable_if<mcrl2::utilities::is_iterator<ForwardIterator>::value>::type*>
327inline bool aterm_equals<N>::operator()(const _aterm& term, const function_symbol& symbol, ForwardIterator it, ForwardIterator end) const noexcept
328{
329 // The end is only used for debugging to ensure that the arity and std::distance(it, end) match.
331
332 const std::size_t arity = (N == DynamicNumberOfArguments) ? symbol.arity() : N;
333
334 // Each argument should be equal.
335 for (std::size_t i = 0; i < arity; ++i)
336 {
337 assert(it != end);
338 if (static_cast<const _term_appl&>(term).arg(i) != (*it))
339 {
340 return false;
341 }
342 ++it;
343 }
344
345 assert(it == end);
346 return term.function() == symbol;
347}
348
349template<std::size_t N>
350bool aterm_equals_finite<N>::operator()(const _aterm& term, const function_symbol& symbol, std::array<unprotected_aterm_core, N> arguments) const noexcept
351{
352 // Each argument should be equal.
353 for (std::size_t i = 0; i < N; ++i)
354 {
355 if (static_cast<const _aterm_appl<N>&>(term).arg(i) != arguments[i])
356 {
357 return false;
358 }
359 }
360
361 return term.function() == symbol;
362}
363
364template<std::size_t I = 0,
365 typename... Tp,
366 typename std::enable_if<I == sizeof...(Tp), void>::type* = nullptr>
367bool equal_args(const _aterm_appl<8>&, const Tp&...)
368{
369 return true;
370}
371
372template<std::size_t I = 0,
373 typename... Tp,
374 typename std::enable_if<I < sizeof...(Tp), void>::type* = nullptr>
375bool equal_args(const _aterm_appl<8>& term, const Tp&... t)
376{
377 return term.arg(I) == std::get<I>(std::forward_as_tuple(t...)) && equal_args<I+1>(term, t...);
378}
379
380template<std::size_t N>
381template<typename ...Args>
382bool aterm_equals_finite<N>::operator()(const _aterm& term, const function_symbol& symbol, const Args&... args) const noexcept
383{
384 return term.function() == symbol && equal_args(static_cast<const _aterm_appl<8>&>(term), args...);
385}
386
387bool aterm_int_equals::operator()(const _aterm_int& first, const _aterm_int& second) const noexcept
388{
389 return (first.value() == second.value());
390}
391
392bool aterm_int_equals::operator()(const _aterm_int& term, std::size_t value) const noexcept
393{
394 return (term.value() == value);
395}
396
397} // namespace detail
398} // namespace atermpp
399
400#endif // MCRL2_ATERMPP_DETAIL_ATERM_HASH_H_
The aterm_core base class that provides protection of the underlying shared terms.
Definition aterm_core.h:182
const function_symbol & function() const
Returns the function symbol belonging to an aterm.
Definition aterm.h:144
This class stores a term followed by N arguments. Where N should be equal to the arity of the functio...
Definition aterm.h:34
const aterm_core & arg(std::size_t index) const
Definition aterm.h:97
The underlying integer term that actually carries the integer data.
Definition aterm_int.h:22
This is the class to which an aterm points.
Definition aterm_core.h:48
std::size_t arity() const
Return the arity (number of arguments) of the function symbol (function_symbol).
An unprotected term does not change the reference count of the shared term when it is copied or moved...
Definition aterm_core.h:32
This file contains a specialisation for hashes on pairs. This is not a part of the standard,...
This file contains a workaround that allows to assign a small array of elements on the stack....
_aterm * address(const unprotected_aterm_core &t)
Definition aterm_core.h:239
std::size_t combine(const std::size_t hnr, const unprotected_aterm_core &term)
Auxiliary function to combine hnr with aterms.
Definition aterm_hash.h:148
std::size_t combine_args(std::size_t seed, const Tp &...)
Definition aterm_hash.h:237
_aterm_appl<> _term_appl
A default instantiation for the underlying term application.
Definition aterm.h:113
constexpr std::size_t DynamicNumberOfArguments
Indicates that the number of arguments is not known at compile time.
Definition aterm_hash.h:68
The main namespace for the aterm++ library.
Definition algorithm.h:21
data_expression I(const data_expression &x)
normalizer< Function > N(const Function &f)
const data_expression & arg(const data_expression &e)
Function for projecting out argument. arg from an application.
Definition bag1.h:1618
const function_symbol & first()
Constructor for function symbol @first.
Definition nat1.h:1791
std::size_t hash_combine_cheap(const std::size_t seed, const std::size_t hash_number)
Auxiliary function to combine seed with a hash number.
void mcrl2_unused(T &&...)
Function that can be used to silence unused parameter warnings.
Definition unused.h:20
STL namespace.
bool operator()(const _aterm &term, const function_symbol &symbol, const Args &... args) const noexcept
bool operator()(const _aterm &term, const function_symbol &symbol, std::array< unprotected_aterm_core, N > key) const noexcept
Returns true iff first and second are value-equivalent.
Definition aterm_hash.h:115
bool operator()(const _aterm &term, const function_symbol &symbol, ForwardIterator begin, ForwardIterator end) const noexcept
bool operator()(const _aterm &first, const _aterm &second) const noexcept
bool operator()(const _aterm &term, const function_symbol &symbol) const noexcept
bool operator()(const _aterm &term, const function_symbol &symbol, unprotected_aterm_core arguments[]) const noexcept
Computes the hash of the given term.
Definition aterm_hash.h:91
std::size_t operator()(const function_symbol &symbol, const Args &... args) const noexcept
std::size_t operator()(const function_symbol &symbol, std::array< unprotected_aterm_core, N > key) const noexcept
Definition aterm_hash.h:222
Computes the hash of the given term.
Definition aterm_hash.h:75
std::size_t operator()(const function_symbol &symbol) const noexcept
Definition aterm_hash.h:175
std::size_t operator()(const _aterm &term) const noexcept
Implementation.
Definition aterm_hash.h:157
std::size_t operator()(const function_symbol &symbol, ForwardIterator begin, ForwardIterator end) const noexcept
Definition aterm_hash.h:200
std::size_t operator()(const function_symbol &symbol, unprotected_aterm_core arguments[]) const noexcept
Definition aterm_hash.h:182
Returns true iff the given term(s) or value are equivalent.
Definition aterm_hash.h:139
bool operator()(const _aterm_int &term, std::size_t value) const noexcept
bool operator()(const _aterm_int &first, const _aterm_int &second) const noexcept
Computes the hash of the integral term arguments.
Definition aterm_hash.h:103
std::size_t operator()(const _aterm_int &term) const noexcept
std::size_t operator()(std::size_t value) const noexcept
std::size_t operator()(const atermpp::aterm_core &t) const
Definition aterm_hash.h:53
std::size_t operator()(const atermpp::detail::_aterm *term) const
Definition aterm_hash.h:29
std::size_t operator()(const atermpp::unprotected_aterm_core &term) const
Definition aterm_hash.h:42
#define hash(l, r, m)
Definition tree_set.cpp:23