Implement a simple placement algorithm (e.g. Best/First/Worst-fit) for a memory pool. A memory pool is just a large piece of contiguous memory that you want to use for all future requests.

Block merging and splitting is not required.

Implement a fixed-size memory allocator. Block coalescing and block splitting will not be required.

You will need to correctly implement one of the standard placement algorithms: Worst fit, First-fit, Best-fit

You will complete the functions allocate, release and associated placement function in the file memorypool.c. These functions will behave like malloc and free respectively except that allocate memory from an external, fixed size memory pool. Your code will not call malloc, sbrk etc, instead, when allocate requires more memory it will call our function void* growpool(size_t extra) which behaves like sbrk except it returns NULL if no more memory is available. The pool is contiguous (you can assume that it is a simple char array).

A very simple (but incomplete!) allocator would just request more memory for each allocate request:

void* allocate(size_t size){

void* mem = growpool(size);

// NULL if we are less than size bytes from the end of the pool

return mem;

}

void release(void*ptr) { /* do nothing */}

typedef struct Block {

struct Block *next;

size_t size; // # of usable bytes in this block

int is_free; // 0 (allocated) or 1 (available)

} Block;

The linked list will contain all currently-allocated blocks and available free blocks.A simple O(N) search of all of these blocks will have sufficient performance.

Assume that the block entry is immediately before the available memory region. For example,

int main(){

void* mem = allocate(100); // internally this will call growpool( 100+sizeof(Block) )

// The internal linked list now includes this allocation

Block* b = mem - sizeof(Block);

// Expect b->size to be 100,

// b->is_free to be 0

// (and b points to the first byte of the memory pool)

release(mem);

// Expect b->size to be 100, b->is_free to be 1

void* ptr = allocate(64);

// allocate can reuse the existing block!

// Expect b->size to be 100, b->is_free to be 0 and ptr == mem

}