CIDR Subnet Allocator (C)
Topics: backtracking, assignment, recursion
Problem
Allocate fixed-size blocks (think: subnets carved out of a CIDR range) from a pool
of free blocks. Each request must be given a distinct free block whose size is
at least the requested size — a small bipartite-assignment problem.
typedef struct { int offset, size; } Block;
typedef struct { const char *name; int size; } Request;
bool allocate_all(const Block *freeb, int nfree, const Request *reqs, int nreq, Block *out);
Return true if every request can be placed; on success fill out[] (parallel
to reqs[]) where out[i] carries the chosen free block's offset and the
request's size. Return false if no complete assignment exists.
Key concepts
- Backtracking, not greedy: assigning each request to the first block that
fits can strand a later request. Place
reqs[i] in some unused big-enough block,
recurse on the rest, and on a dead end undo the choice and try the next block.
- Distinct blocks: mark a block used while a request holds it; a single free
block can't satisfy two requests.
- The classic trap: free
{0,4},{4,2}, requests a=2, b=4. Greedy gives a
the {0,4} block, leaving nothing for b=4 — only backtracking reassigns a to
{4,2} and frees {0,4} for b.
A fixed used[] array tracks which blocks are taken — no allocation needed.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/subnet && /tmp/subnet
Sign in to submit your solution.