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