legacy-libs/grpc-cloned/deps/grpc/third_party/abseil-cpp/absl/container/fixed_array.h

   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
  53 namespace absl {
  54
  55 constexpr 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.
  80 template <typename T, size_t N = kFixedArrayUseDefault,
  81           typename A = std::allocator<T>>
  82 class 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
 489 template <typename T, size_t N, typename A>
 490 constexpr size_t FixedArray<T, N, A>::kInlineBytesDefault;
 491
 492 template <typename T, size_t N, typename A>
 493 constexpr typename FixedArray<T, N, A>::size_type
 494     FixedArray<T, N, A>::inline_elements;
 495
 496 template <typename T, size_t N, typename A>
 497 void 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
 507 template <typename T, size_t N, typename A>
 508 void 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_