From 6d9ea2b46f470406e1f49acc30b272c6e9f6cc5e Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Wed, 28 Sep 2022 10:44:11 -0700 Subject: Add common_policy_traits - a subset of hash_policy_traits that can be shared between raw_hash_set and btree. Also remove the transfer implementations from btree_set.h and flat_hash_set.h, which are equivalent to the default implementations. Motivation: this will simplify upcoming changes related to trivial relocation. PiperOrigin-RevId: 477493403 Change-Id: I75babef4c93dec3a8105f86c58af54199bb1ec9c --- .../internal/common_policy_traits_test.cc | 119 +++++++++++++++++++++ 1 file changed, 119 insertions(+) create mode 100644 absl/container/internal/common_policy_traits_test.cc (limited to 'absl/container/internal/common_policy_traits_test.cc') diff --git a/absl/container/internal/common_policy_traits_test.cc b/absl/container/internal/common_policy_traits_test.cc new file mode 100644 index 00000000..768d870e --- /dev/null +++ b/absl/container/internal/common_policy_traits_test.cc @@ -0,0 +1,119 @@ +// Copyright 2022 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/internal/common_policy_traits.h" + +#include +#include +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { +namespace { + +using ::testing::MockFunction; +using ::testing::Return; +using ::testing::ReturnRef; + +using Slot = int; + +struct PolicyWithoutOptionalOps { + using slot_type = Slot; + using key_type = Slot; + using init_type = Slot; + + static std::function construct; + static std::function destroy; + + static std::function element; +}; + +std::function PolicyWithoutOptionalOps::construct; +std::function PolicyWithoutOptionalOps::destroy; + +std::function PolicyWithoutOptionalOps::element; + +struct PolicyWithOptionalOps : PolicyWithoutOptionalOps { + static std::function transfer; +}; + +std::function PolicyWithOptionalOps::transfer; + +struct Test : ::testing::Test { + Test() { + PolicyWithoutOptionalOps::construct = [&](void* a1, Slot* a2, Slot a3) { + construct.Call(a1, a2, std::move(a3)); + }; + PolicyWithoutOptionalOps::destroy = [&](void* a1, Slot* a2) { + destroy.Call(a1, a2); + }; + + PolicyWithoutOptionalOps::element = [&](Slot* a1) -> Slot& { + return element.Call(a1); + }; + + PolicyWithOptionalOps::transfer = [&](void* a1, Slot* a2, Slot* a3) { + return transfer.Call(a1, a2, a3); + }; + } + + std::allocator alloc; + int a = 53; + + MockFunction construct; + MockFunction destroy; + + MockFunction element; + + MockFunction transfer; +}; + +TEST_F(Test, construct) { + EXPECT_CALL(construct, Call(&alloc, &a, 53)); + common_policy_traits::construct(&alloc, &a, 53); +} + +TEST_F(Test, destroy) { + EXPECT_CALL(destroy, Call(&alloc, &a)); + common_policy_traits::destroy(&alloc, &a); +} + +TEST_F(Test, element) { + int b = 0; + EXPECT_CALL(element, Call(&a)).WillOnce(ReturnRef(b)); + EXPECT_EQ(&b, &common_policy_traits::element(&a)); +} + +TEST_F(Test, without_transfer) { + int b = 42; + EXPECT_CALL(element, Call(&b)).WillOnce(::testing::ReturnRef(b)); + EXPECT_CALL(construct, Call(&alloc, &a, b)); + EXPECT_CALL(destroy, Call(&alloc, &b)); + common_policy_traits::transfer(&alloc, &a, &b); +} + +TEST_F(Test, with_transfer) { + int b = 42; + EXPECT_CALL(transfer, Call(&alloc, &a, &b)); + common_policy_traits::transfer(&alloc, &a, &b); +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl -- cgit v1.2.3 From f8e0ff7f33338c2874b75e45e4ea5abbfafb954c Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Mon, 3 Oct 2022 10:51:40 -0700 Subject: Use trivial relocation for transfers in swisstable and b-tree. PiperOrigin-RevId: 478547898 Change-Id: Ie20cd0a49df042be912888ee238333a5f5fa0404 --- absl/container/internal/common_policy_traits.h | 15 ++++++++++++++- absl/container/internal/common_policy_traits_test.cc | 9 +++++---- absl/container/internal/container_memory.h | 13 ++++++++++++- 3 files changed, 31 insertions(+), 6 deletions(-) (limited to 'absl/container/internal/common_policy_traits_test.cc') diff --git a/absl/container/internal/common_policy_traits.h b/absl/container/internal/common_policy_traits.h index cc2e89ba..c99e68f4 100644 --- a/absl/container/internal/common_policy_traits.h +++ b/absl/container/internal/common_policy_traits.h @@ -16,6 +16,7 @@ #define ABSL_CONTAINER_INTERNAL_COMMON_POLICY_TRAITS_H_ #include +#include #include #include #include @@ -32,7 +33,8 @@ template struct common_policy_traits { // The actual object stored in the container. using slot_type = typename Policy::slot_type; - + using reference = decltype(Policy::element(std::declval())); + using value_type = typename std::remove_reference::type; // PRECONDITION: `slot` is UNINITIALIZED // POSTCONDITION: `slot` is INITIALIZED @@ -89,6 +91,17 @@ struct common_policy_traits { template static void transfer_impl(Alloc* alloc, slot_type* new_slot, slot_type* old_slot, char) { +#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606 + if (absl::is_trivially_relocatable()) { + // TODO(b/247130232): remove cast after fixing class-memaccess warning. + std::memcpy(static_cast( + std::launder(const_cast*>( + &element(new_slot)))), + &element(old_slot), sizeof(value_type)); + return; + } +#endif + construct(alloc, new_slot, std::move(element(old_slot))); destroy(alloc, old_slot); } diff --git a/absl/container/internal/common_policy_traits_test.cc b/absl/container/internal/common_policy_traits_test.cc index 768d870e..5eaa4aae 100644 --- a/absl/container/internal/common_policy_traits_test.cc +++ b/absl/container/internal/common_policy_traits_test.cc @@ -27,7 +27,7 @@ namespace container_internal { namespace { using ::testing::MockFunction; -using ::testing::Return; +using ::testing::AnyNumber; using ::testing::ReturnRef; using Slot = int; @@ -101,9 +101,10 @@ TEST_F(Test, element) { TEST_F(Test, without_transfer) { int b = 42; - EXPECT_CALL(element, Call(&b)).WillOnce(::testing::ReturnRef(b)); - EXPECT_CALL(construct, Call(&alloc, &a, b)); - EXPECT_CALL(destroy, Call(&alloc, &b)); + EXPECT_CALL(element, Call(&a)).Times(AnyNumber()).WillOnce(ReturnRef(a)); + EXPECT_CALL(element, Call(&b)).WillOnce(ReturnRef(b)); + EXPECT_CALL(construct, Call(&alloc, &a, b)).Times(AnyNumber()); + EXPECT_CALL(destroy, Call(&alloc, &b)).Times(AnyNumber()); common_policy_traits::transfer(&alloc, &a, &b); } diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 00e9f6d7..c29c533b 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h @@ -17,6 +17,7 @@ #include #include +#include #include #include #include @@ -340,7 +341,8 @@ template struct map_slot_policy { using slot_type = map_slot_type; using value_type = std::pair; - using mutable_value_type = std::pair; + using mutable_value_type = + std::pair, absl::remove_const_t>; private: static void emplace(slot_type* slot) { @@ -424,6 +426,15 @@ struct map_slot_policy { static void transfer(Allocator* alloc, slot_type* new_slot, slot_type* old_slot) { emplace(new_slot); +#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606 + if (absl::is_trivially_relocatable()) { + // TODO(b/247130232): remove cast after fixing class-memaccess warning. + std::memcpy(static_cast(std::launder(&new_slot->value)), + &old_slot->value, sizeof(value_type)); + return; + } +#endif + if (kMutableKeys::value) { absl::allocator_traits::construct( *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value)); -- cgit v1.2.3