tor-browser

FastVector.h (22966B)

---

//
// 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 <initializer_list>
#include <iterator>

namespace angle
{

template <class Iter>
class WrapIter
{
 public:
   typedef Iter iterator_type;
   typedef typename std::iterator_traits<iterator_type>::value_type value_type;
   typedef typename std::iterator_traits<iterator_type>::difference_type difference_type;
   typedef typename std::iterator_traits<iterator_type>::pointer pointer;
   typedef typename std::iterator_traits<iterator_type>::reference reference;
   typedef typename std::iterator_traits<iterator_type>::iterator_category iterator_category;

   WrapIter() : mIter() {}
   WrapIter(const Iter &iter) : mIter(iter) {}
   ~WrapIter() = default;

   WrapIter &operator=(const WrapIter &x)
   {
       mIter = x.mIter;
       return *this;
   }

   bool operator==(const WrapIter &x) const { return mIter == x.mIter; }
   bool operator!=(const WrapIter &x) const { return mIter != x.mIter; }
   bool operator<(const WrapIter &x) const { return mIter < x.mIter; }
   bool operator<=(const WrapIter &x) const { return mIter <= x.mIter; }
   bool operator>(const WrapIter &x) const { return mIter > x.mIter; }
   bool operator>=(const WrapIter &x) const { return mIter >= x.mIter; }

   WrapIter &operator++()
   {
       mIter++;
       return *this;
   }

   WrapIter operator++(int)
   {
       WrapIter tmp(mIter);
       mIter++;
       return tmp;
   }

   WrapIter operator+(difference_type n)
   {
       WrapIter tmp(mIter);
       tmp.mIter += n;
       return tmp;
   }

   WrapIter operator-(difference_type n)
   {
       WrapIter tmp(mIter);
       tmp.mIter -= n;
       return tmp;
   }

   difference_type operator-(const WrapIter &x) const { return mIter - x.mIter; }

   iterator_type operator->() const { return mIter; }

   reference operator*() const { return *mIter; }

 private:
   iterator_type mIter;
};

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 *>;

   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 resize(size_type count);
   void resize(size_type count, const value_type &value);

   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;

   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)
{
   return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
}

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)
{
   return !(a == b);
}

template <class T, size_t N, class Storage>
ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
{
   return mData == mFixedStorage.data();
}

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)
{
   ensure_capacity(count);
   mSize = count;
   std::fill(begin(), end(), value);
}

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(size_type count)
{
   ensure_capacity(count);
   mSize = count;
}

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

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

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
{
   assign_from_initializer_list(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)
{
   size_t newSize = last - first;
   ensure_capacity(newSize);
   mSize = newSize;
   std::copy(first, last, begin());
}

template <class T, size_t N, class Storage>
FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
   const FastVector<T, N, Storage> &other)
{
   ensure_capacity(other.mSize);
   mSize = other.mSize;
   std::copy(other.begin(), other.end(), begin());
   return *this;
}

template <class T, size_t N, class Storage>
FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
{
   swap(other);
   return *this;
}

template <class T, size_t N, class Storage>
FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
   std::initializer_list<value_type> init)
{
   assign_from_initializer_list(init);
   return *this;
}

template <class T, size_t N, class Storage>
FastVector<T, N, Storage>::~FastVector()
{
   clear();
   if (!uses_fixed_storage())
   {
       delete[] mData;
   }
}

template <class T, size_t N, class Storage>
typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
{
   ASSERT(pos < mSize);
   return mData[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
{
   ASSERT(pos < mSize);
   return mData[pos];
}

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
   size_type pos)
{
   ASSERT(pos < mSize);
   return mData[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
{
   ASSERT(pos < mSize);
   return mData[pos];
}

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

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

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

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

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
{
   return mData + mSize;
}

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
   const
{
   return mData + mSize;
}

template <class T, size_t N, class Storage>
ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
{
   return mSize == 0;
}

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

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

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
{
   if (mSize == mReservedSize)
       ensure_capacity(mSize + 1);
   mData[mSize++] = value;
}

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

template <class T, size_t N, class Storage>
template <typename... Args>
ANGLE_INLINE void FastVector<T, N, Storage>::emplace_back(Args &&...args)
{
   if (mSize == mReservedSize)
       ensure_capacity(mSize + 1);
   mData[mSize++] = std::move(T(std::forward<Args>(args)...));
}

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
{
   ASSERT(mSize > 0);
   mSize--;
}

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
{
   ASSERT(mSize > 0);
   return mData[0];
}

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
   const
{
   ASSERT(mSize > 0);
   return mData[0];
}

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
{
   ASSERT(mSize > 0);
   return mData[mSize - 1];
}

template <class T, size_t N, class Storage>
ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
   const
{
   ASSERT(mSize > 0);
   return mData[mSize - 1];
}

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
{
   std::swap(mSize, other.mSize);

   pointer tempData = other.mData;
   if (uses_fixed_storage())
       other.mData = other.mFixedStorage.data();
   else
       other.mData = mData;
   if (tempData == other.mFixedStorage.data())
       mData = mFixedStorage.data();
   else
       mData = tempData;
   std::swap(mReservedSize, other.mReservedSize);

   if (uses_fixed_storage() || other.uses_fixed_storage())
       std::swap(mFixedStorage, other.mFixedStorage);
}

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::resize(size_type count)
{
   if (count > mSize)
   {
       ensure_capacity(count);
   }
   mSize = count;
}

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
{
   if (count > mSize)
   {
       ensure_capacity(count);
       std::fill(mData + mSize, mData + count, value);
   }
   mSize = count;
}

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

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
{
   ensure_capacity(init.size());
   mSize        = init.size();
   size_t index = 0;
   for (auto &value : init)
   {
       mData[index++] = value;
   }
}

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
{
   size_t len = mSize - 1;
   for (size_t index = 0; index < len; ++index)
   {
       if (mData[index] == element)
       {
           mData[index] = std::move(mData[len]);
           break;
       }
   }
   pop_back();
}

template <class T, size_t N, class Storage>
ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(iterator pos)
{
   ASSERT(pos >= begin());
   ASSERT(pos < end());
   size_t len = mSize - 1;
   *pos       = std::move(mData[len]);
   pop_back();
}

template <class T, size_t N, class Storage>
void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
{
   // We have a minimum capacity of N.
   if (mReservedSize < capacity)
   {
       ASSERT(capacity > N);
       size_type newSize = std::max(mReservedSize, N);
       while (newSize < capacity)
       {
           newSize *= 2;
       }

       pointer newData = new value_type[newSize];

       if (mSize > 0)
       {
           std::move(begin(), end(), newData);
       }

       if (!uses_fixed_storage())
       {
           delete[] mData;
       }

       mData         = newData;
       mReservedSize = newSize;
   }
}

template <class Value, size_t N>
class FastMap final
{
 public:
   FastMap() {}
   ~FastMap() {}

   Value &operator[](uint32_t key)
   {
       if (mData.size() <= key)
       {
           mData.resize(key + 1, {});
       }
       return mData[key];
   }

   const Value &operator[](uint32_t key) const
   {
       ASSERT(key < mData.size());
       return mData[key];
   }

   void clear() { mData.clear(); }

   bool empty() const { return mData.empty(); }
   size_t size() const { return mData.size(); }

   const Value *data() const { return mData.data(); }

   bool operator==(const FastMap<Value, N> &other) const
   {
       return (size() == other.size()) &&
              (memcmp(data(), other.data(), size() * sizeof(Value)) == 0);
   }

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

template <class Key, class Value, size_t N>
class FlatUnorderedMap final
{
 public:
   using Pair           = std::pair<Key, Value>;
   using Storage        = FastVector<Pair, N>;
   using iterator       = typename Storage::iterator;
   using const_iterator = typename Storage::const_iterator;

   FlatUnorderedMap()  = default;
   ~FlatUnorderedMap() = default;

   iterator begin() { return mData.begin(); }
   const_iterator begin() const { return mData.begin(); }
   iterator end() { return mData.end(); }
   const_iterator end() const { return mData.end(); }

   iterator find(const Key &key)
   {
       for (auto it = mData.begin(); it != mData.end(); ++it)
       {
           if (it->first == key)
           {
               return it;
           }
       }
       return mData.end();
   }

   const_iterator find(const Key &key) const
   {
       for (auto it = mData.begin(); it != mData.end(); ++it)
       {
           if (it->first == key)
           {
               return it;
           }
       }
       return mData.end();
   }

   Value &operator[](const Key &key)
   {
       iterator it = find(key);
       if (it != end())
       {
           return it->second;
       }

       mData.push_back(Pair(key, {}));
       return mData.back().second;
   }

   void insert(Pair pair)
   {
       ASSERT(!contains(pair.first));
       mData.push_back(std::move(pair));
   }

   void insert(const Key &key, Value value) { insert(Pair(key, value)); }

   void erase(iterator pos) { mData.remove_and_permute(pos); }

   bool contains(const Key &key) const { return find(key) != end(); }

   void clear() { mData.clear(); }

   bool get(const Key &key, Value *value) const
   {
       auto it = find(key);
       if (it != end())
       {
           *value = it->second;
           return true;
       }
       return false;
   }

   bool empty() const { return mData.empty(); }
   size_t size() const { return mData.size(); }

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

template <class T, size_t N>
class FlatUnorderedSet final
{
 public:
   using Storage        = FastVector<T, N>;
   using iterator       = typename Storage::iterator;
   using const_iterator = typename Storage::const_iterator;

   FlatUnorderedSet()  = default;
   ~FlatUnorderedSet() = default;

   iterator begin() { return mData.begin(); }
   const_iterator begin() const { return mData.begin(); }
   iterator end() { return mData.end(); }
   const_iterator end() const { return mData.end(); }

   iterator find(const T &value)
   {
       for (auto it = mData.begin(); it != mData.end(); ++it)
       {
           if (*it == value)
           {
               return it;
           }
       }
       return mData.end();
   }

   const_iterator find(const T &value) const
   {
       for (auto it = mData.begin(); it != mData.end(); ++it)
       {
           if (*it == value)
           {
               return it;
           }
       }
       return mData.end();
   }

   bool empty() const { return mData.empty(); }

   void insert(const T &value)
   {
       ASSERT(!contains(value));
       mData.push_back(value);
   }

   void erase(const T &value)
   {
       ASSERT(contains(value));
       mData.remove_and_permute(value);
   }

   void remove(const T &value) { erase(value); }

   bool contains(const T &value) const { return find(value) != end(); }

   void clear() { mData.clear(); }

   bool operator==(const FlatUnorderedSet<T, N> &other) const { return mData == other.mData; }

 private:
   Storage mData;
};

class FastIntegerSet final
{
 public:
   static constexpr size_t kWindowSize             = 64;
   static constexpr size_t kOneLessThanKWindowSize = kWindowSize - 1;
   static constexpr size_t kShiftForDivision =
       static_cast<size_t>(rx::Log2(static_cast<unsigned int>(kWindowSize)));
   using KeyBitSet = angle::BitSet64<kWindowSize>;

   ANGLE_INLINE FastIntegerSet();
   ANGLE_INLINE ~FastIntegerSet();

   ANGLE_INLINE void ensureCapacity(size_t size)
   {
       if (capacity() <= size)
       {
           reserve(size * 2);
       }
   }

   ANGLE_INLINE void insert(uint64_t key)
   {
       size_t sizedKey = static_cast<size_t>(key);

       ASSERT(!contains(sizedKey));
       ensureCapacity(sizedKey);
       ASSERT(capacity() > sizedKey);

       size_t index  = sizedKey >> kShiftForDivision;
       size_t offset = sizedKey & kOneLessThanKWindowSize;

       mKeyData[index].set(offset, true);
   }

   ANGLE_INLINE bool contains(uint64_t key) const
   {
       size_t sizedKey = static_cast<size_t>(key);

       size_t index  = sizedKey >> kShiftForDivision;
       size_t offset = sizedKey & kOneLessThanKWindowSize;

       return (sizedKey < capacity()) && (mKeyData[index].test(offset));
   }

   ANGLE_INLINE void clear()
   {
       for (KeyBitSet &it : mKeyData)
       {
           it.reset();
       }
   }

   ANGLE_INLINE bool empty() const
   {
       for (const KeyBitSet &it : mKeyData)
       {
           if (it.any())
           {
               return false;
           }
       }
       return true;
   }

   ANGLE_INLINE size_t size() const
   {
       size_t valid_entries = 0;
       for (const KeyBitSet &it : mKeyData)
       {
           valid_entries += it.count();
       }
       return valid_entries;
   }

 private:
   ANGLE_INLINE size_t capacity() const { return kWindowSize * mKeyData.size(); }

   ANGLE_INLINE void reserve(size_t newSize)
   {
       size_t alignedSize = rx::roundUpPow2(newSize, kWindowSize);
       size_t count       = alignedSize >> kShiftForDivision;

       mKeyData.resize(count, KeyBitSet::Zero());
   }

   std::vector<KeyBitSet> mKeyData;
};

// This is needed to accommodate the chromium style guide error -
//      [chromium-style] Complex constructor has an inlined body.
ANGLE_INLINE FastIntegerSet::FastIntegerSet() {}
ANGLE_INLINE FastIntegerSet::~FastIntegerSet() {}

template <typename Value>
class FastIntegerMap final
{
 public:
   FastIntegerMap() {}
   ~FastIntegerMap() {}

   ANGLE_INLINE void ensureCapacity(size_t size)
   {
       // Ensure key set has capacity
       mKeySet.ensureCapacity(size);

       // Ensure value vector has capacity
       ensureCapacityImpl(size);
   }

   ANGLE_INLINE void insert(uint64_t key, Value value)
   {
       // Insert key
       ASSERT(!mKeySet.contains(key));
       mKeySet.insert(key);

       // Insert value
       size_t sizedKey = static_cast<size_t>(key);
       ensureCapacityImpl(sizedKey);
       ASSERT(capacity() > sizedKey);
       mValueData[sizedKey] = value;
   }

   ANGLE_INLINE bool contains(uint64_t key) const { return mKeySet.contains(key); }

   ANGLE_INLINE bool get(uint64_t key, Value *out) const
   {
       if (!mKeySet.contains(key))
       {
           return false;
       }

       size_t sizedKey = static_cast<size_t>(key);
       *out            = mValueData[sizedKey];
       return true;
   }

   ANGLE_INLINE void clear() { mKeySet.clear(); }

   ANGLE_INLINE bool empty() const { return mKeySet.empty(); }

   ANGLE_INLINE size_t size() const { return mKeySet.size(); }

 private:
   ANGLE_INLINE size_t capacity() const { return mValueData.size(); }

   ANGLE_INLINE void ensureCapacityImpl(size_t size)
   {
       if (capacity() <= size)
       {
           reserve(size * 2);
       }
   }

   ANGLE_INLINE void reserve(size_t newSize)
   {
       size_t alignedSize = rx::roundUpPow2(newSize, FastIntegerSet::kWindowSize);
       mValueData.resize(alignedSize);
   }

   FastIntegerSet mKeySet;
   std::vector<Value> mValueData;
};
}  // namespace angle

#endif  // COMMON_FASTVECTOR_H_