For my game engine that I'm trying to write without using STL I implemented dynamic array class(some kind of std::vector). I would like to know whether this code suits best practices. I'm also not enough knowledged about move semantics and all that stuff, so please tell if I should add them somewhere in my code. My engine does not use C++ exceptions, so noexcept
is skipped even in places where it should be.
#pragma once
#include "Core/Engine/Core.h"
#include "Math/MathCommon.h"
#include "Core/Container/Iterator.h"
#include <initializer_list>
namespace Hermes
{
/**
* Templated dynamic array
* Assumes that elements are reallocate-able, e.g. we don't need to call anybody when moving object in memory
* Basically that means that object MUST NOT have pointers to themselves and/or other elements of array
* NOTE : currently this implementation will never shrink allocated memory itself,
* so you have to do it manually for better memory usage
*/
template<typename ElementType>
struct TArray
{
public:
FORCEINLINE TArray() : Data(0), ElementCount(0), AllocatedCount(0)
{
}
FORCEINLINE TArray(size_t InitialCount) : Data(0), ElementCount(0), AllocatedCount(0)
{
Resize(InitialCount);
}
FORCEINLINE TArray(size_t InitialCount, const ElementType& Filler) : Data(0), ElementCount(0), AllocatedCount(0)
{
Fill(0, InitialCount, Filler);
}
FORCEINLINE TArray(const TArray<ElementType>& Other) : Data(0), ElementCount(0), AllocatedCount(0)
{
Copy(0, Other.ElementCount, Other.GetData());
}
FORCEINLINE TArray(TArray<ElementType>&& Other) : Data(Other.Data), ElementCount(Other.ElementCount), AllocatedCount(Other.AllocatedCount)
{
Other.Data = 0;
Other.ElementCount = 0;
Other.AllocatedCount = 0;
}
FORCEINLINE TArray(const std::initializer_list<ElementType>& List)
{
Copy(0, List.size(), List._First);
}
FORCEINLINE TArray(size_t Count, const ElementType* Source)
{
Copy(0, Count, Source);
}
FORCEINLINE TArray<ElementType>& operator=(const TArray<ElementType>& Other)
{
ElementCount = 0;
Copy(0, Other.ElementCount, Other.Data);
Resize(Other.ElementCount);
}
FORCEINLINE TArray<ElementType>& operator=(TArray<ElementType>&& Other)
{
MemoryOperations::Swap(ElementCount, Other.ElementCount);
MemoryOperations::Swap(AllocatedCount, Other.AllocatedCount);
MemoryOperations::Swap(Data, Other.Data);
return *this;
}
FORCEINLINE TArray<ElementType>& operator=(const std::initializer_list<ElementType> List)
{
Copy(0, List.size(), List._First);
}
FORCEINLINE ~TArray()
{
Resize(0);
}
FORCEINLINE bool RangeCheck(size_t Index) const
{
return (Index >= 0) && (Index < ElementCount);
}
FORCEINLINE ElementType* GetData()
{
return Data;
}
FORCEINLINE const ElementType* GetData() const
{
return Data;
}
FORCEINLINE ElementType& operator[](size_t Index)
{
return Data[Index];
}
FORCEINLINE const ElementType& operator[](size_t Index) const
{
return Data[Index];
}
FORCEINLINE size_t Size() const
{
return ElementCount;
}
FORCEINLINE size_t Capacity() const
{
return AllocatedCount;
}
FORCEINLINE size_t Slack() const
{
return AllocatedCount - ElementCount;
}
FORCEINLINE size_t AppendUnitialized(size_t Count)
{
size_t StartIndex = ElementCount;
Resize(ElementCount + Count);
ElementCount += Count;
return StartIndex;
}
FORCEINLINE size_t AppendDefaulted(size_t Count)
{
size_t StartIndex = AppendUnitialized(Count);
MemoryOperations::ConstructDefaultItems<ElementType>(&Data[StartIndex], Count);
return StartIndex;
}
FORCEINLINE size_t Append(const ElementType& Item, size_t Count = 1)
{
Fill(ElementCount, Count, Item);
return ElementCount;
}
FORCEINLINE size_t Append(const TArray<ElementType>& Other)
{
size_t StartIndex = ElementCount;
Copy(StartIndex, Other.ElementCount, Other.Data);
return StartIndex;
}
FORCEINLINE size_t Append(const std::initializer_list<ElementType>& List)
{
size_t StartIndex = ElementCount;
Copy(StartIndex, List.size(), List.begin());
return StartIndex;
}
FORCEINLINE size_t Append(size_t Count, const ElementType* Source)
{
size_t StartIndex = ElementCount;
Copy(StartIndex, Count, Source);
return StartIndex;
}
FORCEINLINE size_t InsertUninitialized(size_t Index, size_t Count)
{
HERMES_ASSERT(Index < ElementCount);
if (!Count) return -1;
Resize(ElementCount + Count);
Memory::Memmove(&Data[Index + Count], &Data[Index], Count * sizeof(ElementType));
ElementCount += Count;
return Index;
}
FORCEINLINE size_t InsertDefaulted(size_t Index, size_t Count)
{
InsertUninitialized(Index, Count);
MemoryOperations::ConstructDefaultItems<ElementType>(&Data[Index], Count);
return Index;
}
FORCEINLINE size_t Insert(size_t Index, const ElementType& Item, size_t Count = 1)
{
InsertUninitialized(Index, Count);
Fill(Index, Count, Item);
return Index;
}
FORCEINLINE size_t Insert(size_t Index, const TArray<ElementType&> Other)
{
InsertUninitialized(Index, Count);
Copy(Index, Count, Other.Data);
return Index;
}
FORCEINLINE size_t Insert(size_t Index, std::initializer_list<ElementType> Source)
{
InsertUninitialized(Index, Count);
Copy(Index, Source.size(), Source._First);
}
FORCEINLINE size_t Insert(size_t Index, size_t Count, const ElementType* Source)
{
InsertUninitialized(Index, Count);
Copy(Index, Count, Source);
return Index;
}
/**
* Appends elements to the end of array
*/
FORCEINLINE size_t Push(const ElementType& Item)
{
return Append(Item);
}
/**
* Appends element to the end of array constructing it with given args
*/
template<typename... ArgsType>
FORCEINLINE void Emplace(ArgsType&&... Args)
{
size_t Index = AppendUnitialized(1);
new (Data + Index) ElementType(MemoryOperations::Forward<ArgsType>(Args)...);
return Index;
}
template<typename... ArgsType>
FORCEINLINE ElementType& EmplaceAt(size_t Index, ArgsType&&... Args)
{
InsertUninitialized(Index, 1);
new (Data + Index) ElementType(MemoryOperations::Forward<ArgsType>(Args)...);
return Data[Index];
}
/**
* Returns copy of last element of array and removes it from array
*/
FORCEINLINE ElementType Pop()
{
HERMES_ASSERT(ElementCount > 0)
auto Result = Data[ElementCount - 1];
RemoveAt(ElementCount - 1);
return Result;
}
/**
* Resizes array to at least NewCount elements, but could allocate more to reduce memory fragmentation
* If NewCount < ElementCount last elements will be properly destroyed
*/
FORCEINLINE void Resize(size_t NewCount)
{
if (NewCount != AllocatedCount)
{
if (NewCount < ElementCount)
{
MemoryOperations::DestroyItems(&Data[NewCount], ElementCount - NewCount);
}
size_t EstimatedAllocationSize = sizeof(ElementType) * NewCount; //EngineGlobals::GAllocator().GetOptimalAllocationSize(sizeof(ElementType) * NewCount, alignof(ElementType));
Data = (ElementType*)realloc(Data, EstimatedAllocationSize); //EngineGlobals::GAllocator().Reallocate(Data, EstimatedAllocationSize, alignof(ElementType));
AllocatedCount = (EstimatedAllocationSize / sizeof(ElementType));
if (NewCount < ElementCount)
ElementCount = NewCount;
}
}
/**
* Destroys all elements and makes sure that array could fit at least NewCount elements
*/
FORCEINLINE void Reset(size_t NewCount)
{
Resize(NewCount);
MemoryOperations::DestroyItems(Data, NewCount);
}
/**
* Removes extra slack, although it still may exist to optimize memory allocation
*/
FORCEINLINE void Trim()
{
Resize(ElementCount);
}
/**
* Removes everything from array and leave extra slack as required
*/
FORCEINLINE void Empty(size_t ExtraSlack = 0)
{
// We need to manually destroy items placed at slack memory because Resize won't do that
MemoryOperations::DestroyItems(Data, ExtraSlack);
ElementCount = 0;
Resize(ExtraSlack);
}
FORCEINLINE void RemoveAt(size_t Index, size_t Count = 1)
{
MemoryOperations::DestroyItems(Data + Index, Count);
Memory::Memmove(Data + Index, Data + Index + Count, Count * sizeof(ElementType));
ElementCount -= Count;
}
typedef TRangedIterator<ElementType> Iterator;
typedef TRangedIterator<const ElementType> ConstIterator;
/**
* Functions required to allow this container to be used in ranged-for loops
*/
FORCEINLINE Iterator begin() { return Iterator(Data); }
FORCEINLINE Iterator end() { return Iterator(Data + ElementCount); }
FORCEINLINE ConstIterator cbegin() { return ConstIterator(Data); }
FORCEINLINE ConstIterator cend() { return ConstIterator(Data + ElementCount); }
private:
/**
* Fills range from Data[Start] to Data[Start + Count] with Filler using copy constructor
* This function properly destroys and overrides data stored at [Start; Start + Count] range and resize array if needed
*/
FORCEINLINE void Fill(size_t Start, size_t Count, const ElementType& Filler)
{
if (Start + Count > ElementCount)
Resize(Start + Count);
if (Start < ElementCount)
MemoryOperations::DestroyItems(&Data[Start], max(min(ElementCount - Start, Count), 0));
MemoryOperations::CopyConstructItem(&Data[Start], Filler, Count);
ElementCount = Math::Max(Start + Count, ElementCount);
}
/**
* Copies Count elements from Source to Data[Start]
* This function properly destroys and overrides data stored at [Start; Start + Count] range and resize array if needed
*/
FORCEINLINE void Copy(size_t Start, size_t Count, const ElementType* Source)
{
if (Start + Count > ElementCount)
Resize(Start + Count);
if (Start < ElementCount)
MemoryOperations::DestroyItems(&Data[Start], max(min(ElementCount - Start, Count), 0));
MemoryOperations::CopyConstructItems(&Data[Start], Source, Count);
ElementCount = Math::Max(Start + Count, ElementCount);
}
private:
ElementType* Data;
size_t ElementCount;
size_t AllocatedCount;
};
}
EDIT:
Here's all header files required. I've also modified source code to use realloc
instead of my custom-made allocator to reduce amount of source code. I know that realloc
of 0 size and nullptr is implementation-dependent, but my implementation correctly handles it so no problems here.
Core/Engine/Core.h
#pragma once
#ifdef HERMES_PLATFORM_WINDOWS
#include <windows.h>
#define DLL_IMPORT __declspec(dllimport)
#define DLL_EXPORT __declspec(dllexport)
#define FORCEINLINE __forceinline
#define HERMES_ASSERT(Expression, ...) if (!(Expression)) DebugBreak();
#endif
#ifdef HERMES_BUILD_ENGINE
#define HERMES_API DLL_EXPORT
#define GAME_API DLL_IMPORT
#elif defined HERMES_BUILD_GAME
#define HERMES_API DLL_IMPORT
#define GAME_API DLL_EXPORT
#else
#error "Either HERMES_BUILD_ENGINE or HERMES_BUILD_GAME need to be specified"
#endif
#define CREATE_APP_INSTANCE_FUNCTION_NAME "CreateApplicationInstance"
#ifdef HERMES_PLATFORM_WINDOWS
typedef char int8 ;
typedef unsigned char uint8 ;
typedef short int int16 ;
typedef unsigned short int uint16;
typedef int int32 ;
typedef unsigned int uint32;
typedef long long int64 ;
typedef unsigned long long uint64;
typedef uint64 size_t; // We compile only 64 bit builds on Windows
#endif
Math/MathCommon.h
#pragma once
#include "Core/Engine/Core.h"
namespace Hermes
{
namespace Math
{
// TODO : intrinsic versions
/**
* log2 for 32-bit numbers
*/
FORCEINLINE uint8 FloorLog2(uint32 Number)
{
uint32 Result = 0;
if (Number >= 1ull << 16) { Number >>= 16; Result += 16; }
if (Number >= 1ull << 8) { Number >>= 8; Result += 8; }
if (Number >= 1ull << 4) { Number >>= 4; Result += 4; }
if (Number >= 1ull << 2) { Number >>= 2; Result += 2; }
if (Number >= 1ull << 1) { Result += 1; }
return (Number == 0) ? 0 : Result;
}
/**
* log2 for 64-bit numbers
*/
FORCEINLINE uint8 FloorLog2_64(uint64 Number)
{
uint32 Result = 0;
if (Number >= 1ull << 32) { Number >>= 32; Result += 32; }
if (Number >= 1ull << 16) { Number >>= 16; Result += 16; }
if (Number >= 1ull << 8) { Number >>= 8; Result += 8; }
if (Number >= 1ull << 4) { Number >>= 4; Result += 4; }
if (Number >= 1ull << 2) { Number >>= 2; Result += 2; }
if (Number >= 1ull << 1) { Result += 1; }
return (Number == 0) ? 0 : Result;
}
FORCEINLINE bool IsPowerOf2(uint64 Number)
{
return !(Number & (Number - 1));
}
FORCEINLINE int64 CeilIntegerDivide(int64 Dividend, int64 Divisor)
{
return ((Dividend + Divisor - 1) / Divisor);
}
template<typename T>
FORCEINLINE T Max(T A, T B)
{
return (A > B ? A : B);
}
template<typename T>
FORCEINLINE T Min(T A, T B)
{
return (A < B ? A : B);
}
}
}
Core/Container/Iterator.h
#pragma once
#include "Core/Engine/Core.h"
namespace Hermes
{
/**
* Very simple iterator that only defines functions required by ranged-for loop
*/
template<typename ElementType>
struct TRangedIterator
{
public:
FORCEINLINE TRangedIterator(ElementType* InPtr) : Ptr(InPtr) {}
FORCEINLINE bool operator!=(const TRangedIterator<ElementType>& Other) const { return Ptr != Other.Ptr; }
FORCEINLINE TRangedIterator<ElementType>& operator++() { Ptr++; return *this; }
FORCEINLINE ElementType& operator*() const { return *Ptr; }
private:
ElementType* Ptr;
};
}
#define FORCEINLINE __forceinline
(and then using FORCEINLINE everywhere) is probably a bad idea. Forcing inline is probably going to make your code both slower and larger. The compiler is much better at deciding when to inline code than a human is (it can make intelligent decisions based on a lot of factors that could change over the lifetime of the code). \$\endgroup\$ – Martin York Jan 16 at 17:22