hash_function_defaults.h
Go to the documentation of this file.
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"
57 
58 namespace absl {
59 namespace container_internal {
60 
61 // The hash of an object of type T is computed by using absl::Hash.
62 template <class T, class E = void>
63 struct HashEq {
65  using Eq = std::equal_to<T>;
66 };
67 
68 struct StringHash {
69  using is_transparent = void;
70 
71  size_t operator()(absl::string_view v) const {
73  }
74 };
75 
76 // Supports heterogeneous lookup for string-like elements.
77 struct StringHashEq {
78  using Hash = StringHash;
79  struct Eq {
80  using is_transparent = void;
82  return lhs == rhs;
83  }
84  };
85 };
86 
87 template <>
88 struct HashEq<std::string> : StringHashEq {};
89 template <>
91 
92 // Supports heterogeneous lookup for pointers and smart pointers.
93 template <class T>
94 struct HashEq<T*> {
95  struct Hash {
96  using is_transparent = void;
97  template <class U>
98  size_t operator()(const U& ptr) const {
99  return absl::Hash<const T*>{}(HashEq::ToPtr(ptr));
100  }
101  };
102  struct Eq {
103  using is_transparent = void;
104  template <class A, class B>
105  bool operator()(const A& a, const B& b) const {
106  return HashEq::ToPtr(a) == HashEq::ToPtr(b);
107  }
108  };
109 
110  private:
111  static const T* ToPtr(const T* ptr) { return ptr; }
112  template <class U, class D>
113  static const T* ToPtr(const std::unique_ptr<U, D>& ptr) {
114  return ptr.get();
115  }
116  template <class U>
117  static const T* ToPtr(const std::shared_ptr<U>& ptr) {
118  return ptr.get();
119  }
120 };
121 
122 template <class T, class D>
123 struct HashEq<std::unique_ptr<T, D>> : HashEq<T*> {};
124 template <class T>
125 struct HashEq<std::shared_ptr<T>> : HashEq<T*> {};
126 
127 // This header's visibility is restricted. If you need to access the default
128 // hasher please use the container's ::hasher alias instead.
129 //
130 // Example: typename Hash = typename absl::flat_hash_map<K, V>::hasher
131 template <class T>
133 
134 // This header's visibility is restricted. If you need to access the default
135 // key equal please use the container's ::key_equal alias instead.
136 //
137 // Example: typename Eq = typename absl::flat_hash_map<K, V, Hash>::key_equal
138 template <class T>
140 
141 } // namespace container_internal
142 } // namespace absl
143 
144 #endif // ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_
int v
Definition: variant_test.cc:81
static const T * ToPtr(const std::shared_ptr< U > &ptr)
typename container_internal::HashEq< T >::Hash hash_default_hash
Definition: algorithm.h:29
static const T * ToPtr(const std::unique_ptr< U, D > &ptr)
char * ptr
size_t operator()(absl::string_view v) const
bool operator()(absl::string_view lhs, absl::string_view rhs) const
typename container_internal::HashEq< T >::Eq hash_default_eq
uint64_t b
Definition: layout_test.cc:50
bool operator()(const A &a, const B &b) const


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:56