node_hash_set_test.cc (6453B)
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 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 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 118 bool IsEven(int k) { return k % 2 == 0; } 119 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 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