TypeErasedDynamicArray.h

#pragma once

#include "Allocator/Allocator.h"
#include "Closure/Function.h"
#include "TypeMeta/TypeMeta.h"

namespace SE {

template<typename TAllocator>
class TTypeErasedArray;

template<Impl::EGlobalAllocatorType AllocatorType>
class TTypeErasedArray<TGlobalAllocator<AllocatorType>> {
public:
    using FAllocator = TGlobalAllocator<AllocatorType>;
    static constexpr uint32 GrowthRatio = 2u;

    constexpr TTypeErasedArray() = default;

    TTypeErasedArray(const TTypeErasedArray &Other) {
        Meta = Other.Meta;
        Elements = Other ? Alloc(Other.GetSize()) : nullptr;
        Meta->CopyConstruct(Elements, *Other, Other.GetSize());
        Size = Other.GetSize();
        MaxSize = Other.GetSize();
    }

    TTypeErasedArray &operator=(const TTypeErasedArray &Other) {
        Check((void *)&Other != (void *)this);
        Check(MaxSize == 0 || Meta->Matches(Other.Meta));
        if(MaxSize == 0) {
            Meta = Other.Meta;
        }
        EnsureMaxSize(Other.GetSize());
        var LowestSize = Math::Min(Size, Other.GetSize());
        // Assign old elements to new elements.
        Meta->CopyAssign(Elements, *Other, LowestSize);
        // Construct elements above old size and below new size.
        if(Size < Other.GetSize()) {
            Meta->CopyConstruct(Offset(Size), Other.Offset(Size), Other.GetSize() - Size);
        }
        if(Size > Other.GetSize()) {
            Meta->Destruct(Offset(Other.GetSize()), Size - Other.GetSize());
        }
        Size = Other.GetSize();
        return *this;
    }

    TTypeErasedArray(TTypeErasedArray &&Other) {
        Swap(Elements, Other.Elements);
        Swap(Size, Other.Size);
        Swap(MaxSize, Other.MaxSize);
        Swap(Meta, Other.Meta);
        if constexpr(FAllocator::MemoryOwnership) {
            Swap(MemoryOwnership, Other.MemoryOwnership);
        }
    }

    TTypeErasedArray &operator=(TTypeErasedArray &&Other) {
        Swap(Elements, Other.Elements);
        Swap(Size, Other.Size);
        Swap(MaxSize, Other.MaxSize);
        Swap(Meta, Other.Meta);
        if constexpr(FAllocator::MemoryOwnership) {
            Swap(MemoryOwnership, Other.MemoryOwnership);
        }
        return *this;
    }

    ~TTypeErasedArray() {
        Meta->Destruct(Elements, Size);
        Free(Elements, MaxSize);
    }
    
    void Setup(const Meta::FTypeMeta *InMeta) {
        Check(MaxSize == 0);
        Meta = InMeta;
    }

    void *Create() {
        EnsureMaxSize(Size + 1);
        var Result = Offset(Size);
        Meta->Construct(Result);
        ++Size;
        return Result;
    }

    void Resize(uint32 InSize) {
        EnsureMaxSize(InSize);
        // Construct elements above old size and below new size.
        if(Size < InSize) {
            Meta->Construct(Offset(Size), InSize - Size);
        }
        // Destruct elements above new size.
        if(Size > InSize) {
            Meta->Destruct(Offset(InSize), Size - InSize);
        }
        Size = InSize;
    }

    void Resize(uint32 InSize, const void *Other) {
        EnsureMaxSize(InSize);
        // Construct elements above old size and below new size.
        for(var Index = Size; Index < InSize; ++Index) {
            Meta->CopyConstruct(Offset(Index), Other, InSize - Size);
        }
        // Destruct elements above new size.
        if(Size > InSize) {
            Meta->Destruct(Offset(InSize), Size - InSize);
        }
        Size = InSize;
    }

    void Clear() {
        Meta->Destruct(Elements, Size);
        Size = 0;
    }

    void Shrink() {
        if(Size < MaxSize) {
            if(Meta->Reallocable) {
                if(Size > 0) {
                    Elements = Realloc(Elements, Size, MaxSize);
                } else {
                    Free(Elements, MaxSize);
                    Elements = nullptr;
                }
            } else {
                if(Size > 0) {
                    typename FAllocator::FMemoryOwnership OldMemoryOwnership;
                    if constexpr(FAllocator ::MemoryOwnership) {
                        Swap(MemoryOwnership, OldMemoryOwnership);
                    }
                    var NewElements = Alloc(Size);
                    Meta->MoveConstruct(NewElements, Elements, Size);
                    Meta->Destruct(Elements, Size);
                    if constexpr(FAllocator ::MemoryOwnership) {
                        Swap(MemoryOwnership, OldMemoryOwnership);
                    }
                    Free(Elements, MaxSize);
                    if constexpr(FAllocator ::MemoryOwnership) {
                        Swap(MemoryOwnership, OldMemoryOwnership);
                    }
                    Elements = NewElements;
                } else {
                    Meta->Destruct(Elements, Size);
                    Free(Elements, MaxSize);
                    Elements = nullptr;
                }
            }
            MaxSize = Size;
        }
    }

    void *AddCopy(const void *Value) {
        Checkf(&Value < **this || &Value > Offset(MaxSize), "Adding own element is unsafe due to realloc");
        EnsureMaxSize(Size + 1);
        var Result = Offset(Size);
        Meta->CopyConstruct(Result, Value, 1);
        return Result;
    }

    void *AddMove(void *Value) {
        Checkf(&Value < **this || &Value > Offset(MaxSize), "Adding own element is unsafe due to realloc");
        EnsureMaxSize(Size + 1);
        var Result = Offset(Size);
        Meta->MoveConstruct(Result, Value, 1);
        return Result;
    }
    
    template<typename T>
    T &Add(const T &Value) {
        VerboseCheck(Meta->Matches<T>());
        return *(T *)AddCopy(&Value);
    }
    
    template<typename T>
    T &Add(T &&Value) {
        VerboseCheck(Meta->Matches<T>());
        return *(T *)AddMove(&Value);
    }

    void RemoveNoSwap(uint32 InIndex) {
        Check(Size > InIndex);
        --Size;
        Meta->RemoveNoSwap(Offset(InIndex), Size - InIndex);
    }

    void RemoveSwap(uint32 Index) {
        Check(Size > Index);
        --Size;
        if(Index != Size) {
            Meta->MoveAssign(Offset(Index), Offset(Size), 1);
        }
        Meta->Destruct(Offset(Size), 1);
    }

    void MoveElement(uint32 From, uint32 To) {
        Check(Size > From);
        Check(Size > To);
        Meta->MoveElement(Elements, From, To);
    }

    void RemoveLast() {
        Check(Size > 0);
        --Size;
        Meta->Destruct(Offset(Size), 1);
    }

    void *operator*() {
        return Elements;
    }

    const void *operator*() const {
        return Elements;
    }

    uint32 GetSize() const {
        return Size;
    }

    bool IsEmpty() const {
        return Size == 0;
    }

    explicit operator bool() const {
        return !IsEmpty();
    }

    void EnsureMaxSize(uint32 InMaxSize) {
        Check(Meta);
        if(MaxSize < InMaxSize) {
            uint32 NewMaxSize;
            if(Meta->ElementSize < 1024) {
                NewMaxSize = Math::Max(MaxSize * GrowthRatio, InMaxSize);
            } else {
                NewMaxSize = InMaxSize;
            }
            if(Meta->Reallocable) {
                if(Elements) {
                    Elements = Realloc(Elements, NewMaxSize, MaxSize);
                } else {
                    Elements = Alloc(NewMaxSize);
                }
            } else {
                if(Elements) {
                    typename FAllocator::FMemoryOwnership OldMemoryOwnership;
                    if constexpr(FAllocator ::MemoryOwnership) {
                        Swap(MemoryOwnership, OldMemoryOwnership);
                    }
                    var NewElements = Alloc(NewMaxSize);
                    Meta->MoveConstruct(NewElements, Elements, Size);
                    Meta->Destruct(Elements, Size);
                    if constexpr(FAllocator ::MemoryOwnership) {
                        Swap(MemoryOwnership, OldMemoryOwnership);
                    }
                    Free(Elements, MaxSize);
                    if constexpr(FAllocator ::MemoryOwnership) {
                        Swap(MemoryOwnership, OldMemoryOwnership);
                    }
                    Elements = NewElements;
                } else {
                    Elements = Alloc(NewMaxSize);
                }
            }
            MaxSize = NewMaxSize;
        }
    }

private:
    void *Elements = nullptr;
    uint32 Size = 0;
    uint32 MaxSize = 0;
    const Meta::FTypeMeta *Meta = nullptr;
    [[no_unique_address]] typename FAllocator::FMemoryOwnership MemoryOwnership;

    void *Alloc(uint32 InSize) {
        void *Result;
        if constexpr(FAllocator::MemoryOwnership) {
            Result = FAllocator::Alloc(InSize * Meta->ElementSize, Meta->ElementAlignment, MemoryOwnership);
        } else {
            Result = FAllocator::Alloc(InSize * Meta->ElementSize, Meta->ElementAlignment);
        }
        return Result;
    }

    void *Realloc(void *Ptr, uint32 InSize, uint32 OldSize) {
        void *Result;
        if constexpr(FAllocator::MemoryOwnership) {
            Result = FAllocator::Realloc(Ptr, InSize * Meta->ElementSize, OldSize * Meta->ElementSize, Meta->ElementAlignment, MemoryOwnership);
        } else {
            Result = FAllocator::Realloc(Ptr, InSize * Meta->ElementSize, OldSize * Meta->ElementSize, Meta->ElementAlignment);
        }
        return Result;
    }

    void Free(void *Ptr, uint32 InSize) {
        if constexpr(FAllocator::MemoryOwnership) {
            FAllocator::Free(Ptr, InSize * Meta->ElementSize, Meta->ElementAlignment, MemoryOwnership);
        } else {
            FAllocator::Free(Ptr, InSize * Meta->ElementSize, Meta->ElementAlignment);
        }
    }
    
    void *Offset(uint32 Index) const {
        return (byte *)Elements + Meta->ElementSize * Index;
    }
};

using FHeapTypeErasedArray = TTypeErasedArray<FHeapAllocator>;

using FPoolTypeErasedArray = TTypeErasedArray<FPoolAllocator>;

using FFrameTypeErasedArray = TTypeErasedArray<FFrameAllocator>;

}  // namespace SE

TypeMeta.h

#pragma once

#include "Primitives/Primitives.h"
#include "Closure/Function.h"
#include "Meta/MetaMemory.h"
#include <string.h>

namespace SE {

namespace Meta {

namespace Impl {

template<typename T>
void ConstructImpl(void *Ptr, uint32 Size) {
    if constexpr (Meta::IsTrivialConstruct<T>) {
        // Do nothing.
    } else {
        var Elements = (T *)Ptr;
        for(var Index = 0u; Index < Size; ++Index) {
            Meta::Construct(Elements[Index]);
        }
    }
}

template<typename T>
void CopyConstructImpl(void *Ptr, const void *Other, uint32 Size) {
    if constexpr (Meta::IsTrivialCopy<T>) {
        memcpy(Ptr, Other, sizeof(T) * Size);
    } else {
        var Elements = (T *)Ptr;
        var OtherElements = (const T *)Other;
        for(var Index = 0u; Index < Size; ++Index) {
            Meta::Construct(Elements[Index], OtherElements[Index]);
        }
    }
}

template<typename T>
void CopyAssignImpl(void *Ptr, const void *Other, uint32 Size) {
    if constexpr (Meta::IsTrivialCopy<T>) {
        memcpy(Ptr, Other, sizeof(T) * Size);
    } else {
        var Elements = (T *)Ptr;
        var OtherElements = (const T *)Other;
        for(var Index = 0u; Index < Size; ++Index) {
            Elements[Index] = OtherElements[Index];
        }
    }
}


template<typename T>
void MoveConstructImpl(void *Ptr, void *Other, uint32 Size) {
    if constexpr (Meta::IsTrivialMove<T>) {
        memcpy(Ptr, Other, sizeof(T) * Size);
    } else {
        var Elements = (T *)Ptr;
        var OtherElements = (T *)Other;
        for(var Index = 0u; Index < Size; ++Index) {
            Meta::Construct(Elements[Index], Move(OtherElements[Index]));
        }
    }
}

template<typename T>
void MoveAssignImpl(void *Ptr, void *Other, uint32 Size) {
    if constexpr (Meta::IsTrivialMove<T>) {
        memcpy(Ptr, Other, sizeof(T) * Size);
    } else {
        var Elements = (T *)Ptr;
        var OtherElements = (T *)Other;
        for(var Index = 0u; Index < Size; ++Index) {
            Elements[Index] = Move(OtherElements[Index]);
        }
    }
}

template<typename T>
void RemoveNoSwapImpl(void *Ptr, uint32 Size) {
    var Elements = (T *)Ptr;
    if constexpr(Meta::IsTrivialMove<T> && Meta::IsTrivialDestruct<T>) {
        memmove(Elements, Elements + 1, sizeof(T) * Size);
    } else {
        // Move removed element above the size.
        for(var Index = 0u; Index < Size; ++Index) {
            Swap(Elements[Index], Elements[Index + 1]);
        }
    }
    if constexpr(!Meta::IsTrivialDestruct<T>) {
        Meta::Destruct(Elements[Size]);
    }
}

template<typename T>
void MoveElementImpl(void *Ptr, uint32 From, uint32 To) {
    if(From > To) {
        Swap(From, To);
    }
    var Elements = (T *)Ptr;
    if constexpr(Meta::IsTrivialMove<T> && Meta::IsTrivialDestruct<T>) {
        var Size = To - From;
        if(Size > 0) {
            T Temp = Move(Elements[From]);
            memmove(Elements + From, Elements + From + 1, sizeof(T) * Size);
            Elements[To] = Move(Temp);
        }
    } else {
        for(var Index = From; Index < To; ++Index) {
            Swap(Elements[Index], Elements[Index + 1]);
        }
    }
}

template<typename T>
void DestructImpl(void *Ptr, uint32 Size) {
    if constexpr (Meta::IsTrivialConstruct<T>) {
        // Do nothing.
    } else {
        var Elements = (T *)Ptr;
        for(var Index = 0u; Index < Size; ++Index) {
            Meta::Destruct(Elements[Index]);
        }
    }
}

}

struct FTypeMeta {
    uint32 ElementSize = 0;
    uint32 ElementAlignment = 0;
    bool Reallocable = false;
    TFunction<void(void *Ptr, uint32 Size)> *Construct = nullptr;
    TFunction<void(void *Ptr, const void *Other, uint32 Size)> *CopyConstruct = nullptr;
    TFunction<void(void *Ptr, const void *Other, uint32 Size)> *CopyAssign = nullptr;
    TFunction<void(void *Ptr, void *Other, uint32 Size)> *MoveConstruct = nullptr;
    TFunction<void(void *Ptr, void *Other, uint32 Size)> *MoveAssign = nullptr;
    TFunction<void(void *Ptr, uint32 Size)> *RemoveNoSwap = nullptr;
    TFunction<void(void *Ptr, uint32 From, uint32 To)> *MoveElement = nullptr;
    TFunction<void(void *Ptr, uint32 Size)> *Destruct = nullptr;
    
    template<typename T>
    inline constexpr bool Matches() const {
        return Construct == Impl::ConstructImpl<T>;
    }
    inline constexpr bool Matches(const FTypeMeta &Other) const {
        return Construct == Other.Construct;
    }
};

template<typename T>
FTypeMeta TypeMeta() {
    FTypeMeta Meta;
    Meta.ElementSize = sizeof(T);
    Meta.ElementAlignment = alignof(T);
    Meta.Reallocable = Meta::IsTrivialMove<T> && Meta::IsTrivialDestruct<T>;
    Meta.Construct = Impl::ConstructImpl<T>;
    Meta.CopyConstruct = Impl::CopyConstructImpl<T>;
    Meta.CopyAssign = Impl::CopyAssignImpl<T>;
    Meta.MoveConstruct = Impl::MoveConstructImpl<T>;
    Meta.MoveAssign = Impl::MoveAssignImpl<T>;
    Meta.RemoveNoSwap = Impl::RemoveNoSwapImpl<T>;
    Meta.MoveElement = Impl::MoveElementImpl<T>;
    Meta.Destruct = Impl::ConstructImpl<T>;
    return Meta;
}

}

}