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