summaryrefslogtreecommitdiff
path: root/absl/hash/hash.h
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2018-09-27 12:24:54 -0700
committerGravatar Derek Mauro <dmauro@google.com>2018-09-27 15:28:12 -0400
commit48cd2c3f351ff188bc85684b84a91b6e6d17d896 (patch)
tree6f92b0cbb0f8282b7df1cd567cb66406fbbb6f80 /absl/hash/hash.h
parente291c279e458761e77a69b09b129d3d1e81f1e80 (diff)
Export of internal Abseil changes.
-- 4eacae3ff1b14b1d309e8092185bc10e8a6203cf by Derek Mauro <dmauro@google.com>: Release SwissTable - a fast, efficient, cache-friendly hash table. https://www.youtube.com/watch?v=ncHmEUmJZf4 PiperOrigin-RevId: 214816527 -- df8c3dfab3cfb2f4365909a84d0683b193cfbb11 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 214785288 -- 1eabd5266bbcebc33eecc91e5309b751856a75c8 by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 214722931 -- 2ebbfac950f83146b46253038e7dd7dcde9f2951 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 214701684 GitOrigin-RevId: 4eacae3ff1b14b1d309e8092185bc10e8a6203cf Change-Id: I9ba64e395b22ad7863213d157b8019b082adc19d
Diffstat (limited to 'absl/hash/hash.h')
-rw-r--r--absl/hash/hash.h312
1 files changed, 312 insertions, 0 deletions
diff --git a/absl/hash/hash.h b/absl/hash/hash.h
new file mode 100644
index 00000000..c7ba4c2b
--- /dev/null
+++ b/absl/hash/hash.h
@@ -0,0 +1,312 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// -----------------------------------------------------------------------------
+// File: hash.h
+// -----------------------------------------------------------------------------
+//
+// This header file defines the Abseil `hash` library and the Abseil hashing
+// framework. This framework consists of the following:
+//
+// * The `absl::Hash` functor, which is used to invoke the hasher within the
+// Abseil hashing framework. `absl::Hash<T>` supports most basic types and
+// a number of Abseil types out of the box.
+// * `AbslHashValue`, an extension point that allows you to extend types to
+// support Abseil hashing without requiring you to define a hashing
+// algorithm.
+// * `HashState`, a type-erased class which implement the manipulation of the
+// hash state (H) itself. containing member functions `combine()` and
+// `combine_contiguous()`, which you can use to contribute to an existing
+// hash state when hashing your types.
+//
+// Unlike `std::hash` or other hashing frameworks, the Abseil hashing framework
+// provides most of its utility by abstracting away the hash algorithm (and its
+// implementation) entirely. Instead, a type invokes the Abseil hashing
+// framework by simply combining its state with the state of known, hashable
+// types. Hashing of that combined state is separately done by `absl::Hash`.
+//
+// Example:
+//
+// // Suppose we have a class `Circle` for which we want to add hashing
+// class Circle {
+// public:
+// ...
+// private:
+// std::pair<int, int> center_;
+// int radius_;
+// };
+//
+// // To add hashing support to `Circle`, we simply need to add an ordinary
+// // function `AbslHashValue()`, and return the combined hash state of the
+// // existing hash state and the class state:
+//
+// template <typename H>
+// friend H AbslHashValue(H h, const Circle& c) {
+// return H::combine(std::move(h), c.center_, c.radius_);
+// }
+//
+// For more information, see Adding Type Support to `absl::Hash` below.
+//
+#ifndef ABSL_HASH_HASH_H_
+#define ABSL_HASH_HASH_H_
+
+#include "absl/hash/internal/hash.h"
+
+namespace absl {
+
+// -----------------------------------------------------------------------------
+// `absl::Hash`
+// -----------------------------------------------------------------------------
+//
+// `absl::Hash<T>` is a convenient general-purpose hash functor for a type `T`
+// satisfying any of the following conditions (in order):
+//
+// * T is an arithmetic or pointer type
+// * T defines an overload for `AbslHashValue(H, const T&)` for an arbitrary
+// hash state `H`.
+// - T defines a specialization of `HASH_NAMESPACE::hash<T>`
+// - T defines a specialization of `std::hash<T>`
+//
+// `absl::Hash` intrinsically supports the following types:
+//
+// * All integral types (including bool)
+// * All enum types
+// * All floating-point types (although hashing them is discouraged)
+// * All pointer types, including nullptr_t
+// * std::pair<T1, T2>, if T1 and T2 are hashable
+// * std::tuple<Ts...>, if all the Ts... are hashable
+// * std::unique_ptr and std::shared_ptr
+// * All string-like types including:
+// * std::string
+// * std::string_view (as well as any instance of std::basic_string that
+// uses char and std::char_traits)
+// * All the standard sequence containers (provided the elements are hashable)
+// * All the standard ordered associative containers (provided the elements are
+// hashable)
+// * absl types such as the following:
+// * absl::string_view
+// * absl::InlinedVector
+// * absl::FixedArray
+// * absl::unit128
+// * absl::Time, absl::Duration, and absl::TimeZone
+//
+// Note: the list above is not meant to be exhaustive. Additional type support
+// may be added, in which case the above list will be updated.
+//
+// -----------------------------------------------------------------------------
+// absl::Hash Invocation Evaluation
+// -----------------------------------------------------------------------------
+//
+// When invoked, `absl::Hash<T>` searches for supplied hash functions in the
+// following order:
+//
+// * Natively supported types out of the box (see above)
+// * Types for which an `AbslHashValue()` overload is provided (such as
+// user-defined types). See "Adding Type Support to `absl::Hash`" below.
+// * Types which define a `HASH_NAMESPACE::hash<T>` specialization (aka
+// `__gnu_cxx::hash<T>` for gcc/Clang or `stdext::hash<T>` for MSVC)
+// * Types which define a `std::hash<T>` specialization
+//
+// The fallback to legacy hash functions exists mainly for backwards
+// compatibility. If you have a choice, prefer defining an `AbslHashValue`
+// overload instead of specializing any legacy hash functors.
+//
+// -----------------------------------------------------------------------------
+// The Hash State Concept, and using `HashState` for Type Erasure
+// -----------------------------------------------------------------------------
+//
+// The `absl::Hash` framework relies on the Concept of a "hash state." Such a
+// hash state is used in several places:
+//
+// * Within existing implementations of `absl::Hash<T>` to store the hashed
+// state of an object. Note that it is up to the implementation how it stores
+// such state. A hash table, for example, may mix the state to produce an
+// integer value; a testing framework may simply hold a vector of that state.
+// * Within implementations of `AbslHashValue()` used to extend user-defined
+// types. (See "Adding Type Support to absl::Hash" below.)
+// * Inside a `HashState`, providing type erasure for the concept of a hash
+// state, which you can use to extend the `absl::Hash` framework for types
+// that are otherwise difficult to extend using `AbslHashValue()`. (See the
+// `HashState` class below.)
+//
+// The "hash state" concept contains two member functions for mixing hash state:
+//
+// * `H::combine()`
+//
+// Combines an arbitrary number of values into a hash state, returning the
+// updated state. Note that the existing hash state is move-only and must be
+// passed by value.
+//
+// Each of the value types T must be hashable by H.
+//
+// NOTE:
+//
+// state = H::combine(std::move(state), value1, value2, value3);
+//
+// must be guaranteed to produce the same hash expansion as
+//
+// state = H::combine(std::move(state), value1);
+// state = H::combine(std::move(state), value2);
+// state = H::combine(std::move(state), value3);
+//
+// * `H::combine_contiguous()`
+//
+// Combines a contiguous array of `size` elements into a hash state,
+// returning the updated state. Note that the existing hash state is
+// move-only and must be passed by value.
+//
+// NOTE:
+//
+// state = H::combine_contiguous(std::move(state), data, size);
+//
+// need NOT be guaranteed to produce the same hash expansion as a loop
+// (it may perform internal optimizations). If you need this guarantee, use a
+// loop instead.
+//
+// -----------------------------------------------------------------------------
+// Adding Type Support to `absl::Hash`
+// -----------------------------------------------------------------------------
+//
+// To add support for your user-defined type, add a proper `AbslHashValue()`
+// overload as a free (non-member) function. The overload will take an
+// existing hash state and should combine that state with state from the type.
+//
+// Example:
+//
+// template <typename H>
+// H AbslHashValue(H state, const MyType& v) {
+// return H::combine(std::move(state), v.field1, ..., v.fieldN);
+// }
+//
+// where `(field1, ..., fieldN)` are the members you would use on your
+// `operator==` to define equality.
+//
+// Notice that `AbslHashValue` is not a class member, but an ordinary function.
+// An `AbslHashValue` overload for a type should only be declared in the same
+// file and namespace as said type. The proper `AbslHashValue` implementation
+// for a given type will be discovered via ADL.
+//
+// Note: unlike `std::hash', `absl::Hash` should never be specialized. It must
+// only be extended by adding `AbslHashValue()` overloads.
+//
+template <typename T>
+using Hash = absl::hash_internal::Hash<T>;
+
+// HashState
+//
+// A type erased version of the hash state concept, for use in user-defined
+// `AbslHashValue` implementations that can't use templates (such as PImpl
+// classes, virtual functions, etc.). The type erasure adds overhead so it
+// should be avoided unless necessary.
+//
+// Note: This wrapper will only erase calls to:
+// combine_contiguous(H, const unsigned char*, size_t)
+//
+// All other calls will be handled internally and will not invoke overloads
+// provided by the wrapped class.
+//
+// Users of this class should still define a template `AbslHashValue` function,
+// but can use `absl::HashState::Create(&state)` to erase the type of the hash
+// state and dispatch to their private hashing logic.
+//
+// This state can be used like any other hash state. In particular, you can call
+// `HashState::combine()` and `HashState::combine_contiguous()` on it.
+//
+// Example:
+//
+// class Interface {
+// public:
+// template <typename H>
+// friend H AbslHashValue(H state, const Interface& value) {
+// state = H::combine(std::move(state), std::type_index(typeid(*this)));
+// value.HashValue(absl::HashState::Create(&state));
+// return state;
+// }
+// private:
+// virtual void HashValue(absl::HashState state) const = 0;
+// };
+//
+// class Impl : Interface {
+// private:
+// void HashValue(absl::HashState state) const override {
+// absl::HashState::combine(std::move(state), v1_, v2_);
+// }
+// int v1_;
+// string v2_;
+// };
+class HashState : public hash_internal::HashStateBase<HashState> {
+ public:
+ // HashState::Create()
+ //
+ // Create a new `HashState` instance that wraps `state`. All calls to
+ // `combine()` and `combine_contiguous()` on the new instance will be
+ // redirected to the original `state` object. The `state` object must outlive
+ // the `HashState` instance.
+ template <typename T>
+ static HashState Create(T* state) {
+ HashState s;
+ s.Init(state);
+ return s;
+ }
+
+ HashState(const HashState&) = delete;
+ HashState& operator=(const HashState&) = delete;
+ HashState(HashState&&) = default;
+ HashState& operator=(HashState&&) = default;
+
+ // HashState::combine()
+ //
+ // Combines an arbitrary number of values into a hash state, returning the
+ // updated state.
+ using HashState::HashStateBase::combine;
+
+ // HashState::combine_contiguous()
+ //
+ // Combines a contiguous array of `size` elements into a hash state, returning
+ // the updated state.
+ static HashState combine_contiguous(HashState hash_state,
+ const unsigned char* first, size_t size) {
+ hash_state.combine_contiguous_(hash_state.state_, first, size);
+ return hash_state;
+ }
+ using HashState::HashStateBase::combine_contiguous;
+
+ private:
+ HashState() = default;
+
+ template <typename T>
+ static void CombineContiguousImpl(void* p, const unsigned char* first,
+ size_t size) {
+ T& state = *static_cast<T*>(p);
+ state = T::combine_contiguous(std::move(state), first, size);
+ }
+
+ template <typename T>
+ void Init(T* state) {
+ state_ = state;
+ combine_contiguous_ = &CombineContiguousImpl<T>;
+ }
+
+ // Do not erase an already erased state.
+ void Init(HashState* state) {
+ state_ = state->state_;
+ combine_contiguous_ = state->combine_contiguous_;
+ }
+
+ void* state_;
+ void (*combine_contiguous_)(void*, const unsigned char*, size_t);
+};
+
+} // namespace absl
+#endif // ABSL_HASH_HASH_H_