1 // Copyright 2018 The Abseil Authors.
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
7 // https://www.apache.org/licenses/LICENSE-2.0
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.
15 #ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_
16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_
18 #include "gmock/gmock.h"
19 #include "gtest/gtest.h"
20 #include "absl/container/internal/hash_generator_testing.h"
21 #include "absl/container/internal/hash_policy_testing.h"
24 namespace container_internal {
26 template <class UnordMap>
27 class ModifiersTest : public ::testing::Test {};
29 TYPED_TEST_SUITE_P(ModifiersTest);
31 TYPED_TEST_P(ModifiersTest, Clear) {
32 using T = hash_internal::GeneratedType<TypeParam>;
33 std::vector<T> values;
34 std::generate_n(std::back_inserter(values), 10,
35 hash_internal::Generator<T>());
36 TypeParam m(values.begin(), values.end());
37 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
39 EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
40 EXPECT_TRUE(m.empty());
43 TYPED_TEST_P(ModifiersTest, Insert) {
44 using T = hash_internal::GeneratedType<TypeParam>;
45 using V = typename TypeParam::mapped_type;
46 T val = hash_internal::Generator<T>()();
48 auto p = m.insert(val);
49 EXPECT_TRUE(p.second);
50 EXPECT_EQ(val, *p.first);
51 T val2 = {val.first, hash_internal::Generator<V>()()};
53 EXPECT_FALSE(p.second);
54 EXPECT_EQ(val, *p.first);
57 TYPED_TEST_P(ModifiersTest, InsertHint) {
58 using T = hash_internal::GeneratedType<TypeParam>;
59 using V = typename TypeParam::mapped_type;
60 T val = hash_internal::Generator<T>()();
62 auto it = m.insert(m.end(), val);
63 EXPECT_TRUE(it != m.end());
65 T val2 = {val.first, hash_internal::Generator<V>()()};
66 it = m.insert(it, val2);
67 EXPECT_TRUE(it != m.end());
71 TYPED_TEST_P(ModifiersTest, InsertRange) {
72 using T = hash_internal::GeneratedType<TypeParam>;
73 std::vector<T> values;
74 std::generate_n(std::back_inserter(values), 10,
75 hash_internal::Generator<T>());
77 m.insert(values.begin(), values.end());
78 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
81 TYPED_TEST_P(ModifiersTest, InsertOrAssign) {
82 #ifdef UNORDERED_MAP_CXX17
84 using K = typename TypeParam::key_type;
85 using V = typename TypeParam::mapped_type;
86 K k = hash_internal::Generator<K>()();
87 V val = hash_internal::Generator<V>()();
89 auto p = m.insert_or_assign(k, val);
90 EXPECT_TRUE(p.second);
91 EXPECT_EQ(k, get<0>(*p.first));
92 EXPECT_EQ(val, get<1>(*p.first));
93 V val2 = hash_internal::Generator<V>()();
94 p = m.insert_or_assign(k, val2);
95 EXPECT_FALSE(p.second);
96 EXPECT_EQ(k, get<0>(*p.first));
97 EXPECT_EQ(val2, get<1>(*p.first));
101 TYPED_TEST_P(ModifiersTest, InsertOrAssignHint) {
102 #ifdef UNORDERED_MAP_CXX17
104 using K = typename TypeParam::key_type;
105 using V = typename TypeParam::mapped_type;
106 K k = hash_internal::Generator<K>()();
107 V val = hash_internal::Generator<V>()();
109 auto it = m.insert_or_assign(m.end(), k, val);
110 EXPECT_TRUE(it != m.end());
111 EXPECT_EQ(k, get<0>(*it));
112 EXPECT_EQ(val, get<1>(*it));
113 V val2 = hash_internal::Generator<V>()();
114 it = m.insert_or_assign(it, k, val2);
115 EXPECT_EQ(k, get<0>(*it));
116 EXPECT_EQ(val2, get<1>(*it));
120 TYPED_TEST_P(ModifiersTest, Emplace) {
121 using T = hash_internal::GeneratedType<TypeParam>;
122 using V = typename TypeParam::mapped_type;
123 T val = hash_internal::Generator<T>()();
125 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
126 // with test traits/policy.
127 auto p = m.emplace(val);
128 EXPECT_TRUE(p.second);
129 EXPECT_EQ(val, *p.first);
130 T val2 = {val.first, hash_internal::Generator<V>()()};
132 EXPECT_FALSE(p.second);
133 EXPECT_EQ(val, *p.first);
136 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
137 using T = hash_internal::GeneratedType<TypeParam>;
138 using V = typename TypeParam::mapped_type;
139 T val = hash_internal::Generator<T>()();
141 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
142 // with test traits/policy.
143 auto it = m.emplace_hint(m.end(), val);
145 T val2 = {val.first, hash_internal::Generator<V>()()};
146 it = m.emplace_hint(it, val2);
150 TYPED_TEST_P(ModifiersTest, TryEmplace) {
151 #ifdef UNORDERED_MAP_CXX17
152 using T = hash_internal::GeneratedType<TypeParam>;
153 using V = typename TypeParam::mapped_type;
154 T val = hash_internal::Generator<T>()();
156 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
157 // with test traits/policy.
158 auto p = m.try_emplace(val.first, val.second);
159 EXPECT_TRUE(p.second);
160 EXPECT_EQ(val, *p.first);
161 T val2 = {val.first, hash_internal::Generator<V>()()};
162 p = m.try_emplace(val2.first, val2.second);
163 EXPECT_FALSE(p.second);
164 EXPECT_EQ(val, *p.first);
168 TYPED_TEST_P(ModifiersTest, TryEmplaceHint) {
169 #ifdef UNORDERED_MAP_CXX17
170 using T = hash_internal::GeneratedType<TypeParam>;
171 using V = typename TypeParam::mapped_type;
172 T val = hash_internal::Generator<T>()();
174 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
175 // with test traits/policy.
176 auto it = m.try_emplace(m.end(), val.first, val.second);
178 T val2 = {val.first, hash_internal::Generator<V>()()};
179 it = m.try_emplace(it, val2.first, val2.second);
185 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
187 // In openmap we chose not to return the iterator from erase because that's
188 // more expensive. As such we adapt erase to return an iterator here.
191 auto operator()(Map* m, int) const
192 -> IfNotVoid<decltype(m->erase(m->begin()))> {
193 return m->erase(m->begin());
196 typename Map::iterator operator()(Map* m, ...) const {
197 auto it = m->begin();
203 TYPED_TEST_P(ModifiersTest, Erase) {
204 using T = hash_internal::GeneratedType<TypeParam>;
206 std::vector<T> values;
207 std::generate_n(std::back_inserter(values), 10,
208 hash_internal::Generator<T>());
209 TypeParam m(values.begin(), values.end());
210 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
211 auto& first = *m.begin();
212 std::vector<T> values2;
213 for (const auto& val : values)
214 if (get<0>(val) != get<0>(first)) values2.push_back(val);
215 auto it = EraseFirst()(&m, 0);
216 ASSERT_TRUE(it != m.end());
217 EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
218 EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values2.begin(),
222 TYPED_TEST_P(ModifiersTest, EraseRange) {
223 using T = hash_internal::GeneratedType<TypeParam>;
224 std::vector<T> values;
225 std::generate_n(std::back_inserter(values), 10,
226 hash_internal::Generator<T>());
227 TypeParam m(values.begin(), values.end());
228 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
229 auto it = m.erase(m.begin(), m.end());
230 EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
231 EXPECT_TRUE(it == m.end());
234 TYPED_TEST_P(ModifiersTest, EraseKey) {
235 using T = hash_internal::GeneratedType<TypeParam>;
236 std::vector<T> values;
237 std::generate_n(std::back_inserter(values), 10,
238 hash_internal::Generator<T>());
239 TypeParam m(values.begin(), values.end());
240 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
241 EXPECT_EQ(1, m.erase(values[0].first));
242 EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
243 EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
247 TYPED_TEST_P(ModifiersTest, Swap) {
248 using T = hash_internal::GeneratedType<TypeParam>;
251 std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
252 std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
253 TypeParam m1(v1.begin(), v1.end());
254 TypeParam m2(v2.begin(), v2.end());
255 EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v1));
256 EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v2));
258 EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v2));
259 EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v1));
262 // TODO(alkis): Write tests for extract.
263 // TODO(alkis): Write tests for merge.
265 REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint,
266 InsertRange, InsertOrAssign, InsertOrAssignHint,
267 Emplace, EmplaceHint, TryEmplace, TryEmplaceHint,
268 Erase, EraseRange, EraseKey, Swap);
270 } // namespace container_internal
273 #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_