diff options
Diffstat (limited to 'absl/container/fixed_array.h')
| -rw-r--r-- | absl/container/fixed_array.h | 493 |
1 files changed, 493 insertions, 0 deletions
diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h new file mode 100644 index 0000000..20bde27 --- /dev/null +++ b/absl/container/fixed_array.h @@ -0,0 +1,493 @@ +// 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" + +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; + + // 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) {} + + // Create the array from an initializer_list. + FixedArray(std::initializer_list<T> init_list) + : FixedArray(init_list.begin(), init_list.end()) {} + + ~FixedArray() {} + + // Copy and move construction and assignment are deleted because (1) you can't + // copy or move an array, (2) assignment breaks the invariant that the size of + // a `FixedArray` never changes, and (3) there's no clear answer as to what + // should happen to a moved-from `FixedArray`. + FixedArray(const 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())) { + ::operator delete[](begin()); + } 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 Allocate(n); + } else { + this->AnnotateConstruct(n); + return this->data(); + } + } + + Holder* Allocate(size_type n) { + return static_cast<Holder*>(::operator new[](n * sizeof(Holder))); + } + + 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_ |