--- /dev/null
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
+#define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
+
+#include <cstddef>
+#include <cstring>
+#include <iterator>
+#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"
+#include "absl/types/span.h"
+
+namespace absl {
+namespace inlined_vector_internal {
+
+template <typename Iterator>
+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) {
+ using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ if (destroy_first != nullptr) {
+ for (auto i = destroy_size; i != 0;) {
+ --i;
+ AllocatorTraits::destroy(*alloc_ptr, destroy_first + i);
+ }
+
+#ifndef NDEBUG
+ // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
+ //
+ // Cast to `void*` to tell the compiler that we don't care that we might be
+ // scribbling on a vtable pointer.
+ auto* memory_ptr = static_cast<void*>(destroy_first);
+ auto memory_size = sizeof(ValueType) * destroy_size;
+ std::memset(memory_ptr, 0xab, memory_size);
+#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 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;
+ using size_type = typename AllocatorType::size_type;
+
+ pointer data;
+ size_type size;
+ 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_;
+ }
+
+ void AssignNext(pointer assign_at) {
+ *assign_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_);
+ }
+
+ void AssignNext(pointer assign_at) { *assign_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);
+ }
+
+ 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 AllocatorType>
+class ConstructionTransaction {
+ using pointer = typename AllocatorType::pointer;
+ using size_type = typename AllocatorType::size_type;
+
+ public:
+ explicit ConstructionTransaction(AllocatorType* alloc_ptr)
+ : alloc_data_(*alloc_ptr, nullptr) {}
+
+ ConstructionTransaction(const ConstructionTransaction&) = delete;
+ void operator=(const ConstructionTransaction&) = delete;
+
+ template <typename ValueAdapter>
+ void Construct(pointer data, ValueAdapter* values_ptr, size_type size) {
+ inlined_vector_internal::ConstructElements(std::addressof(GetAllocator()),
+ data, values_ptr, size);
+ GetData() = data;
+ GetSize() = size;
+ }
+ void Commit() {
+ GetData() = nullptr;
+ GetSize() = 0;
+ }
+
+ ~ConstructionTransaction() {
+ if (GetData() != nullptr) {
+ inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()),
+ GetData(), GetSize());
+ }
+ }
+
+ private:
+ AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); }
+ pointer& GetData() { return alloc_data_.template get<1>(); }
+ size_type& GetSize() { return size_; }
+
+ container_internal::CompressedTuple<AllocatorType, pointer> alloc_data_;
+ size_type size_ = 0;
+};
+
+template <typename T, size_t N, typename A>
+class Storage {
+ public:
+ using allocator_type = A;
+ using value_type = typename allocator_type::value_type;
+ using pointer = typename allocator_type::pointer;
+ using const_pointer = typename allocator_type::const_pointer;
+ using reference = typename allocator_type::reference;
+ using const_reference = typename allocator_type::const_reference;
+ using rvalue_reference = typename allocator_type::value_type&&;
+ using size_type = typename allocator_type::size_type;
+ using difference_type = typename allocator_type::difference_type;
+ using iterator = pointer;
+ 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>;
+
+ using AllocationTransaction =
+ inlined_vector_internal::AllocationTransaction<allocator_type>;
+ using ConstructionTransaction =
+ inlined_vector_internal::ConstructionTransaction<allocator_type>;
+
+ Storage() : metadata_() {}
+
+ explicit Storage(const allocator_type& alloc)
+ : metadata_(alloc, /* empty and inlined */ 0) {}
+
+ ~Storage() {
+ pointer data = GetIsAllocated() ? GetAllocatedData() : GetInlinedData();
+ inlined_vector_internal::DestroyElements(GetAllocPtr(), data, GetSize());
+ DeallocateIfAllocated();
+ }
+
+ size_type GetSize() const { return GetSizeAndIsAllocated() >> 1; }
+
+ bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; }
+
+ pointer GetInlinedData() {
+ return reinterpret_cast<pointer>(
+ std::addressof(data_.inlined.inlined_data[0]));
+ }
+
+ const_pointer GetInlinedData() const {
+ return reinterpret_cast<const_pointer>(
+ std::addressof(data_.inlined.inlined_data[0]));
+ }
+
+ pointer GetAllocatedData() { return data_.allocated.allocated_data; }
+
+ const_pointer GetAllocatedData() const {
+ return data_.allocated.allocated_data;
+ }
+
+ size_type GetAllocatedCapacity() const {
+ return data_.allocated.allocated_capacity;
+ }
+
+ StorageView MakeStorageView() {
+ return GetIsAllocated() ? StorageView{GetAllocatedData(), GetSize(),
+ GetAllocatedCapacity()}
+ : StorageView{GetInlinedData(), GetSize(),
+ static_cast<size_type>(N)};
+ }
+
+ allocator_type* GetAllocPtr() {
+ return std::addressof(metadata_.template get<0>());
+ }
+
+ const allocator_type* GetAllocPtr() const {
+ return std::addressof(metadata_.template get<0>());
+ }
+
+ 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 MemcpyFrom(const Storage& other_storage) {
+ assert(IsMemcpyOk::value || other_storage.GetIsAllocated());
+
+ GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated();
+ data_ = other_storage.data_;
+ }
+
+ template <typename ValueAdapter>
+ void Initialize(ValueAdapter values, size_type new_size);
+
+ template <typename ValueAdapter>
+ void Assign(ValueAdapter values, size_type new_size);
+
+ template <typename ValueAdapter>
+ void Resize(ValueAdapter values, size_type new_size);
+
+ template <typename... Args>
+ reference EmplaceBack(Args&&... args);
+
+ iterator Erase(const_iterator from, const_iterator to);
+
+ void Reserve(size_type requested_capacity);
+
+ void ShrinkToFit();
+
+ void Swap(Storage* other_storage_ptr);
+
+ private:
+ size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
+
+ const size_type& GetSizeAndIsAllocated() const {
+ return metadata_.template get<1>();
+ }
+
+ static size_type NextCapacityFrom(size_type current_capacity) {
+ return current_capacity * 2;
+ }
+
+ static size_type LegacyNextCapacityFrom(size_type current_capacity,
+ size_type requested_capacity) {
+ // TODO(johnsoncj): Get rid of this old behavior.
+ size_type new_capacity = current_capacity;
+ while (new_capacity < requested_capacity) {
+ new_capacity *= 2;
+ }
+ return new_capacity;
+ }
+
+ using Metadata =
+ container_internal::CompressedTuple<allocator_type, size_type>;
+
+ struct Allocated {
+ pointer allocated_data;
+ size_type allocated_capacity;
+ };
+
+ struct Inlined {
+ using InlinedDataElement =
+ absl::aligned_storage_t<sizeof(value_type), alignof(value_type)>;
+ InlinedDataElement inlined_data[N];
+ };
+
+ union Data {
+ Allocated allocated;
+ Inlined inlined;
+ };
+
+ Metadata metadata_;
+ Data data_;
+};
+
+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);
+}
+
+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>
+template <typename ValueAdapter>
+auto Storage<T, N, A>::Resize(ValueAdapter values, size_type new_size) -> void {
+ StorageView storage_view = MakeStorageView();
+
+ AllocationTransaction allocation_tx(GetAllocPtr());
+ ConstructionTransaction construction_tx(GetAllocPtr());
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(storage_view.data));
+
+ absl::Span<value_type> construct_loop;
+ absl::Span<value_type> move_construct_loop;
+ absl::Span<value_type> destroy_loop;
+
+ if (new_size > storage_view.capacity) {
+ pointer new_data = allocation_tx.Allocate(
+ LegacyNextCapacityFrom(storage_view.capacity, new_size));
+
+ // Construct new objects in `new_data`
+ construct_loop = {new_data + storage_view.size,
+ new_size - storage_view.size};
+
+ // Move all existing objects into `new_data`
+ move_construct_loop = {new_data, storage_view.size};
+
+ // Destroy all existing objects in `storage_view.data`
+ destroy_loop = {storage_view.data, storage_view.size};
+ } else if (new_size > storage_view.size) {
+ // Construct new objects in `storage_view.data`
+ construct_loop = {storage_view.data + storage_view.size,
+ new_size - storage_view.size};
+ } else {
+ // Destroy end `storage_view.size - new_size` objects in `storage_view.data`
+ destroy_loop = {storage_view.data + new_size, storage_view.size - new_size};
+ }
+
+ construction_tx.Construct(construct_loop.data(), &values,
+ construct_loop.size());
+
+ inlined_vector_internal::ConstructElements(
+ GetAllocPtr(), move_construct_loop.data(), &move_values,
+ move_construct_loop.size());
+
+ inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(),
+ destroy_loop.size());
+
+ construction_tx.Commit();
+ if (allocation_tx.DidAllocate()) {
+ DeallocateIfAllocated();
+ AcquireAllocation(&allocation_tx);
+ SetIsAllocated();
+ }
+
+ SetSize(new_size);
+}
+
+template <typename T, size_t N, typename A>
+template <typename... Args>
+auto Storage<T, N, A>::EmplaceBack(Args&&... args) -> reference {
+ StorageView storage_view = MakeStorageView();
+
+ AllocationTransaction allocation_tx(GetAllocPtr());
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(storage_view.data));
+
+ pointer construct_data =
+ (storage_view.size == storage_view.capacity
+ ? allocation_tx.Allocate(NextCapacityFrom(storage_view.capacity))
+ : storage_view.data);
+
+ pointer last_ptr = construct_data + storage_view.size;
+ AllocatorTraits::construct(*GetAllocPtr(), last_ptr,
+ std::forward<Args>(args)...);
+
+ if (allocation_tx.DidAllocate()) {
+ ABSL_INTERNAL_TRY {
+ inlined_vector_internal::ConstructElements(
+ GetAllocPtr(), allocation_tx.GetData(), &move_values,
+ storage_view.size);
+ }
+ ABSL_INTERNAL_CATCH_ANY {
+ AllocatorTraits::destroy(*GetAllocPtr(), last_ptr);
+ ABSL_INTERNAL_RETHROW;
+ }
+
+ inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
+ storage_view.size);
+
+ DeallocateIfAllocated();
+ AcquireAllocation(&allocation_tx);
+ SetIsAllocated();
+ }
+
+ AddSize(1);
+ return *last_ptr;
+}
+
+template <typename T, size_t N, typename A>
+auto Storage<T, N, A>::Erase(const_iterator from, const_iterator to)
+ -> iterator {
+ assert(from != to);
+
+ StorageView storage_view = MakeStorageView();
+
+ size_type erase_size = std::distance(from, to);
+ size_type erase_index =
+ std::distance(const_iterator(storage_view.data), from);
+ size_type erase_end_index = erase_index + erase_size;
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(storage_view.data + erase_end_index));
+
+ inlined_vector_internal::AssignElements(storage_view.data + erase_index,
+ &move_values,
+ storage_view.size - erase_end_index);
+
+ inlined_vector_internal::DestroyElements(
+ GetAllocPtr(), storage_view.data + (storage_view.size - erase_size),
+ erase_size);
+
+ SubtractSize(erase_size);
+ return iterator(storage_view.data + erase_index);
+}
+
+template <typename T, size_t N, typename A>
+auto Storage<T, N, A>::Reserve(size_type requested_capacity) -> void {
+ StorageView storage_view = MakeStorageView();
+
+ if (ABSL_PREDICT_FALSE(requested_capacity <= storage_view.capacity)) return;
+
+ AllocationTransaction allocation_tx(GetAllocPtr());
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(storage_view.data));
+
+ pointer new_data = allocation_tx.Allocate(
+ LegacyNextCapacityFrom(storage_view.capacity, requested_capacity));
+
+ inlined_vector_internal::ConstructElements(GetAllocPtr(), new_data,
+ &move_values, storage_view.size);
+
+ inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
+ storage_view.size);
+
+ DeallocateIfAllocated();
+ AcquireAllocation(&allocation_tx);
+ SetIsAllocated();
+}
+
+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();
+ }
+}
+
+template <typename T, size_t N, typename A>
+auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
+ using std::swap;
+ assert(this != other_storage_ptr);
+
+ if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) {
+ // Both are allocated, thus we can swap the allocations at the top level.
+
+ swap(data_.allocated, other_storage_ptr->data_.allocated);
+ } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) {
+ // Both are inlined, thus element-wise swap up to smaller size, then move
+ // the remaining elements.
+
+ Storage* small_ptr = this;
+ Storage* large_ptr = other_storage_ptr;
+ if (small_ptr->GetSize() > large_ptr->GetSize()) swap(small_ptr, large_ptr);
+
+ for (size_type i = 0; i < small_ptr->GetSize(); ++i) {
+ swap(small_ptr->GetInlinedData()[i], large_ptr->GetInlinedData()[i]);
+ }
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(large_ptr->GetInlinedData() + small_ptr->GetSize()));
+
+ inlined_vector_internal::ConstructElements(
+ large_ptr->GetAllocPtr(),
+ small_ptr->GetInlinedData() + small_ptr->GetSize(), &move_values,
+ large_ptr->GetSize() - small_ptr->GetSize());
+
+ inlined_vector_internal::DestroyElements(
+ large_ptr->GetAllocPtr(),
+ large_ptr->GetInlinedData() + small_ptr->GetSize(),
+ large_ptr->GetSize() - small_ptr->GetSize());
+ } else {
+ // One is allocated and the other is inlined, thus we first move the
+ // elements from the inlined instance to the inlined space in the allocated
+ // instance and then we can finish by having the other vector take on the
+ // allocation.
+
+ Storage* allocated_ptr = this;
+ Storage* inlined_ptr = other_storage_ptr;
+ if (!allocated_ptr->GetIsAllocated()) swap(allocated_ptr, inlined_ptr);
+
+ StorageView allocated_storage_view{allocated_ptr->GetAllocatedData(),
+ allocated_ptr->GetSize(),
+ allocated_ptr->GetAllocatedCapacity()};
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(inlined_ptr->GetInlinedData()));
+
+ ABSL_INTERNAL_TRY {
+ inlined_vector_internal::ConstructElements(
+ inlined_ptr->GetAllocPtr(), allocated_ptr->GetInlinedData(),
+ &move_values, inlined_ptr->GetSize());
+ }
+ ABSL_INTERNAL_CATCH_ANY {
+ // Writing to inlined data will trample on the existing state, thus it
+ // needs to be restored when a construction fails.
+ allocated_ptr->SetAllocatedData(allocated_storage_view.data,
+ allocated_storage_view.capacity);
+ ABSL_INTERNAL_RETHROW;
+ }
+
+ inlined_vector_internal::DestroyElements(inlined_ptr->GetAllocPtr(),
+ inlined_ptr->GetInlinedData(),
+ inlined_ptr->GetSize());
+
+ inlined_ptr->SetAllocatedData(allocated_storage_view.data,
+ allocated_storage_view.capacity);
+ }
+
+ // All cases swap the size, `is_allocated` boolean and the allocator.
+ swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated());
+ swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr());
+}
+
+} // namespace inlined_vector_internal
+} // namespace absl
+
+#endif // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
git://repos.xcallymotion.com / motion2.git / blobdiff