summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel26
-rw-r--r--absl/container/CMakeLists.txt27
-rw-r--r--absl/container/btree_set.h6
-rw-r--r--absl/container/flat_hash_set.h7
-rw-r--r--absl/container/internal/btree.h25
-rw-r--r--absl/container/internal/common_policy_traits.h101
-rw-r--r--absl/container/internal/common_policy_traits_test.cc119
-rw-r--r--absl/container/internal/hash_policy_traits.h59
-rw-r--r--absl/container/internal/hash_policy_traits_test.cc64
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