Coverage Report

Created: 2024-09-23 06:29

/src/abseil-cpp/absl/container/internal/inlined_vector.h
Line
Count
Source (jump to first uncovered line)
1
// Copyright 2019 The Abseil Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      https://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14
15
#ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_H_
16
#define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_H_
17
18
#include <algorithm>
19
#include <cstddef>
20
#include <cstring>
21
#include <iterator>
22
#include <limits>
23
#include <memory>
24
#include <new>
25
#include <type_traits>
26
#include <utility>
27
28
#include "absl/base/attributes.h"
29
#include "absl/base/config.h"
30
#include "absl/base/internal/identity.h"
31
#include "absl/base/macros.h"
32
#include "absl/container/internal/compressed_tuple.h"
33
#include "absl/memory/memory.h"
34
#include "absl/meta/type_traits.h"
35
#include "absl/types/span.h"
36
37
namespace absl {
38
ABSL_NAMESPACE_BEGIN
39
namespace inlined_vector_internal {
40
41
// GCC does not deal very well with the below code
42
#if !defined(__clang__) && defined(__GNUC__)
43
#pragma GCC diagnostic push
44
#pragma GCC diagnostic ignored "-Warray-bounds"
45
#endif
46
47
template <typename A>
48
using AllocatorTraits = std::allocator_traits<A>;
49
template <typename A>
50
using ValueType = typename AllocatorTraits<A>::value_type;
51
template <typename A>
52
using SizeType = typename AllocatorTraits<A>::size_type;
53
template <typename A>
54
using Pointer = typename AllocatorTraits<A>::pointer;
55
template <typename A>
56
using ConstPointer = typename AllocatorTraits<A>::const_pointer;
57
template <typename A>
58
using SizeType = typename AllocatorTraits<A>::size_type;
59
template <typename A>
60
using DifferenceType = typename AllocatorTraits<A>::difference_type;
61
template <typename A>
62
using Reference = ValueType<A>&;
63
template <typename A>
64
using ConstReference = const ValueType<A>&;
65
template <typename A>
66
using Iterator = Pointer<A>;
67
template <typename A>
68
using ConstIterator = ConstPointer<A>;
69
template <typename A>
70
using ReverseIterator = typename std::reverse_iterator<Iterator<A>>;
71
template <typename A>
72
using ConstReverseIterator = typename std::reverse_iterator<ConstIterator<A>>;
73
template <typename A>
74
using MoveIterator = typename std::move_iterator<Iterator<A>>;
75
76
template <typename Iterator>
77
using IsAtLeastForwardIterator = std::is_convertible<
78
    typename std::iterator_traits<Iterator>::iterator_category,
79
    std::forward_iterator_tag>;
80
81
template <typename A>
82
using IsMoveAssignOk = std::is_move_assignable<ValueType<A>>;
83
template <typename A>
84
using IsSwapOk = absl::type_traits_internal::IsSwappable<ValueType<A>>;
85
86
template <typename A, bool IsTriviallyDestructible =
87
                          absl::is_trivially_destructible<ValueType<A>>::value>
88
struct DestroyAdapter;
89
90
template <typename A>
91
struct DestroyAdapter<A, /* IsTriviallyDestructible */ false> {
92
  static void DestroyElements(A& allocator, Pointer<A> destroy_first,
93
                              SizeType<A> destroy_size) {
94
    for (SizeType<A> i = destroy_size; i != 0;) {
95
      --i;
96
      AllocatorTraits<A>::destroy(allocator, destroy_first + i);
97
    }
98
  }
99
};
100
101
template <typename A>
102
struct DestroyAdapter<A, /* IsTriviallyDestructible */ true> {
103
  static void DestroyElements(A& allocator, Pointer<A> destroy_first,
104
0
                              SizeType<A> destroy_size) {
105
0
    static_cast<void>(allocator);
106
0
    static_cast<void>(destroy_first);
107
0
    static_cast<void>(destroy_size);
108
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::DestroyAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, true>::DestroyElements(std::__1::allocator<absl::str_format_internal::FormatArgImpl>&, absl::str_format_internal::FormatArgImpl*, unsigned long)
Unexecuted instantiation: absl::inlined_vector_internal::DestroyAdapter<std::__1::allocator<absl::LogSink*>, true>::DestroyElements(std::__1::allocator<absl::LogSink*>&, absl::LogSink**, unsigned long)
109
};
110
111
template <typename A>
112
struct Allocation {
113
  Pointer<A> data = nullptr;
114
  SizeType<A> capacity = 0;
115
};
116
117
template <typename A,
118
          bool IsOverAligned =
119
              (alignof(ValueType<A>) > ABSL_INTERNAL_DEFAULT_NEW_ALIGNMENT)>
120
struct MallocAdapter {
121
0
  static Allocation<A> Allocate(A& allocator, SizeType<A> requested_capacity) {
122
0
    return {AllocatorTraits<A>::allocate(allocator, requested_capacity),
123
0
            requested_capacity};
124
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::MallocAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, false>::Allocate(std::__1::allocator<absl::str_format_internal::FormatArgImpl>&, unsigned long)
Unexecuted instantiation: absl::inlined_vector_internal::MallocAdapter<std::__1::allocator<absl::LogSink*>, false>::Allocate(std::__1::allocator<absl::LogSink*>&, unsigned long)
125
126
  static void Deallocate(A& allocator, Pointer<A> pointer,
127
0
                         SizeType<A> capacity) {
128
0
    AllocatorTraits<A>::deallocate(allocator, pointer, capacity);
129
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::MallocAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, false>::Deallocate(std::__1::allocator<absl::str_format_internal::FormatArgImpl>&, absl::str_format_internal::FormatArgImpl*, unsigned long)
Unexecuted instantiation: absl::inlined_vector_internal::MallocAdapter<std::__1::allocator<absl::LogSink*>, false>::Deallocate(std::__1::allocator<absl::LogSink*>&, absl::LogSink**, unsigned long)
130
};
131
132
template <typename A, typename ValueAdapter>
133
void ConstructElements(absl::internal::type_identity_t<A>& allocator,
134
                       Pointer<A> construct_first, ValueAdapter& values,
135
5.12M
                       SizeType<A> construct_size) {
136
10.2M
  for (SizeType<A> i = 0; i < construct_size; ++i) {
137
5.12M
    ABSL_INTERNAL_TRY { values.ConstructNext(allocator, construct_first + i); }
138
5.12M
    ABSL_INTERNAL_CATCH_ANY {
139
0
      DestroyAdapter<A>::DestroyElements(allocator, construct_first, i);
140
0
      ABSL_INTERNAL_RETHROW;
141
0
    }
142
5.12M
  }
143
5.12M
}
void absl::inlined_vector_internal::ConstructElements<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, absl::str_format_internal::FormatArgImpl const*> >(absl::internal::type_identity<std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::type&, std::__1::allocator_traits<std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::pointer, absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, absl::str_format_internal::FormatArgImpl const*>&, std::__1::allocator_traits<std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::size_type)
Line
Count
Source
135
5.12M
                       SizeType<A> construct_size) {
136
10.2M
  for (SizeType<A> i = 0; i < construct_size; ++i) {
137
5.12M
    ABSL_INTERNAL_TRY { values.ConstructNext(allocator, construct_first + i); }
138
5.12M
    ABSL_INTERNAL_CATCH_ANY {
139
0
      DestroyAdapter<A>::DestroyElements(allocator, construct_first, i);
140
0
      ABSL_INTERNAL_RETHROW;
141
0
    }
142
5.12M
  }
143
5.12M
}
Unexecuted instantiation: void absl::inlined_vector_internal::ConstructElements<std::__1::allocator<absl::LogSink*>, absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::LogSink*>, std::__1::move_iterator<absl::LogSink**> > >(absl::internal::type_identity<std::__1::allocator<absl::LogSink*> >::type&, std::__1::allocator_traits<std::__1::allocator<absl::LogSink*> >::pointer, absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::LogSink*>, std::__1::move_iterator<absl::LogSink**> >&, std::__1::allocator_traits<std::__1::allocator<absl::LogSink*> >::size_type)
144
145
template <typename A, typename ValueAdapter>
146
void AssignElements(Pointer<A> assign_first, ValueAdapter& values,
147
                    SizeType<A> assign_size) {
148
  for (SizeType<A> i = 0; i < assign_size; ++i) {
149
    values.AssignNext(assign_first + i);
150
  }
151
}
152
153
template <typename A>
154
struct StorageView {
155
  Pointer<A> data;
156
  SizeType<A> size;
157
  SizeType<A> capacity;
158
};
159
160
template <typename A, typename Iterator>
161
class IteratorValueAdapter {
162
 public:
163
5.12M
  explicit IteratorValueAdapter(const Iterator& it) : it_(it) {}
Unexecuted instantiation: absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::LogSink*>, std::__1::move_iterator<absl::LogSink**> >::IteratorValueAdapter(std::__1::move_iterator<absl::LogSink**> const&)
absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, absl::str_format_internal::FormatArgImpl const*>::IteratorValueAdapter(absl::str_format_internal::FormatArgImpl const* const&)
Line
Count
Source
163
5.12M
  explicit IteratorValueAdapter(const Iterator& it) : it_(it) {}
164
165
5.12M
  void ConstructNext(A& allocator, Pointer<A> construct_at) {
166
5.12M
    AllocatorTraits<A>::construct(allocator, construct_at, *it_);
167
5.12M
    ++it_;
168
5.12M
  }
absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::str_format_internal::FormatArgImpl>, absl::str_format_internal::FormatArgImpl const*>::ConstructNext(std::__1::allocator<absl::str_format_internal::FormatArgImpl>&, absl::str_format_internal::FormatArgImpl*)
Line
Count
Source
165
5.12M
  void ConstructNext(A& allocator, Pointer<A> construct_at) {
166
5.12M
    AllocatorTraits<A>::construct(allocator, construct_at, *it_);
167
5.12M
    ++it_;
168
5.12M
  }
Unexecuted instantiation: absl::inlined_vector_internal::IteratorValueAdapter<std::__1::allocator<absl::LogSink*>, std::__1::move_iterator<absl::LogSink**> >::ConstructNext(std::__1::allocator<absl::LogSink*>&, absl::LogSink**)
169
170
  void AssignNext(Pointer<A> assign_at) {
171
    *assign_at = *it_;
172
    ++it_;
173
  }
174
175
 private:
176
  Iterator it_;
177
};
178
179
template <typename A>
180
class CopyValueAdapter {
181
 public:
182
  explicit CopyValueAdapter(ConstPointer<A> p) : ptr_(p) {}
183
184
  void ConstructNext(A& allocator, Pointer<A> construct_at) {
185
    AllocatorTraits<A>::construct(allocator, construct_at, *ptr_);
186
  }
187
188
  void AssignNext(Pointer<A> assign_at) { *assign_at = *ptr_; }
189
190
 private:
191
  ConstPointer<A> ptr_;
192
};
193
194
template <typename A>
195
class DefaultValueAdapter {
196
 public:
197
  explicit DefaultValueAdapter() {}
198
199
  void ConstructNext(A& allocator, Pointer<A> construct_at) {
200
    AllocatorTraits<A>::construct(allocator, construct_at);
201
  }
202
203
  void AssignNext(Pointer<A> assign_at) { *assign_at = ValueType<A>(); }
204
};
205
206
template <typename A>
207
class AllocationTransaction {
208
 public:
209
  explicit AllocationTransaction(A& allocator)
210
0
      : allocator_data_(allocator, nullptr), capacity_(0) {}
211
212
0
  ~AllocationTransaction() {
213
0
    if (DidAllocate()) {
214
0
      MallocAdapter<A>::Deallocate(GetAllocator(), GetData(), GetCapacity());
215
0
    }
216
0
  }
217
218
  AllocationTransaction(const AllocationTransaction&) = delete;
219
  void operator=(const AllocationTransaction&) = delete;
220
221
0
  A& GetAllocator() { return allocator_data_.template get<0>(); }
222
0
  Pointer<A>& GetData() { return allocator_data_.template get<1>(); }
223
0
  SizeType<A>& GetCapacity() { return capacity_; }
224
225
0
  bool DidAllocate() { return GetData() != nullptr; }
226
227
0
  Pointer<A> Allocate(SizeType<A> requested_capacity) {
228
0
    Allocation<A> result =
229
0
        MallocAdapter<A>::Allocate(GetAllocator(), requested_capacity);
230
0
    GetData() = result.data;
231
0
    GetCapacity() = result.capacity;
232
0
    return result.data;
233
0
  }
234
235
0
  ABSL_MUST_USE_RESULT Allocation<A> Release() && {
236
0
    Allocation<A> result = {GetData(), GetCapacity()};
237
0
    Reset();
238
0
    return result;
239
0
  }
240
241
 private:
242
0
  void Reset() {
243
0
    GetData() = nullptr;
244
0
    GetCapacity() = 0;
245
0
  }
246
247
  container_internal::CompressedTuple<A, Pointer<A>> allocator_data_;
248
  SizeType<A> capacity_;
249
};
250
251
template <typename A>
252
class ConstructionTransaction {
253
 public:
254
  explicit ConstructionTransaction(A& allocator)
255
      : allocator_data_(allocator, nullptr), size_(0) {}
256
257
  ~ConstructionTransaction() {
258
    if (DidConstruct()) {
259
      DestroyAdapter<A>::DestroyElements(GetAllocator(), GetData(), GetSize());
260
    }
261
  }
262
263
  ConstructionTransaction(const ConstructionTransaction&) = delete;
264
  void operator=(const ConstructionTransaction&) = delete;
265
266
  A& GetAllocator() { return allocator_data_.template get<0>(); }
267
  Pointer<A>& GetData() { return allocator_data_.template get<1>(); }
268
  SizeType<A>& GetSize() { return size_; }
269
270
  bool DidConstruct() { return GetData() != nullptr; }
271
  template <typename ValueAdapter>
272
  void Construct(Pointer<A> data, ValueAdapter& values, SizeType<A> size) {
273
    ConstructElements<A>(GetAllocator(), data, values, size);
274
    GetData() = data;
275
    GetSize() = size;
276
  }
277
  void Commit() && {
278
    GetData() = nullptr;
279
    GetSize() = 0;
280
  }
281
282
 private:
283
  container_internal::CompressedTuple<A, Pointer<A>> allocator_data_;
284
  SizeType<A> size_;
285
};
286
287
template <typename T, size_t N, typename A>
288
class Storage {
289
 public:
290
  struct MemcpyPolicy {};
291
  struct ElementwiseAssignPolicy {};
292
  struct ElementwiseSwapPolicy {};
293
  struct ElementwiseConstructPolicy {};
294
295
  using MoveAssignmentPolicy = absl::conditional_t<
296
      // Fast path: if the value type can be trivially move assigned and
297
      // destroyed, and we know the allocator doesn't do anything fancy, then
298
      // it's safe for us to simply adopt the contents of the storage for
299
      // `other` and remove its own reference to them. It's as if we had
300
      // individually move-assigned each value and then destroyed the original.
301
      absl::conjunction<absl::is_trivially_move_assignable<ValueType<A>>,
302
                        absl::is_trivially_destructible<ValueType<A>>,
303
                        std::is_same<A, std::allocator<ValueType<A>>>>::value,
304
      MemcpyPolicy,
305
      // Otherwise we use move assignment if possible. If not, we simulate
306
      // move assignment using move construction.
307
      //
308
      // Note that this is in contrast to e.g. std::vector and std::optional,
309
      // which are themselves not move-assignable when their contained type is
310
      // not.
311
      absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
312
                          ElementwiseConstructPolicy>>;
313
314
  // The policy to be used specifically when swapping inlined elements.
315
  using SwapInlinedElementsPolicy = absl::conditional_t<
316
      // Fast path: if the value type can be trivially relocated, and we
317
      // know the allocator doesn't do anything fancy, then it's safe for us
318
      // to simply swap the bytes in the inline storage. It's as if we had
319
      // relocated the first vector's elements into temporary storage,
320
      // relocated the second's elements into the (now-empty) first's,
321
      // and then relocated from temporary storage into the second.
322
      absl::conjunction<absl::is_trivially_relocatable<ValueType<A>>,
323
                        std::is_same<A, std::allocator<ValueType<A>>>>::value,
324
      MemcpyPolicy,
325
      absl::conditional_t<IsSwapOk<A>::value, ElementwiseSwapPolicy,
326
                          ElementwiseConstructPolicy>>;
327
328
0
  static SizeType<A> NextCapacity(SizeType<A> current_capacity) {
329
0
    return current_capacity * 2;
330
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::NextCapacity(unsigned long)
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::NextCapacity(unsigned long)
331
332
  static SizeType<A> ComputeCapacity(SizeType<A> current_capacity,
333
0
                                     SizeType<A> requested_capacity) {
334
0
    return (std::max)(NextCapacity(current_capacity), requested_capacity);
335
0
  }
336
337
  // ---------------------------------------------------------------------------
338
  // Storage Constructors and Destructor
339
  // ---------------------------------------------------------------------------
340
341
3.79M
  Storage() : metadata_(A(), /* size and is_allocated */ 0u) {}
342
343
  explicit Storage(const A& allocator)
344
5.12M
      : metadata_(allocator, /* size and is_allocated */ 0u) {}
345
346
8.92M
  ~Storage() {
347
    // Fast path: if we are empty and not allocated, there's nothing to do.
348
8.92M
    if (GetSizeAndIsAllocated() == 0) {
349
3.79M
      return;
350
3.79M
    }
351
352
    // Fast path: if no destructors need to be run and we know the allocator
353
    // doesn't do anything fancy, then all we need to do is deallocate (and
354
    // maybe not even that).
355
5.12M
    if (absl::is_trivially_destructible<ValueType<A>>::value &&
356
5.12M
        std::is_same<A, std::allocator<ValueType<A>>>::value) {
357
5.12M
      DeallocateIfAllocated();
358
5.12M
      return;
359
5.12M
    }
360
361
0
    DestroyContents();
362
0
  }
absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::~Storage()
Line
Count
Source
346
3.79M
  ~Storage() {
347
    // Fast path: if we are empty and not allocated, there's nothing to do.
348
3.79M
    if (GetSizeAndIsAllocated() == 0) {
349
3.79M
      return;
350
3.79M
    }
351
352
    // Fast path: if no destructors need to be run and we know the allocator
353
    // doesn't do anything fancy, then all we need to do is deallocate (and
354
    // maybe not even that).
355
0
    if (absl::is_trivially_destructible<ValueType<A>>::value &&
356
0
        std::is_same<A, std::allocator<ValueType<A>>>::value) {
357
0
      DeallocateIfAllocated();
358
0
      return;
359
0
    }
360
361
0
    DestroyContents();
362
0
  }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::~Storage()
Line
Count
Source
346
5.12M
  ~Storage() {
347
    // Fast path: if we are empty and not allocated, there's nothing to do.
348
5.12M
    if (GetSizeAndIsAllocated() == 0) {
349
0
      return;
350
0
    }
351
352
    // Fast path: if no destructors need to be run and we know the allocator
353
    // doesn't do anything fancy, then all we need to do is deallocate (and
354
    // maybe not even that).
355
5.12M
    if (absl::is_trivially_destructible<ValueType<A>>::value &&
356
5.12M
        std::is_same<A, std::allocator<ValueType<A>>>::value) {
357
5.12M
      DeallocateIfAllocated();
358
5.12M
      return;
359
5.12M
    }
360
361
0
    DestroyContents();
362
0
  }
363
364
  // ---------------------------------------------------------------------------
365
  // Storage Member Accessors
366
  // ---------------------------------------------------------------------------
367
368
14.0M
  SizeType<A>& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetSizeAndIsAllocated()
Line
Count
Source
368
10.2M
  SizeType<A>& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetSizeAndIsAllocated()
Line
Count
Source
368
3.79M
  SizeType<A>& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
369
370
33.2M
  const SizeType<A>& GetSizeAndIsAllocated() const {
371
33.2M
    return metadata_.template get<1>();
372
33.2M
  }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetSizeAndIsAllocated() const
Line
Count
Source
370
25.6M
  const SizeType<A>& GetSizeAndIsAllocated() const {
371
25.6M
    return metadata_.template get<1>();
372
25.6M
  }
absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetSizeAndIsAllocated() const
Line
Count
Source
370
7.58M
  const SizeType<A>& GetSizeAndIsAllocated() const {
371
7.58M
    return metadata_.template get<1>();
372
7.58M
  }
373
374
14.0M
  SizeType<A> GetSize() const { return GetSizeAndIsAllocated() >> 1; }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetSize() const
Line
Count
Source
374
10.2M
  SizeType<A> GetSize() const { return GetSizeAndIsAllocated() >> 1; }
absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetSize() const
Line
Count
Source
374
3.79M
  SizeType<A> GetSize() const { return GetSizeAndIsAllocated() >> 1; }
375
376
19.1M
  bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetIsAllocated() const
Line
Count
Source
376
15.3M
  bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; }
absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetIsAllocated() const
Line
Count
Source
376
3.79M
  bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; }
377
378
0
  Pointer<A> GetAllocatedData() {
379
    // GCC 12 has a false-positive -Wmaybe-uninitialized warning here.
380
#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
381
#pragma GCC diagnostic push
382
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
383
#endif
384
0
    return data_.allocated.allocated_data;
385
#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
386
#pragma GCC diagnostic pop
387
#endif
388
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetAllocatedData()
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetAllocatedData()
389
390
0
  ConstPointer<A> GetAllocatedData() const {
391
0
    return data_.allocated.allocated_data;
392
0
  }
393
394
  // ABSL_ATTRIBUTE_NO_SANITIZE_CFI is used because the memory pointed to may be
395
  // uninitialized, a common pattern in allocate()+construct() APIs.
396
  // https://clang.llvm.org/docs/ControlFlowIntegrity.html#bad-cast-checking
397
  // NOTE: When this was written, LLVM documentation did not explicitly
398
  // mention that casting `char*` and using `reinterpret_cast` qualifies
399
  // as a bad cast.
400
8.92M
  ABSL_ATTRIBUTE_NO_SANITIZE_CFI Pointer<A> GetInlinedData() {
401
8.92M
    return reinterpret_cast<Pointer<A>>(data_.inlined.inlined_data);
402
8.92M
  }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetInlinedData()
Line
Count
Source
400
5.12M
  ABSL_ATTRIBUTE_NO_SANITIZE_CFI Pointer<A> GetInlinedData() {
401
5.12M
    return reinterpret_cast<Pointer<A>>(data_.inlined.inlined_data);
402
5.12M
  }
absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetInlinedData()
Line
Count
Source
400
3.79M
  ABSL_ATTRIBUTE_NO_SANITIZE_CFI Pointer<A> GetInlinedData() {
401
3.79M
    return reinterpret_cast<Pointer<A>>(data_.inlined.inlined_data);
402
3.79M
  }
403
404
5.12M
  ABSL_ATTRIBUTE_NO_SANITIZE_CFI ConstPointer<A> GetInlinedData() const {
405
5.12M
    return reinterpret_cast<ConstPointer<A>>(data_.inlined.inlined_data);
406
5.12M
  }
407
408
0
  SizeType<A> GetAllocatedCapacity() const {
409
0
    return data_.allocated.allocated_capacity;
410
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetAllocatedCapacity() const
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetAllocatedCapacity() const
411
412
5.12M
  SizeType<A> GetInlinedCapacity() const {
413
5.12M
    return static_cast<SizeType<A>>(kOptimalInlinedSize);
414
5.12M
  }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetInlinedCapacity() const
Line
Count
Source
412
5.12M
  SizeType<A> GetInlinedCapacity() const {
413
5.12M
    return static_cast<SizeType<A>>(kOptimalInlinedSize);
414
5.12M
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetInlinedCapacity() const
415
416
0
  StorageView<A> MakeStorageView() {
417
0
    return GetIsAllocated() ? StorageView<A>{GetAllocatedData(), GetSize(),
418
0
                                             GetAllocatedCapacity()}
419
0
                            : StorageView<A>{GetInlinedData(), GetSize(),
420
0
                                             GetInlinedCapacity()};
421
0
  }
422
423
5.12M
  A& GetAllocator() { return metadata_.template get<0>(); }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::GetAllocator()
Line
Count
Source
423
5.12M
  A& GetAllocator() { return metadata_.template get<0>(); }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::GetAllocator()
424
425
  const A& GetAllocator() const { return metadata_.template get<0>(); }
426
427
  // ---------------------------------------------------------------------------
428
  // Storage Member Mutators
429
  // ---------------------------------------------------------------------------
430
431
  ABSL_ATTRIBUTE_NOINLINE void InitFrom(const Storage& other);
432
433
  template <typename ValueAdapter>
434
  void Initialize(ValueAdapter values, SizeType<A> new_size);
435
436
  template <typename ValueAdapter>
437
  void Assign(ValueAdapter values, SizeType<A> new_size);
438
439
  template <typename ValueAdapter>
440
  void Resize(ValueAdapter values, SizeType<A> new_size);
441
442
  template <typename ValueAdapter>
443
  Iterator<A> Insert(ConstIterator<A> pos, ValueAdapter values,
444
                     SizeType<A> insert_count);
445
446
  template <typename... Args>
447
  Reference<A> EmplaceBack(Args&&... args);
448
449
  Iterator<A> Erase(ConstIterator<A> from, ConstIterator<A> to);
450
451
  void Reserve(SizeType<A> requested_capacity);
452
453
  void ShrinkToFit();
454
455
  void Swap(Storage* other_storage_ptr);
456
457
0
  void SetIsAllocated() {
458
0
    GetSizeAndIsAllocated() |= static_cast<SizeType<A>>(1);
459
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::SetIsAllocated()
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::SetIsAllocated()
460
461
  void UnsetIsAllocated() {
462
    GetSizeAndIsAllocated() &= ((std::numeric_limits<SizeType<A>>::max)() - 1);
463
  }
464
465
  void SetSize(SizeType<A> size) {
466
    GetSizeAndIsAllocated() =
467
        (size << 1) | static_cast<SizeType<A>>(GetIsAllocated());
468
  }
469
470
  void SetAllocatedSize(SizeType<A> size) {
471
    GetSizeAndIsAllocated() = (size << 1) | static_cast<SizeType<A>>(1);
472
  }
473
474
0
  void SetInlinedSize(SizeType<A> size) {
475
0
    GetSizeAndIsAllocated() = size << static_cast<SizeType<A>>(1);
476
0
  }
477
478
5.12M
  void AddSize(SizeType<A> count) {
479
5.12M
    GetSizeAndIsAllocated() += count << static_cast<SizeType<A>>(1);
480
5.12M
  }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::AddSize(unsigned long)
Line
Count
Source
478
5.12M
  void AddSize(SizeType<A> count) {
479
5.12M
    GetSizeAndIsAllocated() += count << static_cast<SizeType<A>>(1);
480
5.12M
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::AddSize(unsigned long)
481
482
  void SubtractSize(SizeType<A> count) {
483
    ABSL_HARDENING_ASSERT(count <= GetSize());
484
485
    GetSizeAndIsAllocated() -= count << static_cast<SizeType<A>>(1);
486
  }
487
488
0
  void SetAllocation(Allocation<A> allocation) {
489
0
    data_.allocated.allocated_data = allocation.data;
490
0
    data_.allocated.allocated_capacity = allocation.capacity;
491
0
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::SetAllocation(absl::inlined_vector_internal::Allocation<std::__1::allocator<absl::str_format_internal::FormatArgImpl> >)
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::SetAllocation(absl::inlined_vector_internal::Allocation<std::__1::allocator<absl::LogSink*> >)
492
493
  void MemcpyFrom(const Storage& other_storage) {
494
    // Assumption check: it doesn't make sense to memcpy inlined elements unless
495
    // we know the allocator doesn't do anything fancy, and one of the following
496
    // holds:
497
    //
498
    //  *  The elements are trivially relocatable.
499
    //
500
    //  *  It's possible to trivially assign the elements and then destroy the
501
    //     source.
502
    //
503
    //  *  It's possible to trivially copy construct/assign the elements.
504
    //
505
    {
506
      using V = ValueType<A>;
507
      ABSL_HARDENING_ASSERT(
508
          other_storage.GetIsAllocated() ||
509
          (std::is_same<A, std::allocator<V>>::value &&
510
           (
511
               // First case above
512
               absl::is_trivially_relocatable<V>::value ||
513
               // Second case above
514
               (absl::is_trivially_move_assignable<V>::value &&
515
                absl::is_trivially_destructible<V>::value) ||
516
               // Third case above
517
               (absl::is_trivially_copy_constructible<V>::value ||
518
                absl::is_trivially_copy_assignable<V>::value))));
519
    }
520
521
    GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated();
522
    data_ = other_storage.data_;
523
  }
524
525
5.12M
  void DeallocateIfAllocated() {
526
5.12M
    if (GetIsAllocated()) {
527
0
      MallocAdapter<A>::Deallocate(GetAllocator(), GetAllocatedData(),
528
0
                                   GetAllocatedCapacity());
529
0
    }
530
5.12M
  }
absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::DeallocateIfAllocated()
Line
Count
Source
525
5.12M
  void DeallocateIfAllocated() {
526
5.12M
    if (GetIsAllocated()) {
527
0
      MallocAdapter<A>::Deallocate(GetAllocator(), GetAllocatedData(),
528
0
                                   GetAllocatedCapacity());
529
0
    }
530
5.12M
  }
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::DeallocateIfAllocated()
531
532
 private:
533
  ABSL_ATTRIBUTE_NOINLINE void DestroyContents();
534
535
  using Metadata = container_internal::CompressedTuple<A, SizeType<A>>;
536
537
  struct Allocated {
538
    Pointer<A> allocated_data;
539
    SizeType<A> allocated_capacity;
540
  };
541
542
  // `kOptimalInlinedSize` is an automatically adjusted inlined capacity of the
543
  // `InlinedVector`. Sometimes, it is possible to increase the capacity (from
544
  // the user requested `N`) without increasing the size of the `InlinedVector`.
545
  static constexpr size_t kOptimalInlinedSize =
546
      (std::max)(N, sizeof(Allocated) / sizeof(ValueType<A>));
547
548
  struct Inlined {
549
    alignas(ValueType<A>) char inlined_data[sizeof(
550
        ValueType<A>[kOptimalInlinedSize])];
551
  };
552
553
  union Data {
554
    Allocated allocated;
555
    Inlined inlined;
556
  };
557
558
  void SwapN(ElementwiseSwapPolicy, Storage* other, SizeType<A> n);
559
  void SwapN(ElementwiseConstructPolicy, Storage* other, SizeType<A> n);
560
561
  void SwapInlinedElements(MemcpyPolicy, Storage* other);
562
  template <typename NotMemcpyPolicy>
563
  void SwapInlinedElements(NotMemcpyPolicy, Storage* other);
564
565
  template <typename... Args>
566
  ABSL_ATTRIBUTE_NOINLINE Reference<A> EmplaceBackSlow(Args&&... args);
567
568
  Metadata metadata_;
569
  Data data_;
570
};
571
572
template <typename T, size_t N, typename A>
573
0
void Storage<T, N, A>::DestroyContents() {
574
0
  Pointer<A> data = GetIsAllocated() ? GetAllocatedData() : GetInlinedData();
575
0
  DestroyAdapter<A>::DestroyElements(GetAllocator(), data, GetSize());
576
0
  DeallocateIfAllocated();
577
0
}
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::str_format_internal::FormatArgImpl, 4ul, std::__1::allocator<absl::str_format_internal::FormatArgImpl> >::DestroyContents()
Unexecuted instantiation: absl::inlined_vector_internal::Storage<absl::LogSink*, 16ul, std::__1::allocator<absl::LogSink*> >::DestroyContents()
578
579
template <typename T, size_t N, typename A>
580
void Storage<T, N, A>::InitFrom(const Storage& other) {
581
  const SizeType<A> n = other.GetSize();
582
  ABSL_HARDENING_ASSERT(n > 0);  // Empty sources handled handled in caller.
583
  ConstPointer<A> src;
584
  Pointer<A> dst;
585
  if (!other.GetIsAllocated()) {
586
    dst = GetInlinedData();
587
    src = other.GetInlinedData();
588
  } else {
589
    // Because this is only called from the `InlinedVector` constructors, it's
590
    // safe to take on the allocation with size `0`. If `ConstructElements(...)`
591
    // throws, deallocation will be automatically handled by `~Storage()`.
592
    SizeType<A> requested_capacity = ComputeCapacity(GetInlinedCapacity(), n);
593
    Allocation<A> allocation =
594
        MallocAdapter<A>::Allocate(GetAllocator(), requested_capacity);
595
    SetAllocation(allocation);
596
    dst = allocation.data;
597
    src = other.GetAllocatedData();
598
  }
599
600
  // Fast path: if the value type is trivially copy constructible and we know
601
  // the allocator doesn't do anything fancy, then we know it is legal for us to
602
  // simply memcpy the other vector's elements.
603
  if (absl::is_trivially_copy_constructible<ValueType<A>>::value &&
604
      std::is_same<A, std::allocator<ValueType<A>>>::value) {
605
    std::memcpy(reinterpret_cast<char*>(dst),
606
                reinterpret_cast<const char*>(src), n * sizeof(ValueType<A>));
607
  } else {
608
    auto values = IteratorValueAdapter<A, ConstPointer<A>>(src);
609
    ConstructElements<A>(GetAllocator(), dst, values, n);
610
  }
611
612
  GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
613
}
614
615
template <typename T, size_t N, typename A>
616
template <typename ValueAdapter>
617
auto Storage<T, N, A>::Initialize(ValueAdapter values,
618
5.12M
                                  SizeType<A> new_size) -> void {
619
  // Only callable from constructors!
620
5.12M
  ABSL_HARDENING_ASSERT(!GetIsAllocated());
621
5.12M
  ABSL_HARDENING_ASSERT(GetSize() == 0);
622
623
5.12M
  Pointer<A> construct_data;
624
5.12M
  if (new_size > GetInlinedCapacity()) {
625
    // Because this is only called from the `InlinedVector` constructors, it's
626
    // safe to take on the allocation with size `0`. If `ConstructElements(...)`
627
    // throws, deallocation will be automatically handled by `~Storage()`.
628
0
    SizeType<A> requested_capacity =
629
0
        ComputeCapacity(GetInlinedCapacity(), new_size);
630
0
    Allocation<A> allocation =
631
0
        MallocAdapter<A>::Allocate(GetAllocator(), requested_capacity);
632
0
    construct_data = allocation.data;
633
0
    SetAllocation(allocation);
634
0
    SetIsAllocated();
635
5.12M
  } else {
636
5.12M
    construct_data = GetInlinedData();
637
5.12M
  }
638
639
5.12M
  ConstructElements<A>(GetAllocator(), construct_data, values, new_size);
640
641
  // Since the initial size was guaranteed to be `0` and the allocated bit is
642
  // already correct for either case, *adding* `new_size` gives us the correct
643
  // result faster than setting it directly.
644
5.12M
  AddSize(new_size);
645
5.12M
}
646
647
template <typename T, size_t N, typename A>
648
template <typename ValueAdapter>
649
auto Storage<T, N, A>::Assign(ValueAdapter values,
650
                              SizeType<A> new_size) -> void {
651
  StorageView<A> storage_view = MakeStorageView();
652
653
  AllocationTransaction<A> allocation_tx(GetAllocator());
654
655
  absl::Span<ValueType<A>> assign_loop;
656
  absl::Span<ValueType<A>> construct_loop;
657
  absl::Span<ValueType<A>> destroy_loop;
658
659
  if (new_size > storage_view.capacity) {
660
    SizeType<A> requested_capacity =
661
        ComputeCapacity(storage_view.capacity, new_size);
662
    construct_loop = {allocation_tx.Allocate(requested_capacity), new_size};
663
    destroy_loop = {storage_view.data, storage_view.size};
664
  } else if (new_size > storage_view.size) {
665
    assign_loop = {storage_view.data, storage_view.size};
666
    construct_loop = {storage_view.data + storage_view.size,
667
                      new_size - storage_view.size};
668
  } else {
669
    assign_loop = {storage_view.data, new_size};
670
    destroy_loop = {storage_view.data + new_size, storage_view.size - new_size};
671
  }
672
673
  AssignElements<A>(assign_loop.data(), values, assign_loop.size());
674
675
  ConstructElements<A>(GetAllocator(), construct_loop.data(), values,
676
                       construct_loop.size());
677
678
  DestroyAdapter<A>::DestroyElements(GetAllocator(), destroy_loop.data(),
679
                                     destroy_loop.size());
680
681
  if (allocation_tx.DidAllocate()) {
682
    DeallocateIfAllocated();
683
    SetAllocation(std::move(allocation_tx).Release());
684
    SetIsAllocated();
685
  }
686
687
  SetSize(new_size);
688
}
689
690
template <typename T, size_t N, typename A>
691
template <typename ValueAdapter>
692
auto Storage<T, N, A>::Resize(ValueAdapter values,
693
                              SizeType<A> new_size) -> void {
694
  StorageView<A> storage_view = MakeStorageView();
695
  Pointer<A> const base = storage_view.data;
696
  const SizeType<A> size = storage_view.size;
697
  A& alloc = GetAllocator();
698
  if (new_size <= size) {
699
    // Destroy extra old elements.
700
    DestroyAdapter<A>::DestroyElements(alloc, base + new_size, size - new_size);
701
  } else if (new_size <= storage_view.capacity) {
702
    // Construct new elements in place.
703
    ConstructElements<A>(alloc, base + size, values, new_size - size);
704
  } else {
705
    // Steps:
706
    //  a. Allocate new backing store.
707
    //  b. Construct new elements in new backing store.
708
    //  c. Move existing elements from old backing store to new backing store.
709
    //  d. Destroy all elements in old backing store.
710
    // Use transactional wrappers for the first two steps so we can roll
711
    // back if necessary due to exceptions.
712
    AllocationTransaction<A> allocation_tx(alloc);
713
    SizeType<A> requested_capacity =
714
        ComputeCapacity(storage_view.capacity, new_size);
715
    Pointer<A> new_data = allocation_tx.Allocate(requested_capacity);
716
717
    ConstructionTransaction<A> construction_tx(alloc);
718
    construction_tx.Construct(new_data + size, values, new_size - size);
719
720
    IteratorValueAdapter<A, MoveIterator<A>> move_values(
721
        (MoveIterator<A>(base)));
722
    ConstructElements<A>(alloc, new_data, move_values, size);
723
724
    DestroyAdapter<A>::DestroyElements(alloc, base, size);
725
    std::move(construction_tx).Commit();
726
    DeallocateIfAllocated();
727
    SetAllocation(std::move(allocation_tx).Release());
728
    SetIsAllocated();
729
  }
730
  SetSize(new_size);
731
}
732
733
template <typename T, size_t N, typename A>
734
template <typename ValueAdapter>
735
auto Storage<T, N, A>::Insert(ConstIterator<A> pos, ValueAdapter values,
736
                              SizeType<A> insert_count) -> Iterator<A> {
737
  StorageView<A> storage_view = MakeStorageView();
738
739
  auto insert_index = static_cast<SizeType<A>>(
740
      std::distance(ConstIterator<A>(storage_view.data), pos));
741
  SizeType<A> insert_end_index = insert_index + insert_count;
742
  SizeType<A> new_size = storage_view.size + insert_count;
743
744
  if (new_size > storage_view.capacity) {
745
    AllocationTransaction<A> allocation_tx(GetAllocator());
746
    ConstructionTransaction<A> construction_tx(GetAllocator());
747
    ConstructionTransaction<A> move_construction_tx(GetAllocator());
748
749
    IteratorValueAdapter<A, MoveIterator<A>> move_values(
750
        MoveIterator<A>(storage_view.data));
751
752
    SizeType<A> requested_capacity =
753
        ComputeCapacity(storage_view.capacity, new_size);
754
    Pointer<A> new_data = allocation_tx.Allocate(requested_capacity);
755
756
    construction_tx.Construct(new_data + insert_index, values, insert_count);
757
758
    move_construction_tx.Construct(new_data, move_values, insert_index);
759
760
    ConstructElements<A>(GetAllocator(), new_data + insert_end_index,
761
                         move_values, storage_view.size - insert_index);
762
763
    DestroyAdapter<A>::DestroyElements(GetAllocator(), storage_view.data,
764
                                       storage_view.size);
765
766
    std::move(construction_tx).Commit();
767
    std::move(move_construction_tx).Commit();
768
    DeallocateIfAllocated();
769
    SetAllocation(std::move(allocation_tx).Release());
770
771
    SetAllocatedSize(new_size);
772
    return Iterator<A>(new_data + insert_index);
773
  } else {
774
    SizeType<A> move_construction_destination_index =
775
        (std::max)(insert_end_index, storage_view.size);
776
777
    ConstructionTransaction<A> move_construction_tx(GetAllocator());
778
779
    IteratorValueAdapter<A, MoveIterator<A>> move_construction_values(
780
        MoveIterator<A>(storage_view.data +
781
                        (move_construction_destination_index - insert_count)));
782
    absl::Span<ValueType<A>> move_construction = {
783
        storage_view.data + move_construction_destination_index,
784
        new_size - move_construction_destination_index};
785
786
    Pointer<A> move_assignment_values = storage_view.data + insert_index;
787
    absl::Span<ValueType<A>> move_assignment = {
788
        storage_view.data + insert_end_index,
789
        move_construction_destination_index - insert_end_index};
790
791
    absl::Span<ValueType<A>> insert_assignment = {move_assignment_values,
792
                                                  move_construction.size()};
793
794
    absl::Span<ValueType<A>> insert_construction = {
795
        insert_assignment.data() + insert_assignment.size(),
796
        insert_count - insert_assignment.size()};
797
798
    move_construction_tx.Construct(move_construction.data(),
799
                                   move_construction_values,
800
                                   move_construction.size());
801
802
    for (Pointer<A>
803
             destination = move_assignment.data() + move_assignment.size(),
804
             last_destination = move_assignment.data(),
805
             source = move_assignment_values + move_assignment.size();
806
         ;) {
807
      --destination;
808
      --source;
809
      if (destination < last_destination) break;
810
      *destination = std::move(*source);
811
    }
812
813
    AssignElements<A>(insert_assignment.data(), values,
814
                      insert_assignment.size());
815
816
    ConstructElements<A>(GetAllocator(), insert_construction.data(), values,
817
                         insert_construction.size());
818
819
    std::move(move_construction_tx).Commit();
820
821
    AddSize(insert_count);
822
    return Iterator<A>(storage_view.data + insert_index);
823
  }
824
}
825
826
template <typename T, size_t N, typename A>
827
template <typename... Args>
828
0
auto Storage<T, N, A>::EmplaceBack(Args&&... args) -> Reference<A> {
829
0
  StorageView<A> storage_view = MakeStorageView();
830
0
  const SizeType<A> n = storage_view.size;
831
0
  if (ABSL_PREDICT_TRUE(n != storage_view.capacity)) {
832
    // Fast path; new element fits.
833
0
    Pointer<A> last_ptr = storage_view.data + n;
834
0
    AllocatorTraits<A>::construct(GetAllocator(), last_ptr,
835
0
                                  std::forward<Args>(args)...);
836
0
    AddSize(1);
837
0
    return *last_ptr;
838
0
  }
839
  // TODO(b/173712035): Annotate with musttail attribute to prevent regression.
840
0
  return EmplaceBackSlow(std::forward<Args>(args)...);
841
0
}
842
843
template <typename T, size_t N, typename A>
844
template <typename... Args>
845
0
auto Storage<T, N, A>::EmplaceBackSlow(Args&&... args) -> Reference<A> {
846
0
  StorageView<A> storage_view = MakeStorageView();
847
0
  AllocationTransaction<A> allocation_tx(GetAllocator());
848
0
  IteratorValueAdapter<A, MoveIterator<A>> move_values(
849
0
      MoveIterator<A>(storage_view.data));
850
0
  SizeType<A> requested_capacity = NextCapacity(storage_view.capacity);
851
0
  Pointer<A> construct_data = allocation_tx.Allocate(requested_capacity);
852
0
  Pointer<A> last_ptr = construct_data + storage_view.size;
853
854
  // Construct new element.
855
0
  AllocatorTraits<A>::construct(GetAllocator(), last_ptr,
856
0
                                std::forward<Args>(args)...);
857
  // Move elements from old backing store to new backing store.
858
0
  ABSL_INTERNAL_TRY {
859
0
    ConstructElements<A>(GetAllocator(), allocation_tx.GetData(), move_values,
860
0
                         storage_view.size);
861
0
  }
862
0
  ABSL_INTERNAL_CATCH_ANY {
863
0
    AllocatorTraits<A>::destroy(GetAllocator(), last_ptr);
864
0
    ABSL_INTERNAL_RETHROW;
865
0
  }
866
  // Destroy elements in old backing store.
867
0
  DestroyAdapter<A>::DestroyElements(GetAllocator(), storage_view.data,
868
0
                                     storage_view.size);
869
870
0
  DeallocateIfAllocated();
871
0
  SetAllocation(std::move(allocation_tx).Release());
872
0
  SetIsAllocated();
873
0
  AddSize(1);
874
0
  return *last_ptr;
875
0
}
876
877
template <typename T, size_t N, typename A>
878
auto Storage<T, N, A>::Erase(ConstIterator<A> from,
879
                             ConstIterator<A> to) -> Iterator<A> {
880
  StorageView<A> storage_view = MakeStorageView();
881
882
  auto erase_size = static_cast<SizeType<A>>(std::distance(from, to));
883
  auto erase_index = static_cast<SizeType<A>>(
884
      std::distance(ConstIterator<A>(storage_view.data), from));
885
  SizeType<A> erase_end_index = erase_index + erase_size;
886
887
  // Fast path: if the value type is trivially relocatable and we know
888
  // the allocator doesn't do anything fancy, then we know it is legal for us to
889
  // simply destroy the elements in the "erasure window" (which cannot throw)
890
  // and then memcpy downward to close the window.
891
  if (absl::is_trivially_relocatable<ValueType<A>>::value &&
892
      std::is_nothrow_destructible<ValueType<A>>::value &&
893
      std::is_same<A, std::allocator<ValueType<A>>>::value) {
894
    DestroyAdapter<A>::DestroyElements(
895
        GetAllocator(), storage_view.data + erase_index, erase_size);
896
    std::memmove(
897
        reinterpret_cast<char*>(storage_view.data + erase_index),
898
        reinterpret_cast<const char*>(storage_view.data + erase_end_index),
899
        (storage_view.size - erase_end_index) * sizeof(ValueType<A>));
900
  } else {
901
    IteratorValueAdapter<A, MoveIterator<A>> move_values(
902
        MoveIterator<A>(storage_view.data + erase_end_index));
903
904
    AssignElements<A>(storage_view.data + erase_index, move_values,
905
                      storage_view.size - erase_end_index);
906
907
    DestroyAdapter<A>::DestroyElements(
908
        GetAllocator(), storage_view.data + (storage_view.size - erase_size),
909
        erase_size);
910
  }
911
  SubtractSize(erase_size);
912
  return Iterator<A>(storage_view.data + erase_index);
913
}
914
915
template <typename T, size_t N, typename A>
916
auto Storage<T, N, A>::Reserve(SizeType<A> requested_capacity) -> void {
917
  StorageView<A> storage_view = MakeStorageView();
918
919
  if (ABSL_PREDICT_FALSE(requested_capacity <= storage_view.capacity)) return;
920
921
  AllocationTransaction<A> allocation_tx(GetAllocator());
922
923
  IteratorValueAdapter<A, MoveIterator<A>> move_values(
924
      MoveIterator<A>(storage_view.data));
925
926
  SizeType<A> new_requested_capacity =
927
      ComputeCapacity(storage_view.capacity, requested_capacity);
928
  Pointer<A> new_data = allocation_tx.Allocate(new_requested_capacity);
929
930
  ConstructElements<A>(GetAllocator(), new_data, move_values,
931
                       storage_view.size);
932
933
  DestroyAdapter<A>::DestroyElements(GetAllocator(), storage_view.data,
934
                                     storage_view.size);
935
936
  DeallocateIfAllocated();
937
  SetAllocation(std::move(allocation_tx).Release());
938
  SetIsAllocated();
939
}
940
941
template <typename T, size_t N, typename A>
942
auto Storage<T, N, A>::ShrinkToFit() -> void {
943
  // May only be called on allocated instances!
944
  ABSL_HARDENING_ASSERT(GetIsAllocated());
945
946
  StorageView<A> storage_view{GetAllocatedData(), GetSize(),
947
                              GetAllocatedCapacity()};
948
949
  if (ABSL_PREDICT_FALSE(storage_view.size == storage_view.capacity)) return;
950
951
  AllocationTransaction<A> allocation_tx(GetAllocator());
952
953
  IteratorValueAdapter<A, MoveIterator<A>> move_values(
954
      MoveIterator<A>(storage_view.data));
955
956
  Pointer<A> construct_data;
957
  if (storage_view.size > GetInlinedCapacity()) {
958
    SizeType<A> requested_capacity = storage_view.size;
959
    construct_data = allocation_tx.Allocate(requested_capacity);
960
    if (allocation_tx.GetCapacity() >= storage_view.capacity) {
961
      // Already using the smallest available heap allocation.
962
      return;
963
    }
964
  } else {
965
    construct_data = GetInlinedData();
966
  }
967
968
  ABSL_INTERNAL_TRY {
969
    ConstructElements<A>(GetAllocator(), construct_data, move_values,
970
                         storage_view.size);
971
  }
972
  ABSL_INTERNAL_CATCH_ANY {
973
    SetAllocation({storage_view.data, storage_view.capacity});
974
    ABSL_INTERNAL_RETHROW;
975
  }
976
977
  DestroyAdapter<A>::DestroyElements(GetAllocator(), storage_view.data,
978
                                     storage_view.size);
979
980
  MallocAdapter<A>::Deallocate(GetAllocator(), storage_view.data,
981
                               storage_view.capacity);
982
983
  if (allocation_tx.DidAllocate()) {
984
    SetAllocation(std::move(allocation_tx).Release());
985
  } else {
986
    UnsetIsAllocated();
987
  }
988
}
989
990
template <typename T, size_t N, typename A>
991
auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
992
  using std::swap;
993
  ABSL_HARDENING_ASSERT(this != other_storage_ptr);
994
995
  if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) {
996
    swap(data_.allocated, other_storage_ptr->data_.allocated);
997
  } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) {
998
    SwapInlinedElements(SwapInlinedElementsPolicy{}, other_storage_ptr);
999
  } else {
1000
    Storage* allocated_ptr = this;
1001
    Storage* inlined_ptr = other_storage_ptr;
1002
    if (!allocated_ptr->GetIsAllocated()) swap(allocated_ptr, inlined_ptr);
1003
1004
    StorageView<A> allocated_storage_view{
1005
        allocated_ptr->GetAllocatedData(), allocated_ptr->GetSize(),
1006
        allocated_ptr->GetAllocatedCapacity()};
1007
1008
    IteratorValueAdapter<A, MoveIterator<A>> move_values(
1009
        MoveIterator<A>(inlined_ptr->GetInlinedData()));
1010
1011
    ABSL_INTERNAL_TRY {
1012
      ConstructElements<A>(inlined_ptr->GetAllocator(),
1013
                           allocated_ptr->GetInlinedData(), move_values,
1014
                           inlined_ptr->GetSize());
1015
    }
1016
    ABSL_INTERNAL_CATCH_ANY {
1017
      allocated_ptr->SetAllocation(Allocation<A>{
1018
          allocated_storage_view.data, allocated_storage_view.capacity});
1019
      ABSL_INTERNAL_RETHROW;
1020
    }
1021
1022
    DestroyAdapter<A>::DestroyElements(inlined_ptr->GetAllocator(),
1023
                                       inlined_ptr->GetInlinedData(),
1024
                                       inlined_ptr->GetSize());
1025
1026
    inlined_ptr->SetAllocation(Allocation<A>{allocated_storage_view.data,
1027
                                             allocated_storage_view.capacity});
1028
  }
1029
1030
  swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated());
1031
  swap(GetAllocator(), other_storage_ptr->GetAllocator());
1032
}
1033
1034
template <typename T, size_t N, typename A>
1035
void Storage<T, N, A>::SwapN(ElementwiseSwapPolicy, Storage* other,
1036
                             SizeType<A> n) {
1037
  std::swap_ranges(GetInlinedData(), GetInlinedData() + n,
1038
                   other->GetInlinedData());
1039
}
1040
1041
template <typename T, size_t N, typename A>
1042
void Storage<T, N, A>::SwapN(ElementwiseConstructPolicy, Storage* other,
1043
                             SizeType<A> n) {
1044
  Pointer<A> a = GetInlinedData();
1045
  Pointer<A> b = other->GetInlinedData();
1046
  // see note on allocators in `SwapInlinedElements`.
1047
  A& allocator_a = GetAllocator();
1048
  A& allocator_b = other->GetAllocator();
1049
  for (SizeType<A> i = 0; i < n; ++i, ++a, ++b) {
1050
    ValueType<A> tmp(std::move(*a));
1051
1052
    AllocatorTraits<A>::destroy(allocator_a, a);
1053
    AllocatorTraits<A>::construct(allocator_b, a, std::move(*b));
1054
1055
    AllocatorTraits<A>::destroy(allocator_b, b);
1056
    AllocatorTraits<A>::construct(allocator_a, b, std::move(tmp));
1057
  }
1058
}
1059
1060
template <typename T, size_t N, typename A>
1061
void Storage<T, N, A>::SwapInlinedElements(MemcpyPolicy, Storage* other) {
1062
  Data tmp = data_;
1063
  data_ = other->data_;
1064
  other->data_ = tmp;
1065
}
1066
1067
template <typename T, size_t N, typename A>
1068
template <typename NotMemcpyPolicy>
1069
void Storage<T, N, A>::SwapInlinedElements(NotMemcpyPolicy policy,
1070
                                           Storage* other) {
1071
  // Note: `destroy` needs to use pre-swap allocator while `construct` -
1072
  // post-swap allocator. Allocators will be swapped later on outside of
1073
  // `SwapInlinedElements`.
1074
  Storage* small_ptr = this;
1075
  Storage* large_ptr = other;
1076
  if (small_ptr->GetSize() > large_ptr->GetSize()) {
1077
    std::swap(small_ptr, large_ptr);
1078
  }
1079
1080
  auto small_size = small_ptr->GetSize();
1081
  auto diff = large_ptr->GetSize() - small_size;
1082
  SwapN(policy, other, small_size);
1083
1084
  IteratorValueAdapter<A, MoveIterator<A>> move_values(
1085
      MoveIterator<A>(large_ptr->GetInlinedData() + small_size));
1086
1087
  ConstructElements<A>(large_ptr->GetAllocator(),
1088
                       small_ptr->GetInlinedData() + small_size, move_values,
1089
                       diff);
1090
1091
  DestroyAdapter<A>::DestroyElements(large_ptr->GetAllocator(),
1092
                                     large_ptr->GetInlinedData() + small_size,
1093
                                     diff);
1094
}
1095
1096
// End ignore "array-bounds"
1097
#if !defined(__clang__) && defined(__GNUC__)
1098
#pragma GCC diagnostic pop
1099
#endif
1100
1101
}  // namespace inlined_vector_internal
1102
ABSL_NAMESPACE_END
1103
}  // namespace absl
1104
1105
#endif  // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_H_