summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-07-17 16:35:47 -0400
committerGravatar Derek Mauro <dmauro@google.com>2019-07-17 16:40:57 -0400
commitc6c3c1b498e4ee939b24be59cae29d59c3863be8 (patch)
tree030b875cdbbd25d2d0b7bca0b68a71351eeb2c41 /absl/container
parent44efe96dfca674a17b45ca53fc77fb69f1e29bf4 (diff)
Export of internal Abseil changes.
-- ed3a3431eee9e48e6553b0320e0308d2dde6725c by Derek Mauro <dmauro@google.com>: Project import generated by Copybara. PiperOrigin-RevId: 258631680 GitOrigin-RevId: ed3a3431eee9e48e6553b0320e0308d2dde6725c Change-Id: I1d7ae86a79783842092d29504605ba039c369603
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel3
-rw-r--r--absl/container/CMakeLists.txt3
-rw-r--r--absl/container/internal/common.h23
-rw-r--r--absl/container/internal/compressed_tuple.h49
-rw-r--r--absl/container/internal/compressed_tuple_test.cc201
-rw-r--r--absl/container/internal/hashtablez_sampler.cc2
-rw-r--r--absl/container/internal/raw_hash_set.h2
-rw-r--r--absl/container/internal/test_instance_tracker.h2
8 files changed, 269 insertions, 16 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 17d725c1..b8cf17fc 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -44,7 +44,10 @@ cc_test(
linkopts = ABSL_DEFAULT_LINKOPTS,
deps = [
":compressed_tuple",
+ ":test_instance_tracker",
"//absl/memory",
+ "//absl/types:any",
+ "//absl/types:optional",
"//absl/utility",
"@com_google_googletest//:gtest_main",
],
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 6df331e1..5d7c75dd 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -43,8 +43,11 @@ absl_cc_test(
COPTS
${ABSL_TEST_COPTS}
DEPS
+ absl::any
absl::compressed_tuple
absl::memory
+ absl::optional
+ absl::test_instance_tracker
absl::utility
gmock_main
)
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
index b06e7113..591d3ea1 100644
--- a/absl/container/internal/common.h
+++ b/absl/container/internal/common.h
@@ -77,10 +77,18 @@ class node_handle_base {
protected:
friend struct CommonAccess;
- node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) {
+ struct transfer_tag_t {};
+ node_handle_base(transfer_tag_t, const allocator_type& a, slot_type* s)
+ : alloc_(a) {
PolicyTraits::transfer(alloc(), slot(), s);
}
+ struct move_tag_t {};
+ node_handle_base(move_tag_t, const allocator_type& a, slot_type* s)
+ : alloc_(a) {
+ PolicyTraits::construct(alloc(), slot(), s);
+ }
+
void destroy() {
if (!empty()) {
PolicyTraits::destroy(alloc(), slot());
@@ -121,7 +129,7 @@ class node_handle : public node_handle_base<PolicyTraits, Alloc> {
private:
friend struct CommonAccess;
- node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
+ using Base::Base;
};
// For maps.
@@ -148,7 +156,7 @@ class node_handle<Policy, PolicyTraits, Alloc,
private:
friend struct CommonAccess;
- node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
+ using Base::Base;
};
// Provide access to non-public node-handle functions.
@@ -164,8 +172,13 @@ struct CommonAccess {
}
template <typename T, typename... Args>
- static T Make(Args&&... args) {
- return T(std::forward<Args>(args)...);
+ static T Transfer(Args&&... args) {
+ return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...);
+ }
+
+ template <typename T, typename... Args>
+ static T Move(Args&&... args) {
+ return T(typename T::move_tag_t{}, std::forward<Args>(args)...);
}
};
diff --git a/absl/container/internal/compressed_tuple.h b/absl/container/internal/compressed_tuple.h
index c29ab41e..7d08e370 100644
--- a/absl/container/internal/compressed_tuple.h
+++ b/absl/container/internal/compressed_tuple.h
@@ -102,7 +102,9 @@ template <typename T, size_t I,
struct Storage {
T value;
constexpr Storage() = default;
- explicit constexpr Storage(T&& v) : value(absl::forward<T>(v)) {}
+ template <typename V>
+ explicit constexpr Storage(absl::in_place_t, V&& v)
+ : value(absl::forward<V>(v)) {}
constexpr const T& get() const& { return value; }
T& get() & { return value; }
constexpr const T&& get() const&& { return absl::move(*this).value; }
@@ -112,7 +114,11 @@ struct Storage {
template <typename T, size_t I>
struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<T, I, true> : T {
constexpr Storage() = default;
- explicit constexpr Storage(T&& v) : T(absl::forward<T>(v)) {}
+
+ template <typename V>
+ explicit constexpr Storage(absl::in_place_t, V&& v)
+ : T(absl::forward<V>(v)) {}
+
constexpr const T& get() const& { return *this; }
T& get() & { return *this; }
constexpr const T&& get() const&& { return absl::move(*this); }
@@ -132,8 +138,9 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
: uses_inheritance,
Storage<Ts, std::integral_constant<size_t, I>::value>... {
constexpr CompressedTupleImpl() = default;
- explicit constexpr CompressedTupleImpl(Ts&&... args)
- : Storage<Ts, I>(absl::forward<Ts>(args))... {}
+ template <typename... Vs>
+ explicit constexpr CompressedTupleImpl(absl::in_place_t, Vs&&... args)
+ : Storage<Ts, I>(absl::in_place, absl::forward<Vs>(args))... {}
friend CompressedTuple<Ts...>;
};
@@ -143,8 +150,9 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
// We use the dummy identity function as above...
: Storage<Ts, std::integral_constant<size_t, I>::value, false>... {
constexpr CompressedTupleImpl() = default;
- explicit constexpr CompressedTupleImpl(Ts&&... args)
- : Storage<Ts, I, false>(absl::forward<Ts>(args))... {}
+ template <typename... Vs>
+ explicit constexpr CompressedTupleImpl(absl::in_place_t, Vs&&... args)
+ : Storage<Ts, I, false>(absl::in_place, absl::forward<Vs>(args))... {}
friend CompressedTuple<Ts...>;
};
@@ -159,6 +167,11 @@ constexpr bool ShouldAnyUseBase() {
Or({std::integral_constant<bool, ShouldUseBase<Ts>()>()...})){};
}
+template <typename T, typename V>
+using TupleMoveConstructible = typename std::conditional<
+ std::is_reference<T>::value, std::is_convertible<V, T>,
+ std::is_constructible<T, V&&>>::type;
+
} // namespace internal_compressed_tuple
// Helper class to perform the Empty Base Class Optimization.
@@ -192,9 +205,29 @@ class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
using StorageT = internal_compressed_tuple::Storage<ElemT<I>, I>;
public:
+ // There seems to be a bug in MSVC dealing in which using '=default' here will
+ // cause the compiler to ignore the body of other constructors. The work-
+ // around is to explicitly implement the default constructor.
+#if defined(_MSC_VER)
+ constexpr CompressedTuple() : CompressedTuple::CompressedTupleImpl() {}
+#else
constexpr CompressedTuple() = default;
- explicit constexpr CompressedTuple(Ts... base)
- : CompressedTuple::CompressedTupleImpl(absl::forward<Ts>(base)...) {}
+#endif
+ explicit constexpr CompressedTuple(const Ts&... base)
+ : CompressedTuple::CompressedTupleImpl(absl::in_place, base...) {}
+
+ template <typename... Vs,
+ absl::enable_if_t<
+ absl::conjunction<
+ // Ensure we are not hiding default copy/move constructors.
+ absl::negation<std::is_same<void(CompressedTuple),
+ void(absl::decay_t<Vs>...)>>,
+ internal_compressed_tuple::TupleMoveConstructible<
+ Ts, Vs&&>...>::value,
+ bool> = true>
+ explicit constexpr CompressedTuple(Vs&&... base)
+ : CompressedTuple::CompressedTupleImpl(absl::in_place,
+ absl::forward<Vs>(base)...) {}
template <int I>
ElemT<I>& get() & {
diff --git a/absl/container/internal/compressed_tuple_test.cc b/absl/container/internal/compressed_tuple_test.cc
index 3b0ec455..19af8f10 100644
--- a/absl/container/internal/compressed_tuple_test.cc
+++ b/absl/container/internal/compressed_tuple_test.cc
@@ -19,7 +19,10 @@
#include "gmock/gmock.h"
#include "gtest/gtest.h"
+#include "absl/container/internal/test_instance_tracker.h"
#include "absl/memory/memory.h"
+#include "absl/types/any.h"
+#include "absl/types/optional.h"
#include "absl/utility/utility.h"
// These are declared at global scope purely so that error messages
@@ -43,10 +46,14 @@ struct TwoValues {
U value2;
};
+
namespace absl {
namespace container_internal {
namespace {
+using absl::test_internal::CopyableMovableInstance;
+using absl::test_internal::InstanceTracker;
+
TEST(CompressedTupleTest, Sizeof) {
EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int>));
EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int, Empty<0>>));
@@ -62,6 +69,141 @@ TEST(CompressedTupleTest, Sizeof) {
sizeof(CompressedTuple<int, Empty<0>, NotEmpty<double>, Empty<1>>));
}
+TEST(CompressedTupleTest, OneMoveOnRValueConstructionTemp) {
+ InstanceTracker tracker;
+ CompressedTuple<CopyableMovableInstance> x1(CopyableMovableInstance(1));
+ EXPECT_EQ(tracker.instances(), 1);
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_LE(tracker.moves(), 1);
+ EXPECT_EQ(x1.get<0>().value(), 1);
+}
+
+TEST(CompressedTupleTest, OneMoveOnRValueConstructionMove) {
+ InstanceTracker tracker;
+
+ CopyableMovableInstance i1(1);
+ CompressedTuple<CopyableMovableInstance> x1(std::move(i1));
+ EXPECT_EQ(tracker.instances(), 2);
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_LE(tracker.moves(), 1);
+ EXPECT_EQ(x1.get<0>().value(), 1);
+}
+
+TEST(CompressedTupleTest, OneMoveOnRValueConstructionMixedTypes) {
+ InstanceTracker tracker;
+ CopyableMovableInstance i1(1);
+ CopyableMovableInstance i2(2);
+ Empty<0> empty;
+ CompressedTuple<CopyableMovableInstance, CopyableMovableInstance&, Empty<0>>
+ x1(std::move(i1), i2, empty);
+ EXPECT_EQ(x1.get<0>().value(), 1);
+ EXPECT_EQ(x1.get<1>().value(), 2);
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_EQ(tracker.moves(), 1);
+}
+
+struct IncompleteType;
+CompressedTuple<CopyableMovableInstance, IncompleteType&, Empty<0>>
+MakeWithIncomplete(CopyableMovableInstance i1,
+ IncompleteType& t, // NOLINT
+ Empty<0> empty) {
+ return CompressedTuple<CopyableMovableInstance, IncompleteType&, Empty<0>>{
+ std::move(i1), t, empty};
+}
+
+struct IncompleteType {};
+TEST(CompressedTupleTest, OneMoveOnRValueConstructionWithIncompleteType) {
+ InstanceTracker tracker;
+ CopyableMovableInstance i1(1);
+ Empty<0> empty;
+ struct DerivedType : IncompleteType {int value = 0;};
+ DerivedType fd;
+ fd.value = 7;
+
+ CompressedTuple<CopyableMovableInstance, IncompleteType&, Empty<0>> x1 =
+ MakeWithIncomplete(std::move(i1), fd, empty);
+
+ EXPECT_EQ(x1.get<0>().value(), 1);
+ EXPECT_EQ(static_cast<DerivedType&>(x1.get<1>()).value, 7);
+
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_EQ(tracker.moves(), 2);
+}
+
+TEST(CompressedTupleTest,
+ OneMoveOnRValueConstructionMixedTypes_BraceInitPoisonPillExpected) {
+ InstanceTracker tracker;
+ CopyableMovableInstance i1(1);
+ CopyableMovableInstance i2(2);
+ CompressedTuple<CopyableMovableInstance, CopyableMovableInstance&, Empty<0>>
+ x1(std::move(i1), i2, {}); // NOLINT
+ EXPECT_EQ(x1.get<0>().value(), 1);
+ EXPECT_EQ(x1.get<1>().value(), 2);
+ EXPECT_EQ(tracker.instances(), 3);
+ // We are forced into the `const Ts&...` constructor (invoking copies)
+ // because we need it to deduce the type of `{}`.
+ // std::tuple also has this behavior.
+ // Note, this test is proof that this is expected behavior, but it is not
+ // _desired_ behavior.
+ EXPECT_EQ(tracker.copies(), 1);
+ EXPECT_EQ(tracker.moves(), 0);
+}
+
+TEST(CompressedTupleTest, OneCopyOnLValueConstruction) {
+ InstanceTracker tracker;
+ CopyableMovableInstance i1(1);
+
+ CompressedTuple<CopyableMovableInstance> x1(i1);
+ EXPECT_EQ(tracker.copies(), 1);
+ EXPECT_EQ(tracker.moves(), 0);
+
+ tracker.ResetCopiesMovesSwaps();
+
+ CopyableMovableInstance i2(2);
+ const CopyableMovableInstance& i2_ref = i2;
+ CompressedTuple<CopyableMovableInstance> x2(i2_ref);
+ EXPECT_EQ(tracker.copies(), 1);
+ EXPECT_EQ(tracker.moves(), 0);
+}
+
+TEST(CompressedTupleTest, OneMoveOnRValueAccess) {
+ InstanceTracker tracker;
+ CopyableMovableInstance i1(1);
+ CompressedTuple<CopyableMovableInstance> x(std::move(i1));
+ tracker.ResetCopiesMovesSwaps();
+
+ CopyableMovableInstance i2 = std::move(x).get<0>();
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_EQ(tracker.moves(), 1);
+}
+
+TEST(CompressedTupleTest, OneCopyOnLValueAccess) {
+ InstanceTracker tracker;
+
+ CompressedTuple<CopyableMovableInstance> x(CopyableMovableInstance(0));
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_EQ(tracker.moves(), 1);
+
+ CopyableMovableInstance t = x.get<0>();
+ EXPECT_EQ(tracker.copies(), 1);
+ EXPECT_EQ(tracker.moves(), 1);
+}
+
+TEST(CompressedTupleTest, ZeroCopyOnRefAccess) {
+ InstanceTracker tracker;
+
+ CompressedTuple<CopyableMovableInstance> x(CopyableMovableInstance(0));
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_EQ(tracker.moves(), 1);
+
+ CopyableMovableInstance& t1 = x.get<0>();
+ const CopyableMovableInstance& t2 = x.get<0>();
+ EXPECT_EQ(tracker.copies(), 0);
+ EXPECT_EQ(tracker.moves(), 1);
+ EXPECT_EQ(t1.value(), 0);
+ EXPECT_EQ(t2.value(), 0);
+}
+
TEST(CompressedTupleTest, Access) {
struct S {
std::string x;
@@ -173,7 +315,40 @@ TEST(CompressedTupleTest, MoveOnlyElements) {
EXPECT_EQ(*x1, 5);
}
+TEST(CompressedTupleTest, MoveConstructionMoveOnlyElements) {
+ CompressedTuple<std::unique_ptr<std::string>> base(
+ absl::make_unique<std::string>("str"));
+ EXPECT_EQ(*base.get<0>(), "str");
+
+ CompressedTuple<std::unique_ptr<std::string>> copy(std::move(base));
+ EXPECT_EQ(*copy.get<0>(), "str");
+}
+
+TEST(CompressedTupleTest, AnyElements) {
+ any a(std::string("str"));
+ CompressedTuple<any, any&> x(any(5), a);
+ EXPECT_EQ(absl::any_cast<int>(x.get<0>()), 5);
+ EXPECT_EQ(absl::any_cast<std::string>(x.get<1>()), "str");
+
+ a = 0.5f;
+ EXPECT_EQ(absl::any_cast<float>(x.get<1>()), 0.5);
+
+ // Ensure copy construction work in the face of a type with a universal
+ // implicit constructor;
+ CompressedTuple<absl::any> c{}, d(c); // NOLINT
+}
+
TEST(CompressedTupleTest, Constexpr) {
+ struct NonTrivialStruct {
+ constexpr NonTrivialStruct() = default;
+ constexpr int value() const { return v; }
+ int v = 5;
+ };
+ struct TrivialStruct {
+ TrivialStruct() = default;
+ constexpr int value() const { return v; }
+ int v;
+ };
constexpr CompressedTuple<int, double, CompressedTuple<int>, Empty<0>> x(
7, 1.25, CompressedTuple<int>(5), {});
constexpr int x0 = x.get<0>();
@@ -186,6 +361,32 @@ TEST(CompressedTupleTest, Constexpr) {
EXPECT_EQ(x2, 5);
EXPECT_EQ(x3, CallType::kConstRef);
+#if !defined(__GNUC__) || defined(__clang__) || __GNUC__ > 4
+ constexpr CompressedTuple<Empty<0>, TrivialStruct, int> trivial = {};
+ constexpr CallType trivial0 = trivial.get<0>().value();
+ constexpr int trivial1 = trivial.get<1>().value();
+ constexpr int trivial2 = trivial.get<2>();
+
+ EXPECT_EQ(trivial0, CallType::kConstRef);
+ EXPECT_EQ(trivial1, 0);
+ EXPECT_EQ(trivial2, 0);
+#endif
+
+ constexpr CompressedTuple<Empty<0>, NonTrivialStruct, absl::optional<int>>
+ non_trivial = {};
+ constexpr CallType non_trivial0 = non_trivial.get<0>().value();
+ constexpr int non_trivial1 = non_trivial.get<1>().value();
+ constexpr absl::optional<int> non_trivial2 = non_trivial.get<2>();
+
+ EXPECT_EQ(non_trivial0, CallType::kConstRef);
+ EXPECT_EQ(non_trivial1, 5);
+ EXPECT_EQ(non_trivial2, absl::nullopt);
+
+ static constexpr char data[] = "DEF";
+ constexpr CompressedTuple<const char*> z(data);
+ constexpr const char* z1 = z.get<0>();
+ EXPECT_EQ(std::string(z1), std::string(data));
+
#if defined(__clang__)
// An apparent bug in earlier versions of gcc claims these are ambiguous.
constexpr int x2m = absl::move(x.get<2>()).get<0>();
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc
index 6667d3ad..d03dd82e 100644
--- a/absl/container/internal/hashtablez_sampler.cc
+++ b/absl/container/internal/hashtablez_sampler.cc
@@ -32,7 +32,7 @@ constexpr int HashtablezInfo::kMaxStackDepth;
namespace {
ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
- false
+ false
};
ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20};
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index c4889cd4..656e9806 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1182,7 +1182,7 @@ class raw_hash_set {
node_type extract(const_iterator position) {
auto node =
- CommonAccess::Make<node_type>(alloc_ref(), position.inner_.slot_);
+ CommonAccess::Transfer<node_type>(alloc_ref(), position.inner_.slot_);
erase_meta_only(position);
return node;
}
diff --git a/absl/container/internal/test_instance_tracker.h b/absl/container/internal/test_instance_tracker.h
index 3d4b2980..c4731dbe 100644
--- a/absl/container/internal/test_instance_tracker.h
+++ b/absl/container/internal/test_instance_tracker.h
@@ -23,7 +23,7 @@
namespace absl {
namespace test_internal {
-// A type that counts number of occurences of the type, the live occurrences of
+// A type that counts number of occurrences of the type, the live occurrences of
// the type, as well as the number of copies, moves, swaps, and comparisons that
// have occurred on the type. This is used as a base class for the copyable,
// copyable+movable, and movable types below that are used in actual tests. Use