chromium/third_party/angle/src/common/FastVector.h

//
// Copyright 2018 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// FastVector.h:
//   A vector class with a initial fixed size and variable growth.
//   Based on FixedVector.
//

#ifndef COMMON_FASTVECTOR_H_
#define COMMON_FASTVECTOR_H_

#include "bitset_utils.h"
#include "common/debug.h"

#include <algorithm>
#include <array>
#include <cstring>
#include <initializer_list>
#include <iterator>

namespace angle
{

template <class Iter>
class WrapIter
{ … };

template <class T, size_t N, class Storage = std::array<T, N>>
class FastVector final
{
  public:
    using value_type      = typename Storage::value_type;
    using size_type       = typename Storage::size_type;
    using reference       = typename Storage::reference;
    using const_reference = typename Storage::const_reference;
    using pointer         = typename Storage::pointer;
    using const_pointer   = typename Storage::const_pointer;
    using iterator        = WrapIter<T *>;
    using const_iterator  = WrapIter<const T *>;

    // This class does not call destructors when resizing down (for performance reasons).
    static_assert(std::is_trivially_destructible_v<value_type>);

    FastVector();
    FastVector(size_type count, const value_type &value);
    FastVector(size_type count);

    FastVector(const FastVector<T, N, Storage> &other);
    FastVector(FastVector<T, N, Storage> &&other);
    FastVector(std::initializer_list<value_type> init);

    template <class InputIt, std::enable_if_t<!std::is_integral<InputIt>::value, bool> = true>
    FastVector(InputIt first, InputIt last);

    FastVector<T, N, Storage> &operator=(const FastVector<T, N, Storage> &other);
    FastVector<T, N, Storage> &operator=(FastVector<T, N, Storage> &&other);
    FastVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);

    ~FastVector();

    reference at(size_type pos);
    const_reference at(size_type pos) const;

    reference operator[](size_type pos);
    const_reference operator[](size_type pos) const;

    pointer data();
    const_pointer data() const;

    iterator begin();
    const_iterator begin() const;

    iterator end();
    const_iterator end() const;

    bool empty() const;
    size_type size() const;

    void clear();

    void push_back(const value_type &value);
    void push_back(value_type &&value);

    template <typename... Args>
    void emplace_back(Args &&...args);

    void pop_back();

    reference front();
    const_reference front() const;

    reference back();
    const_reference back() const;

    void swap(FastVector<T, N, Storage> &other);
    void resetWithRawData(size_type count, const uint8_t *data);

    void resize(size_type count);
    void resize(size_type count, const value_type &value);

    // Only for use with non trivially constructible types.
    // When increasing size, new elements may have previous values. Use with caution in cases when
    // initialization of new elements is not required (will be explicitly initialized later), or
    // is never resizing down (not possible to reuse previous values).
    void resize_maybe_value_reuse(size_type count);
    // Only for use with non trivially constructible types.
    // No new elements added, so this function is safe to use. Generates ASSERT() if try resize up.
    void resize_down(size_type count);

    void reserve(size_type count);

    // Specialty function that removes a known element and might shuffle the list.
    void remove_and_permute(const value_type &element);
    void remove_and_permute(iterator pos);

  private:
    void assign_from_initializer_list(std::initializer_list<value_type> init);
    void ensure_capacity(size_t capacity);
    bool uses_fixed_storage() const;
    void resize_impl(size_type count);

    Storage mFixedStorage;
    pointer mData           = mFixedStorage.data();
    size_type mSize         = 0;
    size_type mReservedSize = N;
};

template <class T, size_t N, class StorageN, size_t M, class StorageM>
bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
{ … }

template <class T, size_t N, class StorageN, size_t M, class StorageM>
bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector()
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(size_type count)
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
    : … { … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : … { … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
{ … }

template <class T, size_t N, class Storage>
template <class InputIt, std::enable_if_t<!std::is_integral<InputIt>::value, bool>>
FastVector<T, N, Storage>::FastVector(InputIt first, InputIt last)
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
    const FastVector<T, N, Storage> &other)
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
    std::initializer_list<value_type> init)
{ … }

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::~FastVector()
{ … }

template <class T, size_t N, class Storage>
typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
{ … }

template <class T, size_t N, class Storage>
typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
    size_type pos) const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
    size_type pos)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference
FastVector<T, N, Storage>::operator[](size_type pos) const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_pointer
angle::FastVector<T, N, Storage>::data() const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
    const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
    const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::clear()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
{ … }

template <class T, size_t N, class Storage>
template <typename... Args>
ANGLE_INLINE void FastVector<T, N, Storage>::emplace_back(Args &&...args)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
    const
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
    const
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::resetWithRawData(size_type count, const uint8_t *data)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::resize(size_type count)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::resize_maybe_value_reuse(size_type count)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::resize_down(size_type count)
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::resize_impl(size_type count)
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::reserve(size_type count)
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
{ … }

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(iterator pos)
{ … }

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
{ … }

template <class Value, size_t N, class Storage = FastVector<Value, N>>
class FastMap final
{
  public:
    using value_type      = typename Storage::value_type;
    using size_type       = typename Storage::size_type;
    using reference       = typename Storage::reference;
    using const_reference = typename Storage::const_reference;
    using pointer         = typename Storage::pointer;
    using const_pointer   = typename Storage::const_pointer;
    using iterator        = typename Storage::iterator;
    using const_iterator  = typename Storage::const_iterator;

    FastMap() { … }
    ~FastMap() { … }

    Value &operator[](uint32_t key)
    { … }

    const Value &operator[](uint32_t key) const { … }

    Value &at(uint32_t key)
    { … }

    const Value &at(uint32_t key) const
    { … }

    void clear() { … }

    void resetWithRawData(size_type count, const uint8_t *data)
    { … }

    bool empty() const { … }
    size_t size() const { … }

    const Value *data() const { … }

    bool operator==(const FastMap<Value, N> &other) const
    { … }

    iterator begin() { … }
    const_iterator begin() const { … }

    iterator end() { … }
    const_iterator end() const { … }

  private:
    FastVector<Value, N> mData;
};

template <class Key, class Value, size_t N>
class FlatUnorderedMap final
{ … };

template <class T, size_t N>
class FlatUnorderedSet final
{ … };
}  // namespace angle

#endif  // COMMON_FASTVECTOR_H_