memory pool running on O(1)

Question

is there a way to design a C++ memory pool (for a specific class only) that can allocate and free memory in O(1)?

let's say I have class T, I was thinking of allocating only chunks of 100*sizeof(T) when needed. But then how can I deal with the fragmentation that occurs when a specific object is deleted in the chunk? I can have a boolean value for each slot to tell if the slot is occupied or not, but then I need an algorithm to give me the next free slot.

Is there any standard way to implement this in O(1)? I guess this is a fairly common thing

edit : image to see what I mean

Answer 1

This solution is using additional memory (which may or may not be what you want), also you'll have problems if you try to free a chunk twice in a row.

Preallocate enough memory. Divide it into chunks, one per object. Keep a list of free chunks. When you allocate a new object, pick a chunk from the top of the free chunks list. When you free an object, append its chunk to the list of free chunks. Both of these operations are O(1).

It would look something like this:

Init:

char* mem = new char[CHUNK_SIZE * OBJ_COUNT];
std::list<char*> free_chunks;
for (char* c = mem, int i = 0; i < OBJ_COUNT; ++i)
{
   free_chunks.push_back(c);
   c += CHUNK_SIZE;
}

Getting a new chunk for allocation:

   if(free_chunks.size() > 0)
   {
    char* c = free_chunks.back();
    free_chunks.pop_back();
    return c;
   }
   else{ // Error, not enough memory... }

Returning a chunk after deallocation:

free_chunks.push_back(c);

Answer 2

You can implement simple object pool with O(1) object retriving. But your objects need to have imternal pointer to next object. Inside constructor of pool some precalculating:

pool.reserve(capacity); //std::vector<Object*>
for (int i = 0; i < capacity; ++i) {
    pool.push_back(new Object());
}
for (int i = 0; i < capacity-1; ++i) {
    pool[i]->setNext(pool[i+1].get());
}
first_available = pool[0].get(); //variable where you store first free object 
pool[capacity-1]->setNext(NULL);

Then getObject method is:

getObject* getObject()
{
    getObject* obj = first_available;
    first_available = first_available->getNext();
    return obj;
}

void returnObject(Object* obj)
{
    obj->setNext(first_available);
    first_available = obj;
}

Hope it helps.