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/node_hash_set.h"
16
17 #include <cstddef>
18 #include <memory>
19 #include <string>
20 #include <utility>
21 #include <vector>
22
23 #include "gmock/gmock.h"
24 #include "gtest/gtest.h"
25 #include "absl/base/config.h"
26 #include "absl/container/internal/hash_generator_testing.h"
27 #include "absl/container/internal/hash_policy_testing.h"
28 #include "absl/container/internal/unordered_set_constructor_test.h"
29 #include "absl/container/internal/unordered_set_lookup_test.h"
30 #include "absl/container/internal/unordered_set_members_test.h"
31 #include "absl/container/internal/unordered_set_modifiers_test.h"
32 #include "absl/memory/memory.h"
33
34 namespace absl {
35 ABSL_NAMESPACE_BEGIN
36 namespace container_internal {
37 namespace {
38 using ::absl::container_internal::hash_internal::Enum;
39 using ::absl::container_internal::hash_internal::EnumClass;
40 using ::testing::IsEmpty;
41 using ::testing::Pointee;
42 using ::testing::UnorderedElementsAre;
43 using ::testing::UnorderedElementsAreArray;
44
45 using SetTypes = ::testing::Types<
46 node_hash_set<int, StatefulTestingHash, StatefulTestingEqual, Alloc<int>>,
47 node_hash_set<std::string, StatefulTestingHash, StatefulTestingEqual,
48 Alloc<std::string>>,
49 node_hash_set<Enum, StatefulTestingHash, StatefulTestingEqual, Alloc<Enum>>,
50 node_hash_set<EnumClass, StatefulTestingHash, StatefulTestingEqual,
51 Alloc<EnumClass>>>;
52
53 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, ConstructorTest, SetTypes);
54 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, LookupTest, SetTypes);
55 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, MembersTest, SetTypes);
56 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, ModifiersTest, SetTypes);
57
TEST(NodeHashSet,MoveableNotCopyableCompiles)58 TEST(NodeHashSet, MoveableNotCopyableCompiles) {
59 node_hash_set<std::unique_ptr<void*>> t;
60 node_hash_set<std::unique_ptr<void*>> u;
61 u = std::move(t);
62 }
63
TEST(NodeHashSet,MergeExtractInsert)64 TEST(NodeHashSet, MergeExtractInsert) {
65 struct Hash {
66 size_t operator()(const std::unique_ptr<int>& p) const { return *p; }
67 };
68 struct Eq {
69 bool operator()(const std::unique_ptr<int>& a,
70 const std::unique_ptr<int>& b) const {
71 return *a == *b;
72 }
73 };
74 absl::node_hash_set<std::unique_ptr<int>, Hash, Eq> set1, set2;
75 set1.insert(absl::make_unique<int>(7));
76 set1.insert(absl::make_unique<int>(17));
77
78 set2.insert(absl::make_unique<int>(7));
79 set2.insert(absl::make_unique<int>(19));
80
81 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17)));
82 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(19)));
83
84 set1.merge(set2);
85
86 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17), Pointee(19)));
87 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
88
89 auto node = set1.extract(absl::make_unique<int>(7));
90 EXPECT_TRUE(node);
91 EXPECT_THAT(node.value(), Pointee(7));
92 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(17), Pointee(19)));
93
94 auto insert_result = set2.insert(std::move(node));
95 EXPECT_FALSE(node);
96 EXPECT_FALSE(insert_result.inserted);
97 EXPECT_TRUE(insert_result.node);
98 EXPECT_THAT(insert_result.node.value(), Pointee(7));
99 EXPECT_EQ(**insert_result.position, 7);
100 EXPECT_NE(insert_result.position->get(), insert_result.node.value().get());
101 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
102
103 node = set1.extract(absl::make_unique<int>(17));
104 EXPECT_TRUE(node);
105 EXPECT_THAT(node.value(), Pointee(17));
106 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(19)));
107
108 node.value() = absl::make_unique<int>(23);
109
110 insert_result = set2.insert(std::move(node));
111 EXPECT_FALSE(node);
112 EXPECT_TRUE(insert_result.inserted);
113 EXPECT_FALSE(insert_result.node);
114 EXPECT_EQ(**insert_result.position, 23);
115 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23)));
116 }
117
IsEven(int k)118 bool IsEven(int k) { return k % 2 == 0; }
119
TEST(NodeHashSet,EraseIf)120 TEST(NodeHashSet, EraseIf) {
121 // Erase all elements.
122 {
123 node_hash_set<int> s = {1, 2, 3, 4, 5};
124 EXPECT_EQ(erase_if(s, [](int) { return true; }), 5);
125 EXPECT_THAT(s, IsEmpty());
126 }
127 // Erase no elements.
128 {
129 node_hash_set<int> s = {1, 2, 3, 4, 5};
130 EXPECT_EQ(erase_if(s, [](int) { return false; }), 0);
131 EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5));
132 }
133 // Erase specific elements.
134 {
135 node_hash_set<int> s = {1, 2, 3, 4, 5};
136 EXPECT_EQ(erase_if(s, [](int k) { return k % 2 == 1; }), 3);
137 EXPECT_THAT(s, UnorderedElementsAre(2, 4));
138 }
139 // Predicate is function reference.
140 {
141 node_hash_set<int> s = {1, 2, 3, 4, 5};
142 EXPECT_EQ(erase_if(s, IsEven), 2);
143 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
144 }
145 // Predicate is function pointer.
146 {
147 node_hash_set<int> s = {1, 2, 3, 4, 5};
148 EXPECT_EQ(erase_if(s, &IsEven), 2);
149 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
150 }
151 }
152
TEST(NodeHashSet,CForEach)153 TEST(NodeHashSet, CForEach) {
154 using ValueType = std::pair<int, int>;
155 node_hash_set<ValueType> s;
156 std::vector<ValueType> expected;
157 for (int i = 0; i < 100; ++i) {
158 {
159 SCOPED_TRACE("mutable object iteration");
160 std::vector<ValueType> v;
161 absl::container_internal::c_for_each_fast(
162 s, [&v](const ValueType& p) { v.push_back(p); });
163 ASSERT_THAT(v, UnorderedElementsAreArray(expected));
164 }
165 {
166 SCOPED_TRACE("const object iteration");
167 std::vector<ValueType> v;
168 const node_hash_set<ValueType>& cs = s;
169 absl::container_internal::c_for_each_fast(
170 cs, [&v](const ValueType& p) { v.push_back(p); });
171 ASSERT_THAT(v, UnorderedElementsAreArray(expected));
172 }
173 {
174 SCOPED_TRACE("temporary object iteration");
175 std::vector<ValueType> v;
176 absl::container_internal::c_for_each_fast(
177 node_hash_set<ValueType>(s),
178 [&v](const ValueType& p) { v.push_back(p); });
179 ASSERT_THAT(v, UnorderedElementsAreArray(expected));
180 }
181 s.emplace(i, i);
182 expected.emplace_back(i, i);
183 }
184 }
185
186 } // namespace
187 } // namespace container_internal
188 ABSL_NAMESPACE_END
189 } // namespace absl
190