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 #ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
17
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"
22
23 namespace absl {
24 ABSL_NAMESPACE_BEGIN
25 namespace container_internal {
26
27 template <class UnordSet>
28 class ModifiersTest : public ::testing::Test {};
29
30 TYPED_TEST_SUITE_P(ModifiersTest);
31
TYPED_TEST_P(ModifiersTest,Clear)32 TYPED_TEST_P(ModifiersTest, Clear) {
33 using T = hash_internal::GeneratedType<TypeParam>;
34 std::vector<T> values;
35 std::generate_n(std::back_inserter(values), 10,
36 hash_internal::Generator<T>());
37 TypeParam m(values.begin(), values.end());
38 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
39 m.clear();
40 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
41 EXPECT_TRUE(m.empty());
42 }
43
TYPED_TEST_P(ModifiersTest,Insert)44 TYPED_TEST_P(ModifiersTest, Insert) {
45 using T = hash_internal::GeneratedType<TypeParam>;
46 T val = hash_internal::Generator<T>()();
47 TypeParam m;
48 auto p = m.insert(val);
49 EXPECT_TRUE(p.second);
50 EXPECT_EQ(val, *p.first);
51 p = m.insert(val);
52 EXPECT_FALSE(p.second);
53 }
54
TYPED_TEST_P(ModifiersTest,InsertHint)55 TYPED_TEST_P(ModifiersTest, InsertHint) {
56 using T = hash_internal::GeneratedType<TypeParam>;
57 T val = hash_internal::Generator<T>()();
58 TypeParam m;
59 auto it = m.insert(m.end(), val);
60 EXPECT_TRUE(it != m.end());
61 EXPECT_EQ(val, *it);
62 it = m.insert(it, val);
63 EXPECT_TRUE(it != m.end());
64 EXPECT_EQ(val, *it);
65 }
66
TYPED_TEST_P(ModifiersTest,InsertRange)67 TYPED_TEST_P(ModifiersTest, InsertRange) {
68 using T = hash_internal::GeneratedType<TypeParam>;
69 std::vector<T> values;
70 std::generate_n(std::back_inserter(values), 10,
71 hash_internal::Generator<T>());
72 TypeParam m;
73 m.insert(values.begin(), values.end());
74 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
75 }
76
TYPED_TEST_P(ModifiersTest,InsertWithinCapacity)77 TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) {
78 using T = hash_internal::GeneratedType<TypeParam>;
79 T val = hash_internal::Generator<T>()();
80 TypeParam m;
81 m.reserve(10);
82 const size_t original_capacity = m.bucket_count();
83 m.insert(val);
84 EXPECT_EQ(m.bucket_count(), original_capacity);
85 m.insert(val);
86 EXPECT_EQ(m.bucket_count(), original_capacity);
87 }
88
TYPED_TEST_P(ModifiersTest,InsertRangeWithinCapacity)89 TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) {
90 #if !defined(__GLIBCXX__)
91 using T = hash_internal::GeneratedType<TypeParam>;
92 std::vector<T> base_values;
93 std::generate_n(std::back_inserter(base_values), 10,
94 hash_internal::Generator<T>());
95 std::vector<T> values;
96 while (values.size() != 100) {
97 values.insert(values.end(), base_values.begin(), base_values.end());
98 }
99 TypeParam m;
100 m.reserve(10);
101 const size_t original_capacity = m.bucket_count();
102 m.insert(values.begin(), values.end());
103 EXPECT_EQ(m.bucket_count(), original_capacity);
104 #endif
105 }
106
TYPED_TEST_P(ModifiersTest,Emplace)107 TYPED_TEST_P(ModifiersTest, Emplace) {
108 using T = hash_internal::GeneratedType<TypeParam>;
109 T val = hash_internal::Generator<T>()();
110 TypeParam m;
111 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
112 // with test traits/policy.
113 auto p = m.emplace(val);
114 EXPECT_TRUE(p.second);
115 EXPECT_EQ(val, *p.first);
116 p = m.emplace(val);
117 EXPECT_FALSE(p.second);
118 EXPECT_EQ(val, *p.first);
119 }
120
TYPED_TEST_P(ModifiersTest,EmplaceHint)121 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
122 using T = hash_internal::GeneratedType<TypeParam>;
123 T val = hash_internal::Generator<T>()();
124 TypeParam m;
125 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
126 // with test traits/policy.
127 auto it = m.emplace_hint(m.end(), val);
128 EXPECT_EQ(val, *it);
129 it = m.emplace_hint(it, val);
130 EXPECT_EQ(val, *it);
131 }
132
133 template <class V>
134 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
135
136 // In openmap we chose not to return the iterator from erase because that's
137 // more expensive. As such we adapt erase to return an iterator here.
138 struct EraseFirst {
139 template <class Map>
140 auto operator()(Map* m, int) const
141 -> IfNotVoid<decltype(m->erase(m->begin()))> {
142 return m->erase(m->begin());
143 }
144 template <class Map>
operatorEraseFirst145 typename Map::iterator operator()(Map* m, ...) const {
146 auto it = m->begin();
147 m->erase(it++);
148 return it;
149 }
150 };
151
TYPED_TEST_P(ModifiersTest,Erase)152 TYPED_TEST_P(ModifiersTest, Erase) {
153 using T = hash_internal::GeneratedType<TypeParam>;
154 std::vector<T> values;
155 std::generate_n(std::back_inserter(values), 10,
156 hash_internal::Generator<T>());
157 TypeParam m(values.begin(), values.end());
158 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
159 std::vector<T> values2;
160 for (const auto& val : values)
161 if (val != *m.begin()) values2.push_back(val);
162 auto it = EraseFirst()(&m, 0);
163 ASSERT_TRUE(it != m.end());
164 EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
165 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values2.begin(),
166 values2.end()));
167 }
168
TYPED_TEST_P(ModifiersTest,EraseRange)169 TYPED_TEST_P(ModifiersTest, EraseRange) {
170 using T = hash_internal::GeneratedType<TypeParam>;
171 std::vector<T> values;
172 std::generate_n(std::back_inserter(values), 10,
173 hash_internal::Generator<T>());
174 TypeParam m(values.begin(), values.end());
175 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
176 auto it = m.erase(m.begin(), m.end());
177 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
178 EXPECT_TRUE(it == m.end());
179 }
180
TYPED_TEST_P(ModifiersTest,EraseKey)181 TYPED_TEST_P(ModifiersTest, EraseKey) {
182 using T = hash_internal::GeneratedType<TypeParam>;
183 std::vector<T> values;
184 std::generate_n(std::back_inserter(values), 10,
185 hash_internal::Generator<T>());
186 TypeParam m(values.begin(), values.end());
187 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
188 EXPECT_EQ(1, m.erase(values[0]));
189 EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
190 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
191 values.end()));
192 }
193
TYPED_TEST_P(ModifiersTest,Swap)194 TYPED_TEST_P(ModifiersTest, Swap) {
195 using T = hash_internal::GeneratedType<TypeParam>;
196 std::vector<T> v1;
197 std::vector<T> v2;
198 std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
199 std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
200 TypeParam m1(v1.begin(), v1.end());
201 TypeParam m2(v2.begin(), v2.end());
202 EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v1));
203 EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v2));
204 m1.swap(m2);
205 EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v2));
206 EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v1));
207 }
208
209 // TODO(alkis): Write tests for extract.
210 // TODO(alkis): Write tests for merge.
211
212 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint,
213 InsertRange, InsertWithinCapacity,
214 InsertRangeWithinCapacity, Emplace, EmplaceHint,
215 Erase, EraseRange, EraseKey, Swap);
216
217 } // namespace container_internal
218 ABSL_NAMESPACE_END
219 } // namespace absl
220
221 #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
222