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