Size Classes

Every allocator you have built so far walks a list — O(n) in the number of free blocks. Real programs allocate millions of times per second; production allocators cannot afford the walk. Their answer is segregated free lists: declare a fixed set of size classes up front and keep ONE free list per class.

classes:   16    32    64      128    256    512    1024
free:     [ ]   [ ]   [a,b]    [ ]    [c]    [ ]    [ ]

ALLOC n rounds n UP to the smallest class that holds it and pops that class's list — O(1), no searching. FREE pushes the block back onto its class's list — O(1) again. Segregation is the backbone of tcmalloc, jemalloc, and mimalloc, and it is what makes best-fit affordable: within one class every block is the same size, so "best" is whatever you pop.

The rounding rule (and its off-by-one)

"Smallest class greater than or equal to the request" has boundaries worth spelling out:

ALLOC 16   -> class=16      exact boundary stays put
ALLOC 17   -> class=32      one byte over jumps a whole class
ALLOC 2000 -> TOO_LARGE     bigger than the largest class

Write the comparison as class >= size. Requests beyond 1024 have no class here — print TOO_LARGE. Real allocators route oversized requests around the class system entirely: glibc hands anything over 128 KB straight to mmap.

What rounding costs

The gap between request and class is pure waste — internal fragmentation. With power-of-two spacing the worst case is just under 50% (a 65-byte request occupies 128 bytes). That is why production allocators space classes tighter: jemalloc's run 16, 32, 48, 64, 80, ... — subdividing each power of two caps the waste near 25% at the cost of more lists. Our seven classes keep the model readable; the Fragmentation lesson has you measure the waste precisely.

This lesson's bookkeeping

Per class, track two counters: blocks currently ALLOCATED, and blocks sitting on the FREE list.

• ALLOC <size> — find the class. If its free list is non-empty, REUSE a freed block: free count -1, alloc count +1. Otherwise mint a new block: alloc +1. Either way print class=<n>.
• FREE <class> — return one allocated block of that class to its list: alloc -1, free +1, print OK. If that class has nothing allocated, print BAD.
• STATS — ALL seven classes, in ascending order, every time — zeros included: <c>:alloc=<a>:free=<f>.

Bonwick's slab allocator (two lessons ahead) pushes segregation one step further: a pool per object TYPE, not per size — zero rounding waste for the type it serves.

Your exercise

Two tests pin the rounding rule from both sides. Hidden test 5: ALLOC 17 must print exactly class=32. Test 6: ALLOC 16 must print class=16 — if your comparison is the strict class > size, this one rounds up to class=32 and fails. Test 6 also catches the reuse rule: after ALLOC 16, FREE 16, ALLOC 16, its STATS must read 16:alloc=1:free=0. If your ALLOC always mints a new block without checking the free list first, you print 16:alloc=1:free=1 — a phantom block the grader rejects.