Implement a bitmap allocator with find-first-zero.
#include <stdint.h>
#define NBLOCKS 256u
static uint32_t bitmap[NBLOCKS / 32]; /* 1 = used, 0 = free */
int find_first_zero(void)
{
for (unsigned w = 0; w < NBLOCKS / 32; w++) {
if (bitmap[w] != 0xFFFFFFFFu) { /* skip full words quickly */
unsigned bit = (unsigned)__builtin_ctz(~bitmap[w]); /* lowest 0 bit */
return (int)(w * 32u + bit);
}
}
return -1; /* all used */
}
int bm_alloc(void)
{
int i = find_first_zero();
if (i >= 0) bitmap[i / 32] |= 1u << (i % 32);
return i;
}
void bm_free(int i)
{
bitmap[i / 32] &= ~(1u << (i % 32));
}
/* allocate n contiguous blocks (simple scan) */
int bm_alloc_range(unsigned n)
{
unsigned run = 0;
for (unsigned i = 0; i < NBLOCKS; i++) {
if (bitmap[i / 32] & (1u << (i % 32))) { run = 0; continue; }
if (++run == n) {
unsigned start = i + 1 - n;
for (unsigned j = start; j <= i; j++) bitmap[j / 32] |= 1u << (j % 32);
return (int)start;
}
}
return -1;
}
Points: one bit per block makes the metadata tiny (256 blocks → 32 bytes); scan word by word and use ctz(~word) to find the first free bit in O(1) per word; add a "next search position" hint to avoid rescanning full words; protect with a lock in concurrent code (or use atomic bit operations). Used for flash sector maps, file-system block allocation, PID and IRQ number allocation (Linux ida/bitmap_find_next_zero_area), and page-frame allocation in simple kernels.