SmallVector.h

#pragma once
 
#include "../Memory/Allocator.h"
 
#include <cstring>
#include <utility>
#include <initializer_list>
 
namespace Cogs
{
  namespace Collections
  {
    class COGSFOUNDATION_API SmallVectorBase
    {
    protected:
      SmallVectorBase(void * data, size_t capacity, Memory::Allocator * allocator) :
        firstPtr(data),
        lastPtr(data),
        capacityPtr(static_cast<uint8_t*>(firstPtr) + capacity),
        allocator(allocator)
      {}
 
      void growPod(const void* firstElement, const size_t minSizeBytes);
 
      size_t sizeInBytes() const
      {
        return static_cast<size_t>(static_cast<uint8_t*>(lastPtr) - static_cast<uint8_t*>(firstPtr));
      }
 
      size_t capacityInBytes() const
      {
        return static_cast<size_t>(static_cast<uint8_t*>(capacityPtr) - static_cast<uint8_t*>(firstPtr));
      }
 
      void * firstPtr;
      void * lastPtr;
      void * capacityPtr;
      Memory::Allocator * allocator;
    };
 
    template<typename T>
    class SmallVectorTemplateBase : public SmallVectorBase
    {
    public:
      bool empty() const { return lastPtr == firstPtr; }
      size_t size() const { return end() - begin(); }
      size_t capacity() const { return static_cast<T *>(capacityPtr) - begin(); }
 
      T * data() { return static_cast<T *>(firstPtr); }
      const T * data() const { return static_cast<const T *>(firstPtr); }
 
      T * begin() { return static_cast<T *>(firstPtr); }
      T * end() { return static_cast<T *>(lastPtr); }
 
      const T * begin() const { return static_cast<const T *>(firstPtr); }
      const T * end() const { return static_cast<const T *>(lastPtr); }
      const T * cbegin() const { return static_cast<const T *>(firstPtr); }
      const T * cend() const { return static_cast<const T *>(lastPtr); }
 
      T & operator[](const size_t index)
      {
        assert(index < size() && "Index out of bounds");
        return begin()[index];
      }
 
      const T & operator[](const size_t index) const
      {
        assert(index < size() && "Index out of bounds");
        return begin()[index];
      }
 
      T & back()
      {
        assert(!empty());
        return end()[-1];
      }
 
      const T & back() const
      {
        assert(!empty());
        return end()[-1];
      }
 
      T & front()
      {
        assert(!empty());
        return begin()[0];
      }
 
      const T & front() const
      {
        assert(!empty());
        return begin()[0];
      }
 
    protected:
      SmallVectorTemplateBase(size_t capacity, Memory::Allocator * allocator) :
        SmallVectorBase(&firstElement, capacity * sizeof(T), allocator) {}
 
      bool isSmall() const { return firstPtr == &firstElement; }
 
      void setSize(size_t newSize)
      {
        assert(begin() + newSize <= capacityPtr && "Size exceeds capacity.");
        lastPtr = begin() + newSize;
      }
 
      void reset()
      {
        firstPtr = lastPtr = capacityPtr = &firstElement;
      }
 
      alignas(T) uint8_t firstElement[sizeof(T)];
    };
 
    template<typename T, bool isPod>
    class SmallVectorImplBase : public SmallVectorTemplateBase<T>
    {
    public:
      void push_back(const T & t)
      {
        if (this->size() == this->capacity()) {
          grow();
        }
 
        new (this->end()) T(t);
        this->setSize(this->size() + 1);
      }
 
      void push_back(T && t)
      {
        if (this->size() == this->capacity()) {
          grow();
        }
 
        new (this->end()) T(std::move(t));
        this->setSize(this->size() + 1);
      }
 
      template<typename... Args>
      void emplace_back(Args &&... args)
      {
        if (this->size() == this->capacity()) {
          grow();
        }
 
        new (this->end()) T(std::forward<Args>(args)...);
        this->setSize(this->size() + 1);
      }
 
      void pop_back()
      {
        this->setSize(this->size() - 1);
        this->back()->~T();
      }
 
      // Erase element.
      void erase(const T* pos)
      {
        const size_t index = pos - this->begin();
        assert(index < this->size() && "Index out of bounds");
        (this->begin() + index)->~T();
        this->move(this->begin()+index+1, this->end(), this->begin() + index);
        this->setSize(this->size() - 1);
      }
 
    protected:
      SmallVectorImplBase(size_t capacity, Memory::Allocator * allocator) :
        SmallVectorTemplateBase<T>(capacity, allocator) {}
 
      void grow(size_t minSize = 0)
      {
        size_t newCapacity = this->capacity() * 2;
        if (minSize > newCapacity) newCapacity = minSize;
 
        const size_t currentSize = this->size();
 
        auto newBuffer = static_cast<T *>(this->allocator->allocate(newCapacity * sizeof(T)));
 
        moveNew(this->begin(), this->end(), newBuffer);
 
        destroy(this->begin(), this->end());
 
        this->firstPtr = newBuffer;
        this->lastPtr = newBuffer + currentSize;
        this->capacityPtr = newBuffer + newCapacity;
      }
 
      void initialize(T* first, const T* last)
      {
        while (first != last) {
          new (first++) T();
        }
      }
 
      void destroy(T* first, const T* last)
      {
        while (first != last) {
          (first++)->~T();
        }
      }
 
      template<typename T1, typename T2>
      void moveNew(T1 first, T1 last, T2 dest)
      {
        while (first != last) {
          new (dest++) T(std::move(*first++));
        }
      }
 
      template<typename T1, typename T2>
      void move(T1 first, T1 last, T2 dest)
      {
        while (first != last) {
          (*dest++) = std::move(*first++);
        }
      }
 
      template<typename T1, typename T2>
      void copy(T1 first, T1 last, T2 dest)
      {
        while (first != last) {
          (*dest++) = *first++;
        }
      }
 
      template<typename T1, typename T2>
      void copyNew(T1 first, T1 last, T2 dest)
      {
        while (first != last) {
          new (dest++) T(*first++);
        }
      }
    };
 
    template<typename T>
    class SmallVectorImplBase<T, true> : public SmallVectorTemplateBase<T>
    {
    public:
      void push_back(const T & t)
      {
        if (this->size() == this->capacity()) {
          this->grow();
        }
 
        new (this->end()) T(t);
        this->setSize(this->size() + 1);
      }
 
      void pop_back()
      {
        this->setSize(this->size() - 1);
      }
 
      // Erase element.
      void erase(const T* pos)
      {
        const size_t index = pos - this->begin();
        assert(index < this->size() && "Index out of bounds");
        this->move(this->begin() + index + 1, this->end(), this->begin() + index);
        this->setSize(this->size() - 1);
      }
 
    protected:
      SmallVectorImplBase(size_t capacity, Memory::Allocator * allocator) :
        SmallVectorTemplateBase<T>(capacity, allocator)
      {}
 
      void grow(size_t minSize = 0)
      {
        this->growPod(&this->firstElement, minSize * sizeof(T));
      }
 
      void initialize(T *, T *) {}
      void destroy(T *, T *) {}
 
      template<typename T1, typename T2>
      void move(T1 first, T1 last, T2 dest)
      {
        copy(first, last, dest);
      }
 
      template<typename T1, typename T2>
      void copy(T1 first, T1 last, T2 dest)
      {
        copyNew(first, last, dest);
      }
 
      template<typename T1, typename T2>
      void copyNew(T1 first, T1 last, T2 dest)
      {
        std::memcpy(dest, first, (last - first) * sizeof(T));
      }
    };
 
    template<typename T>
    class SmallVectorImpl : public SmallVectorImplBase<T, std::is_trivially_copyable<T>::value>
    {
    public:
      ~SmallVectorImpl()
      {
        this->destroy(this->begin(), this->end());
 
        if (!this->isSmall()) {
          release();
        }
      }
 
      SmallVectorImpl & operator=(const SmallVectorImpl & other)
      {
        if (this == &other) return *this;
 
        clear();
 
        if (this->capacity() < other.capacity()) {
          this->grow(other.size());
        }
 
        this->copyNew(other.begin(), other.end(), this->begin());
 
        this->setSize(other.size());
 
        return *this;
      }
 
      SmallVectorImpl & operator=(SmallVectorImpl && other) noexcept
      {
        if (this == &other) return *this;
 
        this->destroy(this->begin(), this->end());
 
        if (!other.isSmall()) {
          if (!this->isSmall()) {
            release();
          }
 
          this->firstPtr = other.firstPtr;
          this->lastPtr = other.lastPtr;
          this->capacityPtr = other.capacityPtr;
          this->allocator = other.allocator;
 
          other.reset();
 
          return *this;
        }
 
        if (this->capacity() < other.capacity()) {
          this->grow(other.size());
        }
 
        this->move(other.begin(), other.end(), this->begin());
 
        this->setSize(other.size());
 
        return *this;
      }
 
      void resize(size_t newSize)
      {
        if (newSize > this->capacity()) {
          this->grow(newSize);
        }
 
        this->setSize(newSize);
      }
 
      void reserve(size_t newCapacity)
      {
        if (newCapacity >= this->capacity()) {
          this->grow(newCapacity);
        }
      }
 
      void clear()
      {
        this->destroy(this->begin(), this->end());
 
        this->setSize(0);
      }
 
      template<typename T1>
      void assign(T1 first, T1 last)
      {
        clear();
        const size_t newSize = last - first;
 
        if (newSize > this->capacity()) {
          this->grow(newSize);
        }
 
        this->copyNew(first, last, this->data());
        this->setSize(newSize);
      }
 
      void assign(std::initializer_list<T> il)
      {
        assign(il.begin(), il.end());
      }
 
      template<typename T1>
      void append(T1 first, T1 last)
      {
        const size_t newSize = last - first + this->size();
 
        if (newSize > this->capacity()) {
          this->grow(newSize);
        }
 
        this->copyNew(first, last, this->end());
        this->setSize(newSize);
      }
 
      void append(std::initializer_list<T> il)
      {
        append(il.begin(), il.end());
      }
 
    protected:
      SmallVectorImpl(size_t capacity, Memory::Allocator * allocator = Memory::Allocator::overflowAllocator()) :
        SmallVectorImplBase<T, std::is_trivially_copyable<T>::value>(capacity, allocator)
      {}
 
      void release()
      {
        this->allocator->deallocate(this->firstPtr, this->capacityInBytes());
      }
    };
 
    template<typename T, size_t Size>
    class SmallVector : public SmallVectorImpl<T>
    {
      template<typename Ts, size_t Sizes>
      struct SmallVectorStorage
      {
        alignas(Ts) uint8_t inlineStorage[sizeof(Ts) * Sizes];
      };
 
      template<typename Ts> struct SmallVectorStorage<Ts, 0> {};
      template<typename Ts> struct SmallVectorStorage<Ts, 1> {};
 
    public:
      // using iterator_category = std::random_access_iterator_tag;
      using value_type = T;
      using difference_type = ptrdiff_t;
      using pointer = const T*;
      using reference = const T&;
 
      SmallVector() : SmallVectorImpl<T>(Size) {};
      explicit SmallVector(size_t size) : SmallVectorImpl<T>(Size) { this->resize(size); }
      SmallVector(Memory::Allocator * allocator) : SmallVectorImpl<T>(Size, allocator) {};
 
      SmallVector(SmallVector && other) noexcept : SmallVectorImpl<T>(Size)
      {
        SmallVectorImpl<T>::operator=(std::move(other));
      }
 
      SmallVector(SmallVectorImpl<T> && other) noexcept : SmallVectorImpl<T>(Size)
      {
        SmallVectorImpl<T>::operator=(std::move(other));
      }
 
      SmallVector(const SmallVector & other) : SmallVectorImpl<T>(Size)
      {
        SmallVectorImpl<T>::operator=(other);
      }
 
      SmallVector(const SmallVectorImpl<T> & other) : SmallVectorImpl<T>(Size)
      {
        SmallVectorImpl<T>::operator=(other);
      }
 
      SmallVector(std::initializer_list<T> il) : SmallVectorImpl<T>(Size)
      {
        this->assign(il);
      }
 
      SmallVector & operator=(const SmallVector & other)
      {
        SmallVectorImpl<T>::operator=(other);
        return *this;
      }
 
      SmallVector & operator=(SmallVector && other) noexcept
      {
        SmallVectorImpl<T>::operator=(std::move(other));
        return *this;
      }
 
      SmallVector & operator=(SmallVectorImpl<T> && other) noexcept
      {
        SmallVectorImpl<T>::operator=(std::move(other));
        return *this;
      }
 
    private:
      SmallVectorStorage<T, Size> inlineStorage;
    };
  }
}