All CS 3x projects are STRICTLY solo. You may not collaborate with other students.

Setup

You MUST work solo on this project! You may not collaborate at all with anyone else! Please use the SSH link found at the picture after clicking the link in the registration email:

Introduction

We’ve seen the reason why we would want to encode more information in a char **, using our strarray_t. But is this implementation inefficient?

It’s been introduced in lecture that pointers can reference information that exists on the heap. While you don’t know the exact reasoning for it (take CS24 :D), iterating over pointers with addresses that are not contiguous in memory is quite expensive in terms of runtime upon dereference. To get around this, we will create a new struct which stores strings contiguously in memory and later use this in our webserver.

Arrays of Strings: A Reimplementation

Task 0. Your first task is to implement all functions in library/packed_strarray.c subject to the documentation in include/packed_strarray.h.

COMMENTS ADDED FOR MORE GUIDANCE/CLARITY Your packed_strarray’s len field is the number of elements rather than the length of the concatenation of the strings. Your packed_strarray_get should raise an assert if idx is not a valid index into the array.

Note that to count as correct, your code must run with no output from address sanitizer, leak sanitizer, or undefined behavior sanitizer. Additionally, the strings must be stored consecutively in memory without any padding/garbage bytes between each string.

You can then run make task0 to make sure you’re done.

Arrays of … who knows?: A Generalization

Our data structures so far have only supported strings. If we wanted to make an array of any other type, we’d need to copy paste our code and be very careful about updating all the types! We’d like to avoid doing this and only write code once, that can then be used for multiple types. In Java, we saw this in action with ArrayList<T>… but C doesn’t have generics or a “universal type” like Object. Instead, we have the void * type, which acts as a “pointer to an unknown type”, and can be cast to a pointer to any type.

But not all types are equivalent. For example, if we have an int * versus a strarray_t *, their freeing requirements are very different. Additionally, if we wanted to store the data contiguously (like in packed_strarray_t), these types are of different size, but the rest of the implementation would be the same.

Now we can generalize on both of these constraints! We will save the free generalization until later in the course, but for now, we can store our data size on initialization for use when “get”-ing, allowing us to make use of void * store our generic data! The free problem and what type data is being stored are left to the caller (the test cases).

Task 1. Implement all functions in library/packed_generic_array.c subject to the documentation in include/packed_generic_array.h.

COMMENTS ADDED RECENTLY FOR MORE GUIDANCE Your packed_generic_array_get should raise an assert if idx is not a valid index into the array.

Note that to count as correct, your code must run with no output from address sanitizer, leak sanitizer, or undefined behavior sanitizer. Additionally, data must be stored consecutively in memory without any padding/garbage bytes between each piece of data.

You can then run make task1 to make sure you’re done.

Make sure to push to gitlab.