container/internal/hash_function_defaults.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // Define the default Hash and Eq functions for SwissTable containers.
0016 //
0017 // std::hash<T> and std::equal_to<T> are not appropriate hash and equal
0018 // functions for SwissTable containers. There are two reasons for this.
0019 //
0020 // SwissTable containers are power of 2 sized containers:
0021 //
0022 // This means they use the lower bits of the hash value to find the slot for
0023 // each entry. The typical hash function for integral types is the identity.
0024 // This is a very weak hash function for SwissTable and any power of 2 sized
0025 // hashtable implementation which will lead to excessive collisions. For
0026 // SwissTable we use murmur3 style mixing to reduce collisions to a minimum.
0027 //
0028 // SwissTable containers support heterogeneous lookup:
0029 //
0030 // In order to make heterogeneous lookup work, hash and equal functions must be
0031 // polymorphic. At the same time they have to satisfy the same requirements the
0032 // C++ standard imposes on hash functions and equality operators. That is:
0033 //
0034 //   if hash_default_eq<T>(a, b) returns true for any a and b of type T, then
0035 //   hash_default_hash<T>(a) must equal hash_default_hash<T>(b)
0036 //
0037 // For SwissTable containers this requirement is relaxed to allow a and b of
0038 // any and possibly different types. Note that like the standard the hash and
0039 // equal functions are still bound to T. This is important because some type U
0040 // can be hashed by/tested for equality differently depending on T. A notable
0041 // example is `const char*`. `const char*` is treated as a c-style string when
0042 // the hash function is hash<std::string> but as a pointer when the hash
0043 // function is hash<void*>.
0044 //
0045 #ifndef ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_
0046 #define ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_
0047
0048 #include <cstddef>
0049 #include <functional>
0050 #include <memory>
0051 #include <string>
0052 #include <type_traits>
0053
0054 #include "absl/base/config.h"
0055 #include "absl/container/internal/common.h"
0056 #include "absl/hash/hash.h"
0057 #include "absl/meta/type_traits.h"
0058 #include "absl/strings/cord.h"
0059 #include "absl/strings/string_view.h"
0060
0061 #ifdef ABSL_HAVE_STD_STRING_VIEW
0062 #include <string_view>
0063 #endif
0064
0065 namespace absl {
0066 ABSL_NAMESPACE_BEGIN
0067 namespace container_internal {
0068
0069 // The hash of an object of type T is computed by using absl::Hash.
0070 template <class T, class E = void>
0071 struct HashEq {
0072   using Hash = absl::Hash<T>;
0073   using Eq = std::equal_to<T>;
0074 };
0075
0076 struct StringHash {
0077   using is_transparent = void;
0078
0079   size_t operator()(absl::string_view v) const {
0080     return absl::Hash<absl::string_view>{}(v);
0081   }
0082   size_t operator()(const absl::Cord& v) const {
0083     return absl::Hash<absl::Cord>{}(v);
0084   }
0085 };
0086
0087 struct StringEq {
0088   using is_transparent = void;
0089   bool operator()(absl::string_view lhs, absl::string_view rhs) const {
0090     return lhs == rhs;
0091   }
0092   bool operator()(const absl::Cord& lhs, const absl::Cord& rhs) const {
0093     return lhs == rhs;
0094   }
0095   bool operator()(const absl::Cord& lhs, absl::string_view rhs) const {
0096     return lhs == rhs;
0097   }
0098   bool operator()(absl::string_view lhs, const absl::Cord& rhs) const {
0099     return lhs == rhs;
0100   }
0101 };
0102
0103 // Supports heterogeneous lookup for string-like elements.
0104 struct StringHashEq {
0105   using Hash = StringHash;
0106   using Eq = StringEq;
0107 };
0108
0109 template <>
0110 struct HashEq<std::string> : StringHashEq {};
0111 template <>
0112 struct HashEq<absl::string_view> : StringHashEq {};
0113 template <>
0114 struct HashEq<absl::Cord> : StringHashEq {};
0115
0116 #ifdef ABSL_HAVE_STD_STRING_VIEW
0117
0118 template <typename TChar>
0119 struct BasicStringHash {
0120   using is_transparent = void;
0121
0122   size_t operator()(std::basic_string_view<TChar> v) const {
0123     return absl::Hash<std::basic_string_view<TChar>>{}(v);
0124   }
0125 };
0126
0127 template <typename TChar>
0128 struct BasicStringEq {
0129   using is_transparent = void;
0130   bool operator()(std::basic_string_view<TChar> lhs,
0131                   std::basic_string_view<TChar> rhs) const {
0132     return lhs == rhs;
0133   }
0134 };
0135
0136 // Supports heterogeneous lookup for w/u16/u32 string + string_view + char*.
0137 template <typename TChar>
0138 struct BasicStringHashEq {
0139   using Hash = BasicStringHash<TChar>;
0140   using Eq = BasicStringEq<TChar>;
0141 };
0142
0143 template <>
0144 struct HashEq<std::wstring> : BasicStringHashEq<wchar_t> {};
0145 template <>
0146 struct HashEq<std::wstring_view> : BasicStringHashEq<wchar_t> {};
0147 template <>
0148 struct HashEq<std::u16string> : BasicStringHashEq<char16_t> {};
0149 template <>
0150 struct HashEq<std::u16string_view> : BasicStringHashEq<char16_t> {};
0151 template <>
0152 struct HashEq<std::u32string> : BasicStringHashEq<char32_t> {};
0153 template <>
0154 struct HashEq<std::u32string_view> : BasicStringHashEq<char32_t> {};
0155
0156 #endif  // ABSL_HAVE_STD_STRING_VIEW
0157
0158 // Supports heterogeneous lookup for pointers and smart pointers.
0159 template <class T>
0160 struct HashEq<T*> {
0161   struct Hash {
0162     using is_transparent = void;
0163     template <class U>
0164     size_t operator()(const U& ptr) const {
0165       return absl::Hash<const T*>{}(HashEq::ToPtr(ptr));
0166     }
0167   };
0168   struct Eq {
0169     using is_transparent = void;
0170     template <class A, class B>
0171     bool operator()(const A& a, const B& b) const {
0172       return HashEq::ToPtr(a) == HashEq::ToPtr(b);
0173     }
0174   };
0175
0176  private:
0177   static const T* ToPtr(const T* ptr) { return ptr; }
0178   template <class U, class D>
0179   static const T* ToPtr(const std::unique_ptr<U, D>& ptr) {
0180     return ptr.get();
0181   }
0182   template <class U>
0183   static const T* ToPtr(const std::shared_ptr<U>& ptr) {
0184     return ptr.get();
0185   }
0186 };
0187
0188 template <class T, class D>
0189 struct HashEq<std::unique_ptr<T, D>> : HashEq<T*> {};
0190 template <class T>
0191 struct HashEq<std::shared_ptr<T>> : HashEq<T*> {};
0192
0193 template <typename T, typename E = void>
0194 struct HasAbslContainerHash : std::false_type {};
0195
0196 template <typename T>
0197 struct HasAbslContainerHash<T, absl::void_t<typename T::absl_container_hash>>
0198     : std::true_type {};
0199
0200 template <typename T, typename E = void>
0201 struct HasAbslContainerEq : std::false_type {};
0202
0203 template <typename T>
0204 struct HasAbslContainerEq<T, absl::void_t<typename T::absl_container_eq>>
0205     : std::true_type {};
0206
0207 template <typename T, typename E = void>
0208 struct AbslContainerEq {
0209   using type = std::equal_to<>;
0210 };
0211
0212 template <typename T>
0213 struct AbslContainerEq<
0214     T, typename std::enable_if_t<HasAbslContainerEq<T>::value>> {
0215   using type = typename T::absl_container_eq;
0216 };
0217
0218 template <typename T, typename E = void>
0219 struct AbslContainerHash {
0220   using type = void;
0221 };
0222
0223 template <typename T>
0224 struct AbslContainerHash<
0225     T, typename std::enable_if_t<HasAbslContainerHash<T>::value>> {
0226   using type = typename T::absl_container_hash;
0227 };
0228
0229 // HashEq specialization for user types that provide `absl_container_hash` and
0230 // (optionally) `absl_container_eq`. This specialization allows user types to
0231 // provide heterogeneous lookup without requiring to explicitly specify Hash/Eq
0232 // type arguments in unordered Abseil containers.
0233 //
0234 // Both `absl_container_hash` and `absl_container_eq` should be transparent
0235 // (have inner is_transparent type). While there is no technical reason to
0236 // restrict to transparent-only types, there is also no feasible use case when
0237 // it shouldn't be transparent - it is easier to relax the requirement later if
0238 // such a case arises rather than restricting it.
0239 //
0240 // If type provides only `absl_container_hash` then `eq` part will be
0241 // `std::equal_to<void>`.
0242 //
0243 // User types are not allowed to provide only a `Eq` part as there is no
0244 // feasible use case for this behavior - if Hash should be a default one then Eq
0245 // should be an equivalent to the `std::equal_to<T>`.
0246 template <typename T>
0247 struct HashEq<T, typename std::enable_if_t<HasAbslContainerHash<T>::value>> {
0248   using Hash = typename AbslContainerHash<T>::type;
0249   using Eq = typename AbslContainerEq<T>::type;
0250   static_assert(IsTransparent<Hash>::value,
0251                 "absl_container_hash must be transparent. To achieve it add a "
0252                 "`using is_transparent = void;` clause to this type.");
0253   static_assert(IsTransparent<Eq>::value,
0254                 "absl_container_eq must be transparent. To achieve it add a "
0255                 "`using is_transparent = void;` clause to this type.");
0256 };
0257
0258 // This header's visibility is restricted.  If you need to access the default
0259 // hasher please use the container's ::hasher alias instead.
0260 //
0261 // Example: typename Hash = typename absl::flat_hash_map<K, V>::hasher
0262 template <class T>
0263 using hash_default_hash = typename container_internal::HashEq<T>::Hash;
0264
0265 // This header's visibility is restricted.  If you need to access the default
0266 // key equal please use the container's ::key_equal alias instead.
0267 //
0268 // Example: typename Eq = typename absl::flat_hash_map<K, V, Hash>::key_equal
0269 template <class T>
0270 using hash_default_eq = typename container_internal::HashEq<T>::Eq;
0271
0272 }  // namespace container_internal
0273 ABSL_NAMESPACE_END
0274 }  // namespace absl
0275
0276 #endif  // ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_