Part 1: Memory Allocation
The goal of this part of the assignment is to write your own memory allocator,
using the free list algorithm. We will start with two warm-up problems to get you
used to working with memory at a low level. Then you will write a memory
allocator that only allocates fixed-size blocks. Finally, you will write a full-fledged
memory allocator that handles variable-size blocks.
Problem 1 — 15 marks of 100, 9 secret marks (filename: wrapper-p1.cc)
We have provided a header a10p1.h and an object file a10p1.o that provide a
int64_t *arena() // Note: we are using int64_t instead of int on this
// so that our numeric values are the same width as our
pointers (i.e., 64 bits)
The arena function returns the address of the beginning of a block of RAM that
may be used for dynamic memory allocation. Initially, the size of the arena (in
bytes) is stored in the first word. That is, the expression *arena() returns the size
of the arena, which will not be less than 223 or greater than 231. You may also
assume it is a multiple of 8.
Aside from the first word, which contains the size of the arena in bytes, you can
assume that every word in the arena is initialized to 0.
In C++, using the provided p1starter.cc as a starter, write a
function wain(a,n) where a is the address of the first of n 64-bit words of RAM.
Each word will contain a number between 1 and 1,000,000. Your wain function
should return the number of times that the most frequent element occurs.
You must solve this problem in linear time (i.e., O(n) where n is the size of the
input array). Otherwise, you will likely fail some of the TestingSystem tests.
Apart from the stack space occupied by ordinary program variables, and the heap
space occupied by user input, all of the memory your program uses (i.e., for arrays,
etc.) must come from the memory returned by arena.
More specifically, the code you write is not permitted to
use new, delete, malloc, calloc, realloc, free, or any STL containers, or any other
function that accomplishes a similar purpose to these.
You are allowed to use a few integer, pointer and char variables for things like
important values or addresses, loop counters, etc. but you should not store large
amounts of data using these variables. In particular, do not create any array
variables (e.g. int64_t array;).
You are not allowed to #include anything other than the headers already included
by the starter code p1wrapper.cc, and the header <cstdio> (C style input/output).
You do not need <cstdio> at all for this problem, but TestingSystem accepts it,
mostly for consistency with Problem 2 (where you are allowed to use it for I/O if
you prefer it to C++ streams). Perhaps you can use it for debugging if you are a fan