blob: 1d05fd1d37abc5a9dc1fb89ae4c9e796de2efe61 [file] [log] [blame]
// Copyright 2020 The Pigweed 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
//
// https://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.
#pragma once
#include <algorithm>
#include <array>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <new>
#include <type_traits>
#include <utility>
#include "pw_assert/assert.h"
#include "pw_polyfill/language_feature_macros.h"
namespace pw {
namespace vector_impl {
template <typename I>
using IsIterator = std::negation<
std::is_same<typename std::iterator_traits<I>::value_type, void>>;
// Used as max_size in the generic-size Vector<T> interface.
PW_INLINE_VARIABLE constexpr size_t kGeneric = size_t(-1);
// The DestructorHelper is used to make Vector<T> trivially destructible if T
// is. This could be replaced with a C++20 constraint.
template <typename VectorClass, bool kIsTriviallyDestructible>
class DestructorHelper;
template <typename VectorClass>
class DestructorHelper<VectorClass, true> {
public:
~DestructorHelper() = default;
};
template <typename VectorClass>
class DestructorHelper<VectorClass, false> {
public:
~DestructorHelper() { static_cast<VectorClass*>(this)->clear(); }
};
} // namespace vector_impl
// The Vector class is similar to std::vector, except it is backed by a
// fixed-size buffer. Vectors must be declared with an explicit maximum size
// (e.g. Vector<int, 10>) but vectors can be used and referred to without the
// max size template parameter (e.g. Vector<int>).
//
// To allow referring to a pw::Vector without an explicit maximum size, all
// Vector classes inherit from Vector<T, vector_impl::kGeneric>, which stores
// the maximum size in a variable. This allows Vectors to be used without having
// to know their maximum size at compile time. It also keeps code size small
// since function implementations are shared for all maximum sizes.
template <typename T, size_t max_size = vector_impl::kGeneric>
class Vector : public Vector<T, vector_impl::kGeneric> {
public:
using typename Vector<T, vector_impl::kGeneric>::value_type;
using typename Vector<T, vector_impl::kGeneric>::size_type;
using typename Vector<T, vector_impl::kGeneric>::difference_type;
using typename Vector<T, vector_impl::kGeneric>::reference;
using typename Vector<T, vector_impl::kGeneric>::const_reference;
using typename Vector<T, vector_impl::kGeneric>::pointer;
using typename Vector<T, vector_impl::kGeneric>::const_pointer;
using typename Vector<T, vector_impl::kGeneric>::iterator;
using typename Vector<T, vector_impl::kGeneric>::const_iterator;
using typename Vector<T, vector_impl::kGeneric>::reverse_iterator;
using typename Vector<T, vector_impl::kGeneric>::const_reverse_iterator;
// Construct
Vector() noexcept : Vector<T, vector_impl::kGeneric>(max_size) {}
Vector(size_type count, const T& value)
: Vector<T, vector_impl::kGeneric>(max_size, count, value) {}
explicit Vector(size_type count)
: Vector<T, vector_impl::kGeneric>(max_size, count, T()) {}
template <
typename Iterator,
typename...,
typename = std::enable_if_t<vector_impl::IsIterator<Iterator>::value>>
Vector(Iterator first, Iterator last)
: Vector<T, vector_impl::kGeneric>(max_size, first, last) {}
Vector(const Vector& other)
: Vector<T, vector_impl::kGeneric>(max_size, other) {}
template <size_t kOtherMaxSize>
Vector(const Vector<T, kOtherMaxSize>& other)
: Vector<T, vector_impl::kGeneric>(max_size, other) {}
Vector(Vector&& other) noexcept
: Vector<T, vector_impl::kGeneric>(max_size, std::move(other)) {}
template <size_t kOtherMaxSize>
Vector(Vector<T, kOtherMaxSize>&& other) noexcept
: Vector<T, vector_impl::kGeneric>(max_size, std::move(other)) {}
Vector(std::initializer_list<T> list)
: Vector<T, vector_impl::kGeneric>(max_size, list) {}
Vector& operator=(const Vector& other) {
Vector<T>::assign(other.begin(), other.end());
return *this;
}
template <size_t kOtherMaxSize>
Vector& operator=(const Vector<T, kOtherMaxSize>& other) noexcept {
Vector<T>::assign(other.begin(), other.end());
return *this;
}
Vector& operator=(Vector&& other) noexcept {
Vector<T>::operator=(std::move(other));
return *this;
}
template <size_t kOtherMaxSize>
Vector& operator=(Vector<T, kOtherMaxSize>&& other) noexcept {
Vector<T>::operator=(std::move(other));
return *this;
}
Vector& operator=(std::initializer_list<T> list) {
this->assign(list.begin(), list.end());
return *this;
}
// All other vector methods are implemented on the Vector<T> base class.
private:
friend class Vector<T, vector_impl::kGeneric>;
static_assert(max_size <= std::numeric_limits<size_type>::max());
// Provides access to the underlying array as an array of T.
#ifdef __cpp_lib_launder
pointer array() { return std::launder(reinterpret_cast<T*>(&array_)); }
const_pointer array() const {
return std::launder(reinterpret_cast<const T*>(&array_));
}
#else
pointer array() { return reinterpret_cast<T*>(&array_); }
const_pointer array() const { return reinterpret_cast<const T*>(&array_); }
#endif // __cpp_lib_launder
// Vector entries are stored as uninitialized memory blocks aligned correctly
// for the type. Elements are initialized on demand with placement new.
//
// This uses std::array instead of a C array to support zero-length Vectors.
// Zero-length C arrays are non-standard, but std::array<T, 0> is valid.
// The alignas specifier is required ensure that a zero-length array is
// aligned the same as an array with elements.
alignas(T) std::array<std::aligned_storage_t<sizeof(T), alignof(T)>,
max_size> array_;
};
// Defines the generic-sized Vector<T> specialization, which serves as the base
// class for Vector<T> of any maximum size. Except for constructors, all Vector
// methods are implemented on this class.
template <typename T>
class Vector<T, vector_impl::kGeneric>
: public vector_impl::DestructorHelper<
Vector<T, vector_impl::kGeneric>,
std::is_trivially_destructible<T>::value> {
public:
using value_type = T;
// Use unsigned short instead of size_t. Since Vectors are statically
// allocated, 65535 entries is a reasonable upper limit. This reduces Vector's
// overhead by packing the size and capacity into 32 bits.
using size_type = unsigned short;
using difference_type = ptrdiff_t;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = T*;
using const_pointer = const 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>;
// A vector without an explicit maximum size (Vector<T>) cannot be constructed
// directly. Instead, construct a Vector<T, max_size>. Vectors of any max size
// can be used through a Vector<T> pointer or reference.
// Assign
Vector& operator=(const Vector& other) {
assign(other.begin(), other.end());
return *this;
}
Vector& operator=(Vector&& other) noexcept {
clear();
MoveFrom(other);
return *this;
}
Vector& operator=(std::initializer_list<T> list) {
assign(list);
return *this;
}
void assign(size_type count, const T& value) {
clear();
Append(count, value);
}
template <
typename Iterator,
typename...,
typename = std::enable_if_t<vector_impl::IsIterator<Iterator>::value>>
void assign(Iterator first, Iterator last) {
clear();
CopyFrom(first, last);
}
void assign(std::initializer_list<T> list) {
assign(list.begin(), list.end());
}
// Access
reference at(size_type index) {
PW_ASSERT(index < size());
return data()[index];
}
const_reference at(size_type index) const {
PW_ASSERT(index < size());
return data()[index];
}
reference operator[](size_type index) {
PW_DASSERT(index < size());
return data()[index];
}
const_reference operator[](size_type index) const {
PW_DASSERT(index < size());
return data()[index];
}
reference front() { return data()[0]; }
const_reference front() const { return data()[0]; }
reference back() { return data()[size() - 1]; }
const_reference back() const { return data()[size() - 1]; }
// The underlying data is not part of the generic-length vector class. It is
// provided in the derived class from which this instance was constructed. To
// access the data, down-cast this to a Vector with a known max size, and
// return a pointer to the start of the array, which is the same for all
// vectors with explicit max size.
T* data() noexcept { return static_cast<Vector<T, 0>*>(this)->array(); }
const T* data() const noexcept {
return static_cast<const Vector<T, 0>*>(this)->array();
}
// Iterate
iterator begin() noexcept { return &data()[0]; }
const_iterator begin() const noexcept { return &data()[0]; }
const_iterator cbegin() const noexcept { return &data()[0]; }
iterator end() noexcept { return &data()[size()]; }
const_iterator end() const noexcept { return &data()[size()]; }
const_iterator cend() const noexcept { return &data()[size()]; }
reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return reverse_iterator(end()); }
const_reverse_iterator crbegin() const noexcept {
return reverse_iterator(cend());
}
reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return reverse_iterator(begin()); }
const_reverse_iterator crend() const noexcept {
return reverse_iterator(cbegin());
}
// Size
[[nodiscard]] bool empty() const noexcept { return size() == 0u; }
// True if there is no free space in the vector. Operations that add elements
// (push_back, insert, etc.) will fail if full() is true.
[[nodiscard]] bool full() const noexcept { return size() == max_size(); }
// Returns the number of elements in the Vector. Uses size_t instead of
// size_type for consistency with other containers.
size_t size() const noexcept { return size_; }
// Returns the maximum number of elements in this Vector.
size_t max_size() const noexcept { return max_size_; }
size_t capacity() const noexcept { return max_size(); }
// Modify
void clear() noexcept;
// TODO(hepler): insert, emplace, and erase are not yet implemented.
// Currently, items can only be added to or removed from the end.
iterator insert(const_iterator index, const T& value);
iterator insert(const_iterator index, T&& value);
iterator insert(const_iterator index, size_type count, const T& value);
template <typename Iterator>
iterator insert(const_iterator index, Iterator first, Iterator last);
iterator insert(const_iterator index, std::initializer_list<T> list);
template <typename... Args>
iterator emplace(const_iterator index, Args&&... args);
iterator erase(const_iterator index);
iterator erase(const_iterator first, const_iterator last);
void push_back(const T& value) { emplace_back(value); }
void push_back(T&& value) { emplace_back(std::move(value)); }
template <typename... Args>
void emplace_back(Args&&... args);
void pop_back();
void resize(size_type new_size) { resize(new_size, T()); }
void resize(size_type new_size, const T& value);
protected:
// Vectors without an explicit size cannot be constructed directly. Instead,
// the maximum size must be provided.
explicit constexpr Vector(size_type max_size) noexcept
: max_size_(max_size) {}
Vector(size_type max_size, size_type count, const T& value)
: Vector(max_size) {
Append(count, value);
}
Vector(size_type max_size, size_type count) : Vector(max_size, count, T()) {}
template <
typename Iterator,
typename...,
typename = std::enable_if_t<vector_impl::IsIterator<Iterator>::value>>
Vector(size_type max_size, Iterator first, Iterator last) : Vector(max_size) {
CopyFrom(first, last);
}
Vector(size_type max_size, const Vector& other) : Vector(max_size) {
CopyFrom(other.begin(), other.end());
}
Vector(size_type max_size, Vector&& other) noexcept : Vector(max_size) {
MoveFrom(other);
}
Vector(size_type max_size, std::initializer_list<T> list) : Vector(max_size) {
CopyFrom(list.begin(), list.end());
}
private:
template <typename Iterator>
void CopyFrom(Iterator first, Iterator last);
void MoveFrom(Vector& other) noexcept;
void Append(size_type count, const T& value);
const size_type max_size_;
size_type size_ = 0;
};
// Compare
template <typename T, size_t kLhsSize, size_t kRhsSize>
bool operator==(const Vector<T, kLhsSize>& lhs,
const Vector<T, kRhsSize>& rhs) {
return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
template <typename T, size_t kLhsSize, size_t kRhsSize>
bool operator!=(const Vector<T, kLhsSize>& lhs,
const Vector<T, kRhsSize>& rhs) {
return !(lhs == rhs);
}
template <typename T, size_t kLhsSize, size_t kRhsSize>
bool operator<(const Vector<T, kLhsSize>& lhs, const Vector<T, kRhsSize>& rhs) {
return std::lexicographical_compare(
lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
template <typename T, size_t kLhsSize, size_t kRhsSize>
bool operator<=(const Vector<T, kLhsSize>& lhs,
const Vector<T, kRhsSize>& rhs) {
return !(rhs < lhs);
}
template <typename T, size_t kLhsSize, size_t kRhsSize>
bool operator>(const Vector<T, kLhsSize>& lhs, const Vector<T, kRhsSize>& rhs) {
return rhs < lhs;
}
template <typename T, size_t kLhsSize, size_t kRhsSize>
bool operator>=(const Vector<T, kLhsSize>& lhs,
const Vector<T, kRhsSize>& rhs) {
return !(lhs < rhs);
}
// Function implementations
template <typename T>
void Vector<T, vector_impl::kGeneric>::clear() noexcept {
for (auto& item : *this) {
item.~T();
}
size_ = 0;
}
template <typename T>
template <typename... Args>
void Vector<T, vector_impl::kGeneric>::emplace_back(Args&&... args) {
if (!full()) {
new (&data()[size_]) T(std::forward<Args>(args)...);
size_ += 1;
}
}
template <typename T>
void Vector<T, vector_impl::kGeneric>::pop_back() {
if (!empty()) {
back().~T();
size_ -= 1;
}
}
template <typename T>
void Vector<T, vector_impl::kGeneric>::resize(size_type new_size,
const T& value) {
if (size() < new_size) {
Append(std::min(max_size(), size_t(new_size)) - size(), value);
} else {
while (size() > new_size) {
pop_back();
}
}
}
template <typename T>
template <typename Iterator>
void Vector<T, vector_impl::kGeneric>::CopyFrom(Iterator first, Iterator last) {
while (first != last) {
push_back(*first++);
}
}
template <typename T>
void Vector<T, vector_impl::kGeneric>::MoveFrom(Vector& other) noexcept {
for (auto&& item : other) {
emplace_back(std::move(item));
}
other.clear();
}
template <typename T>
void Vector<T, vector_impl::kGeneric>::Append(size_type count, const T& value) {
for (size_t i = 0; i < count; ++i) {
push_back(value);
}
}
} // namespace pw