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