Growing (and shrinking) memory pool

Question

Let's say, for the purpose of the question, we have a memory pool that has n blocks allocated initially. However, when the capacity is reached, the pool wants to grow and become twice the size it was (2n).

Now this resize operation can be done with realloc in C, however the function itself may return a pointer to a different memory (with the old data copied in).

This means the pointers returned by the memory pool allocator may no longer be valid (since the memory may have been moved).

What would be a nice way to overcome this problem? Or is it even possible at all?

Answer 1

Allocate out of multiple non-contiguous pools of memory. When one pool is full, allocate a second pool, allowing it to be someplace else in your virtual address space.

Then the problem is one of keeping track of where your pools are. Typically you'd use some of the space in each pool for bookkeeping. For example, you might reserve one pointer's worth of space to keep a simple linear linked list of all the pools. More sophisticated allocators tend to require more bookkeeping overhead.

Answer 2

Instead of using realloc, malloc a new/additional chunk of blocks (assuming there's no reason why the blocks, which are managed and returned and returned by your pool allocator, need to be in a single contiguous chunk of memory).