Drake
hash.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include <cmath>
4 #include <cstddef>
5 #include <functional>
6 #include <iostream>
7 #include <map>
8 #include <set>
9 #include <string>
10 #include <type_traits>
11 #include <utility>
12 #include <vector>
13 
17 
18 /// @defgroup hash_append hash_append generic hashing
19 /// @{
20 /// @ingroup cxx
21 /// @brief Drake uses the hash_append pattern as described by N3980.
22 ///
23 /// For a full treatment of the hash_append pattern, refer to:
24 /// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html
25 ///
26 /// <h3>Providing hash_append support within a class</h3>
27 ///
28 /// Drake types may implement a `hash_append` function.
29 /// The function appends every hash-relevant member field into the hasher:
30 /// @code
31 /// class MyValue {
32 /// public:
33 /// ...
34 /// /// Implements the @ref hash_append concept.
35 /// template <class HashAlgorithm>
36 /// friend void hash_append(
37 /// HashAlgorithm& hasher, const MyValue& item) noexcept {
38 /// using drake::hash_append;
39 /// hash_append(hasher, item.my_data_);
40 /// }
41 /// ...
42 /// private:
43 /// std::string my_data_;
44 /// };
45 /// @endcode
46 ///
47 /// Checklist for reviewing a `hash_append` implementation:
48 /// - The function cites `@ref hash_append` in its Doxygen comment.
49 /// - The function is marked `noexcept`.
50 ///
51 /// <h3>Using hashable types</h3>
52 ///
53 /// Types that implement this pattern may be used in unordered collections:
54 /// @code
55 /// std::unordered_set<MyValue, drake::DefaultHash> foo;
56 /// @endcode
57 ///
58 /// Some Drake types may also choose to specialize `std::hash<MyValue>` to use
59 /// `DefaultHash`, so that the second template argument to `std::unordered_set`
60 /// can be omitted. For example, Drake's `symbolic::Expression` header says:
61 /// @code
62 /// namespace std {
63 /// struct hash<drake::symbolic::Expression> : public drake::DefaultHash {};
64 /// } // namespace std
65 /// @endcode
66 /// so that users are able to simply write:
67 /// @code
68 /// std::unordered_set<drake::symbolic::Expression> foo;
69 /// @endcode
70 ///
71 /// @}
72 
73 namespace drake {
74 
75 /// Provides @ref hash_append for integral constants.
76 template <class HashAlgorithm, class T>
79  HashAlgorithm& hasher, const T& item) noexcept {
80  hasher(std::addressof(item), sizeof(item));
81 }
82 
83 /// Provides @ref hash_append for enumerations.
84 template <class HashAlgorithm, class T>
87  HashAlgorithm& hasher, const T& item) noexcept {
88  hasher(std::addressof(item), sizeof(item));
89 }
90 
91 /// Provides @ref hash_append for floating point values.
92 template <class HashAlgorithm, class T>
95  HashAlgorithm& hasher, const T& item) noexcept {
96  // Hashing a NaN makes no sense, since they cannot compare as equal.
97  DRAKE_ASSERT(!std::isnan(item));
98  // +0.0 and -0.0 are equal, so must hash identically.
99  if (item == 0.0) {
100  const T zero{0.0};
101  hasher(std::addressof(zero), sizeof(zero));
102  } else {
103  hasher(std::addressof(item), sizeof(item));
104  }
105 }
106 
107 /// Provides @ref hash_append for std::string.
108 /// (Technically, any string based on `CharT = char`.)
109 template <class HashAlgorithm, class Traits, class Allocator>
111  HashAlgorithm& hasher,
112  const std::basic_string<char, Traits, Allocator>& item) noexcept {
113  using drake::hash_append;
114  hasher(item.data(), item.size());
115  // All collection types must send their size, after their contents.
116  // See the #hash_append_vector anchor in N3980.
117  hash_append(hasher, item.size());
118 }
119 
120 /// Provides @ref hash_append for std::pair.
121 template <class HashAlgorithm, class T1, class T2>
123  HashAlgorithm& hasher, const std::pair<T1, T2>& item) noexcept {
124  using drake::hash_append;
125  hash_append(hasher, item.first);
126  hash_append(hasher, item.second);
127 }
128 
129 /// Provides @ref hash_append for drake::optional.
130 ///
131 /// Note that `std::hash<std::optional<T>>` provides the peculiar invariant
132 /// that the hash of an `optional` bearing a value `v` shall evaluate to the
133 /// same hash as that of the value `v` itself. Hash operations implemented
134 /// with this `hash_append` do *not* provide that invariant.
135 //
136 // NB: In general, implementations of `hash_append` for drake types belong
137 // with the definitions of their respective drake types, not here.
138 //
139 // However, since `drake::optional` is more or less an alias for an
140 // STL type, and in particular since `drake_optional.h` is included
141 // in the ":essential" library, and `hash.h` is not, this is the
142 // better location for this definition.
143 template <class HashAlgorithm, class T>
145  HashAlgorithm& hasher, const drake::optional<T>& item) noexcept {
146  if (item) {
147  hash_append(hasher, *item);
148  }
149  hash_append(hasher, item.has_value());
150 };
151 
152 /// Provides @ref hash_append for a range, as given by two iterators.
153 template <class HashAlgorithm, class Iter>
155  // NOLINTNEXTLINE(runtime/references) Per hash_append convention.
156  HashAlgorithm& hasher, Iter begin, Iter end) noexcept {
157  using drake::hash_append;
158  size_t count{0};
159  for (Iter iter = begin; iter != end; ++iter, ++count) {
160  hash_append(hasher, *iter);
161  }
162  // All collection types must send their size, after their contents.
163  // See the #hash_append_vector anchor in N3980.
164  hash_append(hasher, count);
165 }
166 
167 /// Provides @ref hash_append for std::map.
168 ///
169 /// Note that there is no `hash_append` overload for `std::unordered_map`, and
170 /// such an overload must never appear. See n3980.html#unordered for details.
171 template <
172  class HashAlgorithm,
173  class T1,
174  class T2,
175  class Compare,
176  class Allocator>
178  HashAlgorithm& hasher,
179  const std::map<T1, T2, Compare, Allocator>& item) noexcept {
180  return hash_append_range(hasher, item.begin(), item.end());
181 };
182 
183 /// Provides @ref hash_append for std::set.
184 ///
185 /// Note that there is no `hash_append` overload for `std::unordered_set`, and
186 /// such an overload must never appear. See n3980.html#unordered for details.
187 template <
188  class HashAlgorithm,
189  class Key,
190  class Compare,
191  class Allocator>
193  HashAlgorithm& hasher,
194  const std::set<Key, Compare, Allocator>& item) noexcept {
195  return hash_append_range(hasher, item.begin(), item.end());
196 };
197 
198 /// A hashing functor, somewhat like `std::hash`. Given an item of type @p T,
199 /// applies @ref hash_append to it, directing the bytes to append into the
200 /// given @p HashAlgorithm, and then finally returning the algorithm's result.
201 template <class HashAlgorithm>
202 struct uhash {
203  using result_type = typename HashAlgorithm::result_type;
204 
205  template <class T>
206  result_type operator()(const T& item) const noexcept {
207  HashAlgorithm hasher;
208  using drake::hash_append;
209  hash_append(hasher, item);
210  return static_cast<result_type>(hasher);
211  }
212 };
213 
214 namespace detail {
215 /// The FNV1a hash algorithm, used for @ref hash_append.
216 /// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
217 class FNV1aHasher {
218  public:
219  using result_type = size_t;
220 
221  void operator()(const void* data, size_t length) noexcept {
222  const uint8_t* const begin = static_cast<const uint8_t*>(data);
223  const uint8_t* const end = begin + length;
224  for (const uint8_t* iter = begin; iter < end; ++iter) {
225  hash_ = (hash_ ^ *iter) * 1099511628211u;
226  }
227  }
228 
229  explicit operator size_t() noexcept {
230  return hash_;
231  }
232 
233  private:
234  static_assert(sizeof(result_type) == (64 / 8), "We require a 64-bit size_t");
235  result_type hash_{0xcbf29ce484222325u};
236 };
237 } // namespace detail
238 
239 /// The default HashAlgorithm concept implementation across Drake. This is
240 /// guaranteed to have a result_type of size_t to be compatible with std::hash.
242 
243 /// The default hashing functor, akin to std::hash.
245 
246 /// An adapter that forwards the HashAlgorithm::operator(data, length) function
247 /// concept into a runtime-provided std::function of the same signature. This
248 /// is useful for passing a concrete HashAlgorithm implementation through into
249 /// non-templated code, such as with an Impl or Cell pattern.
251  /// A std::function whose signature matches HashAlgorithm::operator().
252  using Func = std::function<void(const void*, size_t)>;
253 
254  /// Create a delegating hasher that calls the given @p func.
255  explicit DelegatingHasher(Func func) : func_(std::move(func)) {
256  // In order for operator() to be noexcept, it must have a non-empty func_.
257  DRAKE_THROW_UNLESS(static_cast<bool>(func_));
258  }
259 
260  /// Append [data, data + length) bytes into the wrapped algorithm.
261  void operator()(const void* data, size_t length) noexcept {
262  func_(data, length);
263  }
264 
265  private:
266  const Func func_;
267 };
268 
269 } // namespace drake
An adapter that forwards the HashAlgorithm::operator(data, length) function concept into a runtime-pr...
Definition: hash.h:250
bool isnan(const Eigen::AutoDiffScalar< DerType > &x)
Overloads isnan to mimic std::isnan from <cmath>.
Definition: autodiff_overloads.h:52
double value
Definition: wrap_test_util_py.cc:12
Provides a convenient wrapper to throw an exception when a condition is unmet.
Definition: automotive_demo.cc:105
STL namespace.
#define DRAKE_THROW_UNLESS(condition)
Evaluates condition and iff the value is false will throw an exception with a message showing at leas...
Definition: drake_throw.h:23
size_t result_type
Definition: hash.h:219
stx::optional< T > optional
Definition: drake_optional.h:22
DelegatingHasher(Func func)
Create a delegating hasher that calls the given func.
Definition: hash.h:255
#define DRAKE_ASSERT(condition)
DRAKE_ASSERT(condition) is similar to the built-in assert(condition) from the C++ system header <cas...
Definition: drake_assert.h:37
Provides Drake&#39;s assertion implementation.
Provides drake::optional as an alias for the appropriate implementation of std::optional or std::expe...
void operator()(const void *data, size_t length) noexcept
Definition: hash.h:221
std::enable_if_t< std::is_integral< T >::value > hash_append(HashAlgorithm &hasher, const T &item) noexcept
Provides hash_append generic hashing for integral constants.
Definition: hash.h:78
A hashing functor, somewhat like std::hash.
Definition: hash.h:202
optional< api::LaneEnd::Which > end
Definition: loader.cc:42
result_type operator()(const T &item) const noexcept
Definition: hash.h:206
typename HashAlgorithm::result_type result_type
Definition: hash.h:203
void operator()(const void *data, size_t length) noexcept
Append [data, data + length) bytes into the wrapped algorithm.
Definition: hash.h:261
The FNV1a hash algorithm, used for hash_append generic hashing.
Definition: hash.h:217
const char * func
Definition: drake_throw.h:16
std::function< void(const void *, size_t)> Func
A std::function whose signature matches HashAlgorithm::operator().
Definition: hash.h:252
void hash_append_range(HashAlgorithm &hasher, Iter begin, Iter end) noexcept
Provides hash_append generic hashing for a range, as given by two iterators.
Definition: hash.h:154
int data
Definition: value_test.cc:20