Submit a single file UserID.assignment4.tar to cuLearn with all the files specified below.
Your grade for this assignment will be based on correctness and style.
Create text a file with the name "myemail" that has a single line in it, consisting of your email address. Something like "firstname_lastname@carleton.ca" (or your hotmail or gmail or hellokittymail or ...). Do not include the quotes in the name of the file or in your email address. This must be a plain text file (with no extension).
The results of the correctness tests will be emailed to the email address that you put in this file.
Basic Heap: Each memory location in our model of the RAM will be an instance of type Memory:
typedef union Memory_u Memory;
union Memory_u{
char character;
unsigned int size;
unsigned long address;
};
In each memory location of our simulated heap,
which we'll call a memory cell,
we can either store actual data (the character field)
or other information that is needed for
the dynamic memory management.
Each time we allocate some memory on our simulated heap, we need to use at least four (4) consecutive memory cells:
Our simulated heap will simply be an array of Memory in the actual heap. Array index zero (0) will correspond to memory address zero in our simulated heap and is off limits (to read or write) just as memory location zero (NULL) is off limits in your normal programs.
You will implement all of the functions found in
nonstdlib.h
(found here)
that are not already
defined in nonstdlib.c
(found here).
These functions include
Memory* initializeHeap(unsigned long size); // Purpose: allocate memory on the actual heap for our // simulated heap. Returns a pointer to the first // memory location that we have reserved for our // simulated heap // (This function is partially defined for you ) // (you can add code to it, but do not change ) // (the last line of it in the .c file ) void dumpHeap(Memory* heap, int size); // Purpose: display the contents of the simulated heap // to stderr. // The size input parameter (which must be a multiple // of four) defines how many Memory cells we display // on a given row of output. // (A more precise description of the output // is given here.) typedef unsigned long charPointer; charPointer charMalloc(Memory* heap, unsigned int size); // Purpose: allocates memory in the heap for size // chars. // Returns the memory location in the simulated heap // where the head memory cell for the allocated // block of memory is. (memory location is heap array index) // Returns 0 if allocation failed because there was // no place in the heap for this requested block of memory bool charFree(Memory* heap, charPointer address); // Purpose: frees the memory allocated in the heap // for the block at location address // (memory locations in the simulated heap // correspond to array indices in the heap) // Function does nothing if this memory location // has already been freed (and not allocated again) // Returns false if the memory address has not been // the return value of a call to charMalloc(). // Returns true otherwise.
In order to implement these functions, you will need to maintain a table of some sort. This table will need to keep track of which memory locations in the simulated heap are currently allocated and which have ever been allocated. You should use a global data structure in nonstdlib.c for this (so that all your functions can always access and modify this table).
When allocating memory, we will use a simple technique of simply allocating memory in the next available space in the heap after the most recent allocation. (This will be elaborated on in Thursday's lecture; information will be added here after the lecture for those that miss the class.)
Add the files nonstdlib.h and nonstdlib.c
to your tar file. Make sure you add an appropriate header guard
to the .h file. Your nonstdlib.c file should not have a main()
function in it.
Arrays: In array.h
(found here) there are
two function prototypes for reading and writing elements
in an array of chars (a charPointer instance). These
array functions perform bounds checking on the index
values supplied. You will implement these functions
in array.c.
Be sure that you are accessing the correct memory cells where the characters are located.
For example, code using an array might look like
Memory* heap = initializaHeap(100000);
charPointer array = charMalloc(heap, 10);
setChar(heap, array, 2, 'q');
char c;
if( getChar(heap, array, 2, &c) )
printf("character=%c\n", c);
charFree(heap, array);
which creates the heap, allocates an array of 10 chars,
sets array[2] = 'q', puts array[2] into c, prints c, and then
frees the memory allocated for array.
Add the files array.h and array.c
to your tar file. Make sure you add an appropriate header guard
to the .h file. Your array.c file should not have a main()
function in it.
Main: Write a main.c file that
have a main function to demonstrate your dynamic memory
and array usage. Your program should accept two
command line arguments: the first will determine the
size of your heap (number of Memory cells) and the
second will determine the number of columns of
memory cells when using the dumpHeap() function.
Your code should call dumpHeap().
For example, if main is the executable of your program then you would run your program from the shell as
./main 10000 8to generate a heap with 10000 memory cells, and when printing the heap to stderr, it is displayed with 8 memory cells on each row.
Add the file main.c
to your tar file.
Be sure to include a Makefile which creates the executable
main by linking the object code for main,
nonstdlib and array.
Last modified : March 11, 2013