about summary refs log tree commit diff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel8
-rw-r--r--absl/container/fixed_array.h27
-rw-r--r--absl/container/fixed_array_test.cc38
-rw-r--r--absl/container/inlined_vector.h36
-rw-r--r--absl/container/inlined_vector_test.cc77
5 files changed, 171 insertions, 15 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 7d550cb16c5a..8bdf63122aba 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -18,6 +18,7 @@ load(
     "//absl:copts.bzl",
     "ABSL_DEFAULT_COPTS",
     "ABSL_TEST_COPTS",
+    "ABSL_EXCEPTIONS_FLAG",
 )
 
 package(default_visibility = ["//visibility:public"])
@@ -33,16 +34,16 @@ cc_library(
         "//absl/base:core_headers",
         "//absl/base:dynamic_annotations",
         "//absl/base:throw_delegate",
+        "//absl/memory",
     ],
 )
 
 cc_test(
     name = "fixed_array_test",
     srcs = ["fixed_array_test.cc"],
-    copts = ABSL_TEST_COPTS + ["-fexceptions"],
+    copts = ABSL_TEST_COPTS + ABSL_EXCEPTIONS_FLAG,
     deps = [
         ":fixed_array",
-        "//absl/base:core_headers",
         "//absl/base:exception_testing",
         "//absl/memory",
         "@com_google_googletest//:gtest_main",
@@ -55,7 +56,6 @@ cc_test(
     copts = ABSL_TEST_COPTS,
     deps = [
         ":fixed_array",
-        "//absl/base:core_headers",
         "//absl/base:exception_testing",
         "//absl/memory",
         "@com_google_googletest//:gtest_main",
@@ -77,7 +77,7 @@ cc_library(
 cc_test(
     name = "inlined_vector_test",
     srcs = ["inlined_vector_test.cc"],
-    copts = ABSL_TEST_COPTS + ["-fexceptions"],
+    copts = ABSL_TEST_COPTS + ABSL_EXCEPTIONS_FLAG,
     deps = [
         ":inlined_vector",
         ":test_instance_tracker",
diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h
index 58240b499a56..b92d90564d21 100644
--- a/absl/container/fixed_array.h
+++ b/absl/container/fixed_array.h
@@ -47,6 +47,7 @@
 #include "absl/base/macros.h"
 #include "absl/base/optimization.h"
 #include "absl/base/port.h"
+#include "absl/memory/memory.h"
 
 namespace absl {
 
@@ -107,6 +108,15 @@ class FixedArray {
           ? kInlineBytesDefault / sizeof(value_type)
           : inlined;
 
+  FixedArray(const FixedArray& other) : rep_(other.begin(), other.end()) {}
+  FixedArray(FixedArray&& other) noexcept(
+  // clang-format off
+      absl::allocator_is_nothrow<std::allocator<value_type>>::value &&
+  // clang-format on
+          std::is_nothrow_move_constructible<value_type>::value)
+      : rep_(std::make_move_iterator(other.begin()),
+             std::make_move_iterator(other.end())) {}
+
   // Creates an array object that can store `n` elements.
   // Note that trivially constructible elements will be uninitialized.
   explicit FixedArray(size_type n) : rep_(n) {}
@@ -126,11 +136,9 @@ class FixedArray {
 
   ~FixedArray() {}
 
-  // Copy and move construction and assignment are deleted because (1) you can't
-  // copy or move an array, (2) assignment breaks the invariant that the size of
-  // a `FixedArray` never changes, and (3) there's no clear answer as to what
-  // should happen to a moved-from `FixedArray`.
-  FixedArray(const FixedArray&) = delete;
+  // Assignments are deleted because they break the invariant that the size of a
+  // `FixedArray` never changes.
+  void operator=(FixedArray&&) = delete;
   void operator=(const FixedArray&) = delete;
 
   // FixedArray::size()
@@ -167,6 +175,7 @@ class FixedArray {
   // fixed array. This pointer can be used to access and modify the contained
   // elements.
   pointer data() { return AsValue(rep_.begin()); }
+
   // FixedArray::operator[]
   //
   // Returns a reference the ith element of the fixed array.
@@ -449,7 +458,7 @@ class FixedArray {
       // Loop optimizes to nothing for trivially destructible T.
       for (Holder* p = end(); p != begin();) (--p)->~Holder();
       if (IsAllocated(size())) {
-        ::operator delete[](begin());
+        std::allocator<Holder>().deallocate(p_, n_);
       } else {
         this->AnnotateDestruct(size());
       }
@@ -461,17 +470,13 @@ class FixedArray {
    private:
     Holder* MakeHolder(size_type n) {
       if (IsAllocated(n)) {
-        return Allocate(n);
+        return std::allocator<Holder>().allocate(n);
       } else {
         this->AnnotateConstruct(n);
         return this->data();
       }
     }
 
-    Holder* Allocate(size_type n) {
-      return static_cast<Holder*>(::operator new[](n * sizeof(Holder)));
-    }
-
     bool IsAllocated(size_type n) const { return n > inline_elements; }
 
     const size_type n_;
diff --git a/absl/container/fixed_array_test.cc b/absl/container/fixed_array_test.cc
index 9e88eab0c696..2142132d1352 100644
--- a/absl/container/fixed_array_test.cc
+++ b/absl/container/fixed_array_test.cc
@@ -27,6 +27,8 @@
 #include "absl/base/internal/exception_testing.h"
 #include "absl/memory/memory.h"
 
+using ::testing::ElementsAreArray;
+
 namespace {
 
 // Helper routine to determine if a absl::FixedArray used stack allocation.
@@ -89,6 +91,41 @@ class ThreeInts {
 
 int ThreeInts::counter = 0;
 
+TEST(FixedArrayTest, CopyCtor) {
+  absl::FixedArray<int, 10> on_stack(5);
+  std::iota(on_stack.begin(), on_stack.end(), 0);
+  absl::FixedArray<int, 10> stack_copy = on_stack;
+  EXPECT_THAT(stack_copy, ElementsAreArray(on_stack));
+  EXPECT_TRUE(IsOnStack(stack_copy));
+
+  absl::FixedArray<int, 10> allocated(15);
+  std::iota(allocated.begin(), allocated.end(), 0);
+  absl::FixedArray<int, 10> alloced_copy = allocated;
+  EXPECT_THAT(alloced_copy, ElementsAreArray(allocated));
+  EXPECT_FALSE(IsOnStack(alloced_copy));
+}
+
+TEST(FixedArrayTest, MoveCtor) {
+  absl::FixedArray<std::unique_ptr<int>, 10> on_stack(5);
+  for (int i = 0; i < 5; ++i) {
+    on_stack[i] = absl::make_unique<int>(i);
+  }
+
+  absl::FixedArray<std::unique_ptr<int>, 10> stack_copy = std::move(on_stack);
+  for (int i = 0; i < 5; ++i) EXPECT_EQ(*(stack_copy[i]), i);
+  EXPECT_EQ(stack_copy.size(), on_stack.size());
+
+  absl::FixedArray<std::unique_ptr<int>, 10> allocated(15);
+  for (int i = 0; i < 15; ++i) {
+    allocated[i] = absl::make_unique<int>(i);
+  }
+
+  absl::FixedArray<std::unique_ptr<int>, 10> alloced_copy =
+      std::move(allocated);
+  for (int i = 0; i < 15; ++i) EXPECT_EQ(*(alloced_copy[i]), i);
+  EXPECT_EQ(allocated.size(), alloced_copy.size());
+}
+
 TEST(FixedArrayTest, SmallObjects) {
   // Small object arrays
   {
@@ -467,6 +504,7 @@ struct PickyDelete {
 
 TEST(FixedArrayTest, UsesGlobalAlloc) { absl::FixedArray<PickyDelete, 0> a(5); }
 
+
 TEST(FixedArrayTest, Data) {
   static const int kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
   absl::FixedArray<int> fa(std::begin(kInput), std::end(kInput));
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 4bf9c18adec4..feba87b58217 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -573,6 +573,42 @@ class InlinedVector {
     }
   }
 
+  // InlinedVector::shrink_to_fit()
+  //
+  // Reduces memory usage by freeing unused memory.
+  // After this call `capacity()` will be equal to `max(N, size())`.
+  //
+  // If `size() <= N` and the elements are currently stored on the heap, they
+  // will be moved to the inlined storage and the heap memory deallocated.
+  // If `size() > N` and `size() < capacity()` the elements will be moved to
+  // a reallocated storage on heap.
+  void shrink_to_fit() {
+    const auto s = size();
+    if (!allocated() || s == capacity()) {
+      // There's nothing to deallocate.
+      return;
+    }
+
+    if (s <= N) {
+      // Move the elements to the inlined storage.
+      // We have to do this using a temporary, because inlined_storage and
+      // allocation_storage are in a union field.
+      auto temp = std::move(*this);
+      assign(std::make_move_iterator(temp.begin()),
+             std::make_move_iterator(temp.end()));
+      return;
+    }
+
+    // Reallocate storage and move elements.
+    // We can't simply use the same approach as above, because assign() would
+    // call into reserve() internally and reserve larger capacity than we need.
+    Allocation new_allocation(allocator(), s);
+    UninitializedCopy(std::make_move_iterator(allocated_space()),
+                      std::make_move_iterator(allocated_space() + s),
+                      new_allocation.buffer());
+    ResetAllocation(new_allocation, s);
+  }
+
   // InlinedVector::swap()
   //
   // Swaps the contents of this inlined vector with the contents of `other`.
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc
index 8527ba1aa008..0e39855b3066 100644
--- a/absl/container/inlined_vector_test.cc
+++ b/absl/container/inlined_vector_test.cc
@@ -407,6 +407,69 @@ TEST(InlinedVectorTest, EmplaceBack) {
   EXPECT_EQ(allocated_element.second, 1729);
 }
 
+TEST(InlinedVectorTest, ShrinkToFitGrowingVector) {
+  absl::InlinedVector<std::pair<std::string, int>, 1> v;
+
+  v.shrink_to_fit();
+  EXPECT_EQ(v.capacity(), 1);
+
+  v.emplace_back("answer", 42);
+  v.shrink_to_fit();
+  EXPECT_EQ(v.capacity(), 1);
+
+  v.emplace_back("taxicab", 1729);
+  EXPECT_GE(v.capacity(), 2);
+  v.shrink_to_fit();
+  EXPECT_EQ(v.capacity(), 2);
+
+  v.reserve(100);
+  EXPECT_GE(v.capacity(), 100);
+  v.shrink_to_fit();
+  EXPECT_EQ(v.capacity(), 2);
+}
+
+TEST(InlinedVectorTest, ShrinkToFitEdgeCases) {
+  {
+    absl::InlinedVector<std::pair<std::string, int>, 1> v;
+    v.emplace_back("answer", 42);
+    v.emplace_back("taxicab", 1729);
+    EXPECT_GE(v.capacity(), 2);
+    v.pop_back();
+    v.shrink_to_fit();
+    EXPECT_EQ(v.capacity(), 1);
+    EXPECT_EQ(v[0].first, "answer");
+    EXPECT_EQ(v[0].second, 42);
+  }
+
+  {
+    absl::InlinedVector<std::string, 2> v(100);
+    v.resize(0);
+    v.shrink_to_fit();
+    EXPECT_EQ(v.capacity(), 2);  // inlined capacity
+  }
+
+  {
+    absl::InlinedVector<std::string, 2> v(100);
+    v.resize(1);
+    v.shrink_to_fit();
+    EXPECT_EQ(v.capacity(), 2);  // inlined capacity
+  }
+
+  {
+    absl::InlinedVector<std::string, 2> v(100);
+    v.resize(2);
+    v.shrink_to_fit();
+    EXPECT_EQ(v.capacity(), 2);
+  }
+
+  {
+    absl::InlinedVector<std::string, 2> v(100);
+    v.resize(3);
+    v.shrink_to_fit();
+    EXPECT_EQ(v.capacity(), 3);
+  }
+}
+
 TEST(IntVec, Insert) {
   for (int len = 0; len < 20; len++) {
     for (int pos = 0; pos <= len; pos++) {
@@ -1589,6 +1652,20 @@ TEST(AllocatorSupportTest, CountAllocations) {
     AllocVec v3(std::move(v), alloc3);
     EXPECT_THAT(allocated3, v3.size() * sizeof(int));
   }
+  EXPECT_EQ(allocated, 0);
+  {
+    // Test shrink_to_fit deallocations.
+    AllocVec v(8, 2, alloc);
+    EXPECT_EQ(allocated, 8 * sizeof(int));
+    v.resize(5);
+    EXPECT_EQ(allocated, 8 * sizeof(int));
+    v.shrink_to_fit();
+    EXPECT_EQ(allocated, 5 * sizeof(int));
+    v.resize(4);
+    EXPECT_EQ(allocated, 5 * sizeof(int));
+    v.shrink_to_fit();
+    EXPECT_EQ(allocated, 0);
+  }
 }
 
 TEST(AllocatorSupportTest, SwapBothAllocated) {
generated by cgit-pink 1.4.1 (git 2.44.2) at 2025-01-05T03ยท04+0000