Export of internal Abseil changes.

--
7a6ff16a85beb730c172d5d25cf1b5e1be885c56 by Laramie Leavitt <lar@google.com>:

Internal change.

PiperOrigin-RevId: 254454546

--
ff8f9bafaefc26d451f576ea4a06d150aed63f6f by Andy Soffer <asoffer@google.com>:

Internal changes

PiperOrigin-RevId: 254451562

--
deefc5b651b479ce36f0b4ef203e119c0c8936f2 by CJ Johnson <johnsoncj@google.com>:

Account for subtracting unsigned values from the size of InlinedVector

PiperOrigin-RevId: 254450625

--
3c677316a27bcadc17e41957c809ca472d5fef14 by Andy Soffer <asoffer@google.com>:

Add C++17's std::make_from_tuple to absl/utility/utility.h

PiperOrigin-RevId: 254411573

--
4ee3536a918830eeec402a28fc31a62c7c90b940 by CJ Johnson <johnsoncj@google.com>:

Adds benchmark for the rest of the InlinedVector public API

PiperOrigin-RevId: 254408378

--
e5a21a00700ee83498ff1efbf649169756463ee4 by CJ Johnson <johnsoncj@google.com>:

Updates the definition of InlinedVector::shrink_to_fit() to be exception safe and adds exception safety tests for it.

PiperOrigin-RevId: 254401387

--
2ea82e72b86d82d78b4e4712a63a55981b53c64b by Laramie Leavitt <lar@google.com>:

Use absl::InsecureBitGen in place of std::mt19937
in tests absl/random/...distribution_test.cc

PiperOrigin-RevId: 254289444

--
fa099e02c413a7ffda732415e8105cad26a90337 by Andy Soffer <asoffer@google.com>:

Internal changes

PiperOrigin-RevId: 254286334

--
ce34b7f36933b30cfa35b9c9a5697a792b5666e4 by Andy Soffer <asoffer@google.com>:

Internal changes

PiperOrigin-RevId: 254273059

--
6f9c473da7c2090c2e85a37c5f00622e8a912a89 by Jorg Brown <jorg@google.com>:

Change absl::container_internal::CompressedTuple to instantiate its
internal Storage class with the name of the type it's holding, rather
than the name of the Tuple.  This is not an externally-visible change,
other than less compiler memory is used and less debug information is
generated.

PiperOrigin-RevId: 254269285

--
8bd3c186bf2fc0c55d8a2dd6f28a5327502c9fba by Andy Soffer <asoffer@google.com>:

Adding short-hand IntervalClosed for IntervalClosedClosed and IntervalOpen for
IntervalOpenOpen.

PiperOrigin-RevId: 254252419

--
ea957f99b6a04fccd42aa05605605f3b44b1ecfd by Abseil Team <absl-team@google.com>:

Do not directly use __SIZEOF_INT128__.

In order to avoid linker errors when building with clang-cl (__fixunsdfti, __udivti3 and __fixunssfti are undefined), this CL uses ABSL_HAVE_INTRINSIC_INT128 which is not defined for clang-cl.

PiperOrigin-RevId: 254250739

--
89ab385cd26b34d64130bce856253aaba96d2345 by Andy Soffer <asoffer@google.com>:

Internal changes

PiperOrigin-RevId: 254242321

--
cffc793d93eca6d6bdf7de733847b6ab4a255ae9 by CJ Johnson <johnsoncj@google.com>:

Adds benchmark for InlinedVector::reserve(size_type)

PiperOrigin-RevId: 254199226

--
c90c7a9fa3c8f0c9d5114036979548b055ea2f2a by Gennadiy Rozental <rogeeff@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 254072387

--
c4c388beae016c9570ab54ffa1d52660e4a85b7b by Laramie Leavitt <lar@google.com>:

Internal cleanup.

PiperOrigin-RevId: 254062381

--
d3c992e221cc74e5372d0c8fa410170b6a43c062 by Tom Manshreck <shreck@google.com>:

Update distributions.h to Abseil standards

PiperOrigin-RevId: 254054946

--
d15ad0035c34ef11b14fadc5a4a2d3ec415f5518 by CJ Johnson <johnsoncj@google.com>:

Removes functions with only one caller from the implementation details of InlinedVector by manually inlining the definitions

PiperOrigin-RevId: 254005427

--
2f37e807efc3a8ef1f4b539bdd379917d4151520 by Andy Soffer <asoffer@google.com>:

Initial release of Abseil Random

PiperOrigin-RevId: 253999861

--
24ed1694b6430791d781ed533a8f8ccf6cac5856 by CJ Johnson <johnsoncj@google.com>:

Updates the definition of InlinedVector::assign(...)/InlinedVector::operator=(...) to new, exception-safe implementations with exception safety tests to boot

PiperOrigin-RevId: 253993691

--
5613d95f5a7e34a535cfaeadce801441e990843e by CJ Johnson <johnsoncj@google.com>:

Adds benchmarks for InlinedVector::shrink_to_fit()

PiperOrigin-RevId: 253989647

--
2a96ddfdac40bbb8cb6a7f1aeab90917067c6e63 by Abseil Team <absl-team@google.com>:

Initial release of Abseil Random

PiperOrigin-RevId: 253927497

--
bf1aff8fc9ffa921ad74643e9525ecf25b0d8dc1 by Andy Soffer <asoffer@google.com>:

Initial release of Abseil Random

PiperOrigin-RevId: 253920512

--
bfc03f4a3dcda3cf3a4b84bdb84cda24e3394f41 by Laramie Leavitt <lar@google.com>:

Internal change.

PiperOrigin-RevId: 253886486

--
05036cfcc078ca7c5f581a00dfb0daed568cbb69 by Eric Fiselier <ericwf@google.com>:

Don't include `winsock2.h` because it drags in `windows.h` and friends,
and they define awful macros like OPAQUE, ERROR, and more. This has the
potential to break abseil users.

Instead we only forward declare `timeval` and require Windows users
include `winsock2.h` themselves. This is both inconsistent and poor QoI, but so
including 'windows.h' is bad too.

PiperOrigin-RevId: 253852615
GitOrigin-RevId: 7a6ff16a85beb730c172d5d25cf1b5e1be885c56
Change-Id: Icd6aff87da26f29ec8915da856f051129987cef6

3 files changed, 256 insertions, 40 deletions

diff --git a/absl/container/internal/compressed_tuple.h b/absl/container/internal/compressed_tuple.h
index bb3471f..1713ad6 100644
--- a/absl/container/internal/compressed_tuple.h
+++ b/absl/container/internal/compressed_tuple.h
@@ -32,6 +32,7 @@
 #ifndef ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_
 #define ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_
 
+#include <initializer_list>
 #include <tuple>
 #include <type_traits>
 #include <utility>
@@ -75,17 +76,30 @@ constexpr bool IsFinal() {
 #endif
 }
 
+// We can't use EBCO on other CompressedTuples because that would mean that we
+// derive from multiple Storage<> instantiations with the same I parameter,
+// and potentially from multiple identical Storage<> instantiations.  So anytime
+// we use type inheritance rather than encapsulation, we mark
+// CompressedTupleImpl, to make this easy to detect.
+struct uses_inheritance {};
+
 template <typename T>
 constexpr bool ShouldUseBase() {
-  return std::is_class<T>::value && std::is_empty<T>::value && !IsFinal<T>();
+  return std::is_class<T>::value && std::is_empty<T>::value && !IsFinal<T>() &&
+         !std::is_base_of<uses_inheritance, T>::value;
 }
 
 // The storage class provides two specializations:
 //  - For empty classes, it stores T as a base class.
 //  - For everything else, it stores T as a member.
-template <typename D, size_t I, bool = ShouldUseBase<ElemT<D, I>>()>
+template <typename T, size_t I,
+#if defined(_MSC_VER)
+          bool UseBase =
+              ShouldUseBase<typename std::enable_if<true, T>::type>()>
+#else
+          bool UseBase = ShouldUseBase<T>()>
+#endif
 struct Storage {
-  using T = ElemT<D, I>;
   T value;
   constexpr Storage() = default;
   explicit constexpr Storage(T&& v) : value(absl::forward<T>(v)) {}
@@ -95,10 +109,8 @@ struct Storage {
   T&& get() && { return std::move(*this).value; }
 };
 
-template <typename D, size_t I>
-struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true>
-    : ElemT<D, I> {
-  using T = internal_compressed_tuple::ElemT<D, I>;
+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)) {}
   constexpr const T& get() const& { return *this; }
@@ -107,29 +119,54 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true>
   T&& get() && { return std::move(*this); }
 };
 
-template <typename D, typename I>
+template <typename D, typename I, bool ShouldAnyUseBase>
 struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl;
 
-template <typename... Ts, size_t... I>
-struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC
-    CompressedTupleImpl<CompressedTuple<Ts...>, absl::index_sequence<I...>>
+template <typename... Ts, size_t... I, bool ShouldAnyUseBase>
+struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
+    CompressedTuple<Ts...>, absl::index_sequence<I...>, ShouldAnyUseBase>
     // We use the dummy identity function through std::integral_constant to
     // convince MSVC of accepting and expanding I in that context. Without it
     // you would get:
     //   error C3548: 'I': parameter pack cannot be used in this context
-    : Storage<CompressedTuple<Ts...>,
-              std::integral_constant<size_t, I>::value>... {
+    : 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))... {}
+  friend CompressedTuple<Ts...>;
+};
+
+template <typename... Ts, size_t... I>
+struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl<
+    CompressedTuple<Ts...>, absl::index_sequence<I...>, false>
+    // 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<CompressedTuple<Ts...>, I>(absl::forward<Ts>(args))... {}
+      : Storage<Ts, I, false>(absl::forward<Ts>(args))... {}
+  friend CompressedTuple<Ts...>;
 };
 
+std::false_type Or(std::initializer_list<std::false_type>);
+std::true_type Or(std::initializer_list<bool>);
+
+// MSVC requires this to be done separately rather than within the declaration
+// of CompressedTuple below.
+template <typename... Ts>
+constexpr bool ShouldAnyUseBase() {
+  return decltype(
+      Or({std::integral_constant<bool, ShouldUseBase<Ts>()>()...})){};
+}
+
 }  // namespace internal_compressed_tuple
 
 // Helper class to perform the Empty Base Class Optimization.
 // Ts can contain classes and non-classes, empty or not. For the ones that
 // are empty classes, we perform the CompressedTuple. If all types in Ts are
-// empty classes, then CompressedTuple<Ts...> is itself an empty class.
+// empty classes, then CompressedTuple<Ts...> is itself an empty class.  (This
+// does not apply when one or more of those empty classes is itself an empty
+// CompressedTuple.)
 //
 // To access the members, use member .get<N>() function.
 //
@@ -145,7 +182,8 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC
 template <typename... Ts>
 class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
     : private internal_compressed_tuple::CompressedTupleImpl<
-          CompressedTuple<Ts...>, absl::index_sequence_for<Ts...>> {
+          CompressedTuple<Ts...>, absl::index_sequence_for<Ts...>,
+          internal_compressed_tuple::ShouldAnyUseBase<Ts...>()> {
  private:
   template <int I>
   using ElemT = internal_compressed_tuple::ElemT<CompressedTuple, I>;
@@ -157,24 +195,24 @@ class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
 
   template <int I>
   ElemT<I>& get() & {
-    return internal_compressed_tuple::Storage<CompressedTuple, I>::get();
+    return internal_compressed_tuple::Storage<ElemT<I>, I>::get();
   }
 
   template <int I>
   constexpr const ElemT<I>& get() const& {
-    return internal_compressed_tuple::Storage<CompressedTuple, I>::get();
+    return internal_compressed_tuple::Storage<ElemT<I>, I>::get();
   }
 
   template <int I>
   ElemT<I>&& get() && {
     return std::move(*this)
-        .internal_compressed_tuple::template Storage<CompressedTuple, I>::get();
+        .internal_compressed_tuple::template Storage<ElemT<I>, I>::get();
   }
 
   template <int I>
   constexpr const ElemT<I>&& get() const&& {
     return absl::move(*this)
-        .internal_compressed_tuple::template Storage<CompressedTuple, I>::get();
+        .internal_compressed_tuple::template Storage<ElemT<I>, I>::get();
   }
 };
 
diff --git a/absl/container/internal/compressed_tuple_test.cc b/absl/container/internal/compressed_tuple_test.cc
index 28e7741..3b0ec45 100644
--- a/absl/container/internal/compressed_tuple_test.cc
+++ b/absl/container/internal/compressed_tuple_test.cc
@@ -22,10 +22,8 @@
 #include "absl/memory/memory.h"
 #include "absl/utility/utility.h"
 
-namespace absl {
-namespace container_internal {
-namespace {
-
+// These are declared at global scope purely so that error messages
+// are smaller and easier to understand.
 enum class CallType { kConstRef, kConstMove };
 
 template <int>
@@ -45,6 +43,10 @@ struct TwoValues {
   U value2;
 };
 
+namespace absl {
+namespace container_internal {
+namespace {
+
 TEST(CompressedTupleTest, Sizeof) {
   EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int>));
   EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int, Empty<0>>));
@@ -120,9 +122,14 @@ TEST(CompressedTupleTest, Nested) {
   EXPECT_EQ(4 * sizeof(char),
             sizeof(CompressedTuple<CompressedTuple<char, char>,
                                    CompressedTuple<char, char>>));
-  EXPECT_TRUE(
-      (std::is_empty<CompressedTuple<CompressedTuple<Empty<0>>,
-                                     CompressedTuple<Empty<1>>>>::value));
+  EXPECT_TRUE((std::is_empty<CompressedTuple<Empty<0>, Empty<1>>>::value));
+
+  // Make sure everything still works when things are nested.
+  struct CT_Empty : CompressedTuple<Empty<0>> {};
+  CompressedTuple<Empty<0>, CT_Empty> nested_empty;
+  auto contained = nested_empty.get<0>();
+  auto nested = nested_empty.get<1>().get<0>();
+  EXPECT_TRUE((std::is_same<decltype(contained), decltype(nested)>::value));
 }
 
 TEST(CompressedTupleTest, Reference) {
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index 92c21ab..f117ee0 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -25,6 +25,7 @@
 #include "absl/container/internal/compressed_tuple.h"
 #include "absl/memory/memory.h"
 #include "absl/meta/type_traits.h"
+#include "absl/types/span.h"
 
 namespace absl {
 namespace inlined_vector_internal {
@@ -78,6 +79,14 @@ void ConstructElements(AllocatorType* alloc_ptr, ValueType* construct_first,
   }
 }
 
+template <typename ValueType, typename ValueAdapter, typename SizeType>
+void AssignElements(ValueType* assign_first, ValueAdapter* values_ptr,
+                    SizeType assign_size) {
+  for (SizeType i = 0; i < assign_size; ++i) {
+    values_ptr->AssignNext(assign_first + i);
+  }
+}
+
 template <typename AllocatorType>
 struct StorageView {
   using pointer = typename AllocatorType::pointer;
@@ -101,6 +110,11 @@ class IteratorValueAdapter {
     ++it_;
   }
 
+  void AssignNext(pointer assign_at) {
+    *assign_at = *it_;
+    ++it_;
+  }
+
  private:
   Iterator it_;
 };
@@ -119,6 +133,8 @@ class CopyValueAdapter {
     AllocatorTraits::construct(*alloc_ptr, construct_at, *ptr_);
   }
 
+  void AssignNext(pointer assign_at) { *assign_at = *ptr_; }
+
  private:
   const_pointer ptr_;
 };
@@ -135,6 +151,44 @@ class DefaultValueAdapter {
   void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
     AllocatorTraits::construct(*alloc_ptr, construct_at);
   }
+
+  void AssignNext(pointer assign_at) { *assign_at = value_type(); }
+};
+
+template <typename AllocatorType>
+class AllocationTransaction {
+  using value_type = typename AllocatorType::value_type;
+  using pointer = typename AllocatorType::pointer;
+  using size_type = typename AllocatorType::size_type;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit AllocationTransaction(AllocatorType* alloc_ptr)
+      : alloc_data_(*alloc_ptr, nullptr) {}
+
+  AllocationTransaction(const AllocationTransaction&) = delete;
+  void operator=(const AllocationTransaction&) = delete;
+
+  AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); }
+  pointer& GetData() { return alloc_data_.template get<1>(); }
+  size_type& GetCapacity() { return capacity_; }
+
+  bool DidAllocate() { return GetData() != nullptr; }
+  pointer Allocate(size_type capacity) {
+    GetData() = AllocatorTraits::allocate(GetAllocator(), capacity);
+    GetCapacity() = capacity;
+    return GetData();
+  }
+
+  ~AllocationTransaction() {
+    if (DidAllocate()) {
+      AllocatorTraits::deallocate(GetAllocator(), GetData(), GetCapacity());
+    }
+  }
+
+ private:
+  container_internal::CompressedTuple<AllocatorType, pointer> alloc_data_;
+  size_type capacity_ = 0;
 };
 
 template <typename T, size_t N, typename A>
@@ -167,6 +221,9 @@ class Storage {
   using DefaultValueAdapter =
       inlined_vector_internal::DefaultValueAdapter<allocator_type>;
 
+  using AllocationTransaction =
+      inlined_vector_internal::AllocationTransaction<allocator_type>;
+
   Storage() : metadata_() {}
 
   explicit Storage(const allocator_type& alloc)
@@ -215,19 +272,48 @@ class Storage {
 
   void SetIsAllocated() { GetSizeAndIsAllocated() |= 1; }
 
+  void UnsetIsAllocated() {
+    SetIsAllocated();
+    GetSizeAndIsAllocated() -= 1;
+  }
+
   void SetAllocatedSize(size_type size) {
     GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1);
   }
 
   void SetInlinedSize(size_type size) { GetSizeAndIsAllocated() = size << 1; }
 
+  void SetSize(size_type size) {
+    GetSizeAndIsAllocated() =
+        (size << 1) | static_cast<size_type>(GetIsAllocated());
+  }
+
   void AddSize(size_type count) { GetSizeAndIsAllocated() += count << 1; }
 
+  void SubtractSize(size_type count) {
+    assert(count <= GetSize());
+    GetSizeAndIsAllocated() -= count << 1;
+  }
+
   void SetAllocatedData(pointer data, size_type capacity) {
     data_.allocated.allocated_data = data;
     data_.allocated.allocated_capacity = capacity;
   }
 
+  void DeallocateIfAllocated() {
+    if (GetIsAllocated()) {
+      AllocatorTraits::deallocate(*GetAllocPtr(), GetAllocatedData(),
+                                  GetAllocatedCapacity());
+    }
+  }
+
+  void AcquireAllocation(AllocationTransaction* allocation_tx_ptr) {
+    SetAllocatedData(allocation_tx_ptr->GetData(),
+                     allocation_tx_ptr->GetCapacity());
+    allocation_tx_ptr->GetData() = nullptr;
+    allocation_tx_ptr->GetCapacity() = 0;
+  }
+
   void SwapSizeAndIsAllocated(Storage* other) {
     using std::swap;
     swap(GetSizeAndIsAllocated(), other->GetSizeAndIsAllocated());
@@ -238,11 +324,11 @@ class Storage {
     swap(data_.allocated, other->data_.allocated);
   }
 
-  void MemcpyContents(const Storage& other) {
-    assert(IsMemcpyOk::value);
+  void MemcpyFrom(const Storage& other_storage) {
+    assert(IsMemcpyOk::value || other_storage.GetIsAllocated());
 
-    GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
-    data_ = other.data_;
+    GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated();
+    data_ = other_storage.data_;
   }
 
   void DestroyAndDeallocate();
@@ -250,6 +336,11 @@ class Storage {
   template <typename ValueAdapter>
   void Initialize(ValueAdapter values, size_type new_size);
 
+  template <typename ValueAdapter>
+  void Assign(ValueAdapter values, size_type new_size);
+
+  void ShrinkToFit();
+
  private:
   size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
 
@@ -282,15 +373,10 @@ class Storage {
 
 template <typename T, size_t N, typename A>
 void Storage<T, N, A>::DestroyAndDeallocate() {
-  StorageView storage_view = MakeStorageView();
-
-  inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
-                                           storage_view.size);
-
-  if (GetIsAllocated()) {
-    AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
-                                storage_view.capacity);
-  }
+  inlined_vector_internal::DestroyElements(
+      GetAllocPtr(), (GetIsAllocated() ? GetAllocatedData() : GetInlinedData()),
+      GetSize());
+  DeallocateIfAllocated();
 }
 
 template <typename T, size_t N, typename A>
@@ -323,6 +409,91 @@ auto Storage<T, N, A>::Initialize(ValueAdapter values, size_type new_size)
   AddSize(new_size);
 }
 
+template <typename T, size_t N, typename A>
+template <typename ValueAdapter>
+auto Storage<T, N, A>::Assign(ValueAdapter values, size_type new_size) -> void {
+  StorageView storage_view = MakeStorageView();
+
+  AllocationTransaction allocation_tx(GetAllocPtr());
+
+  absl::Span<value_type> assign_loop;
+  absl::Span<value_type> construct_loop;
+  absl::Span<value_type> destroy_loop;
+
+  if (new_size > storage_view.capacity) {
+    construct_loop = {allocation_tx.Allocate(new_size), new_size};
+    destroy_loop = {storage_view.data, storage_view.size};
+  } else if (new_size > storage_view.size) {
+    assign_loop = {storage_view.data, storage_view.size};
+    construct_loop = {storage_view.data + storage_view.size,
+                      new_size - storage_view.size};
+  } else {
+    assign_loop = {storage_view.data, new_size};
+    destroy_loop = {storage_view.data + new_size, storage_view.size - new_size};
+  }
+
+  inlined_vector_internal::AssignElements(assign_loop.data(), &values,
+                                          assign_loop.size());
+  inlined_vector_internal::ConstructElements(
+      GetAllocPtr(), construct_loop.data(), &values, construct_loop.size());
+  inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(),
+                                           destroy_loop.size());
+
+  if (allocation_tx.DidAllocate()) {
+    DeallocateIfAllocated();
+    AcquireAllocation(&allocation_tx);
+    SetIsAllocated();
+  }
+
+  SetSize(new_size);
+}
+
+template <typename T, size_t N, typename A>
+auto Storage<T, N, A>::ShrinkToFit() -> void {
+  // May only be called on allocated instances!
+  assert(GetIsAllocated());
+
+  StorageView storage_view = {GetAllocatedData(), GetSize(),
+                              GetAllocatedCapacity()};
+
+  AllocationTransaction allocation_tx(GetAllocPtr());
+
+  IteratorValueAdapter<MoveIterator> move_values(
+      MoveIterator(storage_view.data));
+
+  pointer construct_data;
+
+  if (storage_view.size <= static_cast<size_type>(N)) {
+    construct_data = GetInlinedData();
+  } else if (storage_view.size < GetAllocatedCapacity()) {
+    construct_data = allocation_tx.Allocate(storage_view.size);
+  } else {
+    return;
+  }
+
+  ABSL_INTERNAL_TRY {
+    inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data,
+                                               &move_values, storage_view.size);
+  }
+  ABSL_INTERNAL_CATCH_ANY {
+    // Writing to inlined data will trample on the existing state, thus it needs
+    // to be restored when a construction fails.
+    SetAllocatedData(storage_view.data, storage_view.capacity);
+    ABSL_INTERNAL_RETHROW;
+  }
+
+  inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
+                                           storage_view.size);
+  AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
+                              storage_view.capacity);
+
+  if (allocation_tx.DidAllocate()) {
+    AcquireAllocation(&allocation_tx);
+  } else {
+    UnsetIsAllocated();
+  }
+}
+
 }  // namespace inlined_vector_internal
 }  // namespace absl