Allocator

Problem Statement

Allocator You have to implement an allocator that hands out variables inside a block of computer memory. The memory consists of N bytes, addressed 0 through N-1 . N is a power of 2. The allocator supports two operations. alloc(size) Allocates a variable that occupies size consecutive bytes and returns the address of its first byte. size is always 1 , 4 or 8 . No byte may belong to two variables at the same time. Whenever a run of size consecutive free bytes exists, the variable must be allocated. Among all addresses at which it fits, the allocator always picks the smallest one. If no run of size consecutive free bytes exists, the operation fails and returns -1 . free(address) Frees the variable that starts at address , so every byte that variable occupied becomes free again and can be handed out to a later alloc . free returns nothing. address is always a value returned by an earlier alloc for a variable that is still allocated. Why the smallest address Several positions may be able to