PoolArray - C array tracking

A pattern I have found myself using a number of times is a pool array, you can just use an array, and simply scan over it when you need to find an unused item, however that can be a little inefficient, another strategy could be to use a linked link and allocate and free individual items as you need, this is an even worse strategy.

Instead PoolArray, uses a couple of doubly linked lists to keep track of active and available items in a pool of items. Being doubly linked you can remove an item from a list without needing to scan through it. This means tracking down an unused item is fast, albeit at the cost of a little extra memory...

In order to make my take on a pool array generic, you need to pass the array to the initialization function as a void pointer, meaning you also have to specify the item size and the number of items in the array. Supposing you have a struct something like this, and an accompanying array.

typedef struct shot {
    ...
} shot;

shot shotArray[totalShots];
PoolArray pool;

initializing the pool array would be done like this

PoolArrayInit(&pool, shotArray, sizeof(shot), totalShots );

When we want to find an unused item, just get the next item from the pool

    shot* s = PoolArrayGetNextItem(&pool);
    if (!s) {
        return;
    }

The item you get back from the pool should always be checked in case the pool is at capacity in which case you will get NULL back. When you've finished with an item just use

PoolArrayRetireNode(&pool, node);

Note that you need to use a PoolArrayNode for this, this is usually no problem as you'll be iterating through the active list.... if you're in a situation where you only have an item pointer which should be a rare situation, use it to set a flag in your stuct to mark it for retirement in the next update loop.

You can loop through a list with a for loop as long you're not retiring nodes... (for example when rendering, if you have a separate update and render loop which is generally good practice)

for(PoolArrayNode* node = pool.activeList; node; node = node->next) {

If you do need to retire an item while looping through the active list, you must do things differently.

PoolArrayNode* node = pa.activeList;
while(node) {
    PoolArrayNode* next = node->next;
    shot* s = (shot*)node->userData;
 
    if(checkShot(s)) {
        PoolArrayRetireNode(&pa, node);
    }

    node = next;
}

Note that at the end of the loop node is set with the value you got at the start of the loop, the reason for this is that modifying a list you are looping through it is inadvisable and the node you have retired is now on a different list.... this is why you must find out which is the next node before you retire it (if you do).

Its also possible to retire all the nodes in the active list by calling

PoolArrayDeactivateAll(&pool);

When you have finished completely with the pool don't forget to destroy it

PoolArrayDestroy(pool);

If you've chosen to allocate the array that backs the pool array you can now free that too....

This it basically all you need to know however, you can log failures of PoolArrayGetNextItem just to check you have an appropriate size for your pool, you might even decide to reserve a number of items for the player and not bother if the baddies can't shoot occasionally.... in a function to set up a shot you might do something like this

void addShot(bool isAlien, Vector2 p)
{
    // is there available shots it the pool for the aliens
    if (isAlien) {
        if ( pool.Available - reservedShots < 1) {
            return;
        }
    }
    // enlist a shot...
    shot* s = PoolArrayGetNextItem(&pa);
    if (!s) {
        return;
    }
    s->isAlien = isAlien;
    s->pos.x = p.x;
    s->pos.y = p.y;

This gives the player priority over the pool, while still allowing the the baddies to fill the rest of the pool to capacity. Note that you don't even need to return the new item from this function as the item is now in the active list ready to be used with all the other active items.

While there are some minor caveats to using the pool array like looping and retiring I think its reasonably easy to use and it does mean you can just reserve a bunch of items in a pool and side step any of the potential pitfalls of allocating individual items on the fly or scanning through a possibly large array hunting for an available unused item.

Needless to say you should never attempt to directly manipulate the pool lists or the available count as this will likely be more trouble than its worth and will probably break things.

You can get the self contained header and a simple console app example here

Enjoy!