diff options
Diffstat (limited to 'absl/container/internal/hash_function_defaults.h')
-rw-r--r-- | absl/container/internal/hash_function_defaults.h | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/absl/container/internal/hash_function_defaults.h b/absl/container/internal/hash_function_defaults.h new file mode 100644 index 0000000..dd6cd8f --- /dev/null +++ b/absl/container/internal/hash_function_defaults.h @@ -0,0 +1,148 @@ +// 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. +// +// Define the default Hash and Eq functions for SwissTable containers. +// +// std::hash<T> and std::equal_to<T> are not appropriate hash and equal +// functions for SwissTable containers. There are two reasons for this. +// +// SwissTable containers are power of 2 sized containers: +// +// This means they use the lower bits of the hash value to find the slot for +// each entry. The typical hash function for integral types is the identity. +// This is a very weak hash function for SwissTable and any power of 2 sized +// hashtable implementation which will lead to excessive collisions. For +// SwissTable we use murmur3 style mixing to reduce collisions to a minimum. +// +// SwissTable containers support heterogeneous lookup: +// +// In order to make heterogeneous lookup work, hash and equal functions must be +// polymorphic. At the same time they have to satisfy the same requirements the +// C++ standard imposes on hash functions and equality operators. That is: +// +// if hash_default_eq<T>(a, b) returns true for any a and b of type T, then +// hash_default_hash<T>(a) must equal hash_default_hash<T>(b) +// +// For SwissTable containers this requirement is relaxed to allow a and b of +// any and possibly different types. Note that like the standard the hash and +// equal functions are still bound to T. This is important because some type U +// can be hashed by/tested for equality differently depending on T. A notable +// example is `const char*`. `const char*` is treated as a c-style string when +// the hash function is hash<string> but as a pointer when the hash function is +// hash<void*>. +// +#ifndef ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ +#define ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ + +#include <stdint.h> +#include <cstddef> +#include <memory> +#include <string> +#include <type_traits> + +#include "absl/base/config.h" +#include "absl/hash/hash.h" +#include "absl/strings/string_view.h" + +namespace absl { +namespace container_internal { + +// The hash of an object of type T is computed by using absl::Hash. +template <class T, class E = void> +struct HashEq { + using Hash = absl::Hash<T>; + using Eq = std::equal_to<T>; +}; + +struct StringHash { + using is_transparent = void; + + size_t operator()(absl::string_view v) const { + return absl::Hash<absl::string_view>{}(v); + } +}; + +// Supports heterogeneous lookup for string-like elements. +struct StringHashEq { + using Hash = StringHash; + struct Eq { + using is_transparent = void; + bool operator()(absl::string_view lhs, absl::string_view rhs) const { + return lhs == rhs; + } + }; +}; + +#if defined(HAS_GLOBAL_STRING) +template <> +struct HashEq<std::string> : StringHashEq {}; +#endif +template <> +struct HashEq<std::string> : StringHashEq {}; +template <> +struct HashEq<absl::string_view> : StringHashEq {}; + +// Supports heterogeneous lookup for pointers and smart pointers. +template <class T> +struct HashEq<T*> { + struct Hash { + using is_transparent = void; + template <class U> + size_t operator()(const U& ptr) const { + return absl::Hash<const T*>{}(HashEq::ToPtr(ptr)); + } + }; + struct Eq { + using is_transparent = void; + template <class A, class B> + bool operator()(const A& a, const B& b) const { + return HashEq::ToPtr(a) == HashEq::ToPtr(b); + } + }; + + private: + static const T* ToPtr(const T* ptr) { return ptr; } + template <class U, class D> + static const T* ToPtr(const std::unique_ptr<U, D>& ptr) { + return ptr.get(); + } + template <class U> + static const T* ToPtr(const std::shared_ptr<U>& ptr) { + return ptr.get(); + } +}; + +template <class T, class D> +struct HashEq<std::unique_ptr<T, D>> : HashEq<T*> {}; +template <class T> +struct HashEq<std::shared_ptr<T>> : HashEq<T*> {}; + +// This header's visibility is restricted. If you need to access the default +// hasher please use the container's ::hasher alias instead. +// +// Example: typename Hash = typename absl::flat_hash_map<K, V>::hasher +template <class T> +using hash_default_hash = typename container_internal::HashEq<T>::Hash; + +// This header's visibility is restricted. If you need to access the default +// key equal please use the container's ::key_equal alias instead. +// +// Example: typename Eq = typename absl::flat_hash_map<K, V, Hash>::key_equal +template <class T> +using hash_default_eq = typename container_internal::HashEq<T>::Eq; + +} // namespace container_internal +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ |