Class : 2015 May Game Engine I

Memory manger is an important topic, the memory is limit, and every time I call new and delete are wasting time, for avoiding that, I can allocate a chunk of memory at beginning. In this case, I can shorten the time of dynamic memory.

First, I need to operator override new and delete.

inline void * operator new (size_t size)
{
return MemoryManager::GetInstance()-
>Allocate(static_cast)unsigned
int(size));
}

inline void operator delete (void * p)
{
MemoryManager::GetInstance()->DeAllocate(p);
}

After I done that, I need header structure and footer structure to know whether our memory chunk is going to use or return.

struct Header
{
//How much free memory is inside this block, we need to take a note
//that we know whether this memory is used, if high order bit is 1(us//ing), if high order bit is 0, not using yet.
unsigned int size;
// Point to the previous free header, it is a Cyclic doubly linked
// list
Header * prev;
// Point to the previous free header, it is a Cyclic doubly linked li//st
Header * next;
};

//Footer is the same aspect, but its location is at the foot of the memory block, high order bit is 1 is using , vice versa
struct Footer
{
unsigned int size;
};

//We are going to make a Heap class, and its component are header and footer
class Heap
{
private;
// Allocated memory for this entire heap
char * pool;
Header* freeListEntry;
Header* firstHeader;
Footer* lastFooter;
public:
//allocate
void Init(unsigned int poolSize);
Header * FindBlock(unsigned int allocSize);
void * Allocate(unsigned int allocSize);

//deallocate
void DeAllocate(void * data);
bool DeAllocateRight(void * data);
bool DeAllocateLeft(void * data);
void DeAllocateMiddle(void * data);
};

For the allocate part, there are three functions, Init, FindBlock, Allocate

The biggest point of manipulate the address is you need to transfer
to (char*) first, and you can mark the location based on the shift
size. After that, transfer again to the (header*) or (footer*), then
everything should be good.

void Heap::Init(unsigned int poolSize)
{

//make the pointer address location
pool =reinterpret_cast<char*>( malloc(poolSize));

freeListEntry = reinterpret_cast<Header*>(pool);

//real size need to subtract the header and footer structure size
freeListEntry->size = poolSize - sizeof(*firstHeader) - sizeof(*lastFooter);

//make a cyclic double link list
freeListEntry->prev = freeListEntry;
freeListEntry->next = freeListEntry;

firstHeader = freeListEntry;

//make last Footer address location
lastFooter = reinterpret_cast

<Footer *>((char*)firstHeader +
sizeof(*firstHeader) + freeListEntry->size);

lastFooter->size = freeListEntry->size ;

Find the block of memory is suitable for the requirement

Header * Heap::FindBlock(unsigned int allocSize)
{
Header* FreeList = freeListEntry;

do
{
if (allocSize < FreeList->size)
return FreeList;

FreeList = FreeList->next;
}

while (FreeList != freeListEntry);
return nullptr;
} 

If you allocate, need to turn on the highest bit, I use bitwise operator to do that. While you allocate, there is two cases, one is the block of memory is bigger than you want+ header and footer size, so you can split, the other case is not bigger, so no splitting.

void* Heap::Allocate(unsigned int allocSize)
{
Header* free_head = FindBlock(allocSize);
Footer* free_foot = nullptr;
Header* used_head = nullptr;
Footer* used_foot = nullptr;
void* data = nullptr;

//find big enough size
if (free_head != nullptr)
{
//spiltting case
if ((allocSize + sizeof(Footer) + sizeof(Header))< (free_head->size))
{
used_foot = reinterpret_cast<Footer*>((char*)free_head + sizeof(Header) +
free_head->size);
used_foot->size = allocSize | (1 << 31);

used_head = reinterpret_cast<Header*>((char*)used_ foot - (allocSize +
sizeof(Header)));

used_head->size = allocSize | (1 << 31);

free_foot = reinterpret_cast<Footer*>((char*)used_head -
sizeof(Footer));

free_head->size = free_head->size - (allocSize +
sizeof(Footer) + sizeof(Header));
free_foot->size = free_head->size;

data = reinterpret_cast<void*>((char*)used_head+sizeof(Head er));
}
else
{
//no spiltting case

free_foot = reinterpret_cast<Footer*>((char*)free_head + free_head->size +
sizeof(Header));
free_head->size = free_head->size | (1 << 31); free_foot->size = free_head->size;

data = reinterpret_cast<void*>((char*)free_head + sizeof(Header));

//no list in circle
if (freeListEntry == free_head)
{
freeListEntry = freeListEntry->next;
if (freeListEntry == freeListEntry->next)
freeListEntry = nullptr;
}
//still list in circle

free_head->next->prev = free_head->prev;
free_head->prev->next = free_head->next;
free_head->next = nullptr;
free_head->prev = nullptr;

}
}

return data;
}

Right now the allocate is done, I shift to deallocate part, on the opposite of allocate, deallocate need to turn off the highest bit, I use bitwise operator to do that again. While we deallocate, we need to merge the block of memory if needed, in this case, we use three functions to do that, deallocateRight, deacllocateLeft, deallocateMiddle.

void Heap::DeAllocate(void * data)
{
bool merged_left = false;
bool merged_right = false;

merged_right = DeAllocateRight(data);
merged_left = DeAllocateLeft(data);

//add block to free list
if (merged_left != true)
{
DeAllocateMiddle(data);
}
}

bool Heap::DeAllocateLeft(void * data)
{
Header* dataHeader = reinterpret_cast<Header*>((char*)data - sizeof(Header));
if (dataHeader == firstHeader)
return false;

//get left footer
Footer* dataLeftFooter = reinterpret_cast<Footer*>((char*)data - sizeof(Header) -
sizeof(Footer));
unsigned int dataLeftSize = dataLeftFooter->size;

int LeftSizeHighBit = dataLeftSize >> 31;
//check high bit
if (LeftSizeHighBit == 0)
{
//can merge left
//get the data header size first
Header* dataHeader = reinterpret_cast<Header*>((char*)data-sizeof(Header));
unsigned int dataSize = dataHeader->size;

//get the dataFooter
Footer* dataFooter = reinterpret_cast<Footer*>((char*)data + dataSize);

//get total size
unsigned int totalSize = dataLeftSize + sizeof(Header) + sizeof(Footer) +
dataSize;

//adjust the data Left Header size
Header* dataLeftHeader = reinterpret_cast<Header*>((char*)data - sizeof(Header) -
sizeof(Footer) - dataLeftSize - sizeof(Header));
dataLeftHeader->size = totalSize;
dataFooter->size = dataLeftHeader->size;

return true;
}
else if (LeftSizeHighBit == 1)
{
//handle link list
return false;
}
else
{
//impossible
assert(0);
return false;
}
}

bool Heap::DeAllocateRight(void * data)
{
//read how much data first
Header* dataHeader = reinterpret_cast<Header*>((char*)data - sizeof(Header));
unsigned int dataSize = dataHeader->size;

//modify the High bit of size
dataSize &amp;amp;amp;= ~(1 << 31);
dataHeader->size = dataSize;

//footer also modify the High bit of size
Footer* dataFooter = reinterpret_cast<Footer*>((char*)data + dataSize);
dataFooter->size = dataSize;

if (dataFooter == lastFooter)
return false;

//right can be merge?
Header* dataRightHeader = reinterpret_cast<Header*>((char*)dataFooter +
sizeof(Footer));
unsigned int RightSize = dataRightHeader->size;
int RightSizeHighBit = RightSize >> 31;

if (RightSizeHighBit == 1)
{
return false;
}
else if (RightSizeHighBit == 0)
{
//it's 0, not being using , can merge
//handle link first, take the right block off free list
dataRightHeader->prev->next = dataRightHeader->next;
dataRightHeader->next->prev = dataRightHeader->prev;
dataRightHeader->prev = nullptr;
dataRightHeader->next = nullptr;

//get the dataRightFooter
Footer* dataRightFooter = reinterpret_cast<Footer*>((char*)dataRightHeader +
sizeof(Header) + RightSize);

//adjust the size
dataHeader->size = dataSize + sizeof(Header) + sizeof(Footer) + RightSize;
dataRightFooter->size = dataHeader->size;
return true;
}
else
{
//impossible here,
assert(0);
return false;
}
}

void Heap::DeAllocateMiddle(void * data)
{
//read how much data first
Header* dataHeader = reinterpret_cast<Header*>((char*)data -sizeof(Header));

if (freeListEntry->next != nullptr)
{
freeListEntry->next->prev = dataHeader;
dataHeader->prev = freeListEntry;
dataHeader->next = freeListEntry->next;
freeListEntry->next = dataHeader;
}
}

Basically that the major code of how to manipulate use pre-allocate heap, you can decide which memory you need at first, and try and error what’s the size in the game.
Thanks for reading.