fragmentedobjectallocator.cpp

// Fragmented object allocator
// 
// Simplified code as example for a fragmented object allocator.
//
// by feyd//godX.de
 
#include <cstdint>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#ifdef _WINDOWS
#include <windows.h>
#else
#include <time.h>
#endif
 
template<class _TYPE>
class CFragmentedObjectAllocator
{
public:
    CFragmentedObjectAllocator(size_t nSize) : 
        m_objects(nSize), m_fragments(nSize), 
        m_nFragmentPosition(0), m_nMaxPosition(0), 
        m_nSize(nSize) {};
    virtual ~CFragmentedObjectAllocator() {};
 
    virtual _TYPE* Allocate()
    {
        if(m_nFragmentPosition>0)
            return &m_objects[m_fragments[--m_nFragmentPosition]];
        if(m_nMaxPosition>=m_nSize)
            return nullptr;
        return &m_objects[m_nMaxPosition++];
    }
 
    virtual void Free(const _TYPE* pObject)
    {
        size_t nIndex = pObject-&m_objects[0];
        m_fragments[m_nFragmentPosition++] = nIndex;
    }
private:
    std::vector<_TYPE> m_objects;
    std::vector<size_t> m_fragments;
    size_t m_nFragmentPosition;
    size_t m_nMaxPosition;
    size_t m_nSize;
};
 
template<class _TYPE>
class CNormalObjectAllocator
{
public:
    CNormalObjectAllocator(size_t nSize) {};
    virtual ~CNormalObjectAllocator() {};
 
    virtual _TYPE* Allocate()
    {
        return new _TYPE;
    }
 
    virtual void Free(const _TYPE* pObject)
    {
        delete pObject;
    }
};
 
struct BinaryTreeNode
{
    BinaryTreeNode* pParent;
    BinaryTreeNode* pSide[2];
    bool bWordEnd;
};
 
template<class _ALLOC>
class CWordIndex : _ALLOC
{
public:
    CWordIndex(size_t nSize) : _ALLOC(nSize)
    {
        m_pRoot = _ALLOC::Allocate();
        m_pRoot->pParent = nullptr;
        m_pRoot->pSide[0] = nullptr;
        m_pRoot->pSide[1] = nullptr;
        m_pRoot->bWordEnd = false;
    }
 
    virtual ~CWordIndex()
    {
        RecursiveDelete(m_pRoot);
        _ALLOC::Free(m_pRoot);
    }
 
    void Add(const char* pWord)
    {
        BinaryTreeNode* pIndex = Find(pWord, true);
        pIndex->bWordEnd = true;
    }
 
    void Remove(const char* pWord)
    {
        BinaryTreeNode* pIndex = Find(pWord, false);
        if(pIndex)
            pIndex->bWordEnd = false;
        while(pIndex && pIndex!=m_pRoot)
        {
            if(pIndex->pSide[0] || pIndex->pSide[1])
                break;
 
            BinaryTreeNode* pParent = pIndex->pParent;
            if(pParent->pSide[0]==pIndex)
                pParent->pSide[0] = nullptr;
            if(pParent->pSide[1]==pIndex)
                pParent->pSide[1] = nullptr;
            _ALLOC::Free(pIndex);
            pIndex = pParent;
        }
    }
 
    BinaryTreeNode* Find(const char* pWord, bool bCreate=false)
    {
        BinaryTreeNode* pIndex = m_pRoot;
        while(*pWord)
        {
            for(int n=7; n>=0; n--)
            {
                int nSide = (*pWord>>n)&1;
                if(!pIndex->pSide[nSide])
                {
                    if(!bCreate)
                        return nullptr;
                    BinaryTreeNode* pNewIndex = _ALLOC::Allocate();
                    pIndex->pSide[nSide] = pNewIndex;
                    pNewIndex->pParent = pIndex;
                    pNewIndex->pSide[0] = nullptr;
                    pNewIndex->pSide[1] = nullptr;
                    pNewIndex->bWordEnd = false;
                    pIndex = pNewIndex;
                } else {
                    pIndex = pIndex->pSide[nSide];
                }
            }
            pWord++;
        }
        return pIndex;
    }
 
private:
    void RecursiveDelete(BinaryTreeNode* pIndex)
    {
        if(!pIndex)
            return;
        RecursiveDelete(pIndex->pSide[0]);
        RecursiveDelete(pIndex->pSide[1]);
    }
    BinaryTreeNode* m_pRoot;
};
 
uint64_t GetTime()
{
#ifdef _WINDOWS
    return GetTickCount();
#else
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec*1000+t.tv_nsec/1000000;
#endif
}
 
template<class _ALLOC>
class CTest
{
public:
    CTest(const char* pType, int argc, const char* argv[], int nNumberOfTests)
    {
        CWordIndex<_ALLOC> index(16384);
 
        int nTime = GetTime();
        for(int m=0; m<nNumberOfTests; m++)
        {
            for(int n=1; n<argc-1; n++)
                index.Add(argv[n]);
            for(int n=1; n<argc-1; n++)
                index.Remove(argv[n]);
        }
        nTime = GetTime()-nTime;
        printf("    %s object allocator %dms for %d iterations\r\n", pType, nTime, nNumberOfTests);
 
        for(int n=1; n<argc-1; n++)
            index.Add(argv[n]);
        BinaryTreeNode* pIndex = index.Find(argv[argc-1]);
        if(!pIndex)
        {
            printf("    '%s' not found\r\n", argv[argc-1]);
        } else {
            if(!pIndex->bWordEnd)
            {
                printf("    '%s' not found\r\n", argv[argc-1]);
            } else {
                printf("    '%s' found\r\n", argv[argc-1]);
            }
        }       
    }
};
 
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
    printf("Fragmented Object Allocator test...\r\n\r\n");
 
    if(argc>2)
    {
        int nNumberOfTests = 100000;
 
        CTest<CFragmentedObjectAllocator<BinaryTreeNode> > testFragmented("Fragmented", argc, argv, nNumberOfTests);
        CTest<CNormalObjectAllocator<BinaryTreeNode> > testNormal("Normal", argc, argv, nNumberOfTests);
    } else {
        printf("not enough arguments\r\n");
    }
    return 0;
}