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
27namespace 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
50template <typename T, typename Enable>
51struct HeterogeneousAccessEqualTo : std::equal_to<T> {};
52
53template <typename T, typename Enable>
54struct HeterogeneousAccessHash : std::hash<T> {
55 using folly_is_avalanching = IsAvalanchingHasher<std::hash<T>, T>;
56};
57
58//////// strings
59
60namespace detail {
61
62template <typename T, typename Enable = void>
63struct 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*>.
70template <typename T>
71struct 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
79template <typename T>
80using TransparentlyConvertibleToRange = std::is_convertible<
81 T,
82 Range<typename ValueTypeForTransparentConversionToRange<T>::type const*>>;
83
84template <typename T>
85struct 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
101template <typename T>
102struct 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
148template <typename T>
149struct HeterogeneousAccessEqualTo<
150 T,
151 std::enable_if_t<detail::TransparentlyConvertibleToRange<T>::value>>
152 : detail::TransparentRangeEqualTo<
153 typename detail::ValueTypeForTransparentConversionToRange<T>::type> {
154};
155
156template <typename T>
157struct 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