AllocatorFixedSizeFreeList.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
#include "HAL/UnrealMemory.h"
#include "CoreGlobals.h"
 
template<uint32 AllocationSize, uint32 BlockSize>
class TAllocatorFixedSizeFreeList
{
public:
    TAllocatorFixedSizeFreeList(uint32 InitialBlockSize=0)
        :FreeList(nullptr)
        ,NumAllocated(0)
        ,NumLive(0)
    {
        // need enough memory to store pointers for the free list
        static_assert(AllocationSize >= sizeof(FreeListNode), "Allocation size must be large enough to hold pointer.");
 
        // warm the cache
        Grow(InitialBlockSize);
    }
 
    ~TAllocatorFixedSizeFreeList()
    {
        // by now all block better have been returned to me
        check(GIsCriticalError || NumLive == 0); 
        // WRH - 2007/09/14 - Note we are stranding memory here.
        // These pools are meant to be global and never deleted. 
    }
 
    void *Allocate()
    {
        CheckInvariants();
        if (!FreeList)
        {
            checkSlow(NumLive == NumAllocated);
            Grow(BlockSize);
        }
        // grab next free element, updating FreeList pointer
        void *rawMem = (void *)FreeList;
        FreeList = FreeList->NextFreeAllocation;
        ++NumLive;
        CheckInvariants();
        return rawMem;
    }
 
    void Free(void *Element)
    {
        CheckInvariants();
        checkSlow( NumLive > 0 );
        --NumLive;
        FreeListNode* NewFreeElement = (FreeListNode*)Element;
        NewFreeElement->NextFreeAllocation = FreeList;
        FreeList = NewFreeElement;
        CheckInvariants();
    }
 
    uint32 GetAllocatedSize() const
    {
        CheckInvariants();
        return NumAllocated * AllocationSize;
    }
 
    void Grow(uint32 NumElements)
    {
        if (NumElements == 0) 
        {
            return;
        }
 
        // need enough memory to store pointers for the free list
        check(AllocationSize*NumElements >= sizeof(FreeListNode));
 
        // allocate a block of memory
        uint8* RawMem = (uint8*)FMemory::Malloc(AllocationSize * NumElements);
        FreeListNode* NewFreeList = (FreeListNode*)RawMem;
        
        // Chain the block into a list of free list nodes
        for (uint32 i=0;i<NumElements-1;++i,NewFreeList=NewFreeList->NextFreeAllocation)
        {
            NewFreeList->NextFreeAllocation = (FreeListNode*)(RawMem + (i+1)*AllocationSize);
        }
 
        // link the last Node to the previous FreeList
        NewFreeList->NextFreeAllocation = FreeList;
        FreeList = (FreeListNode*)RawMem;
 
        NumAllocated += NumElements;
    }
 
private:
 
    struct FreeListNode
    {
        FreeListNode* NextFreeAllocation;
    };
 
    void CheckInvariants() const
    {
        checkSlow(NumAllocated >= NumLive);
    }
 
private:
 
    FreeListNode* FreeList;
 
    uint32 NumAllocated;
 
    uint32 NumLive;
};