Allocate from buffer in C

Question

I am building a simple particle system and want to use a single array buffer of structs to manage my particles. That said, I can't find a C function that allows me to malloc() and free() from an arbitrary buffer. Here is some pseudocode to show my intent:

Particle* particles = (Particle*) malloc( sizeof(Particle) * numParticles );
Particle* firstParticle = <buffer_alloc>( particles );
initialize_particle( firstParticle );
// ... Some more stuff
if (firstParticle->life < 0)
    <buffer_free>( firstParticle );

// @ program's end
free(particles);

Where <buffer_alloc> and <buffer_free> are functions that allocate and free memory chunks from arbitrary pointers (possibly with additional metadata such as buffer length, etc.). Do such functions exist and/or is there a better way to do this? Thank you!

Answer 1

Yeah, you’d have to write your own. It’s so simple it’s really silly, but its performance will scream in comparison to simply using malloc() and free() all the time....

static const int maxParticles = 1000;

static Particle particleBuf[maxParticles]; // global static array

static Particle* headParticle;

void initParticleAllocator()
{
    Particle* p = particleBuf;
    Particle* pEnd = &particleBuf[maxParticles-1];
    // create a linked list of unallocated Particles
    while (p!=pEnd)
    {
        *((Particle**)p) = p+1;
        ++p;
    }
    *((Particle**)p) = NULL; // terminate the end of the list
    headParticle = particleBuf; // point 'head' at the 1st unalloc'ed one
}

Particle* ParticleAlloc()
{
    // grab the next unalloc'ed Particle from the list
    Particle* ret = headParticle;
    if (ret)
        headParticle = *(Particle**)ret;
    return ret; // will return NULL if no more available
}

void ParticleFree(Particle* p)
{
    // return p to the list of unalloc'ed Particles
    *((Particle**)p) = headParticle;
    headParticle = p;
}

You could modify the approach above to not start with any global static array at all, and use malloc() at first when the user calls ParticleAlloc(), but when Particles are returned, don't call free() but instead add the returned ones to the linked list of unalloc'ed particles. Then the next caller to ParticleAlloc() will get one off the list of free Particles rather than use malloc(). Any time there are no more on the free list, your ParticleAlloc() function could then fall back on malloc(). Or use a mix of the two strategies, which would really be the best of both worlds: If you know that your user will almost certainly be using at least 1000 Particles but occasionally might need more, you could start with a static array of 1000 and fall back on calling malloc() if you run out. If you do it that way, the malloc()'ed ones do not need special handling; just add them to your list of unalloc'ed Particles when they come back to ParticleFree(). You do NOT need to bother calling free() on them when your program exits; the OS will free the process'es entire memory space, so any leaked memory will clear up at that point.

I should mention that since you question was tagged "C" and not "C++", I answered it in the form of a C solution. In C++, the best way to implement this same thing would be to add "operator new" and "operator delete" methods to your Particle class. They would contain basically the same code as I showed above, but they override (not overload) the global 'new' operator and, for the Particle class only, define a specialized allocator that replaces global 'new'. The cool thing is that users of Particle objects don't even have to know that there's a special allocator; they simply use 'new' and 'delete' as normal and remain blissfully unaware that their Particle objects are coming from a special pre-allocated pool.

Answer 2

Oh, sorry. This question is C only I see. Not C++. Well, if it was C++ the following would help you out.

Look at Boost's pool allocation library.

It sounds to me that each of your allocations is the same size? The size of a particle, correct? If so the pool allocation functions from Boost will work really well and you don't have to write your own.

Answer 3

You would have to write your own, or find someone who has already written them and reuse what they wrote. There isn't a standard C library to manage that scenario, AFAIK.

You'd probably need 4 functions for your 'buffer allocation' code:

typedef struct ba_handle ba_handle;

ba_handle *ba_create(size_t element_size, size_t initial_space);
void  ba_destroy(ba_handle *ba);

void *ba_alloc(ba_handle *ba);
void  ba_free(ba_handle *ba, void *space);

The create function would do the initial allocation of space, and arrange to parcel out the information in units of the element_size. The returned handle allows you to have separate buffer allocations for different types (or even for the same type several times). The destroy function forcibly releases all the space associated with the handle.

The allocate function provides you with a new unit of space for use. The free function releases that for reuse.

Behind the scenes, the code keeps track of which units are in use (a bit map, perhaps) and might allocate extra space as needed, or might deny space when the initial allocation is used up. You could arrange for it to fail more or less dramatically when it runs out of space (so the allocator never returns a null pointer). Clearly, the free function can validate that the pointer it is given was one it supplied by the buffer allocator handle that is currently in use. This allows it to detect some errors that regular free() does not normally detect (though the GNU C library version of malloc() et al does seem to do some sanity checking that others do not necessarily do).

Answer 4

Maybe try something like this instead...

Particle * particles[numParticles];
particles[0] = malloc(sizeof(Particle));
initialize_particle( particle[0] );

// ... Some more stuff
if (particle[0]->life < 0)
    free( particle[0] );

// @ program's end
// don't free(particles);

Answer 5

I am building a simple particle system and want to use a single array buffer of structs to manage my particles.

I think you answered it:

static Particle myParticleArray[numParticles];

Gets allocated at the start of the program and deallocated at the end, simple. Or do like your pseudocode and malloc the array all at once. You might ask yourself why allocate a single particle, why not allocate the whole system? Write your API functions to take a pointer to a particle array and an index.