about summary refs log tree commit diff
path: root/absl/container/internal
diff options
context:
space:
mode:
authorAbseil Team <absl-team@google.com>2019-07-17T20·35-0400
committerDerek Mauro <dmauro@google.com>2019-07-17T20·40-0400
commitc6c3c1b498e4ee939b24be59cae29d59c3863be8 (patch)
tree030b875cdbbd25d2d0b7bca0b68a71351eeb2c41 /absl/container/internal
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/internal')
-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
6 files changed, 263 insertions, 16 deletions
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
index b06e71131801..591d3ea11fa2 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 c29ab41eb9fd..7d08e370dec1 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 3b0ec4555abf..19af8f10aa6c 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 6667d3ad847a..d03dd82e7fd5 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 c4889cd47506..656e9806d899 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 3d4b2980ea8b..c4731dbe3d1d 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