diff options
Diffstat (limited to 'absl/container')
| -rw-r--r-- | absl/container/BUILD.bazel | 26 | ||||
| -rw-r--r-- | absl/container/CMakeLists.txt | 27 | ||||
| -rw-r--r-- | absl/container/btree_set.h | 6 | ||||
| -rw-r--r-- | absl/container/flat_hash_set.h | 7 | ||||
| -rw-r--r-- | absl/container/internal/btree.h | 25 | ||||
| -rw-r--r-- | absl/container/internal/common_policy_traits.h | 101 | ||||
| -rw-r--r-- | absl/container/internal/common_policy_traits_test.cc | 119 | ||||
| -rw-r--r-- | absl/container/internal/hash_policy_traits.h | 59 | ||||
| -rw-r--r-- | absl/container/internal/hash_policy_traits_test.cc | 64 |
9 files changed, 278 insertions, 156 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index d749c1ca..71afe9d2 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -460,7 +460,10 @@ cc_library( hdrs = ["internal/hash_policy_traits.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/meta:type_traits"], + deps = [ + ":common_policy_traits", + "//absl/meta:type_traits", + ], ) cc_test( @@ -475,6 +478,26 @@ cc_test( ) cc_library( + name = "common_policy_traits", + hdrs = ["internal/common_policy_traits.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + visibility = ["//visibility:private"], + deps = ["//absl/meta:type_traits"], +) + +cc_test( + name = "common_policy_traits_test", + srcs = ["internal/common_policy_traits_test.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":common_policy_traits", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( name = "hashtable_debug", hdrs = ["internal/hashtable_debug.h"], copts = ABSL_DEFAULT_COPTS, @@ -905,6 +928,7 @@ cc_library( visibility = ["//visibility:public"], deps = [ ":common", + ":common_policy_traits", ":compressed_tuple", ":container_memory", ":layout", diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 4155f335..a3fdb969 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -28,6 +28,7 @@ absl_cc_library( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::container_common + absl::common_policy_traits absl::compare absl::compressed_tuple absl::container_memory @@ -531,6 +532,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::common_policy_traits absl::meta PUBLIC ) @@ -550,6 +552,31 @@ absl_cc_test( # Internal-only target, do not depend on directly. absl_cc_library( NAME + common_policy_traits + HDRS + "internal/common_policy_traits.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::meta + PUBLIC +) + +absl_cc_test( + NAME + common_policy_traits_test + SRCS + "internal/common_policy_traits_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::common_policy_traits + GTest::gmock_main +) + +# Internal-only target, do not depend on directly. +absl_cc_library( + NAME hashtablez_sampler HDRS "internal/hashtablez_sampler.h" diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h index 695b09f5..e823a2a0 100644 --- a/absl/container/btree_set.h +++ b/absl/container/btree_set.h @@ -760,12 +760,6 @@ struct set_slot_policy { static void destroy(Alloc *alloc, slot_type *slot) { absl::allocator_traits<Alloc>::destroy(*alloc, slot); } - - template <typename Alloc> - static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) { - construct(alloc, new_slot, old_slot); - destroy(alloc, old_slot); - } }; // A parameters structure for holding the type parameters for a btree_set. diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index 4938c703..f5376f99 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h @@ -474,13 +474,6 @@ struct FlatHashSetPolicy { absl::allocator_traits<Allocator>::destroy(*alloc, slot); } - template <class Allocator> - static void transfer(Allocator* alloc, slot_type* new_slot, - slot_type* old_slot) { - construct(alloc, new_slot, std::move(*old_slot)); - destroy(alloc, old_slot); - } - static T& element(slot_type* slot) { return *slot; } template <class F, class... Args> diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 203823b0..ecf31bea 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -61,6 +61,7 @@ #include "absl/base/internal/raw_logging.h" #include "absl/base/macros.h" #include "absl/container/internal/common.h" +#include "absl/container/internal/common_policy_traits.h" #include "absl/container/internal/compressed_tuple.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/layout.h" @@ -356,7 +357,7 @@ class map_value_compare { template <typename Key, typename Compare, typename Alloc, int TargetNodeSize, bool IsMulti, bool IsMap, typename SlotPolicy> -struct common_params { +struct common_params : common_policy_traits<SlotPolicy> { using original_key_compare = Compare; // If Compare is a common comparator for a string-like type, then we adapt it @@ -438,28 +439,6 @@ struct common_params { absl::conditional_t<(kNodeSlotSpace / sizeof(slot_type) > (std::numeric_limits<uint8_t>::max)()), uint16_t, uint8_t>; // NOLINT - - // The following methods are necessary for passing this struct as PolicyTraits - // for node_handle and/or are used within btree. - static value_type &element(slot_type *slot) { - return slot_policy::element(slot); - } - static const value_type &element(const slot_type *slot) { - return slot_policy::element(slot); - } - template <class... Args> - static void construct(Alloc *alloc, slot_type *slot, Args &&...args) { - slot_policy::construct(alloc, slot, std::forward<Args>(args)...); - } - static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { - slot_policy::construct(alloc, slot, other); - } - static void destroy(Alloc *alloc, slot_type *slot) { - slot_policy::destroy(alloc, slot); - } - static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) { - slot_policy::transfer(alloc, new_slot, old_slot); - } }; // An adapter class that converts a lower-bound compare into an upper-bound diff --git a/absl/container/internal/common_policy_traits.h b/absl/container/internal/common_policy_traits.h new file mode 100644 index 00000000..cc2e89ba --- /dev/null +++ b/absl/container/internal/common_policy_traits.h @@ -0,0 +1,101 @@ +// 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. + +#ifndef ABSL_CONTAINER_INTERNAL_COMMON_POLICY_TRAITS_H_ +#define ABSL_CONTAINER_INTERNAL_COMMON_POLICY_TRAITS_H_ + +#include <cstddef> +#include <memory> +#include <new> +#include <type_traits> +#include <utility> + +#include "absl/meta/type_traits.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +// Defines how slots are initialized/destroyed/moved. +template <class Policy, class = void> +struct common_policy_traits { + // The actual object stored in the container. + using slot_type = typename Policy::slot_type; + + + // PRECONDITION: `slot` is UNINITIALIZED + // POSTCONDITION: `slot` is INITIALIZED + template <class Alloc, class... Args> + static void construct(Alloc* alloc, slot_type* slot, Args&&... args) { + Policy::construct(alloc, slot, std::forward<Args>(args)...); + } + + // PRECONDITION: `slot` is INITIALIZED + // POSTCONDITION: `slot` is UNINITIALIZED + template <class Alloc> + static void destroy(Alloc* alloc, slot_type* slot) { + Policy::destroy(alloc, slot); + } + + // Transfers the `old_slot` to `new_slot`. Any memory allocated by the + // allocator inside `old_slot` to `new_slot` can be transferred. + // + // OPTIONAL: defaults to: + // + // clone(new_slot, std::move(*old_slot)); + // destroy(old_slot); + // + // PRECONDITION: `new_slot` is UNINITIALIZED and `old_slot` is INITIALIZED + // POSTCONDITION: `new_slot` is INITIALIZED and `old_slot` is + // UNINITIALIZED + template <class Alloc> + static void transfer(Alloc* alloc, slot_type* new_slot, slot_type* old_slot) { + transfer_impl(alloc, new_slot, old_slot, 0); + } + + // PRECONDITION: `slot` is INITIALIZED + // POSTCONDITION: `slot` is INITIALIZED + // Note: we use remove_const_t so that the two overloads have different args + // in the case of sets with explicitly const value_types. + template <class P = Policy> + static auto element(absl::remove_const_t<slot_type>* slot) + -> decltype(P::element(slot)) { + return P::element(slot); + } + template <class P = Policy> + static auto element(const slot_type* slot) -> decltype(P::element(slot)) { + return P::element(slot); + } + + private: + // Use auto -> decltype as an enabler. + template <class Alloc, class P = Policy> + static auto transfer_impl(Alloc* alloc, slot_type* new_slot, + slot_type* old_slot, int) + -> decltype((void)P::transfer(alloc, new_slot, old_slot)) { + P::transfer(alloc, new_slot, old_slot); + } + template <class Alloc> + static void transfer_impl(Alloc* alloc, slot_type* new_slot, + slot_type* old_slot, char) { + construct(alloc, new_slot, std::move(element(old_slot))); + destroy(alloc, old_slot); + } +}; + +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_COMMON_POLICY_TRAITS_H_ 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 <functional> +#include <memory> +#include <new> + +#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<void(void*, Slot*, Slot)> construct; + static std::function<void(void*, Slot*)> destroy; + + static std::function<Slot&(Slot*)> element; +}; + +std::function<void(void*, Slot*, Slot)> PolicyWithoutOptionalOps::construct; +std::function<void(void*, Slot*)> PolicyWithoutOptionalOps::destroy; + +std::function<Slot&(Slot*)> PolicyWithoutOptionalOps::element; + +struct PolicyWithOptionalOps : PolicyWithoutOptionalOps { + static std::function<void(void*, Slot*, Slot*)> transfer; +}; + +std::function<void(void*, Slot*, Slot*)> 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<Slot> alloc; + int a = 53; + + MockFunction<void(void*, Slot*, Slot)> construct; + MockFunction<void(void*, Slot*)> destroy; + + MockFunction<Slot&(Slot*)> element; + + MockFunction<void(void*, Slot*, Slot*)> transfer; +}; + +TEST_F(Test, construct) { + EXPECT_CALL(construct, Call(&alloc, &a, 53)); + common_policy_traits<PolicyWithoutOptionalOps>::construct(&alloc, &a, 53); +} + +TEST_F(Test, destroy) { + EXPECT_CALL(destroy, Call(&alloc, &a)); + common_policy_traits<PolicyWithoutOptionalOps>::destroy(&alloc, &a); +} + +TEST_F(Test, element) { + int b = 0; + EXPECT_CALL(element, Call(&a)).WillOnce(ReturnRef(b)); + EXPECT_EQ(&b, &common_policy_traits<PolicyWithoutOptionalOps>::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<PolicyWithoutOptionalOps>::transfer(&alloc, &a, &b); +} + +TEST_F(Test, with_transfer) { + int b = 42; + EXPECT_CALL(transfer, Call(&alloc, &a, &b)); + common_policy_traits<PolicyWithOptionalOps>::transfer(&alloc, &a, &b); +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h index 46c97b18..164ec123 100644 --- a/absl/container/internal/hash_policy_traits.h +++ b/absl/container/internal/hash_policy_traits.h @@ -21,6 +21,7 @@ #include <type_traits> #include <utility> +#include "absl/container/internal/common_policy_traits.h" #include "absl/meta/type_traits.h" namespace absl { @@ -29,7 +30,7 @@ namespace container_internal { // Defines how slots are initialized/destroyed/moved. template <class Policy, class = void> -struct hash_policy_traits { +struct hash_policy_traits : common_policy_traits<Policy> { // The type of the keys stored in the hashtable. using key_type = typename Policy::key_type; @@ -87,43 +88,6 @@ struct hash_policy_traits { // Defaults to false if not provided by the policy. using constant_iterators = ConstantIteratorsImpl<>; - // PRECONDITION: `slot` is UNINITIALIZED - // POSTCONDITION: `slot` is INITIALIZED - template <class Alloc, class... Args> - static void construct(Alloc* alloc, slot_type* slot, Args&&... args) { - Policy::construct(alloc, slot, std::forward<Args>(args)...); - } - - // PRECONDITION: `slot` is INITIALIZED - // POSTCONDITION: `slot` is UNINITIALIZED - template <class Alloc> - static void destroy(Alloc* alloc, slot_type* slot) { - Policy::destroy(alloc, slot); - } - - // Transfers the `old_slot` to `new_slot`. Any memory allocated by the - // allocator inside `old_slot` to `new_slot` can be transferred. - // - // OPTIONAL: defaults to: - // - // clone(new_slot, std::move(*old_slot)); - // destroy(old_slot); - // - // PRECONDITION: `new_slot` is UNINITIALIZED and `old_slot` is INITIALIZED - // POSTCONDITION: `new_slot` is INITIALIZED and `old_slot` is - // UNINITIALIZED - template <class Alloc> - static void transfer(Alloc* alloc, slot_type* new_slot, slot_type* old_slot) { - transfer_impl(alloc, new_slot, old_slot, 0); - } - - // PRECONDITION: `slot` is INITIALIZED - // POSTCONDITION: `slot` is INITIALIZED - template <class P = Policy> - static auto element(slot_type* slot) -> decltype(P::element(slot)) { - return P::element(slot); - } - // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`. // // If `slot` is nullptr, returns the constant amount of memory owned by any @@ -174,8 +138,8 @@ struct hash_policy_traits { // Used for node handle manipulation. template <class P = Policy> static auto mutable_key(slot_type* slot) - -> decltype(P::apply(ReturnKey(), element(slot))) { - return P::apply(ReturnKey(), element(slot)); + -> decltype(P::apply(ReturnKey(), hash_policy_traits::element(slot))) { + return P::apply(ReturnKey(), hash_policy_traits::element(slot)); } // Returns the "value" (as opposed to the "key") portion of the element. Used @@ -184,21 +148,6 @@ struct hash_policy_traits { static auto value(T* elem) -> decltype(P::value(elem)) { return P::value(elem); } - - private: - // Use auto -> decltype as an enabler. - template <class Alloc, class P = Policy> - static auto transfer_impl(Alloc* alloc, slot_type* new_slot, - slot_type* old_slot, int) - -> decltype((void)P::transfer(alloc, new_slot, old_slot)) { - P::transfer(alloc, new_slot, old_slot); - } - template <class Alloc> - static void transfer_impl(Alloc* alloc, slot_type* new_slot, - slot_type* old_slot, char) { - construct(alloc, new_slot, std::move(element(old_slot))); - destroy(alloc, old_slot); - } }; } // namespace container_internal diff --git a/absl/container/internal/hash_policy_traits_test.cc b/absl/container/internal/hash_policy_traits_test.cc index 6ef8b9e0..82d7cc3a 100644 --- a/absl/container/internal/hash_policy_traits_test.cc +++ b/absl/container/internal/hash_policy_traits_test.cc @@ -38,81 +38,31 @@ struct PolicyWithoutOptionalOps { using key_type = Slot; using init_type = Slot; - static std::function<void(void*, Slot*, Slot)> construct; - static std::function<void(void*, Slot*)> destroy; - static std::function<Slot&(Slot*)> element; static int apply(int v) { return apply_impl(v); } static std::function<int(int)> apply_impl; static std::function<Slot&(Slot*)> value; }; -std::function<void(void*, Slot*, Slot)> PolicyWithoutOptionalOps::construct; -std::function<void(void*, Slot*)> PolicyWithoutOptionalOps::destroy; - -std::function<Slot&(Slot*)> PolicyWithoutOptionalOps::element; std::function<int(int)> PolicyWithoutOptionalOps::apply_impl; std::function<Slot&(Slot*)> PolicyWithoutOptionalOps::value; -struct PolicyWithOptionalOps : PolicyWithoutOptionalOps { - static std::function<void(void*, Slot*, Slot*)> transfer; -}; - -std::function<void(void*, Slot*, Slot*)> 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); - }; PolicyWithoutOptionalOps::apply_impl = [&](int a1) -> int { return apply.Call(a1); }; PolicyWithoutOptionalOps::value = [&](Slot* a1) -> Slot& { return value.Call(a1); }; - - PolicyWithOptionalOps::transfer = [&](void* a1, Slot* a2, Slot* a3) { - return transfer.Call(a1, a2, a3); - }; } std::allocator<int> alloc; int a = 53; - - MockFunction<void(void*, Slot*, Slot)> construct; - MockFunction<void(void*, Slot*)> destroy; - - MockFunction<Slot&(Slot*)> element; MockFunction<int(int)> apply; MockFunction<Slot&(Slot*)> value; - - MockFunction<void(void*, Slot*, Slot*)> transfer; }; -TEST_F(Test, construct) { - EXPECT_CALL(construct, Call(&alloc, &a, 53)); - hash_policy_traits<PolicyWithoutOptionalOps>::construct(&alloc, &a, 53); -} - -TEST_F(Test, destroy) { - EXPECT_CALL(destroy, Call(&alloc, &a)); - hash_policy_traits<PolicyWithoutOptionalOps>::destroy(&alloc, &a); -} - -TEST_F(Test, element) { - int b = 0; - EXPECT_CALL(element, Call(&a)).WillOnce(ReturnRef(b)); - EXPECT_EQ(&b, &hash_policy_traits<PolicyWithoutOptionalOps>::element(&a)); -} - TEST_F(Test, apply) { EXPECT_CALL(apply, Call(42)).WillOnce(Return(1337)); EXPECT_EQ(1337, (hash_policy_traits<PolicyWithoutOptionalOps>::apply(42))); @@ -124,20 +74,6 @@ TEST_F(Test, value) { EXPECT_EQ(&b, &hash_policy_traits<PolicyWithoutOptionalOps>::value(&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)); - hash_policy_traits<PolicyWithoutOptionalOps>::transfer(&alloc, &a, &b); -} - -TEST_F(Test, with_transfer) { - int b = 42; - EXPECT_CALL(transfer, Call(&alloc, &a, &b)); - hash_policy_traits<PolicyWithOptionalOps>::transfer(&alloc, &a, &b); -} - } // namespace } // namespace container_internal ABSL_NAMESPACE_END |