CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
Path: blob/master/Common/Data/Collections/FastVec.h
Views: 1401
#pragma once12// Yet another replacement for std::vector, this time for use in graphics queues.3// Its major difference is that you can append uninitialized structures and initialize them after.4// This is not allows by std::vector but is very useful for our sometimes oversized unions.5// Also, copies during resize are done by memcpy, not by any move constructor or similar.67#include <cstdlib>8#include <cstring>9#include <cstdint>1011#include "Common/Log.h"1213template<class T>14class FastVec {15public:16FastVec() {}17FastVec(size_t initialCapacity) {18capacity_ = initialCapacity;19data_ = (T *)malloc(initialCapacity * sizeof(T));20_assert_(data_ != nullptr);21}22~FastVec() { free(data_); }2324T &push_uninitialized() {25if (size_ < capacity_) {26size_++;27return data_[size_ - 1];28} else {29ExtendByOne();30return data_[size_ - 1];31}32}3334void push_back(const T &t) {35T &dest = push_uninitialized();36dest = t;37}3839// Move constructor40FastVec(FastVec &&other) {41data_ = other.data_;42size_ = other.size_;43capacity_ = other.capacity_;44other.data_ = nullptr;45other.size_ = 0;46other.capacity_ = 0;47}4849FastVec &operator=(FastVec &&other) {50if (this != &other) {51free(data_);52data_ = other.data_;53size_ = other.size_;54capacity_ = other.capacity_;55other.data_ = nullptr;56other.size_ = 0;57other.capacity_ = 0;58}59return *this;60}6162// No copy constructor.63FastVec(const FastVec &other) = delete;64FastVec &operator=(const FastVec &other) = delete;6566size_t size() const { return size_; }67size_t capacity() const { return capacity_; }68void clear() { size_ = 0; }69bool empty() const { return size_ == 0; }7071const T *data() const { return data_; }7273T *begin() { return data_; }74T *end() { return data_ + size_; }75const T *begin() const { return data_; }76const T *end() const { return data_ + size_; }7778// Out of bounds (past size() - 1) is undefined behavior.79T &operator[] (const size_t index) { return data_[index]; }80const T &operator[] (const size_t index) const { return data_[index]; }81T &at(const size_t index) { return data_[index]; }82const T &at(const size_t index) const { return data_[index]; }8384// These two are invalid if empty().85const T &back() const { return (*this)[size() - 1]; }86const T &front() const { return (*this)[0]; }8788// Limited functionality for inserts and similar, add as needed.89T &insert(T *iter) {90int pos = iter - data_;91ExtendByOne();92if (pos + 1 < (int)size_) {93memmove(data_ + pos + 1, data_ + pos, (size_ - pos) * sizeof(T));94}95return data_[pos];96}9798void insert(T *destIter, const T *beginIter, const T *endIter) {99int pos = destIter - data_;100if (beginIter == endIter)101return;102size_t newItems = endIter - beginIter;103IncreaseCapacityTo(size_ + newItems);104memmove(data_ + pos + newItems, data_ + pos, (size_ - pos) * sizeof(T));105memcpy(data_ + pos, beginIter, newItems * sizeof(T));106size_ += newItems;107}108109void resize(size_t size) {110if (size < size_) {111size_ = size;112} else {113// TODO114}115}116117void reserve(size_t newCapacity) {118IncreaseCapacityTo(newCapacity);119}120121void extend(const T *newData, size_t count) {122IncreaseCapacityTo(size_ + count);123memcpy(data_ + size_, newData, count * sizeof(T));124size_ += count;125}126127T *extend_uninitialized(size_t count) {128size_t sz = size_;129if (size_ + count <= capacity_) {130size_ += count;131return &data_[sz];132} else {133size_t newCapacity = size_ + count * 2; // Leave some extra room when growing in all cases134if (newCapacity < capacity_ * 2) {135// Standard amortized O(1).136newCapacity = capacity_ * 2;137}138IncreaseCapacityTo(newCapacity);139size_ += count;140return &data_[sz];141}142}143144void LockCapacity() {145#ifdef _DEBUG146capacityLocked_ = true;147#endif148}149150private:151void IncreaseCapacityTo(size_t newCapacity) {152#ifdef _DEBUG153_dbg_assert_(!capacityLocked_);154#endif155if (newCapacity <= capacity_)156return;157T *oldData = data_;158data_ = (T *)malloc(sizeof(T) * newCapacity);159_assert_msg_(data_ != nullptr, "%d", (int)newCapacity);160if (capacity_ != 0) {161memcpy(data_, oldData, sizeof(T) * size_);162free(oldData);163}164capacity_ = newCapacity;165}166167void ExtendByOne() {168// We don't really extend capacity by one though - instead we use169// the usual doubling amortization.170size_t newCapacity = capacity_ * 2;171if (newCapacity < 16) {172newCapacity = 16;173}174IncreaseCapacityTo(newCapacity);175size_++;176}177178size_t size_ = 0;179size_t capacity_ = 0;180T *data_ = nullptr;181#ifdef _DEBUG182bool capacityLocked_ = false;183#endif184};185186// Simple cyclical vector.187template <class T, size_t size>188class HistoryBuffer {189public:190T &Add(size_t index) {191#ifdef _DEBUG192_dbg_assert_((int64_t)index >= 0);193#endif194if (index > maxIndex_)195maxIndex_ = index;196T &entry = data_[index % size];197entry = T{};198return entry;199}200201const T &Back(size_t index) const {202#ifdef _DEBUG203_dbg_assert_(index < maxIndex_ && index < size);204#endif205return data_[(maxIndex_ - index) % size];206}207208// Out of bounds (past size() - 1) is undefined behavior.209T &operator[] (const size_t index) {210#ifdef _DEBUG211_dbg_assert_(index <= maxIndex_);212#endif213return data_[index % size];214}215const T &operator[] (const size_t index) const {216#ifdef _DEBUG217_dbg_assert_(index <= maxIndex_);218#endif219return data_[index % size];220}221size_t MaxIndex() const {222return maxIndex_;223}224225private:226T data_[size]{};227size_t maxIndex_ = 0;228};229230231