1 | /* |
2 | * Copyright 2018-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <functional> |
20 | #include <string> |
21 | |
22 | #include <folly/Range.h> |
23 | #include <folly/Traits.h> |
24 | #include <folly/container/HeterogeneousAccess-fwd.h> |
25 | #include <folly/hash/Hash.h> |
26 | |
27 | namespace folly { |
28 | |
29 | // folly::HeterogeneousAccessEqualTo<T>, and |
30 | // folly::HeterogeneousAccessHash<T> are functors suitable as defaults |
31 | // for containers that support heterogeneous access. When possible, they |
32 | // will be marked as transparent. When no transparent implementation |
33 | // is available then they fall back to std::equal_to and std::hash |
34 | // respectively. Since the fallbacks are not marked as transparent, |
35 | // heterogeneous lookup won't be available in that case. A corresponding |
36 | // HeterogeneousAccessLess<T> could be easily added if desired. |
37 | // |
38 | // If T can be implicitly converted to a StringPiece or |
39 | // to a Range<T::value_type const*> that is hashable, then |
40 | // HeterogeneousAccess{EqualTo,Hash}<T> will be transparent without any |
41 | // additional work. In practice this is true for T that can be convered to |
42 | // StringPiece or Range<IntegralType const*>. This includes std::string, |
43 | // std::string_view (when available), std::array, folly::Range, |
44 | // std::vector, and folly::small_vector. |
45 | // |
46 | // Additional specializations of HeterogeneousAccess*<T> should go in |
47 | // the header that declares T. Don't forget to typedef is_transparent to |
48 | // void and folly_is_avalanching to std::true_type in the specializations. |
49 | |
50 | template <typename T, typename Enable> |
51 | struct HeterogeneousAccessEqualTo : std::equal_to<T> {}; |
52 | |
53 | template <typename T, typename Enable> |
54 | struct HeterogeneousAccessHash : std::hash<T> { |
55 | using folly_is_avalanching = IsAvalanchingHasher<std::hash<T>, T>; |
56 | }; |
57 | |
58 | //////// strings |
59 | |
60 | namespace detail { |
61 | |
62 | template <typename T, typename Enable = void> |
63 | struct ValueTypeForTransparentConversionToRange { |
64 | using type = char; |
65 | }; |
66 | |
67 | // We assume that folly::hasher<folly::Range<T const*>> won't be enabled |
68 | // when it would be lower quality than std::hash<U> for a U that is |
69 | // convertible to folly::Range<T const*>. |
70 | template <typename T> |
71 | struct ValueTypeForTransparentConversionToRange< |
72 | T, |
73 | void_t<decltype( |
74 | std::declval<hasher<Range<typename T::value_type const*>>>()( |
75 | std::declval<Range<typename T::value_type const*>>()))>> { |
76 | using type = std::remove_const_t<typename T::value_type>; |
77 | }; |
78 | |
79 | template <typename T> |
80 | using TransparentlyConvertibleToRange = std::is_convertible< |
81 | T, |
82 | Range<typename ValueTypeForTransparentConversionToRange<T>::type const*>>; |
83 | |
84 | template <typename T> |
85 | struct TransparentRangeEqualTo { |
86 | using is_transparent = void; |
87 | |
88 | template <typename U1, typename U2> |
89 | bool operator()(U1 const& lhs, U2 const& rhs) const { |
90 | return Range<T const*>{lhs} == Range<T const*>{rhs}; |
91 | } |
92 | |
93 | // This overload is not required for functionality, but |
94 | // guarantees that replacing std::equal_to<std::string> with |
95 | // HeterogeneousAccessEqualTo<std::string> is truly zero overhead |
96 | bool operator()(std::string const& lhs, std::string const& rhs) const { |
97 | return lhs == rhs; |
98 | } |
99 | }; |
100 | |
101 | template <typename T> |
102 | struct TransparentRangeHash { |
103 | using is_transparent = void; |
104 | using folly_is_avalanching = std::true_type; |
105 | |
106 | private: |
107 | template <typename U> |
108 | static std::size_t hashImpl(Range<U const*> piece) { |
109 | return hasher<Range<U const*>>{}(piece); |
110 | } |
111 | |
112 | static std::size_t hashImpl(StringPiece piece) { |
113 | #if defined(_GLIBCXX_STRING) |
114 | return std::_Hash_impl::hash(piece.begin(), piece.size()); |
115 | #elif defined(_LIBCPP_STRING) |
116 | return std::__do_string_hash(piece.begin(), piece.end()); |
117 | #else |
118 | return hasher<StringPiece>{}(piece); |
119 | #endif |
120 | } |
121 | |
122 | public: |
123 | template <typename U> |
124 | std::size_t operator()(U const& stringish) const { |
125 | return hashImpl(Range<T const*>{stringish}); |
126 | } |
127 | |
128 | // Neither this overload nor the platform-conditional compilation |
129 | // is required for functionality, but implementing it this |
130 | // way guarantees that replacing std::hash<std::string> with |
131 | // HeterogeneousAccessHash<std::string> is actually zero overhead |
132 | // in the case that the underlying implementations make different |
133 | // optimality tradeoffs (short versus long string performance, for |
134 | // example). If folly::hasher<StringPiece> dominated the performance |
135 | // of std::hash<std::string> then we should consider using it all of |
136 | // the time. |
137 | std::size_t operator()(std::string const& str) const { |
138 | #if defined(_GLIBCXX_STRING) || defined(_LIBCPP_STRING) |
139 | return std::hash<std::string>{}(str); |
140 | #else |
141 | return hasher<StringPiece>{}(str); |
142 | #endif |
143 | } |
144 | }; |
145 | |
146 | } // namespace detail |
147 | |
148 | template <typename T> |
149 | struct HeterogeneousAccessEqualTo< |
150 | T, |
151 | std::enable_if_t<detail::TransparentlyConvertibleToRange<T>::value>> |
152 | : detail::TransparentRangeEqualTo< |
153 | typename detail::ValueTypeForTransparentConversionToRange<T>::type> { |
154 | }; |
155 | |
156 | template <typename T> |
157 | struct HeterogeneousAccessHash< |
158 | T, |
159 | std::enable_if_t<detail::TransparentlyConvertibleToRange<T>::value>> |
160 | : detail::TransparentRangeHash< |
161 | typename detail::ValueTypeForTransparentConversionToRange<T>::type> { |
162 | }; |
163 | |
164 | } // namespace folly |
165 | |