memory.h

#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cstdlib>
#include <cstring>

#define POOLSIZE 512

class Memory {
public:
    static Memory* Instance(); //singleton called with Memory::Instance()
    void* Allocate(size_t); //returns a void pointer and creates a respective pool if none available
    void  Free(void*, size_t); //marks the void pointer as available

private:
    Memory() {}
    ~Memory();
    static Memory* pInstance;
    //add a copy constructor
    //add an assignment operator

    struct Pool {
        void* pool;
        Pool* next;
    };

    std::map<size_t, Pool> poolList; //contains list of memory pool heads
    std::map<size_t, Pool>::iterator poolListIter;
    std::map<size_t,   std::set<void*> > chunkUsed; //used pointers
    std::map<size_t, std::queue<void*> > chunkFree; //available pointers
    std::map<size_t,   std::set<void*> >::iterator chunkUsedIter;
    std::map<size_t, std::queue<void*> >::iterator chunkFreeIter;

    void* ExpandPool(size_t, size_t);
    void SegmentPool(void*, size_t, size_t);
    void Cleanup();
    void Cleanup(size_t); //support to clear specific pools...
};

Memory* Memory::pInstance = NULL;

Memory::~Memory() {
    Cleanup();
}

Memory* Memory::Instance() {
    if(!pInstance) pInstance = new Memory();
    return pInstance;
}

void* Memory::Allocate(size_t size) {
    void* ptr = NULL;
    chunkFreeIter = chunkFree.find(size);

    if(chunkFreeIter == chunkFree.end()) { //if free chunk queue does not exist for size...
        //if there is no free chunk queue, that means there is no respective pool list
        poolListIter  = poolList.find(size);
        Pool chunk;
        chunk.pool = NULL; chunk.next = NULL;
        poolList.insert(std::pair<size_t, Pool>(size, chunk));
        ptr = ExpandPool(size, POOLSIZE); //returns void* to pool head

        std::queue<void*> freequeue;
        chunkFree.insert(std::pair<size_t, std::queue<void*> >(size, freequeue));

        SegmentPool(ptr, size, POOLSIZE); //Adds void pointers to free queue from pool

        std::set<void*> usedset;
        chunkUsed.insert(std::pair<size_t, std::set<void*> >(size, usedset));
    }
    else if (chunkFreeIter->second.empty()) { //if free chunk queue is empty...
        ptr = ExpandPool(size, POOLSIZE);
        SegmentPool(ptr, size, POOLSIZE);
    }

    chunkUsedIter = chunkUsed.find(size);
    ptr = (chunkFreeIter->second).front();

    (chunkFreeIter->second).pop(); //pop pointer from free queue
    chunkUsedIter->second.insert(ptr); //place into used set

    return ptr;
}

void Memory::Free(void* ptr, size_t sizetype) {
    chunkFreeIter = chunkFree.find(sizetype); // <size_t, queue<> >
    chunkUsedIter = chunkUsed.find(sizetype); // <size_t, set<> >
    chunkFreeIter->second.push(ptr); //add pointer to free queue
    chunkUsedIter->second.erase(ptr);
}


void* Memory::ExpandPool(size_t sizetype, size_t sizepool = POOLSIZE) {
    poolListIter = poolList.find(sizetype); //assumption that pool exists
    Pool* pChunk = &(poolListIter->second);

    while(pChunk->next != NULL) pChunk = pChunk->next; //iterate to last
    pChunk->next = new Pool;
    pChunk = pChunk->next;

    pChunk->pool = malloc(sizetype*sizepool);
    pChunk->next = NULL;

    return pChunk->pool;
}

void Memory::SegmentPool(void* pool, size_t sizetype, size_t sizepool) {
    void* ptr;
    chunkFreeIter = chunkFree.find(sizetype); //chunkFreeIter->second == (queue<>)

    for(size_t ii = 0; ii < sizepool; ii++) {
        ptr = (char*) pool + sizetype * ii;
        chunkFreeIter->second.push(ptr);
    }
}

void Memory::Cleanup() {
    /*
    Pool.pool == void*
    Pool.next == Pool*
    */

    chunkFree.clear();
    chunkUsed.clear();

    for(poolListIter = poolList.begin(); poolListIter != poolList.end(); poolListIter++) {
        Pool* pHead  = &(poolListIter->second);
        free(pHead->pool);

        if(pHead->next != NULL) {
            Pool* pChunk = pHead->next;
            while(pChunk->next != NULL) {
                Pool* pNext = pChunk->next;
                free(pChunk->pool);
                delete pChunk;
                pChunk = pNext;
            }
            free(pChunk->pool);
            delete pChunk;
        }
    }
}

void Memory::Cleanup(size_t sizetype) {
    chunkUsed.erase(sizetype);
    chunkFree.erase(sizetype);

    poolListIter = poolList.find(sizetype);
    Pool* pHead  = &(poolListIter->second);
    free(pHead->pool);

    if(pHead->next != NULL) {
        Pool* pChunk = pHead->next;
        while(pChunk->next != NULL) {
            Pool* pNext = pChunk->next;
            free(pChunk->pool); //void*
            delete pChunk;
            pChunk = pNext;
        }
        free(pChunk->pool);
        delete pChunk;
    }

    poolList.erase(poolListIter);
}


class foo {
public:
    foo(double a, double b) : x(a), y(b) {}
    void* operator new(size_t size)  { return Memory::Instance()->Allocate(size); }
    void  operator delete(void* ptr) { Memory::Instance()->Free(ptr, sizeof(foo)); }

private:
    double x, y;
};


int main() {
    foo* array[1000];
    for(int i = 0; i < 5000; i++) {
        for(int j = 0; j < 1000; j++) {
            array[j] = new foo(i, j);
        }
        for(int j = 0; j < 1000; j++) {
            delete array[j];
        }
    }

    return 0;
}