Fixed-Block Memory Pool
Many firmware projects forbid malloc. Implement a pool of POOL_BLOCKS blocks of BLOCK_SIZE bytes from a static array:
pool_init()prepares the pool.pool_alloc()returns a free block in O(1), orNULLif none remain.pool_free(p)returns a block in O(1).
Use no memory beyond the static array itself (no separate bitmap).
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
A free block is not in use, so you can store a "next free block" pointer inside it. Chain all free blocks into a singly linked free list.
#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#define BLOCK_SIZE 32u
#define POOL_BLOCKS 4u
typedef union block {
union block *next; /* valid while free */
unsigned char data[BLOCK_SIZE]; /* valid while allocated */
} block_t;
static block_t pool[POOL_BLOCKS];
static block_t *free_list;
void pool_init(void)
{
for (unsigned i = 0; i < POOL_BLOCKS - 1u; i++)
pool[i].next = &pool[i + 1];
pool[POOL_BLOCKS - 1u].next = NULL;
free_list = &pool[0];
}
void *pool_alloc(void)
{
block_t *b = free_list;
if (b) free_list = b->next;
return b;
}
void pool_free(void *p)
{
if (!p) return;
block_t *b = p;
b->next = free_list;
free_list = b;
}
The union guarantees each block is large enough and aligned for a pointer. Allocation pops the head of the free list and freeing pushes onto it, both O(1) and deterministic, with no fragmentation because every block is the same size. This is the idea behind RTOS memory pools (ThreadX block pools, Zephyr k_mem_slab).
For use from both tasks and ISRs, wrap alloc and free in a critical section. Debug builds often add a magic value or a range check in pool_free to catch double frees and foreign pointers.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
pool_init();
void *b[POOL_BLOCKS];
for (unsigned i = 0; i < POOL_BLOCKS; i++) { b[i] = pool_alloc(); CHECK(b[i] != NULL); }
CHECK(pool_alloc() == NULL);
for (unsigned i = 0; i < POOL_BLOCKS; i++)
for (unsigned j = i + 1; j < POOL_BLOCKS; j++) CHECK(b[i] != b[j]);
CHECK(((uintptr_t)b[0] % sizeof(void *)) == 0);
pool_free(b[2]);
CHECK(pool_alloc() == b[2]);
pool_free(b[0]); pool_free(b[1]);
CHECK(pool_alloc() != NULL && pool_alloc() != NULL && pool_alloc() == NULL);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}