#ifndef SLANG_VIRTUAL_POOL_ALLOCATOR_H
#define SLANG_VIRTUAL_POOL_ALLOCATOR_H

namespace Slang
{

/// A virtual free-list allocater.
/// This class doesn't actually allocates memory, instead it operates on a
/// virtual integer space. Can be used to implement various types of object pools
/// that needs to support contiguous allocations of more than one elements.
class VirtualObjectPool
{
public:
    struct FreeListNode
    {
        int Offset;
        int Length;
        FreeListNode* prev;
        FreeListNode* next;
    };
    FreeListNode* freeListHead = nullptr;

public:
    void destroy()
    {
        auto list = freeListHead;
        while (list)
        {
            auto next = list->next;
            delete list;
            list = next;
        }
        freeListHead = nullptr;
    }

    ~VirtualObjectPool() { destroy(); }

    void initPool(int numElements)
    {
        freeListHead = new FreeListNode();
        freeListHead->prev = freeListHead->next = nullptr;
        freeListHead->Offset = 0;
        freeListHead->Length = numElements;
    }

    int alloc(int size)
    {
        if (!freeListHead)
            return -1;
        auto freeBlock = freeListHead;
        while (freeBlock && freeBlock->Length < size)
            freeBlock = freeBlock->next;
        if (!freeBlock || freeBlock->Length < size)
            return -1;
        int result = freeBlock->Offset;
        freeBlock->Offset += size;
        freeBlock->Length -= size;
        if (freeBlock->Length == 0)
        {
            if (freeBlock->prev)
                freeBlock->prev->next = freeBlock->next;
            if (freeBlock->next)
                freeBlock->next->prev = freeBlock->prev;
            if (freeBlock == freeListHead)
                freeListHead = freeBlock->next;
            delete freeBlock;
        }
        return result;
    }
    void free(int offset, int size)
    {
        if (!freeListHead)
        {
            freeListHead = new FreeListNode();
            freeListHead->next = freeListHead->prev = nullptr;
            freeListHead->Length = size;
            freeListHead->Offset = offset;
            return;
        }
        auto freeListNode = freeListHead;
        FreeListNode* prevFreeNode = nullptr;
        while (freeListNode && freeListNode->Offset < offset + size)
        {
            prevFreeNode = freeListNode;
            freeListNode = freeListNode->next;
        }
        FreeListNode* newNode = new FreeListNode();
        newNode->Offset = offset;
        newNode->Length = size;
        newNode->prev = prevFreeNode;
        newNode->next = freeListNode;
        if (freeListNode)
            freeListNode->prev = newNode;
        if (prevFreeNode)
            prevFreeNode->next = newNode;
        if (freeListNode == freeListHead)
            freeListHead = newNode;
        if (prevFreeNode && prevFreeNode->Offset + prevFreeNode->Length == newNode->Offset)
        {
            prevFreeNode->Length += newNode->Length;
            prevFreeNode->next = freeListNode;
            if (freeListNode)
                freeListNode->prev = prevFreeNode;
            delete newNode;
            newNode = prevFreeNode;
        }
        if (freeListNode && newNode->Offset + newNode->Length == freeListNode->Offset)
        {
            newNode->Length += freeListNode->Length;
            newNode->next = freeListNode->next;
            if (freeListNode->next)
                freeListNode->next->prev = newNode;
            delete freeListNode;
        }
    }
};

} // namespace Slang
#endif