Assn 3: Mega array

Due: 5:00pm, Tuesday, September 16. Value: 35 pts.

In this assignment, you'll implement a data structure that we'll call a mega-array.

Data structure

Both Python and Java has the notion of an “expanding list,” called simply a list in Python and an ArrayList in Java. In both languages, this is done using what in C would be a struct holding the number of elements and a pointer to a generously sized array. Once enough elements have been added to fill the array, an even more generously sized array is created, all the values are copied into this new array, and the struct pointer is redirected to point to this new array. A shortcoming of this is that it depends on creating an enormous array, and there can be quite a bit of copying as the array grows.

In this assignment, we'll implement an alternative technique to deal with such an “expanding list” that we'll call a mega-array. A mega-array is an array of 1,024 pointers to “pages,” each page holding up to 1,024 different values. Once one page becomes full, we'll create a new, empty page and add a pointer to it into the mega-array's page array.

In C, the mega-array is defined using two different struct definitions.

struct mega_page {

    int data[1024];

};



struct mega_array {

    int size;

    struct mega_page *page[1024];

};

Below is an example diagram of a mega-array after the first 1,025 primes have been added into it.

In adding the first value (2), the first mega_page was created, and the 2 was added into it. Each subsequent prime through the 1,024th were also added into that page, filling it up. But upon adding the 1,025th prime, a new page had to be created, and a pointer to it was added into the second slot of the mega_array's page array.

Setting up the assignment

This assignment has three files that you should download into your project.

mega.c: Defines the struct mega_array as well as a library of functions for manipulating it. This is the only file you will modify for this assignment.
mega.h: Contains prototypes for the functions found in mega.c.
mega_test.c: Contains a main function that runs through a battery of tests. If your program passes all the tests with no memory problems or leaks reported by valgrind, there is a good chance that your solution is correct. That is not a guarantee, though.

If you are using the command line to compile your solution, you will want to compile both C files together using “ gcc mega_test.c mega.c ”.

Your job

The distributed mega.c file defines struct mega_array as outlined above and contains definitions for six functions for manipulating a mega-array. Three of these are already defined, and you should not modify them at all. Your job is to complete the remaining three.

struct mega_array* mega_new(): (Already defined) Allocates and returns a new, blank mega-array.
int mega_size(struct mega_array *m): (Already defined) Returns how many elements are currently in the mega-array.
int mega_get(struct mega_array *m, int index): (Already defined) Returns the element at slot index of the mega-array, or INT_MIN if index is invalid.
int mega_add(struct mega_array *m, int value): (For you to complete) Grows the mega-array by one slot and places value into that slot, returning 1 upon success. It returns 0 upon failure, which only happens when the array has already completely full — that is, it already has 1024 full pages. In this case, nothing should be changed in the array.
int mega_pop(struct mega_array *m): (For you to complete) Shrinks the mega-array by one slot, returning the value that was in that slot; or, if the mega-array was already empty, it returns INT_MIN.
void mega_free(struct mega_array *m): (For you to complete) Deallocates the struct mega_array as well as all the pages within it. Please note that you will not be able to verify that this works without using valgrind (or a similar tool). [How to use valgrind]

What to submit

Make sure you use a memory-profiling tool such as valgrind. [How to use] It will pick up on any memory leaks or other memory errors that may still exist in your program despite the appearance of working.

In submitting your solution, you should include only the mega.c file, including the provided code.