This project is STRICTLY solo. You may not collaborate with other students at all.

Setup

Register for the project using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions. You MUST work solo on this project! You may not collaborate at all with anyone else! Please use the SSH link found on the registration page and in the email sent to you, it should look something like this git@gitlab.caltech.edu:cs3-24sp/solo01-blank.git.

Introduction

You open your web browser (obviously Chrome, because Google took over the world). You type in “https://sof.tware.design/projects/solo/01”. Somehow, magically stuff appears in your browser window. It’s text, and links, and pictures, and OMG…how does that even work? Over the weeks of this course, you will figure out how the HTTP protocol works, and, along the way, send your own content to your own browser. Wow!

Unfortunately, as this is an extremely complicated process, we have to start simple. In fact, this week’s solo project won’t even look like it’s related to a web server, but we promise it will be relevant (even, useful!) to next week’s solo project.

In this project, you’ll implement the following two libraries:

a string utility for splitting strings
a dictionary with string keys and values

An Extended String Library

Before continuing to the next section, you’ll need to understand the concepts of “encapsulation” and “modules”

Please read our reading on modules, and ask any questions you need to before continuing.

Arrays of Strings

Recall that you used a struct type named strarray_t in project00 which had a data field and a length field. Hopefully you recall that to initialize a strarray_t, you had to:

allocate memory for the whole struct
initialize the length field
allocate memory for the data field

This pattern shows up a lot in code (see the modules reading above), and it should not be repeatedly written throughout your code. To fix this, your first task will be to write a strarray_t module to avoid duplication of this code in practice.

Task 0a. Your first task is to implement the strarray_init and strarray_free functions in library/strarray.c subject to the documentation in include/strarray.h.

Once you are done, run make task0a to check your code.

Note that to count as correct, your code must run with no output from address sanitizer, leak sanitizer, or undefined behavior sanitizer.

A More Useful `strsplit`

Last time, you also wrote a strsplit function which split a string on spaces. Hopefully, you felt like you were writing it in a clunky way, because…

the allocations were randomly spread throughout the code and possibly repeated (makes it harder to see the “big picture” of the code)
you used no helper functions (unable to reused code)
there’s no particular reason to only split on spaces (lack of abstraction/generalization)

Good news! You now have a chance (ahem a requirement) to fix these issues. There should be a substantive difference in code quality between your project00 code and your solo01 code.

Task 0b. Implement the mystr_indexof function in library/mystr.c subject to the documentation in include/mystr.h.

Once you are done, run make task0b to check your code.

Task 0c. Implement the mystr_split function in library/mystr.c subject to the documentation in include/mystr.h.

Once you are done, run make task0c.

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

CS 2, Redux: A Dictionary Library

In CS 2, we re-wrote the java.util package to understand how it was built. In C, we have to do this, because… there’s no good standard library. (whoo….)

As you hopefully remember from CS 2, “dictionaries” (that is key-value stores like HashMap or TreeMap, in Java) are extremely essential to doing anything useful.

While we could start by asking you to write another hash table, we’ll take mercy: you only have to write a linked list! In fact, it would be silly to write a complicated data structure at this point when you don’t even know exactly how it will be used.

We’ll start by working with keys and values that are both strictly of type char * (aka “C String”). Since it’s just a prototype, we really don’t care about efficiency; so, a linked list will suffice.

Task 1a. Implement the node_init and node_free functions in library/ll.c to define a singly-linked node for a linked list.

There are no tests for these functions since they’re not part of the external interface.

Before continuing to the next section, you’ll need to understand the concept of “memory ownership”.

Please read our reading on ownership, and ask any questions you need to before continuing.

Linked List

The remaining tasks should all implement pieces of a singly-linked list. Any attempt at using a different data structure (an array list, a tree, a hash table, etc.) will result in no credit, even if the gitlab tests pass.

Task 1b. Implement the ll_init, ll_free, ll_put, and ll_get functions.

Note that ll_put should be written to expect heap-allocated strings which will then be “owned” by the dictionary. ll_free should then free those strings.

ll_get should return pointers to the strings owned by the dictionary. The pointers returned by ll_get are correspondingly valid until the dictionary is freed or modified by ll_put.

Once you are done, run make task1b to test your code.

Finally, it’s useful to be able to access all the keys in a dictionary, like you would iterate a HashMap with .keySet() in Java.

Task 1c. Implement the ll_get_keys function.

Once you are done, run make task1c.

To double check everything, run make test. Once all tests pass, commit and push your code to GitLab.