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 <stdint.h> 49 #include <cstddef> 50 #include <memory> 51 #include <string> 52 #include <type_traits> 53 54 #include "absl/base/config.h" 55 #include "absl/hash/hash.h" 56 #include "absl/strings/cord.h" 57 #include "absl/strings/string_view.h" 58 59 namespace absl { 60 ABSL_NAMESPACE_BEGIN 61 namespace container_internal { 62 63 // The hash of an object of type T is computed by using absl::Hash. 64 template <class T, class E = void> 65 struct HashEq { 66 using Hash = absl::Hash<T>; 67 using Eq = std::equal_to<T>; 68 }; 69 70 struct StringHash { 71 using is_transparent = void; 72 operatorStringHash73 size_t operator()(absl::string_view v) const { 74 return absl::Hash<absl::string_view>{}(v); 75 } operatorStringHash76 size_t operator()(const absl::Cord& v) const { 77 return absl::Hash<absl::Cord>{}(v); 78 } 79 }; 80 81 // Supports heterogeneous lookup for string-like elements. 82 struct StringHashEq { 83 using Hash = StringHash; 84 struct Eq { 85 using is_transparent = void; operatorStringHashEq::Eq86 bool operator()(absl::string_view lhs, absl::string_view rhs) const { 87 return lhs == rhs; 88 } operatorStringHashEq::Eq89 bool operator()(const absl::Cord& lhs, const absl::Cord& rhs) const { 90 return lhs == rhs; 91 } operatorStringHashEq::Eq92 bool operator()(const absl::Cord& lhs, absl::string_view rhs) const { 93 return lhs == rhs; 94 } operatorStringHashEq::Eq95 bool operator()(absl::string_view lhs, const absl::Cord& rhs) const { 96 return lhs == rhs; 97 } 98 }; 99 }; 100 101 template <> 102 struct HashEq<std::string> : StringHashEq {}; 103 template <> 104 struct HashEq<absl::string_view> : StringHashEq {}; 105 template <> 106 struct HashEq<absl::Cord> : StringHashEq {}; 107 108 // Supports heterogeneous lookup for pointers and smart pointers. 109 template <class T> 110 struct HashEq<T*> { 111 struct Hash { 112 using is_transparent = void; 113 template <class U> 114 size_t operator()(const U& ptr) const { 115 return absl::Hash<const T*>{}(HashEq::ToPtr(ptr)); 116 } 117 }; 118 struct Eq { 119 using is_transparent = void; 120 template <class A, class B> 121 bool operator()(const A& a, const B& b) const { 122 return HashEq::ToPtr(a) == HashEq::ToPtr(b); 123 } 124 }; 125 126 private: 127 static const T* ToPtr(const T* ptr) { return ptr; } 128 template <class U, class D> 129 static const T* ToPtr(const std::unique_ptr<U, D>& ptr) { 130 return ptr.get(); 131 } 132 template <class U> 133 static const T* ToPtr(const std::shared_ptr<U>& ptr) { 134 return ptr.get(); 135 } 136 }; 137 138 template <class T, class D> 139 struct HashEq<std::unique_ptr<T, D>> : HashEq<T*> {}; 140 template <class T> 141 struct HashEq<std::shared_ptr<T>> : HashEq<T*> {}; 142 143 // This header's visibility is restricted. If you need to access the default 144 // hasher please use the container's ::hasher alias instead. 145 // 146 // Example: typename Hash = typename absl::flat_hash_map<K, V>::hasher 147 template <class T> 148 using hash_default_hash = typename container_internal::HashEq<T>::Hash; 149 150 // This header's visibility is restricted. If you need to access the default 151 // key equal please use the container's ::key_equal alias instead. 152 // 153 // Example: typename Eq = typename absl::flat_hash_map<K, V, Hash>::key_equal 154 template <class T> 155 using hash_default_eq = typename container_internal::HashEq<T>::Eq; 156 157 } // namespace container_internal 158 ABSL_NAMESPACE_END 159 } // namespace absl 160 161 #endif // ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ 162