hash.h
Go to the documentation of this file.
1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // -----------------------------------------------------------------------------
16 // File: hash.h
17 // -----------------------------------------------------------------------------
18 //
19 // This header file defines the Abseil `hash` library and the Abseil hashing
20 // framework. This framework consists of the following:
21 //
22 // * The `absl::Hash` functor, which is used to invoke the hasher within the
23 // Abseil hashing framework. `absl::Hash<T>` supports most basic types and
24 // a number of Abseil types out of the box.
25 // * `AbslHashValue`, an extension point that allows you to extend types to
26 // support Abseil hashing without requiring you to define a hashing
27 // algorithm.
28 // * `HashState`, a type-erased class which implements the manipulation of the
29 // hash state (H) itself, contains member functions `combine()` and
30 // `combine_contiguous()`, which you can use to contribute to an existing
31 // hash state when hashing your types.
32 //
33 // Unlike `std::hash` or other hashing frameworks, the Abseil hashing framework
34 // provides most of its utility by abstracting away the hash algorithm (and its
35 // implementation) entirely. Instead, a type invokes the Abseil hashing
36 // framework by simply combining its state with the state of known, hashable
37 // types. Hashing of that combined state is separately done by `absl::Hash`.
38 //
39 // One should assume that a hash algorithm is chosen randomly at the start of
40 // each process. E.g., absl::Hash<int>()(9) in one process and
41 // absl::Hash<int>()(9) in another process are likely to differ.
42 //
43 // Example:
44 //
45 // // Suppose we have a class `Circle` for which we want to add hashing:
46 // class Circle {
47 // public:
48 // ...
49 // private:
50 // std::pair<int, int> center_;
51 // int radius_;
52 // };
53 //
54 // // To add hashing support to `Circle`, we simply need to add a free
55 // // (non-member) function `AbslHashValue()`, and return the combined hash
56 // // state of the existing hash state and the class state. You can add such a
57 // // free function using a friend declaration within the body of the class:
58 // class Circle {
59 // public:
60 // ...
61 // template <typename H>
62 // friend H AbslHashValue(H h, const Circle& c) {
63 // return H::combine(std::move(h), c.center_, c.radius_);
64 // }
65 // ...
66 // };
67 //
68 // For more information, see Adding Type Support to `absl::Hash` below.
69 //
70 #ifndef ABSL_HASH_HASH_H_
71 #define ABSL_HASH_HASH_H_
72 
74 
75 namespace absl {
76 
77 // -----------------------------------------------------------------------------
78 // `absl::Hash`
79 // -----------------------------------------------------------------------------
80 //
81 // `absl::Hash<T>` is a convenient general-purpose hash functor for any type `T`
82 // satisfying any of the following conditions (in order):
83 //
84 // * T is an arithmetic or pointer type
85 // * T defines an overload for `AbslHashValue(H, const T&)` for an arbitrary
86 // hash state `H`.
87 // - T defines a specialization of `HASH_NAMESPACE::hash<T>`
88 // - T defines a specialization of `std::hash<T>`
89 //
90 // `absl::Hash` intrinsically supports the following types:
91 //
92 // * All integral types (including bool)
93 // * All enum types
94 // * All floating-point types (although hashing them is discouraged)
95 // * All pointer types, including nullptr_t
96 // * std::pair<T1, T2>, if T1 and T2 are hashable
97 // * std::tuple<Ts...>, if all the Ts... are hashable
98 // * std::unique_ptr and std::shared_ptr
99 // * All string-like types including:
100 // * std::string
101 // * std::string_view (as well as any instance of std::basic_string that
102 // uses char and std::char_traits)
103 // * All the standard sequence containers (provided the elements are hashable)
104 // * All the standard ordered associative containers (provided the elements are
105 // hashable)
106 // * absl types such as the following:
107 // * absl::string_view
108 // * absl::InlinedVector
109 // * absl::FixedArray
110 // * absl::uint128
111 // * absl::Time, absl::Duration, and absl::TimeZone
112 //
113 // Note: the list above is not meant to be exhaustive. Additional type support
114 // may be added, in which case the above list will be updated.
115 //
116 // -----------------------------------------------------------------------------
117 // absl::Hash Invocation Evaluation
118 // -----------------------------------------------------------------------------
119 //
120 // When invoked, `absl::Hash<T>` searches for supplied hash functions in the
121 // following order:
122 //
123 // * Natively supported types out of the box (see above)
124 // * Types for which an `AbslHashValue()` overload is provided (such as
125 // user-defined types). See "Adding Type Support to `absl::Hash`" below.
126 // * Types which define a `HASH_NAMESPACE::hash<T>` specialization (aka
127 // `__gnu_cxx::hash<T>` for gcc/Clang or `stdext::hash<T>` for MSVC)
128 // * Types which define a `std::hash<T>` specialization
129 //
130 // The fallback to legacy hash functions exists mainly for backwards
131 // compatibility. If you have a choice, prefer defining an `AbslHashValue`
132 // overload instead of specializing any legacy hash functors.
133 //
134 // -----------------------------------------------------------------------------
135 // The Hash State Concept, and using `HashState` for Type Erasure
136 // -----------------------------------------------------------------------------
137 //
138 // The `absl::Hash` framework relies on the Concept of a "hash state." Such a
139 // hash state is used in several places:
140 //
141 // * Within existing implementations of `absl::Hash<T>` to store the hashed
142 // state of an object. Note that it is up to the implementation how it stores
143 // such state. A hash table, for example, may mix the state to produce an
144 // integer value; a testing framework may simply hold a vector of that state.
145 // * Within implementations of `AbslHashValue()` used to extend user-defined
146 // types. (See "Adding Type Support to absl::Hash" below.)
147 // * Inside a `HashState`, providing type erasure for the concept of a hash
148 // state, which you can use to extend the `absl::Hash` framework for types
149 // that are otherwise difficult to extend using `AbslHashValue()`. (See the
150 // `HashState` class below.)
151 //
152 // The "hash state" concept contains two member functions for mixing hash state:
153 //
154 // * `H::combine(state, values...)`
155 //
156 // Combines an arbitrary number of values into a hash state, returning the
157 // updated state. Note that the existing hash state is move-only and must be
158 // passed by value.
159 //
160 // Each of the value types T must be hashable by H.
161 //
162 // NOTE:
163 //
164 // state = H::combine(std::move(state), value1, value2, value3);
165 //
166 // must be guaranteed to produce the same hash expansion as
167 //
168 // state = H::combine(std::move(state), value1);
169 // state = H::combine(std::move(state), value2);
170 // state = H::combine(std::move(state), value3);
171 //
172 // * `H::combine_contiguous(state, data, size)`
173 //
174 // Combines a contiguous array of `size` elements into a hash state,
175 // returning the updated state. Note that the existing hash state is
176 // move-only and must be passed by value.
177 //
178 // NOTE:
179 //
180 // state = H::combine_contiguous(std::move(state), data, size);
181 //
182 // need NOT be guaranteed to produce the same hash expansion as a loop
183 // (it may perform internal optimizations). If you need this guarantee, use a
184 // loop instead.
185 //
186 // -----------------------------------------------------------------------------
187 // Adding Type Support to `absl::Hash`
188 // -----------------------------------------------------------------------------
189 //
190 // To add support for your user-defined type, add a proper `AbslHashValue()`
191 // overload as a free (non-member) function. The overload will take an
192 // existing hash state and should combine that state with state from the type.
193 //
194 // Example:
195 //
196 // template <typename H>
197 // H AbslHashValue(H state, const MyType& v) {
198 // return H::combine(std::move(state), v.field1, ..., v.fieldN);
199 // }
200 //
201 // where `(field1, ..., fieldN)` are the members you would use on your
202 // `operator==` to define equality.
203 //
204 // Notice that `AbslHashValue` is not a class member, but an ordinary function.
205 // An `AbslHashValue` overload for a type should only be declared in the same
206 // file and namespace as said type. The proper `AbslHashValue` implementation
207 // for a given type will be discovered via ADL.
208 //
209 // Note: unlike `std::hash', `absl::Hash` should never be specialized. It must
210 // only be extended by adding `AbslHashValue()` overloads.
211 //
212 template <typename T>
214 
215 // HashState
216 //
217 // A type erased version of the hash state concept, for use in user-defined
218 // `AbslHashValue` implementations that can't use templates (such as PImpl
219 // classes, virtual functions, etc.). The type erasure adds overhead so it
220 // should be avoided unless necessary.
221 //
222 // Note: This wrapper will only erase calls to:
223 // combine_contiguous(H, const unsigned char*, size_t)
224 //
225 // All other calls will be handled internally and will not invoke overloads
226 // provided by the wrapped class.
227 //
228 // Users of this class should still define a template `AbslHashValue` function,
229 // but can use `absl::HashState::Create(&state)` to erase the type of the hash
230 // state and dispatch to their private hashing logic.
231 //
232 // This state can be used like any other hash state. In particular, you can call
233 // `HashState::combine()` and `HashState::combine_contiguous()` on it.
234 //
235 // Example:
236 //
237 // class Interface {
238 // public:
239 // template <typename H>
240 // friend H AbslHashValue(H state, const Interface& value) {
241 // state = H::combine(std::move(state), std::type_index(typeid(*this)));
242 // value.HashValue(absl::HashState::Create(&state));
243 // return state;
244 // }
245 // private:
246 // virtual void HashValue(absl::HashState state) const = 0;
247 // };
248 //
249 // class Impl : Interface {
250 // private:
251 // void HashValue(absl::HashState state) const override {
252 // absl::HashState::combine(std::move(state), v1_, v2_);
253 // }
254 // int v1_;
255 // std::string v2_;
256 // };
257 class HashState : public hash_internal::HashStateBase<HashState> {
258  public:
259  // HashState::Create()
260  //
261  // Create a new `HashState` instance that wraps `state`. All calls to
262  // `combine()` and `combine_contiguous()` on the new instance will be
263  // redirected to the original `state` object. The `state` object must outlive
264  // the `HashState` instance.
265  template <typename T>
266  static HashState Create(T* state) {
267  HashState s;
268  s.Init(state);
269  return s;
270  }
271 
272  HashState(const HashState&) = delete;
273  HashState& operator=(const HashState&) = delete;
274  HashState(HashState&&) = default;
275  HashState& operator=(HashState&&) = default;
276 
277  // HashState::combine()
278  //
279  // Combines an arbitrary number of values into a hash state, returning the
280  // updated state.
281  using HashState::HashStateBase::combine;
282 
283  // HashState::combine_contiguous()
284  //
285  // Combines a contiguous array of `size` elements into a hash state, returning
286  // the updated state.
288  const unsigned char* first, size_t size) {
289  hash_state.combine_contiguous_(hash_state.state_, first, size);
290  return hash_state;
291  }
292  using HashState::HashStateBase::combine_contiguous;
293 
294  private:
295  HashState() = default;
296 
297  template <typename T>
298  static void CombineContiguousImpl(void* p, const unsigned char* first,
299  size_t size) {
300  T& state = *static_cast<T*>(p);
301  state = T::combine_contiguous(std::move(state), first, size);
302  }
303 
304  template <typename T>
305  void Init(T* state) {
306  state_ = state;
307  combine_contiguous_ = &CombineContiguousImpl<T>;
308  }
309 
310  // Do not erase an already erased state.
311  void Init(HashState* state) {
312  state_ = state->state_;
314  }
315 
316  void* state_;
317  void (*combine_contiguous_)(void*, const unsigned char*, size_t);
318 };
319 
320 } // namespace absl
321 
322 #endif // ABSL_HASH_HASH_H_
HashState & operator=(const HashState &)=delete
static HashState Create(T *state)
Definition: hash.h:266
void Init(T *state)
Definition: hash.h:305
void * state_
Definition: hash.h:316
HashState()=default
Definition: algorithm.h:29
static HashState combine_contiguous(HashState hash_state, const unsigned char *first, size_t size)
Definition: hash.h:287
static void CombineContiguousImpl(void *p, const unsigned char *first, size_t size)
Definition: hash.h:298
uintptr_t size
void Init(HashState *state)
Definition: hash.h:311
void(* combine_contiguous_)(void *, const unsigned char *, size_t)
Definition: hash.h:317
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:18