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// -----------------------------------------------------------------------------
16// File: inlined_vector.h
17// -----------------------------------------------------------------------------
18//
19// This header file contains the declaration and definition of an "inlined
20// vector" which behaves in an equivalent fashion to a `std::vector`, except
21// that storage for small sequences of the vector are provided inline without
22// requiring any heap allocation.
23//
24// An `absl::InlinedVector<T, N>` specifies the default capacity `N` as one of
25// its template parameters. Instances where `size() <= N` hold contained
26// elements in inline space. Typically `N` is very small so that sequences that
27// are expected to be short do not require allocations.
28//
29// An `absl::InlinedVector` does not usually require a specific allocator. If
30// the inlined vector grows beyond its initial constraints, it will need to
31// allocate (as any normal `std::vector` would). This is usually performed with
32// the default allocator (defined as `std::allocator<T>`). Optionally, a custom
33// allocator type may be specified as `A` in `absl::InlinedVector<T, N, A>`.
34
35#ifndef ABSL_CONTAINER_INLINED_VECTOR_H_
36#define ABSL_CONTAINER_INLINED_VECTOR_H_
37
38#include <algorithm>
39#include <cassert>
40#include <cstddef>
41#include <cstdlib>
42#include <cstring>
43#include <initializer_list>
44#include <iterator>
45#include <memory>
46#include <type_traits>
47#include <utility>
48
49#include "absl/algorithm/algorithm.h"
50#include "absl/base/internal/throw_delegate.h"
51#include "absl/base/optimization.h"
52#include "absl/base/port.h"
53#include "absl/container/internal/inlined_vector.h"
54#include "absl/memory/memory.h"
55
56namespace absl {
57// -----------------------------------------------------------------------------
58// InlinedVector
59// -----------------------------------------------------------------------------
60//
61// An `absl::InlinedVector` is designed to be a drop-in replacement for
62// `std::vector` for use cases where the vector's size is sufficiently small
63// that it can be inlined. If the inlined vector does grow beyond its estimated
64// capacity, it will trigger an initial allocation on the heap, and will behave
65// as a `std:vector`. The API of the `absl::InlinedVector` within this file is
66// designed to cover the same API footprint as covered by `std::vector`.
67template <typename T, size_t N, typename A = std::allocator<T>>
68class InlinedVector {
69 static_assert(
70 N > 0, "InlinedVector cannot be instantiated with `0` inlined elements.");
71
72 using Storage = inlined_vector_internal::Storage<T, N, A>;
73 using rvalue_reference = typename Storage::rvalue_reference;
74 using MoveIterator = typename Storage::MoveIterator;
75 using AllocatorTraits = typename Storage::AllocatorTraits;
76 using IsMemcpyOk = typename Storage::IsMemcpyOk;
77
78 template <typename Iterator>
79 using IteratorValueAdapter =
80 typename Storage::template IteratorValueAdapter<Iterator>;
81 using CopyValueAdapter = typename Storage::CopyValueAdapter;
82 using DefaultValueAdapter = typename Storage::DefaultValueAdapter;
83
84 template <typename Iterator>
85 using EnableIfAtLeastForwardIterator = absl::enable_if_t<
86 inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>;
87
88 template <typename Iterator>
89 using DisableIfAtLeastForwardIterator = absl::enable_if_t<
90 !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>;
91
92 public:
93 using allocator_type = typename Storage::allocator_type;
94 using value_type = typename Storage::value_type;
95 using pointer = typename Storage::pointer;
96 using const_pointer = typename Storage::const_pointer;
97 using reference = typename Storage::reference;
98 using const_reference = typename Storage::const_reference;
99 using size_type = typename Storage::size_type;
100 using difference_type = typename Storage::difference_type;
101 using iterator = typename Storage::iterator;
102 using const_iterator = typename Storage::const_iterator;
103 using reverse_iterator = typename Storage::reverse_iterator;
104 using const_reverse_iterator = typename Storage::const_reverse_iterator;
105
106 // ---------------------------------------------------------------------------
107 // InlinedVector Constructors and Destructor
108 // ---------------------------------------------------------------------------
109
110 // Creates an empty inlined vector with a value-initialized allocator.
111 InlinedVector() noexcept(noexcept(allocator_type())) : storage_() {}
112
113 // Creates an empty inlined vector with a specified allocator.
114 explicit InlinedVector(const allocator_type& alloc) noexcept
115 : storage_(alloc) {}
116
117 // Creates an inlined vector with `n` copies of `value_type()`.
118 explicit InlinedVector(size_type n,
119 const allocator_type& alloc = allocator_type())
120 : storage_(alloc) {
121 storage_.Initialize(DefaultValueAdapter(), n);
122 }
123
124 // Creates an inlined vector with `n` copies of `v`.
125 InlinedVector(size_type n, const_reference v,
126 const allocator_type& alloc = allocator_type())
127 : storage_(alloc) {
128 storage_.Initialize(CopyValueAdapter(v), n);
129 }
130
131 // Creates an inlined vector of copies of the values in `list`.
132 InlinedVector(std::initializer_list<value_type> list,
133 const allocator_type& alloc = allocator_type())
134 : InlinedVector(list.begin(), list.end(), alloc) {}
135
136 // Creates an inlined vector with elements constructed from the provided
137 // forward iterator range [`first`, `last`).
138 //
139 // NOTE: The `enable_if` prevents ambiguous interpretation between a call to
140 // this constructor with two integral arguments and a call to the above
141 // `InlinedVector(size_type, const_reference)` constructor.
142 template <typename ForwardIterator,
143 EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr>
144 InlinedVector(ForwardIterator first, ForwardIterator last,
145 const allocator_type& alloc = allocator_type())
146 : storage_(alloc) {
147 storage_.Initialize(IteratorValueAdapter<ForwardIterator>(first),
148 std::distance(first, last));
149 }
150
151 // Creates an inlined vector with elements constructed from the provided input
152 // iterator range [`first`, `last`).
153 template <typename InputIterator,
154 DisableIfAtLeastForwardIterator<InputIterator>* = nullptr>
155 InlinedVector(InputIterator first, InputIterator last,
156 const allocator_type& alloc = allocator_type())
157 : storage_(alloc) {
158 std::copy(first, last, std::back_inserter(*this));
159 }
160
161 // Creates a copy of an `other` inlined vector using `other`'s allocator.
162 InlinedVector(const InlinedVector& other)
163 : InlinedVector(other, *other.storage_.GetAllocPtr()) {}
164
165 // Creates a copy of an `other` inlined vector using a specified allocator.
166 InlinedVector(const InlinedVector& other, const allocator_type& alloc)
167 : storage_(alloc) {
168 if (IsMemcpyOk::value && !other.storage_.GetIsAllocated()) {
169 storage_.MemcpyFrom(other.storage_);
170 } else {
171 storage_.Initialize(IteratorValueAdapter<const_pointer>(other.data()),
172 other.size());
173 }
174 }
175
176 // Creates an inlined vector by moving in the contents of an `other` inlined
177 // vector without performing any allocations. If `other` contains allocated
178 // memory, the newly-created instance will take ownership of that memory
179 // (leaving `other` empty). However, if `other` does not contain allocated
180 // memory (i.e. is inlined), the new inlined vector will perform element-wise
181 // move construction of `other`'s elements.
182 //
183 // NOTE: since no allocation is performed for the inlined vector in either
184 // case, the `noexcept(...)` specification depends on whether moving the
185 // underlying objects can throw. We assume:
186 // a) Move constructors should only throw due to allocation failure.
187 // b) If `value_type`'s move constructor allocates, it uses the same
188 // allocation function as the `InlinedVector`'s allocator. Thus, the move
189 // constructor is non-throwing if the allocator is non-throwing or
190 // `value_type`'s move constructor is specified as `noexcept`.
191 InlinedVector(InlinedVector&& other) noexcept(
192 absl::allocator_is_nothrow<allocator_type>::value ||
193 std::is_nothrow_move_constructible<value_type>::value)
194 : storage_(*other.storage_.GetAllocPtr()) {
195 if (IsMemcpyOk::value) {
196 storage_.MemcpyFrom(other.storage_);
197 other.storage_.SetInlinedSize(0);
198 } else if (other.storage_.GetIsAllocated()) {
199 storage_.SetAllocatedData(other.storage_.GetAllocatedData(),
200 other.storage_.GetAllocatedCapacity());
201 storage_.SetAllocatedSize(other.storage_.GetSize());
202 other.storage_.SetInlinedSize(0);
203 } else {
204 IteratorValueAdapter<MoveIterator> other_values(
205 MoveIterator(other.storage_.GetInlinedData()));
206 inlined_vector_internal::ConstructElements(
207 storage_.GetAllocPtr(), storage_.GetInlinedData(), &other_values,
208 other.storage_.GetSize());
209 storage_.SetInlinedSize(other.storage_.GetSize());
210 }
211 }
212
213 // Creates an inlined vector by moving in the contents of an `other` inlined
214 // vector, performing allocations with the specified `alloc` allocator. If
215 // `other`'s allocator is not equal to `alloc` and `other` contains allocated
216 // memory, this move constructor will create a new allocation.
217 //
218 // NOTE: since allocation is performed in this case, this constructor can
219 // only be `noexcept` if the specified allocator is also `noexcept`. If this
220 // is the case, or if `other` contains allocated memory, this constructor
221 // performs element-wise move construction of its contents.
222 //
223 // Only in the case where `other`'s allocator is equal to `alloc` and `other`
224 // contains allocated memory will the newly created inlined vector take
225 // ownership of `other`'s allocated memory.
226 InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
227 absl::allocator_is_nothrow<allocator_type>::value)
228 : storage_(alloc) {
229 if (IsMemcpyOk::value) {
230 storage_.MemcpyFrom(other.storage_);
231 other.storage_.SetInlinedSize(0);
232 } else if ((*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) &&
233 other.storage_.GetIsAllocated()) {
234 storage_.SetAllocatedData(other.storage_.GetAllocatedData(),
235 other.storage_.GetAllocatedCapacity());
236 storage_.SetAllocatedSize(other.storage_.GetSize());
237 other.storage_.SetInlinedSize(0);
238 } else {
239 storage_.Initialize(
240 IteratorValueAdapter<MoveIterator>(MoveIterator(other.data())),
241 other.size());
242 }
243 }
244
245 ~InlinedVector() {}
246
247 // ---------------------------------------------------------------------------
248 // InlinedVector Member Accessors
249 // ---------------------------------------------------------------------------
250
251 // `InlinedVector::empty()`
252 //
253 // Checks if the inlined vector has no elements.
254 bool empty() const noexcept { return !size(); }
255
256 // `InlinedVector::size()`
257 //
258 // Returns the number of elements in the inlined vector.
259 size_type size() const noexcept { return storage_.GetSize(); }
260
261 // `InlinedVector::max_size()`
262 //
263 // Returns the maximum number of elements the vector can hold.
264 size_type max_size() const noexcept {
265 // One bit of the size storage is used to indicate whether the inlined
266 // vector is allocated. As a result, the maximum size of the container that
267 // we can express is half of the max for `size_type`.
268 return (std::numeric_limits<size_type>::max)() / 2;
269 }
270
271 // `InlinedVector::capacity()`
272 //
273 // Returns the number of elements that can be stored in the inlined vector
274 // without requiring a reallocation of underlying memory.
275 //
276 // NOTE: For most inlined vectors, `capacity()` should equal the template
277 // parameter `N`. For inlined vectors which exceed this capacity, they
278 // will no longer be inlined and `capacity()` will equal its capacity on the
279 // allocated heap.
280 size_type capacity() const noexcept {
281 return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity()
282 : static_cast<size_type>(N);
283 }
284
285 // `InlinedVector::data()`
286 //
287 // Returns a `pointer` to elements of the inlined vector. This pointer can be
288 // used to access and modify the contained elements.
289 // Only results within the range [`0`, `size()`) are defined.
290 pointer data() noexcept {
291 return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
292 : storage_.GetInlinedData();
293 }
294
295 // Overload of `InlinedVector::data()` to return a `const_pointer` to elements
296 // of the inlined vector. This pointer can be used to access (but not modify)
297 // the contained elements.
298 const_pointer data() const noexcept {
299 return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
300 : storage_.GetInlinedData();
301 }
302
303 // `InlinedVector::operator[]()`
304 //
305 // Returns a `reference` to the `i`th element of the inlined vector using the
306 // array operator.
307 reference operator[](size_type i) {
308 assert(i < size());
309 return data()[i];
310 }
311
312 // Overload of `InlinedVector::operator[]()` to return a `const_reference` to
313 // the `i`th element of the inlined vector.
314 const_reference operator[](size_type i) const {
315 assert(i < size());
316 return data()[i];
317 }
318
319 // `InlinedVector::at()`
320 //
321 // Returns a `reference` to the `i`th element of the inlined vector.
322 reference at(size_type i) {
323 if (ABSL_PREDICT_FALSE(i >= size())) {
324 base_internal::ThrowStdOutOfRange(
325 "`InlinedVector::at(size_type)` failed bounds check");
326 }
327 return data()[i];
328 }
329
330 // Overload of `InlinedVector::at()` to return a `const_reference` to the
331 // `i`th element of the inlined vector.
332 const_reference at(size_type i) const {
333 if (ABSL_PREDICT_FALSE(i >= size())) {
334 base_internal::ThrowStdOutOfRange(
335 "`InlinedVector::at(size_type) const` failed bounds check");
336 }
337 return data()[i];
338 }
339
340 // `InlinedVector::front()`
341 //
342 // Returns a `reference` to the first element of the inlined vector.
343 reference front() {
344 assert(!empty());
345 return at(0);
346 }
347
348 // Overload of `InlinedVector::front()` returns a `const_reference` to the
349 // first element of the inlined vector.
350 const_reference front() const {
351 assert(!empty());
352 return at(0);
353 }
354
355 // `InlinedVector::back()`
356 //
357 // Returns a `reference` to the last element of the inlined vector.
358 reference back() {
359 assert(!empty());
360 return at(size() - 1);
361 }
362
363 // Overload of `InlinedVector::back()` to return a `const_reference` to the
364 // last element of the inlined vector.
365 const_reference back() const {
366 assert(!empty());
367 return at(size() - 1);
368 }
369
370 // `InlinedVector::begin()`
371 //
372 // Returns an `iterator` to the beginning of the inlined vector.
373 iterator begin() noexcept { return data(); }
374
375 // Overload of `InlinedVector::begin()` to return a `const_iterator` to
376 // the beginning of the inlined vector.
377 const_iterator begin() const noexcept { return data(); }
378
379 // `InlinedVector::end()`
380 //
381 // Returns an `iterator` to the end of the inlined vector.
382 iterator end() noexcept { return data() + size(); }
383
384 // Overload of `InlinedVector::end()` to return a `const_iterator` to the
385 // end of the inlined vector.
386 const_iterator end() const noexcept { return data() + size(); }
387
388 // `InlinedVector::cbegin()`
389 //
390 // Returns a `const_iterator` to the beginning of the inlined vector.
391 const_iterator cbegin() const noexcept { return begin(); }
392
393 // `InlinedVector::cend()`
394 //
395 // Returns a `const_iterator` to the end of the inlined vector.
396 const_iterator cend() const noexcept { return end(); }
397
398 // `InlinedVector::rbegin()`
399 //
400 // Returns a `reverse_iterator` from the end of the inlined vector.
401 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
402
403 // Overload of `InlinedVector::rbegin()` to return a
404 // `const_reverse_iterator` from the end of the inlined vector.
405 const_reverse_iterator rbegin() const noexcept {
406 return const_reverse_iterator(end());
407 }
408
409 // `InlinedVector::rend()`
410 //
411 // Returns a `reverse_iterator` from the beginning of the inlined vector.
412 reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
413
414 // Overload of `InlinedVector::rend()` to return a `const_reverse_iterator`
415 // from the beginning of the inlined vector.
416 const_reverse_iterator rend() const noexcept {
417 return const_reverse_iterator(begin());
418 }
419
420 // `InlinedVector::crbegin()`
421 //
422 // Returns a `const_reverse_iterator` from the end of the inlined vector.
423 const_reverse_iterator crbegin() const noexcept { return rbegin(); }
424
425 // `InlinedVector::crend()`
426 //
427 // Returns a `const_reverse_iterator` from the beginning of the inlined
428 // vector.
429 const_reverse_iterator crend() const noexcept { return rend(); }
430
431 // `InlinedVector::get_allocator()`
432 //
433 // Returns a copy of the allocator of the inlined vector.
434 allocator_type get_allocator() const { return *storage_.GetAllocPtr(); }
435
436 // ---------------------------------------------------------------------------
437 // InlinedVector Member Mutators
438 // ---------------------------------------------------------------------------
439
440 // `InlinedVector::operator=()`
441 //
442 // Replaces the contents of the inlined vector with copies of the elements in
443 // the provided `std::initializer_list`.
444 InlinedVector& operator=(std::initializer_list<value_type> list) {
445 assign(list.begin(), list.end());
446 return *this;
447 }
448
449 // Overload of `InlinedVector::operator=()` to replace the contents of the
450 // inlined vector with the contents of `other`.
451 InlinedVector& operator=(const InlinedVector& other) {
452 if (ABSL_PREDICT_TRUE(this != std::addressof(other))) {
453 const_pointer other_data = other.data();
454 assign(other_data, other_data + other.size());
455 }
456 return *this;
457 }
458
459 // Overload of `InlinedVector::operator=()` to replace the contents of the
460 // inlined vector with the contents of `other`.
461 //
462 // NOTE: As a result of calling this overload, `other` may be empty or it's
463 // contents may be left in a moved-from state.
464 InlinedVector& operator=(InlinedVector&& other) {
465 if (ABSL_PREDICT_FALSE(this == std::addressof(other))) return *this;
466
467 if (IsMemcpyOk::value || other.storage_.GetIsAllocated()) {
468 inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(),
469 size());
470 storage_.DeallocateIfAllocated();
471 storage_.MemcpyFrom(other.storage_);
472 other.storage_.SetInlinedSize(0);
473 } else {
474 storage_.Assign(IteratorValueAdapter<MoveIterator>(
475 MoveIterator(other.storage_.GetInlinedData())),
476 other.size());
477 }
478
479 return *this;
480 }
481
482 // `InlinedVector::assign()`
483 //
484 // Replaces the contents of the inlined vector with `n` copies of `v`.
485 void assign(size_type n, const_reference v) {
486 storage_.Assign(CopyValueAdapter(v), n);
487 }
488
489 // Overload of `InlinedVector::assign()` to replace the contents of the
490 // inlined vector with copies of the values in the provided
491 // `std::initializer_list`.
492 void assign(std::initializer_list<value_type> list) {
493 assign(list.begin(), list.end());
494 }
495
496 // Overload of `InlinedVector::assign()` to replace the contents of the
497 // inlined vector with the forward iterator range [`first`, `last`).
498 template <typename ForwardIterator,
499 EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr>
500 void assign(ForwardIterator first, ForwardIterator last) {
501 storage_.Assign(IteratorValueAdapter<ForwardIterator>(first),
502 std::distance(first, last));
503 }
504
505 // Overload of `InlinedVector::assign()` to replace the contents of the
506 // inlined vector with the input iterator range [`first`, `last`).
507 template <typename InputIterator,
508 DisableIfAtLeastForwardIterator<InputIterator>* = nullptr>
509 void assign(InputIterator first, InputIterator last) {
510 size_type i = 0;
511 for (; i < size() && first != last; ++i, static_cast<void>(++first)) {
512 at(i) = *first;
513 }
514
515 erase(data() + i, data() + size());
516
517 std::copy(first, last, std::back_inserter(*this));
518 }
519
520 // `InlinedVector::resize()`
521 //
522 // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
523 // the inlined vector's current size, extra elements are destroyed. If `n` is
524 // larger than the initial size, new elements are value-initialized.
525 void resize(size_type n) { storage_.Resize(DefaultValueAdapter(), n); }
526
527 // Overload of `InlinedVector::resize()` to resize the inlined vector to
528 // contain `n` elements where, if `n` is larger than `size()`, the new values
529 // will be copy-constructed from `v`.
530 void resize(size_type n, const_reference v) {
531 storage_.Resize(CopyValueAdapter(v), n);
532 }
533
534 // `InlinedVector::insert()`
535 //
536 // Copies `v` into `pos`, returning an `iterator` pointing to the newly
537 // inserted element.
538 iterator insert(const_iterator pos, const_reference v) {
539 return emplace(pos, v);
540 }
541
542 // Overload of `InlinedVector::insert()` for moving `v` into `pos`, returning
543 // an iterator pointing to the newly inserted element.
544 iterator insert(const_iterator pos, rvalue_reference v) {
545 return emplace(pos, std::move(v));
546 }
547
548 // Overload of `InlinedVector::insert()` for inserting `n` contiguous copies
549 // of `v` starting at `pos`. Returns an `iterator` pointing to the first of
550 // the newly inserted elements.
551 iterator insert(const_iterator pos, size_type n, const_reference v) {
552 assert(pos >= begin() && pos <= end());
553 if (ABSL_PREDICT_FALSE(n == 0)) {
554 return const_cast<iterator>(pos);
555 }
556 value_type copy = v;
557 std::pair<iterator, iterator> it_pair = ShiftRight(pos, n);
558 std::fill(it_pair.first, it_pair.second, copy);
559 UninitializedFill(it_pair.second, it_pair.first + n, copy);
560 return it_pair.first;
561 }
562
563 // Overload of `InlinedVector::insert()` for copying the contents of the
564 // `std::initializer_list` into the vector starting at `pos`. Returns an
565 // `iterator` pointing to the first of the newly inserted elements.
566 iterator insert(const_iterator pos, std::initializer_list<value_type> list) {
567 return insert(pos, list.begin(), list.end());
568 }
569
570 // Overload of `InlinedVector::insert()` for inserting elements constructed
571 // from the forward iterator range [`first`, `last`). Returns an `iterator`
572 // pointing to the first of the newly inserted elements.
573 //
574 // NOTE: The `enable_if` is intended to disambiguate the two three-argument
575 // overloads of `insert()`.
576 template <typename ForwardIterator,
577 EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr>
578 iterator insert(const_iterator pos, ForwardIterator first,
579 ForwardIterator last) {
580 assert(pos >= begin() && pos <= end());
581 if (ABSL_PREDICT_FALSE(first == last)) {
582 return const_cast<iterator>(pos);
583 }
584 auto n = std::distance(first, last);
585 std::pair<iterator, iterator> it_pair = ShiftRight(pos, n);
586 size_type used_spots = it_pair.second - it_pair.first;
587 auto open_spot = std::next(first, used_spots);
588 std::copy(first, open_spot, it_pair.first);
589 UninitializedCopy(open_spot, last, it_pair.second);
590 return it_pair.first;
591 }
592
593 // Overload of `InlinedVector::insert()` for inserting elements constructed
594 // from the input iterator range [`first`, `last`). Returns an `iterator`
595 // pointing to the first of the newly inserted elements.
596 template <typename InputIterator,
597 DisableIfAtLeastForwardIterator<InputIterator>* = nullptr>
598 iterator insert(const_iterator pos, InputIterator first, InputIterator last) {
599 assert(pos >= begin());
600 assert(pos <= end());
601
602 size_type index = std::distance(cbegin(), pos);
603 for (size_type i = index; first != last; ++i, static_cast<void>(++first)) {
604 insert(data() + i, *first);
605 }
606
607 return iterator(data() + index);
608 }
609
610 // `InlinedVector::emplace()`
611 //
612 // Constructs and inserts an object in the inlined vector at the given `pos`,
613 // returning an `iterator` pointing to the newly emplaced element.
614 template <typename... Args>
615 iterator emplace(const_iterator pos, Args&&... args) {
616 assert(pos >= begin());
617 assert(pos <= end());
618 if (ABSL_PREDICT_FALSE(pos == end())) {
619 emplace_back(std::forward<Args>(args)...);
620 return end() - 1;
621 }
622
623 T new_t = T(std::forward<Args>(args)...);
624
625 auto range = ShiftRight(pos, 1);
626 if (range.first == range.second) {
627 // constructing into uninitialized memory
628 Construct(range.first, std::move(new_t));
629 } else {
630 // assigning into moved-from object
631 *range.first = T(std::move(new_t));
632 }
633
634 return range.first;
635 }
636
637 // `InlinedVector::emplace_back()`
638 //
639 // Constructs and appends a new element to the end of the inlined vector,
640 // returning a `reference` to the emplaced element.
641 template <typename... Args>
642 reference emplace_back(Args&&... args) {
643 size_type s = size();
644 if (ABSL_PREDICT_FALSE(s == capacity())) {
645 size_type new_capacity = 2 * capacity();
646 pointer new_data =
647 AllocatorTraits::allocate(*storage_.GetAllocPtr(), new_capacity);
648 reference new_element =
649 Construct(new_data + s, std::forward<Args>(args)...);
650 UninitializedCopy(std::make_move_iterator(data()),
651 std::make_move_iterator(data() + s), new_data);
652 ResetAllocation(new_data, new_capacity, s + 1);
653 return new_element;
654 } else {
655 pointer space;
656 if (storage_.GetIsAllocated()) {
657 storage_.SetAllocatedSize(s + 1);
658 space = storage_.GetAllocatedData();
659 } else {
660 storage_.SetInlinedSize(s + 1);
661 space = storage_.GetInlinedData();
662 }
663 return Construct(space + s, std::forward<Args>(args)...);
664 }
665 }
666
667 // `InlinedVector::push_back()`
668 //
669 // Appends a copy of `v` to the end of the inlined vector.
670 void push_back(const_reference v) { static_cast<void>(emplace_back(v)); }
671
672 // Overload of `InlinedVector::push_back()` for moving `v` into a newly
673 // appended element.
674 void push_back(rvalue_reference v) {
675 static_cast<void>(emplace_back(std::move(v)));
676 }
677
678 // `InlinedVector::pop_back()`
679 //
680 // Destroys the element at the end of the inlined vector and shrinks the size
681 // by `1` (unless the inlined vector is empty, in which case this is a no-op).
682 void pop_back() noexcept {
683 assert(!empty());
684
685 AllocatorTraits::destroy(*storage_.GetAllocPtr(), data() + (size() - 1));
686 storage_.SubtractSize(1);
687 }
688
689 // `InlinedVector::erase()`
690 //
691 // Erases the element at `pos` of the inlined vector, returning an `iterator`
692 // pointing to the first element following the erased element.
693 //
694 // NOTE: May return the end iterator, which is not dereferencable.
695 iterator erase(const_iterator pos) {
696 assert(pos >= begin());
697 assert(pos < end());
698
699 iterator position = const_cast<iterator>(pos);
700 std::move(position + 1, end(), position);
701 pop_back();
702 return position;
703 }
704
705 // Overload of `InlinedVector::erase()` for erasing all elements in the
706 // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing
707 // to the first element following the range erased or the end iterator if `to`
708 // was the end iterator.
709 iterator erase(const_iterator from, const_iterator to) {
710 assert(begin() <= from);
711 assert(from <= to);
712 assert(to <= end());
713
714 iterator range_start = const_cast<iterator>(from);
715 iterator range_end = const_cast<iterator>(to);
716
717 size_type s = size();
718 ptrdiff_t erase_gap = std::distance(range_start, range_end);
719 if (erase_gap > 0) {
720 pointer space;
721 if (storage_.GetIsAllocated()) {
722 space = storage_.GetAllocatedData();
723 storage_.SetAllocatedSize(s - erase_gap);
724 } else {
725 space = storage_.GetInlinedData();
726 storage_.SetInlinedSize(s - erase_gap);
727 }
728 std::move(range_end, space + s, range_start);
729 Destroy(space + s - erase_gap, space + s);
730 }
731 return range_start;
732 }
733
734 // `InlinedVector::clear()`
735 //
736 // Destroys all elements in the inlined vector, sets the size of `0` and
737 // deallocates the heap allocation if the inlined vector was allocated.
738 void clear() noexcept {
739 inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(),
740 size());
741 storage_.DeallocateIfAllocated();
742 storage_.SetInlinedSize(0);
743 }
744
745 // `InlinedVector::reserve()`
746 //
747 // Enlarges the underlying representation of the inlined vector so it can hold
748 // at least `n` elements. This method does not change `size()` or the actual
749 // contents of the vector.
750 //
751 // NOTE: If `n` does not exceed `capacity()`, `reserve()` will have no
752 // effects. Otherwise, `reserve()` will reallocate, performing an n-time
753 // element-wise move of everything contained.
754 void reserve(size_type n) { storage_.Reserve(n); }
755
756 // `InlinedVector::shrink_to_fit()`
757 //
758 // Reduces memory usage by freeing unused memory. After this call, calls to
759 // `capacity()` will be equal to `max(N, size())`.
760 //
761 // If `size() <= N` and the elements are currently stored on the heap, they
762 // will be moved to the inlined storage and the heap memory will be
763 // deallocated.
764 //
765 // If `size() > N` and `size() < capacity()` the elements will be moved to a
766 // smaller heap allocation.
767 void shrink_to_fit() {
768 if (storage_.GetIsAllocated()) {
769 storage_.ShrinkToFit();
770 }
771 }
772
773 // `InlinedVector::swap()`
774 //
775 // Swaps the contents of this inlined vector with the contents of `other`.
776 void swap(InlinedVector& other) {
777 using std::swap;
778
779 if (ABSL_PREDICT_FALSE(this == std::addressof(other))) {
780 return;
781 }
782
783 bool is_allocated = storage_.GetIsAllocated();
784 bool other_is_allocated = other.storage_.GetIsAllocated();
785
786 if (is_allocated && other_is_allocated) {
787 // Both out of line, so just swap the tag, allocation, and allocator.
788 storage_.SwapSizeAndIsAllocated(std::addressof(other.storage_));
789 storage_.SwapAllocatedSizeAndCapacity(std::addressof(other.storage_));
790 swap(*storage_.GetAllocPtr(), *other.storage_.GetAllocPtr());
791
792 return;
793 }
794
795 if (!is_allocated && !other_is_allocated) {
796 // Both inlined: swap up to smaller size, then move remaining elements.
797 InlinedVector* a = this;
798 InlinedVector* b = std::addressof(other);
799 if (size() < other.size()) {
800 swap(a, b);
801 }
802
803 const size_type a_size = a->size();
804 const size_type b_size = b->size();
805 assert(a_size >= b_size);
806 // `a` is larger. Swap the elements up to the smaller array size.
807 std::swap_ranges(a->storage_.GetInlinedData(),
808 a->storage_.GetInlinedData() + b_size,
809 b->storage_.GetInlinedData());
810
811 // Move the remaining elements:
812 // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
813 b->UninitializedCopy(a->storage_.GetInlinedData() + b_size,
814 a->storage_.GetInlinedData() + a_size,
815 b->storage_.GetInlinedData() + b_size);
816 a->Destroy(a->storage_.GetInlinedData() + b_size,
817 a->storage_.GetInlinedData() + a_size);
818
819 storage_.SwapSizeAndIsAllocated(std::addressof(other.storage_));
820 swap(*storage_.GetAllocPtr(), *other.storage_.GetAllocPtr());
821
822 assert(b->size() == a_size);
823 assert(a->size() == b_size);
824 return;
825 }
826
827 // One is out of line, one is inline.
828 // We first move the elements from the inlined vector into the
829 // inlined space in the other vector. We then put the other vector's
830 // pointer/capacity into the originally inlined vector and swap
831 // the tags.
832 InlinedVector* a = this;
833 InlinedVector* b = std::addressof(other);
834 if (a->storage_.GetIsAllocated()) {
835 swap(a, b);
836 }
837
838 assert(!a->storage_.GetIsAllocated());
839 assert(b->storage_.GetIsAllocated());
840
841 const size_type a_size = a->size();
842 const size_type b_size = b->size();
843 // In an optimized build, `b_size` would be unused.
844 static_cast<void>(b_size);
845
846 // Made Local copies of `size()`, these can now be swapped
847 a->storage_.SwapSizeAndIsAllocated(std::addressof(b->storage_));
848
849 // Copy out before `b`'s union gets clobbered by `inline_space`
850 pointer b_data = b->storage_.GetAllocatedData();
851 size_type b_capacity = b->storage_.GetAllocatedCapacity();
852
853 b->UninitializedCopy(a->storage_.GetInlinedData(),
854 a->storage_.GetInlinedData() + a_size,
855 b->storage_.GetInlinedData());
856 a->Destroy(a->storage_.GetInlinedData(),
857 a->storage_.GetInlinedData() + a_size);
858
859 a->storage_.SetAllocatedData(b_data, b_capacity);
860
861 if (*a->storage_.GetAllocPtr() != *b->storage_.GetAllocPtr()) {
862 swap(*a->storage_.GetAllocPtr(), *b->storage_.GetAllocPtr());
863 }
864
865 assert(b->size() == a_size);
866 assert(a->size() == b_size);
867 }
868
869 private:
870 template <typename H, typename TheT, size_t TheN, typename TheA>
871 friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a);
872
873 void ResetAllocation(pointer new_data, size_type new_capacity,
874 size_type new_size) {
875 if (storage_.GetIsAllocated()) {
876 Destroy(storage_.GetAllocatedData(),
877 storage_.GetAllocatedData() + size());
878 assert(begin() == storage_.GetAllocatedData());
879 AllocatorTraits::deallocate(*storage_.GetAllocPtr(),
880 storage_.GetAllocatedData(),
881 storage_.GetAllocatedCapacity());
882 } else {
883 Destroy(storage_.GetInlinedData(), storage_.GetInlinedData() + size());
884 }
885
886 storage_.SetAllocatedData(new_data, new_capacity);
887 storage_.SetAllocatedSize(new_size);
888 }
889
890 template <typename... Args>
891 reference Construct(pointer p, Args&&... args) {
892 absl::allocator_traits<allocator_type>::construct(
893 *storage_.GetAllocPtr(), p, std::forward<Args>(args)...);
894 return *p;
895 }
896
897 template <typename Iterator>
898 void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
899 for (; src != src_last; ++dst, ++src) Construct(dst, *src);
900 }
901
902 template <typename... Args>
903 void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
904 for (; dst != dst_last; ++dst) Construct(dst, args...);
905 }
906
907 // Destroy [`from`, `to`) in place.
908 void Destroy(pointer from, pointer to) {
909 for (pointer cur = from; cur != to; ++cur) {
910 absl::allocator_traits<allocator_type>::destroy(*storage_.GetAllocPtr(),
911 cur);
912 }
913#if !defined(NDEBUG)
914 // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
915 // Cast to `void*` to tell the compiler that we don't care that we might be
916 // scribbling on a vtable pointer.
917 if (from != to) {
918 auto len = sizeof(value_type) * std::distance(from, to);
919 std::memset(reinterpret_cast<void*>(from), 0xab, len);
920 }
921#endif // !defined(NDEBUG)
922 }
923
924 // Shift all elements from `position` to `end()` by `n` places to the right.
925 // If the vector needs to be enlarged, memory will be allocated.
926 // Returns `iterator`s pointing to the start of the previously-initialized
927 // portion and the start of the uninitialized portion of the created gap.
928 // The number of initialized spots is `pair.second - pair.first`. The number
929 // of raw spots is `n - (pair.second - pair.first)`.
930 //
931 // Updates the size of the InlinedVector internally.
932 std::pair<iterator, iterator> ShiftRight(const_iterator position,
933 size_type n) {
934 iterator start_used = const_cast<iterator>(position);
935 iterator start_raw = const_cast<iterator>(position);
936 size_type s = size();
937 size_type required_size = s + n;
938
939 if (required_size > capacity()) {
940 // Compute new capacity by repeatedly doubling current capacity
941 size_type new_capacity = capacity();
942 while (new_capacity < required_size) {
943 new_capacity <<= 1;
944 }
945 // Move everyone into the new allocation, leaving a gap of `n` for the
946 // requested shift.
947 pointer new_data =
948 AllocatorTraits::allocate(*storage_.GetAllocPtr(), new_capacity);
949 size_type index = position - begin();
950 UninitializedCopy(std::make_move_iterator(data()),
951 std::make_move_iterator(data() + index), new_data);
952 UninitializedCopy(std::make_move_iterator(data() + index),
953 std::make_move_iterator(data() + s),
954 new_data + index + n);
955 ResetAllocation(new_data, new_capacity, s);
956
957 // New allocation means our iterator is invalid, so we'll recalculate.
958 // Since the entire gap is in new space, there's no used space to reuse.
959 start_raw = begin() + index;
960 start_used = start_raw;
961 } else {
962 // If we had enough space, it's a two-part move. Elements going into
963 // previously-unoccupied space need an `UninitializedCopy()`. Elements
964 // going into a previously-occupied space are just a `std::move()`.
965 iterator pos = const_cast<iterator>(position);
966 iterator raw_space = end();
967 size_type slots_in_used_space = raw_space - pos;
968 size_type new_elements_in_used_space = (std::min)(n, slots_in_used_space);
969 size_type new_elements_in_raw_space = n - new_elements_in_used_space;
970 size_type old_elements_in_used_space =
971 slots_in_used_space - new_elements_in_used_space;
972
973 UninitializedCopy(
974 std::make_move_iterator(pos + old_elements_in_used_space),
975 std::make_move_iterator(raw_space),
976 raw_space + new_elements_in_raw_space);
977 std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
978
979 // If the gap is entirely in raw space, the used space starts where the
980 // raw space starts, leaving no elements in used space. If the gap is
981 // entirely in used space, the raw space starts at the end of the gap,
982 // leaving all elements accounted for within the used space.
983 start_used = pos;
984 start_raw = pos + new_elements_in_used_space;
985 }
986 storage_.AddSize(n);
987 return std::make_pair(start_used, start_raw);
988 }
989
990 Storage storage_;
991};
992
993// -----------------------------------------------------------------------------
994// InlinedVector Non-Member Functions
995// -----------------------------------------------------------------------------
996
997// `swap()`
998//
999// Swaps the contents of two inlined vectors. This convenience function
1000// simply calls `InlinedVector::swap()`.
1001template <typename T, size_t N, typename A>
1002void swap(absl::InlinedVector<T, N, A>& a,
1003 absl::InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) {
1004 a.swap(b);
1005}
1006
1007// `operator==()`
1008//
1009// Tests the equivalency of the contents of two inlined vectors.
1010template <typename T, size_t N, typename A>
1011bool operator==(const absl::InlinedVector<T, N, A>& a,
1012 const absl::InlinedVector<T, N, A>& b) {
1013 auto a_data = a.data();
1014 auto a_size = a.size();
1015 auto b_data = b.data();
1016 auto b_size = b.size();
1017 return absl::equal(a_data, a_data + a_size, b_data, b_data + b_size);
1018}
1019
1020// `operator!=()`
1021//
1022// Tests the inequality of the contents of two inlined vectors.
1023template <typename T, size_t N, typename A>
1024bool operator!=(const absl::InlinedVector<T, N, A>& a,
1025 const absl::InlinedVector<T, N, A>& b) {
1026 return !(a == b);
1027}
1028
1029// `operator<()`
1030//
1031// Tests whether the contents of one inlined vector are less than the contents
1032// of another through a lexicographical comparison operation.
1033template <typename T, size_t N, typename A>
1034bool operator<(const absl::InlinedVector<T, N, A>& a,
1035 const absl::InlinedVector<T, N, A>& b) {
1036 auto a_data = a.data();
1037 auto a_size = a.size();
1038 auto b_data = b.data();
1039 auto b_size = b.size();
1040 return std::lexicographical_compare(a_data, a_data + a_size, b_data,
1041 b_data + b_size);
1042}
1043
1044// `operator>()`
1045//
1046// Tests whether the contents of one inlined vector are greater than the
1047// contents of another through a lexicographical comparison operation.
1048template <typename T, size_t N, typename A>
1049bool operator>(const absl::InlinedVector<T, N, A>& a,
1050 const absl::InlinedVector<T, N, A>& b) {
1051 return b < a;
1052}
1053
1054// `operator<=()`
1055//
1056// Tests whether the contents of one inlined vector are less than or equal to
1057// the contents of another through a lexicographical comparison operation.
1058template <typename T, size_t N, typename A>
1059bool operator<=(const absl::InlinedVector<T, N, A>& a,
1060 const absl::InlinedVector<T, N, A>& b) {
1061 return !(b < a);
1062}
1063
1064// `operator>=()`
1065//
1066// Tests whether the contents of one inlined vector are greater than or equal to
1067// the contents of another through a lexicographical comparison operation.
1068template <typename T, size_t N, typename A>
1069bool operator>=(const absl::InlinedVector<T, N, A>& a,
1070 const absl::InlinedVector<T, N, A>& b) {
1071 return !(a < b);
1072}
1073
1074// `AbslHashValue()`
1075//
1076// Provides `absl::Hash` support for `absl::InlinedVector`. You do not normally
1077// call this function directly.
1078template <typename H, typename TheT, size_t TheN, typename TheA>
1079H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a) {
1080 auto a_data = a.data();
1081 auto a_size = a.size();
1082 return H::combine(H::combine_contiguous(std::move(h), a_data, a_size),
1083 a_size);
1084}
1085
1086} // namespace absl
1087
1088#endif // ABSL_CONTAINER_INLINED_VECTOR_H_
1089