hash_instantiated_test.cc (9036B)
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 // This file contains a few select absl::Hash tests that, due to their reliance 16 // on INSTANTIATE_TYPED_TEST_SUITE_P, require a large amount of memory to 17 // compile. Put new tests in hash_test.cc, not this file. 18 19 #include "absl/hash/hash.h" 20 21 #include <stddef.h> 22 23 #include <algorithm> 24 #include <deque> 25 #include <forward_list> 26 #include <initializer_list> 27 #include <list> 28 #include <map> 29 #include <set> 30 #include <string> 31 #include <type_traits> 32 #include <unordered_map> 33 #include <unordered_set> 34 #include <utility> 35 #include <vector> 36 37 #include "gtest/gtest.h" 38 #include "absl/container/btree_map.h" 39 #include "absl/container/btree_set.h" 40 #include "absl/container/flat_hash_map.h" 41 #include "absl/container/flat_hash_set.h" 42 #include "absl/container/node_hash_map.h" 43 #include "absl/container/node_hash_set.h" 44 #include "absl/hash/hash_testing.h" 45 #include "absl/hash/internal/hash_test.h" 46 47 namespace { 48 49 using ::absl::hash_test_internal::is_hashable; 50 using ::absl::hash_test_internal::TypeErasedContainer; 51 52 // Dummy type with unordered equality and hashing semantics. This preserves 53 // input order internally, and is used below to ensure we get test coverage 54 // for equal sequences with different iteraton orders. 55 template <typename T> 56 class UnorderedSequence { 57 public: 58 UnorderedSequence() = default; 59 template <typename TT> 60 UnorderedSequence(std::initializer_list<TT> l) 61 : values_(l.begin(), l.end()) {} 62 template <typename ForwardIterator, 63 typename std::enable_if<!std::is_integral<ForwardIterator>::value, 64 bool>::type = true> 65 UnorderedSequence(ForwardIterator begin, ForwardIterator end) 66 : values_(begin, end) {} 67 // one-argument constructor of value type T, to appease older toolchains that 68 // get confused by one-element initializer lists in some contexts 69 explicit UnorderedSequence(const T& v) : values_(&v, &v + 1) {} 70 71 using value_type = T; 72 73 size_t size() const { return values_.size(); } 74 typename std::vector<T>::const_iterator begin() const { 75 return values_.begin(); 76 } 77 typename std::vector<T>::const_iterator end() const { return values_.end(); } 78 79 friend bool operator==(const UnorderedSequence& lhs, 80 const UnorderedSequence& rhs) { 81 return lhs.size() == rhs.size() && 82 std::is_permutation(lhs.begin(), lhs.end(), rhs.begin()); 83 } 84 friend bool operator!=(const UnorderedSequence& lhs, 85 const UnorderedSequence& rhs) { 86 return !(lhs == rhs); 87 } 88 template <typename H> 89 friend H AbslHashValue(H h, const UnorderedSequence& u) { 90 return H::combine(H::combine_unordered(std::move(h), u.begin(), u.end()), 91 u.size()); 92 } 93 94 private: 95 std::vector<T> values_; 96 }; 97 98 template <typename T> 99 class HashValueSequenceTest : public testing::Test {}; 100 TYPED_TEST_SUITE_P(HashValueSequenceTest); 101 102 TYPED_TEST_P(HashValueSequenceTest, BasicUsage) { 103 EXPECT_TRUE((is_hashable<TypeParam>::value)); 104 105 using IntType = typename TypeParam::value_type; 106 auto a = static_cast<IntType>(0); 107 auto b = static_cast<IntType>(23); 108 auto c = static_cast<IntType>(42); 109 110 std::vector<TypeParam> exemplars = { 111 TypeParam(), TypeParam(), TypeParam{a, b, c}, 112 TypeParam{a, c, b}, TypeParam{c, a, b}, TypeParam{a}, 113 TypeParam{a, a}, TypeParam{a, a, a}, TypeParam{a, a, b}, 114 TypeParam{a, b, a}, TypeParam{b, a, a}, TypeParam{a, b}, 115 TypeParam{b, c}}; 116 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); 117 } 118 119 REGISTER_TYPED_TEST_SUITE_P(HashValueSequenceTest, BasicUsage); 120 using IntSequenceTypes = testing::Types< 121 std::deque<int>, std::forward_list<int>, std::list<int>, std::vector<int>, 122 std::vector<bool>, TypeErasedContainer<std::vector<int>>, std::set<int>, 123 std::multiset<int>, UnorderedSequence<int>, 124 TypeErasedContainer<UnorderedSequence<int>>, std::unordered_set<int>, 125 std::unordered_multiset<int>, absl::flat_hash_set<int>, 126 absl::node_hash_set<int>, absl::btree_set<int>>; 127 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueSequenceTest, IntSequenceTypes); 128 129 template <typename T> 130 class HashValueNestedSequenceTest : public testing::Test {}; 131 TYPED_TEST_SUITE_P(HashValueNestedSequenceTest); 132 133 TYPED_TEST_P(HashValueNestedSequenceTest, BasicUsage) { 134 using T = TypeParam; 135 using V = typename T::value_type; 136 std::vector<T> exemplars = { 137 // empty case 138 T{}, 139 // sets of empty sets 140 T{V{}}, T{V{}, V{}}, T{V{}, V{}, V{}}, 141 // multisets of different values 142 T{V{1}}, T{V{1, 1}, V{1, 1}}, T{V{1, 1, 1}, V{1, 1, 1}, V{1, 1, 1}}, 143 // various orderings of same nested sets 144 T{V{}, V{1, 2}}, T{V{}, V{2, 1}}, T{V{1, 2}, V{}}, T{V{2, 1}, V{}}, 145 // various orderings of various nested sets, case 2 146 T{V{1, 2}, V{3, 4}}, T{V{1, 2}, V{4, 3}}, T{V{1, 3}, V{2, 4}}, 147 T{V{1, 3}, V{4, 2}}, T{V{1, 4}, V{2, 3}}, T{V{1, 4}, V{3, 2}}, 148 T{V{2, 3}, V{1, 4}}, T{V{2, 3}, V{4, 1}}, T{V{2, 4}, V{1, 3}}, 149 T{V{2, 4}, V{3, 1}}, T{V{3, 4}, V{1, 2}}, T{V{3, 4}, V{2, 1}}}; 150 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); 151 } 152 153 REGISTER_TYPED_TEST_SUITE_P(HashValueNestedSequenceTest, BasicUsage); 154 template <typename T> 155 using TypeErasedSet = TypeErasedContainer<UnorderedSequence<T>>; 156 157 using NestedIntSequenceTypes = testing::Types< 158 std::vector<std::vector<int>>, std::vector<UnorderedSequence<int>>, 159 std::vector<TypeErasedSet<int>>, UnorderedSequence<std::vector<int>>, 160 UnorderedSequence<UnorderedSequence<int>>, 161 UnorderedSequence<TypeErasedSet<int>>, TypeErasedSet<std::vector<int>>, 162 TypeErasedSet<UnorderedSequence<int>>, TypeErasedSet<TypeErasedSet<int>>>; 163 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueNestedSequenceTest, 164 NestedIntSequenceTypes); 165 166 template <typename T> 167 class HashValueAssociativeMapTest : public testing::Test {}; 168 TYPED_TEST_SUITE_P(HashValueAssociativeMapTest); 169 170 TYPED_TEST_P(HashValueAssociativeMapTest, BasicUsage) { 171 using M = TypeParam; 172 using V = typename M::value_type; 173 std::vector<M> exemplars{M{}, 174 M{V{0, "foo"}}, 175 M{V{1, "foo"}}, 176 M{V{0, "bar"}}, 177 M{V{1, "bar"}}, 178 M{V{0, "foo"}, V{42, "bar"}}, 179 M{V{42, "bar"}, V{0, "foo"}}, 180 M{V{1, "foo"}, V{42, "bar"}}, 181 M{V{1, "foo"}, V{43, "bar"}}, 182 M{V{1, "foo"}, V{43, "baz"}}}; 183 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); 184 } 185 186 REGISTER_TYPED_TEST_SUITE_P(HashValueAssociativeMapTest, BasicUsage); 187 using AssociativeMapTypes = testing::Types< 188 std::map<int, std::string>, std::unordered_map<int, std::string>, 189 absl::flat_hash_map<int, std::string>, 190 absl::node_hash_map<int, std::string>, absl::btree_map<int, std::string>, 191 UnorderedSequence<std::pair<const int, std::string>>>; 192 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueAssociativeMapTest, 193 AssociativeMapTypes); 194 195 template <typename T> 196 class HashValueAssociativeMultimapTest : public testing::Test {}; 197 TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest); 198 199 TYPED_TEST_P(HashValueAssociativeMultimapTest, BasicUsage) { 200 using MM = TypeParam; 201 using V = typename MM::value_type; 202 std::vector<MM> exemplars{MM{}, 203 MM{V{0, "foo"}}, 204 MM{V{1, "foo"}}, 205 MM{V{0, "bar"}}, 206 MM{V{1, "bar"}}, 207 MM{V{0, "foo"}, V{0, "bar"}}, 208 MM{V{0, "bar"}, V{0, "foo"}}, 209 MM{V{0, "foo"}, V{42, "bar"}}, 210 MM{V{1, "foo"}, V{42, "bar"}}, 211 MM{V{1, "foo"}, V{1, "foo"}, V{43, "bar"}}, 212 MM{V{1, "foo"}, V{43, "bar"}, V{1, "foo"}}, 213 MM{V{1, "foo"}, V{43, "baz"}}}; 214 EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); 215 } 216 217 REGISTER_TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest, BasicUsage); 218 using AssociativeMultimapTypes = 219 testing::Types<std::multimap<int, std::string>, 220 std::unordered_multimap<int, std::string>>; 221 INSTANTIATE_TYPED_TEST_SUITE_P(My, HashValueAssociativeMultimapTest, 222 AssociativeMultimapTypes); 223 224 } // namespace