Export of internal Abseil changes.

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

Merge external PR #324

PiperOrigin-RevId: 253849839

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

Merge external PR #323

PiperOrigin-RevId: 253849558

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

Removes `ivi` namespace typedef to reduce reader confusion

PiperOrigin-RevId: 253789534

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

New benchmarks the various overloads of InlinedVector::assign(...)/InlinedVector::operator=(...)

PiperOrigin-RevId: 253787316

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

Updates the definition of `InlinedVector::pop_back(...)` to be cleaner and more direct (hiding the is_allocated branch behind a single call to `data()`)

Adds exception safety test for `InlinedVector::pop_back(...)`

PiperOrigin-RevId: 253607385

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

Adds the remaining constructor exception safety tests for InlinedVector

PiperOrigin-RevId: 253592324

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

Updates the constructors of InlinedVector to new, exception-safe and more-performant implementations.

PiperOrigin-RevId: 253294508
GitOrigin-RevId: 635146be541d732fbf2e9c93c6bec89035552484
Change-Id: I7d37a749632084f5d7fa56d42392e622a9d0180d

1 files changed, 129 insertions, 3 deletions

diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index f4eb92ec169a..92c21ab96571 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -21,6 +21,7 @@
 #include <memory>
 #include <utility>
 
+#include "absl/base/macros.h"
 #include "absl/container/internal/compressed_tuple.h"
 #include "absl/memory/memory.h"
 #include "absl/meta/type_traits.h"
@@ -33,6 +34,14 @@ using IsAtLeastForwardIterator = std::is_convertible<
     typename std::iterator_traits<Iterator>::iterator_category,
     std::forward_iterator_tag>;
 
+template <typename AllocatorType>
+using IsMemcpyOk = absl::conjunction<
+    std::is_same<std::allocator<typename AllocatorType::value_type>,
+                 AllocatorType>,
+    absl::is_trivially_copy_constructible<typename AllocatorType::value_type>,
+    absl::is_trivially_copy_assignable<typename AllocatorType::value_type>,
+    absl::is_trivially_destructible<typename AllocatorType::value_type>>;
+
 template <typename AllocatorType, typename ValueType, typename SizeType>
 void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first,
                      SizeType destroy_size) {
@@ -52,6 +61,23 @@ void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first,
 #endif  // NDEBUG
 }
 
+template <typename AllocatorType, typename ValueType, typename ValueAdapter,
+          typename SizeType>
+void ConstructElements(AllocatorType* alloc_ptr, ValueType* construct_first,
+                       ValueAdapter* values_ptr, SizeType construct_size) {
+  // If any construction fails, all completed constructions are rolled back.
+  for (SizeType i = 0; i < construct_size; ++i) {
+    ABSL_INTERNAL_TRY {
+      values_ptr->ConstructNext(alloc_ptr, construct_first + i);
+    }
+    ABSL_INTERNAL_CATCH_ANY {
+      inlined_vector_internal::DestroyElements(alloc_ptr, construct_first, i);
+
+      ABSL_INTERNAL_RETHROW;
+    }
+  }
+}
+
 template <typename AllocatorType>
 struct StorageView {
   using pointer = typename AllocatorType::pointer;
@@ -62,6 +88,55 @@ struct StorageView {
   size_type capacity;
 };
 
+template <typename AllocatorType, typename Iterator>
+class IteratorValueAdapter {
+  using pointer = typename AllocatorType::pointer;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit IteratorValueAdapter(const Iterator& it) : it_(it) {}
+
+  void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
+    AllocatorTraits::construct(*alloc_ptr, construct_at, *it_);
+    ++it_;
+  }
+
+ private:
+  Iterator it_;
+};
+
+template <typename AllocatorType>
+class CopyValueAdapter {
+  using pointer = typename AllocatorType::pointer;
+  using const_pointer = typename AllocatorType::const_pointer;
+  using const_reference = typename AllocatorType::const_reference;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit CopyValueAdapter(const_reference v) : ptr_(std::addressof(v)) {}
+
+  void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
+    AllocatorTraits::construct(*alloc_ptr, construct_at, *ptr_);
+  }
+
+ private:
+  const_pointer ptr_;
+};
+
+template <typename AllocatorType>
+class DefaultValueAdapter {
+  using pointer = typename AllocatorType::pointer;
+  using value_type = typename AllocatorType::value_type;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit DefaultValueAdapter() {}
+
+  void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
+    AllocatorTraits::construct(*alloc_ptr, construct_at);
+  }
+};
+
 template <typename T, size_t N, typename A>
 class Storage {
  public:
@@ -78,10 +153,20 @@ class Storage {
   using const_iterator = const_pointer;
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  using MoveIterator = std::move_iterator<iterator>;
   using AllocatorTraits = absl::allocator_traits<allocator_type>;
+  using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<allocator_type>;
 
   using StorageView = inlined_vector_internal::StorageView<allocator_type>;
 
+  template <typename Iterator>
+  using IteratorValueAdapter =
+      inlined_vector_internal::IteratorValueAdapter<allocator_type, Iterator>;
+  using CopyValueAdapter =
+      inlined_vector_internal::CopyValueAdapter<allocator_type>;
+  using DefaultValueAdapter =
+      inlined_vector_internal::DefaultValueAdapter<allocator_type>;
+
   Storage() : metadata_() {}
 
   explicit Storage(const allocator_type& alloc)
@@ -128,6 +213,8 @@ class Storage {
     return std::addressof(metadata_.template get<0>());
   }
 
+  void SetIsAllocated() { GetSizeAndIsAllocated() |= 1; }
+
   void SetAllocatedSize(size_type size) {
     GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1);
   }
@@ -151,8 +238,18 @@ class Storage {
     swap(data_.allocated, other->data_.allocated);
   }
 
+  void MemcpyContents(const Storage& other) {
+    assert(IsMemcpyOk::value);
+
+    GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
+    data_ = other.data_;
+  }
+
   void DestroyAndDeallocate();
 
+  template <typename ValueAdapter>
+  void Initialize(ValueAdapter values, size_type new_size);
+
  private:
   size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
 
@@ -185,11 +282,10 @@ class Storage {
 
 template <typename T, size_t N, typename A>
 void Storage<T, N, A>::DestroyAndDeallocate() {
-  namespace ivi = inlined_vector_internal;
-
   StorageView storage_view = MakeStorageView();
 
-  ivi::DestroyElements(GetAllocPtr(), storage_view.data, storage_view.size);
+  inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
+                                           storage_view.size);
 
   if (GetIsAllocated()) {
     AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
@@ -197,6 +293,36 @@ void Storage<T, N, A>::DestroyAndDeallocate() {
   }
 }
 
+template <typename T, size_t N, typename A>
+template <typename ValueAdapter>
+auto Storage<T, N, A>::Initialize(ValueAdapter values, size_type new_size)
+    -> void {
+  // Only callable from constructors!
+  assert(!GetIsAllocated());
+  assert(GetSize() == 0);
+
+  pointer construct_data;
+
+  if (new_size > static_cast<size_type>(N)) {
+    // Because this is only called from the `InlinedVector` constructors, it's
+    // safe to take on the allocation with size `0`. If `ConstructElements(...)`
+    // throws, deallocation will be automatically handled by `~Storage()`.
+    construct_data = AllocatorTraits::allocate(*GetAllocPtr(), new_size);
+    SetAllocatedData(construct_data, new_size);
+    SetIsAllocated();
+  } else {
+    construct_data = GetInlinedData();
+  }
+
+  inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data,
+                                             &values, new_size);
+
+  // Since the initial size was guaranteed to be `0` and the allocated bit is
+  // already correct for either case, *adding* `new_size` gives us the correct
+  // result faster than setting it directly.
+  AddSize(new_size);
+}
+
 }  // namespace inlined_vector_internal
 }  // namespace absl