a pool / fixed-size-block allocator
Imagine a board with a hundred identical pegholes, used to hold a hundred identical pegs. Handing out a peg is trivial — grab any empty hole's peg. Returning one is trivial too — drop it in any empty hole. Because every peg and every hole is the same size, you never have to measure, search, or worry about fit. A pool allocator works exactly like this for memory: it manages many blocks that are all the same fixed size, so allocation and freeing become a single pointer move each.
Here is the construction. You decide one block size up front — say sizeof(struct Particle), 64 bytes — and carve a big slab of memory into an array of those fixed-size slots. The free slots are strung together into a free list, with each free slot's first bytes holding a pointer to the next free slot (the inline free-list-pointer trick again, safe because a free slot is unused). To allocate, you pop the head of the free list: take the first free slot, set the list head to that slot's next pointer, done. To free, you push: write the current list head into the freed slot's first bytes and make it the new head. Both operations are O(1) with no size argument, no rounding, no fit search, and no fragmentation — every slot is interchangeable, so a freed slot perfectly fits the next request.
Pools are the standard tool when a program creates and destroys huge numbers of one specific object type: particles in a game, connection records in a server, nodes in a tree. They are fast, predictable (constant-time, no worst-case search), and free of fragmentation because all blocks are identical. The honest limits: a pool only serves one size, so you typically run several pools for different object types; and a single pool of N slots can hold at most N objects — you must size it, or chain in more slabs when it fills.
typedef struct Slot { struct Slot *next; } Slot; Slot *free_head; /* head of the free list */ void *pool_alloc(void) { if (!free_head) return NULL; Slot *s = free_head; /* pop the head ... */ free_head = s->next; /* ... O(1), no search */ return s; } void pool_free(void *p) { Slot *s = p; s->next = free_head; /* push it back, O(1) */ free_head = s; }
Every slot is the same size, so alloc and free are a single list pop and push -- no fit search, no fragmentation.
A pool fixes the size at construction; ask it for a different size and it cannot help. This is the deliberate trade: it gives up generality to gain constant-time, fragmentation-free service for one object type.