Add absl::linked_hash_set and absl::linked_hash_map These are hash containers ordered by insertion. PiperOrigin-RevId: 846682470 Change-Id: I1c7fc54197d074666754f94b477782400197a14e
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index b419f1b..91e220a 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -95,6 +95,8 @@ "container/internal/raw_hash_set.h" "container/internal/raw_hash_set_resize_impl.h" "container/internal/tracked.h" + "container/linked_hash_map.h" + "container/linked_hash_set.h" "container/node_hash_map.h" "container/node_hash_set.h" "crc/crc32c.cc"
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index ab6533f..b61dcc0 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -496,6 +496,7 @@ linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_policy_testing", + "//absl/base:config", "//absl/base:no_destructor", "//absl/memory", "//absl/meta:type_traits", @@ -945,6 +946,7 @@ deps = [ ":hash_generator_testing", ":hash_policy_testing", + "//absl/base:config", "@googletest//:gtest", ], ) @@ -984,6 +986,7 @@ deps = [ ":hash_generator_testing", ":hash_policy_testing", + "//absl/base:config", "//absl/meta:type_traits", "@googletest//:gtest", ], @@ -1200,3 +1203,122 @@ "@google_benchmark//:benchmark_main", ], ) + +cc_library( + name = "heterogeneous_lookup_testing", + testonly = True, + hdrs = ["internal/heterogeneous_lookup_testing.h"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + "//absl/base:config", + "//absl/container:test_instance_tracker", + "@googletest//:gtest", + ], +) + +cc_library( + name = "linked_hash_set", + hdrs = ["linked_hash_set.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":common", + "//absl/base:config", + "//absl/base:core_headers", + "//absl/container:flat_hash_set", + ], +) + +cc_test( + name = "linked_hash_set_test", + srcs = ["linked_hash_set_test.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":heterogeneous_lookup_testing", + ":linked_hash_set", + "//absl/base:config", + "//absl/container:hash_generator_testing", + "//absl/container:hash_policy_testing", + "//absl/container:test_instance_tracker", + "//absl/container:unordered_set_constructor_test", + "//absl/container:unordered_set_lookup_test", + "//absl/container:unordered_set_members_test", + "//absl/container:unordered_set_modifiers_test", + "//absl/strings:string_view", + "@googletest//:gtest", + "@googletest//:gtest_main", + ], +) + +cc_binary( + name = "linked_hash_set_benchmark", + testonly = True, + srcs = ["linked_hash_set_benchmark.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":linked_hash_set", + "//absl/functional:function_ref", + "//absl/strings:str_format", + "//absl/strings:string_view", + "@google_benchmark//:benchmark_main", + ], +) + +cc_library( + name = "linked_hash_map", + hdrs = ["linked_hash_map.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":common", + "//absl/base:config", + "//absl/base:core_headers", + "//absl/base:throw_delegate", + "//absl/container:flat_hash_set", + ], +) + +cc_test( + name = "linked_hash_map_test", + srcs = ["linked_hash_map_test.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":heterogeneous_lookup_testing", + ":linked_hash_map", + "//absl/base:config", + "//absl/base:exception_testing", + "//absl/container:hash_generator_testing", + "//absl/container:hash_policy_testing", + "//absl/container:test_instance_tracker", + "//absl/container:unordered_map_constructor_test", + "//absl/container:unordered_map_lookup_test", + "//absl/container:unordered_map_members_test", + "//absl/container:unordered_map_modifiers_test", + "//absl/strings:string_view", + "@googletest//:gtest", + "@googletest//:gtest_main", + ], +) + +cc_binary( + name = "linked_hash_map_benchmark", + testonly = True, + srcs = ["linked_hash_map_benchmark.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":linked_hash_map", + "//absl/functional:function_ref", + "//absl/strings:str_format", + "//absl/strings:string_view", + "@google_benchmark//:benchmark_main", + ], +)
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index adce9a9..40b8b07 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -541,6 +541,7 @@ COPTS ${ABSL_TEST_COPTS} DEPS + absl::config absl::hash_policy_testing absl::memory absl::meta @@ -950,6 +951,7 @@ COPTS ${ABSL_TEST_COPTS} DEPS + absl::config absl::hash_generator_testing absl::hash_policy_testing GTest::gmock @@ -1009,6 +1011,7 @@ COPTS ${ABSL_TEST_COPTS} DEPS + absl::config absl::hash_generator_testing absl::hash_policy_testing GTest::gmock @@ -1104,3 +1107,100 @@ absl::hashtablez_sampler GTest::gmock_main ) + +absl_cc_library( + NAME + heterogeneous_lookup_testing + HDRS + "internal/heterogeneous_lookup_testing.h" + COPTS + ${ABSL_TEST_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::config + absl::test_instance_tracker + GTest::gmock +) + +absl_cc_library( + NAME + linked_hash_set + HDRS + "linked_hash_set.h" + COPTS + ${ABSL_DEFAULT_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::container_common + absl::config + absl::core_headers + absl::flat_hash_set +) + +absl_cc_test( + NAME + linked_hash_set_test + SRCS + "linked_hash_set_test.cc" + COPTS + ${ABSL_TEST_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::linked_hash_set + absl::config + absl::heterogeneous_lookup_testing + absl::hash_generator_testing + absl::hash_policy_testing + absl::string_view + absl::test_instance_tracker + absl::unordered_set_constructor_test + absl::unordered_set_lookup_test + absl::unordered_set_members_test + absl::unordered_set_modifiers_test + GTest::gmock_main +) + +absl_cc_library( + NAME + linked_hash_map + HDRS + "linked_hash_map.h" + COPTS + ${ABSL_DEFAULT_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::container_common + absl::config + absl::core_headers + absl::flat_hash_set + absl::throw_delegate +) + +absl_cc_test( + NAME + linked_hash_map_test + SRCS + "linked_hash_map_test.cc" + COPTS + ${ABSL_TEST_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::linked_hash_map + absl::config + absl::exception_testing + absl::heterogeneous_lookup_testing + absl::hash_generator_testing + absl::hash_policy_testing + absl::string_view + absl::test_instance_tracker + absl::unordered_set_constructor_test + absl::unordered_set_lookup_test + absl::unordered_set_members_test + absl::unordered_set_modifiers_test + GTest::gmock_main +)
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc index e1d9382..73f28c7 100644 --- a/absl/container/flat_hash_map_test.cc +++ b/absl/container/flat_hash_map_test.cc
@@ -39,8 +39,7 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { namespace { -using ::absl::container_internal::hash_internal::Enum; -using ::absl::container_internal::hash_internal::EnumClass; + using ::testing::_; using ::testing::IsEmpty; using ::testing::Pair;
diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc index ca069b4..9b6a6d1 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc
@@ -43,8 +43,6 @@ namespace container_internal { namespace { -using ::absl::container_internal::hash_internal::Enum; -using ::absl::container_internal::hash_internal::EnumClass; using ::testing::IsEmpty; using ::testing::Pointee; using ::testing::UnorderedElementsAre;
diff --git a/absl/container/internal/hash_generator_testing.cc b/absl/container/internal/hash_generator_testing.cc index be20e21..4ae58da 100644 --- a/absl/container/internal/hash_generator_testing.cc +++ b/absl/container/internal/hash_generator_testing.cc
@@ -26,7 +26,6 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { -namespace hash_internal { std::string Generator<std::string>::operator()() const { absl::InsecureBitGen gen; @@ -50,7 +49,6 @@ return res; } -} // namespace hash_internal } // namespace container_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/container/internal/hash_generator_testing.h b/absl/container/internal/hash_generator_testing.h index 14c878e..4c5d87b 100644 --- a/absl/container/internal/hash_generator_testing.h +++ b/absl/container/internal/hash_generator_testing.h
@@ -31,6 +31,7 @@ #include <utility> #include <vector> +#include "absl/base/config.h" #include "absl/container/internal/hash_policy_testing.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" @@ -40,7 +41,6 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { -namespace hash_internal { namespace generator_internal { template <class Container, class = void> @@ -165,7 +165,6 @@ } }; -} // namespace hash_internal } // namespace container_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/container/internal/hash_policy_testing.h b/absl/container/internal/hash_policy_testing.h index e9f5757..86ea96a 100644 --- a/absl/container/internal/hash_policy_testing.h +++ b/absl/container/internal/hash_policy_testing.h
@@ -170,18 +170,4 @@ ABSL_NAMESPACE_END } // namespace absl -// ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS is false for glibcxx versions -// where the unordered containers are missing certain constructors that -// take allocator arguments. This test is defined ad-hoc for the platforms -// we care about (notably Crosstool 17) because libstdcxx's useless -// versioning scheme precludes a more principled solution. -// From GCC-4.9 Changelog: (src: https://gcc.gnu.org/gcc-4.9/changes.html) -// "the unordered associative containers in <unordered_map> and <unordered_set> -// meet the allocator-aware container requirements;" -#if defined(__GLIBCXX__) && __GLIBCXX__ <= 20140425 -#define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 0 -#else -#define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 1 -#endif - #endif // ABSL_CONTAINER_INTERNAL_HASH_POLICY_TESTING_H_
diff --git a/absl/container/internal/heterogeneous_lookup_testing.h b/absl/container/internal/heterogeneous_lookup_testing.h new file mode 100644 index 0000000..b8cfae3 --- /dev/null +++ b/absl/container/internal/heterogeneous_lookup_testing.h
@@ -0,0 +1,80 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_CONTAINER_INTERNAL_HETEROGENEOUS_LOOKUP_TESTING_H_ +#define ABSL_CONTAINER_INTERNAL_HETEROGENEOUS_LOOKUP_TESTING_H_ + +#include <cstddef> +#include <ostream> + +#include "gmock/gmock.h" +#include "absl/base/config.h" +#include "absl/container/internal/test_instance_tracker.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +// An expensive class that is convertible to CheapType to demonstrate +// heterogeneous lookups. +class ExpensiveType : public absl::test_internal::CopyableMovableInstance { + public: + explicit ExpensiveType(int value) + : absl::test_internal::CopyableMovableInstance(value) {} + + friend std::ostream& operator<<(std::ostream& os, const ExpensiveType& a) { + return os << a.value(); + } +}; + +class CheapType { + public: + explicit CheapType(const int value) : value_(value) {} + + explicit operator ExpensiveType() const { return ExpensiveType(value_); } + + int value() const { return value_; } + + private: + int value_; +}; + +struct HeterogeneousHash { + using is_transparent = void; + size_t operator()(const ExpensiveType& a) const { return a.value(); } + size_t operator()(const CheapType& a) const { return a.value(); } +}; + +struct HeterogeneousEqual { + using is_transparent = void; + bool operator()(const ExpensiveType& a, const ExpensiveType& b) const { + return a.value() == b.value(); + } + bool operator()(const ExpensiveType& a, const CheapType& b) const { + return a.value() == b.value(); + } + bool operator()(const CheapType& a, const ExpensiveType& b) const { + return a.value() == b.value(); + } +}; + +MATCHER_P(HasExpensiveValue, n, "") { + return ::testing::ExplainMatchResult(n, arg.value(), result_listener); +} + +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_HETEROGENEOUS_LOOKUP_TESTING_H_
diff --git a/absl/container/internal/unordered_map_constructor_test.h b/absl/container/internal/unordered_map_constructor_test.h index 7e84dc2..1076aea 100644 --- a/absl/container/internal/unordered_map_constructor_test.h +++ b/absl/container/internal/unordered_map_constructor_test.h
@@ -21,6 +21,7 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/container/internal/hash_generator_testing.h" #include "absl/container/internal/hash_policy_testing.h" @@ -85,28 +86,8 @@ EXPECT_GE(m.bucket_count(), 123); } -template <typename T> -struct is_std_unordered_map : std::false_type {}; - -template <typename... T> -struct is_std_unordered_map<std::unordered_map<T...>> : std::true_type {}; - -#if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17) -using has_cxx14_std_apis = std::true_type; -#else -using has_cxx14_std_apis = std::false_type; -#endif - -template <typename T> -using expect_cxx14_apis = - absl::disjunction<absl::negation<is_std_unordered_map<T>>, - has_cxx14_std_apis>; - template <typename TypeParam> -void BucketCountAllocTest(std::false_type) {} - -template <typename TypeParam> -void BucketCountAllocTest(std::true_type) { +void BucketCountAllocTest() { using A = typename TypeParam::allocator_type; A alloc(0); TypeParam m(123, alloc); @@ -117,14 +98,11 @@ } TYPED_TEST_P(ConstructorTest, BucketCountAlloc) { - BucketCountAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + BucketCountAllocTest<TypeParam>(); } template <typename TypeParam> -void BucketCountHashAllocTest(std::false_type) {} - -template <typename TypeParam> -void BucketCountHashAllocTest(std::true_type) { +void BucketCountHashAllocTest() { using H = typename TypeParam::hasher; using A = typename TypeParam::allocator_type; H hasher; @@ -138,25 +116,11 @@ } TYPED_TEST_P(ConstructorTest, BucketCountHashAlloc) { - BucketCountHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + BucketCountHashAllocTest<TypeParam>(); } -#if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS -using has_alloc_std_constructors = std::true_type; -#else -using has_alloc_std_constructors = std::false_type; -#endif - -template <typename T> -using expect_alloc_constructors = - absl::disjunction<absl::negation<is_std_unordered_map<T>>, - has_alloc_std_constructors>; - template <typename TypeParam> -void AllocTest(std::false_type) {} - -template <typename TypeParam> -void AllocTest(std::true_type) { +void AllocTest() { using A = typename TypeParam::allocator_type; A alloc(0); TypeParam m(alloc); @@ -165,12 +129,10 @@ EXPECT_THAT(m, ::testing::UnorderedElementsAre()); } -TYPED_TEST_P(ConstructorTest, Alloc) { - AllocTest<TypeParam>(expect_alloc_constructors<TypeParam>()); -} +TYPED_TEST_P(ConstructorTest, Alloc) { AllocTest<TypeParam>(); } TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; @@ -178,8 +140,7 @@ E equal; A alloc(0); std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::UniqueGenerator<T>()); + std::generate_n(std::back_inserter(values), 10, UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.key_eq(), equal); @@ -189,16 +150,12 @@ } template <typename TypeParam> -void InputIteratorBucketAllocTest(std::false_type) {} - -template <typename TypeParam> -void InputIteratorBucketAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InputIteratorBucketAllocTest() { + using T = GeneratedType<TypeParam>; using A = typename TypeParam::allocator_type; A alloc(0); std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::UniqueGenerator<T>()); + std::generate_n(std::back_inserter(values), 10, UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, alloc); EXPECT_EQ(m.get_allocator(), alloc); EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); @@ -206,22 +163,18 @@ } TYPED_TEST_P(ConstructorTest, InputIteratorBucketAlloc) { - InputIteratorBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InputIteratorBucketAllocTest<TypeParam>(); } template <typename TypeParam> -void InputIteratorBucketHashAllocTest(std::false_type) {} - -template <typename TypeParam> -void InputIteratorBucketHashAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InputIteratorBucketHashAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using A = typename TypeParam::allocator_type; H hasher; A alloc(0); std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::UniqueGenerator<T>()); + std::generate_n(std::back_inserter(values), 10, UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.get_allocator(), alloc); @@ -230,18 +183,18 @@ } TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashAlloc) { - InputIteratorBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InputIteratorBucketHashAllocTest<TypeParam>(); } TYPED_TEST_P(ConstructorTest, CopyConstructor) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam n(m); @@ -252,18 +205,15 @@ } template <typename TypeParam> -void CopyConstructorAllocTest(std::false_type) {} - -template <typename TypeParam> -void CopyConstructorAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void CopyConstructorAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam n(m, A(11)); @@ -274,20 +224,20 @@ } TYPED_TEST_P(ConstructorTest, CopyConstructorAlloc) { - CopyConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>()); + CopyConstructorAllocTest<TypeParam>(); } // TODO(alkis): Test non-propagating allocators on copy constructors. TYPED_TEST_P(ConstructorTest, MoveConstructor) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam t(m); @@ -299,18 +249,15 @@ } template <typename TypeParam> -void MoveConstructorAllocTest(std::false_type) {} - -template <typename TypeParam> -void MoveConstructorAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void MoveConstructorAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam t(m); @@ -322,14 +269,14 @@ } TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) { - MoveConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>()); + MoveConstructorAllocTest<TypeParam>(); } // TODO(alkis): Test non-propagating allocators on move constructors. TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::UniqueGenerator<T> gen; + using T = GeneratedType<TypeParam>; + UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; @@ -346,13 +293,10 @@ } template <typename TypeParam> -void InitializerListBucketAllocTest(std::false_type) {} - -template <typename TypeParam> -void InitializerListBucketAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InitializerListBucketAllocTest() { + using T = GeneratedType<TypeParam>; using A = typename TypeParam::allocator_type; - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; A alloc(0); TypeParam m(values, 123, alloc); @@ -362,20 +306,17 @@ } TYPED_TEST_P(ConstructorTest, InitializerListBucketAlloc) { - InitializerListBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InitializerListBucketAllocTest<TypeParam>(); } template <typename TypeParam> -void InitializerListBucketHashAllocTest(std::false_type) {} - -template <typename TypeParam> -void InitializerListBucketHashAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InitializerListBucketHashAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using A = typename TypeParam::allocator_type; H hasher; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values, 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); @@ -385,18 +326,18 @@ } TYPED_TEST_P(ConstructorTest, InitializerListBucketHashAlloc) { - InitializerListBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InitializerListBucketHashAllocTest<TypeParam>(); } TYPED_TEST_P(ConstructorTest, Assignment) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam n; n = m; @@ -409,14 +350,14 @@ // (it depends on traits). TYPED_TEST_P(ConstructorTest, MoveAssignment) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::UniqueGenerator<T> gen; + UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam t(m); TypeParam n; @@ -427,8 +368,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::UniqueGenerator<T> gen; + using T = GeneratedType<TypeParam>; + UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -436,8 +377,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::UniqueGenerator<T> gen; + using T = GeneratedType<TypeParam>; + UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam n({gen()}); n = m; @@ -445,8 +386,8 @@ } TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::UniqueGenerator<T> gen; + using T = GeneratedType<TypeParam>; + UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam t(m); TypeParam n({gen()}); @@ -455,8 +396,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::UniqueGenerator<T> gen; + using T = GeneratedType<TypeParam>; + UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -464,8 +405,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::UniqueGenerator<T> gen; + using T = GeneratedType<TypeParam>; + UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values); m = *&m; // Avoid -Wself-assign
diff --git a/absl/container/internal/unordered_map_lookup_test.h b/absl/container/internal/unordered_map_lookup_test.h index 3713cd9..ba037c0 100644 --- a/absl/container/internal/unordered_map_lookup_test.h +++ b/absl/container/internal/unordered_map_lookup_test.h
@@ -30,10 +30,9 @@ TYPED_TEST_SUITE_P(LookupTest); TYPED_TEST_P(LookupTest, At) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); for (const auto& p : values) { const auto& val = m.at(p.first); @@ -42,11 +41,10 @@ } TYPED_TEST_P(LookupTest, OperatorBracket) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& p : values) { auto& val = m[p.first]; @@ -58,10 +56,9 @@ } TYPED_TEST_P(LookupTest, Count) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& p : values) EXPECT_EQ(0, m.count(p.first)) << ::testing::PrintToString(p.first); @@ -72,10 +69,9 @@ TYPED_TEST_P(LookupTest, Find) { using std::get; - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& p : values) EXPECT_TRUE(m.end() == m.find(p.first)) @@ -90,10 +86,9 @@ TYPED_TEST_P(LookupTest, EqualRange) { using std::get; - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& p : values) { auto r = m.equal_range(p.first);
diff --git a/absl/container/internal/unordered_map_members_test.h b/absl/container/internal/unordered_map_members_test.h index 7d48cdb..e9f4979 100644 --- a/absl/container/internal/unordered_map_members_test.h +++ b/absl/container/internal/unordered_map_members_test.h
@@ -36,10 +36,10 @@ EXPECT_TRUE((std::is_same<std::pair<const typename TypeParam::key_type, typename TypeParam::mapped_type>, typename TypeParam::value_type>())); - EXPECT_TRUE((absl::conjunction< - absl::negation<std::is_signed<typename TypeParam::size_type>>, + EXPECT_TRUE((std::conjunction< + std::negation<std::is_signed<typename TypeParam::size_type>>, std::is_integral<typename TypeParam::size_type>>())); - EXPECT_TRUE((absl::conjunction< + EXPECT_TRUE((std::conjunction< std::is_signed<typename TypeParam::difference_type>, std::is_integral<typename TypeParam::difference_type>>())); EXPECT_TRUE((std::is_convertible<
diff --git a/absl/container/internal/unordered_map_modifiers_test.h b/absl/container/internal/unordered_map_modifiers_test.h index 4d9ab30..a0b01a0 100644 --- a/absl/container/internal/unordered_map_modifiers_test.h +++ b/absl/container/internal/unordered_map_modifiers_test.h
@@ -32,10 +32,9 @@ TYPED_TEST_SUITE_P(ModifiersTest); TYPED_TEST_P(ModifiersTest, Clear) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); m.clear(); @@ -44,63 +43,61 @@ } TYPED_TEST_P(ModifiersTest, Insert) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; auto p = m.insert(val); EXPECT_TRUE(p.second); EXPECT_EQ(val, *p.first); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; p = m.insert(val2); EXPECT_FALSE(p.second); EXPECT_EQ(val, *p.first); } TYPED_TEST_P(ModifiersTest, InsertHint) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; auto it = m.insert(m.end(), val); EXPECT_TRUE(it != m.end()); EXPECT_EQ(val, *it); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; it = m.insert(it, val2); EXPECT_TRUE(it != m.end()); EXPECT_EQ(val, *it); } TYPED_TEST_P(ModifiersTest, InsertRange) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; m.insert(values.begin(), values.end()); ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); } TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; m.reserve(10); const size_t original_capacity = m.bucket_count(); m.insert(val); EXPECT_EQ(m.bucket_count(), original_capacity); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; m.insert(val2); EXPECT_EQ(m.bucket_count(), original_capacity); } TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) { #if !defined(__GLIBCXX__) - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> base_values; - std::generate_n(std::back_inserter(base_values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(base_values), 10, Generator<T>()); std::vector<T> values; while (values.size() != 100) { std::copy_n(base_values.begin(), 10, std::back_inserter(values)); @@ -114,106 +111,98 @@ } TYPED_TEST_P(ModifiersTest, InsertOrAssign) { -#ifdef UNORDERED_MAP_CXX17 using std::get; using K = typename TypeParam::key_type; using V = typename TypeParam::mapped_type; - K k = hash_internal::Generator<K>()(); - V val = hash_internal::Generator<V>()(); + K k = Generator<K>()(); + V val = Generator<V>()(); TypeParam m; auto p = m.insert_or_assign(k, val); EXPECT_TRUE(p.second); EXPECT_EQ(k, get<0>(*p.first)); EXPECT_EQ(val, get<1>(*p.first)); - V val2 = hash_internal::Generator<V>()(); + V val2 = Generator<V>()(); p = m.insert_or_assign(k, val2); EXPECT_FALSE(p.second); EXPECT_EQ(k, get<0>(*p.first)); EXPECT_EQ(val2, get<1>(*p.first)); -#endif } TYPED_TEST_P(ModifiersTest, InsertOrAssignHint) { -#ifdef UNORDERED_MAP_CXX17 using std::get; using K = typename TypeParam::key_type; using V = typename TypeParam::mapped_type; - K k = hash_internal::Generator<K>()(); - V val = hash_internal::Generator<V>()(); + K k = Generator<K>()(); + V val = Generator<V>()(); TypeParam m; auto it = m.insert_or_assign(m.end(), k, val); EXPECT_TRUE(it != m.end()); EXPECT_EQ(k, get<0>(*it)); EXPECT_EQ(val, get<1>(*it)); - V val2 = hash_internal::Generator<V>()(); + V val2 = Generator<V>()(); it = m.insert_or_assign(it, k, val2); EXPECT_EQ(k, get<0>(*it)); EXPECT_EQ(val2, get<1>(*it)); -#endif } TYPED_TEST_P(ModifiersTest, Emplace) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps // with test traits/policy. auto p = m.emplace(val); EXPECT_TRUE(p.second); EXPECT_EQ(val, *p.first); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; p = m.emplace(val2); EXPECT_FALSE(p.second); EXPECT_EQ(val, *p.first); } TYPED_TEST_P(ModifiersTest, EmplaceHint) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps // with test traits/policy. auto it = m.emplace_hint(m.end(), val); EXPECT_EQ(val, *it); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; it = m.emplace_hint(it, val2); EXPECT_EQ(val, *it); } TYPED_TEST_P(ModifiersTest, TryEmplace) { -#ifdef UNORDERED_MAP_CXX17 - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps // with test traits/policy. auto p = m.try_emplace(val.first, val.second); EXPECT_TRUE(p.second); EXPECT_EQ(val, *p.first); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; p = m.try_emplace(val2.first, val2.second); EXPECT_FALSE(p.second); EXPECT_EQ(val, *p.first); -#endif } TYPED_TEST_P(ModifiersTest, TryEmplaceHint) { -#ifdef UNORDERED_MAP_CXX17 - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps // with test traits/policy. auto it = m.try_emplace(m.end(), val.first, val.second); EXPECT_EQ(val, *it); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; it = m.try_emplace(it, val2.first, val2.second); EXPECT_EQ(val, *it); -#endif } template <class V> @@ -236,11 +225,10 @@ }; TYPED_TEST_P(ModifiersTest, Erase) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using std::get; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); auto& first = *m.begin(); @@ -255,10 +243,9 @@ } TYPED_TEST_P(ModifiersTest, EraseRange) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); auto it = m.erase(m.begin(), m.end()); @@ -267,10 +254,9 @@ } TYPED_TEST_P(ModifiersTest, EraseKey) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); EXPECT_EQ(1, m.erase(values[0].first)); @@ -280,11 +266,11 @@ } TYPED_TEST_P(ModifiersTest, Swap) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> v1; std::vector<T> v2; - std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>()); - std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(v1), 5, Generator<T>()); + std::generate_n(std::back_inserter(v2), 5, Generator<T>()); TypeParam m1(v1.begin(), v1.end()); TypeParam m2(v2.begin(), v2.end()); EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v1)); @@ -327,20 +313,18 @@ // Test that we do not move from rvalue arguments if an insertion does not // happen. TYPED_TEST_P(UniquePtrModifiersTest, TryEmplace) { -#ifdef UNORDERED_MAP_CXX17 - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using V = typename TypeParam::mapped_type; - T val = hash_internal::Generator<T>()(); + T val = Generator<T>()(); TypeParam m; auto p = m.try_emplace(val.first, std::move(val.second)); EXPECT_TRUE(p.second); // A moved from std::unique_ptr is guaranteed to be nullptr. EXPECT_EQ(val.second, nullptr); - T val2 = {val.first, hash_internal::Generator<V>()()}; + T val2 = {val.first, Generator<V>()()}; p = m.try_emplace(val2.first, std::move(val2.second)); EXPECT_FALSE(p.second); EXPECT_NE(val2.second, nullptr); -#endif } REGISTER_TYPED_TEST_SUITE_P(UniquePtrModifiersTest, TryEmplace);
diff --git a/absl/container/internal/unordered_set_constructor_test.h b/absl/container/internal/unordered_set_constructor_test.h index af1116e..7038a0c 100644 --- a/absl/container/internal/unordered_set_constructor_test.h +++ b/absl/container/internal/unordered_set_constructor_test.h
@@ -21,6 +21,7 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/container/internal/hash_generator_testing.h" #include "absl/container/internal/hash_policy_testing.h" #include "absl/meta/type_traits.h" @@ -94,28 +95,8 @@ EXPECT_GE(cm.bucket_count(), 123); } -template <typename T> -struct is_std_unordered_set : std::false_type {}; - -template <typename... T> -struct is_std_unordered_set<std::unordered_set<T...>> : std::true_type {}; - -#if defined(UNORDERED_SET_CXX14) || defined(UNORDERED_SET_CXX17) -using has_cxx14_std_apis = std::true_type; -#else -using has_cxx14_std_apis = std::false_type; -#endif - -template <typename T> -using expect_cxx14_apis = - absl::disjunction<absl::negation<is_std_unordered_set<T>>, - has_cxx14_std_apis>; - template <typename TypeParam> -void BucketCountAllocTest(std::false_type) {} - -template <typename TypeParam> -void BucketCountAllocTest(std::true_type) { +void BucketCountAllocTest() { using A = typename TypeParam::allocator_type; A alloc(0); TypeParam m(123, alloc); @@ -126,14 +107,11 @@ } TYPED_TEST_P(ConstructorTest, BucketCountAlloc) { - BucketCountAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + BucketCountAllocTest<TypeParam>(); } template <typename TypeParam> -void BucketCountHashAllocTest(std::false_type) {} - -template <typename TypeParam> -void BucketCountHashAllocTest(std::true_type) { +void BucketCountHashAllocTest() { using H = typename TypeParam::hasher; using A = typename TypeParam::allocator_type; H hasher; @@ -147,25 +125,11 @@ } TYPED_TEST_P(ConstructorTest, BucketCountHashAlloc) { - BucketCountHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + BucketCountHashAllocTest<TypeParam>(); } -#if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS -using has_alloc_std_constructors = std::true_type; -#else -using has_alloc_std_constructors = std::false_type; -#endif - -template <typename T> -using expect_alloc_constructors = - absl::disjunction<absl::negation<is_std_unordered_set<T>>, - has_alloc_std_constructors>; - template <typename TypeParam> -void AllocTest(std::false_type) {} - -template <typename TypeParam> -void AllocTest(std::true_type) { +void AllocTest() { using A = typename TypeParam::allocator_type; A alloc(0); TypeParam m(alloc); @@ -174,12 +138,10 @@ EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre()); } -TYPED_TEST_P(ConstructorTest, Alloc) { - AllocTest<TypeParam>(expect_alloc_constructors<TypeParam>()); -} +TYPED_TEST_P(ConstructorTest, Alloc) { AllocTest<TypeParam>(); } TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; @@ -187,8 +149,7 @@ E equal; A alloc(0); std::vector<T> values; - for (size_t i = 0; i != 10; ++i) - values.push_back(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) values.push_back(Generator<T>()()); TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.key_eq(), equal); @@ -198,16 +159,12 @@ } template <typename TypeParam> -void InputIteratorBucketAllocTest(std::false_type) {} - -template <typename TypeParam> -void InputIteratorBucketAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InputIteratorBucketAllocTest() { + using T = GeneratedType<TypeParam>; using A = typename TypeParam::allocator_type; A alloc(0); std::vector<T> values; - for (size_t i = 0; i != 10; ++i) - values.push_back(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) values.push_back(Generator<T>()()); TypeParam m(values.begin(), values.end(), 123, alloc); EXPECT_EQ(m.get_allocator(), alloc); EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); @@ -215,22 +172,18 @@ } TYPED_TEST_P(ConstructorTest, InputIteratorBucketAlloc) { - InputIteratorBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InputIteratorBucketAllocTest<TypeParam>(); } template <typename TypeParam> -void InputIteratorBucketHashAllocTest(std::false_type) {} - -template <typename TypeParam> -void InputIteratorBucketHashAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InputIteratorBucketHashAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using A = typename TypeParam::allocator_type; H hasher; A alloc(0); std::vector<T> values; - for (size_t i = 0; i != 10; ++i) - values.push_back(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) values.push_back(Generator<T>()()); TypeParam m(values.begin(), values.end(), 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.get_allocator(), alloc); @@ -239,11 +192,11 @@ } TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashAlloc) { - InputIteratorBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InputIteratorBucketHashAllocTest<TypeParam>(); } TYPED_TEST_P(ConstructorTest, CopyConstructor) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; @@ -251,7 +204,7 @@ E equal; A alloc(0); TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(Generator<T>()()); TypeParam n(m); EXPECT_EQ(m.hash_function(), n.hash_function()); EXPECT_EQ(m.key_eq(), n.key_eq()); @@ -261,11 +214,8 @@ } template <typename TypeParam> -void CopyConstructorAllocTest(std::false_type) {} - -template <typename TypeParam> -void CopyConstructorAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void CopyConstructorAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; @@ -273,7 +223,7 @@ E equal; A alloc(0); TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(Generator<T>()()); TypeParam n(m, A(11)); EXPECT_EQ(m.hash_function(), n.hash_function()); EXPECT_EQ(m.key_eq(), n.key_eq()); @@ -282,13 +232,13 @@ } TYPED_TEST_P(ConstructorTest, CopyConstructorAlloc) { - CopyConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>()); + CopyConstructorAllocTest<TypeParam>(); } // TODO(alkis): Test non-propagating allocators on copy constructors. TYPED_TEST_P(ConstructorTest, MoveConstructor) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; @@ -296,7 +246,7 @@ E equal; A alloc(0); TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(Generator<T>()()); TypeParam t(m); TypeParam n(std::move(t)); EXPECT_EQ(m.hash_function(), n.hash_function()); @@ -306,11 +256,8 @@ } template <typename TypeParam> -void MoveConstructorAllocTest(std::false_type) {} - -template <typename TypeParam> -void MoveConstructorAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void MoveConstructorAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; @@ -318,7 +265,7 @@ E equal; A alloc(0); TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(Generator<T>()()); TypeParam t(m); TypeParam n(std::move(t), A(1)); EXPECT_EQ(m.hash_function(), n.hash_function()); @@ -328,14 +275,14 @@ } TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) { - MoveConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>()); + MoveConstructorAllocTest<TypeParam>(); } // TODO(alkis): Test non-propagating allocators on move constructors. TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + using T = GeneratedType<TypeParam>; + Generator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; @@ -352,13 +299,10 @@ } template <typename TypeParam> -void InitializerListBucketAllocTest(std::false_type) {} - -template <typename TypeParam> -void InitializerListBucketAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InitializerListBucketAllocTest() { + using T = GeneratedType<TypeParam>; using A = typename TypeParam::allocator_type; - hash_internal::Generator<T> gen; + Generator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; A alloc(0); TypeParam m(values, 123, alloc); @@ -368,20 +312,17 @@ } TYPED_TEST_P(ConstructorTest, InitializerListBucketAlloc) { - InitializerListBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InitializerListBucketAllocTest<TypeParam>(); } template <typename TypeParam> -void InitializerListBucketHashAllocTest(std::false_type) {} - -template <typename TypeParam> -void InitializerListBucketHashAllocTest(std::true_type) { - using T = hash_internal::GeneratedType<TypeParam>; +void InitializerListBucketHashAllocTest() { + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using A = typename TypeParam::allocator_type; H hasher; A alloc(0); - hash_internal::Generator<T> gen; + Generator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values, 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); @@ -391,18 +332,18 @@ } TYPED_TEST_P(ConstructorTest, InitializerListBucketHashAlloc) { - InitializerListBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>()); + InitializerListBucketHashAllocTest<TypeParam>(); } TYPED_TEST_P(ConstructorTest, CopyAssignment) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::Generator<T> gen; + Generator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam n; n = m; @@ -415,14 +356,14 @@ // (it depends on traits). TYPED_TEST_P(ConstructorTest, MoveAssignment) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; using A = typename TypeParam::allocator_type; H hasher; E equal; A alloc(0); - hash_internal::Generator<T> gen; + Generator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam t(m); TypeParam n; @@ -433,8 +374,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + using T = GeneratedType<TypeParam>; + Generator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -442,8 +383,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + using T = GeneratedType<TypeParam>; + Generator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam n({gen()}); n = m; @@ -451,8 +392,8 @@ } TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + using T = GeneratedType<TypeParam>; + Generator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam t(m); TypeParam n({gen()}); @@ -461,8 +402,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + using T = GeneratedType<TypeParam>; + Generator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -470,8 +411,8 @@ } TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) { - using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + using T = GeneratedType<TypeParam>; + Generator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values); m = *&m; // Avoid -Wself-assign.
diff --git a/absl/container/internal/unordered_set_lookup_test.h b/absl/container/internal/unordered_set_lookup_test.h index b35f766..dc63118 100644 --- a/absl/container/internal/unordered_set_lookup_test.h +++ b/absl/container/internal/unordered_set_lookup_test.h
@@ -30,10 +30,9 @@ TYPED_TEST_SUITE_P(LookupTest); TYPED_TEST_P(LookupTest, Count) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& v : values) EXPECT_EQ(0, m.count(v)) << ::testing::PrintToString(v); @@ -43,10 +42,9 @@ } TYPED_TEST_P(LookupTest, Find) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& v : values) EXPECT_TRUE(m.end() == m.find(v)) << ::testing::PrintToString(v); @@ -65,10 +63,9 @@ } TYPED_TEST_P(LookupTest, EqualRange) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; for (const auto& v : values) { auto r = m.equal_range(v);
diff --git a/absl/container/internal/unordered_set_members_test.h b/absl/container/internal/unordered_set_members_test.h index 4c5e104..b416fef 100644 --- a/absl/container/internal/unordered_set_members_test.h +++ b/absl/container/internal/unordered_set_members_test.h
@@ -35,10 +35,10 @@ TYPED_TEST_P(MembersTest, Typedefs) { EXPECT_TRUE((std::is_same<typename TypeParam::key_type, typename TypeParam::value_type>())); - EXPECT_TRUE((absl::conjunction< - absl::negation<std::is_signed<typename TypeParam::size_type>>, + EXPECT_TRUE((std::conjunction< + std::negation<std::is_signed<typename TypeParam::size_type>>, std::is_integral<typename TypeParam::size_type>>())); - EXPECT_TRUE((absl::conjunction< + EXPECT_TRUE((std::conjunction< std::is_signed<typename TypeParam::difference_type>, std::is_integral<typename TypeParam::difference_type>>())); EXPECT_TRUE((std::is_convertible<
diff --git a/absl/container/internal/unordered_set_modifiers_test.h b/absl/container/internal/unordered_set_modifiers_test.h index d8864bb..b647642 100644 --- a/absl/container/internal/unordered_set_modifiers_test.h +++ b/absl/container/internal/unordered_set_modifiers_test.h
@@ -30,10 +30,9 @@ TYPED_TEST_SUITE_P(ModifiersTest); TYPED_TEST_P(ModifiersTest, Clear) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); m.clear(); @@ -42,8 +41,8 @@ } TYPED_TEST_P(ModifiersTest, Insert) { - using T = hash_internal::GeneratedType<TypeParam>; - T val = hash_internal::Generator<T>()(); + using T = GeneratedType<TypeParam>; + T val = Generator<T>()(); TypeParam m; auto p = m.insert(val); EXPECT_TRUE(p.second); @@ -53,8 +52,8 @@ } TYPED_TEST_P(ModifiersTest, InsertHint) { - using T = hash_internal::GeneratedType<TypeParam>; - T val = hash_internal::Generator<T>()(); + using T = GeneratedType<TypeParam>; + T val = Generator<T>()(); TypeParam m; auto it = m.insert(m.end(), val); EXPECT_TRUE(it != m.end()); @@ -65,18 +64,17 @@ } TYPED_TEST_P(ModifiersTest, InsertRange) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m; m.insert(values.begin(), values.end()); ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); } TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) { - using T = hash_internal::GeneratedType<TypeParam>; - T val = hash_internal::Generator<T>()(); + using T = GeneratedType<TypeParam>; + T val = Generator<T>()(); TypeParam m; m.reserve(10); const size_t original_capacity = m.bucket_count(); @@ -88,10 +86,9 @@ TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) { #if !defined(__GLIBCXX__) - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> base_values; - std::generate_n(std::back_inserter(base_values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(base_values), 10, Generator<T>()); std::vector<T> values; while (values.size() != 100) { values.insert(values.end(), base_values.begin(), base_values.end()); @@ -105,8 +102,8 @@ } TYPED_TEST_P(ModifiersTest, Emplace) { - using T = hash_internal::GeneratedType<TypeParam>; - T val = hash_internal::Generator<T>()(); + using T = GeneratedType<TypeParam>; + T val = Generator<T>()(); TypeParam m; // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps // with test traits/policy. @@ -119,8 +116,8 @@ } TYPED_TEST_P(ModifiersTest, EmplaceHint) { - using T = hash_internal::GeneratedType<TypeParam>; - T val = hash_internal::Generator<T>()(); + using T = GeneratedType<TypeParam>; + T val = Generator<T>()(); TypeParam m; // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps // with test traits/policy. @@ -150,10 +147,9 @@ }; TYPED_TEST_P(ModifiersTest, Erase) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); std::vector<T> values2; @@ -167,10 +163,9 @@ } TYPED_TEST_P(ModifiersTest, EraseRange) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); auto it = m.erase(m.begin(), m.end()); @@ -179,10 +174,9 @@ } TYPED_TEST_P(ModifiersTest, EraseKey) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> values; - std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(values), 10, Generator<T>()); TypeParam m(values.begin(), values.end()); ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); EXPECT_EQ(1, m.erase(values[0])); @@ -192,11 +186,11 @@ } TYPED_TEST_P(ModifiersTest, Swap) { - using T = hash_internal::GeneratedType<TypeParam>; + using T = GeneratedType<TypeParam>; std::vector<T> v1; std::vector<T> v2; - std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>()); - std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>()); + std::generate_n(std::back_inserter(v1), 5, Generator<T>()); + std::generate_n(std::back_inserter(v2), 5, Generator<T>()); TypeParam m1(v1.begin(), v1.end()); TypeParam m2(v2.begin(), v2.end()); EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v1));
diff --git a/absl/container/linked_hash_map.h b/absl/container/linked_hash_map.h new file mode 100644 index 0000000..cec0ada --- /dev/null +++ b/absl/container/linked_hash_map.h
@@ -0,0 +1,660 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// File: linked_hash_map.h +// ----------------------------------------------------------------------------- +// +// This is a simple insertion-ordered map. It provides O(1) amortized +// insertions and lookups, as well as iteration over the map in the insertion +// order. +// +// This class is thread-compatible. +// +// Iterators point into the list and should be stable in the face of +// mutations, except for an iterator pointing to an element that was just +// deleted. +// +// This class supports heterogeneous lookups. + +#ifndef ABSL_CONTAINER_LINKED_HASH_MAP_H_ +#define ABSL_CONTAINER_LINKED_HASH_MAP_H_ + +#include <cassert> +#include <cstddef> +#include <initializer_list> +#include <list> +#include <memory> +#include <string> +#include <tuple> +#include <type_traits> +#include <utility> + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/base/internal/throw_delegate.h" +#include "absl/base/optimization.h" +#include "absl/container/flat_hash_set.h" +#include "absl/container/internal/common.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN + +template <typename Key, typename Value, + typename KeyHash = typename absl::flat_hash_set<Key>::hasher, + typename KeyEq = + typename absl::flat_hash_set<Key, KeyHash>::key_equal, + typename Alloc = std::allocator<std::pair<const Key, Value>>> +class linked_hash_map { + using KeyArgImpl = absl::container_internal::KeyArg< + absl::container_internal::IsTransparent<KeyEq>::value && + absl::container_internal::IsTransparent<KeyHash>::value>; + + public: + using key_type = Key; + using mapped_type = Value; + using hasher = KeyHash; + using key_equal = KeyEq; + using value_type = std::pair<const key_type, mapped_type>; + using allocator_type = Alloc; + using difference_type = ptrdiff_t; + + private: + template <class K> + using key_arg = typename KeyArgImpl::template type<K, key_type>; + + using ListType = std::list<value_type, Alloc>; + + template <class Fn> + class Wrapped { + template <typename K> + static const K& ToKey(const K& k) { + return k; + } + static const key_type& ToKey(typename ListType::const_iterator it) { + return it->first; + } + static const key_type& ToKey(typename ListType::iterator it) { + return it->first; + } + + Fn fn_; + + friend linked_hash_map; + + public: + using is_transparent = void; + + Wrapped() = default; + explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} + + template <class... Args> + auto operator()(Args&&... args) const + -> decltype(this->fn_(ToKey(args)...)) { + return fn_(ToKey(args)...); + } + }; + using SetType = + absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, + Wrapped<key_equal>, Alloc>; + + class NodeHandle { + public: + using key_type = linked_hash_map::key_type; + using mapped_type = linked_hash_map::mapped_type; + using allocator_type = linked_hash_map::allocator_type; + + constexpr NodeHandle() noexcept = default; + NodeHandle(NodeHandle&& nh) noexcept = default; + ~NodeHandle() = default; + NodeHandle& operator=(NodeHandle&& node) noexcept = default; + bool empty() const noexcept { return list_.empty(); } + explicit operator bool() const noexcept { return !empty(); } + allocator_type get_allocator() const { return list_.get_allocator(); } + const key_type& key() const { return list_.front().first; } + mapped_type& mapped() { return list_.front().second; } + void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } + + private: + friend linked_hash_map; + + explicit NodeHandle(ListType list) : list_(std::move(list)) {} + ListType list_; + }; + + template <class Iterator, class NodeType> + struct InsertReturnType { + Iterator position; + bool inserted; + NodeType node; + }; + + public: + using iterator = typename ListType::iterator; + using const_iterator = typename ListType::const_iterator; + using reverse_iterator = typename ListType::reverse_iterator; + using const_reverse_iterator = typename ListType::const_reverse_iterator; + using reference = typename ListType::reference; + using const_reference = typename ListType::const_reference; + using size_type = typename ListType::size_type; + using pointer = typename std::allocator_traits<allocator_type>::pointer; + using const_pointer = + typename std::allocator_traits<allocator_type>::const_pointer; + using node_type = NodeHandle; + using insert_return_type = InsertReturnType<iterator, node_type>; + + linked_hash_map() {} + + explicit linked_hash_map(size_t bucket_count, const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : set_(bucket_count, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), + alloc), + list_(alloc) {} + + linked_hash_map(size_t bucket_count, const hasher& hash, + const allocator_type& alloc) + : linked_hash_map(bucket_count, hash, key_equal(), alloc) {} + + linked_hash_map(size_t bucket_count, const allocator_type& alloc) + : linked_hash_map(bucket_count, hasher(), key_equal(), alloc) {} + + explicit linked_hash_map(const allocator_type& alloc) + : linked_hash_map(0, hasher(), key_equal(), alloc) {} + + template <class InputIt> + linked_hash_map(InputIt first, InputIt last, size_t bucket_count = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : linked_hash_map(bucket_count, hash, eq, alloc) { + insert(first, last); + } + + template <class InputIt> + linked_hash_map(InputIt first, InputIt last, size_t bucket_count, + const hasher& hash, const allocator_type& alloc) + : linked_hash_map(first, last, bucket_count, hash, key_equal(), alloc) {} + + template <class InputIt> + linked_hash_map(InputIt first, InputIt last, size_t bucket_count, + const allocator_type& alloc) + : linked_hash_map(first, last, bucket_count, hasher(), key_equal(), + alloc) {} + + template <class InputIt> + linked_hash_map(InputIt first, InputIt last, const allocator_type& alloc) + : linked_hash_map(first, last, /*bucket_count=*/0, hasher(), key_equal(), + alloc) {} + + linked_hash_map(std::initializer_list<value_type> init, + size_t bucket_count = 0, const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : linked_hash_map(init.begin(), init.end(), bucket_count, hash, eq, + alloc) {} + + linked_hash_map(std::initializer_list<value_type> init, size_t bucket_count, + const hasher& hash, const allocator_type& alloc) + : linked_hash_map(init, bucket_count, hash, key_equal(), alloc) {} + + linked_hash_map(std::initializer_list<value_type> init, size_t bucket_count, + const allocator_type& alloc) + : linked_hash_map(init, bucket_count, hasher(), key_equal(), alloc) {} + + linked_hash_map(std::initializer_list<value_type> init, + const allocator_type& alloc) + : linked_hash_map(init, /*bucket_count=*/0, hasher(), key_equal(), + alloc) {} + + linked_hash_map(const linked_hash_map& other) + : linked_hash_map(other.bucket_count(), other.hash_function(), + other.key_eq(), other.get_allocator()) { + CopyFrom(other); + } + + linked_hash_map(const linked_hash_map& other, const allocator_type& alloc) + : linked_hash_map(other.bucket_count(), other.hash_function(), + other.key_eq(), alloc) { + CopyFrom(other); + } + + linked_hash_map(linked_hash_map&& other) noexcept + : set_(std::move(other.set_)), list_(std::move(other.list_)) { + // Since the list and set must agree for other to end up "valid", + // explicitly clear them. + other.set_.clear(); + other.list_.clear(); + } + + linked_hash_map(linked_hash_map&& other, const allocator_type& alloc) + : linked_hash_map(0, other.hash_function(), other.key_eq(), alloc) { + if (get_allocator() == other.get_allocator()) { + *this = std::move(other); + } else { + CopyFrom(std::move(other)); + } + } + + linked_hash_map& operator=(const linked_hash_map& other) { + if (this == &other) return *this; + // Make a new set, with other's hash/eq/alloc. + set_ = SetType(other.bucket_count(), other.set_.hash_function(), + other.set_.key_eq(), other.get_allocator()); + // Copy the list, with other's allocator. + list_ = ListType(other.get_allocator()); + CopyFrom(other); + return *this; + } + + linked_hash_map& operator=(linked_hash_map&& other) noexcept { + // underlying containers will handle progagate_on_container_move details + set_ = std::move(other.set_); + list_ = std::move(other.list_); + other.set_.clear(); + other.list_.clear(); + return *this; + } + + linked_hash_map& operator=(std::initializer_list<value_type> values) { + clear(); + insert(values.begin(), values.end()); + return *this; + } + + // Derive size_ from set_, as list::size might be O(N). + size_type size() const { return set_.size(); } + size_type max_size() const noexcept { return ~size_type{}; } + bool empty() const { return set_.empty(); } + + // Iteration is list-like, in insertion order. + // These are all forwarded. + iterator begin() { return list_.begin(); } + iterator end() { return list_.end(); } + const_iterator begin() const { return list_.begin(); } + const_iterator end() const { return list_.end(); } + const_iterator cbegin() const { return list_.cbegin(); } + const_iterator cend() const { return list_.cend(); } + reverse_iterator rbegin() { return list_.rbegin(); } + reverse_iterator rend() { return list_.rend(); } + const_reverse_iterator rbegin() const { return list_.rbegin(); } + const_reverse_iterator rend() const { return list_.rend(); } + const_reverse_iterator crbegin() const { return list_.crbegin(); } + const_reverse_iterator crend() const { return list_.crend(); } + reference front() { return list_.front(); } + reference back() { return list_.back(); } + const_reference front() const { return list_.front(); } + const_reference back() const { return list_.back(); } + + void pop_front() { erase(begin()); } + void pop_back() { erase(std::prev(end())); } + + ABSL_ATTRIBUTE_REINITIALIZES void clear() { + set_.clear(); + list_.clear(); + } + + void reserve(size_t n) { set_.reserve(n); } + size_t capacity() const { return set_.capacity(); } + size_t bucket_count() const { return set_.bucket_count(); } + float load_factor() const { return set_.load_factor(); } + + hasher hash_function() const { return set_.hash_function().fn_; } + key_equal key_eq() const { return set_.key_eq().fn_; } + allocator_type get_allocator() const { return list_.get_allocator(); } + + template <class K = key_type> + size_type erase(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return 0; + auto list_it = *found; + // Erase set entry first since it refers to the list element. + set_.erase(found); + list_.erase(list_it); + return 1; + } + + iterator erase(const_iterator position) { + auto found = set_.find(position); + assert(*found == position); + set_.erase(found); + return list_.erase(position); + } + + iterator erase(iterator position) { + return erase(static_cast<const_iterator>(position)); + } + + iterator erase(iterator first, iterator last) { + while (first != last) first = erase(first); + return first; + } + + iterator erase(const_iterator first, const_iterator last) { + while (first != last) first = erase(first); + if (first == end()) return end(); + return *set_.find(first); + } + + template <class K = key_type> + iterator find(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return *found; + } + + template <class K = key_type> + const_iterator find(const key_arg<K>& key) const { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return *found; + } + + template <class K = key_type> + size_type count(const key_arg<K>& key) const { + return contains(key) ? 1 : 0; + } + template <class K = key_type> + bool contains(const key_arg<K>& key) const { + return set_.contains(key); + } + + template <class K = key_type> + mapped_type& at(const key_arg<K>& key) { + auto it = find(key); + if (ABSL_PREDICT_FALSE(it == end())) { + absl::base_internal::ThrowStdOutOfRange("absl::linked_hash_map::at"); + } + return it->second; + } + + template <class K = key_type> + const mapped_type& at(const key_arg<K>& key) const { + return const_cast<linked_hash_map*>(this)->at(key); + } + + template <class K = key_type> + std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { + auto iter = set_.find(key); + if (iter == set_.end()) return {end(), end()}; + return {*iter, std::next(*iter)}; + } + + template <class K = key_type> + std::pair<const_iterator, const_iterator> equal_range( + const key_arg<K>& key) const { + auto iter = set_.find(key); + if (iter == set_.end()) return {end(), end()}; + return {*iter, std::next(*iter)}; + } + + template <class K = key_type> + mapped_type& operator[](const key_arg<K>& key) { + return LazyEmplaceInternal(key).first->second; + } + + template <class K = key_type, K* = nullptr> + mapped_type& operator[](key_arg<K>&& key) { + return LazyEmplaceInternal(std::forward<key_arg<K>>(key)).first->second; + } + + std::pair<iterator, bool> insert(const value_type& v) { + return InsertInternal(v); + } + std::pair<iterator, bool> insert(value_type&& v) { + return InsertInternal(std::move(v)); + } + + iterator insert(const_iterator, const value_type& v) { + return insert(v).first; + } + iterator insert(const_iterator, value_type&& v) { + return insert(std::move(v)).first; + } + + void insert(std::initializer_list<value_type> ilist) { + insert(ilist.begin(), ilist.end()); + } + + template <class InputIt> + void insert(InputIt first, InputIt last) { + for (; first != last; ++first) insert(*first); + } + + insert_return_type insert(node_type&& node) { + if (node.empty()) return {end(), false, node_type()}; + if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { + list_.splice(list_.end(), node.list_); + return {*set_itr, true, node_type()}; + } else { + return {*set_itr, false, std::move(node)}; + } + } + + iterator insert(const_iterator, node_type&& node) { + return insert(std::move(node)).first; + } + + // The last two template parameters ensure that both arguments are rvalues + // (lvalue arguments are handled by the overloads below). This is necessary + // for supporting bitfield arguments. + // + // union { int n : 1; }; + // linked_hash_map<int, int> m; + // m.insert_or_assign(n, n); + template <class K = key_type, class V = mapped_type, K* = nullptr, + V* = nullptr> + std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v) { + return InsertOrAssignInternal(std::forward<key_arg<K>>(k), + std::forward<V>(v)); + } + + template <class K = key_type, class V = mapped_type, K* = nullptr> + std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v) { + return InsertOrAssignInternal(std::forward<key_arg<K>>(k), v); + } + + template <class K = key_type, class V = mapped_type, V* = nullptr> + std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v) { + return InsertOrAssignInternal(k, std::forward<V>(v)); + } + + template <class K = key_type, class V = mapped_type> + std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) { + return InsertOrAssignInternal(k, v); + } + + template <class K = key_type, class V = mapped_type, K* = nullptr, + V* = nullptr> + iterator insert_or_assign(const_iterator, key_arg<K>&& k, V&& v) { + return insert_or_assign(std::forward<key_arg<K>>(k), std::forward<V>(v)) + .first; + } + + template <class K = key_type, class V = mapped_type, K* = nullptr> + iterator insert_or_assign(const_iterator, key_arg<K>&& k, const V& v) { + return insert_or_assign(std::forward<key_arg<K>>(k), v).first; + } + + template <class K = key_type, class V = mapped_type, V* = nullptr> + iterator insert_or_assign(const_iterator, const key_arg<K>& k, V&& v) { + return insert_or_assign(k, std::forward<V>(v)).first; + } + + template <class K = key_type, class V = mapped_type> + iterator insert_or_assign(const_iterator, const key_arg<K>& k, const V& v) { + return insert_or_assign(k, v).first; + } + + template <typename... Args> + std::pair<iterator, bool> emplace(Args&&... args) { + ListType node_donor; + auto list_iter = + node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); + auto ins = set_.insert(list_iter); + if (!ins.second) return {*ins.first, false}; + list_.splice(list_.end(), node_donor, list_iter); + return {list_iter, true}; + } + + template <class K = key_type, class... Args, K* = nullptr> + iterator try_emplace(const_iterator, key_arg<K>&& k, Args&&... args) { + return try_emplace(std::forward<key_arg<K>>(k), std::forward<Args>(args)...) + .first; + } + + template <typename... Args> + iterator emplace_hint(const_iterator, Args&&... args) { + return emplace(std::forward<Args>(args)...).first; + } + + template <class K = key_type, typename... Args, K* = nullptr> + std::pair<iterator, bool> try_emplace(key_arg<K>&& key, Args&&... args) { + return LazyEmplaceInternal(std::forward<key_arg<K>>(key), + std::forward<Args>(args)...); + } + + template <typename H, typename E> + void merge(linked_hash_map<Key, Value, H, E, Alloc>& src) { + auto itr = src.list_.begin(); + while (itr != src.list_.end()) { + if (contains(itr->first)) { + ++itr; + } else { + insert(src.extract(itr++)); + } + } + } + + template <typename H, typename E> + void merge(linked_hash_map<Key, Value, H, E, Alloc>&& src) { + merge(src); + } + + node_type extract(const_iterator position) { + set_.erase(position->first); + ListType extracted_node_list; + extracted_node_list.splice(extracted_node_list.end(), list_, position); + return node_type(std::move(extracted_node_list)); + } + + template <class K = key_type, + std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> + node_type extract(const key_arg<K>& key) { + auto node = set_.extract(key); + if (node.empty()) return node_type(); + ListType extracted_node_list; + extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); + return node_type(std::move(extracted_node_list)); + } + + template <typename H, typename E> + void splice(const_iterator, linked_hash_map<Key, Value, H, E, Alloc>& list, + const_iterator it) { + if (&list == this) { + list_.splice(list_.end(), list.list_, it); + } else { + insert(list.extract(it)); + } + } + + template <class K = key_type, typename... Args> + std::pair<iterator, bool> try_emplace(const key_arg<K>& key, Args&&... args) { + return LazyEmplaceInternal(key, std::forward<Args>(args)...); + } + + template <class K = key_type, typename... Args> + iterator try_emplace(const_iterator, const key_arg<K>& key, Args&&... args) { + return LazyEmplaceInternal(key, std::forward<Args>(args)...).first; + } + + void swap(linked_hash_map& other) noexcept { + using std::swap; + swap(set_, other.set_); + swap(list_, other.list_); + } + + friend bool operator==(const linked_hash_map& a, const linked_hash_map& b) { + if (a.size() != b.size()) return false; + const linked_hash_map* outer = &a; + const linked_hash_map* inner = &b; + if (outer->capacity() > inner->capacity()) std::swap(outer, inner); + for (const value_type& elem : *outer) { + auto it = inner->find(elem.first); + if (it == inner->end()) return false; + if (it->second != elem.second) return false; + } + + return true; + } + + friend bool operator!=(const linked_hash_map& a, const linked_hash_map& b) { + return !(a == b); + } + + void rehash(size_t n) { set_.rehash(n); } + + private: + template <typename Other> + void CopyFrom(Other&& other) { + for (auto& elem : other.list_) { + set_.insert(list_.insert(list_.end(), std::move(elem))); + } + assert(set_.size() == list_.size()); + } + + template <typename U> + std::pair<iterator, bool> InsertInternal(U&& pair) { // NOLINT(build/c++11) + bool constructed = false; + auto set_iter = set_.lazy_emplace(pair.first, [&](const auto& ctor) { + constructed = true; + ctor(list_.emplace(list_.end(), std::forward<U>(pair))); + }); + return {*set_iter, constructed}; + } + + template <class K, class V> + std::pair<iterator, bool> InsertOrAssignInternal(K&& k, V&& v) { + auto [it, inserted] = + LazyEmplaceInternal(std::forward<K>(k), std::forward<V>(v)); + if (!inserted) it->second = std::forward<V>(v); + return {it, inserted}; + } + + template <typename K, typename... Args> + std::pair<iterator, bool> LazyEmplaceInternal(K&& key, Args&&... args) { + bool constructed = false; + auto set_iter = set_.lazy_emplace( + key, [this, &constructed, &key, &args...](const auto& ctor) { + auto list_iter = + list_.emplace(list_.end(), std::piecewise_construct, + std::forward_as_tuple(std::forward<K>(key)), + std::forward_as_tuple(std::forward<Args>(args)...)); + constructed = true; + ctor(list_iter); + }); + return {*set_iter, constructed}; + } + + // The set component, used for speedy lookups. + SetType set_; + + // The list component, used for maintaining insertion order. + ListType list_; +}; + +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_LINKED_HASH_MAP_H_
diff --git a/absl/container/linked_hash_map_benchmark.cc b/absl/container/linked_hash_map_benchmark.cc new file mode 100644 index 0000000..5a0db38 --- /dev/null +++ b/absl/container/linked_hash_map_benchmark.cc
@@ -0,0 +1,140 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <algorithm> +#include <cstddef> +#include <string> +#include <vector> + +#include "absl/container/linked_hash_map.h" +#include "absl/functional/function_ref.h" +#include "absl/strings/str_format.h" +#include "absl/strings/string_view.h" +#include "benchmark/benchmark.h" + +namespace { + +struct BenchmarkData { + std::vector<std::string> sample; + size_t str_bytes = 0; + explicit BenchmarkData(int size, + absl::FunctionRef<std::string(int)> factory) { + sample.reserve(size); + for (int i = 0; i < size; ++i) { + sample.push_back(factory(i)); + str_bytes += sample.back().size(); + } + } +}; + +void BenchmarkTryEmplaceStrings(benchmark::State& state, + absl::FunctionRef<std::string(int)> factory) { + BenchmarkData data(state.range(0), factory); + + // Make a batch around 1Mi bytes. + const size_t batch_size = + std::max(size_t{1}, size_t{1000000} / data.str_bytes); + std::vector<absl::linked_hash_map<std::string, int>> sets(batch_size); + + while (state.KeepRunningBatch(batch_size)) { + state.PauseTiming(); + for (auto& set : sets) set.clear(); + state.ResumeTiming(); + for (auto& set : sets) { + for (const auto& str : data.sample) { + benchmark::DoNotOptimize(set.try_emplace(str)); + } + } + } + + state.SetItemsProcessed(state.iterations() * state.range(0)); + state.SetBytesProcessed(state.iterations() * data.str_bytes); +} + +void BenchmarkInsertOrAssignStrings( + benchmark::State& state, absl::FunctionRef<std::string(int)> factory) { + BenchmarkData data(state.range(0), factory); + + // Make a batch around 1Mi bytes. + const size_t batch_size = std::max(size_t{1}, 1000000 / data.str_bytes); + std::vector<absl::linked_hash_map<std::string, int>> sets(batch_size); + + while (state.KeepRunningBatch(batch_size)) { + state.PauseTiming(); + for (auto& set : sets) set.clear(); + state.ResumeTiming(); + for (auto& set : sets) { + for (const auto& str : data.sample) { + benchmark::DoNotOptimize(set.insert_or_assign(str, 0)); + } + } + } + + state.SetItemsProcessed(state.iterations() * state.range(0)); + state.SetBytesProcessed(state.iterations() * data.str_bytes); +} + +constexpr absl::string_view kFormatShort = "%10d"; +constexpr absl::string_view kFormatLong = + "a longer string that exceeds the SSO %10d"; + +void BM_TryEmplaceShortStrings_Hit(benchmark::State& state) { + BenchmarkTryEmplaceStrings( + state, [](int i) { return absl::StrFormat(kFormatShort, i); }); +} +BENCHMARK(BM_TryEmplaceShortStrings_Hit)->Range(1, 1 << 16); + +void BM_TryEmplaceLongStrings_Hit(benchmark::State& state) { + BenchmarkTryEmplaceStrings( + state, [](int i) { return absl::StrFormat(kFormatLong, i); }); +} +BENCHMARK(BM_TryEmplaceLongStrings_Hit)->Range(1, 1 << 16); + +void BM_TryEmplaceShortStrings_Miss(benchmark::State& state) { + BenchmarkTryEmplaceStrings( + state, [](int i) { return absl::StrFormat(kFormatShort, i % 20); }); +} +BENCHMARK(BM_TryEmplaceShortStrings_Miss)->Range(1, 1 << 16); + +void BM_TryEmplaceLongStrings_Miss(benchmark::State& state) { + BenchmarkTryEmplaceStrings( + state, [](int i) { return absl::StrFormat(kFormatLong, i % 20); }); +} +BENCHMARK(BM_TryEmplaceLongStrings_Miss)->Range(1, 1 << 16); + +void BM_InsertOrAssignShortStrings_Hit(benchmark::State& state) { + BenchmarkInsertOrAssignStrings( + state, [](int i) { return absl::StrFormat(kFormatShort, i); }); +} +BENCHMARK(BM_InsertOrAssignShortStrings_Hit)->Range(1, 1 << 16); + +void BM_InsertOrAssignLongStrings_Hit(benchmark::State& state) { + BenchmarkInsertOrAssignStrings( + state, [](int i) { return absl::StrFormat(kFormatLong, i); }); +} +BENCHMARK(BM_InsertOrAssignLongStrings_Hit)->Range(1, 1 << 16); + +void BM_InsertOrAssignShortStrings_Miss(benchmark::State& state) { + BenchmarkInsertOrAssignStrings( + state, [](int i) { return absl::StrFormat(kFormatShort, i % 20); }); +} +BENCHMARK(BM_InsertOrAssignShortStrings_Miss)->Range(1, 1 << 16); + +void BM_InsertOrAssignLongStrings_Miss(benchmark::State& state) { + BenchmarkInsertOrAssignStrings( + state, [](int i) { return absl::StrFormat(kFormatLong, i % 20); }); +} +BENCHMARK(BM_InsertOrAssignLongStrings_Miss)->Range(1, 1 << 16); + +} // namespace
diff --git a/absl/container/linked_hash_map_test.cc b/absl/container/linked_hash_map_test.cc new file mode 100644 index 0000000..54d42fe --- /dev/null +++ b/absl/container/linked_hash_map_test.cc
@@ -0,0 +1,964 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/container/linked_hash_map.h" + +#include <algorithm> +#include <cstddef> +#include <memory> +#include <string> +#include <tuple> +#include <type_traits> +#include <utility> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/base/internal/exception_testing.h" +#include "absl/container/internal/hash_generator_testing.h" +#include "absl/container/internal/hash_policy_testing.h" +#include "absl/container/internal/heterogeneous_lookup_testing.h" +#include "absl/container/internal/test_instance_tracker.h" +#include "absl/container/internal/unordered_map_constructor_test.h" +#include "absl/container/internal/unordered_map_lookup_test.h" +#include "absl/container/internal/unordered_map_members_test.h" +#include "absl/container/internal/unordered_map_modifiers_test.h" +#include "absl/strings/string_view.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { +namespace { + +using ::testing::ElementsAre; +using ::testing::Pair; +using ::testing::Pointee; + +template <class K, class V> +using Map = linked_hash_map<K, V, StatefulTestingHash, StatefulTestingEqual, + Alloc<std::pair<const K, V>>>; + +static_assert(!std::is_standard_layout<NonStandardLayout>(), ""); + +using MapTypes = + ::testing::Types<Map<int, int>, Map<std::string, int>, + Map<Enum, std::string>, Map<EnumClass, int>, + Map<int, NonStandardLayout>, Map<NonStandardLayout, int>>; + +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashMap, ConstructorTest, MapTypes); +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashMap, LookupTest, MapTypes); +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashMap, MembersTest, MapTypes); +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashMap, ModifiersTest, MapTypes); + +// Tests that the range constructor works. +TEST(LinkedHashMapTest, RangeConstruct) { + const std::pair<int, int> items[] = {{1, 2}, {2, 3}, {3, 4}}; + EXPECT_THAT((linked_hash_map<int, int>(std::begin(items), std::end(items))), + ElementsAre(Pair(1, 2), Pair(2, 3), Pair(3, 4))); +} + +// Tests that copying works. +TEST(LinkedHashMapTest, Copy) { + linked_hash_map<int, int> m{{2, 12}, {3, 13}}; + auto copy = m; + + EXPECT_TRUE(copy.contains(2)); + auto found = copy.find(2); + ASSERT_TRUE(found != copy.end()); + for (auto iter = copy.begin(); iter != copy.end(); ++iter) { + if (iter == found) return; + } + FAIL() << "Copied map's find method returned an invalid iterator."; +} + +// Tests that assignment works. +TEST(LinkedHashMapTest, Assign) { + linked_hash_map<int, int> m{{2, 12}, {3, 13}}; + linked_hash_map<int, int> n{{4, 14}}; + + n = m; + EXPECT_TRUE(n.contains(2)); + auto found = n.find(2); + ASSERT_TRUE(found != n.end()); + for (auto iter = n.begin(); iter != n.end(); ++iter) { + if (iter == found) return; + } + FAIL() << "Assigned map's find method returned an invalid iterator."; +} + +// Tests that move constructor works. +TEST(LinkedHashMapTest, Move) { + // Use unique_ptr as an example of a non-copyable type. + linked_hash_map<int, std::unique_ptr<int>> m; + m[2] = std::make_unique<int>(12); + m[3] = std::make_unique<int>(13); + linked_hash_map<int, std::unique_ptr<int>> n = std::move(m); + EXPECT_THAT(n, ElementsAre(Pair(2, Pointee(12)), Pair(3, Pointee(13)))); +} + +TEST(LinkedHashMapTest, CanInsertMoveOnly) { + linked_hash_map<int, std::unique_ptr<int>> m; + struct Data { + int k, v; + }; + const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}}; + for (const auto& kv : data) + m.insert({kv.k, std::make_unique<int>(int{kv.v})}); + EXPECT_TRUE(m.contains(2)); + auto found = m.find(2); + ASSERT_TRUE(found != m.end()); + EXPECT_EQ(234, *found->second); +} + +TEST(LinkedHashMapTest, CanEmplaceMoveOnly) { + linked_hash_map<int, std::unique_ptr<int>> m; + struct Data { + int k, v; + }; + const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}}; + for (const auto& kv : data) { + m.emplace(std::piecewise_construct, std::make_tuple(kv.k), + std::make_tuple(new int{kv.v})); + } + EXPECT_TRUE(m.contains(2)); + auto found = m.find(2); + ASSERT_TRUE(found != m.end()); + EXPECT_EQ(234, *found->second); +} + +struct NoCopy { + explicit NoCopy(int x) : x(x) {} + NoCopy(const NoCopy&) = delete; + NoCopy& operator=(const NoCopy&) = delete; + NoCopy(NoCopy&&) = delete; + NoCopy& operator=(NoCopy&&) = delete; + int x; +}; + +TEST(LinkedHashMapTest, CanEmplaceNoMoveNoCopy) { + linked_hash_map<int, NoCopy> m; + struct Data { + int k, v; + }; + const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}}; + for (const auto& kv : data) { + m.emplace(std::piecewise_construct, std::make_tuple(kv.k), + std::make_tuple(kv.v)); + } + EXPECT_TRUE(m.contains(2)); + auto found = m.find(2); + ASSERT_TRUE(found != m.end()); + EXPECT_EQ(234, found->second.x); +} + +TEST(LinkedHashMapTest, ConstKeys) { + linked_hash_map<int, int> m; + m.insert(std::make_pair(1, 2)); + // Test that keys are const in iteration. + std::pair<const int, int>& p = *m.begin(); + EXPECT_EQ(1, p.first); +} + +// Tests that iteration from begin() to end() works +TEST(LinkedHashMapTest, Iteration) { + linked_hash_map<int, int> m; + EXPECT_TRUE(m.begin() == m.end()); + + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(3, 13)); + + linked_hash_map<int, int>::iterator i = m.begin(); + ASSERT_TRUE(m.begin() == i); + ASSERT_TRUE(m.end() != i); + EXPECT_EQ(2, i->first); + EXPECT_EQ(12, i->second); + + ++i; + ASSERT_TRUE(m.end() != i); + EXPECT_EQ(1, i->first); + EXPECT_EQ(11, i->second); + + ++i; + ASSERT_TRUE(m.end() != i); + EXPECT_EQ(3, i->first); + EXPECT_EQ(13, i->second); + + ++i; // Should be the end of the line. + ASSERT_TRUE(m.end() == i); +} + +// Tests that reverse iteration from rbegin() to rend() works +TEST(LinkedHashMapTest, ReverseIteration) { + linked_hash_map<int, int> m; + EXPECT_TRUE(m.rbegin() == m.rend()); + + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(3, 13)); + + linked_hash_map<int, int>::reverse_iterator i = m.rbegin(); + ASSERT_TRUE(m.rbegin() == i); + ASSERT_TRUE(m.rend() != i); + EXPECT_EQ(3, i->first); + EXPECT_EQ(13, i->second); + + ++i; + ASSERT_TRUE(m.rend() != i); + EXPECT_EQ(1, i->first); + EXPECT_EQ(11, i->second); + + ++i; + ASSERT_TRUE(m.rend() != i); + EXPECT_EQ(2, i->first); + EXPECT_EQ(12, i->second); + + ++i; // Should be the end of the line. + ASSERT_TRUE(m.rend() == i); +} + +// Tests that clear() works +TEST(LinkedHashMapTest, Clear) { + linked_hash_map<int, int> m; + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(3, 13)); + + ASSERT_EQ(3, m.size()); + + m.clear(); + + EXPECT_EQ(0, m.size()); + + m.clear(); // Make sure we can call it on an empty map. + + EXPECT_EQ(0, m.size()); +} + +// Tests that size() works. +TEST(LinkedHashMapTest, Size) { + linked_hash_map<int, int> m; + EXPECT_EQ(0, m.size()); + m.insert(std::make_pair(2, 12)); + EXPECT_EQ(1, m.size()); + m.insert(std::make_pair(1, 11)); + EXPECT_EQ(2, m.size()); + m.insert(std::make_pair(3, 13)); + EXPECT_EQ(3, m.size()); + m.clear(); + EXPECT_EQ(0, m.size()); +} + +// Tests empty() +TEST(LinkedHashMapTest, Empty) { + linked_hash_map<int, int> m; + ASSERT_TRUE(m.empty()); + m.insert(std::make_pair(2, 12)); + ASSERT_FALSE(m.empty()); + m.clear(); + ASSERT_TRUE(m.empty()); +} + +TEST(LinkedHashMapTest, Erase) { + linked_hash_map<int, int> m; + ASSERT_EQ(0, m.size()); + EXPECT_EQ(0, m.erase(2)); // Nothing to erase yet + + m.insert(std::make_pair(2, 12)); + ASSERT_EQ(1, m.size()); + EXPECT_EQ(1, m.erase(2)); + EXPECT_EQ(0, m.size()); + + EXPECT_EQ(0, m.erase(2)); // Make sure nothing bad happens if we repeat. + EXPECT_EQ(0, m.size()); +} + +TEST(LinkedHashMapTest, Erase2) { + linked_hash_map<int, int> m; + ASSERT_EQ(0, m.size()); + EXPECT_EQ(0, m.erase(2)); // Nothing to erase yet + + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(3, 13)); + m.insert(std::make_pair(4, 14)); + ASSERT_EQ(4, m.size()); + + // Erase middle two + EXPECT_EQ(1, m.erase(1)); + EXPECT_EQ(1, m.erase(3)); + + EXPECT_EQ(2, m.size()); + + // Make sure we can still iterate over everything that's left. + linked_hash_map<int, int>::iterator it = m.begin(); + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(12, it->second); + ++it; + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(14, it->second); + ++it; + ASSERT_TRUE(it == m.end()); + + EXPECT_EQ(0, m.erase(1)); // Make sure nothing bad happens if we repeat. + ASSERT_EQ(2, m.size()); + + EXPECT_EQ(1, m.erase(2)); + EXPECT_EQ(1, m.erase(4)); + ASSERT_EQ(0, m.size()); + + EXPECT_EQ(0, m.erase(1)); // Make sure nothing bad happens if we repeat. + ASSERT_EQ(0, m.size()); +} + +// Test that erase(iter,iter) and erase(iter) compile and work. +TEST(LinkedHashMapTest, Erase3) { + linked_hash_map<int, int> m; + + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(3, 13)); + m.insert(std::make_pair(4, 14)); + + // Erase middle two + linked_hash_map<int, int>::iterator it2 = m.find(2); + linked_hash_map<int, int>::iterator it4 = m.find(4); + EXPECT_EQ(m.erase(it2, it4), m.find(4)); + EXPECT_EQ(2, m.size()); + + // Make sure we can still iterate over everything that's left. + linked_hash_map<int, int>::iterator it = m.begin(); + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(11, it->second); + ++it; + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(14, it->second); + ++it; + ASSERT_TRUE(it == m.end()); + + // Erase first one using an iterator. + EXPECT_EQ(m.erase(m.begin()), m.find(4)); + + // Only the last element should be left. + it = m.begin(); + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(14, it->second); + ++it; + ASSERT_TRUE(it == m.end()); +} + +// Test all types of insertion +TEST(LinkedHashMapTest, Insertion) { + linked_hash_map<int, int> m; + ASSERT_EQ(0, m.size()); + std::pair<linked_hash_map<int, int>::iterator, bool> result; + + result = m.insert(std::make_pair(2, 12)); + ASSERT_EQ(1, m.size()); + EXPECT_TRUE(result.second); + EXPECT_EQ(2, result.first->first); + EXPECT_EQ(12, result.first->second); + + result = m.insert(std::make_pair(1, 11)); + ASSERT_EQ(2, m.size()); + EXPECT_TRUE(result.second); + EXPECT_EQ(1, result.first->first); + EXPECT_EQ(11, result.first->second); + + result = m.insert(std::make_pair(3, 13)); + linked_hash_map<int, int>::iterator result_iterator = result.first; + ASSERT_EQ(3, m.size()); + EXPECT_TRUE(result.second); + EXPECT_EQ(3, result.first->first); + EXPECT_EQ(13, result.first->second); + + result = m.insert(std::make_pair(3, 13)); + EXPECT_EQ(3, m.size()); + EXPECT_FALSE(result.second) << "No insertion should have occurred."; + EXPECT_TRUE(result_iterator == result.first) + << "Duplicate insertion should have given us the original iterator."; + + std::vector<std::pair<int, int>> v = {{3, 13}, {4, 14}, {5, 15}}; + m.insert(v.begin(), v.end()); + // Expect 4 and 5 inserted, 3 not inserted. + EXPECT_EQ(5, m.size()); + EXPECT_EQ(14, m.at(4)); + EXPECT_EQ(15, m.at(5)); +} + +static std::pair<const int, int> Pair(int i, int j) { return {i, j}; } + +// Test front accessors. +TEST(LinkedHashMapTest, Front) { + linked_hash_map<int, int> m; + + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(3, 13)); + + EXPECT_EQ(3, m.size()); + EXPECT_EQ(Pair(2, 12), m.front()); + m.pop_front(); + EXPECT_EQ(2, m.size()); + EXPECT_EQ(Pair(1, 11), m.front()); + m.pop_front(); + EXPECT_EQ(1, m.size()); + EXPECT_EQ(Pair(3, 13), m.front()); + m.pop_front(); + EXPECT_TRUE(m.empty()); +} + +// Test back accessors. +TEST(LinkedHashMapTest, Back) { + linked_hash_map<int, int> m; + + m.insert(std::make_pair(2, 12)); + m.insert(std::make_pair(1, 11)); + m.insert(std::make_pair(3, 13)); + + EXPECT_EQ(3, m.size()); + EXPECT_EQ(Pair(3, 13), m.back()); + m.pop_back(); + EXPECT_EQ(2, m.size()); + EXPECT_EQ(Pair(1, 11), m.back()); + m.pop_back(); + EXPECT_EQ(1, m.size()); + EXPECT_EQ(Pair(2, 12), m.back()); + m.pop_back(); + EXPECT_TRUE(m.empty()); +} + +TEST(LinkedHashMapTest, Find) { + linked_hash_map<int, int> m; + + EXPECT_TRUE(m.end() == m.find(1)) + << "We shouldn't find anything in an empty map."; + + m.insert(std::make_pair(2, 12)); + EXPECT_TRUE(m.end() == m.find(1)) + << "We shouldn't find an element that doesn't exist in the map."; + + std::pair<linked_hash_map<int, int>::iterator, bool> result = + m.insert(std::make_pair(1, 11)); + ASSERT_TRUE(result.second); + ASSERT_TRUE(m.end() != result.first); + EXPECT_TRUE(result.first == m.find(1)) + << "We should have found an element we know exists in the map."; + EXPECT_EQ(11, result.first->second); + + // Check that a follow-up insertion doesn't affect our original + m.insert(std::make_pair(3, 13)); + linked_hash_map<int, int>::iterator it = m.find(1); + ASSERT_TRUE(m.end() != it); + EXPECT_EQ(11, it->second); + + m.clear(); + EXPECT_TRUE(m.end() == m.find(1)) + << "We shouldn't find anything in a map that we've cleared."; +} + +TEST(LinkedHashMapTest, Contains) { + linked_hash_map<int, int> m; + + EXPECT_FALSE(m.contains(1)) << "An empty map shouldn't contain anything."; + + m.insert(std::make_pair(2, 12)); + EXPECT_FALSE(m.contains(1)) + << "The map shouldn't contain an element that doesn't exist."; + + m.insert(std::make_pair(1, 11)); + EXPECT_TRUE(m.contains(1)) + << "The map should contain an element that we know exists."; + + m.clear(); + EXPECT_FALSE(m.contains(1)) + << "A map that we've cleared shouldn't contain anything."; +} + +TEST(LinkedHashMapTest, At) { + linked_hash_map<int, int> m = {{1, 2}}; + EXPECT_EQ(2, m.at(1)); + ABSL_BASE_INTERNAL_EXPECT_FAIL(m.at(3), std::out_of_range, + "linked_hash_map::at"); + + const linked_hash_map<int, int> cm = {{1, 2}}; + EXPECT_EQ(2, cm.at(1)); + ABSL_BASE_INTERNAL_EXPECT_FAIL(cm.at(3), std::out_of_range, + "linked_hash_map::at"); +} + +TEST(LinkedHashMapTest, Swap) { + linked_hash_map<int, int> m1; + linked_hash_map<int, int> m2; + m1.insert(std::make_pair(1, 1)); + m1.insert(std::make_pair(2, 2)); + m2.insert(std::make_pair(3, 3)); + ASSERT_EQ(2, m1.size()); + ASSERT_EQ(1, m2.size()); + m1.swap(m2); + ASSERT_EQ(1, m1.size()); + ASSERT_EQ(2, m2.size()); +} + +TEST(LinkedHashMapTest, InitializerList) { + linked_hash_map<int, int> m{{1, 2}, {3, 4}}; + ASSERT_EQ(2, m.size()); + EXPECT_TRUE(m.contains(1)); + linked_hash_map<int, int>::iterator it = m.find(1); + ASSERT_TRUE(m.end() != it); + EXPECT_EQ(2, it->second); + EXPECT_TRUE(m.contains(3)); + it = m.find(3); + ASSERT_TRUE(m.end() != it); + EXPECT_EQ(4, it->second); +} + +TEST(LinkedHashMapTest, CustomHashAndEquality) { + struct CustomIntHash { + size_t operator()(int x) const { return x; } + }; + struct CustomIntEq { + bool operator()(int x, int y) const { return x == y; } + }; + linked_hash_map<int, int, CustomIntHash, CustomIntEq> m; + m.insert(std::make_pair(1, 1)); + EXPECT_TRUE(m.contains(1)); + EXPECT_EQ(1, m[1]); +} + +TEST(LinkedHashMapTest, EqualRange) { + linked_hash_map<int, int> m{{3, 11}, {1, 13}}; + const auto& const_m = m; + + EXPECT_THAT(m.equal_range(2), testing::Pair(m.end(), m.end())); + EXPECT_THAT(const_m.equal_range(2), + testing::Pair(const_m.end(), const_m.end())); + + EXPECT_THAT(m.equal_range(1), testing::Pair(m.find(1), ++m.find(1))); + EXPECT_THAT(const_m.equal_range(1), + testing::Pair(const_m.find(1), ++const_m.find(1))); +} + +TEST(LinkedHashMapTest, ReserveWorks) { + linked_hash_map<int, int> m; + EXPECT_EQ(0, m.size()); + EXPECT_EQ(0.0, m.load_factor()); + m.reserve(10); + EXPECT_LE(10, m.capacity()); + EXPECT_EQ(0, m.size()); + EXPECT_EQ(0.0, m.load_factor()); + m.emplace(1, 1); + m.emplace(2, 2); + EXPECT_LE(10, m.capacity()); + EXPECT_EQ(2, m.size()); + EXPECT_LT(0.0, m.load_factor()); +} + +// We require key types to have hash and equals. +class CopyableMovableType + : public absl::test_internal::CopyableMovableInstance { + public: + using CopyableMovableInstance::CopyableMovableInstance; + + bool operator==(const CopyableMovableType& o) const { + return value() == o.value(); + } + + template <typename H> + friend H AbslHashValue(H h, const CopyableMovableType& c) { + return H::combine(std::move(h), c.value()); + } +}; + +TEST(LinkedHashMapTest, RValueOperatorAt) { + absl::test_internal::InstanceTracker tracker; + + linked_hash_map<CopyableMovableType, int> map; + map[CopyableMovableType(1)] = 1; + EXPECT_EQ(tracker.copies(), 0); + CopyableMovableType c(2); + map[std::move(c)] = 2; + EXPECT_EQ(tracker.copies(), 0); + EXPECT_THAT(map, ElementsAre(Pair(CopyableMovableType(1), 1), + Pair(CopyableMovableType(2), 2))); +} + +TEST(LinkedHashMapTest, HeterogeneousTests) { + absl::test_internal::InstanceTracker tracker; + + using MapType = linked_hash_map<ExpensiveType, int, HeterogeneousHash, + HeterogeneousEqual>; + MapType map; + ExpensiveType one(1); + map[one] = 1; + // Two instances: 'one' var and an instance in the map. + EXPECT_EQ(2, tracker.instances()); + EXPECT_EQ(1, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + map[one] = 5; + // No construction since key==1 exists. + EXPECT_EQ(2, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + map[CheapType(1)] = 10; + // No construction since key==1 exists. + EXPECT_EQ(2, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + map[CheapType(2)] = 20; + // Construction since key==2 doesn't exist in the map. + EXPECT_EQ(3, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(map, ElementsAre(Pair(HasExpensiveValue(1), 10), + Pair(HasExpensiveValue(2), 20))); + + // find + auto itr = map.find(CheapType(1)); + tracker.ResetCopiesMovesSwaps(); + ASSERT_NE(itr, map.end()); + EXPECT_EQ(10, itr->second); + // contains + EXPECT_TRUE(map.contains(CheapType(2))); + // count + EXPECT_EQ(1, map.count(CheapType(2))); + // equal_range + auto eq_itr_pair = map.equal_range(CheapType(2)); + ASSERT_NE(eq_itr_pair.first, map.end()); + EXPECT_EQ(20, eq_itr_pair.first->second); + // No construction for find, contains, count or equal_range. + EXPECT_EQ(3, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + // insert + auto three = MapType::value_type(CheapType(3), 30); + tracker.ResetCopiesMovesSwaps(); + map.insert(three); + // Two instances: 'three' var and an instance in the map. + EXPECT_EQ(5, tracker.instances()); + EXPECT_EQ(1, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + map.insert(three); + // No additional construction since key==3 exists. + EXPECT_EQ(5, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(map, ElementsAre(Pair(HasExpensiveValue(1), 10), + Pair(HasExpensiveValue(2), 20), + Pair(HasExpensiveValue(3), 30))); + + // Test std::move() using operator[] and insert(). + ExpensiveType four(4); + tracker.ResetCopiesMovesSwaps(); + map[std::move(four)] = 40; + // Two constructions (regular and move). + EXPECT_EQ(7, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(1, tracker.moves()); + + auto five = MapType::value_type(CheapType(5), 50); + tracker.ResetCopiesMovesSwaps(); + map.insert(std::move(five)); + // Two constructions (regular and move). + EXPECT_EQ(9, tracker.instances()); + EXPECT_EQ(1, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(map, ElementsAre(Pair(HasExpensiveValue(1), 10), + Pair(HasExpensiveValue(2), 20), + Pair(HasExpensiveValue(3), 30), + Pair(HasExpensiveValue(4), 40), + Pair(HasExpensiveValue(5), 50))); + + // Insert using std::pair. + tracker.ResetCopiesMovesSwaps(); + map.insert(std::make_pair(ExpensiveType(6), 60)); + EXPECT_EQ(10, tracker.instances()); + EXPECT_EQ(1, tracker.copies()); + EXPECT_EQ(2, tracker.moves()); + + // Heterogeneous erase. + map.erase(CheapType(1)); + // No construction and instance reduced by one. + tracker.ResetCopiesMovesSwaps(); + EXPECT_EQ(9, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(map, ElementsAre(Pair(HasExpensiveValue(2), 20), + Pair(HasExpensiveValue(3), 30), + Pair(HasExpensiveValue(4), 40), + Pair(HasExpensiveValue(5), 50), + Pair(HasExpensiveValue(6), 60))); +} + +TEST(LinkedHashMapTest, HeterogeneousStringViewLookup) { + linked_hash_map<std::string, int> map; + map["foo"] = 1; + map["bar"] = 2; + map["blah"] = 3; + + { + absl::string_view lookup("foo"); + auto itr = map.find(lookup); + ASSERT_NE(itr, map.end()); + EXPECT_EQ(1, itr->second); + } + + // Not found. + { + absl::string_view lookup("foobar"); + EXPECT_EQ(map.end(), map.find(lookup)); + } + + { + absl::string_view lookup("blah"); + auto itr = map.find(lookup); + ASSERT_NE(itr, map.end()); + EXPECT_EQ(3, itr->second); + } +} + +TEST(LinkedHashMapTest, UniversalReferenceWorks) { + linked_hash_map<std::string, int> map; + std::string s = "very very very very very long string"; + map[s] = 1; + EXPECT_EQ(s, "very very very very very long string"); +} + +TEST(LinkedHashMap, ExtractInsert) { + linked_hash_map<int, int> m = {{1, 7}, {2, 9}}; + auto node = m.extract(1); + EXPECT_TRUE(node); + EXPECT_EQ(node.key(), 1); + EXPECT_EQ(node.mapped(), 7); + EXPECT_THAT(m, ElementsAre(Pair(2, 9))); + EXPECT_FALSE(m.contains(1)); + EXPECT_TRUE(m.contains(2)); + + node.mapped() = 17; + m.insert(std::move(node)); + EXPECT_FALSE(node); + EXPECT_THAT(m, ElementsAre(Pair(2, 9), Pair(1, 17))); + EXPECT_TRUE(m.contains(2)); + EXPECT_TRUE(m.contains(1)); + + node = m.extract(m.find(1)); + EXPECT_TRUE(node); + EXPECT_EQ(node.key(), 1); + EXPECT_EQ(node.mapped(), 17); + EXPECT_THAT(m, ElementsAre(Pair(2, 9))); +} + +TEST(LinkedHashMap, Merge) { + linked_hash_map<int, int> m = {{1, 7}, {3, 6}}; + linked_hash_map<int, int> src = {{1, 10}, {2, 9}, {4, 16}}; + + m.merge(src); + + EXPECT_THAT(m, ElementsAre(Pair(1, 7), Pair(3, 6), Pair(2, 9), Pair(4, 16))); + EXPECT_THAT(src, ElementsAre(Pair(1, 10))); + for (int i : {2, 9, 4}) { + EXPECT_FALSE(src.contains(i)); + } +} + +TEST(LinkedHashMap, Splice) { + linked_hash_map<int, int> m = {{1, 7}, {3, 6}}; + linked_hash_map<int, int> src = {{1, 10}, {2, 9}, {4, 16}}; + m.splice(m.end(), m, m.begin()); + + EXPECT_THAT(m, ElementsAre(Pair(3, 6), Pair(1, 7))); + + m.splice(m.end(), src, ++src.begin()); + EXPECT_THAT(m, ElementsAre(Pair(3, 6), Pair(1, 7), Pair(2, 9))); + EXPECT_THAT(src, ElementsAre(Pair(1, 10), Pair(4, 16))); +} + +TEST(LinkedHashMap, EraseRange) { + linked_hash_map<int, int> map = {{1, 1}, {2, 4}, {3, 9}, {4, 16}, {5, 25}, + {6, 36}, {7, 49}, {8, 64}, {9, 81}}; + auto start = map.find(3); + auto end = map.find(8); + auto itr = map.erase(start, end); + ASSERT_NE(itr, map.end()); + EXPECT_THAT(*itr, Pair(8, 64)); + EXPECT_THAT(map, + ElementsAre(Pair(1, 1), Pair(2, 4), Pair(8, 64), Pair(9, 81))); + for (int i : {1, 2, 8, 9}) { + EXPECT_TRUE(map.contains(i)); + } + for (int i : {3, 4, 5, 6, 7}) { + EXPECT_FALSE(map.contains(i)); + } +} + +TEST(LinkedHashMap, InsertInitializerList) { + linked_hash_map<int, int> m; + m.insert({{1, 7}, {2, 9}, {3, 29}}); + EXPECT_THAT(m, ElementsAre(Pair(1, 7), Pair(2, 9), Pair(3, 29))); +} + +TEST(LinkedHashMap, InsertOrAssign) { + linked_hash_map<int, int> m; + { + auto [itr, elem_inserted] = m.insert_or_assign(10, 20); + EXPECT_THAT(*itr, Pair(10, 20)); + EXPECT_EQ(elem_inserted, true); + } + { + auto [itr, elem_inserted] = m.insert_or_assign(10, 30); + EXPECT_THAT(*itr, Pair(10, 30)); + EXPECT_EQ(elem_inserted, false); + } +} + +TEST(LinkedHashMap, TryEmplace) { + linked_hash_map<int, std::pair<int, std::string>> m; + { + auto [itr, elem_inserted] = m.try_emplace(10, 20, "string"); + EXPECT_THAT(*itr, Pair(10, Pair(20, "string"))); + EXPECT_EQ(elem_inserted, true); + } + { + absl::test_internal::InstanceTracker tracker; + std::string s = "some string"; + auto [itr, elem_inserted] = m.try_emplace(10, 2, std::move(s)); + EXPECT_THAT(*itr, Pair(10, Pair(20, "string"))); + EXPECT_EQ(elem_inserted, false); + EXPECT_THAT(tracker.moves(), 0); + } +} + +TEST(LinkedHashMapTest, TryEmplace) { + linked_hash_map<int, std::tuple<int, std::string, std::unique_ptr<float>>> + map; + auto result = map.try_emplace(3, 2, "foo", new float(1.0)); + EXPECT_TRUE(result.second); + EXPECT_EQ(std::get<0>(result.first->second), 2); + EXPECT_EQ(std::get<1>(result.first->second), "foo"); + EXPECT_EQ(*std::get<2>(result.first->second), 1.0); + + // Ptr should not be moved. + auto ptr = std::make_unique<float>(3.0); + auto result2 = map.try_emplace(3, 22, "foo-bar", std::move(ptr)); + EXPECT_FALSE(result2.second); + EXPECT_EQ(std::get<0>(result.first->second), 2); + EXPECT_EQ(std::get<1>(result.first->second), "foo"); + EXPECT_EQ(*std::get<2>(result.first->second), 1.0); + EXPECT_NE(ptr.get(), nullptr); +} + +struct CountedHash { + explicit CountedHash(int* count) : count(count) {} + size_t operator()(int value) const { + ++(*count); + return value; + } + int* count = nullptr; +}; + +// Makes a map too big for small object optimization. Counts the number of +// hashes in `count`, but leaves `count` set to 0. +linked_hash_map<int, std::string, CountedHash> MakeNonSmallMap(int* count) { + const int kFirstKey = -1000; + linked_hash_map<int, std::string, CountedHash> m(0, CountedHash(count)); + for (int i = kFirstKey; i < kFirstKey + 100; ++i) { + m[i] = "foo"; + } + *count = 0; + return m; +} + +constexpr bool BuildHasDebugModeRehashes() { +#if !defined(NDEBUG) || defined(ABSL_HAVE_ADDRESS_SANITIZER) || \ + defined(ABSL_HAVE_MEMORY_SANITIZER) || defined(ABSL_HAVE_THREAD_SANITIZER) + return true; +#else + return false; +#endif +} + +TEST(LinkedHashMapTest, HashCountInOptBuilds) { + if (BuildHasDebugModeRehashes()) { + GTEST_SKIP() << "Only run under NDEBUG: `assert` statements and sanitizer " + "rehashing may cause redundant hashing."; + } + + using Map = linked_hash_map<int, std::string, CountedHash>; + { + int count = 0; + Map m = MakeNonSmallMap(&count); + m.insert({1, "foo"}); + EXPECT_EQ(count, 1); + m.erase(1); + EXPECT_EQ(count, 2); + } + { + int count = 0; + Map m = MakeNonSmallMap(&count); + m[2] = "bar"; + EXPECT_EQ(count, 1); + } + { + int count = 0; + Map m = MakeNonSmallMap(&count); + m.insert({3, "baz"}); + EXPECT_EQ(count, 1); + auto node = m.extract(3); + EXPECT_EQ(count, 2); + m.insert(std::move(node)); + EXPECT_EQ(count, 3); + } + { + int count = 0; + Map m = MakeNonSmallMap(&count); + m.insert_or_assign(4, "qux"); + EXPECT_EQ(count, 1); + } + { + int count = 0; + Map m = MakeNonSmallMap(&count); + m.emplace(5, "vog"); + EXPECT_EQ(count, 1); + } + { + int count = 0; + Map m = MakeNonSmallMap(&count); + m.try_emplace(6, 'x', 42); + EXPECT_EQ(count, 1); + } + { + int src_count = 0, dst_count = 0; + Map src = MakeNonSmallMap(&src_count); + Map dst = MakeNonSmallMap(&dst_count); + src[7] = "siete"; + dst.merge(src); + EXPECT_LE(src_count, 200); + EXPECT_LE(dst_count, 200); + } +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/container/linked_hash_set.h b/absl/container/linked_hash_set.h new file mode 100644 index 0000000..f874cd1 --- /dev/null +++ b/absl/container/linked_hash_set.h
@@ -0,0 +1,524 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// File: linked_hash_set.h +// ----------------------------------------------------------------------------- +// +// This is a simple insertion-ordered set. It provides O(1) amortized +// insertions and lookups, as well as iteration over the set in the insertion +// order. +// +// This class is thread-compatible. +// +// Iterators point into the list and should be stable in the face of +// mutations, except for an iterator pointing to an element that was just +// deleted. +// +// This class supports heterogeneous lookups. + +#ifndef ABSL_CONTAINER_LINKED_HASH_SET_H_ +#define ABSL_CONTAINER_LINKED_HASH_SET_H_ + +#include <cassert> +#include <cstddef> +#include <initializer_list> +#include <list> +#include <memory> +#include <type_traits> +#include <utility> + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/container/flat_hash_set.h" +#include "absl/container/internal/common.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN + +template < + typename Key, typename KeyHash = typename absl::flat_hash_set<Key>::hasher, + typename KeyEq = typename absl::flat_hash_set<Key, KeyHash>::key_equal, + typename Alloc = std::allocator<Key>> +class linked_hash_set { + using KeyArgImpl = absl::container_internal::KeyArg< + absl::container_internal::IsTransparent<KeyEq>::value && + absl::container_internal::IsTransparent<KeyHash>::value>; + + public: + using key_type = Key; + using hasher = KeyHash; + using key_equal = KeyEq; + using value_type = key_type; + using allocator_type = Alloc; + using difference_type = ptrdiff_t; + + private: + template <class K> + using key_arg = typename KeyArgImpl::template type<K, key_type>; + + using ListType = std::list<key_type, Alloc>; + + template <class Fn> + class Wrapped { + template <typename K> + static const K& ToKey(const K& k) { + return k; + } + static const key_type& ToKey(typename ListType::const_iterator it) { + return *it; + } + static const key_type& ToKey(typename ListType::iterator it) { return *it; } + + Fn fn_; + + friend linked_hash_set; + + public: + using is_transparent = void; + + Wrapped() = default; + explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} + + template <class... Args> + auto operator()(Args&&... args) const + -> decltype(this->fn_(ToKey(args)...)) { + return fn_(ToKey(args)...); + } + }; + using SetType = + absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, + Wrapped<key_equal>, Alloc>; + + class NodeHandle { + public: + using allocator_type = linked_hash_set::allocator_type; + using value_type = linked_hash_set::value_type; + + constexpr NodeHandle() noexcept = default; + NodeHandle(NodeHandle&& nh) noexcept = default; + ~NodeHandle() = default; + NodeHandle& operator=(NodeHandle&& node) noexcept = default; + bool empty() const noexcept { return list_.empty(); } + explicit operator bool() const noexcept { return !empty(); } + allocator_type get_allocator() const { return list_.get_allocator(); } + value_type& value() { return list_.front(); } + void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } + + private: + friend linked_hash_set; + + explicit NodeHandle(ListType list) : list_(std::move(list)) {} + ListType list_; + }; + + template <class Iterator, class NodeType> + struct InsertReturnType { + Iterator position; + bool inserted; + NodeType node; + }; + + public: + using iterator = typename ListType::const_iterator; + using const_iterator = typename ListType::const_iterator; + using reverse_iterator = typename ListType::const_reverse_iterator; + using const_reverse_iterator = typename ListType::const_reverse_iterator; + using reference = typename ListType::reference; + using const_reference = typename ListType::const_reference; + using pointer = typename std::allocator_traits<allocator_type>::pointer; + using const_pointer = + typename std::allocator_traits<allocator_type>::const_pointer; + using size_type = typename ListType::size_type; + using node_type = NodeHandle; + using insert_return_type = InsertReturnType<iterator, node_type>; + + linked_hash_set() {} + + explicit linked_hash_set(size_t bucket_count, const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : set_(bucket_count, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), + alloc), + list_(alloc) {} + + linked_hash_set(size_t bucket_count, const hasher& hash, + const allocator_type& alloc) + : linked_hash_set(bucket_count, hash, key_equal(), alloc) {} + + linked_hash_set(size_t bucket_count, const allocator_type& alloc) + : linked_hash_set(bucket_count, hasher(), key_equal(), alloc) {} + + explicit linked_hash_set(const allocator_type& alloc) + : linked_hash_set(0, hasher(), key_equal(), alloc) {} + + template <class InputIt> + linked_hash_set(InputIt first, InputIt last, size_t bucket_count = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : linked_hash_set(bucket_count, hash, eq, alloc) { + insert(first, last); + } + + template <class InputIter> + linked_hash_set(InputIter first, InputIter last, size_t bucket_count, + const hasher& hash, const allocator_type& alloc) + : linked_hash_set(first, last, bucket_count, hash, key_equal(), alloc) {} + + template <class InputIter> + linked_hash_set(InputIter first, InputIter last, size_t bucket_count, + const allocator_type& alloc) + : linked_hash_set(first, last, bucket_count, hasher(), key_equal(), + alloc) {} + + template <class InputIt> + linked_hash_set(InputIt first, InputIt last, const allocator_type& alloc) + : linked_hash_set(first, last, /*bucket_count=*/0, hasher(), key_equal(), + alloc) {} + + linked_hash_set(std::initializer_list<key_type> init, size_t bucket_count = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : linked_hash_set(init.begin(), init.end(), bucket_count, hash, eq, + alloc) {} + + linked_hash_set(std::initializer_list<key_type> init, size_t bucket_count, + const allocator_type& alloc) + : linked_hash_set(init, bucket_count, hasher(), key_equal(), alloc) {} + + linked_hash_set(std::initializer_list<key_type> init, size_t bucket_count, + const hasher& hash, const allocator_type& alloc) + : linked_hash_set(init, bucket_count, hash, key_equal(), alloc) {} + + linked_hash_set(std::initializer_list<key_type> init, + const allocator_type& alloc) + : linked_hash_set(init, /*bucket_count=*/0, hasher(), key_equal(), + alloc) {} + + linked_hash_set(const linked_hash_set& other) + : linked_hash_set(other.bucket_count(), other.hash_function(), + other.key_eq(), other.get_allocator()) { + CopyFrom(other); + } + + linked_hash_set(const linked_hash_set& other, const allocator_type& alloc) + : linked_hash_set(other.bucket_count(), other.hash_function(), + other.key_eq(), alloc) { + CopyFrom(other); + } + + linked_hash_set(linked_hash_set&& other) noexcept + : set_(std::move(other.set_)), list_(std::move(other.list_)) { + // Since the list and set must agree for other to end up "valid", + // explicitly clear them. + other.set_.clear(); + other.list_.clear(); + } + + linked_hash_set(linked_hash_set&& other, const allocator_type& alloc) + : linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { + if (get_allocator() == other.get_allocator()) { + *this = std::move(other); + } else { + CopyFrom(std::move(other)); + } + } + + linked_hash_set& operator=(const linked_hash_set& other) { + if (this == &other) return *this; + // Make a new set, with other's hash/eq/alloc. + set_ = SetType(other.bucket_count(), other.set_.hash_function(), + other.set_.key_eq(), other.get_allocator()); + // Copy the list, with other's allocator. + list_ = ListType(other.get_allocator()); + CopyFrom(other); + return *this; + } + + linked_hash_set& operator=(linked_hash_set&& other) noexcept { + set_ = std::move(other.set_); + list_ = std::move(other.list_); + other.set_.clear(); + other.list_.clear(); + return *this; + } + + linked_hash_set& operator=(std::initializer_list<key_type> values) { + clear(); + insert(values.begin(), values.end()); + return *this; + } + + // Derive size from set_, as list::size might be O(N). + size_type size() const { return set_.size(); } + size_type max_size() const noexcept { return ~size_type{}; } + bool empty() const { return set_.empty(); } + + // Iteration is list-like, in insertion order. + // These are all forwarded. + iterator begin() { return list_.begin(); } + iterator end() { return list_.end(); } + const_iterator begin() const { return list_.begin(); } + const_iterator end() const { return list_.end(); } + const_iterator cbegin() const { return list_.cbegin(); } + const_iterator cend() const { return list_.cend(); } + reverse_iterator rbegin() { return list_.rbegin(); } + reverse_iterator rend() { return list_.rend(); } + const_reverse_iterator rbegin() const { return list_.rbegin(); } + const_reverse_iterator rend() const { return list_.rend(); } + const_reverse_iterator crbegin() const { return list_.crbegin(); } + const_reverse_iterator crend() const { return list_.crend(); } + reference front() { return list_.front(); } + reference back() { return list_.back(); } + const_reference front() const { return list_.front(); } + const_reference back() const { return list_.back(); } + + void pop_front() { erase(begin()); } + void pop_back() { erase(std::prev(end())); } + + ABSL_ATTRIBUTE_REINITIALIZES void clear() { + set_.clear(); + list_.clear(); + } + + void reserve(size_t n) { set_.reserve(n); } + size_t bucket_count() const { return set_.bucket_count(); } + size_t capacity() const { return set_.capacity(); } + float load_factor() const { return set_.load_factor(); } + + hasher hash_function() const { return set_.hash_function().fn_; } + key_equal key_eq() const { return set_.key_eq().fn_; } + allocator_type get_allocator() const { return list_.get_allocator(); } + + template <typename K = key_type> + size_type erase(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return 0; + auto list_it = *found; + // Erase set entry first since it refers to the list element. + set_.erase(found); + list_.erase(list_it); + return 1; + } + + iterator erase(const_iterator position) { + auto found = set_.find(position); + assert(*found == position); + set_.erase(found); + return list_.erase(position); + } + + iterator erase(const_iterator first, const_iterator last) { + while (first != last) first = erase(first); + return first; + } + + template <typename K = key_type> + iterator find(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return *found; + } + + template <typename K = key_type> + const_iterator find(const key_arg<K>& key) const { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return *found; + } + + template <typename K = key_type> + size_t count(const key_arg<K>& key) const { + return contains(key) ? 1 : 0; + } + template <typename K = key_type> + bool contains(const key_arg<K>& key) const { + return set_.contains(key); + } + + template <typename K = key_type> + std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { + auto iter = set_.find(key); + if (iter == set_.end()) return {end(), end()}; + return {*iter, std::next(*iter)}; + } + + template <typename K = key_type> + std::pair<const_iterator, const_iterator> equal_range( + const key_arg<K>& key) const { + auto iter = set_.find(key); + if (iter == set_.end()) return {end(), end()}; + return {*iter, std::next(*iter)}; + } + + template <typename K = key_type> + std::pair<iterator, bool> insert(const key_arg<K>& k) { + return InsertInternal(list_.end(), k); + } + template <typename K = key_type, K* = nullptr> + std::pair<iterator, bool> insert(key_arg<K>&& k) { + return InsertInternal(list_.end(), std::move(k)); + } + + template <typename K = key_type, + std::enable_if_t< + !std::is_convertible_v<const key_arg<K>&, const_iterator> && + !std::is_convertible_v<const key_arg<K>&, iterator>, + int> = 0> + iterator insert(const_iterator hint, const key_arg<K>& k) { + return InsertInternal(hint, k).first; + } + template < + typename K = key_type, K* = nullptr, + std::enable_if_t<!std::is_convertible_v<key_arg<K>&&, const_iterator> && + !std::is_convertible_v<key_arg<K>&&, iterator>, + int> = 0> + iterator insert(const_iterator hint, key_arg<K>&& k) { + return InsertInternal(hint, std::move(k)).first; + } + + void insert(std::initializer_list<key_type> ilist) { + insert(ilist.begin(), ilist.end()); + } + + template <class InputIt> + void insert(InputIt first, InputIt last) { + for (; first != last; ++first) insert(*first); + } + + insert_return_type insert(node_type&& node) { + if (node.empty()) return {end(), false, node_type()}; + if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { + list_.splice(list_.end(), node.list_); + return {*set_itr, true, node_type()}; + } else { + return {*set_itr, false, std::move(node)}; + } + } + + iterator insert(const_iterator, node_type&& node) { + return insert(std::move(node)).first; + } + + template <typename... Args> + std::pair<iterator, bool> emplace(Args&&... args) { + return EmplaceInternal(list_.end(), std::forward<Args>(args)...); + } + + template <typename... Args> + iterator emplace_hint(const_iterator hint, Args&&... args) { + return EmplaceInternal(hint, std::forward<Args>(args)...).first; + } + + template <typename H, typename E> + void merge(linked_hash_set<Key, H, E, Alloc>& src) { + auto itr = src.list_.begin(); + while (itr != src.list_.end()) { + if (contains(*itr)) { + ++itr; + } else { + insert(src.extract(itr++)); + } + } + } + + template <typename H, typename E> + void merge(linked_hash_set<Key, H, E, Alloc>&& src) { + merge(src); + } + + node_type extract(const_iterator position) { + set_.erase(position); + ListType extracted_node_list; + extracted_node_list.splice(extracted_node_list.end(), list_, position); + return node_type(std::move(extracted_node_list)); + } + + template <class K = key_type, typename std::enable_if_t< + !std::is_same<K, iterator>::value, int> = 0> + node_type extract(const key_arg<K>& key) { + auto node = set_.extract(key); + if (node.empty()) return node_type(); + ListType extracted_node_list; + extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); + return node_type(std::move(extracted_node_list)); + } + + void swap(linked_hash_set& other) noexcept { + using std::swap; + swap(set_, other.set_); + swap(list_, other.list_); + } + + friend bool operator==(const linked_hash_set& a, const linked_hash_set& b) { + if (a.size() != b.size()) return false; + const linked_hash_set* outer = &a; + const linked_hash_set* inner = &b; + if (outer->capacity() > inner->capacity()) std::swap(outer, inner); + for (const value_type& elem : *outer) + if (!inner->contains(elem)) return false; + return true; + } + + friend bool operator!=(const linked_hash_set& a, const linked_hash_set& b) { + return !(a == b); + } + + void rehash(size_t n) { set_.rehash(n); } + + private: + template <typename Other> + void CopyFrom(Other&& other) { + for (auto& elem : other.list_) { + set_.insert(list_.insert(list_.end(), std::move(elem))); + } + assert(set_.size() == list_.size()); + } + + template <typename... Args> + std::pair<iterator, bool> EmplaceInternal(const_iterator hint, + Args&&... args) { + ListType node_donor; + auto list_iter = + node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); + auto ins = set_.insert(list_iter); + if (!ins.second) return {*ins.first, false}; + list_.splice(hint, node_donor, list_iter); + return {list_iter, true}; + } + + template <typename U> + std::pair<iterator, bool> InsertInternal(const_iterator hint, + U&& key) { // NOLINT(build/c++11) + bool constructed = false; + auto set_iter = set_.lazy_emplace(key, [&](const auto& ctor) { + constructed = true; + ctor(list_.emplace(hint, std::forward<U>(key))); + }); + return {*set_iter, constructed}; + } + + // The set component, used for speedy lookups. + SetType set_; + + // The list component, used for maintaining insertion order. + ListType list_; +}; + +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_LINKED_HASH_SET_H_
diff --git a/absl/container/linked_hash_set_benchmark.cc b/absl/container/linked_hash_set_benchmark.cc new file mode 100644 index 0000000..e790e7d --- /dev/null +++ b/absl/container/linked_hash_set_benchmark.cc
@@ -0,0 +1,84 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <algorithm> +#include <cstddef> +#include <string> +#include <vector> + +#include "absl/container/linked_hash_set.h" +#include "absl/functional/function_ref.h" +#include "absl/strings/str_format.h" +#include "absl/strings/string_view.h" +#include "benchmark/benchmark.h" + +namespace { + +void BenchmarkInsertStrings(benchmark::State& state, + absl::FunctionRef<std::string(int)> factory) { + std::vector<std::string> sample; + size_t str_bytes = 0; + for (int i = 0; i < state.range(0); ++i) { + sample.push_back(factory(i)); + str_bytes += sample.back().size(); + } + + // Make a batch around 1Mi bytes. + const size_t batch_size = std::max(size_t{1}, size_t{1000000} / str_bytes); + std::vector<absl::linked_hash_set<std::string>> sets(batch_size); + + while (state.KeepRunningBatch(batch_size)) { + state.PauseTiming(); + for (auto& set : sets) set.clear(); + state.ResumeTiming(); + for (auto& set : sets) { + for (const auto& str : sample) { + benchmark::DoNotOptimize(set.insert(str)); + } + } + } + + state.SetItemsProcessed(state.iterations() * state.range(0)); + state.SetBytesProcessed(state.iterations() * str_bytes); +} + +constexpr absl::string_view kFormatShort = "%10d"; +constexpr absl::string_view kFormatLong = + "a longer string that exceeds the SSO %10d"; + +void BM_InsertShortStrings_Hit(benchmark::State& state) { + BenchmarkInsertStrings( + state, [](int i) { return absl::StrFormat(kFormatShort, i); }); +} +BENCHMARK(BM_InsertShortStrings_Hit)->Range(1, 1 << 16); + +void BM_InsertLongStrings_Hit(benchmark::State& state) { + BenchmarkInsertStrings(state, + [](int i) { return absl::StrFormat(kFormatLong, i); }); +} +BENCHMARK(BM_InsertLongStrings_Hit)->Range(1, 1 << 16); + +void BM_InsertShortStrings_Miss(benchmark::State& state) { + BenchmarkInsertStrings( + state, [](int i) { return absl::StrFormat(kFormatShort, i % 20); }); +} +BENCHMARK(BM_InsertShortStrings_Miss)->Range(1, 1 << 16); + +void BM_InsertLongStrings_Miss(benchmark::State& state) { + BenchmarkInsertStrings( + state, [](int i) { return absl::StrFormat(kFormatLong, i % 20); }); +} +BENCHMARK(BM_InsertLongStrings_Miss)->Range(1, 1 << 16); + +} // namespace
diff --git a/absl/container/linked_hash_set_test.cc b/absl/container/linked_hash_set_test.cc new file mode 100644 index 0000000..b641b97 --- /dev/null +++ b/absl/container/linked_hash_set_test.cc
@@ -0,0 +1,917 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/container/linked_hash_set.h" + +#include <algorithm> +#include <cmath> +#include <cstddef> +#include <memory> +#include <string> +#include <utility> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/container/internal/hash_generator_testing.h" +#include "absl/container/internal/hash_policy_testing.h" +#include "absl/container/internal/heterogeneous_lookup_testing.h" +#include "absl/container/internal/test_instance_tracker.h" +#include "absl/container/internal/unordered_set_constructor_test.h" +#include "absl/container/internal/unordered_set_lookup_test.h" +#include "absl/container/internal/unordered_set_members_test.h" +#include "absl/container/internal/unordered_set_modifiers_test.h" +#include "absl/strings/string_view.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { +namespace { + +using ::testing::ElementsAre; +using ::testing::ElementsAreArray; +using ::testing::Pointee; + +template <class T> +using Set = + linked_hash_set<T, StatefulTestingHash, StatefulTestingEqual, Alloc<T>>; + +using SetTypes = + ::testing::Types<Set<int>, Set<std::string>, Set<Enum>, Set<EnumClass>>; + +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashSet, ConstructorTest, SetTypes); +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashSet, LookupTest, SetTypes); +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashSet, MembersTest, SetTypes); +INSTANTIATE_TYPED_TEST_SUITE_P(LinkedHashSet, ModifiersTest, SetTypes); + +// Tests that the range constructor works. +TEST(LinkedHashSetTest, RangeConstruct) { + const auto items = {1, 2, 3}; + EXPECT_THAT(linked_hash_set<int>(items.begin(), items.end()), + ElementsAre(1, 2, 3)); +} + +// Tests that copying works. +TEST(LinkedHashSetTest, Copy) { + linked_hash_set<int> m{4, 8, 15, 16, 23, 42}; + auto copy = m; + + auto found = copy.find(8); + ASSERT_TRUE(found != copy.end()); + for (auto iter = copy.begin(); iter != copy.end(); ++iter) { + if (iter == found) return; + } + FAIL() << "Copied set's find method returned an invalid iterator."; +} + +// Tests that assignment works. +TEST(LinkedHashSetTest, Assign) { + linked_hash_set<int> m{2, 3}; + linked_hash_set<int> n{4}; + + n = m; + EXPECT_TRUE(n.contains(2)); + auto found = n.find(2); + ASSERT_TRUE(found != n.end()); + for (auto iter = n.begin(); iter != n.end(); ++iter) { + if (iter == found) return; + } + FAIL() << "Assigned set's find method returned an invalid iterator."; +} + +// Tests that move constructor works. +TEST(LinkedHashSetTest, Move) { + // Use unique_ptr as an example of a non-copyable type. + linked_hash_set<std::unique_ptr<int>> m; + m.insert(std::make_unique<int>(2)); + m.insert(std::make_unique<int>(3)); + linked_hash_set<std::unique_ptr<int>> n = std::move(m); + EXPECT_THAT(n, ElementsAre(Pointee(2), Pointee(3))); +} + +struct IntUniquePtrHash { + size_t operator()(const std::unique_ptr<int>& p) const { + return static_cast<size_t>(*p); + } +}; + +struct IntUniquePtrEq { + size_t operator()(const std::unique_ptr<int>& a, + const std::unique_ptr<int>& b) const { + return *a == *b; + } +}; + +// Pretty artificial for a set, but unique_ptr is a convenient move-only type. +TEST(LinkedHashSetTest, CanInsertMoveOnly) { + linked_hash_set<std::unique_ptr<int>, IntUniquePtrHash, IntUniquePtrEq> s; + std::vector<int> data = {4, 8, 15, 16, 23, 42}; + for (int x : data) s.insert(std::make_unique<int>(x)); + EXPECT_EQ(s.size(), data.size()); + for (const std::unique_ptr<int>& elt : s) { + EXPECT_TRUE(s.contains(elt)); + EXPECT_TRUE(s.find(elt) != s.end()); + } +} + +TEST(LinkedHashSetTest, CanMoveMoveOnly) { + linked_hash_set<std::unique_ptr<int>, IntUniquePtrHash, IntUniquePtrEq> s; + std::vector<int> data = {4, 8, 15, 16, 23, 42}; + for (int x : data) s.insert(std::make_unique<int>(x)); + linked_hash_set<std::unique_ptr<int>, IntUniquePtrHash, IntUniquePtrEq> ss = + std::move(s); + EXPECT_EQ(ss.size(), data.size()); +} + +TEST(LinkedHashSetTest, CanEmplaceMoveOnly) { + linked_hash_set<std::unique_ptr<int>, IntUniquePtrHash, IntUniquePtrEq> s; + std::vector<int> data = {4, 8, 15, 16, 23, 42}; + for (const int x : data) { + s.emplace(new int{x}); + } + EXPECT_EQ(s.size(), data.size()); + for (const std::unique_ptr<int>& elt : s) { + EXPECT_TRUE(s.contains(elt)); + EXPECT_TRUE(s.find(elt) != s.end()); + } +} + +TEST(LinkedHashSetTest, CanInsertTransparent) { + linked_hash_set<std::string> s; + s.insert(absl::string_view("foo")); + s.insert(absl::string_view("bar")); + s.insert(absl::string_view("foo")); + EXPECT_THAT(s, ElementsAre("foo", "bar")); +} + +// Tests that iteration from begin() to end() works +TEST(LinkedHashSetTest, Iteration) { + linked_hash_set<int> m; + EXPECT_TRUE(m.begin() == m.end()); + + m.insert(2); + m.insert(1); + m.insert(3); + + linked_hash_set<int>::iterator i = m.begin(); + ASSERT_TRUE(m.begin() == i); + ASSERT_TRUE(m.end() != i); + EXPECT_EQ(2, *i); + + ++i; + ASSERT_TRUE(m.end() != i); + EXPECT_EQ(1, *i); + + ++i; + ASSERT_TRUE(m.end() != i); + EXPECT_EQ(3, *i); + + ++i; + ASSERT_TRUE(m.end() == i); +} + +// Tests that reverse iteration from rbegin() to rend() works +TEST(LinkedHashSetTest, ReverseIteration) { + linked_hash_set<int> m; + EXPECT_TRUE(m.rbegin() == m.rend()); + + m.insert(2); + m.insert(1); + m.insert(3); + + linked_hash_set<int>::reverse_iterator i = m.rbegin(); + ASSERT_TRUE(m.rbegin() == i); + ASSERT_TRUE(m.rend() != i); + EXPECT_EQ(3, *i); + + ++i; + ASSERT_TRUE(m.rend() != i); + EXPECT_EQ(1, *i); + + ++i; + ASSERT_TRUE(m.rend() != i); + EXPECT_EQ(2, *i); + + ++i; + ASSERT_TRUE(m.rend() == i); +} + +// Tests that clear() works +TEST(LinkedHashSetTest, Clear) { + linked_hash_set<int> m{2, 1, 3}; + ASSERT_EQ(3, m.size()); + + m.clear(); + EXPECT_EQ(0, m.size()); + EXPECT_FALSE(m.contains(1)); + EXPECT_TRUE(m.find(1) == m.end()); + + // Make sure we can call it on an empty set. + m.clear(); + EXPECT_EQ(0, m.size()); +} + +// Tests that size() works. +TEST(LinkedHashSetTest, Size) { + linked_hash_set<int> m; + EXPECT_EQ(0, m.size()); + m.insert(2); + EXPECT_EQ(1, m.size()); + m.insert(11); + EXPECT_EQ(2, m.size()); + m.insert(0); + EXPECT_EQ(3, m.size()); + m.insert(0); + EXPECT_EQ(3, m.size()); + m.clear(); + EXPECT_EQ(0, m.size()); +} + +// Tests empty() +TEST(LinkedHashSetTest, Empty) { + linked_hash_set<int> m; + ASSERT_TRUE(m.empty()); + m.insert(2); + ASSERT_FALSE(m.empty()); + m.clear(); + ASSERT_TRUE(m.empty()); +} + +TEST(LinkedHashSetTest, Erase) { + linked_hash_set<int> m; + ASSERT_EQ(0, m.size()); + EXPECT_EQ(0, m.erase(2)); // Nothing to erase yet + + m.insert(2); + ASSERT_EQ(1, m.size()); + EXPECT_EQ(1, m.erase(2)); + EXPECT_EQ(0, m.size()); + EXPECT_TRUE(m.empty()); + + EXPECT_EQ(0, m.erase(2)); // Make sure nothing bad happens if we repeat. + EXPECT_EQ(0, m.size()); + EXPECT_TRUE(m.empty()); +} + +TEST(LinkedHashSetTest, Erase2) { + linked_hash_set<int> m; + ASSERT_EQ(0, m.size()); + EXPECT_EQ(0, m.erase(2)); // Nothing to erase yet + + m.insert(2); + m.insert(1); + m.insert(3); + m.insert(4); + ASSERT_EQ(4, m.size()); + + // Erase middle two + EXPECT_EQ(1, m.erase(1)); + EXPECT_EQ(1, m.erase(3)); + + EXPECT_EQ(2, m.size()); + + // Make sure we can still iterate over everything that's left. + linked_hash_set<int>::iterator it = m.begin(); + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(2, *it); + ++it; + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(4, *it); + ++it; + ASSERT_TRUE(it == m.end()); + + EXPECT_EQ(0, m.erase(1)); // Make sure nothing bad happens if we repeat. + ASSERT_EQ(2, m.size()); + + EXPECT_EQ(1, m.erase(2)); + EXPECT_EQ(1, m.erase(4)); + ASSERT_EQ(0, m.size()); + EXPECT_TRUE(m.empty()); + + EXPECT_EQ(0, m.erase(1)); // Make sure nothing bad happens if we repeat. + ASSERT_EQ(0, m.size()); + EXPECT_TRUE(m.empty()); +} + +// Test that erase(iter,iter) and erase(iter) compile and work. +TEST(LinkedHashSetTest, Erase3) { + linked_hash_set<int> m; + + m.insert(1); + m.insert(2); + m.insert(3); + m.insert(4); + + // Erase middle two + linked_hash_set<int>::iterator it2 = m.find(2); + linked_hash_set<int>::iterator it4 = m.find(4); + EXPECT_EQ(m.erase(it2, it4), m.find(4)); + EXPECT_FALSE(m.contains(2)); + EXPECT_TRUE(m.find(2) == m.end()); + EXPECT_FALSE(m.contains(3)); + EXPECT_TRUE(m.find(3) == m.end()); + EXPECT_EQ(2, m.size()); + + // Make sure we can still iterate over everything that's left. + linked_hash_set<int>::iterator it = m.begin(); + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(1, *it); + ++it; + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(4, *it); + ++it; + ASSERT_TRUE(it == m.end()); + + // Erase first one using an iterator. + EXPECT_EQ(m.erase(m.begin()), m.find(4)); + EXPECT_FALSE(m.contains(1)); + EXPECT_TRUE(m.find(1) == m.end()); + + // Only the last element should be left. + EXPECT_TRUE(m.contains(4)); + it = m.begin(); + ASSERT_TRUE(it != m.end()); + EXPECT_EQ(4, *it); + ++it; + ASSERT_TRUE(it == m.end()); +} + +// Test all types of insertion +TEST(LinkedHashSetTest, Insertion) { + linked_hash_set<int> m; + ASSERT_EQ(0, m.size()); + std::pair<linked_hash_set<int>::iterator, bool> result; + + result = m.insert(2); + ASSERT_EQ(1, m.size()); + EXPECT_TRUE(result.second); + EXPECT_EQ(2, *result.first); + EXPECT_TRUE(m.contains(2)); + EXPECT_TRUE(m.find(2) != m.end()); + + result = m.insert(1); + ASSERT_EQ(2, m.size()); + EXPECT_TRUE(result.second); + EXPECT_EQ(1, *result.first); + EXPECT_TRUE(m.contains(1)); + EXPECT_TRUE(m.find(1) != m.end()); + + result = m.insert(3); + linked_hash_set<int>::iterator result_iterator = result.first; + ASSERT_EQ(3, m.size()); + EXPECT_TRUE(result.second); + EXPECT_EQ(3, *result.first); + EXPECT_TRUE(m.contains(3)); + EXPECT_TRUE(m.find(3) != m.end()); + + result = m.insert(3); + EXPECT_EQ(3, m.size()); + EXPECT_FALSE(result.second) << "No insertion should have occurred."; + EXPECT_TRUE(result_iterator == result.first) + << "Duplicate insertion should have given us the original iterator."; + EXPECT_TRUE(m.contains(3)); + EXPECT_TRUE(m.find(3) != m.end()); + + std::vector<int> v = {3, 4, 5}; + m.insert(v.begin(), v.end()); + // Expect 4 and 5 inserted, 3 not inserted. + EXPECT_EQ(5, m.size()); + EXPECT_TRUE(m.contains(4)); + EXPECT_NE(m.find(4), m.end()); + EXPECT_TRUE(m.contains(5)); + EXPECT_NE(m.find(5), m.end()); +} + +TEST(LinkedHashSetTest, HintedInsertionMoveable) { + linked_hash_set<int> m = {1, 3}; + m.insert(m.find(3), 2); + EXPECT_THAT(m, ElementsAre(1, 2, 3)); +} + +TEST(LinkedHashSetTest, HintedInsertionReference) { + linked_hash_set<int> m = {1, 3}; + const int val = 2; + m.insert(m.find(3), val); + EXPECT_THAT(m, ElementsAre(1, 2, 3)); +} + +TEST(LinkedHashSetTest, HintedEmplaceMoveable) { + linked_hash_set<int> m = {1, 3}; + m.emplace_hint(m.find(3), 2); + EXPECT_THAT(m, ElementsAre(1, 2, 3)); +} + +TEST(LinkedHashSetTest, HintedEmplaceReference) { + linked_hash_set<int> m = {1, 3}; + const int val = 2; + m.emplace_hint(m.find(3), val); + EXPECT_THAT(m, ElementsAre(1, 2, 3)); +} + +// Test front accessors. +TEST(LinkedHashSetTest, Front) { + linked_hash_set<int> m; + + m.insert(222); + m.insert(111); + m.insert(333); + + EXPECT_EQ(3, m.size()); + EXPECT_EQ(222, m.front()); + m.pop_front(); + EXPECT_EQ(2, m.size()); + EXPECT_EQ(111, m.front()); + m.pop_front(); + EXPECT_EQ(1, m.size()); + EXPECT_EQ(333, m.front()); + m.pop_front(); + EXPECT_TRUE(m.empty()); +} + +// Test back accessors. +TEST(LinkedHashSetTest, Back) { + linked_hash_set<int> m; + + m.insert(222); + m.insert(111); + m.insert(333); + + EXPECT_EQ(3, m.size()); + EXPECT_EQ(333, m.back()); + m.pop_back(); + EXPECT_EQ(2, m.size()); + EXPECT_EQ(111, m.back()); + m.pop_back(); + EXPECT_EQ(1, m.size()); + EXPECT_EQ(222, m.back()); + m.pop_back(); + EXPECT_TRUE(m.empty()); +} + +TEST(LinkedHashSetTest, Find) { + linked_hash_set<int> m; + + EXPECT_TRUE(m.end() == m.find(1)) + << "We shouldn't find anything in an empty set."; + + m.insert(2); + EXPECT_TRUE(m.end() == m.find(1)) + << "We shouldn't find an element that doesn't exist in the set."; + + std::pair<linked_hash_set<int>::iterator, bool> result = m.insert(1); + ASSERT_TRUE(result.second); + ASSERT_TRUE(m.end() != result.first); + EXPECT_TRUE(result.first == m.find(1)) + << "We should have found an element we know exists in the set."; + EXPECT_EQ(1, *result.first); + + // Check that a follow-up insertion doesn't affect our original + m.insert(3); + linked_hash_set<int>::iterator it = m.find(1); + ASSERT_TRUE(m.end() != it); + EXPECT_EQ(1, *it); + + m.clear(); + EXPECT_TRUE(m.end() == m.find(1)) + << "We shouldn't find anything in a set that we've cleared."; +} + +TEST(LinkedHashSetTest, Contains) { + linked_hash_set<int> m; + + EXPECT_FALSE(m.contains(1)) << "The empty set shouldn't contain anything."; + + m.insert(2); + EXPECT_FALSE(m.contains(1)) + << "contains() should not return true for an element that doesn't exist " + << "in the set."; + + m.insert(1); + EXPECT_TRUE(m.contains(1)) + << "contains() should return true for an element we know exists in the " + << "set."; + + m.clear(); + EXPECT_FALSE(m.contains(1)) + << "A set that we've cleared shouldn't contain anything."; +} + +TEST(LinkedHashSetTest, Swap) { + linked_hash_set<int> m1; + linked_hash_set<int> m2; + m1.insert(1); + m1.insert(2); + m2.insert(3); + ASSERT_EQ(2, m1.size()); + ASSERT_EQ(1, m2.size()); + m1.swap(m2); + ASSERT_EQ(1, m1.size()); + ASSERT_EQ(2, m2.size()); +} + +TEST(LinkedHashSetTest, InitializerList) { + linked_hash_set<int> m{1, 3}; + ASSERT_EQ(2, m.size()); + EXPECT_TRUE(m.contains(1)); + linked_hash_set<int>::iterator it = m.find(1); + ASSERT_TRUE(m.end() != it); + EXPECT_EQ(1, *it); + it = m.find(3); + EXPECT_TRUE(m.contains(3)); + ASSERT_TRUE(m.end() != it); + EXPECT_EQ(3, *it); +} + +TEST(LinkedHashSetTest, CustomHashAndEquality) { + struct CustomIntHash { + size_t operator()(int x) const { return 0; } + }; + struct CustomIntEq { + bool operator()(int x, int y) const { return abs(x) == abs(y); } + }; + linked_hash_set<int, CustomIntHash, CustomIntEq> m; + m.insert(1); + EXPECT_EQ(1, m.size()); + m.insert(2); + EXPECT_EQ(2, m.size()); + EXPECT_FALSE(m.insert(-2).second); + EXPECT_EQ(2, m.size()); + EXPECT_TRUE(m.contains(-1)); + EXPECT_TRUE(m.find(-1) != m.end()); +} + +TEST(LinkedHashSetTest, EqualRange) { + linked_hash_set<int> m{3, 1}; + const auto& const_m = m; + + EXPECT_THAT(m.equal_range(2), testing::Pair(m.end(), m.end())); + EXPECT_THAT(const_m.equal_range(2), + testing::Pair(const_m.end(), const_m.end())); + + EXPECT_THAT(m.equal_range(1), testing::Pair(m.find(1), ++m.find(1))); + EXPECT_THAT(const_m.equal_range(1), + testing::Pair(const_m.find(1), ++const_m.find(1))); +} + +TEST(LinkedHashSetTest, ReserveWorks) { + linked_hash_set<int> m; + EXPECT_EQ(0, m.size()); + EXPECT_EQ(0.0, m.load_factor()); + m.reserve(10); + EXPECT_LE(10, m.capacity()); + EXPECT_EQ(0, m.size()); + EXPECT_EQ(0.0, m.load_factor()); + m.insert(1); + m.insert(2); + EXPECT_LE(10, m.capacity()); + EXPECT_EQ(2, m.size()); + EXPECT_LT(0.0, m.load_factor()); +} + +TEST(LinkedHashSetTest, HeterogeneousTests) { + absl::test_internal::InstanceTracker tracker; + + linked_hash_set<ExpensiveType, HeterogeneousHash, HeterogeneousEqual> set; + ExpensiveType one(1); + tracker.ResetCopiesMovesSwaps(); + set.insert(one); + // Two instances: 'one' var and an instance in the set. + EXPECT_EQ(2, tracker.instances()); + EXPECT_EQ(1, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + set.insert(one); + // No construction since key==1 exists. + EXPECT_EQ(2, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + set.emplace(CheapType(1)); + // No construction since key==1 exists. + EXPECT_EQ(2, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + set.emplace(CheapType(2)); + // Construction since key==2 doesn't exist in the set. + EXPECT_EQ(3, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(set, ElementsAre(HasExpensiveValue(1), HasExpensiveValue(2))); + + // find + tracker.ResetCopiesMovesSwaps(); + auto itr = set.find(CheapType(1)); + ASSERT_NE(itr, set.end()); + EXPECT_EQ(1, itr->value()); + // contains + EXPECT_TRUE(set.contains(CheapType(2))); + // count + EXPECT_EQ(1, set.count(CheapType(2))); + // equal_range + auto eq_itr_pair = set.equal_range(CheapType(2)); + ASSERT_NE(eq_itr_pair.first, set.end()); + EXPECT_EQ(2, eq_itr_pair.first->value()); + // No construction for find, contains, count or equal_range. + EXPECT_EQ(3, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + // emplace + tracker.ResetCopiesMovesSwaps(); + set.emplace(3); + // Just one construction. + EXPECT_EQ(4, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + + tracker.ResetCopiesMovesSwaps(); + set.emplace(3); + // No additional construction since key==3 exists. + EXPECT_EQ(4, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(set, ElementsAre(HasExpensiveValue(1), HasExpensiveValue(2), + HasExpensiveValue(3))); + + // Test std::move() using insert(). + ExpensiveType four(4); + tracker.ResetCopiesMovesSwaps(); + set.insert(std::move(four)); + // Two constructions (regular and move). + EXPECT_EQ(6, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(1, tracker.moves()); + + EXPECT_THAT(set, ElementsAre(HasExpensiveValue(1), HasExpensiveValue(2), + HasExpensiveValue(3), HasExpensiveValue(4))); + + tracker.ResetCopiesMovesSwaps(); + set.erase(CheapType(1)); + // No construction and instance reduced by one. + EXPECT_EQ(5, tracker.instances()); + EXPECT_EQ(0, tracker.copies()); + EXPECT_EQ(0, tracker.moves()); + EXPECT_THAT(set, ElementsAre(HasExpensiveValue(2), HasExpensiveValue(3), + HasExpensiveValue(4))); +} + +TEST(LinkedHashSetTest, HeterogeneousStringViewLookup) { + linked_hash_set<std::string> set; + set.insert("foo"); + set.insert("bar"); + set.insert("blah"); + + { + absl::string_view lookup("foo"); + auto itr = set.find(lookup); + ASSERT_NE(itr, set.end()); + EXPECT_EQ("foo", *itr); + } + + // Not found. + { + absl::string_view lookup("foobar"); + EXPECT_EQ(set.end(), set.find(lookup)); + } + + { + absl::string_view lookup("blah"); + auto itr = set.find(lookup); + ASSERT_NE(itr, set.end()); + EXPECT_EQ("blah", *itr); + } +} + +TEST(LinkedHashSetTest, EmplaceString) { + std::vector<std::string> v = {"a", "b"}; + linked_hash_set<absl::string_view> hs(v.begin(), v.end()); + EXPECT_THAT(hs, ElementsAreArray(v)); +} + +TEST(LinkedHashSetTest, BitfieldArgument) { + union { + int n : 1; + }; + n = 0; + linked_hash_set<int> s = {n}; + s.insert(n); + s.insert(s.end(), n); + s.insert({n}); + s.erase(n); + s.count(n); + s.find(n); + s.contains(n); + s.equal_range(n); +} + +TEST(LinkedHashSetTest, MergeExtractInsert) { + struct Hash { + size_t operator()(const std::unique_ptr<int>& p) const { return *p; } + }; + struct Eq { + bool operator()(const std::unique_ptr<int>& a, + const std::unique_ptr<int>& b) const { + return *a == *b; + } + }; + linked_hash_set<std::unique_ptr<int>, Hash, Eq> set1, set2; + set1.insert(std::make_unique<int>(7)); + set1.insert(std::make_unique<int>(17)); + + set2.insert(std::make_unique<int>(7)); + set2.insert(std::make_unique<int>(19)); + + EXPECT_THAT(set1, ElementsAre(Pointee(7), Pointee(17))); + EXPECT_THAT(set2, ElementsAre(Pointee(7), Pointee(19))); + + set1.merge(set2); + + EXPECT_THAT(set1, ElementsAre(Pointee(7), Pointee(17), Pointee(19))); + EXPECT_THAT(set2, ElementsAre(Pointee(7))); + + auto node = set1.extract(std::make_unique<int>(7)); + EXPECT_TRUE(node); + EXPECT_THAT(node.value(), Pointee(7)); + EXPECT_THAT(set1, ElementsAre(Pointee(17), Pointee(19))); + + auto insert_result = set2.insert(std::move(node)); + EXPECT_FALSE(node); + EXPECT_FALSE(insert_result.inserted); + EXPECT_TRUE(insert_result.node); + EXPECT_THAT(insert_result.node.value(), Pointee(7)); + EXPECT_EQ(**insert_result.position, 7); + EXPECT_NE(insert_result.position->get(), insert_result.node.value().get()); + EXPECT_THAT(set2, ElementsAre(Pointee(7))); + + node = set1.extract(std::make_unique<int>(17)); + EXPECT_TRUE(node); + EXPECT_THAT(node.value(), Pointee(17)); + EXPECT_THAT(set1, ElementsAre(Pointee(19))); + + node.value() = std::make_unique<int>(23); + + insert_result = set2.insert(std::move(node)); + EXPECT_FALSE(node); + EXPECT_TRUE(insert_result.inserted); + EXPECT_FALSE(insert_result.node); + EXPECT_EQ(**insert_result.position, 23); + EXPECT_THAT(set2, ElementsAre(Pointee(7), Pointee(23))); +} + +TEST(LinkedHashSet, ExtractInsert) { + linked_hash_set<int> s = {1, 7, 2, 9}; + auto node = s.extract(1); + EXPECT_TRUE(node); + EXPECT_EQ(node.value(), 1); + EXPECT_THAT(s, ElementsAre(7, 2, 9)); + EXPECT_FALSE(s.contains(1)); + + node.value() = 17; + s.insert(std::move(node)); + EXPECT_FALSE(node); + EXPECT_THAT(s, ElementsAre(7, 2, 9, 17)); + EXPECT_TRUE(s.contains(17)); + + node = s.extract(s.find(9)); + EXPECT_TRUE(node); + EXPECT_EQ(node.value(), 9); + EXPECT_THAT(s, ElementsAre(7, 2, 17)); + EXPECT_FALSE(s.contains(9)); +} + +TEST(LinkedHashSet, Merge) { + linked_hash_set<int> m = {1, 7, 3, 6, 10}; + linked_hash_set<int> src = {1, 2, 9, 10, 4, 16}; + + m.merge(src); + + EXPECT_THAT(m, ElementsAre(1, 7, 3, 6, 10, 2, 9, 4, 16)); + for (int i : {1, 7, 3, 6, 10, 2, 9, 4, 16}) { + EXPECT_TRUE(m.contains(i)); + } + EXPECT_THAT(src, ElementsAre(1, 10)); + for (int i : {1, 10}) { + EXPECT_TRUE(src.contains(i)); + } + for (int i : {2, 9, 4, 16}) { + EXPECT_FALSE(src.contains(i)); + } +} + +TEST(LinkedHashSet, EraseRange) { + linked_hash_set<int> set = {1, 2, 3, 4, 5, 25, 36, 7, 8, 9, 81}; + auto start = set.find(3); + auto end = set.find(8); + auto itr = set.erase(start, end); + ASSERT_NE(itr, set.end()); + EXPECT_THAT(*itr, 8); + EXPECT_THAT(set, ElementsAre(1, 2, 8, 9, 81)); + for (int i : {1, 2, 8, 9, 81}) { + EXPECT_TRUE(set.contains(i)); + } + for (int i : {3, 4, 5, 25, 36, 7}) { + EXPECT_FALSE(set.contains(i)); + } +} + +TEST(LinkedHashSet, InsertInitializerList) { + linked_hash_set<int> set; + set.insert({1, 7, 2, 9, 3, 29}); + EXPECT_THAT(set, ElementsAre(1, 7, 2, 9, 3, 29)); + for (int i : {1, 7, 2, 9, 3, 29}) { + EXPECT_TRUE(set.contains(i)); + } +} + +struct CountedHash { + explicit CountedHash(int* count) : count(count) {} + size_t operator()(int value) const { + ++(*count); + return value; + } + int* count = nullptr; +}; + +// Makes a set too big for small object optimization. Counts the number of +// hashes in `count`, but leaves `count` set to 0. +linked_hash_set<int, CountedHash> MakeNonSmallSet(int* count) { + const int kFirstKey = -1000; + linked_hash_set<int, CountedHash> s(0, CountedHash(count)); + for (int i = kFirstKey; i < kFirstKey + 100; ++i) { + s.insert(i); + } + *count = 0; + return s; +} + +constexpr bool BuildHasDebugModeRehashes() { +#if !defined(NDEBUG) || defined(ABSL_HAVE_ADDRESS_SANITIZER) || \ + defined(ABSL_HAVE_MEMORY_SANITIZER) || defined(ABSL_HAVE_THREAD_SANITIZER) + return true; +#else + return false; +#endif +} + +TEST(LinkedHashSetTest, HashCountInOptBuilds) { + if (BuildHasDebugModeRehashes()) { + GTEST_SKIP() << "Only run under NDEBUG: `assert` statements and sanitizer " + "rehashing may cause redundant hashing."; + } + + using Set = linked_hash_set<int, CountedHash>; + { + int count = 0; + Set s = MakeNonSmallSet(&count); + s.insert(1); + EXPECT_EQ(count, 1); + s.erase(1); + EXPECT_EQ(count, 2); + } + { + int count = 0; + Set s = MakeNonSmallSet(&count); + s.insert(3); + EXPECT_EQ(count, 1); + auto node = s.extract(3); + EXPECT_EQ(count, 2); + s.insert(std::move(node)); + EXPECT_EQ(count, 3); + } + { + int count = 0; + Set s = MakeNonSmallSet(&count); + s.emplace(5); + EXPECT_EQ(count, 1); + } + { + int src_count = 0, dst_count = 0; + Set src = MakeNonSmallSet(&src_count); + Set dst = MakeNonSmallSet(&dst_count); + src.insert(7); + dst.merge(src); + EXPECT_LE(src_count, 200); + EXPECT_LE(dst_count, 200); + } +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/container/node_hash_set_test.cc b/absl/container/node_hash_set_test.cc index e616ac1..e1f5bd9 100644 --- a/absl/container/node_hash_set_test.cc +++ b/absl/container/node_hash_set_test.cc
@@ -35,8 +35,7 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { namespace { -using ::absl::container_internal::hash_internal::Enum; -using ::absl::container_internal::hash_internal::EnumClass; + using ::testing::IsEmpty; using ::testing::Pointee; using ::testing::UnorderedElementsAre;