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 
14 #include "drake/common/drake_assert.h"
15 #include "drake/common/drake_throw.h"
16 
17 /// @defgroup hash_append hash_append generic hashing
18 /// @{
19 /// @ingroup cxx
20 /// @brief Drake uses the hash_append pattern as described by N3980.
21 ///
22 /// For a full treatment of the hash_append pattern, refer to:
23 /// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html
24 ///
25 /// <h3>Providing hash_append support within a class</h3>
26 ///
27 /// Drake types may implement a `hash_append` function.
28 /// The function appends every hash-relevant member field into the hasher:
29 /// @code
30 /// class MyValue {
31 /// public:
32 /// ...
33 /// /// Implements the @ref hash_append concept.
34 /// template <class HashAlgorithm>
35 /// friend void hash_append(
36 /// HashAlgorithm& hasher, const MyValue& item) noexcept {
37 /// using drake::hash_append;
38 /// hash_append(hasher, item.my_data_);
39 /// }
40 /// ...
41 /// private:
42 /// std::string my_data_;
43 /// };
44 /// @endcode
45 ///
46 /// Checklist for reviewing a `hash_append` implementation:
47 /// - The function cites `@ref hash_append` in its Doxygen comment.
48 /// - The function is marked `noexcept`.
49 ///
50 /// <h3>Using hashable types</h3>
51 ///
52 /// Types that implement this pattern may be used in unordered collections:
53 /// @code
54 /// std::unordered_set<MyValue, drake::DefaultHash> foo;
55 /// @endcode
56 ///
57 /// Some Drake types may also choose to specialize `std::hash<MyValue>` to use
58 /// `DefaultHash`, so that the second template argument to `std::unordered_set`
59 /// can be omitted. For example, Drake's `symbolic::Expression` header says:
60 /// @code
61 /// namespace std {
62 /// struct hash<drake::symbolic::Expression> : public drake::DefaultHash {};
63 /// } // namespace std
64 /// @endcode
65 /// so that users are able to simply write:
66 /// @code
67 /// std::unordered_set<drake::symbolic::Expression> foo;
68 /// @endcode
69 ///
70 /// @}
71 
72 namespace drake {
73 
74 /// Provides @ref hash_append for integral constants.
75 template <class HashAlgorithm, class T>
78  HashAlgorithm& hasher, const T& item) noexcept {
79  hasher(std::addressof(item), sizeof(item));
80 }
81 
82 /// Provides @ref hash_append for enumerations.
83 template <class HashAlgorithm, class T>
86  HashAlgorithm& hasher, const T& item) noexcept {
87  hasher(std::addressof(item), sizeof(item));
88 }
89 
90 /// Provides @ref hash_append for floating point values.
91 template <class HashAlgorithm, class T>
94  HashAlgorithm& hasher, const T& item) noexcept {
95  // Hashing a NaN makes no sense, since they cannot compare as equal.
96  DRAKE_ASSERT(!std::isnan(item));
97  // +0.0 and -0.0 are equal, so must hash identically.
98  if (item == 0.0) {
99  const T zero{0.0};
100  hasher(std::addressof(zero), sizeof(zero));
101  } else {
102  hasher(std::addressof(item), sizeof(item));
103  }
104 }
105 
106 /// Provides @ref hash_append for std::string.
107 /// (Technically, any string based on `CharT = char`.)
108 template <class HashAlgorithm, class Traits, class Allocator>
110  HashAlgorithm& hasher,
111  const std::basic_string<char, Traits, Allocator>& item) noexcept {
112  using drake::hash_append;
113  hasher(item.data(), item.size());
114  // All collection types must send their size, after their contents.
115  // See the #hash_append_vector anchor in N3980.
116  hash_append(hasher, item.size());
117 }
118 
119 /// Provides @ref hash_append for std::pair.
120 template <class HashAlgorithm, class T1, class T2>
122  HashAlgorithm& hasher, const std::pair<T1, T2>& item) noexcept {
123  using drake::hash_append;
124  hash_append(hasher, item.first);
125  hash_append(hasher, item.second);
126 }
127 
128 /// Provides @ref hash_append for a range, as given by two iterators.
129 template <class HashAlgorithm, class Iter>
131  // NOLINTNEXTLINE(runtime/references) Per hash_append convention.
132  HashAlgorithm& hasher, Iter begin, Iter end) noexcept {
133  using drake::hash_append;
134  size_t count{0};
135  for (Iter iter = begin; iter != end; ++iter, ++count) {
136  hash_append(hasher, *iter);
137  }
138  // All collection types must send their size, after their contents.
139  // See the #hash_append_vector anchor in N3980.
140  hash_append(hasher, count);
141 }
142 
143 /// Provides @ref hash_append for std::map.
144 ///
145 /// Note that there is no `hash_append` overload for `std::unordered_map`, and
146 /// such an overload must never appear. See n3980.html#unordered for details.
147 template <
148  class HashAlgorithm,
149  class T1,
150  class T2,
151  class Compare,
152  class Allocator>
154  HashAlgorithm& hasher,
155  const std::map<T1, T2, Compare, Allocator>& item) noexcept {
156  return hash_append_range(hasher, item.begin(), item.end());
157 };
158 
159 /// Provides @ref hash_append for std::set.
160 ///
161 /// Note that there is no `hash_append` overload for `std::unordered_set`, and
162 /// such an overload must never appear. See n3980.html#unordered for details.
163 template <
164  class HashAlgorithm,
165  class Key,
166  class Compare,
167  class Allocator>
169  HashAlgorithm& hasher,
170  const std::set<Key, Compare, Allocator>& item) noexcept {
171  return hash_append_range(hasher, item.begin(), item.end());
172 };
173 
174 /// A hashing functor, somewhat like `std::hash`. Given an item of type @p T,
175 /// applies @ref hash_append to it, directing the bytes to append into the
176 /// given @p HashAlgorithm, and then finally returning the algorithm's result.
177 template <class HashAlgorithm>
178 struct uhash {
179  using result_type = typename HashAlgorithm::result_type;
180 
181  template <class T>
182  result_type operator()(const T& item) const noexcept {
183  HashAlgorithm hasher;
184  using drake::hash_append;
185  hash_append(hasher, item);
186  return static_cast<result_type>(hasher);
187  }
188 };
189 
190 namespace detail {
191 /// The FNV1a hash algorithm, used for @ref hash_append.
192 /// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
193 class FNV1aHasher {
194  public:
195  using result_type = size_t;
196 
197  void operator()(const void* data, size_t length) noexcept {
198  const uint8_t* const begin = static_cast<const uint8_t*>(data);
199  const uint8_t* const end = begin + length;
200  for (const uint8_t* iter = begin; iter < end; ++iter) {
201  hash_ = (hash_ ^ *iter) * 1099511628211u;
202  }
203  }
204 
205  explicit operator size_t() noexcept {
206  return hash_;
207  }
208 
209  private:
210  static_assert(sizeof(result_type) == (64 / 8), "We require a 64-bit size_t");
211  result_type hash_{0xcbf29ce484222325u};
212 };
213 } // namespace detail
214 
215 /// The default HashAlgorithm concept implementation across Drake. This is
216 /// guaranteed to have a result_type of size_t to be compatible with std::hash.
218 
219 /// The default hashing functor, akin to std::hash.
221 
222 /// An adapter that forwards the HashAlgorithm::operator(data, length) function
223 /// concept into a runtime-provided std::function of the same signature. This
224 /// is useful for passing a concrete HashAlgorithm implementation through into
225 /// non-templated code, such as with an Impl or Cell pattern.
227  /// A std::function whose signature matches HashAlgorithm::operator().
228  using Func = std::function<void(const void*, size_t)>;
229 
230  /// Create a delegating hasher that calls the given @p func.
231  explicit DelegatingHasher(Func func) : func_(std::move(func)) {
232  // In order for operator() to be noexcept, it must have a non-empty func_.
233  DRAKE_THROW_UNLESS(static_cast<bool>(func_));
234  }
235 
236  /// Append [data, data + length) bytes into the wrapped algorithm.
237  void operator()(const void* data, size_t length) noexcept {
238  func_(data, length);
239  }
240 
241  private:
242  const Func func_;
243 };
244 
245 } // namespace drake
An adapter that forwards the HashAlgorithm::operator(data, length) function concept into a runtime-pr...
Definition: hash.h:226
bool isnan(const Eigen::AutoDiffScalar< DerType > &x)
Overloads isnan to mimic std::isnan from <cmath>.
Definition: autodiff_overloads.h:52
api::GeoPosition end
Definition: multilane_loader_test.cc:70
Definition: automotive_demo.cc:89
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:195
DelegatingHasher(Func func)
Create a delegating hasher that calls the given func.
Definition: hash.h:231
#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
int value
Definition: copyable_unique_ptr_test.cc:61
void operator()(const void *data, size_t length) noexcept
Definition: hash.h:197
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:77
double length
Definition: multilane_loader_test.cc:71
A hashing functor, somewhat like std::hash.
Definition: hash.h:178
result_type operator()(const T &item) const noexcept
Definition: hash.h:182
typename HashAlgorithm::result_type result_type
Definition: hash.h:179
void operator()(const void *data, size_t length) noexcept
Append [data, data + length) bytes into the wrapped algorithm.
Definition: hash.h:237
The FNV1a hash algorithm, used for hash_append generic hashing.
Definition: hash.h:193
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:228
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:130
int data
Definition: value_test.cc:19