</>EmbeddedInterview

Implement a bitmap allocator with find-first-zero.

Medium"Coding: Systems, Bitmaps & Virtualization"
#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.