| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498 | // Copyright 2017 The Abseil Authors.//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at////      http://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License.//// -----------------------------------------------------------------------------// File: fixed_array.h// -----------------------------------------------------------------------------//// A `FixedArray<T>` represents a non-resizable array of `T` where the length of// the array can be determined at run-time. It is a good replacement for// non-standard and deprecated uses of `alloca()` and variable length arrays// within the GCC extension. (See// https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html).//// `FixedArray` allocates small arrays inline, keeping performance fast by// avoiding heap operations. It also helps reduce the chances of// accidentally overflowing your stack if large input is passed to// your function.#ifndef ABSL_CONTAINER_FIXED_ARRAY_H_#define ABSL_CONTAINER_FIXED_ARRAY_H_#include <algorithm>#include <array>#include <cassert>#include <cstddef>#include <initializer_list>#include <iterator>#include <limits>#include <memory>#include <new>#include <type_traits>#include "absl/algorithm/algorithm.h"#include "absl/base/dynamic_annotations.h"#include "absl/base/internal/throw_delegate.h"#include "absl/base/macros.h"#include "absl/base/optimization.h"#include "absl/base/port.h"#include "absl/memory/memory.h"namespace absl {constexpr static auto kFixedArrayUseDefault = static_cast<size_t>(-1);// -----------------------------------------------------------------------------// FixedArray// -----------------------------------------------------------------------------//// A `FixedArray` provides a run-time fixed-size array, allocating small arrays// inline for efficiency and correctness.//// Most users should not specify an `inline_elements` argument and let// `FixedArray<>` automatically determine the number of elements// to store inline based on `sizeof(T)`. If `inline_elements` is specified, the// `FixedArray<>` implementation will inline arrays of// length <= `inline_elements`.//// Note that a `FixedArray` constructed with a `size_type` argument will// default-initialize its values by leaving trivially constructible types// uninitialized (e.g. int, int[4], double), and others default-constructed.// This matches the behavior of c-style arrays and `std::array`, but not// `std::vector`.//// Note that `FixedArray` does not provide a public allocator; if it requires a// heap allocation, it will do so with global `::operator new[]()` and// `::operator delete[]()`, even if T provides class-scope overrides for these// operators.template <typename T, size_t inlined = kFixedArrayUseDefault>class FixedArray {  static constexpr size_t kInlineBytesDefault = 256;  // std::iterator_traits isn't guaranteed to be SFINAE-friendly until C++17,  // but this seems to be mostly pedantic.  template <typename Iter>  using EnableIfForwardIterator = typename std::enable_if<      std::is_convertible<          typename std::iterator_traits<Iter>::iterator_category,          std::forward_iterator_tag>::value,      int>::type; public:  // For playing nicely with stl:  using value_type = T;  using iterator = T*;  using const_iterator = const T*;  using reverse_iterator = std::reverse_iterator<iterator>;  using const_reverse_iterator = std::reverse_iterator<const_iterator>;  using reference = T&;  using const_reference = const T&;  using pointer = T*;  using const_pointer = const T*;  using difference_type = ptrdiff_t;  using size_type = size_t;  static constexpr size_type inline_elements =      inlined == kFixedArrayUseDefault          ? kInlineBytesDefault / sizeof(value_type)          : inlined;  FixedArray(const FixedArray& other) : rep_(other.begin(), other.end()) {}  FixedArray(FixedArray&& other) noexcept(  // clang-format off      absl::allocator_is_nothrow<std::allocator<value_type>>::value &&  // clang-format on          std::is_nothrow_move_constructible<value_type>::value)      : rep_(std::make_move_iterator(other.begin()),             std::make_move_iterator(other.end())) {}  // Creates an array object that can store `n` elements.  // Note that trivially constructible elements will be uninitialized.  explicit FixedArray(size_type n) : rep_(n) {}  // Creates an array initialized with `n` copies of `val`.  FixedArray(size_type n, const value_type& val) : rep_(n, val) {}  // Creates an array initialized with the elements from the input  // range. The array's size will always be `std::distance(first, last)`.  // REQUIRES: Iter must be a forward_iterator or better.  template <typename Iter, EnableIfForwardIterator<Iter> = 0>  FixedArray(Iter first, Iter last) : rep_(first, last) {}  // Creates the array from an initializer_list.  FixedArray(std::initializer_list<T> init_list)      : FixedArray(init_list.begin(), init_list.end()) {}  ~FixedArray() {}  // Assignments are deleted because they break the invariant that the size of a  // `FixedArray` never changes.  void operator=(FixedArray&&) = delete;  void operator=(const FixedArray&) = delete;  // FixedArray::size()  //  // Returns the length of the fixed array.  size_type size() const { return rep_.size(); }  // FixedArray::max_size()  //  // Returns the largest possible value of `std::distance(begin(), end())` for a  // `FixedArray<T>`. This is equivalent to the most possible addressable bytes  // over the number of bytes taken by T.  constexpr size_type max_size() const {    return std::numeric_limits<difference_type>::max() / sizeof(value_type);  }  // FixedArray::empty()  //  // Returns whether or not the fixed array is empty.  bool empty() const { return size() == 0; }  // FixedArray::memsize()  //  // Returns the memory size of the fixed array in bytes.  size_t memsize() const { return size() * sizeof(value_type); }  // FixedArray::data()  //  // Returns a const T* pointer to elements of the `FixedArray`. This pointer  // can be used to access (but not modify) the contained elements.  const_pointer data() const { return AsValue(rep_.begin()); }  // Overload of FixedArray::data() to return a T* pointer to elements of the  // fixed array. This pointer can be used to access and modify the contained  // elements.  pointer data() { return AsValue(rep_.begin()); }  // FixedArray::operator[]  //  // Returns a reference the ith element of the fixed array.  // REQUIRES: 0 <= i < size()  reference operator[](size_type i) {    assert(i < size());    return data()[i];  }  // Overload of FixedArray::operator()[] to return a const reference to the  // ith element of the fixed array.  // REQUIRES: 0 <= i < size()  const_reference operator[](size_type i) const {    assert(i < size());    return data()[i];  }  // FixedArray::at  //  // Bounds-checked access.  Returns a reference to the ith element of the  // fiexed array, or throws std::out_of_range  reference at(size_type i) {    if (ABSL_PREDICT_FALSE(i >= size())) {      base_internal::ThrowStdOutOfRange("FixedArray::at failed bounds check");    }    return data()[i];  }  // Overload of FixedArray::at() to return a const reference to the ith element  // of the fixed array.  const_reference at(size_type i) const {    if (i >= size()) {      base_internal::ThrowStdOutOfRange("FixedArray::at failed bounds check");    }    return data()[i];  }  // FixedArray::front()  //  // Returns a reference to the first element of the fixed array.  reference front() { return *begin(); }  // Overload of FixedArray::front() to return a reference to the first element  // of a fixed array of const values.  const_reference front() const { return *begin(); }  // FixedArray::back()  //  // Returns a reference to the last element of the fixed array.  reference back() { return *(end() - 1); }  // Overload of FixedArray::back() to return a reference to the last element  // of a fixed array of const values.  const_reference back() const { return *(end() - 1); }  // FixedArray::begin()  //  // Returns an iterator to the beginning of the fixed array.  iterator begin() { return data(); }  // Overload of FixedArray::begin() to return a const iterator to the  // beginning of the fixed array.  const_iterator begin() const { return data(); }  // FixedArray::cbegin()  //  // Returns a const iterator to the beginning of the fixed array.  const_iterator cbegin() const { return begin(); }  // FixedArray::end()  //  // Returns an iterator to the end of the fixed array.  iterator end() { return data() + size(); }  // Overload of FixedArray::end() to return a const iterator to the end of the  // fixed array.  const_iterator end() const { return data() + size(); }  // FixedArray::cend()  //  // Returns a const iterator to the end of the fixed array.  const_iterator cend() const { return end(); }  // FixedArray::rbegin()  //  // Returns a reverse iterator from the end of the fixed array.  reverse_iterator rbegin() { return reverse_iterator(end()); }  // Overload of FixedArray::rbegin() to return a const reverse iterator from  // the end of the fixed array.  const_reverse_iterator rbegin() const {    return const_reverse_iterator(end());  }  // FixedArray::crbegin()  //  // Returns a const reverse iterator from the end of the fixed array.  const_reverse_iterator crbegin() const { return rbegin(); }  // FixedArray::rend()  //  // Returns a reverse iterator from the beginning of the fixed array.  reverse_iterator rend() { return reverse_iterator(begin()); }  // Overload of FixedArray::rend() for returning a const reverse iterator  // from the beginning of the fixed array.  const_reverse_iterator rend() const {    return const_reverse_iterator(begin());  }  // FixedArray::crend()  //  // Returns a reverse iterator from the beginning of the fixed array.  const_reverse_iterator crend() const { return rend(); }  // FixedArray::fill()  //  // Assigns the given `value` to all elements in the fixed array.  void fill(const T& value) { std::fill(begin(), end(), value); }  // Relational operators. Equality operators are elementwise using  // `operator==`, while order operators order FixedArrays lexicographically.  friend bool operator==(const FixedArray& lhs, const FixedArray& rhs) {    return absl::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());  }  friend bool operator!=(const FixedArray& lhs, const FixedArray& rhs) {    return !(lhs == rhs);  }  friend bool operator<(const FixedArray& lhs, const FixedArray& rhs) {    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),                                        rhs.end());  }  friend bool operator>(const FixedArray& lhs, const FixedArray& rhs) {    return rhs < lhs;  }  friend bool operator<=(const FixedArray& lhs, const FixedArray& rhs) {    return !(rhs < lhs);  }  friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) {    return !(lhs < rhs);  } private:  // HolderTraits  //  // Wrapper to hold elements of type T for the case where T is an array type.  // If 'T' is an array type, HolderTraits::type is a struct with a 'T v;'.  // Otherwise, HolderTraits::type is simply 'T'.  //  // Maintainer's Note: The simpler solution would be to simply wrap T in a  // struct whether it's an array or not: 'struct Holder { T v; };', but  // that causes some paranoid diagnostics to misfire about uses of data(),  // believing that 'data()' (aka '&rep_.begin().v') is a pointer to a single  // element, rather than the packed array that it really is.  // e.g.:  //  //     FixedArray<char> buf(1);  //     sprintf(buf.data(), "foo");  //  //     error: call to int __builtin___sprintf_chk(etc...)  //     will always overflow destination buffer [-Werror]  //  class HolderTraits {    template <typename U>    struct SelectImpl {      using type = U;      static pointer AsValue(type* p) { return p; }    };    // Partial specialization for elements of array type.    template <typename U, size_t N>    struct SelectImpl<U[N]> {      struct Holder { U v[N]; };      using type = Holder;      static pointer AsValue(type* p) { return &p->v; }    };    using Impl = SelectImpl<value_type>;   public:    using type = typename Impl::type;    static pointer AsValue(type *p) { return Impl::AsValue(p); }    // TODO(billydonahue): fix the type aliasing violation    // this assertion hints at.    static_assert(sizeof(type) == sizeof(value_type),                  "Holder must be same size as value_type");  };  using Holder = typename HolderTraits::type;  static pointer AsValue(Holder *p) { return HolderTraits::AsValue(p); }  // InlineSpace  //  // Allocate some space, not an array of elements of type T, so that we can  // skip calling the T constructors and destructors for space we never use.  // How many elements should we store inline?  //   a. If not specified, use a default of kInlineBytesDefault bytes (This is  //   currently 256 bytes, which seems small enough to not cause stack overflow  //   or unnecessary stack pollution, while still allowing stack allocation for  //   reasonably long character arrays).  //   b. Never use 0 length arrays (not ISO C++)  //  template <size_type N, typename = void>  class InlineSpace {   public:    Holder* data() { return reinterpret_cast<Holder*>(space_.data()); }    void AnnotateConstruct(size_t n) const { Annotate(n, true); }    void AnnotateDestruct(size_t n) const { Annotate(n, false); }   private:#ifndef ADDRESS_SANITIZER    void Annotate(size_t, bool) const { }#else    void Annotate(size_t n, bool creating) const {      if (!n) return;      const void* bot = &left_redzone_;      const void* beg = space_.data();      const void* end = space_.data() + n;      const void* top = &right_redzone_ + 1;      // args: (beg, end, old_mid, new_mid)      if (creating) {        ANNOTATE_CONTIGUOUS_CONTAINER(beg, top, top, end);        ANNOTATE_CONTIGUOUS_CONTAINER(bot, beg, beg, bot);      } else {        ANNOTATE_CONTIGUOUS_CONTAINER(beg, top, end, top);        ANNOTATE_CONTIGUOUS_CONTAINER(bot, beg, bot, beg);      }    }#endif  // ADDRESS_SANITIZER    using Buffer =        typename std::aligned_storage<sizeof(Holder), alignof(Holder)>::type;    ADDRESS_SANITIZER_REDZONE(left_redzone_);    std::array<Buffer, N> space_;    ADDRESS_SANITIZER_REDZONE(right_redzone_);  };  // specialization when N = 0.  template <typename U>  class InlineSpace<0, U> {   public:    Holder* data() { return nullptr; }    void AnnotateConstruct(size_t) const {}    void AnnotateDestruct(size_t) const {}  };  // Rep  //  // A const Rep object holds FixedArray's size and data pointer.  //  class Rep : public InlineSpace<inline_elements> {   public:    Rep(size_type n, const value_type& val) : n_(n), p_(MakeHolder(n)) {      std::uninitialized_fill_n(p_, n, val);    }    explicit Rep(size_type n) : n_(n), p_(MakeHolder(n)) {      // Loop optimizes to nothing for trivially constructible T.      for (Holder* p = p_; p != p_ + n; ++p)        // Note: no parens: default init only.        // Also note '::' to avoid Holder class placement new operator.        ::new (static_cast<void*>(p)) Holder;    }    template <typename Iter>    Rep(Iter first, Iter last)        : n_(std::distance(first, last)), p_(MakeHolder(n_)) {      std::uninitialized_copy(first, last, AsValue(p_));    }    ~Rep() {      // Destruction must be in reverse order.      // Loop optimizes to nothing for trivially destructible T.      for (Holder* p = end(); p != begin();) (--p)->~Holder();      if (IsAllocated(size())) {        std::allocator<Holder>().deallocate(p_, n_);      } else {        this->AnnotateDestruct(size());      }    }    Holder* begin() const { return p_; }    Holder* end() const { return p_ + n_; }    size_type size() const { return n_; }   private:    Holder* MakeHolder(size_type n) {      if (IsAllocated(n)) {        return std::allocator<Holder>().allocate(n);      } else {        this->AnnotateConstruct(n);        return this->data();      }    }    bool IsAllocated(size_type n) const { return n > inline_elements; }    const size_type n_;    Holder* const p_;  };  // Data members  Rep rep_;};template <typename T, size_t N>constexpr size_t FixedArray<T, N>::inline_elements;template <typename T, size_t N>constexpr size_t FixedArray<T, N>::kInlineBytesDefault;}  // namespace absl#endif  // ABSL_CONTAINER_FIXED_ARRAY_H_
 |