1 // Copyright 2018 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 // http://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 S2_THIRD_PARTY_ABSL_CONTAINER_INLINED_VECTOR_H_
36 #define S2_THIRD_PARTY_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 "s2/third_party/absl/algorithm/algorithm.h"
50 #include "s2/third_party/absl/base/internal/throw_delegate.h"
51 #include "s2/third_party/absl/base/optimization.h"
52 #include "s2/third_party/absl/base/port.h"
53 #include "s2/third_party/absl/memory/memory.h"
54
55
56 namespace absl {
57
58 // -----------------------------------------------------------------------------
59 // InlinedVector
60 // -----------------------------------------------------------------------------
61 //
62 // An `absl::InlinedVector` is designed to be a drop-in replacement for
63 // `std::vector` for use cases where the vector's size is sufficiently small
64 // that it can be inlined. If the inlined vector does grow beyond its estimated
65 // capacity, it will trigger an initial allocation on the heap, and will behave
66 // as a `std:vector`. The API of the `absl::InlinedVector` within this file is
67 // designed to cover the same API footprint as covered by `std::vector`.
68 template <typename T, size_t N, typename A = std::allocator<T>>
69 class InlinedVector {
70 static_assert(N > 0, "InlinedVector requires inline capacity greater than 0");
inlined_capacity()71 constexpr static typename A::size_type inlined_capacity() {
72 return static_cast<typename A::size_type>(N);
73 }
74
75 template <typename Iterator>
76 using DisableIfIntegral =
77 absl::enable_if_t<!std::is_integral<Iterator>::value>;
78
79 template <typename Iterator>
80 using EnableIfInputIterator = absl::enable_if_t<std::is_convertible<
81 typename std::iterator_traits<Iterator>::iterator_category,
82 std::input_iterator_tag>::value>;
83
84 template <typename Iterator>
85 using IteratorCategory =
86 typename std::iterator_traits<Iterator>::iterator_category;
87
88 using rvalue_reference = typename A::value_type&&;
89
90 public:
91 using allocator_type = A;
92 using value_type = typename allocator_type::value_type;
93 using pointer = typename allocator_type::pointer;
94 using const_pointer = typename allocator_type::const_pointer;
95 using reference = typename allocator_type::reference;
96 using const_reference = typename allocator_type::const_reference;
97 using size_type = typename allocator_type::size_type;
98 using difference_type = typename allocator_type::difference_type;
99 using iterator = pointer;
100 using const_iterator = const_pointer;
101 using reverse_iterator = std::reverse_iterator<iterator>;
102 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
103
104 // ---------------------------------------------------------------------------
105 // InlinedVector Constructors and Destructor
106 // ---------------------------------------------------------------------------
107
108 // Creates an empty inlined vector with a default initialized allocator.
noexcept(noexcept (allocator_type ()))109 InlinedVector() noexcept(noexcept(allocator_type()))
110 : allocator_and_tag_(allocator_type()) {}
111
112 // Creates an empty inlined vector with a specified allocator.
InlinedVector(const allocator_type & alloc)113 explicit InlinedVector(const allocator_type& alloc) noexcept
114 : allocator_and_tag_(alloc) {}
115
116 // Creates an inlined vector with `n` copies of `value_type()`.
117 explicit InlinedVector(size_type n,
118 const allocator_type& alloc = allocator_type())
allocator_and_tag_(alloc)119 : allocator_and_tag_(alloc) {
120 InitAssign(n);
121 }
122
123 // Creates an inlined vector with `n` copies of `v`.
124 InlinedVector(size_type n, const_reference v,
125 const allocator_type& alloc = allocator_type())
allocator_and_tag_(alloc)126 : allocator_and_tag_(alloc) {
127 InitAssign(n, v);
128 }
129
130 // Creates an inlined vector of copies of the values in `init_list`.
131 InlinedVector(std::initializer_list<value_type> init_list,
132 const allocator_type& alloc = allocator_type())
allocator_and_tag_(alloc)133 : allocator_and_tag_(alloc) {
134 AppendRange(init_list.begin(), init_list.end());
135 }
136
137 // Creates an inlined vector with elements constructed from the provided
138 // Iterator range [`first`, `last`).
139 //
140 // NOTE: The `enable_if` prevents ambiguous interpretation between a call to
141 // this constructor with two integral arguments and a call to the above
142 // `InlinedVector(size_type, const_reference)` constructor.
143 template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr>
144 InlinedVector(InputIterator first, InputIterator last,
145 const allocator_type& alloc = allocator_type())
allocator_and_tag_(alloc)146 : allocator_and_tag_(alloc) {
147 AppendRange(first, last);
148 }
149
150 // Creates a copy of `other` using `other`'s allocator.
151 InlinedVector(const InlinedVector& other);
152
153 // Creates a copy of `other` but with a specified allocator.
154 InlinedVector(const InlinedVector& other, const allocator_type& alloc);
155
156 // Creates an inlined vector by moving in the contents of `other`.
157 //
158 // NOTE: This move constructor does not allocate and only moves the underlying
159 // objects, so its `noexcept` specification depends on whether moving the
160 // underlying objects can throw or not. We assume:
161 // a) move constructors should only throw due to allocation failure and
162 // b) if `value_type`'s move constructor allocates, it uses the same
163 // allocation function as the `InlinedVector`'s allocator, so the move
164 // constructor is non-throwing if the allocator is non-throwing or
165 // `value_type`'s move constructor is specified as `noexcept`.
166 InlinedVector(InlinedVector&& v) noexcept(
167 absl::allocator_is_nothrow<allocator_type>::value ||
168 std::is_nothrow_move_constructible<value_type>::value);
169
170 // Creates an inlined vector by moving in the contents of `other`.
171 //
172 // NOTE: This move constructor allocates and subsequently moves the underlying
173 // objects, so its `noexcept` specification depends on whether the allocation
174 // can throw and whether moving the underlying objects can throw. Based on the
175 // same assumptions as above, the `noexcept` specification is dominated by
176 // whether the allocation can throw regardless of whether `value_type`'s move
177 // constructor is specified as `noexcept`.
178 InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept(
179 absl::allocator_is_nothrow<allocator_type>::value);
180
~InlinedVector()181 ~InlinedVector() { clear(); }
182
183 // ---------------------------------------------------------------------------
184 // InlinedVector Member Accessors
185 // ---------------------------------------------------------------------------
186
187 // `InlinedVector::empty()`
188 //
189 // Checks if the inlined vector has no elements.
empty()190 bool empty() const noexcept { return !size(); }
191
192 // `InlinedVector::size()`
193 //
194 // Returns the number of elements in the inlined vector.
size()195 size_type size() const noexcept { return tag().size(); }
196
197 // `InlinedVector::max_size()`
198 //
199 // Returns the maximum number of elements the vector can hold.
max_size()200 size_type max_size() const noexcept {
201 // One bit of the size storage is used to indicate whether the inlined
202 // vector is allocated. As a result, the maximum size of the container that
203 // we can express is half of the max for `size_type`.
204 return (std::numeric_limits<size_type>::max)() / 2;
205 }
206
207 // `InlinedVector::capacity()`
208 //
209 // Returns the number of elements that can be stored in the inlined vector
210 // without requiring a reallocation of underlying memory.
211 //
212 // NOTE: For most inlined vectors, `capacity()` should equal
213 // `inlined_capacity()`. For inlined vectors which exceed this capacity, they
214 // will no longer be inlined and `capacity()` will equal its capacity on the
215 // allocated heap.
capacity()216 size_type capacity() const noexcept {
217 return allocated() ? allocation().capacity() : inlined_capacity();
218 }
219
220 // `InlinedVector::data()`
221 //
222 // Returns a `pointer` to elements of the inlined vector. This pointer can be
223 // used to access and modify the contained elements.
224 // Only results within the range [`0`, `size()`) are defined.
data()225 pointer data() noexcept {
226 return allocated() ? allocated_space() : inlined_space();
227 }
228
229 // Overload of `InlinedVector::data()` to return a `const_pointer` to elements
230 // of the inlined vector. This pointer can be used to access (but not modify)
231 // the contained elements.
data()232 const_pointer data() const noexcept {
233 return allocated() ? allocated_space() : inlined_space();
234 }
235
236 // `InlinedVector::operator[]()`
237 //
238 // Returns a `reference` to the `i`th element of the inlined vector using the
239 // array operator.
240 reference operator[](size_type i) {
241 assert(i < size());
242 return data()[i];
243 }
244
245 // Overload of `InlinedVector::operator[]()` to return a `const_reference` to
246 // the `i`th element of the inlined vector.
247 const_reference operator[](size_type i) const {
248 assert(i < size());
249 return data()[i];
250 }
251
252 // `InlinedVector::at()`
253 //
254 // Returns a `reference` to the `i`th element of the inlined vector.
at(size_type i)255 reference at(size_type i) {
256 if (ABSL_PREDICT_FALSE(i >= size())) {
257 base_internal::ThrowStdOutOfRange(
258 "InlinedVector::at() failed bounds check");
259 }
260 return data()[i];
261 }
262
263 // Overload of `InlinedVector::at()` to return a `const_reference` to the
264 // `i`th element of the inlined vector.
at(size_type i)265 const_reference at(size_type i) const {
266 if (ABSL_PREDICT_FALSE(i >= size())) {
267 base_internal::ThrowStdOutOfRange(
268 "InlinedVector::at() failed bounds check");
269 }
270 return data()[i];
271 }
272
273 // `InlinedVector::front()`
274 //
275 // Returns a `reference` to the first element of the inlined vector.
front()276 reference front() {
277 assert(!empty());
278 return at(0);
279 }
280
281 // Overload of `InlinedVector::front()` returns a `const_reference` to the
282 // first element of the inlined vector.
front()283 const_reference front() const {
284 assert(!empty());
285 return at(0);
286 }
287
288 // `InlinedVector::back()`
289 //
290 // Returns a `reference` to the last element of the inlined vector.
back()291 reference back() {
292 assert(!empty());
293 return at(size() - 1);
294 }
295
296 // Overload of `InlinedVector::back()` to return a `const_reference` to the
297 // last element of the inlined vector.
back()298 const_reference back() const {
299 assert(!empty());
300 return at(size() - 1);
301 }
302
303 // `InlinedVector::begin()`
304 //
305 // Returns an `iterator` to the beginning of the inlined vector.
begin()306 iterator begin() noexcept { return data(); }
307
308 // Overload of `InlinedVector::begin()` to return a `const_iterator` to
309 // the beginning of the inlined vector.
begin()310 const_iterator begin() const noexcept { return data(); }
311
312 // `InlinedVector::end()`
313 //
314 // Returns an `iterator` to the end of the inlined vector.
end()315 iterator end() noexcept { return data() + size(); }
316
317 // Overload of `InlinedVector::end()` to return a `const_iterator` to the
318 // end of the inlined vector.
end()319 const_iterator end() const noexcept { return data() + size(); }
320
321 // `InlinedVector::cbegin()`
322 //
323 // Returns a `const_iterator` to the beginning of the inlined vector.
cbegin()324 const_iterator cbegin() const noexcept { return begin(); }
325
326 // `InlinedVector::cend()`
327 //
328 // Returns a `const_iterator` to the end of the inlined vector.
cend()329 const_iterator cend() const noexcept { return end(); }
330
331 // `InlinedVector::rbegin()`
332 //
333 // Returns a `reverse_iterator` from the end of the inlined vector.
rbegin()334 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
335
336 // Overload of `InlinedVector::rbegin()` to return a
337 // `const_reverse_iterator` from the end of the inlined vector.
rbegin()338 const_reverse_iterator rbegin() const noexcept {
339 return const_reverse_iterator(end());
340 }
341
342 // `InlinedVector::rend()`
343 //
344 // Returns a `reverse_iterator` from the beginning of the inlined vector.
rend()345 reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
346
347 // Overload of `InlinedVector::rend()` to return a `const_reverse_iterator`
348 // from the beginning of the inlined vector.
rend()349 const_reverse_iterator rend() const noexcept {
350 return const_reverse_iterator(begin());
351 }
352
353 // `InlinedVector::crbegin()`
354 //
355 // Returns a `const_reverse_iterator` from the end of the inlined vector.
crbegin()356 const_reverse_iterator crbegin() const noexcept { return rbegin(); }
357
358 // `InlinedVector::crend()`
359 //
360 // Returns a `const_reverse_iterator` from the beginning of the inlined
361 // vector.
crend()362 const_reverse_iterator crend() const noexcept { return rend(); }
363
364 // `InlinedVector::get_allocator()`
365 //
366 // Returns a copy of the allocator of the inlined vector.
get_allocator()367 allocator_type get_allocator() const { return allocator(); }
368
369
370 // ---------------------------------------------------------------------------
371 // InlinedVector Member Mutators
372 // ---------------------------------------------------------------------------
373
374 // `InlinedVector::operator=()`
375 //
376 // Replaces the contents of the inlined vector with copies of the elements in
377 // the provided `std::initializer_list`.
378 InlinedVector& operator=(std::initializer_list<value_type> init_list) {
379 AssignRange(init_list.begin(), init_list.end());
380 return *this;
381 }
382
383 // Overload of `InlinedVector::operator=()` to replace the contents of the
384 // inlined vector with the contents of `other`.
385 InlinedVector& operator=(const InlinedVector& other) {
386 if (ABSL_PREDICT_FALSE(this == &other)) return *this;
387
388 // Optimized to avoid reallocation.
389 // Prefer reassignment to copy construction for elements.
390 if (size() < other.size()) { // grow
391 reserve(other.size());
392 std::copy(other.begin(), other.begin() + size(), begin());
393 std::copy(other.begin() + size(), other.end(), std::back_inserter(*this));
394 } else { // maybe shrink
395 erase(begin() + other.size(), end());
396 std::copy(other.begin(), other.end(), begin());
397 }
398 return *this;
399 }
400
401 // Overload of `InlinedVector::operator=()` to replace the contents of the
402 // inlined vector with the contents of `other`.
403 //
404 // NOTE: As a result of calling this overload, `other` may be empty or it's
405 // contents may be left in a moved-from state.
406 InlinedVector& operator=(InlinedVector&& other) {
407 if (ABSL_PREDICT_FALSE(this == &other)) return *this;
408
409 if (other.allocated()) {
410 clear();
411 tag().set_allocated_size(other.size());
412 init_allocation(other.allocation());
413 other.tag() = Tag();
414 } else {
415 if (allocated()) clear();
416 // Both are inlined now.
417 if (size() < other.size()) {
418 auto mid = std::make_move_iterator(other.begin() + size());
419 std::copy(std::make_move_iterator(other.begin()), mid, begin());
420 UninitializedCopy(mid, std::make_move_iterator(other.end()), end());
421 } else {
422 auto new_end = std::copy(std::make_move_iterator(other.begin()),
423 std::make_move_iterator(other.end()), begin());
424 Destroy(new_end, end());
425 }
426 tag().set_inline_size(other.size());
427 }
428 return *this;
429 }
430
431 // `InlinedVector::assign()`
432 //
433 // Replaces the contents of the inlined vector with `n` copies of `v`.
assign(size_type n,const_reference v)434 void assign(size_type n, const_reference v) {
435 if (n <= size()) { // Possibly shrink
436 std::fill_n(begin(), n, v);
437 erase(begin() + n, end());
438 return;
439 }
440 // Grow
441 reserve(n);
442 std::fill_n(begin(), size(), v);
443 if (allocated()) {
444 UninitializedFill(allocated_space() + size(), allocated_space() + n, v);
445 tag().set_allocated_size(n);
446 } else {
447 UninitializedFill(inlined_space() + size(), inlined_space() + n, v);
448 tag().set_inline_size(n);
449 }
450 }
451
452 // Overload of `InlinedVector::assign()` to replace the contents of the
453 // inlined vector with copies of the values in the provided
454 // `std::initializer_list`.
assign(std::initializer_list<value_type> init_list)455 void assign(std::initializer_list<value_type> init_list) {
456 AssignRange(init_list.begin(), init_list.end());
457 }
458
459 // Overload of `InlinedVector::assign()` to replace the contents of the
460 // inlined vector with values constructed from the range [`first`, `last`).
461 template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr>
assign(InputIterator first,InputIterator last)462 void assign(InputIterator first, InputIterator last) {
463 AssignRange(first, last);
464 }
465
466 // `InlinedVector::resize()`
467 //
468 // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
469 // the inlined vector's current size, extra elements are destroyed. If `n` is
470 // larger than the initial size, new elements are value-initialized.
471 void resize(size_type n);
472
473 // Overload of `InlinedVector::resize()` to resize the inlined vector to
474 // contain `n` elements where, if `n` is larger than `size()`, the new values
475 // will be copy-constructed from `v`.
476 void resize(size_type n, const_reference v);
477
478 // `InlinedVector::insert()`
479 //
480 // Copies `v` into `position`, returning an `iterator` pointing to the newly
481 // inserted element.
insert(const_iterator position,const_reference v)482 iterator insert(const_iterator position, const_reference v) {
483 return emplace(position, v);
484 }
485
486 // Overload of `InlinedVector::insert()` for moving `v` into `position`,
487 // returning an iterator pointing to the newly inserted element.
insert(const_iterator position,rvalue_reference v)488 iterator insert(const_iterator position, rvalue_reference v) {
489 return emplace(position, std::move(v));
490 }
491
492 // Overload of `InlinedVector::insert()` for inserting `n` contiguous copies
493 // of `v` starting at `position`. Returns an `iterator` pointing to the first
494 // of the newly inserted elements.
insert(const_iterator position,size_type n,const_reference v)495 iterator insert(const_iterator position, size_type n, const_reference v) {
496 return InsertWithCount(position, n, v);
497 }
498
499 // Overload of `InlinedVector::insert()` for copying the contents of the
500 // `std::initializer_list` into the vector starting at `position`. Returns an
501 // `iterator` pointing to the first of the newly inserted elements.
insert(const_iterator position,std::initializer_list<value_type> init_list)502 iterator insert(const_iterator position,
503 std::initializer_list<value_type> init_list) {
504 return insert(position, init_list.begin(), init_list.end());
505 }
506
507 // Overload of `InlinedVector::insert()` for inserting elements constructed
508 // from the range [`first`, `last`). Returns an `iterator` pointing to the
509 // first of the newly inserted elements.
510 //
511 // NOTE: The `enable_if` is intended to disambiguate the two three-argument
512 // overloads of `insert()`.
513 template <typename InputIterator,
514 typename = EnableIfInputIterator<InputIterator>>
insert(const_iterator position,InputIterator first,InputIterator last)515 iterator insert(const_iterator position, InputIterator first,
516 InputIterator last) {
517 return InsertWithRange(position, first, last,
518 IteratorCategory<InputIterator>());
519 }
520
521 // `InlinedVector::emplace()`
522 //
523 // Constructs and inserts an object in the inlined vector at the given
524 // `position`, returning an `iterator` pointing to the newly emplaced element.
525 template <typename... Args>
526 iterator emplace(const_iterator position, Args&&... args);
527
528 // `InlinedVector::emplace_back()`
529 //
530 // Constructs and appends a new element to the end of the inlined vector,
531 // returning a `reference` to the emplaced element.
532 template <typename... Args>
emplace_back(Args &&...args)533 reference emplace_back(Args&&... args) {
534 size_type s = size();
535 assert(s <= capacity());
536 if (ABSL_PREDICT_FALSE(s == capacity())) {
537 return GrowAndEmplaceBack(std::forward<Args>(args)...);
538 }
539 assert(s < capacity());
540
541 pointer space;
542 if (allocated()) {
543 tag().set_allocated_size(s + 1);
544 space = allocated_space();
545 } else {
546 tag().set_inline_size(s + 1);
547 space = inlined_space();
548 }
549 return Construct(space + s, std::forward<Args>(args)...);
550 }
551
552 // `InlinedVector::push_back()`
553 //
554 // Appends a copy of `v` to the end of the inlined vector.
push_back(const_reference v)555 void push_back(const_reference v) { static_cast<void>(emplace_back(v)); }
556
557 // Overload of `InlinedVector::push_back()` for moving `v` into a newly
558 // appended element.
push_back(rvalue_reference v)559 void push_back(rvalue_reference v) {
560 static_cast<void>(emplace_back(std::move(v)));
561 }
562
563 // `InlinedVector::pop_back()`
564 //
565 // Destroys the element at the end of the inlined vector and shrinks the size
566 // by `1` (unless the inlined vector is empty, in which case this is a no-op).
pop_back()567 void pop_back() noexcept {
568 assert(!empty());
569 size_type s = size();
570 if (allocated()) {
571 Destroy(allocated_space() + s - 1, allocated_space() + s);
572 tag().set_allocated_size(s - 1);
573 } else {
574 Destroy(inlined_space() + s - 1, inlined_space() + s);
575 tag().set_inline_size(s - 1);
576 }
577 }
578
579 // `InlinedVector::erase()`
580 //
581 // Erases the element at `position` of the inlined vector, returning an
582 // `iterator` pointing to the first element following the erased element.
583 //
584 // NOTE: May return the end iterator, which is not dereferencable.
erase(const_iterator position)585 iterator erase(const_iterator position) {
586 assert(position >= begin());
587 assert(position < end());
588
589 iterator pos = const_cast<iterator>(position);
590 std::move(pos + 1, end(), pos);
591 pop_back();
592 return pos;
593 }
594
595 // Overload of `InlinedVector::erase()` for erasing all elements in the
596 // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing
597 // to the first element following the range erased or the end iterator if `to`
598 // was the end iterator.
599 iterator erase(const_iterator from, const_iterator to);
600
601 // `InlinedVector::clear()`
602 //
603 // Destroys all elements in the inlined vector, sets the size of `0` and
604 // deallocates the heap allocation if the inlined vector was allocated.
clear()605 void clear() noexcept {
606 size_type s = size();
607 if (allocated()) {
608 Destroy(allocated_space(), allocated_space() + s);
609 allocation().Dealloc(allocator());
610 } else if (s != 0) { // do nothing for empty vectors
611 Destroy(inlined_space(), inlined_space() + s);
612 }
613 tag() = Tag();
614 }
615
616 // `InlinedVector::reserve()`
617 //
618 // Enlarges the underlying representation of the inlined vector so it can hold
619 // at least `n` elements. This method does not change `size()` or the actual
620 // contents of the vector.
621 //
622 // NOTE: If `n` does not exceed `capacity()`, `reserve()` will have no
623 // effects. Otherwise, `reserve()` will reallocate, performing an n-time
624 // element-wise move of everything contained.
reserve(size_type n)625 void reserve(size_type n) {
626 if (n > capacity()) {
627 // Make room for new elements
628 EnlargeBy(n - size());
629 }
630 }
631
632 // `InlinedVector::shrink_to_fit()`
633 //
634 // Reduces memory usage by freeing unused memory. After this call, calls to
635 // `capacity()` will be equal to `(std::max)(inlined_capacity(), size())`.
636 //
637 // If `size() <= inlined_capacity()` and the elements are currently stored on
638 // the heap, they will be moved to the inlined storage and the heap memory
639 // will be deallocated.
640 //
641 // If `size() > inlined_capacity()` and `size() < capacity()` the elements
642 // will be moved to a smaller heap allocation.
shrink_to_fit()643 void shrink_to_fit() {
644 const auto s = size();
645 if (ABSL_PREDICT_FALSE(!allocated() || s == capacity())) return;
646
647 if (s <= inlined_capacity()) {
648 // Move the elements to the inlined storage.
649 // We have to do this using a temporary, because `inlined_storage` and
650 // `allocation_storage` are in a union field.
651 auto temp = std::move(*this);
652 assign(std::make_move_iterator(temp.begin()),
653 std::make_move_iterator(temp.end()));
654 return;
655 }
656
657 // Reallocate storage and move elements.
658 // We can't simply use the same approach as above, because `assign()` would
659 // call into `reserve()` internally and reserve larger capacity than we need
660 Allocation new_allocation(allocator(), s);
661 UninitializedCopy(std::make_move_iterator(allocated_space()),
662 std::make_move_iterator(allocated_space() + s),
663 new_allocation.buffer());
664 ResetAllocation(new_allocation, s);
665 }
666
667 // `InlinedVector::swap()`
668 //
669 // Swaps the contents of this inlined vector with the contents of `other`.
670 void swap(InlinedVector& other);
671
672 template <typename Hash>
AbslHashValue(Hash hash,const InlinedVector & inlined_vector)673 friend Hash AbslHashValue(Hash hash, const InlinedVector& inlined_vector) {
674 const_pointer p = inlined_vector.data();
675 size_type n = inlined_vector.size();
676 return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n);
677 }
678
679 private:
680 // Holds whether the vector is allocated or not in the lowest bit and the size
681 // in the high bits:
682 // `size_ = (size << 1) | is_allocated;`
683 class Tag {
684 public:
Tag()685 Tag() : size_(0) {}
size()686 size_type size() const { return size_ / 2; }
add_size(size_type n)687 void add_size(size_type n) { size_ += n * 2; }
set_inline_size(size_type n)688 void set_inline_size(size_type n) { size_ = n * 2; }
set_allocated_size(size_type n)689 void set_allocated_size(size_type n) { size_ = (n * 2) + 1; }
allocated()690 bool allocated() const { return size_ % 2; }
691
692 private:
693 size_type size_;
694 };
695
696 // Derives from `allocator_type` to use the empty base class optimization.
697 // If the `allocator_type` is stateless, we can store our instance for free.
698 class AllocatorAndTag : private allocator_type {
699 public:
AllocatorAndTag(const allocator_type & a)700 explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {}
701
tag()702 Tag& tag() { return tag_; }
tag()703 const Tag& tag() const { return tag_; }
704
allocator()705 allocator_type& allocator() { return *this; }
allocator()706 const allocator_type& allocator() const { return *this; }
707
708 private:
709 Tag tag_;
710 };
711
712 class Allocation {
713 public:
Allocation(allocator_type & a,size_type capacity)714 Allocation(allocator_type& a, size_type capacity)
715 : capacity_(capacity), buffer_(Create(a, capacity)) {}
716
Dealloc(allocator_type & a)717 void Dealloc(allocator_type& a) {
718 std::allocator_traits<allocator_type>::deallocate(a, buffer_, capacity_);
719 }
720
capacity()721 size_type capacity() const { return capacity_; }
722
buffer()723 const_pointer buffer() const { return buffer_; }
724
buffer()725 pointer buffer() { return buffer_; }
726
727 private:
Create(allocator_type & a,size_type n)728 static pointer Create(allocator_type& a, size_type n) {
729 return std::allocator_traits<allocator_type>::allocate(a, n);
730 }
731
732 size_type capacity_;
733 pointer buffer_;
734 };
735
tag()736 const Tag& tag() const { return allocator_and_tag_.tag(); }
737
tag()738 Tag& tag() { return allocator_and_tag_.tag(); }
739
allocation()740 Allocation& allocation() {
741 return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation);
742 }
743
allocation()744 const Allocation& allocation() const {
745 return reinterpret_cast<const Allocation&>(
746 rep_.allocation_storage.allocation);
747 }
748
init_allocation(const Allocation & allocation)749 void init_allocation(const Allocation& allocation) {
750 new (&rep_.allocation_storage.allocation) Allocation(allocation);
751 }
752
753 // TODO(absl-team): investigate whether the reinterpret_cast is appropriate.
inlined_space()754 pointer inlined_space() {
755 return reinterpret_cast<pointer>(
756 std::addressof(rep_.inlined_storage.inlined[0]));
757 }
758
inlined_space()759 const_pointer inlined_space() const {
760 return reinterpret_cast<const_pointer>(
761 std::addressof(rep_.inlined_storage.inlined[0]));
762 }
763
allocated_space()764 pointer allocated_space() { return allocation().buffer(); }
765
allocated_space()766 const_pointer allocated_space() const { return allocation().buffer(); }
767
allocator()768 const allocator_type& allocator() const {
769 return allocator_and_tag_.allocator();
770 }
771
allocator()772 allocator_type& allocator() { return allocator_and_tag_.allocator(); }
773
allocated()774 bool allocated() const { return tag().allocated(); }
775
776 // Enlarge the underlying representation so we can store `size_ + delta` elems
777 // in allocated space. The size is not changed, and any newly added memory is
778 // not initialized.
779 void EnlargeBy(size_type delta);
780
781 // Shift all elements from `position` to `end()` by `n` places to the right.
782 // If the vector needs to be enlarged, memory will be allocated.
783 // Returns `iterator`s pointing to the start of the previously-initialized
784 // portion and the start of the uninitialized portion of the created gap.
785 // The number of initialized spots is `pair.second - pair.first`. The number
786 // of raw spots is `n - (pair.second - pair.first)`.
787 //
788 // Updates the size of the InlinedVector internally.
789 std::pair<iterator, iterator> ShiftRight(const_iterator position,
790 size_type n);
791
ResetAllocation(Allocation new_allocation,size_type new_size)792 void ResetAllocation(Allocation new_allocation, size_type new_size) {
793 if (allocated()) {
794 Destroy(allocated_space(), allocated_space() + size());
795 assert(begin() == allocated_space());
796 allocation().Dealloc(allocator());
797 allocation() = new_allocation;
798 } else {
799 Destroy(inlined_space(), inlined_space() + size());
800 init_allocation(new_allocation); // bug: only init once
801 }
802 tag().set_allocated_size(new_size);
803 }
804
805 template <typename... Args>
GrowAndEmplaceBack(Args &&...args)806 reference GrowAndEmplaceBack(Args&&... args) {
807 assert(size() == capacity());
808 const size_type s = size();
809
810 Allocation new_allocation(allocator(), 2 * capacity());
811
812 reference new_element =
813 Construct(new_allocation.buffer() + s, std::forward<Args>(args)...);
814 UninitializedCopy(std::make_move_iterator(data()),
815 std::make_move_iterator(data() + s),
816 new_allocation.buffer());
817
818 ResetAllocation(new_allocation, s + 1);
819
820 return new_element;
821 }
822
823 void InitAssign(size_type n);
824
825 void InitAssign(size_type n, const_reference v);
826
827 template <typename... Args>
Construct(pointer p,Args &&...args)828 reference Construct(pointer p, Args&&... args) {
829 std::allocator_traits<allocator_type>::construct(
830 allocator(), p, std::forward<Args>(args)...);
831 return *p;
832 }
833
834 template <typename Iterator>
UninitializedCopy(Iterator src,Iterator src_last,pointer dst)835 void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
836 for (; src != src_last; ++dst, ++src) Construct(dst, *src);
837 }
838
839 template <typename... Args>
UninitializedFill(pointer dst,pointer dst_last,const Args &...args)840 void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
841 for (; dst != dst_last; ++dst) Construct(dst, args...);
842 }
843
844 // Destroy [`from`, `to`) in place.
845 void Destroy(pointer from, pointer to);
846
847 template <typename Iterator>
AppendRange(Iterator first,Iterator last,std::input_iterator_tag)848 void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) {
849 std::copy(first, last, std::back_inserter(*this));
850 }
851
852 template <typename Iterator>
853 void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag);
854
855 template <typename Iterator>
AppendRange(Iterator first,Iterator last)856 void AppendRange(Iterator first, Iterator last) {
857 AppendRange(first, last, IteratorCategory<Iterator>());
858 }
859
860 template <typename Iterator>
861 void AssignRange(Iterator first, Iterator last, std::input_iterator_tag);
862
863 template <typename Iterator>
864 void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag);
865
866 template <typename Iterator>
AssignRange(Iterator first,Iterator last)867 void AssignRange(Iterator first, Iterator last) {
868 AssignRange(first, last, IteratorCategory<Iterator>());
869 }
870
871 iterator InsertWithCount(const_iterator position, size_type n,
872 const_reference v);
873
874 template <typename InputIterator>
875 iterator InsertWithRange(const_iterator position, InputIterator first,
876 InputIterator last, std::input_iterator_tag);
877
878 template <typename ForwardIterator>
879 iterator InsertWithRange(const_iterator position, ForwardIterator first,
880 ForwardIterator last, std::forward_iterator_tag);
881
882 // Stores either the inlined or allocated representation
883 union Rep {
884 using ValueTypeBuffer =
885 absl::aligned_storage_t<sizeof(value_type), alignof(value_type)>;
886 using AllocationBuffer =
887 absl::aligned_storage_t<sizeof(Allocation), alignof(Allocation)>;
888
889 // Structs wrap the buffers to perform indirection that solves a bizarre
890 // compilation error on Visual Studio (all known versions).
891 struct InlinedRep {
892 // `N` used in place of `inlined_capacity()` due to b/119696660
893 ValueTypeBuffer inlined[N];
894 };
895 struct AllocatedRep {
896 AllocationBuffer allocation;
897 };
898
899 InlinedRep inlined_storage;
900 AllocatedRep allocation_storage;
901 };
902
903 AllocatorAndTag allocator_and_tag_;
904 Rep rep_;
905 };
906
907 // -----------------------------------------------------------------------------
908 // InlinedVector Non-Member Functions
909 // -----------------------------------------------------------------------------
910
911 // `swap()`
912 //
913 // Swaps the contents of two inlined vectors. This convenience function
914 // simply calls `InlinedVector::swap()`.
915 template <typename T, size_t N, typename A>
swap(InlinedVector<T,N,A> & a,InlinedVector<T,N,A> & b)916 void swap(InlinedVector<T, N, A>& a,
917 InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) {
918 a.swap(b);
919 }
920
921 // `operator==()`
922 //
923 // Tests the equivalency of the contents of two inlined vectors.
924 template <typename T, size_t N, typename A>
925 bool operator==(const InlinedVector<T, N, A>& a,
926 const InlinedVector<T, N, A>& b) {
927 return absl::equal(a.begin(), a.end(), b.begin(), b.end());
928 }
929
930 // `operator!=()`
931 //
932 // Tests the inequality of the contents of two inlined vectors.
933 template <typename T, size_t N, typename A>
934 bool operator!=(const InlinedVector<T, N, A>& a,
935 const InlinedVector<T, N, A>& b) {
936 return !(a == b);
937 }
938
939 // `operator<()`
940 //
941 // Tests whether the contents of one inlined vector are less than the contents
942 // of another through a lexicographical comparison operation.
943 template <typename T, size_t N, typename A>
944 bool operator<(const InlinedVector<T, N, A>& a,
945 const InlinedVector<T, N, A>& b) {
946 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
947 }
948
949 // `operator>()`
950 //
951 // Tests whether the contents of one inlined vector are greater than the
952 // contents of another through a lexicographical comparison operation.
953 template <typename T, size_t N, typename A>
954 bool operator>(const InlinedVector<T, N, A>& a,
955 const InlinedVector<T, N, A>& b) {
956 return b < a;
957 }
958
959 // `operator<=()`
960 //
961 // Tests whether the contents of one inlined vector are less than or equal to
962 // the contents of another through a lexicographical comparison operation.
963 template <typename T, size_t N, typename A>
964 bool operator<=(const InlinedVector<T, N, A>& a,
965 const InlinedVector<T, N, A>& b) {
966 return !(b < a);
967 }
968
969 // `operator>=()`
970 //
971 // Tests whether the contents of one inlined vector are greater than or equal to
972 // the contents of another through a lexicographical comparison operation.
973 template <typename T, size_t N, typename A>
974 bool operator>=(const InlinedVector<T, N, A>& a,
975 const InlinedVector<T, N, A>& b) {
976 return !(a < b);
977 }
978
979 // -----------------------------------------------------------------------------
980 // Implementation of InlinedVector
981 //
982 // Do not depend on any below implementation details!
983 // -----------------------------------------------------------------------------
984
985 template <typename T, size_t N, typename A>
InlinedVector(const InlinedVector & other)986 InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other)
987 : allocator_and_tag_(other.allocator()) {
988 reserve(other.size());
989 if (allocated()) {
990 UninitializedCopy(other.begin(), other.end(), allocated_space());
991 tag().set_allocated_size(other.size());
992 } else {
993 UninitializedCopy(other.begin(), other.end(), inlined_space());
994 tag().set_inline_size(other.size());
995 }
996 }
997
998 template <typename T, size_t N, typename A>
InlinedVector(const InlinedVector & other,const allocator_type & alloc)999 InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other,
1000 const allocator_type& alloc)
1001 : allocator_and_tag_(alloc) {
1002 reserve(other.size());
1003 if (allocated()) {
1004 UninitializedCopy(other.begin(), other.end(), allocated_space());
1005 tag().set_allocated_size(other.size());
1006 } else {
1007 UninitializedCopy(other.begin(), other.end(), inlined_space());
1008 tag().set_inline_size(other.size());
1009 }
1010 }
1011
1012 template <typename T, size_t N, typename A>
InlinedVector(InlinedVector && other)1013 InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other) noexcept(
1014 absl::allocator_is_nothrow<allocator_type>::value ||
1015 std::is_nothrow_move_constructible<value_type>::value)
1016 : allocator_and_tag_(other.allocator_and_tag_) {
1017 if (other.allocated()) {
1018 // We can just steal the underlying buffer from the source.
1019 // That leaves the source empty, so we clear its size.
1020 init_allocation(other.allocation());
1021 other.tag() = Tag();
1022 } else {
1023 UninitializedCopy(
1024 std::make_move_iterator(other.inlined_space()),
1025 std::make_move_iterator(other.inlined_space() + other.size()),
1026 inlined_space());
1027 }
1028 }
1029
1030 template <typename T, size_t N, typename A>
InlinedVector(InlinedVector && other,const allocator_type & alloc)1031 InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other,
1032 const allocator_type& alloc) noexcept( //
1033 absl::allocator_is_nothrow<allocator_type>::value)
1034 : allocator_and_tag_(alloc) {
1035 if (other.allocated()) {
1036 if (alloc == other.allocator()) {
1037 // We can just steal the allocation from the source.
1038 tag() = other.tag();
1039 init_allocation(other.allocation());
1040 other.tag() = Tag();
1041 } else {
1042 // We need to use our own allocator
1043 reserve(other.size());
1044 UninitializedCopy(std::make_move_iterator(other.begin()),
1045 std::make_move_iterator(other.end()),
1046 allocated_space());
1047 tag().set_allocated_size(other.size());
1048 }
1049 } else {
1050 UninitializedCopy(
1051 std::make_move_iterator(other.inlined_space()),
1052 std::make_move_iterator(other.inlined_space() + other.size()),
1053 inlined_space());
1054 tag().set_inline_size(other.size());
1055 }
1056 }
1057
1058 template <typename T, size_t N, typename A>
InitAssign(size_type n,const_reference v)1059 void InlinedVector<T, N, A>::InitAssign(size_type n, const_reference v) {
1060 if (n > inlined_capacity()) {
1061 Allocation new_allocation(allocator(), n);
1062 init_allocation(new_allocation);
1063 UninitializedFill(allocated_space(), allocated_space() + n, v);
1064 tag().set_allocated_size(n);
1065 } else {
1066 UninitializedFill(inlined_space(), inlined_space() + n, v);
1067 tag().set_inline_size(n);
1068 }
1069 }
1070
1071 template <typename T, size_t N, typename A>
InitAssign(size_type n)1072 void InlinedVector<T, N, A>::InitAssign(size_type n) {
1073 if (n > inlined_capacity()) {
1074 Allocation new_allocation(allocator(), n);
1075 init_allocation(new_allocation);
1076 UninitializedFill(allocated_space(), allocated_space() + n);
1077 tag().set_allocated_size(n);
1078 } else {
1079 UninitializedFill(inlined_space(), inlined_space() + n);
1080 tag().set_inline_size(n);
1081 }
1082 }
1083
1084 template <typename T, size_t N, typename A>
resize(size_type n)1085 void InlinedVector<T, N, A>::resize(size_type n) {
1086 size_type s = size();
1087 if (n < s) {
1088 erase(begin() + n, end());
1089 return;
1090 }
1091 reserve(n);
1092 assert(capacity() >= n);
1093
1094 // Fill new space with elements constructed in-place.
1095 if (allocated()) {
1096 UninitializedFill(allocated_space() + s, allocated_space() + n);
1097 tag().set_allocated_size(n);
1098 } else {
1099 UninitializedFill(inlined_space() + s, inlined_space() + n);
1100 tag().set_inline_size(n);
1101 }
1102 }
1103
1104 template <typename T, size_t N, typename A>
resize(size_type n,const_reference v)1105 void InlinedVector<T, N, A>::resize(size_type n, const_reference v) {
1106 size_type s = size();
1107 if (n < s) {
1108 erase(begin() + n, end());
1109 return;
1110 }
1111 reserve(n);
1112 assert(capacity() >= n);
1113
1114 // Fill new space with copies of 'v'.
1115 if (allocated()) {
1116 UninitializedFill(allocated_space() + s, allocated_space() + n, v);
1117 tag().set_allocated_size(n);
1118 } else {
1119 UninitializedFill(inlined_space() + s, inlined_space() + n, v);
1120 tag().set_inline_size(n);
1121 }
1122 }
1123
1124 template <typename T, size_t N, typename A>
1125 template <typename... Args>
1126 auto InlinedVector<T, N, A>::emplace(const_iterator position, Args&&... args)
1127 -> iterator {
1128 assert(position >= begin());
1129 assert(position <= end());
1130 if (ABSL_PREDICT_FALSE(position == end())) {
1131 emplace_back(std::forward<Args>(args)...);
1132 return end() - 1;
1133 }
1134
1135 T new_t = T(std::forward<Args>(args)...);
1136
1137 auto range = ShiftRight(position, 1);
1138 if (range.first == range.second) {
1139 // constructing into uninitialized memory
1140 Construct(range.first, std::move(new_t));
1141 } else {
1142 // assigning into moved-from object
1143 *range.first = T(std::move(new_t));
1144 }
1145
1146 return range.first;
1147 }
1148
1149 template <typename T, size_t N, typename A>
1150 auto InlinedVector<T, N, A>::erase(const_iterator from, const_iterator to)
1151 -> iterator {
1152 assert(begin() <= from);
1153 assert(from <= to);
1154 assert(to <= end());
1155
1156 iterator range_start = const_cast<iterator>(from);
1157 iterator range_end = const_cast<iterator>(to);
1158
1159 size_type s = size();
1160 ptrdiff_t erase_gap = std::distance(range_start, range_end);
1161 if (erase_gap > 0) {
1162 pointer space;
1163 if (allocated()) {
1164 space = allocated_space();
1165 tag().set_allocated_size(s - erase_gap);
1166 } else {
1167 space = inlined_space();
1168 tag().set_inline_size(s - erase_gap);
1169 }
1170 std::move(range_end, space + s, range_start);
1171 Destroy(space + s - erase_gap, space + s);
1172 }
1173 return range_start;
1174 }
1175
1176 template <typename T, size_t N, typename A>
swap(InlinedVector & other)1177 void InlinedVector<T, N, A>::swap(InlinedVector& other) {
1178 using std::swap; // Augment ADL with `std::swap`.
1179 if (ABSL_PREDICT_FALSE(this == &other)) return;
1180
1181 if (allocated() && other.allocated()) {
1182 // Both out of line, so just swap the tag, allocation, and allocator.
1183 swap(tag(), other.tag());
1184 swap(allocation(), other.allocation());
1185 swap(allocator(), other.allocator());
1186 return;
1187 }
1188 if (!allocated() && !other.allocated()) {
1189 // Both inlined: swap up to smaller size, then move remaining elements.
1190 InlinedVector* a = this;
1191 InlinedVector* b = &other;
1192 if (size() < other.size()) {
1193 swap(a, b);
1194 }
1195
1196 const size_type a_size = a->size();
1197 const size_type b_size = b->size();
1198 assert(a_size >= b_size);
1199 // `a` is larger. Swap the elements up to the smaller array size.
1200 std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size,
1201 b->inlined_space());
1202
1203 // Move the remaining elements:
1204 // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
1205 b->UninitializedCopy(a->inlined_space() + b_size,
1206 a->inlined_space() + a_size,
1207 b->inlined_space() + b_size);
1208 a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
1209
1210 swap(a->tag(), b->tag());
1211 swap(a->allocator(), b->allocator());
1212 assert(b->size() == a_size);
1213 assert(a->size() == b_size);
1214 return;
1215 }
1216
1217 // One is out of line, one is inline.
1218 // We first move the elements from the inlined vector into the
1219 // inlined space in the other vector. We then put the other vector's
1220 // pointer/capacity into the originally inlined vector and swap
1221 // the tags.
1222 InlinedVector* a = this;
1223 InlinedVector* b = &other;
1224 if (a->allocated()) {
1225 swap(a, b);
1226 }
1227 assert(!a->allocated());
1228 assert(b->allocated());
1229 const size_type a_size = a->size();
1230 const size_type b_size = b->size();
1231 // In an optimized build, `b_size` would be unused.
1232 static_cast<void>(b_size);
1233
1234 // Made Local copies of `size()`, don't need `tag()` accurate anymore
1235 swap(a->tag(), b->tag());
1236
1237 // Copy `b_allocation` out before `b`'s union gets clobbered by `inline_space`
1238 Allocation b_allocation = b->allocation();
1239
1240 b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
1241 b->inlined_space());
1242 a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
1243
1244 a->allocation() = b_allocation;
1245
1246 if (a->allocator() != b->allocator()) {
1247 swap(a->allocator(), b->allocator());
1248 }
1249
1250 assert(b->size() == a_size);
1251 assert(a->size() == b_size);
1252 }
1253
1254 template <typename T, size_t N, typename A>
EnlargeBy(size_type delta)1255 void InlinedVector<T, N, A>::EnlargeBy(size_type delta) {
1256 const size_type s = size();
1257 assert(s <= capacity());
1258
1259 size_type target = std::max(inlined_capacity(), s + delta);
1260
1261 // Compute new capacity by repeatedly doubling current capacity
1262 // TODO(user): Check and avoid overflow?
1263 size_type new_capacity = capacity();
1264 while (new_capacity < target) {
1265 new_capacity <<= 1;
1266 }
1267
1268 Allocation new_allocation(allocator(), new_capacity);
1269
1270 UninitializedCopy(std::make_move_iterator(data()),
1271 std::make_move_iterator(data() + s),
1272 new_allocation.buffer());
1273
1274 ResetAllocation(new_allocation, s);
1275 }
1276
1277 template <typename T, size_t N, typename A>
1278 auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n)
1279 -> std::pair<iterator, iterator> {
1280 iterator start_used = const_cast<iterator>(position);
1281 iterator start_raw = const_cast<iterator>(position);
1282 size_type s = size();
1283 size_type required_size = s + n;
1284
1285 if (required_size > capacity()) {
1286 // Compute new capacity by repeatedly doubling current capacity
1287 size_type new_capacity = capacity();
1288 while (new_capacity < required_size) {
1289 new_capacity <<= 1;
1290 }
1291 // Move everyone into the new allocation, leaving a gap of `n` for the
1292 // requested shift.
1293 Allocation new_allocation(allocator(), new_capacity);
1294 size_type index = position - begin();
1295 UninitializedCopy(std::make_move_iterator(data()),
1296 std::make_move_iterator(data() + index),
1297 new_allocation.buffer());
1298 UninitializedCopy(std::make_move_iterator(data() + index),
1299 std::make_move_iterator(data() + s),
1300 new_allocation.buffer() + index + n);
1301 ResetAllocation(new_allocation, s);
1302
1303 // New allocation means our iterator is invalid, so we'll recalculate.
1304 // Since the entire gap is in new space, there's no used space to reuse.
1305 start_raw = begin() + index;
1306 start_used = start_raw;
1307 } else {
1308 // If we had enough space, it's a two-part move. Elements going into
1309 // previously-unoccupied space need an `UninitializedCopy()`. Elements
1310 // going into a previously-occupied space are just a `std::move()`.
1311 iterator pos = const_cast<iterator>(position);
1312 iterator raw_space = end();
1313 size_type slots_in_used_space = raw_space - pos;
1314 size_type new_elements_in_used_space = std::min(n, slots_in_used_space);
1315 size_type new_elements_in_raw_space = n - new_elements_in_used_space;
1316 size_type old_elements_in_used_space =
1317 slots_in_used_space - new_elements_in_used_space;
1318
1319 UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space),
1320 std::make_move_iterator(raw_space),
1321 raw_space + new_elements_in_raw_space);
1322 std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
1323
1324 // If the gap is entirely in raw space, the used space starts where the raw
1325 // space starts, leaving no elements in used space. If the gap is entirely
1326 // in used space, the raw space starts at the end of the gap, leaving all
1327 // elements accounted for within the used space.
1328 start_used = pos;
1329 start_raw = pos + new_elements_in_used_space;
1330 }
1331 tag().add_size(n);
1332 return std::make_pair(start_used, start_raw);
1333 }
1334
1335 template <typename T, size_t N, typename A>
Destroy(pointer from,pointer to)1336 void InlinedVector<T, N, A>::Destroy(pointer from, pointer to) {
1337 for (pointer cur = from; cur != to; ++cur) {
1338 std::allocator_traits<allocator_type>::destroy(allocator(), cur);
1339 }
1340 #ifndef NDEBUG
1341 // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
1342 // Cast to `void*` to tell the compiler that we don't care that we might be
1343 // scribbling on a vtable pointer.
1344 if (from != to) {
1345 auto len = sizeof(value_type) * std::distance(from, to);
1346 std::memset(reinterpret_cast<void*>(from), 0xab, len);
1347 }
1348 #endif
1349 }
1350
1351 template <typename T, size_t N, typename A>
1352 template <typename Iterator>
AppendRange(Iterator first,Iterator last,std::forward_iterator_tag)1353 void InlinedVector<T, N, A>::AppendRange(Iterator first, Iterator last,
1354 std::forward_iterator_tag) {
1355 auto length = std::distance(first, last);
1356 reserve(size() + length);
1357 if (allocated()) {
1358 UninitializedCopy(first, last, allocated_space() + size());
1359 tag().set_allocated_size(size() + length);
1360 } else {
1361 UninitializedCopy(first, last, inlined_space() + size());
1362 tag().set_inline_size(size() + length);
1363 }
1364 }
1365
1366 template <typename T, size_t N, typename A>
1367 template <typename Iterator>
AssignRange(Iterator first,Iterator last,std::input_iterator_tag)1368 void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last,
1369 std::input_iterator_tag) {
1370 // Optimized to avoid reallocation.
1371 // Prefer reassignment to copy construction for elements.
1372 iterator out = begin();
1373 for (; first != last && out != end(); ++first, ++out) {
1374 *out = *first;
1375 }
1376 erase(out, end());
1377 std::copy(first, last, std::back_inserter(*this));
1378 }
1379
1380 template <typename T, size_t N, typename A>
1381 template <typename Iterator>
AssignRange(Iterator first,Iterator last,std::forward_iterator_tag)1382 void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last,
1383 std::forward_iterator_tag) {
1384 auto length = std::distance(first, last);
1385 // Prefer reassignment to copy construction for elements.
1386 if (static_cast<size_type>(length) <= size()) {
1387 erase(std::copy(first, last, begin()), end());
1388 return;
1389 }
1390 reserve(length);
1391 iterator out = begin();
1392 for (; out != end(); ++first, ++out) *out = *first;
1393 if (allocated()) {
1394 UninitializedCopy(first, last, out);
1395 tag().set_allocated_size(length);
1396 } else {
1397 UninitializedCopy(first, last, out);
1398 tag().set_inline_size(length);
1399 }
1400 }
1401
1402 template <typename T, size_t N, typename A>
1403 auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position,
1404 size_type n, const_reference v)
1405 -> iterator {
1406 assert(position >= begin() && position <= end());
1407 if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position);
1408
1409 value_type copy = v;
1410 std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
1411 std::fill(it_pair.first, it_pair.second, copy);
1412 UninitializedFill(it_pair.second, it_pair.first + n, copy);
1413
1414 return it_pair.first;
1415 }
1416
1417 template <typename T, size_t N, typename A>
1418 template <typename InputIterator>
1419 auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
1420 InputIterator first,
1421 InputIterator last,
1422 std::input_iterator_tag)
1423 -> iterator {
1424 assert(position >= begin() && position <= end());
1425 size_type index = position - cbegin();
1426 size_type i = index;
1427 while (first != last) insert(begin() + i++, *first++);
1428 return begin() + index;
1429 }
1430
1431 template <typename T, size_t N, typename A>
1432 template <typename ForwardIterator>
1433 auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
1434 ForwardIterator first,
1435 ForwardIterator last,
1436 std::forward_iterator_tag)
1437 -> iterator {
1438 assert(position >= begin() && position <= end());
1439 if (ABSL_PREDICT_FALSE(first == last)) return const_cast<iterator>(position);
1440
1441 auto n = std::distance(first, last);
1442 std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
1443 size_type used_spots = it_pair.second - it_pair.first;
1444 ForwardIterator open_spot = std::next(first, used_spots);
1445 std::copy(first, open_spot, it_pair.first);
1446 UninitializedCopy(open_spot, last, it_pair.second);
1447 return it_pair.first;
1448 }
1449
1450 } // namespace absl
1451
1452
1453 #endif // S2_THIRD_PARTY_ABSL_CONTAINER_INLINED_VECTOR_H_
1454