Dynamic Memory Management (Free Store)

Exercise material for using the free store in the C programming language. Fork, clone or download this repository to use the automated tests for solving free store exercise sheet.

Before creating a build to run the tests, it is important that all of the required files (create_arrays.{c,h}, int_array.{c,h}, main.c) are created alongside the *_test.c files. Until all required functions are declared in the header files, compilation will fail. Until all required functions are defined (an empty function body or returning a dummy value is sufficient), the linker won't be able to succeed. In main.c, at least a dummy main(.) function is required for compilation. Do not add a main(.) function to your create_arrays.c or int_array.c files. With all this in place, compile and run the tests as described below. Implement main(.) in a separate module called main.c. Include all header files of this exercise and use all of the implemented functions. Have main(.) print the data and never forget to use free(.). Explain in a comment, why free(.) has to be used.

First, make sure that Criterion is installed on your computer. On Debian-based systems, run

sudo apt install libcriterion-dev

For other systems, the installation from source code is described in the project's documentation.

Create the source and header files as required by the description of the exercise below. Then compile your solution:

mkdir -p build && cd build
cmake ..
make -j4

The test runners provide an excellent interface available with the -h flag. For running some or all of the tests for the task Create arrays on the free store, execute

./create_arrays_test

For running some or all of the tests for the task Create your own int array data type, execute

./int_array_test

If you want to run all of the tests for all tasks at the same time with a high level summary, use the ctest command.

Create Arrays on the Free Store

Implement the following functions:

int* zeros(int count);
int* ones(int count);
int* range(int count);

zeros(.) gets the number of desired elements. It must allocate the memory for an array of the given number of elements and initialize each element to zero. Use calloc(.) to complete this task. Ensure that the call to calloc(.) succeeds and terminate your program accordingly if it fails. ones(.) does the same as zeros, but sets each value to one. Use malloc(.) in this case. Explain in a documentation comment, why malloc(.) is better in this case. Ensure that the call to malloc(.) succeeds and terminate your program accordingly if it fails. range(.) sets the array to 0, 1, 2, 3, ..., count-1 Ensure that the calls to malloc(.) succeeds and terminate your program accordingly if it fails.

Name the source file: create_arrays.c and the corresponding header file create_arrays.h.

Create Your Own int Array Data Type

Implement a data structure IntArray that helps you to work with arrays of dynamic size. The core of the data type should be a struct storing a pointer to an array on the free store and the required metadata.

typedef struct intarray IntArray;
struct intarray {
  size_t reserved;  // available storage
  size_t elements;  // current number of elements
  int* array;
};

Implement the following API to create and work with IntArray:

// create new empty IntArray for 100 elements
IntArray* ia_create();
// create new array with `count` zeros
IntArray* ia_zeros(size_t count);
// create new array with `count` ones
IntArray* ia_ones(size_t count);
// create new array with stop-start elements: start ... stop-1
IntArray* ia_range(int start, int stop);
// free the array and the intarray struct; return NULL
IntArray* ia_free(IntArray* ia);

// remove and return last element of `ia`
int ia_pop_back(IntArray* ia);
/*
 * add `elem` to `ia`
 * if that would exceed the available reserved memory, double the size of
 * the array using `reallocarray`
 */
void ia_push_back(IntArray* ia, int elem);

// return the number of occurrences of `elem` in `ia`
size_t ia_count(IntArray* ia, int elem);
/*
 * Return element at index.
 * If the index is out of bounds, write "IndexError" and some useful context
 * to stderr and terminate the execution of the program.
 */
int ia_index(IntArray* ia, size_t index);
// print a representation of the array to stdout
void ia_print(IntArray* ia);
// return the current number of elements
size_t ia_size(IntArray* ia);
// return the sum of all elements
long int ia_sum(IntArray* ia);

/*
 * Return new `IntArray*` where all elements are the pairwise sum of the
 * elements of the given two arrays. If one array is shorter,
 * solely use the elements of the longer array for the higher indices.
 */
IntArray* ia_add(IntArray* first, IntArray* second);
/*
 * Return new `IntArray*` where all elements are the pairwise product of the
 * elements of the given two arrays. If one array is shorter,
 * solely use the elements of the longer array for the higher indices.
 */
IntArray* ia_mul(IntArray* first, IntArray* second);

All of the above functions must ensure that the data stored in the struct is consistent at all times. For example, adding an element must also increase the value of elements and, if needed, the value of reserved. Use and thoroughly test your implementation in a designated main(.) function in main.c.

Name the source file: int_array.c and the corresponding header file int_array.h.