blob: e616ac1e227429a834e020e7963ee46ae6e2c049 [file] [log] [blame]
Abseil Team48cd2c32018-09-27 12:24:54 -07001// 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//
nik727338b70432019-03-08 10:27:53 -05007// https://www.apache.org/licenses/LICENSE-2.0
Abseil Team48cd2c32018-09-27 12:24:54 -07008//
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
Vitaly Goldshteyn10ac8112024-06-20 13:43:52 -070017#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"
Abseil Team48cd2c32018-09-27 12:24:54 -070028#include "absl/container/internal/unordered_set_constructor_test.h"
29#include "absl/container/internal/unordered_set_lookup_test.h"
Abseil Team9fdf5e52019-03-04 18:05:37 -080030#include "absl/container/internal/unordered_set_members_test.h"
Abseil Team48cd2c32018-09-27 12:24:54 -070031#include "absl/container/internal/unordered_set_modifiers_test.h"
Vitaly Goldshteyn10ac8112024-06-20 13:43:52 -070032#include "absl/memory/memory.h"
Abseil Team48cd2c32018-09-27 12:24:54 -070033
34namespace absl {
Abseil Team12bc53e2019-12-12 10:36:03 -080035ABSL_NAMESPACE_BEGIN
Abseil Team48cd2c32018-09-27 12:24:54 -070036namespace container_internal {
37namespace {
38using ::absl::container_internal::hash_internal::Enum;
39using ::absl::container_internal::hash_internal::EnumClass;
Abseil Team1de01662020-01-03 08:41:10 -080040using ::testing::IsEmpty;
Abseil Team48cd2c32018-09-27 12:24:54 -070041using ::testing::Pointee;
42using ::testing::UnorderedElementsAre;
Vitaly Goldshteyn10ac8112024-06-20 13:43:52 -070043using ::testing::UnorderedElementsAreArray;
Abseil Team48cd2c32018-09-27 12:24:54 -070044
45using SetTypes = ::testing::Types<
46 node_hash_set<int, StatefulTestingHash, StatefulTestingEqual, Alloc<int>>,
47 node_hash_set<std::string, StatefulTestingHash, StatefulTestingEqual,
Abseil Team9fdf5e52019-03-04 18:05:37 -080048 Alloc<std::string>>,
Abseil Team48cd2c32018-09-27 12:24:54 -070049 node_hash_set<Enum, StatefulTestingHash, StatefulTestingEqual, Alloc<Enum>>,
50 node_hash_set<EnumClass, StatefulTestingHash, StatefulTestingEqual,
51 Alloc<EnumClass>>>;
52
Abseil Team5eea0f72019-01-11 10:16:39 -080053INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, ConstructorTest, SetTypes);
54INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, LookupTest, SetTypes);
Abseil Team9fdf5e52019-03-04 18:05:37 -080055INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, MembersTest, SetTypes);
Abseil Team5eea0f72019-01-11 10:16:39 -080056INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashSet, ModifiersTest, SetTypes);
Abseil Team48cd2c32018-09-27 12:24:54 -070057
58TEST(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
64TEST(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
Abseil Team1de01662020-01-03 08:41:10 -0800118bool IsEven(int k) { return k % 2 == 0; }
119
120TEST(NodeHashSet, EraseIf) {
121 // Erase all elements.
122 {
123 node_hash_set<int> s = {1, 2, 3, 4, 5};
Abseil Teamcad715d2021-11-30 14:02:51 -0800124 EXPECT_EQ(erase_if(s, [](int) { return true; }), 5);
Abseil Team1de01662020-01-03 08:41:10 -0800125 EXPECT_THAT(s, IsEmpty());
126 }
127 // Erase no elements.
128 {
129 node_hash_set<int> s = {1, 2, 3, 4, 5};
Abseil Teamcad715d2021-11-30 14:02:51 -0800130 EXPECT_EQ(erase_if(s, [](int) { return false; }), 0);
Abseil Team1de01662020-01-03 08:41:10 -0800131 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};
Abseil Teamcad715d2021-11-30 14:02:51 -0800136 EXPECT_EQ(erase_if(s, [](int k) { return k % 2 == 1; }), 3);
Abseil Team1de01662020-01-03 08:41:10 -0800137 EXPECT_THAT(s, UnorderedElementsAre(2, 4));
138 }
139 // Predicate is function reference.
140 {
141 node_hash_set<int> s = {1, 2, 3, 4, 5};
Abseil Teamcad715d2021-11-30 14:02:51 -0800142 EXPECT_EQ(erase_if(s, IsEven), 2);
Abseil Team1de01662020-01-03 08:41:10 -0800143 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};
Abseil Teamcad715d2021-11-30 14:02:51 -0800148 EXPECT_EQ(erase_if(s, &IsEven), 2);
Abseil Team1de01662020-01-03 08:41:10 -0800149 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
150 }
151}
152
Vitaly Goldshteyn10ac8112024-06-20 13:43:52 -0700153TEST(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
Abseil Team48cd2c32018-09-27 12:24:54 -0700186} // namespace
187} // namespace container_internal
Abseil Team12bc53e2019-12-12 10:36:03 -0800188ABSL_NAMESPACE_END
Abseil Team48cd2c32018-09-27 12:24:54 -0700189} // namespace absl