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// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// -----------------------------------------------------------------------------
16// File: fixed_array.h
17// -----------------------------------------------------------------------------
18//
19// A `FixedArray<T>` represents a non-resizable array of `T` where the length of
20// the array can be determined at run-time. It is a good replacement for
21// non-standard and deprecated uses of `alloca()` and variable length arrays
22// within the GCC extension. (See
23// https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html).
24//
25// `FixedArray` allocates small arrays inline, keeping performance fast by
26// avoiding heap operations. It also helps reduce the chances of
27// accidentally overflowing your stack if large input is passed to
28// your function.
29
30#ifndef ABSL_CONTAINER_FIXED_ARRAY_H_
31#define ABSL_CONTAINER_FIXED_ARRAY_H_
32
33#include <algorithm>
34#include <array>
35#include <cassert>
36#include <cstddef>
37#include <initializer_list>
38#include <iterator>
39#include <limits>
40#include <memory>
41#include <new>
42#include <type_traits>
43
44#include "absl/algorithm/algorithm.h"
45#include "absl/base/dynamic_annotations.h"
46#include "absl/base/internal/throw_delegate.h"
47#include "absl/base/macros.h"
48#include "absl/base/optimization.h"
49#include "absl/base/port.h"
50#include "absl/container/internal/compressed_tuple.h"
51#include "absl/memory/memory.h"
52
53namespace absl {
54
55constexpr static auto kFixedArrayUseDefault = static_cast<size_t>(-1);
56
57// -----------------------------------------------------------------------------
58// FixedArray
59// -----------------------------------------------------------------------------
60//
61// A `FixedArray` provides a run-time fixed-size array, allocating a small array
62// inline for efficiency.
63//
64// Most users should not specify an `inline_elements` argument and let
65// `FixedArray` automatically determine the number of elements
66// to store inline based on `sizeof(T)`. If `inline_elements` is specified, the
67// `FixedArray` implementation will use inline storage for arrays with a
68// length <= `inline_elements`.
69//
70// Note that a `FixedArray` constructed with a `size_type` argument will
71// default-initialize its values by leaving trivially constructible types
72// uninitialized (e.g. int, int[4], double), and others default-constructed.
73// This matches the behavior of c-style arrays and `std::array`, but not
74// `std::vector`.
75//
76// Note that `FixedArray` does not provide a public allocator; if it requires a
77// heap allocation, it will do so with global `::operator new[]()` and
78// `::operator delete[]()`, even if T provides class-scope overrides for these
79// operators.
80template <typename T, size_t N = kFixedArrayUseDefault,
81 typename A = std::allocator<T>>
82class FixedArray {
83 static_assert(!std::is_array<T>::value || std::extent<T>::value > 0,
84 "Arrays with unknown bounds cannot be used with FixedArray.");
85
86 static constexpr size_t kInlineBytesDefault = 256;
87
88 using AllocatorTraits = std::allocator_traits<A>;
89 // std::iterator_traits isn't guaranteed to be SFINAE-friendly until C++17,
90 // but this seems to be mostly pedantic.
91 template <typename Iterator>
92 using EnableIfForwardIterator = absl::enable_if_t<std::is_convertible<
93 typename std::iterator_traits<Iterator>::iterator_category,
94 std::forward_iterator_tag>::value>;
95 static constexpr bool NoexceptCopyable() {
96 return std::is_nothrow_copy_constructible<StorageElement>::value &&
97 absl::allocator_is_nothrow<allocator_type>::value;
98 }
99 static constexpr bool NoexceptMovable() {
100 return std::is_nothrow_move_constructible<StorageElement>::value &&
101 absl::allocator_is_nothrow<allocator_type>::value;
102 }
103 static constexpr bool DefaultConstructorIsNonTrivial() {
104 return !absl::is_trivially_default_constructible<StorageElement>::value;
105 }
106
107 public:
108 using allocator_type = typename AllocatorTraits::allocator_type;
109 using value_type = typename allocator_type::value_type;
110 using pointer = typename allocator_type::pointer;
111 using const_pointer = typename allocator_type::const_pointer;
112 using reference = typename allocator_type::reference;
113 using const_reference = typename allocator_type::const_reference;
114 using size_type = typename allocator_type::size_type;
115 using difference_type = typename allocator_type::difference_type;
116 using iterator = pointer;
117 using const_iterator = const_pointer;
118 using reverse_iterator = std::reverse_iterator<iterator>;
119 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
120
121 static constexpr size_type inline_elements =
122 (N == kFixedArrayUseDefault ? kInlineBytesDefault / sizeof(value_type)
123 : static_cast<size_type>(N));
124
125 FixedArray(
126 const FixedArray& other,
127 const allocator_type& a = allocator_type()) noexcept(NoexceptCopyable())
128 : FixedArray(other.begin(), other.end(), a) {}
129
130 FixedArray(
131 FixedArray&& other,
132 const allocator_type& a = allocator_type()) noexcept(NoexceptMovable())
133 : FixedArray(std::make_move_iterator(other.begin()),
134 std::make_move_iterator(other.end()), a) {}
135
136 // Creates an array object that can store `n` elements.
137 // Note that trivially constructible elements will be uninitialized.
138 explicit FixedArray(size_type n, const allocator_type& a = allocator_type())
139 : storage_(n, a) {
140 if (DefaultConstructorIsNonTrivial()) {
141 memory_internal::ConstructRange(storage_.alloc(), storage_.begin(),
142 storage_.end());
143 }
144 }
145
146 // Creates an array initialized with `n` copies of `val`.
147 FixedArray(size_type n, const value_type& val,
148 const allocator_type& a = allocator_type())
149 : storage_(n, a) {
150 memory_internal::ConstructRange(storage_.alloc(), storage_.begin(),
151 storage_.end(), val);
152 }
153
154 // Creates an array initialized with the size and contents of `init_list`.
155 FixedArray(std::initializer_list<value_type> init_list,
156 const allocator_type& a = allocator_type())
157 : FixedArray(init_list.begin(), init_list.end(), a) {}
158
159 // Creates an array initialized with the elements from the input
160 // range. The array's size will always be `std::distance(first, last)`.
161 // REQUIRES: Iterator must be a forward_iterator or better.
162 template <typename Iterator, EnableIfForwardIterator<Iterator>* = nullptr>
163 FixedArray(Iterator first, Iterator last,
164 const allocator_type& a = allocator_type())
165 : storage_(std::distance(first, last), a) {
166 memory_internal::CopyRange(storage_.alloc(), storage_.begin(), first, last);
167 }
168
169 ~FixedArray() noexcept {
170 for (auto* cur = storage_.begin(); cur != storage_.end(); ++cur) {
171 AllocatorTraits::destroy(storage_.alloc(), cur);
172 }
173 }
174
175 // Assignments are deleted because they break the invariant that the size of a
176 // `FixedArray` never changes.
177 void operator=(FixedArray&&) = delete;
178 void operator=(const FixedArray&) = delete;
179
180 // FixedArray::size()
181 //
182 // Returns the length of the fixed array.
183 size_type size() const { return storage_.size(); }
184
185 // FixedArray::max_size()
186 //
187 // Returns the largest possible value of `std::distance(begin(), end())` for a
188 // `FixedArray<T>`. This is equivalent to the most possible addressable bytes
189 // over the number of bytes taken by T.
190 constexpr size_type max_size() const {
191 return (std::numeric_limits<difference_type>::max)() / sizeof(value_type);
192 }
193
194 // FixedArray::empty()
195 //
196 // Returns whether or not the fixed array is empty.
197 bool empty() const { return size() == 0; }
198
199 // FixedArray::memsize()
200 //
201 // Returns the memory size of the fixed array in bytes.
202 size_t memsize() const { return size() * sizeof(value_type); }
203
204 // FixedArray::data()
205 //
206 // Returns a const T* pointer to elements of the `FixedArray`. This pointer
207 // can be used to access (but not modify) the contained elements.
208 const_pointer data() const { return AsValueType(storage_.begin()); }
209
210 // Overload of FixedArray::data() to return a T* pointer to elements of the
211 // fixed array. This pointer can be used to access and modify the contained
212 // elements.
213 pointer data() { return AsValueType(storage_.begin()); }
214
215 // FixedArray::operator[]
216 //
217 // Returns a reference the ith element of the fixed array.
218 // REQUIRES: 0 <= i < size()
219 reference operator[](size_type i) {
220 assert(i < size());
221 return data()[i];
222 }
223
224 // Overload of FixedArray::operator()[] to return a const reference to the
225 // ith element of the fixed array.
226 // REQUIRES: 0 <= i < size()
227 const_reference operator[](size_type i) const {
228 assert(i < size());
229 return data()[i];
230 }
231
232 // FixedArray::at
233 //
234 // Bounds-checked access. Returns a reference to the ith element of the
235 // fiexed array, or throws std::out_of_range
236 reference at(size_type i) {
237 if (ABSL_PREDICT_FALSE(i >= size())) {
238 base_internal::ThrowStdOutOfRange("FixedArray::at failed bounds check");
239 }
240 return data()[i];
241 }
242
243 // Overload of FixedArray::at() to return a const reference to the ith element
244 // of the fixed array.
245 const_reference at(size_type i) const {
246 if (ABSL_PREDICT_FALSE(i >= size())) {
247 base_internal::ThrowStdOutOfRange("FixedArray::at failed bounds check");
248 }
249 return data()[i];
250 }
251
252 // FixedArray::front()
253 //
254 // Returns a reference to the first element of the fixed array.
255 reference front() { return *begin(); }
256
257 // Overload of FixedArray::front() to return a reference to the first element
258 // of a fixed array of const values.
259 const_reference front() const { return *begin(); }
260
261 // FixedArray::back()
262 //
263 // Returns a reference to the last element of the fixed array.
264 reference back() { return *(end() - 1); }
265
266 // Overload of FixedArray::back() to return a reference to the last element
267 // of a fixed array of const values.
268 const_reference back() const { return *(end() - 1); }
269
270 // FixedArray::begin()
271 //
272 // Returns an iterator to the beginning of the fixed array.
273 iterator begin() { return data(); }
274
275 // Overload of FixedArray::begin() to return a const iterator to the
276 // beginning of the fixed array.
277 const_iterator begin() const { return data(); }
278
279 // FixedArray::cbegin()
280 //
281 // Returns a const iterator to the beginning of the fixed array.
282 const_iterator cbegin() const { return begin(); }
283
284 // FixedArray::end()
285 //
286 // Returns an iterator to the end of the fixed array.
287 iterator end() { return data() + size(); }
288
289 // Overload of FixedArray::end() to return a const iterator to the end of the
290 // fixed array.
291 const_iterator end() const { return data() + size(); }
292
293 // FixedArray::cend()
294 //
295 // Returns a const iterator to the end of the fixed array.
296 const_iterator cend() const { return end(); }
297
298 // FixedArray::rbegin()
299 //
300 // Returns a reverse iterator from the end of the fixed array.
301 reverse_iterator rbegin() { return reverse_iterator(end()); }
302
303 // Overload of FixedArray::rbegin() to return a const reverse iterator from
304 // the end of the fixed array.
305 const_reverse_iterator rbegin() const {
306 return const_reverse_iterator(end());
307 }
308
309 // FixedArray::crbegin()
310 //
311 // Returns a const reverse iterator from the end of the fixed array.
312 const_reverse_iterator crbegin() const { return rbegin(); }
313
314 // FixedArray::rend()
315 //
316 // Returns a reverse iterator from the beginning of the fixed array.
317 reverse_iterator rend() { return reverse_iterator(begin()); }
318
319 // Overload of FixedArray::rend() for returning a const reverse iterator
320 // from the beginning of the fixed array.
321 const_reverse_iterator rend() const {
322 return const_reverse_iterator(begin());
323 }
324
325 // FixedArray::crend()
326 //
327 // Returns a reverse iterator from the beginning of the fixed array.
328 const_reverse_iterator crend() const { return rend(); }
329
330 // FixedArray::fill()
331 //
332 // Assigns the given `value` to all elements in the fixed array.
333 void fill(const value_type& val) { std::fill(begin(), end(), val); }
334
335 // Relational operators. Equality operators are elementwise using
336 // `operator==`, while order operators order FixedArrays lexicographically.
337 friend bool operator==(const FixedArray& lhs, const FixedArray& rhs) {
338 return absl::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
339 }
340
341 friend bool operator!=(const FixedArray& lhs, const FixedArray& rhs) {
342 return !(lhs == rhs);
343 }
344
345 friend bool operator<(const FixedArray& lhs, const FixedArray& rhs) {
346 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
347 rhs.end());
348 }
349
350 friend bool operator>(const FixedArray& lhs, const FixedArray& rhs) {
351 return rhs < lhs;
352 }
353
354 friend bool operator<=(const FixedArray& lhs, const FixedArray& rhs) {
355 return !(rhs < lhs);
356 }
357
358 friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) {
359 return !(lhs < rhs);
360 }
361
362 template <typename H>
363 friend H AbslHashValue(H h, const FixedArray& v) {
364 return H::combine(H::combine_contiguous(std::move(h), v.data(), v.size()),
365 v.size());
366 }
367
368 private:
369 // StorageElement
370 //
371 // For FixedArrays with a C-style-array value_type, StorageElement is a POD
372 // wrapper struct called StorageElementWrapper that holds the value_type
373 // instance inside. This is needed for construction and destruction of the
374 // entire array regardless of how many dimensions it has. For all other cases,
375 // StorageElement is just an alias of value_type.
376 //
377 // Maintainer's Note: The simpler solution would be to simply wrap value_type
378 // in a struct whether it's an array or not. That causes some paranoid
379 // diagnostics to misfire, believing that 'data()' returns a pointer to a
380 // single element, rather than the packed array that it really is.
381 // e.g.:
382 //
383 // FixedArray<char> buf(1);
384 // sprintf(buf.data(), "foo");
385 //
386 // error: call to int __builtin___sprintf_chk(etc...)
387 // will always overflow destination buffer [-Werror]
388 //
389 template <typename OuterT = value_type,
390 typename InnerT = absl::remove_extent_t<OuterT>,
391 size_t InnerN = std::extent<OuterT>::value>
392 struct StorageElementWrapper {
393 InnerT array[InnerN];
394 };
395
396 using StorageElement =
397 absl::conditional_t<std::is_array<value_type>::value,
398 StorageElementWrapper<value_type>, value_type>;
399 using StorageElementBuffer =
400 absl::aligned_storage_t<sizeof(StorageElement), alignof(StorageElement)>;
401
402 static pointer AsValueType(pointer ptr) { return ptr; }
403 static pointer AsValueType(StorageElementWrapper<value_type>* ptr) {
404 return std::addressof(ptr->array);
405 }
406
407 static_assert(sizeof(StorageElement) == sizeof(value_type), "");
408 static_assert(alignof(StorageElement) == alignof(value_type), "");
409
410 struct NonEmptyInlinedStorage {
411 StorageElement* data() {
412 return reinterpret_cast<StorageElement*>(inlined_storage_.data());
413 }
414
415#ifdef ADDRESS_SANITIZER
416 void* RedzoneBegin() { return &redzone_begin_; }
417 void* RedzoneEnd() { return &redzone_end_ + 1; }
418#endif // ADDRESS_SANITIZER
419
420 void AnnotateConstruct(size_type);
421 void AnnotateDestruct(size_type);
422
423 ADDRESS_SANITIZER_REDZONE(redzone_begin_);
424 std::array<StorageElementBuffer, inline_elements> inlined_storage_;
425 ADDRESS_SANITIZER_REDZONE(redzone_end_);
426 };
427
428 struct EmptyInlinedStorage {
429 StorageElement* data() { return nullptr; }
430 void AnnotateConstruct(size_type) {}
431 void AnnotateDestruct(size_type) {}
432 };
433
434 using InlinedStorage =
435 absl::conditional_t<inline_elements == 0, EmptyInlinedStorage,
436 NonEmptyInlinedStorage>;
437
438 // Storage
439 //
440 // An instance of Storage manages the inline and out-of-line memory for
441 // instances of FixedArray. This guarantees that even when construction of
442 // individual elements fails in the FixedArray constructor body, the
443 // destructor for Storage will still be called and out-of-line memory will be
444 // properly deallocated.
445 //
446 class Storage : public InlinedStorage {
447 public:
448 Storage(size_type n, const allocator_type& a)
449 : size_alloc_(n, a), data_(InitializeData()) {}
450
451 ~Storage() noexcept {
452 if (UsingInlinedStorage(size())) {
453 InlinedStorage::AnnotateDestruct(size());
454 } else {
455 AllocatorTraits::deallocate(alloc(), AsValueType(begin()), size());
456 }
457 }
458
459 size_type size() const { return size_alloc_.template get<0>(); }
460 StorageElement* begin() const { return data_; }
461 StorageElement* end() const { return begin() + size(); }
462 allocator_type& alloc() {
463 return size_alloc_.template get<1>();
464 }
465
466 private:
467 static bool UsingInlinedStorage(size_type n) {
468 return n <= inline_elements;
469 }
470
471 StorageElement* InitializeData() {
472 if (UsingInlinedStorage(size())) {
473 InlinedStorage::AnnotateConstruct(size());
474 return InlinedStorage::data();
475 } else {
476 return reinterpret_cast<StorageElement*>(
477 AllocatorTraits::allocate(alloc(), size()));
478 }
479 }
480
481 // `CompressedTuple` takes advantage of EBCO for stateless `allocator_type`s
482 container_internal::CompressedTuple<size_type, allocator_type> size_alloc_;
483 StorageElement* data_;
484 };
485
486 Storage storage_;
487};
488
489template <typename T, size_t N, typename A>
490constexpr size_t FixedArray<T, N, A>::kInlineBytesDefault;
491
492template <typename T, size_t N, typename A>
493constexpr typename FixedArray<T, N, A>::size_type
494 FixedArray<T, N, A>::inline_elements;
495
496template <typename T, size_t N, typename A>
497void FixedArray<T, N, A>::NonEmptyInlinedStorage::AnnotateConstruct(
498 typename FixedArray<T, N, A>::size_type n) {
499#ifdef ADDRESS_SANITIZER
500 if (!n) return;
501 ANNOTATE_CONTIGUOUS_CONTAINER(data(), RedzoneEnd(), RedzoneEnd(), data() + n);
502 ANNOTATE_CONTIGUOUS_CONTAINER(RedzoneBegin(), data(), data(), RedzoneBegin());
503#endif // ADDRESS_SANITIZER
504 static_cast<void>(n); // Mark used when not in asan mode
505}
506
507template <typename T, size_t N, typename A>
508void FixedArray<T, N, A>::NonEmptyInlinedStorage::AnnotateDestruct(
509 typename FixedArray<T, N, A>::size_type n) {
510#ifdef ADDRESS_SANITIZER
511 if (!n) return;
512 ANNOTATE_CONTIGUOUS_CONTAINER(data(), RedzoneEnd(), data() + n, RedzoneEnd());
513 ANNOTATE_CONTIGUOUS_CONTAINER(RedzoneBegin(), data(), RedzoneBegin(), data());
514#endif // ADDRESS_SANITIZER
515 static_cast<void>(n); // Mark used when not in asan mode
516}
517} // namespace absl
518
519#endif // ABSL_CONTAINER_FIXED_ARRAY_H_
520