Realigning pointers after memory realign

Question

I have a memory pool which is a set size and is split into segments of a given size. When I delete some data it flags the segments that data was using as free. Next time I try to allocate memory but don't have space, I realign the memory by shifting all the data down (e.g. First 2 segments are cleared, move all data down by 2 blocks). This all works fine but my issue is my pointers to that data don't change and I am not sure how I can go about doing this.

I allocate memory from my pool by returning a void* to the space in memory, lets assume my pool is the size to hold 2*sizeof(Data).

Data* poolTest = new(pool->GetMemory(sizeof(Data))) Data(5, 5, 5);

So the pool has no reference to the pointer poolTest.

So now if I do this:

pool->Free(poolTest);
Data* poolTest2 = new(pool->GetMemory(sizeof(Data))) Data(4, 5, 5);
Data* poolTest3 = new(pool->GetMemory(sizeof(Data))) Data(3, 5, 5);

The creation of poolTest3 triggers a realignment of memory and now poolTest2 points to the same address as poolTest3 and poolTest1 points to the address that poolTest2 should point to.

I might just be missing something, or my structure is screwed up but I am really stuck on this.

Answer 1

To rephrase your question:

I want to move data around in memory to make room for new allocations. How to I make sure existing pointers still point to the right places?

You can't, unless you keep track of all the pointers, say, by using an array, and instead of accessing your data like this:

*direct_ptr

you now have to do this:

*ptr_map[indirect_ptr]

Every time you move things around, you need to modify ptr_map accordingly.

The array should behave like a stack. You could maybe write a pointer wrapper class that increments some global/static index in the constructor and decrements it in the destructor.

It may save a little space but is quite inefficient for the computer and messy for the programmer.

If you want to do your own memory management, make sure you check out:

https://en.wikipedia.org/wiki/Buddy_memory_allocation

https://en.wikipedia.org/wiki/Slab_allocation

And a good overview of existing techniques:

http://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf