Find the Bug A Book of Incorrect Programs

Memory Allocator

This function is a memory allocator. Allocations are made from a chunk of memory, which in C is simply an array of chars. Memory is always allocated in multiples of a constant block size, so allocations are internally rounded up in size.

A consecutive group of blocks of memory, whether free or allocated, will be called a span. A second “in use” array tracks whether each block is allocated or freed; the “in use” array has one element per block. If a span is free, all the entries in the “in use” array that correspond to the blocks in the span contain the same positive value, which is the number of blocks in the span. If a span is ...