1 // Copyright 2019 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
16 #define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
17
18 #include <algorithm>
19 #include <cstddef>
20 #include <cstring>
21 #include <iterator>
22 #include <limits>
23 #include <memory>
24 #include <utility>
25
26 #include "absl/base/macros.h"
27 #include "absl/container/internal/compressed_tuple.h"
28 #include "absl/memory/memory.h"
29 #include "absl/meta/type_traits.h"
30 #include "absl/types/span.h"
31
32 namespace absl {
33 ABSL_NAMESPACE_BEGIN
34 namespace inlined_vector_internal {
35
36 // GCC does not deal very well with the below code
37 #if !defined(__clang__) && defined(__GNUC__)
38 #pragma GCC diagnostic push
39 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
40 #endif
41
42 template <typename Iterator>
43 using IsAtLeastForwardIterator = std::is_convertible<
44 typename std::iterator_traits<Iterator>::iterator_category,
45 std::forward_iterator_tag>;
46
47 template <typename AllocatorType,
48 typename ValueType =
49 typename absl::allocator_traits<AllocatorType>::value_type>
50 using IsMemcpyOk =
51 absl::conjunction<std::is_same<AllocatorType, std::allocator<ValueType>>,
52 absl::is_trivially_copy_constructible<ValueType>,
53 absl::is_trivially_copy_assignable<ValueType>,
54 absl::is_trivially_destructible<ValueType>>;
55
56 template <typename AllocatorType, typename Pointer, typename SizeType>
DestroyElements(AllocatorType * alloc_ptr,Pointer destroy_first,SizeType destroy_size)57 void DestroyElements(AllocatorType* alloc_ptr, Pointer destroy_first,
58 SizeType destroy_size) {
59 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
60
61 if (destroy_first != nullptr) {
62 for (auto i = destroy_size; i != 0;) {
63 --i;
64 AllocatorTraits::destroy(*alloc_ptr, destroy_first + i);
65 }
66
67 #if !defined(NDEBUG)
68 {
69 using ValueType = typename AllocatorTraits::value_type;
70
71 // Overwrite unused memory with `0xab` so we can catch uninitialized
72 // usage.
73 //
74 // Cast to `void*` to tell the compiler that we don't care that we might
75 // be scribbling on a vtable pointer.
76 void* memory_ptr = destroy_first;
77 auto memory_size = destroy_size * sizeof(ValueType);
78 std::memset(memory_ptr, 0xab, memory_size);
79 }
80 #endif // !defined(NDEBUG)
81 }
82 }
83
84 // If kUseMemcpy is true, memcpy(dst, src, n); else do nothing.
85 // Useful to avoid compiler warnings when memcpy() is used for T values
86 // that are not trivially copyable in non-reachable code.
87 template <bool kUseMemcpy>
88 inline void MemcpyIfAllowed(void* dst, const void* src, size_t n);
89
90 // memcpy when allowed.
91 template <>
92 inline void MemcpyIfAllowed<true>(void* dst, const void* src, size_t n) {
93 memcpy(dst, src, n);
94 }
95
96 // Do nothing for types that are not memcpy-able. This function is only
97 // called from non-reachable branches.
98 template <>
99 inline void MemcpyIfAllowed<false>(void*, const void*, size_t) {}
100
101 template <typename AllocatorType, typename Pointer, typename ValueAdapter,
102 typename SizeType>
ConstructElements(AllocatorType * alloc_ptr,Pointer construct_first,ValueAdapter * values_ptr,SizeType construct_size)103 void ConstructElements(AllocatorType* alloc_ptr, Pointer construct_first,
104 ValueAdapter* values_ptr, SizeType construct_size) {
105 for (SizeType i = 0; i < construct_size; ++i) {
106 ABSL_INTERNAL_TRY {
107 values_ptr->ConstructNext(alloc_ptr, construct_first + i);
108 }
109 ABSL_INTERNAL_CATCH_ANY {
110 inlined_vector_internal::DestroyElements(alloc_ptr, construct_first, i);
111 ABSL_INTERNAL_RETHROW;
112 }
113 }
114 }
115
116 template <typename Pointer, typename ValueAdapter, typename SizeType>
AssignElements(Pointer assign_first,ValueAdapter * values_ptr,SizeType assign_size)117 void AssignElements(Pointer assign_first, ValueAdapter* values_ptr,
118 SizeType assign_size) {
119 for (SizeType i = 0; i < assign_size; ++i) {
120 values_ptr->AssignNext(assign_first + i);
121 }
122 }
123
124 template <typename AllocatorType>
125 struct StorageView {
126 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
127 using Pointer = typename AllocatorTraits::pointer;
128 using SizeType = typename AllocatorTraits::size_type;
129
130 Pointer data;
131 SizeType size;
132 SizeType capacity;
133 };
134
135 template <typename AllocatorType, typename Iterator>
136 class IteratorValueAdapter {
137 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
138 using Pointer = typename AllocatorTraits::pointer;
139
140 public:
IteratorValueAdapter(const Iterator & it)141 explicit IteratorValueAdapter(const Iterator& it) : it_(it) {}
142
ConstructNext(AllocatorType * alloc_ptr,Pointer construct_at)143 void ConstructNext(AllocatorType* alloc_ptr, Pointer construct_at) {
144 AllocatorTraits::construct(*alloc_ptr, construct_at, *it_);
145 ++it_;
146 }
147
AssignNext(Pointer assign_at)148 void AssignNext(Pointer assign_at) {
149 *assign_at = *it_;
150 ++it_;
151 }
152
153 private:
154 Iterator it_;
155 };
156
157 template <typename AllocatorType>
158 class CopyValueAdapter {
159 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
160 using ValueType = typename AllocatorTraits::value_type;
161 using Pointer = typename AllocatorTraits::pointer;
162 using ConstPointer = typename AllocatorTraits::const_pointer;
163
164 public:
CopyValueAdapter(const ValueType & v)165 explicit CopyValueAdapter(const ValueType& v) : ptr_(std::addressof(v)) {}
166
ConstructNext(AllocatorType * alloc_ptr,Pointer construct_at)167 void ConstructNext(AllocatorType* alloc_ptr, Pointer construct_at) {
168 AllocatorTraits::construct(*alloc_ptr, construct_at, *ptr_);
169 }
170
AssignNext(Pointer assign_at)171 void AssignNext(Pointer assign_at) { *assign_at = *ptr_; }
172
173 private:
174 ConstPointer ptr_;
175 };
176
177 template <typename AllocatorType>
178 class DefaultValueAdapter {
179 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
180 using ValueType = typename AllocatorTraits::value_type;
181 using Pointer = typename AllocatorTraits::pointer;
182
183 public:
DefaultValueAdapter()184 explicit DefaultValueAdapter() {}
185
ConstructNext(AllocatorType * alloc_ptr,Pointer construct_at)186 void ConstructNext(AllocatorType* alloc_ptr, Pointer construct_at) {
187 AllocatorTraits::construct(*alloc_ptr, construct_at);
188 }
189
AssignNext(Pointer assign_at)190 void AssignNext(Pointer assign_at) { *assign_at = ValueType(); }
191 };
192
193 template <typename AllocatorType>
194 class AllocationTransaction {
195 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
196 using Pointer = typename AllocatorTraits::pointer;
197 using SizeType = typename AllocatorTraits::size_type;
198
199 public:
AllocationTransaction(AllocatorType * alloc_ptr)200 explicit AllocationTransaction(AllocatorType* alloc_ptr)
201 : alloc_data_(*alloc_ptr, nullptr) {}
202
~AllocationTransaction()203 ~AllocationTransaction() {
204 if (DidAllocate()) {
205 AllocatorTraits::deallocate(GetAllocator(), GetData(), GetCapacity());
206 }
207 }
208
209 AllocationTransaction(const AllocationTransaction&) = delete;
210 void operator=(const AllocationTransaction&) = delete;
211
GetAllocator()212 AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); }
GetData()213 Pointer& GetData() { return alloc_data_.template get<1>(); }
GetCapacity()214 SizeType& GetCapacity() { return capacity_; }
215
DidAllocate()216 bool DidAllocate() { return GetData() != nullptr; }
Allocate(SizeType capacity)217 Pointer Allocate(SizeType capacity) {
218 GetData() = AllocatorTraits::allocate(GetAllocator(), capacity);
219 GetCapacity() = capacity;
220 return GetData();
221 }
222
Reset()223 void Reset() {
224 GetData() = nullptr;
225 GetCapacity() = 0;
226 }
227
228 private:
229 container_internal::CompressedTuple<AllocatorType, Pointer> alloc_data_;
230 SizeType capacity_ = 0;
231 };
232
233 template <typename AllocatorType>
234 class ConstructionTransaction {
235 using AllocatorTraits = absl::allocator_traits<AllocatorType>;
236 using Pointer = typename AllocatorTraits::pointer;
237 using SizeType = typename AllocatorTraits::size_type;
238
239 public:
ConstructionTransaction(AllocatorType * alloc_ptr)240 explicit ConstructionTransaction(AllocatorType* alloc_ptr)
241 : alloc_data_(*alloc_ptr, nullptr) {}
242
~ConstructionTransaction()243 ~ConstructionTransaction() {
244 if (DidConstruct()) {
245 inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()),
246 GetData(), GetSize());
247 }
248 }
249
250 ConstructionTransaction(const ConstructionTransaction&) = delete;
251 void operator=(const ConstructionTransaction&) = delete;
252
GetAllocator()253 AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); }
GetData()254 Pointer& GetData() { return alloc_data_.template get<1>(); }
GetSize()255 SizeType& GetSize() { return size_; }
256
DidConstruct()257 bool DidConstruct() { return GetData() != nullptr; }
258 template <typename ValueAdapter>
Construct(Pointer data,ValueAdapter * values_ptr,SizeType size)259 void Construct(Pointer data, ValueAdapter* values_ptr, SizeType size) {
260 inlined_vector_internal::ConstructElements(std::addressof(GetAllocator()),
261 data, values_ptr, size);
262 GetData() = data;
263 GetSize() = size;
264 }
Commit()265 void Commit() {
266 GetData() = nullptr;
267 GetSize() = 0;
268 }
269
270 private:
271 container_internal::CompressedTuple<AllocatorType, Pointer> alloc_data_;
272 SizeType size_ = 0;
273 };
274
275 template <typename T, size_t N, typename A>
276 class Storage {
277 public:
278 using AllocatorTraits = absl::allocator_traits<A>;
279 using allocator_type = typename AllocatorTraits::allocator_type;
280 using value_type = typename AllocatorTraits::value_type;
281 using pointer = typename AllocatorTraits::pointer;
282 using const_pointer = typename AllocatorTraits::const_pointer;
283 using size_type = typename AllocatorTraits::size_type;
284 using difference_type = typename AllocatorTraits::difference_type;
285
286 using reference = value_type&;
287 using const_reference = const value_type&;
288 using RValueReference = value_type&&;
289 using iterator = pointer;
290 using const_iterator = const_pointer;
291 using reverse_iterator = std::reverse_iterator<iterator>;
292 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
293 using MoveIterator = std::move_iterator<iterator>;
294 using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<allocator_type>;
295
296 using StorageView = inlined_vector_internal::StorageView<allocator_type>;
297
298 template <typename Iterator>
299 using IteratorValueAdapter =
300 inlined_vector_internal::IteratorValueAdapter<allocator_type, Iterator>;
301 using CopyValueAdapter =
302 inlined_vector_internal::CopyValueAdapter<allocator_type>;
303 using DefaultValueAdapter =
304 inlined_vector_internal::DefaultValueAdapter<allocator_type>;
305
306 using AllocationTransaction =
307 inlined_vector_internal::AllocationTransaction<allocator_type>;
308 using ConstructionTransaction =
309 inlined_vector_internal::ConstructionTransaction<allocator_type>;
310
NextCapacity(size_type current_capacity)311 static size_type NextCapacity(size_type current_capacity) {
312 return current_capacity * 2;
313 }
314
ComputeCapacity(size_type current_capacity,size_type requested_capacity)315 static size_type ComputeCapacity(size_type current_capacity,
316 size_type requested_capacity) {
317 return (std::max)(NextCapacity(current_capacity), requested_capacity);
318 }
319
320 // ---------------------------------------------------------------------------
321 // Storage Constructors and Destructor
322 // ---------------------------------------------------------------------------
323
Storage()324 Storage() : metadata_(allocator_type(), /* size and is_allocated */ 0) {}
325
Storage(const allocator_type & alloc)326 explicit Storage(const allocator_type& alloc)
327 : metadata_(alloc, /* size and is_allocated */ 0) {}
328
~Storage()329 ~Storage() {
330 if (GetSizeAndIsAllocated() == 0) {
331 // Empty and not allocated; nothing to do.
332 } else if (IsMemcpyOk::value) {
333 // No destructors need to be run; just deallocate if necessary.
334 DeallocateIfAllocated();
335 } else {
336 DestroyContents();
337 }
338 }
339
340 // ---------------------------------------------------------------------------
341 // Storage Member Accessors
342 // ---------------------------------------------------------------------------
343
GetSizeAndIsAllocated()344 size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
345
GetSizeAndIsAllocated()346 const size_type& GetSizeAndIsAllocated() const {
347 return metadata_.template get<1>();
348 }
349
GetSize()350 size_type GetSize() const { return GetSizeAndIsAllocated() >> 1; }
351
GetIsAllocated()352 bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; }
353
GetAllocatedData()354 pointer GetAllocatedData() { return data_.allocated.allocated_data; }
355
GetAllocatedData()356 const_pointer GetAllocatedData() const {
357 return data_.allocated.allocated_data;
358 }
359
GetInlinedData()360 pointer GetInlinedData() {
361 return reinterpret_cast<pointer>(
362 std::addressof(data_.inlined.inlined_data[0]));
363 }
364
GetInlinedData()365 const_pointer GetInlinedData() const {
366 return reinterpret_cast<const_pointer>(
367 std::addressof(data_.inlined.inlined_data[0]));
368 }
369
GetAllocatedCapacity()370 size_type GetAllocatedCapacity() const {
371 return data_.allocated.allocated_capacity;
372 }
373
GetInlinedCapacity()374 size_type GetInlinedCapacity() const { return static_cast<size_type>(N); }
375
MakeStorageView()376 StorageView MakeStorageView() {
377 return GetIsAllocated()
378 ? StorageView{GetAllocatedData(), GetSize(),
379 GetAllocatedCapacity()}
380 : StorageView{GetInlinedData(), GetSize(), GetInlinedCapacity()};
381 }
382
GetAllocPtr()383 allocator_type* GetAllocPtr() {
384 return std::addressof(metadata_.template get<0>());
385 }
386
GetAllocPtr()387 const allocator_type* GetAllocPtr() const {
388 return std::addressof(metadata_.template get<0>());
389 }
390
391 // ---------------------------------------------------------------------------
392 // Storage Member Mutators
393 // ---------------------------------------------------------------------------
394
395 ABSL_ATTRIBUTE_NOINLINE void InitFrom(const Storage& other);
396
397 template <typename ValueAdapter>
398 void Initialize(ValueAdapter values, size_type new_size);
399
400 template <typename ValueAdapter>
401 void Assign(ValueAdapter values, size_type new_size);
402
403 template <typename ValueAdapter>
404 void Resize(ValueAdapter values, size_type new_size);
405
406 template <typename ValueAdapter>
407 iterator Insert(const_iterator pos, ValueAdapter values,
408 size_type insert_count);
409
410 template <typename... Args>
411 reference EmplaceBack(Args&&... args);
412
413 iterator Erase(const_iterator from, const_iterator to);
414
415 void Reserve(size_type requested_capacity);
416
417 void ShrinkToFit();
418
419 void Swap(Storage* other_storage_ptr);
420
SetIsAllocated()421 void SetIsAllocated() {
422 GetSizeAndIsAllocated() |= static_cast<size_type>(1);
423 }
424
UnsetIsAllocated()425 void UnsetIsAllocated() {
426 GetSizeAndIsAllocated() &= ((std::numeric_limits<size_type>::max)() - 1);
427 }
428
SetSize(size_type size)429 void SetSize(size_type size) {
430 GetSizeAndIsAllocated() =
431 (size << 1) | static_cast<size_type>(GetIsAllocated());
432 }
433
SetAllocatedSize(size_type size)434 void SetAllocatedSize(size_type size) {
435 GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1);
436 }
437
SetInlinedSize(size_type size)438 void SetInlinedSize(size_type size) {
439 GetSizeAndIsAllocated() = size << static_cast<size_type>(1);
440 }
441
AddSize(size_type count)442 void AddSize(size_type count) {
443 GetSizeAndIsAllocated() += count << static_cast<size_type>(1);
444 }
445
SubtractSize(size_type count)446 void SubtractSize(size_type count) {
447 assert(count <= GetSize());
448
449 GetSizeAndIsAllocated() -= count << static_cast<size_type>(1);
450 }
451
SetAllocatedData(pointer data,size_type capacity)452 void SetAllocatedData(pointer data, size_type capacity) {
453 data_.allocated.allocated_data = data;
454 data_.allocated.allocated_capacity = capacity;
455 }
456
AcquireAllocatedData(AllocationTransaction * allocation_tx_ptr)457 void AcquireAllocatedData(AllocationTransaction* allocation_tx_ptr) {
458 SetAllocatedData(allocation_tx_ptr->GetData(),
459 allocation_tx_ptr->GetCapacity());
460
461 allocation_tx_ptr->Reset();
462 }
463
MemcpyFrom(const Storage & other_storage)464 void MemcpyFrom(const Storage& other_storage) {
465 assert(IsMemcpyOk::value || other_storage.GetIsAllocated());
466
467 GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated();
468 data_ = other_storage.data_;
469 }
470
DeallocateIfAllocated()471 void DeallocateIfAllocated() {
472 if (GetIsAllocated()) {
473 AllocatorTraits::deallocate(*GetAllocPtr(), GetAllocatedData(),
474 GetAllocatedCapacity());
475 }
476 }
477
478 private:
479 ABSL_ATTRIBUTE_NOINLINE void DestroyContents();
480
481 using Metadata =
482 container_internal::CompressedTuple<allocator_type, size_type>;
483
484 struct Allocated {
485 pointer allocated_data;
486 size_type allocated_capacity;
487 };
488
489 struct Inlined {
490 alignas(value_type) char inlined_data[sizeof(value_type[N])];
491 };
492
493 union Data {
494 Allocated allocated;
495 Inlined inlined;
496 };
497
498 template <typename... Args>
499 ABSL_ATTRIBUTE_NOINLINE reference EmplaceBackSlow(Args&&... args);
500
501 Metadata metadata_;
502 Data data_;
503 };
504
505 template <typename T, size_t N, typename A>
DestroyContents()506 void Storage<T, N, A>::DestroyContents() {
507 pointer data = GetIsAllocated() ? GetAllocatedData() : GetInlinedData();
508 inlined_vector_internal::DestroyElements(GetAllocPtr(), data, GetSize());
509 DeallocateIfAllocated();
510 }
511
512 template <typename T, size_t N, typename A>
InitFrom(const Storage & other)513 void Storage<T, N, A>::InitFrom(const Storage& other) {
514 const auto n = other.GetSize();
515 assert(n > 0); // Empty sources handled handled in caller.
516 const_pointer src;
517 pointer dst;
518 if (!other.GetIsAllocated()) {
519 dst = GetInlinedData();
520 src = other.GetInlinedData();
521 } else {
522 // Because this is only called from the `InlinedVector` constructors, it's
523 // safe to take on the allocation with size `0`. If `ConstructElements(...)`
524 // throws, deallocation will be automatically handled by `~Storage()`.
525 size_type new_capacity = ComputeCapacity(GetInlinedCapacity(), n);
526 dst = AllocatorTraits::allocate(*GetAllocPtr(), new_capacity);
527 SetAllocatedData(dst, new_capacity);
528 src = other.GetAllocatedData();
529 }
530 if (IsMemcpyOk::value) {
531 MemcpyIfAllowed<IsMemcpyOk::value>(dst, src, sizeof(dst[0]) * n);
532 } else {
533 auto values = IteratorValueAdapter<const_pointer>(src);
534 inlined_vector_internal::ConstructElements(GetAllocPtr(), dst, &values, n);
535 }
536 GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
537 }
538
539 template <typename T, size_t N, typename A>
540 template <typename ValueAdapter>
541 auto Storage<T, N, A>::Initialize(ValueAdapter values, size_type new_size)
542 -> void {
543 // Only callable from constructors!
544 assert(!GetIsAllocated());
545 assert(GetSize() == 0);
546
547 pointer construct_data;
548 if (new_size > GetInlinedCapacity()) {
549 // Because this is only called from the `InlinedVector` constructors, it's
550 // safe to take on the allocation with size `0`. If `ConstructElements(...)`
551 // throws, deallocation will be automatically handled by `~Storage()`.
552 size_type new_capacity = ComputeCapacity(GetInlinedCapacity(), new_size);
553 construct_data = AllocatorTraits::allocate(*GetAllocPtr(), new_capacity);
554 SetAllocatedData(construct_data, new_capacity);
555 SetIsAllocated();
556 } else {
557 construct_data = GetInlinedData();
558 }
559
560 inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data,
561 &values, new_size);
562
563 // Since the initial size was guaranteed to be `0` and the allocated bit is
564 // already correct for either case, *adding* `new_size` gives us the correct
565 // result faster than setting it directly.
566 AddSize(new_size);
567 }
568
569 template <typename T, size_t N, typename A>
570 template <typename ValueAdapter>
571 auto Storage<T, N, A>::Assign(ValueAdapter values, size_type new_size) -> void {
572 StorageView storage_view = MakeStorageView();
573
574 AllocationTransaction allocation_tx(GetAllocPtr());
575
576 absl::Span<value_type> assign_loop;
577 absl::Span<value_type> construct_loop;
578 absl::Span<value_type> destroy_loop;
579
580 if (new_size > storage_view.capacity) {
581 size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size);
582 construct_loop = {allocation_tx.Allocate(new_capacity), new_size};
583 destroy_loop = {storage_view.data, storage_view.size};
584 } else if (new_size > storage_view.size) {
585 assign_loop = {storage_view.data, storage_view.size};
586 construct_loop = {storage_view.data + storage_view.size,
587 new_size - storage_view.size};
588 } else {
589 assign_loop = {storage_view.data, new_size};
590 destroy_loop = {storage_view.data + new_size, storage_view.size - new_size};
591 }
592
593 inlined_vector_internal::AssignElements(assign_loop.data(), &values,
594 assign_loop.size());
595
596 inlined_vector_internal::ConstructElements(
597 GetAllocPtr(), construct_loop.data(), &values, construct_loop.size());
598
599 inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(),
600 destroy_loop.size());
601
602 if (allocation_tx.DidAllocate()) {
603 DeallocateIfAllocated();
604 AcquireAllocatedData(&allocation_tx);
605 SetIsAllocated();
606 }
607
608 SetSize(new_size);
609 }
610
611 template <typename T, size_t N, typename A>
612 template <typename ValueAdapter>
613 auto Storage<T, N, A>::Resize(ValueAdapter values, size_type new_size) -> void {
614 StorageView storage_view = MakeStorageView();
615 auto* const base = storage_view.data;
616 const size_type size = storage_view.size;
617 auto* alloc = GetAllocPtr();
618 if (new_size <= size) {
619 // Destroy extra old elements.
620 inlined_vector_internal::DestroyElements(alloc, base + new_size,
621 size - new_size);
622 } else if (new_size <= storage_view.capacity) {
623 // Construct new elements in place.
624 inlined_vector_internal::ConstructElements(alloc, base + size, &values,
625 new_size - size);
626 } else {
627 // Steps:
628 // a. Allocate new backing store.
629 // b. Construct new elements in new backing store.
630 // c. Move existing elements from old backing store to now.
631 // d. Destroy all elements in old backing store.
632 // Use transactional wrappers for the first two steps so we can roll
633 // back if necessary due to exceptions.
634 AllocationTransaction allocation_tx(alloc);
635 size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size);
636 pointer new_data = allocation_tx.Allocate(new_capacity);
637
638 ConstructionTransaction construction_tx(alloc);
639 construction_tx.Construct(new_data + size, &values, new_size - size);
640
641 IteratorValueAdapter<MoveIterator> move_values((MoveIterator(base)));
642 inlined_vector_internal::ConstructElements(alloc, new_data, &move_values,
643 size);
644
645 inlined_vector_internal::DestroyElements(alloc, base, size);
646 construction_tx.Commit();
647 DeallocateIfAllocated();
648 AcquireAllocatedData(&allocation_tx);
649 SetIsAllocated();
650 }
651 SetSize(new_size);
652 }
653
654 template <typename T, size_t N, typename A>
655 template <typename ValueAdapter>
656 auto Storage<T, N, A>::Insert(const_iterator pos, ValueAdapter values,
657 size_type insert_count) -> iterator {
658 StorageView storage_view = MakeStorageView();
659
660 size_type insert_index =
661 std::distance(const_iterator(storage_view.data), pos);
662 size_type insert_end_index = insert_index + insert_count;
663 size_type new_size = storage_view.size + insert_count;
664
665 if (new_size > storage_view.capacity) {
666 AllocationTransaction allocation_tx(GetAllocPtr());
667 ConstructionTransaction construction_tx(GetAllocPtr());
668 ConstructionTransaction move_construciton_tx(GetAllocPtr());
669
670 IteratorValueAdapter<MoveIterator> move_values(
671 MoveIterator(storage_view.data));
672
673 size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size);
674 pointer new_data = allocation_tx.Allocate(new_capacity);
675
676 construction_tx.Construct(new_data + insert_index, &values, insert_count);
677
678 move_construciton_tx.Construct(new_data, &move_values, insert_index);
679
680 inlined_vector_internal::ConstructElements(
681 GetAllocPtr(), new_data + insert_end_index, &move_values,
682 storage_view.size - insert_index);
683
684 inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
685 storage_view.size);
686
687 construction_tx.Commit();
688 move_construciton_tx.Commit();
689 DeallocateIfAllocated();
690 AcquireAllocatedData(&allocation_tx);
691
692 SetAllocatedSize(new_size);
693 return iterator(new_data + insert_index);
694 } else {
695 size_type move_construction_destination_index =
696 (std::max)(insert_end_index, storage_view.size);
697
698 ConstructionTransaction move_construction_tx(GetAllocPtr());
699
700 IteratorValueAdapter<MoveIterator> move_construction_values(
701 MoveIterator(storage_view.data +
702 (move_construction_destination_index - insert_count)));
703 absl::Span<value_type> move_construction = {
704 storage_view.data + move_construction_destination_index,
705 new_size - move_construction_destination_index};
706
707 pointer move_assignment_values = storage_view.data + insert_index;
708 absl::Span<value_type> move_assignment = {
709 storage_view.data + insert_end_index,
710 move_construction_destination_index - insert_end_index};
711
712 absl::Span<value_type> insert_assignment = {move_assignment_values,
713 move_construction.size()};
714
715 absl::Span<value_type> insert_construction = {
716 insert_assignment.data() + insert_assignment.size(),
717 insert_count - insert_assignment.size()};
718
719 move_construction_tx.Construct(move_construction.data(),
720 &move_construction_values,
721 move_construction.size());
722
723 for (pointer destination = move_assignment.data() + move_assignment.size(),
724 last_destination = move_assignment.data(),
725 source = move_assignment_values + move_assignment.size();
726 ;) {
727 --destination;
728 --source;
729 if (destination < last_destination) break;
730 *destination = std::move(*source);
731 }
732
733 inlined_vector_internal::AssignElements(insert_assignment.data(), &values,
734 insert_assignment.size());
735
736 inlined_vector_internal::ConstructElements(
737 GetAllocPtr(), insert_construction.data(), &values,
738 insert_construction.size());
739
740 move_construction_tx.Commit();
741
742 AddSize(insert_count);
743 return iterator(storage_view.data + insert_index);
744 }
745 }
746
747 template <typename T, size_t N, typename A>
748 template <typename... Args>
749 auto Storage<T, N, A>::EmplaceBack(Args&&... args) -> reference {
750 StorageView storage_view = MakeStorageView();
751 const auto n = storage_view.size;
752 if (ABSL_PREDICT_TRUE(n != storage_view.capacity)) {
753 // Fast path; new element fits.
754 pointer last_ptr = storage_view.data + n;
755 AllocatorTraits::construct(*GetAllocPtr(), last_ptr,
756 std::forward<Args>(args)...);
757 AddSize(1);
758 return *last_ptr;
759 }
760 // TODO(b/173712035): Annotate with musttail attribute to prevent regression.
761 return EmplaceBackSlow(std::forward<Args>(args)...);
762 }
763
764 template <typename T, size_t N, typename A>
765 template <typename... Args>
766 auto Storage<T, N, A>::EmplaceBackSlow(Args&&... args) -> reference {
767 StorageView storage_view = MakeStorageView();
768 AllocationTransaction allocation_tx(GetAllocPtr());
769 IteratorValueAdapter<MoveIterator> move_values(
770 MoveIterator(storage_view.data));
771 size_type new_capacity = NextCapacity(storage_view.capacity);
772 pointer construct_data = allocation_tx.Allocate(new_capacity);
773 pointer last_ptr = construct_data + storage_view.size;
774
775 // Construct new element.
776 AllocatorTraits::construct(*GetAllocPtr(), last_ptr,
777 std::forward<Args>(args)...);
778 // Move elements from old backing store to new backing store.
779 ABSL_INTERNAL_TRY {
780 inlined_vector_internal::ConstructElements(
781 GetAllocPtr(), allocation_tx.GetData(), &move_values,
782 storage_view.size);
783 }
784 ABSL_INTERNAL_CATCH_ANY {
785 AllocatorTraits::destroy(*GetAllocPtr(), last_ptr);
786 ABSL_INTERNAL_RETHROW;
787 }
788 // Destroy elements in old backing store.
789 inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
790 storage_view.size);
791
792 DeallocateIfAllocated();
793 AcquireAllocatedData(&allocation_tx);
794 SetIsAllocated();
795 AddSize(1);
796 return *last_ptr;
797 }
798
799 template <typename T, size_t N, typename A>
800 auto Storage<T, N, A>::Erase(const_iterator from, const_iterator to)
801 -> iterator {
802 StorageView storage_view = MakeStorageView();
803
804 size_type erase_size = std::distance(from, to);
805 size_type erase_index =
806 std::distance(const_iterator(storage_view.data), from);
807 size_type erase_end_index = erase_index + erase_size;
808
809 IteratorValueAdapter<MoveIterator> move_values(
810 MoveIterator(storage_view.data + erase_end_index));
811
812 inlined_vector_internal::AssignElements(storage_view.data + erase_index,
813 &move_values,
814 storage_view.size - erase_end_index);
815
816 inlined_vector_internal::DestroyElements(
817 GetAllocPtr(), storage_view.data + (storage_view.size - erase_size),
818 erase_size);
819
820 SubtractSize(erase_size);
821 return iterator(storage_view.data + erase_index);
822 }
823
824 template <typename T, size_t N, typename A>
825 auto Storage<T, N, A>::Reserve(size_type requested_capacity) -> void {
826 StorageView storage_view = MakeStorageView();
827
828 if (ABSL_PREDICT_FALSE(requested_capacity <= storage_view.capacity)) return;
829
830 AllocationTransaction allocation_tx(GetAllocPtr());
831
832 IteratorValueAdapter<MoveIterator> move_values(
833 MoveIterator(storage_view.data));
834
835 size_type new_capacity =
836 ComputeCapacity(storage_view.capacity, requested_capacity);
837 pointer new_data = allocation_tx.Allocate(new_capacity);
838
839 inlined_vector_internal::ConstructElements(GetAllocPtr(), new_data,
840 &move_values, storage_view.size);
841
842 inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
843 storage_view.size);
844
845 DeallocateIfAllocated();
846 AcquireAllocatedData(&allocation_tx);
847 SetIsAllocated();
848 }
849
850 template <typename T, size_t N, typename A>
851 auto Storage<T, N, A>::ShrinkToFit() -> void {
852 // May only be called on allocated instances!
853 assert(GetIsAllocated());
854
855 StorageView storage_view{GetAllocatedData(), GetSize(),
856 GetAllocatedCapacity()};
857
858 if (ABSL_PREDICT_FALSE(storage_view.size == storage_view.capacity)) return;
859
860 AllocationTransaction allocation_tx(GetAllocPtr());
861
862 IteratorValueAdapter<MoveIterator> move_values(
863 MoveIterator(storage_view.data));
864
865 pointer construct_data;
866 if (storage_view.size > GetInlinedCapacity()) {
867 size_type new_capacity = storage_view.size;
868 construct_data = allocation_tx.Allocate(new_capacity);
869 } else {
870 construct_data = GetInlinedData();
871 }
872
873 ABSL_INTERNAL_TRY {
874 inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data,
875 &move_values, storage_view.size);
876 }
877 ABSL_INTERNAL_CATCH_ANY {
878 SetAllocatedData(storage_view.data, storage_view.capacity);
879 ABSL_INTERNAL_RETHROW;
880 }
881
882 inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
883 storage_view.size);
884
885 AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
886 storage_view.capacity);
887
888 if (allocation_tx.DidAllocate()) {
889 AcquireAllocatedData(&allocation_tx);
890 } else {
891 UnsetIsAllocated();
892 }
893 }
894
895 template <typename T, size_t N, typename A>
896 auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
897 using std::swap;
898 assert(this != other_storage_ptr);
899
900 if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) {
901 swap(data_.allocated, other_storage_ptr->data_.allocated);
902 } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) {
903 Storage* small_ptr = this;
904 Storage* large_ptr = other_storage_ptr;
905 if (small_ptr->GetSize() > large_ptr->GetSize()) swap(small_ptr, large_ptr);
906
907 for (size_type i = 0; i < small_ptr->GetSize(); ++i) {
908 swap(small_ptr->GetInlinedData()[i], large_ptr->GetInlinedData()[i]);
909 }
910
911 IteratorValueAdapter<MoveIterator> move_values(
912 MoveIterator(large_ptr->GetInlinedData() + small_ptr->GetSize()));
913
914 inlined_vector_internal::ConstructElements(
915 large_ptr->GetAllocPtr(),
916 small_ptr->GetInlinedData() + small_ptr->GetSize(), &move_values,
917 large_ptr->GetSize() - small_ptr->GetSize());
918
919 inlined_vector_internal::DestroyElements(
920 large_ptr->GetAllocPtr(),
921 large_ptr->GetInlinedData() + small_ptr->GetSize(),
922 large_ptr->GetSize() - small_ptr->GetSize());
923 } else {
924 Storage* allocated_ptr = this;
925 Storage* inlined_ptr = other_storage_ptr;
926 if (!allocated_ptr->GetIsAllocated()) swap(allocated_ptr, inlined_ptr);
927
928 StorageView allocated_storage_view{allocated_ptr->GetAllocatedData(),
929 allocated_ptr->GetSize(),
930 allocated_ptr->GetAllocatedCapacity()};
931
932 IteratorValueAdapter<MoveIterator> move_values(
933 MoveIterator(inlined_ptr->GetInlinedData()));
934
935 ABSL_INTERNAL_TRY {
936 inlined_vector_internal::ConstructElements(
937 inlined_ptr->GetAllocPtr(), allocated_ptr->GetInlinedData(),
938 &move_values, inlined_ptr->GetSize());
939 }
940 ABSL_INTERNAL_CATCH_ANY {
941 allocated_ptr->SetAllocatedData(allocated_storage_view.data,
942 allocated_storage_view.capacity);
943 ABSL_INTERNAL_RETHROW;
944 }
945
946 inlined_vector_internal::DestroyElements(inlined_ptr->GetAllocPtr(),
947 inlined_ptr->GetInlinedData(),
948 inlined_ptr->GetSize());
949
950 inlined_ptr->SetAllocatedData(allocated_storage_view.data,
951 allocated_storage_view.capacity);
952 }
953
954 swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated());
955 swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr());
956 }
957
958 // End ignore "maybe-uninitialized"
959 #if !defined(__clang__) && defined(__GNUC__)
960 #pragma GCC diagnostic pop
961 #endif
962
963 } // namespace inlined_vector_internal
964 ABSL_NAMESPACE_END
965 } // namespace absl
966
967 #endif // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
968