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 #include "absl/container/flat_hash_set.h"
16
17 #include <vector>
18
19 #include "absl/base/internal/raw_logging.h"
20 #include "absl/container/internal/hash_generator_testing.h"
21 #include "absl/container/internal/unordered_set_constructor_test.h"
22 #include "absl/container/internal/unordered_set_lookup_test.h"
23 #include "absl/container/internal/unordered_set_members_test.h"
24 #include "absl/container/internal/unordered_set_modifiers_test.h"
25 #include "absl/memory/memory.h"
26 #include "absl/strings/string_view.h"
27
28 namespace absl {
29 ABSL_NAMESPACE_BEGIN
30 namespace container_internal {
31 namespace {
32
33 using ::absl::container_internal::hash_internal::Enum;
34 using ::absl::container_internal::hash_internal::EnumClass;
35 using ::testing::IsEmpty;
36 using ::testing::Pointee;
37 using ::testing::UnorderedElementsAre;
38 using ::testing::UnorderedElementsAreArray;
39
40 // Check that absl::flat_hash_set works in a global constructor.
41 struct BeforeMain {
BeforeMainabsl::container_internal::__anone72d51020111::BeforeMain42 BeforeMain() {
43 absl::flat_hash_set<int> x;
44 x.insert(1);
45 ABSL_RAW_CHECK(!x.contains(0), "x should not contain 0");
46 ABSL_RAW_CHECK(x.contains(1), "x should contain 1");
47 }
48 };
49 const BeforeMain before_main;
50
51 template <class T>
52 using Set =
53 absl::flat_hash_set<T, StatefulTestingHash, StatefulTestingEqual, Alloc<T>>;
54
55 using SetTypes =
56 ::testing::Types<Set<int>, Set<std::string>, Set<Enum>, Set<EnumClass>>;
57
58 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ConstructorTest, SetTypes);
59 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, LookupTest, SetTypes);
60 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, MembersTest, SetTypes);
61 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ModifiersTest, SetTypes);
62
TEST(FlatHashSet,EmplaceString)63 TEST(FlatHashSet, EmplaceString) {
64 std::vector<std::string> v = {"a", "b"};
65 absl::flat_hash_set<absl::string_view> hs(v.begin(), v.end());
66 EXPECT_THAT(hs, UnorderedElementsAreArray(v));
67 }
68
TEST(FlatHashSet,BitfieldArgument)69 TEST(FlatHashSet, BitfieldArgument) {
70 union {
71 int n : 1;
72 };
73 n = 0;
74 absl::flat_hash_set<int> s = {n};
75 s.insert(n);
76 s.insert(s.end(), n);
77 s.insert({n});
78 s.erase(n);
79 s.count(n);
80 s.prefetch(n);
81 s.find(n);
82 s.contains(n);
83 s.equal_range(n);
84 }
85
TEST(FlatHashSet,MergeExtractInsert)86 TEST(FlatHashSet, MergeExtractInsert) {
87 struct Hash {
88 size_t operator()(const std::unique_ptr<int>& p) const { return *p; }
89 };
90 struct Eq {
91 bool operator()(const std::unique_ptr<int>& a,
92 const std::unique_ptr<int>& b) const {
93 return *a == *b;
94 }
95 };
96 absl::flat_hash_set<std::unique_ptr<int>, Hash, Eq> set1, set2;
97 set1.insert(absl::make_unique<int>(7));
98 set1.insert(absl::make_unique<int>(17));
99
100 set2.insert(absl::make_unique<int>(7));
101 set2.insert(absl::make_unique<int>(19));
102
103 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17)));
104 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(19)));
105
106 set1.merge(set2);
107
108 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17), Pointee(19)));
109 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
110
111 auto node = set1.extract(absl::make_unique<int>(7));
112 EXPECT_TRUE(node);
113 EXPECT_THAT(node.value(), Pointee(7));
114 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(17), Pointee(19)));
115
116 auto insert_result = set2.insert(std::move(node));
117 EXPECT_FALSE(node);
118 EXPECT_FALSE(insert_result.inserted);
119 EXPECT_TRUE(insert_result.node);
120 EXPECT_THAT(insert_result.node.value(), Pointee(7));
121 EXPECT_EQ(**insert_result.position, 7);
122 EXPECT_NE(insert_result.position->get(), insert_result.node.value().get());
123 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
124
125 node = set1.extract(absl::make_unique<int>(17));
126 EXPECT_TRUE(node);
127 EXPECT_THAT(node.value(), Pointee(17));
128 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(19)));
129
130 node.value() = absl::make_unique<int>(23);
131
132 insert_result = set2.insert(std::move(node));
133 EXPECT_FALSE(node);
134 EXPECT_TRUE(insert_result.inserted);
135 EXPECT_FALSE(insert_result.node);
136 EXPECT_EQ(**insert_result.position, 23);
137 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23)));
138 }
139
IsEven(int k)140 bool IsEven(int k) { return k % 2 == 0; }
141
TEST(FlatHashSet,EraseIf)142 TEST(FlatHashSet, EraseIf) {
143 // Erase all elements.
144 {
145 flat_hash_set<int> s = {1, 2, 3, 4, 5};
146 erase_if(s, [](int) { return true; });
147 EXPECT_THAT(s, IsEmpty());
148 }
149 // Erase no elements.
150 {
151 flat_hash_set<int> s = {1, 2, 3, 4, 5};
152 erase_if(s, [](int) { return false; });
153 EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5));
154 }
155 // Erase specific elements.
156 {
157 flat_hash_set<int> s = {1, 2, 3, 4, 5};
158 erase_if(s, [](int k) { return k % 2 == 1; });
159 EXPECT_THAT(s, UnorderedElementsAre(2, 4));
160 }
161 // Predicate is function reference.
162 {
163 flat_hash_set<int> s = {1, 2, 3, 4, 5};
164 erase_if(s, IsEven);
165 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
166 }
167 // Predicate is function pointer.
168 {
169 flat_hash_set<int> s = {1, 2, 3, 4, 5};
170 erase_if(s, &IsEven);
171 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
172 }
173 }
174
175 } // namespace
176 } // namespace container_internal
177 ABSL_NAMESPACE_END
178 } // namespace absl
179