hash_function_defaults.h (9328B)
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 // Define the default Hash and Eq functions for SwissTable containers. 16 // 17 // std::hash<T> and std::equal_to<T> are not appropriate hash and equal 18 // functions for SwissTable containers. There are two reasons for this. 19 // 20 // SwissTable containers are power of 2 sized containers: 21 // 22 // This means they use the lower bits of the hash value to find the slot for 23 // each entry. The typical hash function for integral types is the identity. 24 // This is a very weak hash function for SwissTable and any power of 2 sized 25 // hashtable implementation which will lead to excessive collisions. For 26 // SwissTable we use murmur3 style mixing to reduce collisions to a minimum. 27 // 28 // SwissTable containers support heterogeneous lookup: 29 // 30 // In order to make heterogeneous lookup work, hash and equal functions must be 31 // polymorphic. At the same time they have to satisfy the same requirements the 32 // C++ standard imposes on hash functions and equality operators. That is: 33 // 34 // if hash_default_eq<T>(a, b) returns true for any a and b of type T, then 35 // hash_default_hash<T>(a) must equal hash_default_hash<T>(b) 36 // 37 // For SwissTable containers this requirement is relaxed to allow a and b of 38 // any and possibly different types. Note that like the standard the hash and 39 // equal functions are still bound to T. This is important because some type U 40 // can be hashed by/tested for equality differently depending on T. A notable 41 // example is `const char*`. `const char*` is treated as a c-style string when 42 // the hash function is hash<std::string> but as a pointer when the hash 43 // function is hash<void*>. 44 // 45 #ifndef ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ 46 #define ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ 47 48 #include <cstddef> 49 #include <functional> 50 #include <memory> 51 #include <string> 52 #include <type_traits> 53 54 #include "absl/base/config.h" 55 #include "absl/container/internal/common.h" 56 #include "absl/hash/hash.h" 57 #include "absl/meta/type_traits.h" 58 #include "absl/strings/cord.h" 59 #include "absl/strings/string_view.h" 60 61 #ifdef ABSL_HAVE_STD_STRING_VIEW 62 #include <string_view> 63 #endif 64 65 namespace absl { 66 ABSL_NAMESPACE_BEGIN 67 namespace container_internal { 68 69 // The hash of an object of type T is computed by using absl::Hash. 70 template <class T, class E = void> 71 struct HashEq { 72 using Hash = absl::Hash<T>; 73 using Eq = std::equal_to<T>; 74 }; 75 76 struct StringHash { 77 using is_transparent = void; 78 79 size_t operator()(absl::string_view v) const { 80 return absl::Hash<absl::string_view>{}(v); 81 } 82 size_t operator()(const absl::Cord& v) const { 83 return absl::Hash<absl::Cord>{}(v); 84 } 85 }; 86 87 struct StringEq { 88 using is_transparent = void; 89 bool operator()(absl::string_view lhs, absl::string_view rhs) const { 90 return lhs == rhs; 91 } 92 bool operator()(const absl::Cord& lhs, const absl::Cord& rhs) const { 93 return lhs == rhs; 94 } 95 bool operator()(const absl::Cord& lhs, absl::string_view rhs) const { 96 return lhs == rhs; 97 } 98 bool operator()(absl::string_view lhs, const absl::Cord& rhs) const { 99 return lhs == rhs; 100 } 101 }; 102 103 // Supports heterogeneous lookup for string-like elements. 104 struct StringHashEq { 105 using Hash = StringHash; 106 using Eq = StringEq; 107 }; 108 109 template <> 110 struct HashEq<std::string> : StringHashEq {}; 111 template <> 112 struct HashEq<absl::string_view> : StringHashEq {}; 113 template <> 114 struct HashEq<absl::Cord> : StringHashEq {}; 115 116 #ifdef ABSL_HAVE_STD_STRING_VIEW 117 118 template <typename TChar> 119 struct BasicStringHash { 120 using is_transparent = void; 121 122 size_t operator()(std::basic_string_view<TChar> v) const { 123 return absl::Hash<std::basic_string_view<TChar>>{}(v); 124 } 125 }; 126 127 template <typename TChar> 128 struct BasicStringEq { 129 using is_transparent = void; 130 bool operator()(std::basic_string_view<TChar> lhs, 131 std::basic_string_view<TChar> rhs) const { 132 return lhs == rhs; 133 } 134 }; 135 136 // Supports heterogeneous lookup for w/u16/u32 string + string_view + char*. 137 template <typename TChar> 138 struct BasicStringHashEq { 139 using Hash = BasicStringHash<TChar>; 140 using Eq = BasicStringEq<TChar>; 141 }; 142 143 template <> 144 struct HashEq<std::wstring> : BasicStringHashEq<wchar_t> {}; 145 template <> 146 struct HashEq<std::wstring_view> : BasicStringHashEq<wchar_t> {}; 147 template <> 148 struct HashEq<std::u16string> : BasicStringHashEq<char16_t> {}; 149 template <> 150 struct HashEq<std::u16string_view> : BasicStringHashEq<char16_t> {}; 151 template <> 152 struct HashEq<std::u32string> : BasicStringHashEq<char32_t> {}; 153 template <> 154 struct HashEq<std::u32string_view> : BasicStringHashEq<char32_t> {}; 155 156 #endif // ABSL_HAVE_STD_STRING_VIEW 157 158 // Supports heterogeneous lookup for pointers and smart pointers. 159 template <class T> 160 struct HashEq<T*> { 161 struct Hash { 162 using is_transparent = void; 163 template <class U> 164 size_t operator()(const U& ptr) const { 165 return absl::Hash<const T*>{}(HashEq::ToPtr(ptr)); 166 } 167 }; 168 struct Eq { 169 using is_transparent = void; 170 template <class A, class B> 171 bool operator()(const A& a, const B& b) const { 172 return HashEq::ToPtr(a) == HashEq::ToPtr(b); 173 } 174 }; 175 176 private: 177 static const T* ToPtr(const T* ptr) { return ptr; } 178 template <class U, class D> 179 static const T* ToPtr(const std::unique_ptr<U, D>& ptr) { 180 return ptr.get(); 181 } 182 template <class U> 183 static const T* ToPtr(const std::shared_ptr<U>& ptr) { 184 return ptr.get(); 185 } 186 }; 187 188 template <class T, class D> 189 struct HashEq<std::unique_ptr<T, D>> : HashEq<T*> {}; 190 template <class T> 191 struct HashEq<std::shared_ptr<T>> : HashEq<T*> {}; 192 193 template <typename T, typename E = void> 194 struct HasAbslContainerHash : std::false_type {}; 195 196 template <typename T> 197 struct HasAbslContainerHash<T, absl::void_t<typename T::absl_container_hash>> 198 : std::true_type {}; 199 200 template <typename T, typename E = void> 201 struct HasAbslContainerEq : std::false_type {}; 202 203 template <typename T> 204 struct HasAbslContainerEq<T, absl::void_t<typename T::absl_container_eq>> 205 : std::true_type {}; 206 207 template <typename T, typename E = void> 208 struct AbslContainerEq { 209 using type = std::equal_to<>; 210 }; 211 212 template <typename T> 213 struct AbslContainerEq< 214 T, typename std::enable_if_t<HasAbslContainerEq<T>::value>> { 215 using type = typename T::absl_container_eq; 216 }; 217 218 template <typename T, typename E = void> 219 struct AbslContainerHash { 220 using type = void; 221 }; 222 223 template <typename T> 224 struct AbslContainerHash< 225 T, typename std::enable_if_t<HasAbslContainerHash<T>::value>> { 226 using type = typename T::absl_container_hash; 227 }; 228 229 // HashEq specialization for user types that provide `absl_container_hash` and 230 // (optionally) `absl_container_eq`. This specialization allows user types to 231 // provide heterogeneous lookup without requiring to explicitly specify Hash/Eq 232 // type arguments in unordered Abseil containers. 233 // 234 // Both `absl_container_hash` and `absl_container_eq` should be transparent 235 // (have inner is_transparent type). While there is no technical reason to 236 // restrict to transparent-only types, there is also no feasible use case when 237 // it shouldn't be transparent - it is easier to relax the requirement later if 238 // such a case arises rather than restricting it. 239 // 240 // If type provides only `absl_container_hash` then `eq` part will be 241 // `std::equal_to<void>`. 242 // 243 // User types are not allowed to provide only a `Eq` part as there is no 244 // feasible use case for this behavior - if Hash should be a default one then Eq 245 // should be an equivalent to the `std::equal_to<T>`. 246 template <typename T> 247 struct HashEq<T, typename std::enable_if_t<HasAbslContainerHash<T>::value>> { 248 using Hash = typename AbslContainerHash<T>::type; 249 using Eq = typename AbslContainerEq<T>::type; 250 static_assert(IsTransparent<Hash>::value, 251 "absl_container_hash must be transparent. To achieve it add a " 252 "`using is_transparent = void;` clause to this type."); 253 static_assert(IsTransparent<Eq>::value, 254 "absl_container_eq must be transparent. To achieve it add a " 255 "`using is_transparent = void;` clause to this type."); 256 }; 257 258 // This header's visibility is restricted. If you need to access the default 259 // hasher please use the container's ::hasher alias instead. 260 // 261 // Example: typename Hash = typename absl::flat_hash_map<K, V>::hasher 262 template <class T> 263 using hash_default_hash = typename container_internal::HashEq<T>::Hash; 264 265 // This header's visibility is restricted. If you need to access the default 266 // key equal please use the container's ::key_equal alias instead. 267 // 268 // Example: typename Eq = typename absl::flat_hash_map<K, V, Hash>::key_equal 269 template <class T> 270 using hash_default_eq = typename container_internal::HashEq<T>::Eq; 271 272 } // namespace container_internal 273 ABSL_NAMESPACE_END 274 } // namespace absl 275 276 #endif // ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_