Bitsets, Bitmaps, and Memory Pools

This chapter covers three compact, performance-oriented structures: bitsets, bitmaps, and memory pools.

Why This Matters

Bitsets and bitmaps pack boolean data into individual bits, saving memory and enabling fast set operations. Memory pools provide deterministic, fast allocation for fixed-size objects — essential in embedded and high-performance systems.

Prerequisites

• c.ds.1 — foundations.
• c.ops.bitwise — bit operators.

Core Concept

Bitset

A bitset stores a set of small integers as bits in an array of unsigned words. Bit i is in word i / W at position i % W, where W is the word width.

typedef struct {
    unsigned long *words;
    size_t nwords;
} Bitset;

Operations: set, clear, test, and (for whole sets) union/intersection/ difference via |, &, ~.

Bitmap

A bitmap is the same idea applied to a fixed region (e.g., a frame buffer, a disk block map, an allocator's free-block map). "Bitmap" usually implies a fixed array of bits with a known mapping.

Memory pool

A memory pool allocates fixed-size blocks from a preallocated region with a free list (c.mem.pool), giving O(1) allocation/deallocation and no fragmentation for that size.

Examples

Bitset set/clear/test

#include <stddef.h>
#include <stdbool.h>
#include <limits.h>

#define WORD_BITS (sizeof(unsigned long) * CHAR_BIT)

typedef struct {
    unsigned long *words;
    size_t nwords;
} Bitset;

static bool bitset_set(Bitset *b, size_t i)
{
    size_t w = i / WORD_BITS, bit = i % WORD_BITS;
    if (w >= b->nwords) return false;
    b->words[w] |=  (1UL << bit);
    return true;
}

static bool bitset_test(const Bitset *b, size_t i)
{
    size_t w = i / WORD_BITS, bit = i % WORD_BITS;
    if (w >= b->nwords) return false;
    return (b->words[w] >> bit) & 1UL;
}

static void bitset_clear(Bitset *b, size_t i)
{
    size_t w = i / WORD_BITS, bit = i % WORD_BITS;
    if (w < b->nwords)
        b->words[w] &= ~(1UL << bit);
}

Memory pool (fixed-size free list)

typedef struct Block {
    struct Block *next;
} Block;

typedef struct {
    Block *free_list;
    size_t block_size;
} Pool;

void *pool_alloc(Pool *p)
{
    if (!p->free_list) return NULL;
    Block *b = p->free_list;
    p->free_list = b->next;
    return b;
}

void pool_free(Pool *p, void *ptr)
{
    Block *b = ptr;
    b->next = p->free_list;
    p->free_list = b;
}

The free-list pointer is stored inside each free block, so there is no extra per-object allocation.

How It Works

Bitsets use one word per W bits; a set operation is a single |/&/~ on the word. A pool stores free blocks in a singly linked list, pushing/popping the head in O(1). The pool must be initialized with a contiguous block and divided into fixed-size pieces.

Variations

Bit-level population count

__builtin_popcount (GCC/Clang) counts set bits in one instruction on supporting hardware.

Bitmap allocation

A bitmap can track which blocks are free in a larger allocator: find a zero bit, set it, allocate; clear it to free. This is the slab allocator's core (c.mem.slab).

Common Mistakes

• Assuming 1UL << bit is safe when bit can equal the word width (shift UB).
• Not sizing words to hold the maximum index.
• Forgetting to initialize the pool free list.
• Calling free on a pool pointer (mixing allocators).

Undefined Behavior

• Shift by >= word width. VERIFIED
• Reading/writing out of the words array. VERIFIED

Portability

• Plain C; the word size is unsigned long, which is implementation-defined.
• Use CHAR_BIT and sizeof rather than hard-coding 32/64.

Under the Hood

Bitsets are compact and cache-friendly (each word covers many bits). Pools avoid the general allocator's overhead and are deterministic — no search, no coalescing.

Practical Usage

• Use bitsets for sets of small integers (flags, primes sieve, visited sets).
• Use bitmaps for allocators, disk maps, and pixel masks.
• Use memory pools for fixed-size objects in embedded and real-time code.

Exercises

1. Implement a bitset with set, clear, test, and count. 2. Implement union, intersection, and difference over two bitsets. 3. Initialize a memory pool from a static buffer and allocate/free many blocks. 4. Use a bitmap to implement a simple fixed-size block allocator.

Deep Challenge

Implement a slab allocator that uses a bitmap to track free slots across three size classes, and explain its complexity, alignment, and determinism compared to malloc.

Related Concepts

• c.alg.bit-algo — bit algorithms.
• c.mem.pool — pools.
• c.emb.3 — bit manipulation in embedded.

References

• Standard data-structure literature; kernel slab allocator design.

Verification

• Bitset/pool semantics and bit operations. VERIFIED
• Shift by >= width is UB. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Bitset set/clear/test
• [ ] Bitmap
• [ ] Memory pool
• [ ] Shift width UB

Mastery levels