As we increase the size of our programs, we run the risk of making our programs too complex to understand. Consider a program that is broken up into eight components. Imagine if there were no restrictions on how these components interacted. In the worst case, every component could interact with every other component.

Now, imagine that a bug is found in, say, component 5. Trying to uncover the cause of the bug may require investigating how this component interacts with other components in the system. In this maximally connected case, we have to see how component 5 interacts with the other seven components of the system. Clearly such a situation is not ideal, especially if there were additional components, say hundreds of them!

But this situation can become worse. Suppose the bug is particularly tricky, and we have to investigate not just how component 5 interacts with every other component, but also how every component interacts with each component that interacts with component 5. That is a bit of a mouthful, but what we mean is that maybe the interactions of any triple of components is the issue. In other words, we have to examine how:

Components 5, 1, and 2,
Components 5, 1, and 3,
Components 5, 1, and 4,
Components 5, 1, and 6,
Components 5, 1, and 7,
Components 5, 2, and 3, ...

... and so forth all interact to find the bug!

Maybe any combination of components that could interact together in the system can cause the bug. In the worst case, we would need to examine all of these combinations to unearth the problem, an exponential number of possibilities in all. Consequently, to build large software artifacts that we have some hope of reasoning about, we need to limit these interactions between components in our system to the bare essentials.

Abstract Data Types

One of the key tools in our arsenal to limit unnecessary interaction between software components is abstraction. By abstraction, we mean that we:

Expose the essential parts of a software component required to interact with others and
Hide all the inessential parts.

This approach to building software helps minimize the surface area of the component we're writing, minimizing the ways it can interact with other components, thus reducing the complexity of our programs!

When our software components are best realized as types in our programs, this abstraction takes the form of abstract data types (ADTs). We break up our component into two parts:

An public interface that defines the ways that our program can interact with this type, i.e., what functions are available to create, use, and delete values of this type.
A private implementation of the interface functions, hidden from the outside world.

A Simple Example: A Counter

Let's examine a simple abstract data type to see this concept in action. Consider a humble counter that keeps track of an ever-increasing value. First, what operations should our counter ADT expose to the outside world? Keeping in mind our mantra of "creation-use-deletion" for types, we need to consider exposing functions for each of these categories. To keep things simple, we'll assume that our counter is only stack-allocated, so we'll have no need to consider the "deletion" category yet.

"Using" a counter amounts to two behaviors: incrementing the counter and fetching its current value. Combining these two behaviors with the need to make a counter in the first place yields three function signatures:

// Creates a new counter, initially with value 0
counter make_counter(void);

// Increments counter c by 1
void increment(counter *c);

// Retrives the value of counter c
int get_value(counter *c);

These three functions form the interface to our counter ADT. Note that we have not defined what the counter type is or how these functions are implemented. The point of the ADT is to separate interface from implementation so that we can expose the former and hide the latter.

Nevertheless, we need to actually provide an implementation, so let's do so. Critically, our choice of what the counter type is will guide our implementation of the interface. The simplest counter is simply an int, so let's go with that and see how everything pans out:

typedef struct {
    int value;
} counter;

counter make_counter(void) {
    counter c;
    c.value = 0;
    return c;
}

void increment(counter *c) {
    // x->f is convenient syntax that means (*x).f
    c->value++;
}

int get_value(counter *c) {
    return c->value;
}

Great! We have provided an implementation of our counter ADT. Presumably, all of this code sits in a single file, so we really haven't "hidden" anything from everyone. Next, let's see how we can organize our C programs to effectively hide implementations and expose interfaces to other parts of our program.

Organizing C Programs Around ADTs

Some programming languages provide strong support for abstractions like ADTs, e.g., classes in object-oriented languages. C, as you are probably used to by now, does not provide such support. This is because such support usually comes at a cost of performance that is disagreeable in the low-level contexts that C is used. Instead, C programs are organized in a particular way to achieve this effect of hiding implementation and exposing interface through the compilation process. This organization is not enforced by C, per se; it is simply a convention that all C programmers follow!

We break up an ADT like our counter into two files:

A header file that contains information about the interface to this ADT.
An implementation file that contains an appropriate implementation of this interface.

Applying this design pattern to our counter example, we create two files:

counter.h is our header file:

// counter.h

#pragma once

// The counter type
typedef struct 
    int value;
} counter;

// Creates a new counter, initially with value 0
counter make_counter(void);

// Increments counter c by 1
void increment(counter *c);

// Retrives the value of counter c
int get_value(counter *c);

counter.c is our implementation file:

// counter.c
#include "counter.h"

counter make_counter(void) {
    counter c;
    c.value = 0;
    return c;
}

void increment(counter *c) {
    // x->f is convenient syntax that means (*x).f
    c->value++;
}

int get_value(counter *c) {
    return c->value;
}

Observe how we link the header and implementation files together. Recall that the #include pre-processor directive copies the contents of a file (more or less) verbatim into the #include's position in the file. Thus, counter.c stays consistent with counter.h by virtue of literal copying-pasting of the latter into the former during compilation!

Also observe the use of a new pre-processor directive, #pragma once, at the top of our header file. #pragma once ensures that only one copy of this file is included (via #include) in any compilation unit of our program. A compilation unit is a single .c file including the complete set of files it (transitively) includes via #include.

To see why multiple copies of our header might be included in a compilation unit, note that we #include our header file not just in our implementation but any file that will use the counter type. Because the header file contains types and function headers, it is precisely the information needed by the compiler to type-check any uses of a counter in our program! But what if a compilation unit includes (a) our counter header and (b) another header header that also #includes counter.h? We then arrive at the situation that #pragma once fixes—ensuring that only one copy of counter.h is included in the overall compilation unit!

To use our counter type, say for example, in our main program, we would have a separate file for main, call it main.c. We would then #include the header file in main. Then, any use of the counter type or its functions will type-check successfully:

// main.c

#include "counter.h"

int main(void) {
    counter c = make_counter();
    printf("Counter is initially %d\n", get_value(&c));
    increment(&c);
    increment(&c);
    increment(&c);
    printf("Counter is now %d\n", get_value(&c));
    return 0; 
}

Finally, when we go to compile our program, we need to include both compilation units in our clang invocation:

$> clang main.c counter.c -o prog
$> ./prog
Counter is initially 0
Counter is initially 3

Note that counter.h is "included" in the compilation by virtue of the #include directives found in main.c and counter.c!

Introduction to Sequences and Lists

Abstract data types can be used to capture many kinds of data. For example, the FILE* type exposed in stdio.h is an ADT over a stream of data that could be drawn from, e.g., a file on disk, the user's keyboard, or their screen. However, ADTs are commonly used to capture classes of data structures, data that is responsible for organizing and storing other data. There are four broad classes of such data structures, defined by the relationships they encode between the data they store:

Sequences capture sequential relationships between data.
Trees capture hierarchical relationships between data.
Maps capture function-like relationships between data.
Graphs capture arbitrary relationships between data.

The study of these structures is the primary topic for CSC 207. But of these, sequences are most common and prevalent in programming, so it is worth our time to explore them in detail now.

We've already seen an example of a particular kind of sequence in programming: the array. An array is a sequence that is:

Fixed-size and
Homogeneous, i.e., stores elements of same type.

We have run into the perils of the limitations of these fixed-size structures already. For example, if we use an array to store user input, how do we cope with the fact that the user enters more data than we have allotted space to the array?

A natural question, therefore, is what is a sequence that is instead a variable-size structure, one that can grow and shrink on demand? This leads us to the abstract data type that we will study for this next leg of the course, the list. We have already seen lists in Scheme/Racket, but we didn't think too hard about how they were implemented. Now that we are working in a systems context, this is a good time to go under the hood and explore the different ways lists can be implemented and the trade-offs between these approaches.

The List ADT

Before we dive into implementation, we must define the interface of this list abstract data type. What are the kinds of operations that we want to perform over some list type? And for simplicity's sake, let's say our list just holds int values. Again, let's appeal to the "creation-use-deletion" mantra for types:

We need functions to create and delete lists:

list* make_list(void);
void free_list(list* lst);

We need a function to add elements to a list, presumably at the end:
```
void list_add(list* lst, int val);
```
We need a function to retrieve elements from the list. Like arrays, lists are sequential in nature, so it is natural to want to retrieve their elements by index:
```
int list_get(list* lst, int index);
```
Since a list is variable-sized, it'll be useful to know the length of a list at any given point in time.
```
int list_length(list* lst);
```
At this point, it might be nice to delete elements (by index) from our list, too:
```
void list_remove(list* lst, int index);
```

With this interface defined, we can envision how operating over a list should work, even without knowing its implementation!

int main(void) {
    list *lst = make_list();
    printf("The size of the empty list is: %d\n", list_length(lst));      // 0
    lst_add(lst, 5);
    lst_add(lst, 9);
    lst_add(lst, 7);
    printf("The size of this list is now: %d\n", list_length(lst));       // 3
    printf("The element at index 1 is: %d\n", list_get(lst, 1));          // 9
    list_remove(lst, 1);
    printf("The element at index 1 now is: %d\n", list_get(lst, 1));      // 7
    printf("And the length of the list is now: %d\n", list_length(lst));  // 2
    free_list(lst);
    return 0;
}

In lab, we'll explore one of the two ways to implement this list ADT: arrays!

Lab Preparation: Reviewing Dynamic Memory Management

Before jumping into lab, we'll want to review the basics of dynamic memory management with malloc and free. To do this, review chapters 17.1–17.4 from King which covers dynamic allocation for both strings and arrays.

Exercise: Enhanced Interface

In our initial exploration of the list ADT, we scoped some basic functions that we might implement. However, there are many other functions to consider, some of which you may have seen in CSC 151! Take some time to brainstorm what other functions might be nice to perform over lists, write down their function signatures, and expand the example main function above with their use.

Homework 5: Wordle

Wordle is a indie word-guessed game-turned social phenomena. The game is quite simple:

Guess the WORDLE in six tries.

Each guess must be a valid five-letter word. Hit the enter button to submit.

After each guess, the color of the tiles will change to show how close your guess was to the word.

In this demonstration exercise, we will use our string/array/pointer manipulation skills to implement a command-line version of Wordle that is as faithful as possible to the original! Cloning an existing application is an excellent starting point for a project that can help you build up programming skills, learn about a new area of discipline, and serve as a basis for a larger endeavour that might appear in your eventual portfolio for job applications!

You should implement your clone of Wordle in a file called wordle.c and upload it to Gradescope when you are done.

The Basic Wordle Game

Many application have a simple core engine that is simple to describe and implement. However, what frequently makes the application interesting are the features built on top of this engine which add complexity and depth. Consequently, when we go to implement an application, it is useful to begin with the core engine and build outwards. Not only does this allow us to structure or architect our program in a natural fashion, it also is a strong confidence builder getting a minimum viable product up and running as quickly as possible.

The core of Wordle is a simple loop. Given a five-letter target word:

For each of the six turns of the game.
- The user guesses a word.
- The game checks to see if the guess matches the target word. If so, the user wins and the game is over.
- Otherwise the game gives a report of how close the guess was to the target word and the turn ends.

In this sense, Wordle is merely a simple guessing game. However, Wordle's reports at the end of each turn are what make it unique. For each character in the guess, Wordle will:

Highlight the character green if the character matches the corresponding character in the target word.
Highlight the character yellow if the character does not match but the character appears somewhere in the target word.

Otherwise, the character is not in the target word, so Wordle displays the character without any additional highlighting.

For example, suppose that the target word is trove and the user guesses the word tread, then the game would:

Highlight t green because it is in the correct position.
Highlight r green because it is in the correct position.
Highlight e yellow because it is in the wrong position but in the target word.

And it would not highlight a and d because they are not in the target word.

Part 1: Getting input from the user

From the game description above, we can see there are three key operations that we must implement to complete the Wordle core engine:

Getting a five-letter word from the user.
Computing a report comparing the user's guess against the target word.
Displaying the report using colors.

Let's start with getting input from the user. Write a function called void get_guess(const int turn, char *guess) that prompts the user for a guess and populates the char buffer pointed to by guess with that guess. The function prompts the user by displaying the text Guess <turn>: where turn is the turn number the game is currently on. A pre-condition of the function is that the character buffer pointed to by guess is at least six characters. For example, if we call get_guess(2, guess), then with the following interaction:

Guess 2: slate

Where the system prints "Guess 2: " and the user responds with slate, then the characters s, l, a, t, e, and the null terminator \0 are all stored in guess.

For now, we will assume the user enters in an appropriate five-letter word and not worry about any kind of error handling and re-prompting that might be required. This means that we can use the stdio.h function char getchar(void) which fetches a single character from the user to build up their guess one character at a time. Make sure to account for the fact that the user will need to enter a newline to send their text to stdin!

Part 2: Computing the report

Assuming we have received the guess from the user, now let's compute the report of how close their guess is to the actual word. While we can combine the computation of the report with the actual reporting, it is beneficial to break up the two steps into separate functions. That way, we can test and debug them independently.

Write a function int check_guess(const char *guess, const char *target, char result []) that takes two strings, the guess and the target, compares them according to the rules of Wordle, and then returns the number of characters that matched exactly. If check_guess returns 5, that means that the guess is equal to the target. As a precondition of the function, guess and target must both be strings of length 5.

result is assumed to be a char array of size five that check_guess populates with the per-character results of the check.

If the ith character of guess matches target exactly, then the ith character of result will be g (for "green").
If the ith character of guess does not match target but the ith character appears somewhere inside of target, then the ith character of result will be y (for "yellow");
Otherwise, the ith character of guess is x (for "no match").

For example, if we call check_guess("tread", "trove", result) then the function returns 2 since t and t matches and result will contain the characters c, c, y, x, and x in sequence.

Part 3: Printing the report

After computing the report and generating the result string, we now need to echo back the guess with appropriate highlighting as described by the report string. Write a function void print_report(const char *guess, const char result []) which prints guess followed by a newline. However, for each character c of guess:

If the corresponding character of result is g, c should be printed with a green background.
If the corresponding character of result is y, c should be printed with a yellow background.
Otherwise, c is printed normally.

To print individual characters, you can use the %c format specifier, taking care to ensure that what you pass to printf has type char rather than char*. To print with colored backgrounds, you will need to take advantage of special ANSI color escape sequences which causes the terminal to print colored text. These character sequences have the form \033[...m where the ... are a series of semicolon separated parameters. The effect of "printing" one of these sequences is to cause the terminal to print subsequent characters with the specified color.

In particular:

\033[1;37;42m renders subsequent text with a green background.
\033[1;37;43m renders subsequent text with a yellow background.
\033[0m resets the colors back to the default.

For example, the following calls to printf:

printf("\033[1;37;42mgreen\033[0m\n");
printf("\033[1;37;43myellow\033[0m\n");

Print green and yellow to the console with green and yellow backgrounds, respectively.

Part 4: Putting it all together

With your three functions in-hand, write a function called void play_game(const char *target) that targets a five-letter target word as input and plays a complete game of Wordle on the command-line.

Part 5: Choosing random words from a dictionary

Finally, we can write a main function that calls play_game to play a Wordle game. The only catch is that we need a dictionary of words to draw from. Let's solve the problem of loading a dictionary from a file in a second step. For now, let's hard code a dictionary in main, an array of test words, randomly choose one of those words, and then pass that word to play_game.

As far as your hard-coded dictionary goes, you should create a small dictionary of strings, e.g.,

char *dictionary [] = { "hello", "slate", ... }

Include a number of five-letter strings so you can adequately test the program before you try to load words from a larger data source.

To randomly choose a word from this array, you will need to use the rand() function from stdlib.h. int rand(void) generates a random number from in the range 0 to RAND_MAX which is usually the largest value that int can take on. This is likely much larger than the length of the array, but since you know the length of the array, you can use the modulus (%) operator to "squish" the random number into a range appropriate for indexing into the array.

rand() is an example of a pseudo-random number generator. It is a deterministic algorithm for generating seemingly (but not actually) random numbers. Pseudo-random number generators need a seed value which determines the start of the "random" sequence they will generate. If you start two generators utilizing the same algorithm with the same seed value, they should produce the same sequence of int values.

The function void srand(int seed) sets the seed for rand. To produce a truly random result, the seed ought to be draw from some "truly random" source of data. Frequently, the current time since 1 January 1970, i.e., the Unix Epoch, is used for this purpose. The time(time_t *result) function from the time.h header returns this value. The argument passed to time is a redundant result pointer that will be loaded with the result of the call to time. Since it is unnecessary, we can pass NULL, the pointer to nothing, to the function.

All that being said, to generate random numbers in our C program, include the following setup in your code:

#include <stdlib.h>
#include <time.h>

int main(int argv, char* argv []) {
    srand(time(NULL));  // set rand's seed to be the current time
    // go on to use rand() to generate random numbers...
}

Part 6: Read in a Complete Dictionary of Words

Finally, instead of a hard-coded dictionary, read the set of possible words from the following file:

words5.txt

This file contains five-letter words extracted from Collins Scrabble Words dictionary. Your program can assume that words5.txt exists in the same directory as the program. However, your program should report a sensible error and exit gracefully if words5.txt does not exist.

Currently, your dictionary is hard-coded to a finite set of words using an array literal. Now, you will need to create a list of strings of the appropriate size to hold all the words found in words5.txt. To do this, you can adapt the array-based list code from a previous lab to store these strings.

With this in mind, you can use fopen and fclose from stdio.h to open the file and then use fgetc to read individual characters of the file. You may assume for the purposes of this that each entry in the file is of the form of five characters and then a newline (\n) character. Note that you will need to also dynamically allocate memory for each string so that your dictionary is a list of pointers to heap-allocated strings that it owns after the dictionary has been loaded!

Extra Bits

At this point, the core of your Wordle game is roughly complete! However, there are many more things that you can add to it. While not required, here are some additions to your Wordle program for both functionality and fun that you can consider. If you include any of these features or others, please make sure to include a comment at the top of the file indicating what you have done.

Feature 1: forgiving prompt

Right now get_guess assumes that the user does "the right thing" and enters exactly five characters and a newline character for their guess. Relax this restriction so that the program re-prompts the user for a five-letter word if they enter in a word that is not exactly five characters long. To do this, you will need to correctly instrument get_guess with appropriate error checking, detecting the situations in which the user has not entered a valid input. You should then re-prompt the user, giving them an optional error message

While seemingly simple, this is fairly tricky functionality to get 100% right. Keep in mind that when entering input, the user will fill the console pipe with a number of characters ending in a newline character. You need to make sure to cover all the cases where execution exhausts part or all of this input, ensuring that subsequent prompts work as expected.

Feature 2: summary report

A memorable feature of Wordle is the summary of the game that the player can share with their friends. The summary consists of a number of rows, one for each guess the player made. Each row is simply the results of print_report for that guess, i.e., the guess information for each character---correct g, out of position y, or not in the target word x. Each character of this row should be colored as with print_report although if you went to copy-and-paste this text to share with a friend only the rows of gs, ys, and xs would remain.

Array-based Lists

Today we introduced the notion of an abstract data type, a type that exposes a set of operations on its values, its interface, but does not expose how it is implemented. Abstract data types are a foundational concept in computer science. They allow us to build interchangable software components that we can develop independently, a requirement for architecting large software systems.

In this lab, we'll build a complete C project that contains:

The definition of a charlist abstract data type that represents a list of char values.
An implementation of the charlist abstract data type using arrays, an array list implementation.
A main function that demonstrates usage of a charlist to implement a function getline that retrieves a complete line of input from the user.

Part 1: Motivation

Consider the following implementation of a function that attempts to get a line of input from the user:

#include <stdio.h>

void fixed_getline(char *buf, FILE *in) {
    char ch = fgetc(in);
    while (ch != '\n') {
        *buf = ch;
        buf++;
        ch = fgetc(in);
    }
    *buf = '\0';
}

Now consider the following main function that invokes fixed_getline to get a line of input from the user:

int main(void) {
    printf("What is your name? ");
    char name [10];
    fixed_getline(name);
    printf("Hello %s!", name);
    // Point A
}

With your partner, discuss a scenario where the user's input causes a memory error in the program. In a sentence or two, classify this error and why it arises in the code.

Part 2: Setting Up the Project

Next, we will set up our project as a multifile C program. Create a new folder and add the following files to it:

charlist.h: a C header file defining the charlist interface.
charlist.c: an implementation of the charlist interface using arrays.
main.c: the entry point of the program which will demonstrate usage of charlist.

In addition to these files, we will also add a Makefile to the folder so that we can build the program in a single short command, make, rather than typing out the clang invocation directly. Add a file called Makefile to this folder with the following contents:

main : charlist.c main.c
	clang -Wall -Werror -g $^ -o $@

.PHONY : clean
clean:
	rm -rf main

Note that the indentation in this file are genuine tab characters and not spaces. With this Makefile, you should be able to issue the command make in the folder to build the program main.

Part 3: Array-based Lists

Before we dive into the code, let's first understand how to implement lists using arrays. Recall from the reading that an array is a fixed-sized, homogeneous, sequential structure. Notably, a list is like an array but it can grow at runtime! Thus, our choice of backing datatype for our charlist will be an array with some extra data needed to facilitate dynamic grow.

As a starting point, let's imagine the following scenario for our charlist:

['a']['b']['c'][   ][   ]

Here, our charlist contains three elements, 'a', 'b' and 'c' whereas the backing array has five slots in total. Thus, in our charlist, we must track two values:

The number of elements of contained by the charlist, its size.
The overall size of the backing array, its capacity.

Throughout the lifetime of a charlist, we'll maintain the invariant that a charlist's size never exceeds its capacity.

With this basic representation in mind, briefly discuss the following questions with your partner. Ask a member of the course staff if you are unsure about any of them!

Why must our charlist maintain this "size ≤ capacity" invariant?
How would we add a new character, say 'd' to our charlist? Where would 'd' go and how would we update our size and capacity accordingly?
Given that the elements of the list are stored in an array, how can we retrieve, say the element 'b' from the list?

Part 4: The `charlist` Interface and Array-based Lists

Next, we'll define the charlist interface in charlist.h interface. Recall from the reading that an ADTs interface defines (a) the datatypes and (b) functions exposed by the ADT. Implementation of these functions will eventually be found in charlist.c.

To complete the charlist interface, add the following to charlist.h.

A #pragma once directive at the top of the file. Agree with your partner on what this directive does and ask a member of the course staff if you are still unsure!
Add a definition for a typedefed struct called charlist. charlist should contain three fields corresponding to data identified in part 3.
Signatures for the following functions over charlists that we will implement:
- make_charlist takes no arguments and returns a pointer to a newly allocated charlist on the heap.
- charlist_size takes a pointer to a charlist as input and returns the size of the charlist as output.
- charlist_get takes a pointer to a charlist and index as input and returns the element at that index as output.
- free_charlist takes a pointer to a charlist and deallocates it.
- charlist_add takes a pointer to a charlist and a char as input and adds that char to the end of the charlist. The function does not return anything as output.

Part 5: The `charlist` Implementation

Now, let's implement the first four charlist functions in charlist.c. In charlist.c you should first include a #include "charlist.h" directive so that our implementations are consistent with the signatures defined in our interface. From there, implement:

make_charlist. You will find that you will need to pick an initial size for your charlist's backing array. For now, you can initialize the charlist's array to be an array of size 10.
charlist_size. If your charlist struct is set up correctly, this function should be a one-liner!
charlist_get. Like charlist_size, this function should also be a one-liner. For now, you do not need to worry about the case where the index is not valid for the charlist.
free_charlist. In this function make sure you deallocate not only the memory for the charlist struct but also its backing array!

Part 6: `charlist` Add

As you saw in part 3, when there is still room in the charlist's backing array, adding an element onto the end of charlist is straightforward. However, what happens when the charlist's backing array is full?

['a']['b']['c']['d']['e']

Suppose we wanted to add 'f' to this list. How can we do it when the backing array is full?

Our strategy is to:

Allocate a new backing array with more space. To avoid having to constantly reallocate memory, let's allocate a new backing array that is twice the size of the original.
Copy the element from the old backing array to the new backing array.
Update our charlist to point to this new backing array, updating the auxiliary fields as needed. Additionally, we should also free the old backing array since it is no longer needed.

In our example, we would allocate a new array of size 10 since the backing array has size 5 and copy the elements over. We can then add 'f' to the end of the new array!

['a']['b']['c']['d']['e']
  |    |    |    |    |
  ∨    ∨    ∨    ∨    ∨
['a']['b']['c']['d']['e']['f'][   ][   ][   ][   ]

Implement this functionality in charlist_add.

(Hint: critically, charlist_add should do two different depending on whether the backing array is full. How can we test whether the backing array is full with the fields in the charlist struct?)

Part 7: Trying Out `charlist`

At this point, we have a complete charlist implementation. But we should make sure everything is in working order. Copy the following skeleton into your main.c file, filling in the middle portion with appropriate code that exercises your implementation.

#include <stdio.h>

// This directive is necessary for main.c to reference our charlist functions!
#include "charlist.h"

int main(void) {
    charlist *lst = make_charlist();

    // TODO: perform operations on lst and check that they work correctly!

    free_charlist(lst);
    return 0;
}

Part 8: Line-by-line Input

Now that our charlist implementation is complete, we can now use it for a pragmatic task: implementing getline in a memory fashion. Add an implementation of void my_getline(charlist *buf, FILE *in) to main.c. You can base your implementation on fixed_getline found in part 1, replacing the explicit array manipulation with calls to charlist functions.

Once you are done, try out my_getline in main.c on a fresh charlist, ensuring that you appropriately store the line of input entered by the user into the input charlist buffer.

(Hint 1: when calling my_getline, you can pass stdin for the in parameter to read from the user's keyboard, i.e., standard input. Note that this parameterization means that we can read lines from any stream, including files via fopen!)

(Hint 2: provided that you add a '\0' null-terminator to the end of the buffer, you can simply pass the backing buffer to a printf call to check your work because it ought to have type char*!)

So far, we have used arrays to hold collections of data. However, arrays suffer from a terrible restriction: once declared, an array's size is fixed. In general, we need data structures that can hold a variable amount of data because we don't know how much data we will receive in advance. The canonical example of this situation is receiving data from the user in the form of console input or files.

In our discussion of abstract data types, we learned about the list ADT, an interface for a variable-sized, homogenous, sequential structure. Our growable buffer/arraylist is one canonical implementation of this interface but suffers from notable limitations. In particular, whenever we "outgrow" the underlying buffer, we have to copy all the elements of the original buffer to the new one. In some circumstances, this leads to undesirable performance!

The linked list is the other primary implementation of the list ADT. Rather than an array, a linked list utilizes a collection of nodes sequentially linked via pointers. It ties together all of the advanced systems programming concepts that we have discussed in the course so far: structs, pointers, and manual memory management. Furthermore, many structures can be thought of as a collection of linked structures, so the design patterns we learn here apply to many other situations we find ourselves in C. Thus, it is a fitting "right of passage" as we end the course---mastery of linked lists is a sign that we have mastered the fundamentals of C and systems programming!

Representation

Recall that in Scheme, we represent lists of data using box-and-pointer diagrams, e.g.,

[0][o]-->[1][o]-->[2][o]-->[3][o]-->[/]

This diagram represents the list [0, 1, 2, 3]. It is built with the expression:

(cons 0 (cons 1 (cons 2 (cons 3 null))))

The cons function produces one of these boxes. Such a box consists of:

A value and
A reference to the next box in the list.

We signify the end of the list using the value, null, written [/] in the diagram above.

In C, we mirror this structure with a struct we will call a node:

struct node {
    int value;
    struct node *next;
};

typedef struct node node;

A node possesses two fields corresponding to the value and the next node in the list. Recall that we can combine the struct and typedef declarations into a single declaration as follows:

typedef struct node {
    int value;
    struct node *next;
} node;

Because pointers are explicit in C, we can designate the NULL pointer as the "absence" of a node, i.e., the end of the list. In other words, the last node in our list will have a next field that contains NULL.

All of our nodes will be allocated on the heap because we don't know in advance how much data our list will store. It is, therefore, convenient to have a function that heap-allocates a chunk of memory to act as a node and populates that chunk with appropriate initial values:

node* make_node(int value, node *next) {
    node *ret = (node*) malloc(sizeof(node));
    ret->value = value;
    ret->next = next;
    return ret;
}

The critical difference between the Racket and C implementations of lists is that in Racket, lists are immutable---once created, a list is never modified. Consequently list operations, specified in a recursive manner produce a new list distinct from list given as input. In contrast, standard C implementations of linked lists are mutable---list operations modify the input list rather than produce new lists. Operations over C linked lists are, therefore, specified in an imperative style, i.e., with loops.

Because of these differences, we add a wrapper to our linked list that holds a pointer to a collection of nodes that constitute the actual list:

typedef struct list {
    node *first;
} list;

We will also heap-allocate our list and thus introduce a function for heap-allocating lists:

list* make_list(void) {
    list *ret = (list*) malloc(sizeof(list));
    ret->first = NULL;
    return ret;
}

Because we have designated a NULL pointer to be the end of a linked list, we represent an empty list by a list whose first field is NULL. Producing a list using this function, e.g., list *l = make_list();, produces the following memory diagram:

Stack      Heap
-----      ----
l [o]----->[\]

The single box in the heap is our list that has a single field, first, that is initially NULL. If we want to add elements onto our list, we can explicitly modify the pointers of the list and its underlying nodes. For example, the assignment l->first = make_node(0, NULL) changes the diagram as follows:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][\]

To add onto the end of the list, we chain together field accesses to modify the last pointer in the list. For example, l->first->next = make_node(1, make_node(2, NULL)).

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]

Exercise: Write It Down

Assume that we previously defined the node and list types given in the reading. Write down the state of memory at each of the indicated points in the following program:

int main(void) {
    list *l = make_list();
    node *n1 = make_node(42, NULL);
    // POINT A
    l->first = n1;
    n1->next = make_node(11, NULL);
    // POINT B
    n1->next->next = make_node(35, n1);
    // POINT C
    return 0;
}

Lists and Pointer Diagrams

As we begin our study of linked lists, it is important we recognize the importance of our memory diagrams in understanding and designing linked list code. Memory diagrams are our lynchpin for moving between high-level intent into low-level code. And with the complexities of non-trivial pointer movement, heap-allocation, and structures, diagrams become more important than ever to ensure that our code matches our intent.

In this lab, we'll go through a number of exercises involving moving between linked list diagrams and code, mirroring how you might use diagrams in real-world coding situations.

Problem 1: Linked Tracing

Assume we have standard definitions of node and list types with associated make functions:

typedef struct node {
    int value;
    struct node *next;
} node;

typedef struct list {
    node *first;
} list;

node* make_node(int value, node *next) {
    node *ret = (node*) malloc(sizeof(node));
    ret->value = value;
    ret->next = next;
    return ret;
}

list* make_list(void) {
    list *ret = (list*) malloc(sizeof(list));
    ret->first = NULL;
    return ret;
}

For each of the following programs, give memory diagrams for each of the following indicated points:

Program 1

int main(void) {
    list *l = make_list();
    node *n1 = make_node(0, NULL);
    node *n2 = make_node(1, NULL);
    // Point A
    n2->next = n1;
    l->first = n2;
    // Point B
    n1->next = make_node(2, make_node(3, NULL));
    l->first = n1;
    // Point C
    return 0;
}

Program 2

void f(int n, list *l) {
    // Point B
    node *n1 = make_node(n, NULL);
    node *n2 = make_node(n+1, NULL);
    node *n3 = make_node(n+2, NULL);
    l->first = n3;
    n3->next = n2;
    n2->next = n1;
}

int main(void) {
    list *l = make_list();
    l->first = make_node(0, make_node(1, NULL));
    // Point A
    f(5, l);
    // Point C
    return 0;
}

Program 3

int main(void) {
    list *l = make_list();
    l->first = make_node(0, make_node(1, make_node(2, NULL)));
    // Point A
    node *n1 = make_node(10, NULL);
    n1->next = l->first;
    l->first = n1;
    // Point B
    node *n2 = make_node(20, n1);
    n1->next = n2;
    // Point C
    return 0;
}

Problem 2: Forth-and-back

Suppose that you have the standard linked list definitions found above. For each set of sequential memory diagrams, give a code snippet that produces those diagrams.

Program 1

// Point A
Stack            Heap
-----            ----
l1 [o]---------->[o]--->[18][o]--->[27][o]--->[32][/]

// Point B
Stack            Heap
-----            ----
l1 [o]---------->[o]--->[18][o]--->[27][o]--->[32][o]--->[80][/]
                          ∧          ∧
n1 [o]--------------------|          |
                                     |
l2 [o]---------->[o]-----------------|

// Point C
Stack            Heap
-----            ----
l1 [o]---------->[o]--->[18][o]--->[27][o]--->[32][o]--->[80][/]
                          ∧          ∧         ∧
n1 [o]--------------------|          |         |
                                     |         |
l2 [o]-------------------------------|         |
                                     |         |
l2 [o]---------->[o]-----------------|         |
                                               |
n2 [o]-----------------------------------------|

Program 2

// Point A
Stack           Heap
-----           ----
l1 [o]--------->[o]--->[0][/]

// Point B
Stack           Heap
-----           ----
l1 [o]--------->[o]--->[0][/]
                        ^
n2 [o]------------------|

n3 [o]------------------------->[1][/]

n4 [o]------------------------------------>[2][/]

// Point C
Stack           Heap
-----           ----
l1 [o]--------->[o]-------------------------|      [0][/]
                                            |       ∧
n2 [o]----------------------------------------------|
                                            |       |
n3 [o]------------------------->[1][o]------|-------|     
                                 ∧          ∨
n4 [o]------------------------------------>[2][o]
                                 |             |
                                 |-------------|

Program 3: Concrete Motions

Each of the following programs represents a concrete instance of one of the linked list motions we will learn about in our next class. As a preview, for each of the following programs, give memory diagrams for each of the following indicated points. In a sentence, describe what behavior the program performed.

Program 1

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, NULL));
    // Point A
    node *n = make_node(0, NULL);
    n->next = l->first;
    l->first = n;
    // Point B 
    return 0;
}

Program 2

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, make_node(3, NULL)));
    // Point A
    node *cur = l->first;
    node *n1 = cur->next;
    cur = n1;
    node *n2 = cur->next;
    cur = n2;
    node *n3 = cur->next;
    cur = n3;
    // Point B
    return 0;
}

Program 3

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, make_node(3, NULL)));
    node *n = l->first;
    node *m = l->first->next;
    // Point A
    n->next = m->next;
    // Point B
    return 0;
}

Program 4: Oh Yeah, Safety

We have introduced function that heap-allocate lists and nodes, but have not discussed how to deallocate these structures! Doing so requires the linked list motions we'll introduce in tomorrow's class. For now, let's introduce a common, errorenous approach to cleaning up a list, a new tool for detecting memory leaks, and how we might fix the resulting memory leak on a concrete linked list instance.

Consider the following code snippet (with suitable auxiliary definitions for node, list, make_node, and make_list):

#include <stdlib.h>

// Definitions of node and list structures and associated functions...

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, make_node(3, NULL)));
    // Point A
    free(l);
    return 0;
}

Draw a memory diagram representing the state of memory at Point A in the code.
Observe that the next line calls the stdlib.h free function which frees a heap-allocated chunk of memory. This ought to clean up the memory and indeed, try compiling and running the program: it seems to complete without errors. However, there is more than what meets the eye here!

Let's use a dynamic analysis tool, AddressSanitizer (ASan), to show that there is actually a memory leak present! ASan is built into recent versions of GCC and Clang and is accessible via the compiler flag, -fsanitize=address. We must compile our program in debug mode, i.e., with -g, and this additional flag to use ASan. ASan is then injected into our code and executes alongside our program. If ASan detects any memory errors, e.g., memory leaks, it will throw an error at runtime and report relevant information.

If you stored your code in a file called leak.c, use the following clang invocation to compile leak.c to leak with ASan support:
```
$> clang leak.c -o leak -g -fsanitize=address -fno-omit-frame-pointer
```
After running your program, you should observe 3 detected memory leaks. Here is an example of one such leak you should encounter. The general form of the error should be the same, but the specific line numbers and addresses will likely be different.
```
Direct leak of 16 byte(s) in 1 object(s) allocated from:
#0 0x7f3eb3881867 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
#1 0x559eb36bc205 in make_node /home/osera/csc161-old-materials/repo/labs/16-linked-lists-setup/leak.c:13
#2 0x559eb36bc302 in main /home/osera/csc161-old-materials/repo/labs/16-linked-lists-setup/leak.c:27
#3 0x7f3eb35cefcf in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
```
This error reports (a) the size of the leaked chunk of memory and (b) a stack trace capturing when and where the leaked memory was initially allocated.

Using this error report, describe in a few sentences:

a. What did the free(l) call actually free? b. What did the free(l) call not free that was leaked?
Fix the code snippet so that it allocates the linked list of three elements but no longer leaks memory. When you rerun the code, it should execute without ASan reporting errors.

When applying data structures to real-world problems, we will frequently need to adapt them to particular domains. In order to have the flexibility to write a variety of operations over a data structure, we need to build a vocabulary of basic methods for manipulating that structure, something I call motions. For example, one motion that you are well-acquainted with is the array traversal:

int *arr, len;
for (int i = 0; i < len; i++) {
    \\ ...
    arr[i]
    \\ ...
}

This motion is something that should come almost automatically to you at this point. If you identify that you need to traverse an array, you can produce this skeleton of code without much thought. Furthermore, you can adapt this skeleton to various situations, e.g., traversing every other element starting with the second:

int *arr, len;
for (int i = 1; i < len; i += 2) {
    \\ ...
    arr[i]
    \\ ...
}

In this section, we investigate the three basic motions you need to know in order to use a linked list: insertion, traversal, and deletion.

Insertion

Suppose that we wish to insert a new element into the front of the list. Concretely, consider the list:

Stack      Heap
-----      ----
l [o]----->[o]-->[1][o]-->[2][\]

How can we insert the value 0 into the front of the list? First, we can create a new node that contains 0 and points to the front of the list:

Stack      Heap
-----      ----
l [o]----->[o]-->[1][o]-->[2][o]-->
                  ^
                  |
              [0][o]

Now, to fix up the diagram, we need to make the first pointer of our list point to this new node.

Stack      Heap
-----      ----
l [o]----->[o]   [1][o]-->[2][o]-->
            |     ^
            |     |
            ->[0][o]

Summarizing the required operations, we:

Create a new node that contains the value to insert and points to the current first node of the list.
Make the list point to this new node as the head of the list.

We can directly translate them into the following insert_front function:

void insert_front(list *list, int v) {
    node *n = make_node(v, list->first);
    list->first = n;
}

We can also collapse these two statements into one:

void insert_front(list *list, int v) {
    list->first = make_node(v, list->first);
}

It is worthwhile to understand how this final function works precisely. Because we evaluate the right-hand side of the assignment first, make_node is passed what list->first initial points to. The assignment then changes list->first to point to the result of make_node.

This compact line can be summarized as the insertion motion for linked lists:

int v;
node *node;
node = make_node(v, node);

We can think of the line as saying "update node to point to a new node in front of what node used to point to".

As a final point, it is worthwhile to note that this function works in the case where the list is empty:

Stack      Heap
-----      ----
l [o]----->[\]

list->first is NULL which means our new node points to NULL:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][\]

But this is exactly the right thing to do for insert_front in this case! This fact is the reason why we included the list struct in our implementation: we needed one level of indirection, i.e., to the head of the list, in order to handle this special case in a uniform manner.

Traversal

Next, let's consider writing a function that computes the total number of elements in the list, its size. To do this for our example list:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]

We must traverse each element, counting the number of elements we visit along the way. If we were to perform a similar operation for an array, e.g., summing up its elements, we would use a for-loop:

int sum = 0;
for (int i = 0; i < len; i++) {
    sum = sum + arr[i];
}

Where the variable i represents the current index we are examining in the array.

We want to apply a similar kind of logic here, but we cannot directly access a linked list's elements by-index. Instead, we will directly hold a pointer to the current node that we are examining:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]
                  ^
                  |
                 cur

Initially this pointer, traditionally called cur , points to the first node in the list. We can declare this auxiliary variable as follows:

node *cur = l->first;

We then advance the pointer to examine the next element. How do we advance cur? Advancing cur means that we need to assign it a new value. The new value we would like to assign cur is a pointer to the node that cur is pointing to, i.e., cur->next. Thus, the line of code to perform the update is:

cur = cur->next;

This results in the following updated diagram.

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]
                            ^
                            |
                           cur

We can then continue to advance the pointer in a loop until we reach the end of the list:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]
                                            
                                          [\]
                                          cur

From the diagram, we see that this situation arises when cur is NULL, i.e., when cur is assigned a copy of the node's next field that holds the value 2. Putting this all together, we can implement the function as follows;

int size(list *list) {
    int sz = 0;
    node *cur = list->first;
    while (cur != NULL) {
        sz = sz + 1;
        cur = cur->next;
    }
    return sz;
}

In summary, the traversal motion looks as follows:

list *list;
node *cur = list->first;
while (cur != NULL) {
    ... cur-> value ...
    cur = cur->next;
}

Most linked list operations require some form of traversal, each with their own little spin on the traversal pattern. It is, therefore, worthwhile to investigate this motion on some additional examples. Let's next consider how to insert at the end of the list. If we want to insert 3 onto the end of the following list:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]

We need to traverse to the end of the list to modify its last pointer. Our standard traversal motion stops when cur is NULL:

Stack      Heap
-----      ----
l [o]----->[o]-->[0][o]-->[1][o]-->[2][\]
                                          [\]
                                          cur

But this is too late! We need to stop when cur is on the last node, so we can modify its next field. We can accomplish this behavior by modifying the guard of the while-loop so that we traverse through the list until cur->next is NULL, i.e., we reach the last node in the list:

while (cur->next != NULL) { /* ... */ }

However, this introduces one additional complication. In the case where the list is empty, cur is initially NULL. Therefore, the first check of this guard will result in a null pointer access where we try to access the next field of a NULL pointer, resulting in undefined behavior.

Because of this, our insert_end function has two cases: whether the list is empty or not.

void insert_end(list *list, int v) {
    node *n = make_node(v, NULL);
    if (list->first == NULL) {
        list->first = n;
    } else {
        node *cur = list->first;
        while (cur->next != NULL) {
            cur = cur->next;
        }
        cur->next = n;
    }

In the case when the list is empty, insert_end behaves like insert_front. Otherwise, we traverse the list until cur is on the last node. At this point, we fix up the last node's pointer to point to our new element. Many list operations that we write have this basic skeleton:

if (list->first == NULL) {
    // Do the operation on an empty list
} else {
    // Do the operation on a non-empty list
}

It is frequently worthwhile to:

Design our functions with this mindset up-front---what does our operation do on the empty list and non-empty list?---and
Test our list functions on both empty and non-empty lists.

Finally, consider the dual operations to make_list and make_node: free_list and free_node. We have some freedom in deciding the behavior of each function. In particular, should make_node free the rest of the nodes that follow it in the list or just itself? Suppose that we choose the former:

void free_node(node *node) {
    free(node);   // N.B. only frees this node, not its next field.
}

How do we implement free_list using free_node? We can perform a standard traversal of the list, freeing every node as we move along. However, if we try the following code snippet inside of our traversal loop:

free_node(cur);
cur = cur->next;  // Bad!

We end up committing a memory error, namely a use-after-free error because we have already freed cur! The simple workaround is to save a pointer to the next node, free cur, and then finally use that saved pointer to advance.

void free_list(list *list) {
    node *cur = list->first;
    while (cur != NULL) {
        node *next = cur->next;
        free_node(cur);
        cur = next;
    }
    free(list);   // Note: don't forget this part!
}

Recursive Traversal

Suppose instead that we wanted our node to be responsible for freeing the nodes that follow it in the list. We could implement a similar loop. However, instead, we can achieve an elegant solution by employing recursive program design ala Racket. Recall that when designing recursive functions over lists, we work with the following design skeleton:

A base case: when the list is empty and
A recursive case: when the list is non-empty.

Here, these cases correspond to when the node we are at is NULL (empty) or non-NULL (non-empty). We can design our recursive function as follows:

To free an empty list, we do nothing.
To free a non-empty list, we free the rest of the list, and then free its head.

And then translate it directly into code:

void free_node(node *node) {
    if (node != NULL) {
        free_node(node->next);
        free(node);
    }
}

Then free_list has the straightforward implementation:

void free_list(list *list) {
    free_node(list->first);   // recursively frees all nodes
    free(list);
}

Again, either implementation of the functions is acceptable---as the designer of the linked list, you simply need to choose one and stick with it throughout your design.

As another example of recursive design, we can rewrite size to be recursive rather than iterative. Note that the signature of the size function as is, int size(list *list), is not appropriate for recursion argument, a list is not recursively defined---the nodes are!

Because of this, we must write a helper function that actually performs the recursion. We can recursively define the function as follows:

The size of an empty list is zero.
The size of a non-empty list is one plus the size of the rest of the list.

And then translate that definition into code:

int node_size(node *node) {
    if (node == NULL) {
        return 0;
    } else {
        return 1 + node_size(node->next);
    }
}

We can then define the user-facing size function in terms of this helper:

int size(list *list) {
    return node_size(list->first);
}

In general, the shape of defining a recursive function over our linked lists has the form:

void helper(node *node) {
    if (node == NULL) {
        // base case---empty list
    } else {
        // recursive case---non-empty list
    }
}

void func(list *list) {
    return helper(list->first);
}

Where func is the user-facing function and helper is the function that actually performs the recursive work over the nodes of the list.

As a rule of thumb, we will favor the iterative version of these operations over the recursive versions. This is because there is a space cost to maintaining all these function calls that the recursive version performs that is not present with the iterative version. Imagine what the stack looks like when we call size on the list, and we finally reach the NULL case:

Stack          Heap
-----          ----
...          [0][o]-->[1][o]-->[2][o]-->
size ---        ^        ^        ^
node [o]--------|        |        |
size ---                 |        |
node [o]-----------------|        |
size ---                          |
node [o]---------------------------
size ---
node [\]

Each recursive function call awaits for the recursive call it makes to return. This means that if the list has n elements, then the stack will grow by n function calls before it begins to return. In contrast, the imperative version of size only requires a single function call, so it does not require any additional stack space to execute.

Functional Aside: Tail-call Optimization Revisited

The space cost induced by the recursive version of size seems to be unavoidable. However, with a little bit of ingenuity and an optimization known as tail-call optimization, we can make the recursive version of size require the same space (roughly) as the imperative version.

The key insight with this optimization is that if a function's final operation is to make a recursive function call, we don't need to create a new stack frame. Instead, we can simply reuse the current stack frame as the new recursive function call's stack frame. By doing so, all the recursive function calls that a function makes only take up a single stack frame rather than n stack frames.

This optimization requires that the function to-be-optimized end with a recursive function call. size is currently not in this form! Consider the single line that makes up the recursive case of size:

return 1 + node_size(node->next);

While the final line of the function contains a recursive function call, note that we must first make the recursive function call and then add one to the result. The fact node_size still has work to do after the recursive call returns (namely add one to the returned value) means that this version of the function cannot be tail-call optimized.

We cannot end the function by performing an addition. To alleviate this issue, we need to re-organize how the function works. Rather than adding one after the recursive call returns, we need to add one before we make the recursive call. But what are we adding one to then, if we can't add it to the result of the recursive call? We instead add one to a new parameter of node_size that accumulates the size of the list:

int node_size(node *node, int acc) {
    if (node == NULL) {
        return acc;
    } else {
        return node_size(node->next, acc + 1);
    }
}

int size(list *list) {
    return node_size(list->first, 0);
}

Now, node_size ends with a recursive function call because the addition happens before the call is made---namely when we evaluate the parameters to the call. In general, we are inverting how node_size performs its computation. Rather than bubbling up the accumulated size from the end of the list back to the front, we push down the accumulated size from the beginning to the end of the list. We can generalize this approach to an advanced form of programming called continuation-passing style where functions take as arguments a continuation denoting what computation to perform after the function completes. With node_size, the "continuation" is simply the value that should be returned after all the node_size calls complete.

Deletion

Finally, how do we remove a particular element, call it v, from a linked list? Let's consider some cases. First, if there is nothing in the list:

Stack      Heap
-----      ----
l [o]----->[o]-->[\]

Then there is nothing to do. In a non-empty list, if v is the first element:

Stack      Heap
-----      ----
l [o]----->[o]-->[v][o]-->[0][o]-->[1][o]-->

We must fix up l->first to point to the node that l->first points to. This pointer is l->first->next, so we have the assignment:

l->first = l->first->next;

This code performs the deletion.

However, if v is not the first element:

Heap
----
... -->[0][o]-->[v][o]-->[1][o]--> ...
        ^
        |
        cur

Then we will need to modify our cur's next pointer to point to what cur->next points to. Like the l->first case, this node is cur->next->next which gives us the assignment:

cur->next = cur->next->next;

These three cases give us the following implementation for delete:

// returns true iff the first occurrence of v is deleted from the list
bool delete(list *list, int v) {
    if (list->first == NULL) {
        return false;
    } else if (list->first->value == v) {
        node *to_del = list->first;
        list->first = list->first->next;
        free_node(to_del);    // assumes that free_node only frees to_del
        return true;
    } else {
        node *cur = list->first;
        while (cur->next != NULL) {
            if (cur->next->value == v) {
                node_t *to_del = cur->next;
                cur->next = cur->next->next;
                free_node(to_del);
                return true;
            }
        }
        return false;
    }
}

Deletion from a linked list provides to be tricker than insertion with several cases, but, nevertheless, the deletion motion is consistent in each case:

node_t *node;
node_t *to_del = node->next;
node->next = node->next->next;
free_node(to_del);

Exercise: One of Many

Implement a function int index_of(list *l, int v) that returns the index of v in l or -1 if v is not found within l. To do this, identify which of the three kinds of linked list motions appropriately captures the behavior of index_of and then adapt the motion skeleton code towards implementing the function.

Linked List Practice

In this lab, we'll implement additional linked list operations to gain practice manipulating linked structures. Implement these functions in your linked list implementation of the list ADT, list.h and list.c, taken from the reading. Make sure to include an appropriate set of tests demonstrating the correctness of your implementation in main.c. Also make sure that your overall programs compiles and runs cleanly with ASan, i.e., compile with -g -fsantize=address.

Write a function, int index_of(list_t *l, int v), that returns the index of the left-most occurrence of v in l or -1 if v is not in l.
Write a function, void insert(list_t *l, int i, int v), that inserts v into index i, shifting the elements of the list to the right. For example, if the list contains the elements [0, 1, 3, 4, 5] and we insert 2 into index 2, the list becomes [0, 1, 2, 3, 4, 5]. If i is not a valid index in l, then the function does nothing.
Write a function, void clear(list_t *l), that clears a list of its contents. Make sure that the nodes that are removed from the list are properly cleaned up!
Write a function, void to_string(list_t *l), that prints out the elements of the list l in the following format: [0, 1, 2, 3, 4, 5]. (Hint: break up the function into three cases: empty list, a list with one element, and a list with more than one element).
Write a function, void dappend(list_t *l1, list_t *l2), that destructively appends l2 onto l1. The nodes of l2 are appended onto the end of l1 so that l2 is empty after completion of dappend.
Write a function, void append(list_t *l1, list_t *l2), that appends l2 onto l1. Copies of the nodes of l2 are appended onto the end of l1. l2 is left un-modified by the function.
Write a function void remove_all(list_t *l, int v) that removes all occurrences of v from l.
Write a function void unique(list_t *l) that removes all duplicate elements from l. (Hint: can you leverage prior functions to make this implementation easier?)
Write a function void reverse(list_t *l) that reverses the list l. (Hint: draw a diagram if you implement this using iteration. If you implement reverse recursively, you will certainly need a helper function with additional arguments.)

For additional practice, try implementing list functions found in other standard libraries from other languages. Here are some examples for you to try out:

Previously we studied the basic linked-based implementation of the list abstract data type. We can further augment this basic implementation in order to optimize common operations or specialize the list's behavior to domain-specific scenarios. In doing so, we begin making trade-offs between features, performance, and implementation complexity.

Memoizing the Size of a List

Recall that the size operation over a linked list traverses the list, counting every node. For small lists, this is not a problem in practice, but if the list is large, then traversing the list—perhaps multiple times in quick succession—is undesirable. Rather than recomputing the size of a list on the fly, we can, instead, remember the size as an additional field of the list structure:

typedef struct list {
    node *first;
    int size;
} list;

size now has a straightforward implementation.

int size(list *l) {
    return l->size;
}

Note that we want to keep the size function even though it is only accessing a field of list. This function still has the effect of hiding the implementation of the list structure even though the function, itself, is very simple.

While size is now simple, we must ensure that the list's size field is kept up-to-date by the other list functions. For example, make_list should initialize the size to be 0:

list* make_list(void) {
    list *ret = (list*) make_list();
    ret->first = NULL;
    ret->size = 0;
    return ret;
}

Functions that insert into the list, e.g., insert_front need to increment the size of the list:

void insert_front(int v, list *l) {
    l->first = make_node(v, l->first);
    l->size++;
}

And functions that remove from the list, e.g., remove_last need to decrement the size:

bool remove_last(list *l) {
    if (l->first == NULL) {
        return false;
    } else {
        node *cur = l->first;
        while (cur->next != NULL) {
            cur = cur->next;
        }
        free(cur->next);  // cur->next is NULL, so this doesn't leak memory!
        cur->next = NULL;
        l->size--;
    }
}

We can capture this responsibility of the list functions to keep the size field updated as an invariant on the list structure:

After the execution of every list function, the size field accurately records the size of the list.

This invariant induces extra burden on our implementation. In particular, you can imagine that it is likely we'll introduce at least one bug into our code by forgetting to update the size field. However, if we are willing to take on this burden, we gain the benefit of a quick way to lookup the size of a list.

End Links

Similar to size, we can also observe a similar sort of performance issue with insert_last. To insert onto the end of the list, we must traverse the entire list. In contrast, we only need to access list->front in order to insert into the front of the list.

To alleviate this issue, we can see that if we had a pointer to the last node of the list, we can use it to quickly append onto the end. This leads to the following variation on our list type:

typedef struct list {
    node *first;
    node *last;
} list;

Like with size, our functions must now ensure that last is always pointing to the last node of the list. Unlike size, keeping last up-to-date requires some careful thought! Let's consider updating insert_back to utilize the last pointer:

void insert_back(int v, list *l) {
    // this code has a bug! do you see it?
    // Hint: think about the possible cases of old_last...
    node *old_last = l->last;
    l->last = make_node(v, null);
    old_last->next = l->last;
}

What's wrong with this code? Consider the field access to old_last->next, this requires that old_last->next, the (old) last node of the list, is non-NULL. When might this not be the case? When the list is empty, of course! Thus, like the insert_front function, we must perform a case analysis on l->last:

void insert_back(int v, list *l) {
    // this code still has a bug! do you see it?
    // Hint: did we forget to update something?
    if (l->last == NULL) {
        l->last = make_node(v, null);
    } else {
        node *old_last = l->last;
        l->last = make_node(v, null);
        old_last->next = l->last;
    }
}

As the code suggests, we forgot to do something. What was it? We needed to update l->first as well because the list was empty! This final code snippet is correct:

void insert_back(int v, list *l) {
    // this code still has a bug! do you see it?
    // Hint: did we forget to update something?
    if (l->last == NULL) {
        l->last = make_node(v, null);
        l->first = l->last;
    } else {
        node *old_last = l->last;
        l->last = make_node(v, null);
        old_last->next = l->last;
    }
}

In the one-element case, both l->first and l->last point to the same node. Will this be a problem when we insert_back an additional element? Let's think through this case with diagrams! In the one element scenario, our list l looks as follows.

l [o]--->[0][/]
  [o]-----^

Let's assume the first cell of l is the first pointer and the second cell is the last pointer. Now, let's modify l so we insert 1 via insert_back. If we follow our code precisely, we:

We hold a temporary pointer to the old last node of the list, 0.
We make the last node of the list a new node containing 1.
We update the old last node to point to this new node.

These three steps modify the diagram as follows:

Step 1:

l        [o]--->[0][ ]
         [o]-----^
old_last [o]-----|

Step 2:

l        [o]--->[0][o]    [1][/]
         [o]-----^---------^
                 |
old_last [o]-----|

Step 3:

l        [o]--->[0][o]--->[1][/]
         [o]-----^---------^
                 |
old_last [o]-----|

So our code works out in the end! But it wasn't clear at all it would do that. We really needed to resort to a diagram to check that our approach was correct. This is the complexity introduced by adding a pointer to the end of the list: we must be very careful about maintaining the first and last pointers since they might be updated at times we don't expect, particularly, when the list is empty.

Riffs on the List ADT

In addition to modifying the linked list implementation, we might also consider modifications of the list ADT itself. By modifications, we don't mean simply adding operations. Instead, we might consider other "list-like" ADTs that can also be implemented using linked lists.

Two of these ADTs are stacks and queues, list-like ADTs that put restrictions on how we can access elements in the list. In the normal list ADT, there usually exists a get-style operation that returns an element of a list by its index. However, many situations involve "list-like" structures but explicitly forbid accessing elements in the middle of the list. For example, with:

A line of people for an activity, we should only add people to the back and remove people from the front.
A stack of books, we should only add and remove books from the top of the stack.

These two scenarios give rise to two different variations of our list ADT:

A queue, a sequential, homogenous, variable-sized data structure that allows for efficient addition to the front and removal from the end of the structure.
A stack, a sequential, homogenous, variable-sized data structure that allows for efficient addition and removal from the front of the structure.

We can codify these interfaces with the following functions, enqueue/dequeue and push/pop, respectively:

// Adds element v to the front of queue q.
void enqueue(int v, queue *q);

// Removes the element at the back of the (assumed to be non-empty) queue.
int dequeue(queue *q);

// Adds element v to the front of stack s.
void push(int v, stack *s);

// Removes the element at the front of the (assumed to be non-empty) stack.
int pop(stack *s)

Note that these structures are precisely lists but with restrictions on how we access these elements. Consequently, there is less to say about the implementations of these functions with our linked implementation. We can implement each function using the standard list operations we've seen previously:

enqueue is insert_front.
dequeue is remove_back.
push is insert_front.
pop is remove_front.

Another way of describing stacks and queues are in terms of how elements flow through the structure:

An element in the queue starts at the front of the queue and exits the back of the queue. This is called first in, last out (FILO) behavior because the latest element added to the queue is the last to leave.
An element in the stack starts at the front of the stack and exits from the front of the stack. This is called first in, first out (FIFO) behavior because the latest element added to the stack is the first to leave.

Exercise: Stack 'em up

Create a complete stack ADT complete with a linked-based implementation. Create files:

stack.h
stack.c
main.c

Which define the interface, implementation, and tests for your stack implementation. Implement the following functions for your stack ADT:

// Returns true iff the stack is empty (contains no elements)
bool is_empty(stack *s);

// Adds element v to the front of stack s.
void push(int v, stack *s);

// Removes the element at the front of the (assumed to be non-empty) stack.
int pop(stack *s)

Note that these implementations should be straightforward adaptions of list functions you have already encountered!

Additional Linked List Practice

Problem 1: "Generic" Linked Lists

Observe that our linked list implementations all have fixed carrier types. That is, the type of the values of the lists are hardcoded, e.g., to int or char. If we wanted a list of type float or char*, we would need to duplicate our entire implementation, substituting our desired carrier type throughout.

If you inspect your linked list implementations, you'll see that (in most cases) your code does not dependent on the carrier type of the list. If there existed a "generic" type, a type that could stand in for all types, you could use that as the carrier types of your list and have one implementation!

a. What type can you use as this "generic" type? (Hint: it is a pointer type!) b. If you made this change to your code, which list functions would not work as expected? How would you modify these functions to make them work with your new generic type? (Hint: this is where function pointers save the day!)

You don't need to change your code for this problem. Brainstorming is fine, but feel free to make a copy of your list implementation and attempt this refactoring for additional practice!

Problem 2: The Problem with "Generic" Linked Lists

There is a big problem with our "generic" linked list! To explore this problem, consider the following memory diagram representing a linked list l over the integers.

stack     heap
-----     ----
l [o]---->[o]--->[0][o]-->[1][o]--->[2][o]-->[3][/]

Can you create this memory layout with your "generic" linked list representation from problem 1? What is the problem you encounter when trying to do so?

Emebdded Linked Lists

Memory locality is an important property of performant code. In short, our hardware performs best when data that is related to each other, e.g., a node's next field and its data, are physically close to each other in memory. With your "generic" implementation, this is, unfortunately, no longer guaranteed.

To regain this guarantee, we need to do some fancy pointer tricks that you could only do in a low-level language like C. Ultimately, our goal is to create "nodes" that look as follows in memory:

|------------|
| Node data  |
|------------|
|            |
| Value data |
|            |
|------------|

In other words, a node is a singular chunk of memory that is the result of "glueing" together both node and "value" data. In our integer example, the "value data" is simply an int, but if we wanted to store structs in our embedded linked list, the value data may contain many fields corresponding to the fields of the struct.

Let's suppose our node data is simply pointer to the next node in the list, i.e., a singular linked list:

typedef struct embedded_node {
    struct embedded_node *next;
} embedded_node;

Where is the data connected to the node? Our embedded_node itself won't know about the data. However, we will allocate node data in such a way that the value data always follows the node data. From there, we can use pointer arithmetic to manufacture pointers to the correct locations.

For example, if we want to access the node portion of this block, we just need to get a pointer to the top of the structure.

n o---> |------------|
        | Node data  |
        |------------|
        |            |
        | Value data |
        |            |
        |------------|

In contrast, if we wish to access the value portion of the block, we need to manufacture an interior pointer to somewhere in the middle of the structure.

        |------------|
        | Node data  |
v o---> |------------|
        |            |
        | Value data |
        |            |
        |------------|

Problem 3: Constructing and Navigating Embedded Nodes

With this description in mind, write the following functions which allow us to make and access the various portions of an embedded linked list.

void* linked_malloc(size_t sz) allocates space for an embedded node on the heap. The size of this node is the size of value data portion of the chunk, sz, plus the size of an embedded_node. linked_malloc returns a pointer to the value data portion of the code!

(Hint 1: what is the byte offset of the value data from the top of the block?)

(Hint 2: normally, adding/subtracting from a pointer increments/decrements the pointer in whole type units. In other words, if p is a pointer to an int (4 bytes), then p+1 is a pointer 4 bytes offset from p, p+2 is a pointer 8 bytes offset from p, etc. What pointer type can you cast to in order to increment your malloc pointer to the start of the value data region of the block?)
embedded_node* get_embedded_node(void *v) returns a pointer to the node data of a chunk of memory allocated by linked_malloc. It is assumed that v is a pointer to the value data portion of this chunk.
void* get_value_data(embedded_node *n) returns a pointer to the value data of a chunk of memory allocated by linked_malloc. It is assumed that v is a pointer to the node data portion of this chunk.

Problem 4: Embedded Linked List Operations

With these three functions, you can now create and manipulate embedded linked lists where the node data is "embedded" alongside the value data! This variant of linked lists is both generic and memory local because the node and value data are next to each other in memory. Implement the following standard linked list functions over embedded linked lists to exercise your implementation.

In all cases, the passed void* pointer lst is assumed to be pointing to a chunk allocated by linked_malloc. The pointer is pointing to the value data portion of the chunk.

size_t length(void *lst) returns the length of the embedded linked list.
void insert_end(void *lst, void *value) inserts value onto the end of list. value is assumed to also be pointing to the value data portion of a a chunk allocated by linked_malloc.
void print(void *lst) prints all the values of embedded linked list lst to the console.
void free_embedded_list(void *lst): frees the embedded linked list. (Hint: for free to work correctly, you must give it a pointer to the top of each linked_malloc` block!)

Intermezzo: Build Tools

Ideally, we do not need to understand how our tools work in order to use them. They should be designed in such a way that their function and use is self-evident. Unfortunately, developer tools, e.g., compilers, editors, and IDEs, are rarely designed with this sort of functionality in mind. Instead, developer tools are designed assuming that you, the programmer, know how their internals work.

This requirement is a double-edged sword. On one hand, their transparency makes them much more difficult to use. For example, consider the error message that arises when you forget the main function in a C program:

$> clang t.c
ld: Undefined symbols:
  _main, referenced from:
      <initial-undefines>
clang: error: linker command failed with exit code 1 (use -v to see invocation)

What is ld? What are "Undefined symbols?" Why can't clang simply say main cannot be found? You, as a programmer, are expected to be able to sift through the noise in this error message to understand the underlying problem. While this error message is rather informative once you get over the language it employs, you have certainly encountered errors in C, whether in your programs, clang, or your editor, that required you to just "know" how things worked in order to derive the actual problem.

The flip side of this transparency is that, with appropriate knowledge of these internals, we can deeply customize our tools to fit exactly the development scenarios we find ourselves in. For example, the emacs is a highly extensible text editor. With appropriate knowledge of how to configurate it using its Lisp-based configuration language, you can create a rich editing experience with support for inline compiler error message and auto-completion.

In this reading, we'll look at some of the build tools you have been using throughout the course with a deeper lens. We'll also give you resources to begin the journey of learning about and ultimately, customizing, your development tools to fit your exact needs.

Separation Compilation

When compiling our C programs, we've sent a single build command to clang, e.g., to compile our linked list programs:

$> clang -Wall -Werror -o prog -g -fsanitize=address list.c main.c

It turns out that this single command hides several steps in the compilation process that become more important to understand as our programs grow! For example, in large-scale C developments, we compile not just two or three C files, but hundreds or even thousands of C files totalling in the millions of lines of source code! In these situations, build times can take hours or even days. So it is important to understand and try to optimize our build times as much as possible.

One important optimization comes from the insight that when we modify a codebase, we typically only modify at most a few files at a time. We can dramatically speed up compilation by only recompiling the parts of the code we modified and integrating those recompiled bits with the rest of the already-compiled program. We call this process separate compilation where we can compile different components of our program independently of each other.

In C, each source file provided to the compiler is consider its own separately compiled unit, called a compilation unit in C parlence. With our standard clang invocation, we don't really separate compilation at work. For example, if we had three .c files, x.c, y.c, and z.c, compiled with the command clang -o prog x.c y.c z.c, we observe the following process, pictured as a diagram:

-------
| x.c |-----\
-------      \   clang -o prog
              \    x.c y.c z.c
-------        \           --------
| y.c |---------o--------> | prog |
-------        /           --------
              /
-------      /
| z.c |-----/
-------

Our three source files do not seem to be separately compiled at all! To observe this separate compilation process at work, we need to use the -c flag which compiles an individual compilation unit into an intermediate file called an object file. For example, if we invoke clang -c x.c we generate an object file called x.o:

-------   clang -c x.c    -------
| x.c | ----------------> | x.o |
-------                   -------

An object file is a compiled file, i.e., machine code, with holes in it. These holes correspond to function definitions found in other compilation units. For example, suppose that x.c is defined thusly:

// x.c

void bar();

void foo() {
    printf("In foo\n");
    bar();
}

bar's type signature is given in x.c but not its implementation. Thus, x.o will have a hole for bar's implementation since it is not provided within x.c directly, presumably provided by either y.c or z.c.

These holes enable each compilation unit to be compiled independently of each other as displayed in the diagram below.

-------   clang -c x.c    -------
| x.c | ----------------> | x.o |
-------                   -------

-------   clang -c y.c    -------
| y.c | ----------------> | y.o |
-------                   -------

-------   clang -c z.c    -------
| z.c | ----------------> | z.o |
-------                   -------

However, we still need to put together these independently-generated object files into a final program. This final step of the compilation process is called linking and is performed by the ld program, although it turns out that we can invoke ld through clang by simply passing in the object files instead of the C source files:

-------   clang -c x.c    -------
| x.c | ----------------> | x.o | ----\
-------                   -------      \   clang -o prog
                                        \    x.o y.o z.o
-------   clang -c y.c    -------        \           --------
| y.c | ----------------> | y.o | --------o--------> | prog |
-------                   -------        /           --------
                                        /
-------   clang -c z.c    -------      /
| z.c | ----------------> | z.o | ----/
-------                   -------

clang hides many flags that it passes to ld to complete the compilation process. For example, here is the (decluttered) call to ld to make our final executable when we call clang on our three-file program. I ran this command on my Mac, so you see a number of Mac-specific flags and directories in the spew.

$> ld -demangle
      -lto_library /Library/Developer/CommandLineTools/usr/lib/libLTO.dylib
      -no_deduplicate
      -dynamic
      -arch arm64
      -platform_version macos 14.0.0 14.0
      -syslibroot /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk
      -o prog
      -L/usr/local/lib
      x.o
      y.o
      z.o
      -lSystem /Library/Developer/CommandLineTools/usr/lib/clang/15.0.0/lib/darwin/libclang_rt.osx.a

(You can view the exact set of commands that clang invokes by passing the verbose -v flag.)

Now suppose that I modify just one my source files, say y.c. To see the effect of my change, I only need to recompile y.c to y.o via the clang -c y.c command. From there, I can re-link the new object file with the older object files. Note that re-linking requires that I process all object files in my program, even those object files I did not touch. But thankfully, I do not have to recompile the untouched compilation units!

Build Management with Makefiles

Separation compilation is a powerful feature of C. However, as you can tell from our running example it is tedious to set up, requiring multiple, precise commands to avoid redundant work. make is a powerful command-line utility for automating multistep build processes. Notably, make can track dependencies between files in a build and smartly issues commands to build a file only when one of its dependency has been modified since the last build.

To use make, we create a file called Makefile (with a capital "M" and no file extension!) alongside our source files. We can then edit our Makefile with build recipes using our text editor. For example, in our previous lab on array lists, we introduced the following Makefile that you copied and used to build your multi-file program:

main : charlist.c main.c
	clang -Wall -Werror -g charlist.c main.c -o main

A Makefile is composed of a collection of recipes, each of which consists of three parts:

A build target.
The build target's dependencies.
Commands to invoke to buil

The Makefile given above is composed of a single recipe for building our main program. The first line of a recipe consists of the build target and its dependencies, separated by a colon. For this recipe, main is our build target and the files charlist.c and main.c are its dependencies. When invoking make on the command-line, we can pass the name of the build target and its corresponding recipe is considered. make invokes the command associated with the recipe, i.e., the subsequent lines of the recipe, if main does not exist or, if it does exist, any one of its dependencies has been modified since main was last modified. For this recipe, we give a call to clang to produce main given our source files.

Importantly, note that the commands of the recipe are all indented one tab character. This indentation must be a tab character instead of multiple spaces. Depending on your editor and settings, you may need to either copy-paste a tab character from a website or search how to enter a tab character in your editor.

Our Makefile does not separately compile our sources. We need to add additional recipes to make this happen. Consider the following updated Makefile that achieves this effect:

main : charlist.o main.o
	clang -Wall -Werror -g charlist.o main.o -o main

charlist.o : charlist.c
	clang -Wall -Werror -g -c charlist.c

main.o : main.c
	clang -Wall -Werror -g -c main.c

The second and third recipes specify how we build object files from our two .c files. And the first recipe updates our original recipe for main to dependent and use these object files to build our program. Now, when we invoke make, the program does the following:

We look at the first recipe to see what main depends on: charlist.o and main.o. We then discover these files' dependencies by looking for their respective recipes and their dependencies and so forth. This search forms a dependency tree of files that depend on each other in this build process. For our `Makefile1, the following tree is formed:
```
     /----> charlist.o ----> charlist.c
    / 
main 
    \
     \----> main.o ----> main.c
```
If any of the dependencies of main are newer than main, we invoke that file's recipe command to update it. If this updates any other files in the dependency tree, we invoke their recipe command to update those files.
Finally, if any of main's dependencies were changed as a result of this process, we invoke main's recipe command to update it.

For example, if we updated only charlist.c (and not main.c), we would:

Update charlist.o by invoking clang -Wall -Werror -g -c charlist.c
Update main by invoking clang -Wall -Werror -g charlist.o main.o -o main.

Note that the process correctly detects that we don't need to recompile main.o since main.c has not been updated!

Learning More About Makefiles

Makefiles are highly configurable to handle a variety of building scenarios. One example of the capabilities of Makefiles are variables that allow us to capture common build patterns in a single recipe. For example, we can concisely write the Makefile above into a generic Makefile that works on any basic C project as follows:

FLAGS = -Wall -Werror -g

prog : charlist.o main.o
	clang $(FLAGS) $^ -o $@

%.o : %.c
	clang $(FLAGS) -c $^

.PHONY : clean

clean :
	rm -rf prog *.o

You can use this Makefile as a starting point for your C projects moving forward, substituting the appropriate object file dependencies for prog in its dependency list. This Makefile uses a number of variables to make things more general-purpose.

We declare a variables FLAGS that allows us to specify the flags to clang in one place. Variables of this sort are declared using the syntax <name> = <text>, and we use the syntax $(<name>) to reference a variable.
We use several automatic variables that are present for each rule:
- $^ expands to the (space separated) dependencies of the recipe.
- $@ expands to the target of the recipe.
Finally, we use wildcard patterns in the third recipe to capture the common recipe for building object files. The recipe pattern %.o : %.c, matches any object file (i.e., a file ending in the .o extension), making it depend on its corresponding C file of the same name, but with a .c extension.

Finally, this Makefile also includes a phony rule that doesn't correspond to a file, but allows us to issue a command concisely. Here the command make clean will delete prog and any object files via the rm command, effectively cleaning our build program from the directory.

For more information on using make, check out the GNU Make manual:

GNU Make Manual

Editors and the Language Server Protocol

Another important aspect of our build tools is our choice of editor. In the old days, there was a stark difference between lightweight text editors and heavyweight integrated development environments (IDEs). As a developer, you would need to make a choice between using a lightweight editor that was quick and responsiveness or a heavyweight editor that provided lots of tools for code introspection, refactoring, and build management.

Today, we get to enjoy the best of both worlds with highly extensible text editors that have a lightweight core, but feature plugins/packages that allow you to add in functionality that quickly approaches the support found in the most comprehensive of IDEs. Three of the most popular of these highly extensible editors are:

The first two of these editors, Emacs and Neovim, are terminal editors that exist entirely within the terminal. Visual Studio Code, in contrast, is a graphical, multi-platform application. While Code is easier to set up and use because it is graphical, it is worth it to invest time in setting up and using a terminal editor like Emacs or Neovim because there are often situations where you need to edit code exclusively in the terminal.

In all three cases, you will want to install appropriate packages for the Language Support Protocol (LSP) which is a standard interface for programming tools to provide services to a text editor including syntax highlight, highlighting errors, code hints, and autocompletion.

In Emacs, you will need to install the Emacs-lsp package.
In Neovim, there are several choices to install, the easiest of which is Coc.
Visual Studio has built-in support for LSP! For our purposes, you just need to install Microsoft's C/C++ Extension Pack.

Sculpting a Development Environment

Like a tradesperson who takes the time to curate and customize their tools, developers do the same with their development tools. Setting up a build system and editor is just the beginning on your journey of customization! As you continue in the curriclum, you should actively look towards refining your development environment. This includes:

Investing in learning Git, a version control system integral for developing larger projects. Github is a Git-hosting service that is a de facto standard in the industry.
Mastering navigating and using the terminal for everyday work. One step towards doing this is using a terminal multiplexing tool that allows you to have multiple virtual terminal windows within a single window. Tmux is the canonical tool in this space.
Further customization of your terminal environment. "Awesome" lists like this denenv one can provide further inspiration for customization!

Memory Management Revisited

C is a unique programming language in that the programmer is wholly responsible for managing their program uses and/or abuses memory. The old adage is particularly useful to remember here:

With great power comes great responsibility!

Indeed, manual memory management is both C's greatest strength and weakness. Certain patterns of low-level, systems programming are quite natural to perform in C. However, we must be diligent in ensuring that our programs do not cause memory safety violations.

For this final leg of the course, we revisit this critical "feature" of C, looking at more advanced, modern perspectives on how to take advantage of manual memory management and stay safe while doing so.

Review: Stack and Heap Allocation

In C, we can allocate data in one of two places:

On the stack via a local variable declaration or a function parameter.
```
int num_widgets = 0;

void process(int amount) {
  // ...
}
```
On the heap via a call to malloc.
```
int *mutable_cell = (int*) malloc(sizeof(int))
```
(Note: this line allocates two chunks of memory: a pointer on the stack called mutable_cell and an int-sized chunk on the heap that mutable_cell points to!)

Stack allocation has many beneficial properties:

Stack allocation is fast, requiring no additional function calls.
Stack allocation is direct, i.e., we (usually) manipulate stack-allocated values directly rather than indirectly via pointers.
Cleaning up stack-allocated memory is automatic, occurring whenever a function call returns.

Because of these properties, we should allocate our data primarily on the stack whenever possible. However, there are limitations to this method of allocation:

Stack-allocated chunks cannot exist outside of the stack frame they were allocated in.
The stack has a limited amount of space. On modern operating systems, this is usually in the range of 1–8 MiB.
The size of stack-allocated chunks must be known at compile-time, i.e., their sizes must be statically determined. In other words, a stack-allocated chunk's size cannot depend on a value known only at runtime, e.g., the number of characters a user will enter at a prompt.

In some cases, we can design our program to circumvent these problems and use stack allocation. In other cases, we must resort to using heap allocation via malloc.

"Out" Parameters

In C, like most languages, a function can only return one value. However, we frequently encounter situations where we want a function to produce multiple values. For example, consider a function read_scores that reads a series of integers from the user, e.g., using fgetc and strtol. This function ought to return an array (likely allocated on the heap) that contains the entered integers. However, the function also needs to report the size of the array as well.

Because C is imperative, i.e., allows values to be mutated, and has explicit pointer types, the idiomatic way of handling this problem is by using the return value of read_scores for the array and passing a pointer to a location that read_scores will fill in with the size of the array. This pointer parameter is called an out parameter. We would write the function read_scores as follows:

int* read_scores (int *sz_out) {
    // ... 
}

Inside of read_scores, we can then write the size of the array to the sz_out parameter. The caller of read_scores would then allocate space for the size, presumably on the stack, and pass a pointer to that chunk to read_scores.

int sz = 0;   // this 0 will be overwritten by read_scores
int *nums = read_scores(&sz);

In some cases, these "out" parameters also allow us to get around the lifetime restrictions of stack-allocated chunks by "inverting" where we perform allocation. For example, recall that stack-allocated arrays are not returned by-copy like other types. We, instead, return a pointer to that stack-allocated array implicitly.

char* read_fixed_size_input() {
  char result [50];
  // ...
  return result;    // returns a pointer to the array, not a copy!
}

This function immediately has a memory error! The returned pointer to result is a dangling pointer because the result array is deallocated when the function returns.

Instead of allocating result inside of read_fixed_size_input, the caller of the function can allocate the result array and pass it as an "out" parameter to the function:

void read_fixed_size_input(char *result) {
  // Now, the function mutates result and returns nothing!
}

int main() {
  char result[50];
  read_fixed_size_input(result);
}

Variable-length Arrays

While "out" parameters solve the lifetime issues associated with stack memory, they do not address the other issues surrounding large, dynamically-determined sizes. An extension to C available in most compilers, variable-length arrays, allows us to use stack-allocated arrays in situations where the size of the desired data is fixed-size but that size is determined.

As a somewhat contrived example, consider the following program snippet that first prompts the user for the size of their name and then uses a variable-length array (VLA) to store that name:


int main() {
  int len = 0;
  printf("How long is your name? ");
  scanf("%d", &len);

  // Consumes the newline character left behind from scanf
  fgetc(stdin);

  printf("What is your name? ");
  char buf [len+1];
  for (int i = 0; i < len; i++) {
    buf[i] = fgetc(stdin);
  }
  buf[len] = '\0';

  printf("Your name is \"%s\"\n", buf);
}

In the code snippet above, note how buf's length is determined dynamically, i.e., it is a value entered by the user! Otherwise, the code behaves as expected, prompting the user first for the length of their name before asking for it. The VLA allows us to cope with a name of any (reasonable) size provided the user gives us the length up-front.

While useful in some cases, VLAs tend to not be as useful in practice as we might expect. The above code snippet demonstrates why: it is rare to be in a situation where our data is both fixed-size but dynamically known. A better prompting function would use our charlist implementation from a previous lab to grow our buffer as the user enters characters rather than demanding the user give us the bound up-front.

When to Allocate on the Heap

We have seen several ways of mitigating the perils of stack allocation. Notably, if we need to avoid a dangling pointer issue where we want to return a chunk of memory from a function, we can allocate the memory outside of the function and use "out" parameters to modify that chunk. However, in situations where:

We need to allocate large chunks of memory that can quickly exceed the size of the stack.
Our memory demands are variable-sized and dynamically determined.

We need to resort to heap allocation with malloc!

One area where we need to be especially cognizant of how we manage our memory is copying data. For example, consider our standard linked list implementation over ints:

typedef struct node {
    int value;
    struct node *next;
} node;

typedef struct {
    node *first;
} list;

node* make_node(int value, node *next) {
    node *ret = (node*) malloc(sizeof(node));
    ret->value = value;
    ret->next = next;
    return ret;
}

list* make_list() {
    list *ret = (list*) malloc(sizeof(list));
    ret->first = NULL;
    return ret;
}

Now consider implementing list* clone_list(list *l) which returns a copy of input list l. A natural implementation of this function is to create new copies of each node as we traverse l:

list* clone_list(list *l) {
    list *ret = make_list()
    if (l->first != NULL) {
        ret->first = make_node(l->first->value, NULL)
        node *cur = l->first;
        node *ret_cur = ret->first;
        while (cur->next != NULL) {
            ret_cur->next = make_node(cur->next->value, NULL);
            cur = cur->next;
            ret_cur = ret_cur->next;
        }
    }
    return ret;
}

For example, the following small program utilizing clone_list:

int main() {
  list *l1 = make_node(0, make_node(1, make_node(2, NULL)));
  list *l2 = clone_list(l1);
  // Point A
}

Produces the following memory layout at the end of the program:

Stack       Heap
-----       ----
l1 [o]----->[o]-->[0][o]-->[1][o]-->[2][/]

l2 [o]----->[o]-->[0][o]-->[1][o]-->[2][/]

However, this is not the only choice of implementation for clone_list. Consider this much simpler implementation instead:

list* clone_list(list *l) {
    list *ret = make_list()
    ret->first = l->first;
    return ret;
}

What memory layout do we obtain with our main program now? We obtain this, very different, layout!

Stack       Heap
-----       ----
l1 [o]----->[o]-->[0][o]-->[1][o]-->[2][/]
                   ∧ 
l2 [o]----->[o]----|

With this second implementation, l2 now shares its nodes with l1!

We say that the first implementation of clone_list produces a deep copy of its input. In contrast, the second implementation produces a shallow copy. With a shallow copy, the resulting copy of the value shares part or all of its memory with its original. In contrast, a deep copy is completely independent of the original.

From both implementations, it should be clear that creating shallow copies of an object is more efficient than producing deep copies. A deep copy requires that we traverse the entire structure to copy values whereas a shallow copy can be made with just a few pointer copies.

However, is sharing nodes between linked lists like this bad? If we never mutated the contents of the linked list, then we would not be able to observe a difference between a shallow and a deep copy! But, we're programming in C and mutation is everywhere, so we have to contend with these effects. In short, whether sharing nodes is acceptable or even preferred depends on the application at hand.

In today's class, we'll continue exploring some of these concepts surrounding memory sharing through several examples. Importantly, we'll also look at a major problem unique to our low-level context when sharing memory: deletion.

(Credit to Stuart Reges and Marty Stepp for the original inspiration for this homework!)

Paranoia

In this homework, you will write a program that uses linked lists to keep track of players in a game of Paranoia. Paranoia (also known by a variety of other names such as Assassin) is a popular "real-life" game where every player is assigned a unique target that only they know about. They must then "tag" that target in a way agreed upon by the group, e.g., with a nerf gun, taking a flag from them ala flag football. A tagged player is then removed them from the game and the person who tags that player inherits their target.

An Example Game and Program Execution

Suppose that we have a Paranoia game consisting of five players: Jane, John, Jackie, Jared, and Jesse. Each of the players is assigned one of the other players as an initial target. This assignment of targets forms a target ring, e.g.,

Jane --> John --> Jackie --> Jared --> Jesse
 ^                                        |
 ------------------------------------------

Here, the assignments of targets are:

Jane is targeting John.
John is targeting Jackie.
Jackie is targeting Jared.
Jared is targeting Jesse.
Jesse is targeting Jane.

When one player eliminates their target, the target is removed from the ring. For example, if Jackie tags Jared, then the ring is updated as follows:

Jane --> John --> Jackie --> Jesse
 ^                              |
 --------------------------------

Now Jackie targets Jesse, Jared's target. Everyone else's targets remain the same. This process continues until only one person is left. For example, if Jane eliminates John and Jackie eliminates Jesse, we have the following ring:

Jane --> Jackie
 ^           |
 -------------

Finally, if Jackie eliminates Jane, then the ring only contains one person---Jackie---whom is the winner:

Jackie

Our program will query the user for the names to enter into the game. It then repeatedly queries the user for names of people who were eliminated until there is only one person left. On every round, the program reports both the list of targets as well as an ordered list of people eliminated so far. Here is a sample invocation of the program emulating the scenario above:

$> ./paranoia
Enter a player's name (press enter to begin game): Jane
Enter another player's name: John
Enter another player's name: Jackie
Enter another player's name: Jared
Enter another player's name: Jesse
Enter another player's name:
Target Ring:
  Jane is stalking John
  John is stalking Jackie
  Jackie is stalking Jared
  Jared is stalking Jesse
  Jesse is stalking Jane
No people have been tagged yet!

There are 5 people left!
Enter a target: Jared
Jared was tagged!
Target Ring:
  Jane is stalking John
  John is stalking Jackie
  Jackie is stalking Jesse
  Jesse is stalking Jane
Tagged List:
  Jared

There are 4 people left!
Enter a target: John
John was tagged!
Target Ring:
  Jane is stalking Jackie
  Jackie is stalking Jesse
  Jesse is stalking Jane
Tagged List:
  Jared
  John

There are 3 people left!
Enter a target: Jesse
Jesse was tagged!
Target Ring:
  Jane is stalking Jackie
  Jackie is stalking Jane
Tagged List:
  Jared
  John
  Jesse

There are 2 people left!
Enter a target: Jane
Jane was tagged!
Jackie is the final person remaining!
Tagged List:
  Jared
  John
  Jesse
  Jane

Note that when the user specifies a target that does not exist (either because they have been tagged already or were never a player to begin with) the game reports an error and continues:

There are 5 people left!
Enter a target: Jerry
Jerry is not a target!
Target Ring:
  Jane is stalking John
  John is stalking Jackie
  Jackie is stalking Jared
  Jared is stalking Jesse
  Jesse is stalking Jane
No people have been tagged yet!

The Paranoia Program

Your program should be broken up into two parts:

A linked list implementation that holds the names of people. This linked list implementation will be used for both the target ring and the tagged list.
A main program driver that queries the user for a set of player names and then plays a game of Paranoia.

The Paranoia Linked List

The linked list implementation should be placed in files called plist.c and plist.h. It should contain a standard linked list implementation as described in class (with a pnode definition for the nodes of the list and a plist definition for the linked list itself). You should implement the following linked list operations and expose them in plist.h:

pnode* make_node(char *name, pnode *next): allocates a new node on the heap with the given values.
plist* make_list(): allocates a new, empty list on the heap.
void free_node(pnode *node): frees the given node.
void free_list(plist *list): frees the given list.
void list_insert(plist *list, char *name): inserts the given name (as a string) into the end of the list.
boolean list_remove(plist *list, char *name): removes the given name from the list, returning true if the name is found and removed and false otherwise.
int list_size(plist *list): returns the number of elements in the list.
void print_as_target_ring: prints the current list interpreting it as the target ring, e.g., if the list contains the names [John, Jane, Mary], print_as_target_ring would output:
```
Target Ring:
John is stalking Jane
Jane is stalking Mary
Mary is stalking John
```
If there is only one person in the target ring, then print_as_target_ring produces:
```
Jackie is the final person remaining!
```
```
Finally if there is no one in the target ring, then `print_as_target_ring` produces:
```
```
There are no targets left!
```
void print_as_tagged_list(plist *list): prints the current list interpreting it as the tagged list, e.g., if the list contains the names [John, Jane, Mary], the function outputs:
```
Tagged List:
John
Jane
Mary
```
If no one has been tagged yet, the function outputs:
```
No people have been tagged yet!
```

The Paranoia Driver

Inside of a file called paranoia.c you should implement the main function for the program. It should use two lists---one for the target ring and the other for the tagged list. The program should behave as follows:

Repeatedly prompt the user for names to enter into the initial target ring. Your program should be able to handle names of unbounded size. You should stop prompting the user when they enter a blank line and then move to the next phase.
Repeatedly play rounds of Paranoia with the user. This consists of querying the user for a target that was eliminated and then updating the target ring and tagged list accordingly. Again, the program should behave gracefully if a target not in the target ring is specified.
Once there is less than one person left, the game prints the final contents of the target ring and tagged list and exits.

To get user input from the user, I highly recommend using the getline function found in stdio.h that we wrote in a previous lab. Alternatively, you can use the various charlist and my_getline implementations we created in previous labs.

Memory Management

You will need to be very careful about heap allocations in your program! In particular:

For every heap allocation you make, you should ask yourself: "whom is responsible for cleaning up this chunk of memory?"
You need to ensure that you avoid leaking not just your linked list nodes, but the strings they hold pointers to.

Use ASan liberal in your development process to ferret out memory error bugs.

Ownership

When sharing memory between structures, memory management bites us yet again. Consider the following situation where we have two linked lists, one of which is a shallow copy of the other:

Stack       Heap
-----       ----
l1 [o]----->[o]-->[0][o]-->[1][o]-->[2][/]
                   ∧ 
l2 [o]----->[o]----|

If we try to free both l1 and l2, we encounter a different kind of memory error, a double free error. This arises because free performs internal bookkeeping to track that the memory passed to it is now available for reuse. freeing memory again mucks up this internal bookkeeping, leading to undefined behavior!

If we were to allow this kind of memory sharing, we have to be very careful about how we deallocate this structure. We need to:

Free the nodes of the list through exactly one of l1 or l2, say l1 for example's sake.
Free the memory allocated to the list struct pointed at by l1.
Free the memory allocated to the list struct pointed at by l2 without double-freeing the nodes that l2 now has a dangling pointer to.

This means we have to treat l2 specially! Such code is easy to write if l1 and l2 are both local variables in the same function, i.e., they are textually next to each other in our program. However, if l1 and l2 get passed to different parts of our code, performing such ad hoc behavior gets tricky. In particular, we have to guarantee that l1 is always deallocated before l2. Otherwise, we'll end up leaking memory!

Now, imagine even worse situations where the two linked lists share nodes in more exotic ways:

Stack       Heap
-----       ----
l1 [o]----->[o]-->[0][o]-->[1][o]-->[2][/]
                            ∧        
l2 [o]----->[o]-->[3][o]----|

Who is responsible for freeing which nodes between the two lists? How can we figure this out programmatically if the lists have arbitrary numbers of shared and unshared nodes?

Maintaining Discipline

In short, it is virtually impossible to handle intricate cases of memory sharing in a general way while also maintaining memory safety! Instead, it is more pragmatic to maintain a particular discipline or collection of design patterns that allows us to maintain our sanity while navigating these problems.

There are several such disciplines of manual memory management that we might adopt in our programs. One of the most common of these disciplines is that of pointer ownership. The key idea behind pointer ownership is that we maintain the following invariant about all of the heap-allocated chunks in our program:

At any point during execution of our program, each heap-allocated chunk has one pointer to it through which the memory is eventually freed We call this pointer the owner pointer.

For example, in the following code snippet:

char *buf = (char*) malloc(sizeof(char) * len);

We create a heap-allocated chunk, presumably to hold a string. The pointer buf becomes the owner pointer for this chunk as it is the only handle we have on the memory. If nothing else happens in our program, we will ultimately need to free the heap-allocated chunk through buf before buf goes out of scope.

Note that there is nothing in our program or C that enforces that buf is an owner pointer or that we must free buf before it goes out of scope. We must, instead, maintain this discipline through good programming practices, including documentation and naming, and diligence.

Transferring Ownership

A key feature of heap-allocated memory is that we can return it from a function. How does this work with owner pointers?

We can transfer ownership of a heap-allocated chunk from one pointer to another. This arises naturally with the constructor functions that we write, e.g., make_list:

list* make_list() {
    // ret is initially the owner for the heap-allocated chunk
    list *ret = (list*) malloc(sizeof(list));
    ret->first = NULL;
    // Now, ownership transfers from ret as it is deallocated...
    return ret;
}

int main() {
    // ...to lst in main!
    list *lst = make_list();

    // lst is ultimately responsible for freeing the chunk
    free_list(lst);
}

Observe in the sample code how ret is the initial owner of the list. But by virtue of returning a copy of this pointer, it transfers ownership to the caller of make_list. main is therefore responsible for freeing the heap-allocated chunk through lst.

The fact that make_list transfers ownership of a heap-allocated to its caller is important enough to document:

// Returns an owner pointer to a new, empty list on the heap.
list* make_list() {
  // ...
}

With this documentation, callers of make_list know that they are responsible for freeing the list they receive from the function.

While ownership transfer occurs most commonly with constructor functions, it also arises in situations where we allocate memory in multiple steps to build a larger structure. For example, we might use the getline function to heap-allocate a chunk of memory, populate it with input from the user, and then store a pointer to that chunk:

typedef struct {
    char *name;   // owner pointer
    int age;
} person;

// Returns a new, heap-allocated person. Ownership of name is transferred
// to this person upon construction.
person* make_person(char *name) {
    person *ret = (person*) malloc(sizeof(person));
    ret->name = name;
    // All people start at age zero!
    ret->age = 0;
    return ret;
}

void free_person(person *p) {
    // N.B., make sure to free name since we own it!
    free(p->name);
    free(p);
}

int main() {
  char *name;
  int sz;
  // Mutates name to point to heap-allocated line of input from stdin.
  getline(&name, &sz, stdin);
  person *p = make_person(name);
  // NULL out `name` since it has been transferred to p
  name = NULL;
  // ...
  free_person(p);
}

In this code, the name pointer in main owns the memory allocated by getline. But then, we transfer ownership of that chunk to the person struct via make_person. Therefore, we know that we do not need to free name in main. Instead, we can trust that free_person will eventually free that chunk for us.

Again, note how none of this is enforced by C. We need to rely on coding conventions to enforce this discipline. One good trick to make this more explicit in code is to reassign any transferred pointers to NULL. This ensures that if such a pointer is used after it has been transferred will result in a quick null pointer dereference instead of undefined behavior.

Borrowing a Pointer

Frequently, other parts of code will want to use a heap-allocated chunk without taking ownership of it. Thus, we also allow parts of code to borrow a heap-allocated chunk, in effect, creating additional pointers to a heap-allocated chunk beyond the owner pointer.

// age_person increments the age of (borrowed) person p by 1.
void age_person(person *p) {
    p->age++;
}

int main() {
    person *jo;
    // initialize jo somehow...
    age_person(jo);

    // Because jo is still the owner pointer for the memory, we must deallocate them now!
    free_person(jo);
}

In this example, age_person borrows jo by taking a copy of the jo pointer and performing a mutation through it.

We allow for multiple borrowed pointers to exist in our program. However, we know that if borrowed pointers exist, then it isn't safe for the owner pointer to free that memory. This is because we might try to erroneously access the chunk through our borrowed pointers if we prematurely free it.

Thus, we introduce the following rule for managing borrowed pointers:

An owner pointer cannot free its chunk of memory until all borrowed pointers to that chunk are deallocated.

Borrowing a pointer by passing it to a function is a simple case since that borrowed pointer is deallocated specifically at the last point that pointer could be used, i.e., at the end of its enclosing function! However, we can get into more intricate borrowing scenarios when those borrowed pointers are stored in other data structures whose lifetime might extend beyond the functions in which they are created.

int main(void) {
  char *stooge1, *stooge2, *stooge3;
  int sz;
  getline(&stooge1, &sz, stdin);
  getline(&stooge2, &sz, stdin);
  getline(&stooge3, &sz, stdin);

  // N.B., stooges should borrow its elements; it is not
  // responsible for freeing them
  char **stooges = (char*) malloc(sizeof(char*) * 3);
  stooges[0] = stooge1;
  stooges[1] = stooge2;
  stooges[2] = stooge3;

  // Do arbitrary stuff to stooges, passing them to other functions, etc.
 
  // Nevertheless, once stooges is deallocated...
  free(stooges);

  // We can free the stooges through our original pointers!
  free(stooge1);
  free(stooge2);
  free(stooge3);
}

In this example, we allow a data structure to borrow three heap-allocated chunks of memory. That data structure can do arbitrary things (besides deallocating the chunks, of course) and live for an arbitrary long period of time. However, by acknowledging that the data structure only borrowed the chunks, we know that we must eventually free the chunks through their original pointers.

Summary of Ownership Rules

Pointer ownership discipline keeps our heap manipulation code from being incomprehensible. This discipline consists of three key rules:

At any point during execution of our program, each heap-allocated chunk has one pointer to it through which the memory is eventually freed We call this pointer the owner pointer.

A copy of a pointer to a heap-allocated chunk is a borrowed pointer to that chunk. Other code can access the chunk through borrowed pointers.

An owner pointer cannot free its chunk of memory until all borrowed pointers to that chunk are deallocated.

Putting Ownership Into Practice

Each of the subsequent programs possesses a memory leak. Lets use the ownership memory management discipline discussed in the reading to understand and, ultimately, fix these programs.

For this lab, you will turn in three debugged programs, prog1.c, prog2.c, and prog3.c. For each program:

Identify the source of the memory leak, using a comment at the line where the leak occurs. Explain in a comment why the leak occurs, using a sentence or two.
For each pointer in the program, identify if that pointer is an owning pointer or a borrowing pointer for that chunk of memory. Along the way, also identify any points in the program where ownership transitions between pointers.
Once you have identified the appropriate owners of the leaked memory, modify the code so that the chunk is freed through the owning pointer before that pointer is deallocated.

Program 1

// prog1.c
#include <stdio.h>
#include <stdlib.h>

int* make_blob() {
    int *ret = (int*) malloc(sizeof(int));
    *ret = 0;
    return ret;
}

void mutate(int *v) {
    *v = 22;
}

int main(void) {
    int *p = make_blob();
    mutate(p);
    printf("%d", *p);
    return 0;
}

Program 2

// prog2.c
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char *value;
    struct node *next;
} node;

typedef struct list {
    node *first;
} list;

node* make_node(char *value, node *next) {
    node *ret = (node*) malloc(sizeof(node));
    ret->value = value;
    ret->next = next;
    return ret;
}

list* make_list(void) {
    list *ret = (list*) malloc(sizeof(list));
    ret->first = NULL;
    return ret;
}


void free_list(list *l) {
    node *cur = l->first;
    while (cur != NULL) {
        node *to_del = cur;
        cur = cur->next;
    }
    free(l);
}

void print_list(list *l) {
    node *cur = l->first;
    while (cur != NULL) {
        printf("%s", cur->value);
        cur = cur->next;
    }
}

char* get_input(void) {
    char *buf = NULL;
    size_t sz = 0;
    // `getline` is a POSIX library function. The function prompts the user for
    // a line of input and modifies the first argument to point to a
    // heap-allocated chunk that holds that input!
    printf("Enter a name: ");
    getline(&buf, &sz, stdin);
    return buf;
}

int main(void) {
    list *l = make_list();
    l->first = make_node(get_input(), make_node(get_input(), make_node(get_input(), NULL)));
    print_list(l);
    free_list(l);
    return 0;
}

Program 3

(Hint: for this program, it may not be obvious who is the owner of the relevant memory blocks. Think about making some heavyweight changes to the code, e.g., copying values around, to make it obvious who owns each heap-allocated block.)

// prog3.c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

const int INITIAL_CAPACITY = 8;
const int NUM_PEOPLE = 3;

typedef struct {
    char **names;
    int size;
    int capacity;
} name_list;

name_list* make_list() {
    name_list *ret = (name_list*) malloc(sizeof(name_list));
    ret->names = (char**) malloc(INITIAL_CAPACITY * sizeof(char*));
    ret->size = 0;
    ret->capacity = INITIAL_CAPACITY;
    return ret;
}

void free_list(name_list *list) {
    free(list->names);
    free(list);
}

void list_add(char* name, name_list *list) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->names = realloc(list->names, list->capacity);
    }
    list->names[list->size++] = name;
}

char* list_get(int index, name_list *list) {
    return list->names[index];
}

char* get_input(void) {
    char *buf = NULL;
    size_t sz = 0;
    printf("Enter a name: ");
    getline(&buf, &sz, stdin);
    return buf;
}

int main() {
    srand(time(NULL));

    name_list *people = make_list();
    for (int i = 0; i < NUM_PEOPLE; i++) {
        list_add(get_input(), people);
    }

    name_list *pool_a = make_list();
    name_list *pool_b = make_list();

    // The people are shuffled between the pools arbitrarily.
    // A person can be in both pools at once. All people
    // end up in at least one of the pools.
    for (int i = 0; i < NUM_PEOPLE; i++) {
        int k = rand() % 3;
        switch (k) {
        case 0:
            list_add(list_get(i, people), pool_a);
            break;
        case 1:
            list_add(list_get(i, people), pool_b);
            break;
        case 2:
            list_add(list_get(i, people), pool_a);
            list_add(list_get(i, people), pool_b);
            break;
        }
    }

    free(pool_a);
    free(pool_b);
    free(people);
}

Productive C Practices

Pointer ownership discipline is an example of a productive C practice, something that we do to keep the complexities of the language under control. We've looked at a number of these practices already in the course:

Use good development tools that report errors (e.g., type errors) as early as possible
Minimize mutation whenever possible.
Favor local variables (stack allocation) over malloc (heap allocation).
Unabashedly draw diagrams to understand the layout of memory.
Use debuggers to aid in code understanding.
Use pointer ownership discipline to manage heap allocations.
Document assumptions about your code not already captured in the text.

Practices like these are what separate productive from unproductive C programmers. With good practices and discipline, we can write efficiently write memory-safe C code.

Below, we describe two additional practices that you should consider employing throughout your code.

`const`-correctness

We now know that much of C's complexity lies in the fact that we mutate the values of memory locations. To reduce the complexity of our code, we can simply minimize the amount of mutation that occurs. Unlike many of the practices above where there is little language support helping us along the way, there is a language feature that helps us maintain good mutation discipline: the const keyword.

const is a qualifier on a type, denoting that the memory location of that type cannot be mutated. In its most basic usage, const is a type-safe alternative to #define constants:

const int NUM_VALUES = 10;

// Produces a type error:
//   error: cannot assign to variable 'NUM_VALUES' with const-qualified type 'const int'
NUM_VALUES = 0;

This declaration is type-safe in the sense that the compiler knows NUM_VALUES is a const int and can produce better diagnostics. Compare this with the equivalent #define:

#define NUM_VALUES 10

// Produces a compiler error:
//   error: expression is not assignable
NUM_VALUES = 0;

Recall that #define just defines a textual substitution—the compiler replaces NUM_VALUES with 10 throughout our code. So the assignment becomes the non-sensible 10 = 0 which produces an error message that requires a bit of interpretation to understand.

In addition to local variable declarations, we can also place const on the types of function parameters. These const qualifiers are much more interesting because they act as documentation for our functions. For example, consider a function that pretty-prints a name from a collection of strings:

void print_name (const char *first_name, const char *middle_initial, const char *last_name) {
    printf("%s %s. %s", first_name, middle_initial, last_name);
}

The types of each of the parameters is const char *. Recall that we read types in C backward, i.e., right-to-left, so we can read this type as:

A pointer to one or more chars that are const, i.e., cannot be modified.

This means that the C compiler will ensure that print_name does not mutate any of its arguments! Since this qualifier appears in the type of the function, callers of the function will know this behavior of print_name without having to read the documentation!

In general, the practice of writing const-correct code involves using const as much as possible, especially in function parameter types, to document precisely where in your code you expect values to be mutable.

`restrict` and Pointer Aliasing

Consider the following simple struct that holds a pointer to a heap-allocated int:

typedef struct {
  int *value;
} cell;

Now consider the following function which moves the heap-allocated value from one cell to another, taking care to deallocate the heap-allocated value from the destination before losing our handle on it.

void move (cell *dst, cell *src) {
  free(dst->value);
  dst->value = src->value;
}

This code has a very subtle memory bug! Can you find it?

Consider the situation where we pass the same cell as both the source and destination for the move:

cell c;
c.value = (int*) malloc(sizeof(int))
*(c.value) = 22;
move(c, c);

Let's trace the execution of move line-by-line. When we first enter move, we have the following memory layout:

main -----
c [o]------------>[22]
move -----         ∧
dst [o]------------|
src [o]------------|

c is a cell, which is just a fancy pointer to a heap-allocated int. We end up making two copies of this cell, one for dst and src, all pointing to the same heap-allocated value 22.

On the next line, we delete 22 through dst:

main -----
c [o]------------>
move -----         ∧
dst [o]------------|
src [o]------------|

We then copy src's pointer into dst. But they were already were the same pointer, so nothing changes!

When we return from the function, we have:

main -----
c [o]------------>

c is now a dangling pointer to a freed chunk of memory. Any access to c->value will be a use-after-free error unless we point c->value to another heap-allocated chunk!

What went wrong here? It turns out that our code does not work when our two pointers src and dst are aliases to the same chunk of memory! Pointer aliasing of this sort is a huge problem in C code. Frequently, our code breaks down if it happens to be the case that two pointers we're operating over can point to the same value. Furthermore, some compiler optimizations are not possible if the compiler cannot prove that two pointers point to distinct memory locations.

The fix to our code, it turns out, is simple: only perform the move if the pointers point to distinct locations. We can check this via a pointer equality comparison:

void move (cell *dst, cell *src) {
    if (dst != src) {
        free(dst->value);
        dst->value = src->value;
    }
}

Alternatively, if we want to document that dst and src are assumed to be pointing to distinct locations, we use the restrict qualifier:

void move (cell * restrict dst, cell * restrict src) {
    // ...
}

By marking the pointer types as restrict, we are declaring that dst and src are restricted to point to distinct locations in memory. Unlike const, the compiler does not enforce this property on the pointers passed to move. Instead, this qualifier acts as documentation for users of the function. It also allows the compiler to perform optimizations on the code assuming that dst and src aren't aliasing the same memory location.

(Strictly speaking, the actual semantics of restrict state that any object accessed dst can only be accessed through dst in move, likewise for src. This means, effectively, that src and dst point to distinct memory locations.)

Unstructured Control Flow

While the reading for today talked about good C practices, we spent our introductory time together talking about one of the bad parts of C that we should avoid: unstructured control flow. In this series of exercises, we'll get a concrete sense for why unstructured control flow is undesirable in most situations, and then explore a situation where it may be appropriate.

Problem 1: Unstructured Tracing

goto allows us to perform local unstructured jumping between labeled points within a function. For the following program, give stack/heap diagrams for each of the indicated points (1, 2, and 3). Check your work by compiling and running your program!

(Hint: labels of the form label: are just annotations in code. For the purposes of statement-by-statement execution, you should ignore them!)

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i = 0;
    int *z = (int*) malloc(sizeof(int));
    *z = 2;
    // Point A
    label_a:
        if (i < 5) goto label_b;
        *z *= *z;
        i++;
        // Point B (first time only)
        goto label_a;
    label_b:
        if (*z % 2 == 0)
            goto label_c;
        else
            goto label_d;
    label_c:
        *z += 1;
    label_d:
        i = 0;
    // Point C
    printf("%d %d\n", *z, i);
}

Even more fun than goto: the setjmp and longjmp functions from the standard header setjmp.h provide facilities for performing global unstructured jumps. With setjmp and longjmp, you can save the contents of the stack and magically "return" to that saved point, regardless of where you are in your program!

int setjmp(jmp_buf env) loads env with values appropriate for remembering the state of the stack at the point of execution of the setjmp function. The function returns 0 on its "initial" invocation (see longjmp).
void longjmp(jmp_buf env, int value) causes the state of the stack to be restored to the setjmp point corresponding to the jmp_buf call that populated env. Program execution continues as if the corresponding setjmp returned but with value produced rather than 0.

For the following program, give stack/heap diagrams for each of the indicated points (A, B, and C). Check your work by compiling and running your program!

#include <setjmp.h>
#include <stdio.h>

jmp_buf env;

int factorial_maybe(int n) {
    if (n == 0) {
        // Point B
        longjmp(env, 11);
        return 0;
    } else {
        int result = 0;
        if (n == 4) {
            // Point A
            if (!(result = setjmp(env))) {
                result = factorial_maybe(n - 1);
            }
        } else {
            result = factorial_maybe(n - 1);
        }
        return n * result;
    }
}

int main(void) {
    int result = factorial_maybe(5);
    // Point C
}

Problem 2: Exceptions to the Rule

Unstructured control flow like goto and setjmp/longjmp seem strictly inferior to structured control flow constructs. Indeed, we should minimize our usage of these constructs whenever possible. However, there are times in C where goto and setjmp/longjmp are actually useful!

Consider the following program:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct blob {
    char *data;
} blob;

char get_single_char(void) {
    char ch = getchar();    // assumes user enters a single character
    getchar();              // ...and get rid of the newline character!
    return ch;
}

bool init_blob(char ch, blob *b) {
    if (ch == 'x') {
        return false;
    }
    b->data = (char*) malloc(sizeof(char));
    *b->data = ch;
    return true;
}

int main(void) {
    blob b1, b2, b3;
    char ch = get_single_char();
    if (!init_blob(ch, &b1)) {
        printf("First round: entered x, fail!");
        return 0;
    }

    ch = get_single_char();
    if (!init_blob(ch, &b2)) {
        printf("Second round: entered x, fail!");
        return 0;
    }

    ch = get_single_char();
    if (!init_blob(ch, &b3)) {
        printf("Third round: entered x, fail!");
        return 0;
    }

    printf("Results: %c, %c, and %c\n", *b1.data, *b2.data, *b3.data);
    free(b3.data);
    free(b2.data);
    free(b1.data);
    return 0;
}

a. This program has a memory leak! Compile and test this program using -g -fsanitize=address to determine where the memory leak occurs. In a few sentences, describe the situations in which this program leaks memory and why this is the case. b. Give a version of this program (without using gotos) that maintains the intent and (as much as possible) keeps the structure of the code intact. c. Now, starting from the original program, use gotos to minimally change the code to make it memory safe. d. In a few sentences, compare and contrast the programs that you receive from parts (b) and (c). What are the strengths and weaknesses of each approach as you see them. e. Suppose someone told you the following:

> `goto`s are evil; Dijkstra said so.
> Never use `goto`s.

Would you agree or disagree with this person?
In a few sentences explain how you would respond to this person.

Lab: Computer Science Murder Mystery

(Credit to David J. Malan for coming up with the original version of this assignment!)

This week we are going to use low-level programming in C to solve a murder mystery.

Backstory

Philadelphia, PA (DP)—A body of a graduate student was found yesterday in the graduate student offices of the CIS department in Levine hall. Campus police said that graduate students in adjacent offices heard noises coming from the office in question early in day. However, since all graduate students are anti-social and never leave their desks because they're constantly slaving away at research, no one actually witnessed the incident or saw the body. The janitorial staff reported the incident to campus police when they found the body during their nightly rounds.

Police released the identity of the graduate student as one Poor G. Student. They also stated that Student was found dead in his own office although they did not release how he was murdered.

Campus police have arrested four graduate students under suspicion of murder. All four graduate students are inhabitants of the office. However insider sources have claimed that the police have no evidence that these students have comitted the acts as the office was found by campus police to be clean with no sign of the weapons that were used in the attack. Our insider sources also claim that the only piece of evidence found at the scene was a digital camera destroyed in the attack, possibly held by the victim while the attack was taking place. Unfortunately, the memory card of the camera was allegedly damaged in the attack as well.

Update (9:49 AM): We have received mugshots and the identities of the four graduate students that are now being held by the police. All four of them have pleaded innocence in light of the lack of evidence against them.

The suspects

The suspects (left-to-right, top-to-bottom) are Daniel, Brent, Vilhelm, and Aileen.

Part 1: Data Recovery

As computer scientists without direct ties to the CIS graduate students, you have been tasked by the campus police to try to extract data from the damaged flash card found at the scene of the murder. While we can't directly load the data on the card, we can still use our hacking skills to extract the evidence. To do so, we first need to know some things about JPEGs and how they are stored on the flash card.

JPEG headers

It turns out that most JPEGs have a unique signature or header that distinguishes them from other types of files. More specifically, the first four bytes of most JPEGs are either

0xff 0xd8 0xff 0xe0

Or:

0xff 0xd8 0xff 0xe1

where we read the bytes from left to right, first to fourth. If you scan the raw bytes of the flash card and come across these patterns of bytes, it is highly likely that you have found a JPEG.

FAT and storing JPEGs on the flash card

Even though we can find the beginning of a JPEG, this is not necessarily the end of the story. The way that a JPEG (more generally, any file) is stored on the flash card is also important. For example, if the JPEG is stored on many different, non-contiguous memory blocks of the flash card (e.g., due to fragmentation), then a simple, naive scan of the flash card will put these disconnected blocks together. This may manifest itself in a corrupted or unreadable file.

Luckily for us, digital cameras only write to the flash card to save a photo. And also, since the camera was new, our victim probably did not get a chance to delete any files from it. Thus, it is safe to assume that most of the photos are contiguously stored on the card.

Furthermore, many flash card/camera systems use a FAT file system where blocks have a size of 512 bytes. This means that cameras only write to the flash card in blocks of 512 bytes. So, for example, a file that is 520 bytes uses the same number of blocks (namely 2) on the memory card (and thus the same amount of storage) as a file that takes 1024 bytes. This unused space in the first case (504 bytes) is called slack space and can be an indication to forensic investigators that real data is lying nearby. For us, since the camera and flash card are new, the slack space should be all 0s (so it shouldn't hurt if we appended this data to the end of a jpeg file). It also means that the headers of the JPEGs that we are looking for will appear only in the first 4 bytes of each 512 byte block we read from the file!

An approach

With all this in mind, we can come up with a basic strategy for recovery the JPEGs from the damaged flash card.

We can iterate over the bytes of the flash card and look for JPEG headers.
Once we find a header, we can open a new file and start filling that file with bytes from the flash card.
Once we find a new header, we can close the previous file and open a new file for writing, continuing in this manner until we reach the end of the flash card.

Logistics and Instructions

Since I can't give everyone in the class a physical copy of the flash card, I've made an image of the flash card for you to use. The flash card only contains the portion of the flash card that we suspect contains the data in question as the original card was 2 GBs. It can be found here:

evidence.raw

Given this file, create a program called recover that takes the name of a card image as an argument and extracts the JPEGs from that card image. The extracted JPEGs should be named ###.jpg where "###" is a three-digit decimal number starting at 000. For example, if there are three files in the card image, then the program should write 000.jpg, 001.jpg, and 002.jpgj.

Here is an example of my recover program on a test card image:

$> ls
card.raw  recover  recover.c
$> ./recover
Usage: ./recover <image>
$> ./recover card.raw
Recovering jpegs from card.raw...
Writing to 000.jpg...
Writing to 001.jpg...
Writing to 002.jpg...
$> ls
000.jpg  001.jpg  002.jpg  card.raw  recover  recover.c
$>

You do not need to duplicate the console output from my program, but your program should give an error/usage message similar to mine when the program is not run with exactly one argument (i.e., just ./recover ./recover foo bar).

Part 2: Whodunit?

After you've extracted the photos, take a look at them and figure out the mystery. Who killed Poor G. Student? Like any good crime, there must means, motive, and opportunity. In a comment at the bottom of your recover.c source file, answer the following questions:

Who committed the crime?
How did they commit the crime (i.e., what weapon did they use)?
Why did they commit the crime?
When did they commit the crime? (absolute time not necessary; relative to some event is fine)

You will get full credit for simply attempting to answer these questions. But it's more important to be right to show off your sleuthing skills. Be creative! Remember that graduate students are silly, superficial beings so don't be afraid to let that factor into your conclusion.

Challenge problem: There's More!

In addition to the jpeg, we suspect that there were other files, in particular an email correspondence, left on the flash drive. Write a program recover_ex that extracts that email correspondence. You can apply a similar approach as with part 1, but note that email correspondence is pure text. You will need to come up with a method to know when you've found the block of bytes corresponding to the email. recover_ex should write the discovered email to mail.txt.

Hints and Advice

For this lab, you will use the file-processing facilities of stdio.h. In particular you should keep in mind the functions fopen, fclose, fread, fwrite, and sprintf.
As mentioned above, you'll need to create a buffer of 512 bytes to store the blocks of data you read from the flash card. There is no "byte" type in C. It turns out that unsigned char serves this purpose since char is defined to be a byte.

Arena Allocation

In class, we discussed an alternative memory management discipline, arena allocation. With this scheme, we maintain one or more arenas, large chunks of memory from which we create allocations. We do not worry about manually freeing individual allocations. Instead, we release an arena once when we are done using it!

Ownership-based memory allocation is the correct tool for most programs. However, in the few cases where arena allocation is applicable, it is both more efficient and easier to get right compared to our standard approaches!

In this optional lab, you will implement an arena allocator as introduced in class. Here is the header that you will implement:

// arena.h
#pragma once

#include <stdlib.h>

typedef struct {
    void *base;  // A pointer to the base of the arena's chunk
    void *bound; // A pointer to the end (bound) of the arena's chunk
    void *cur;   // A pointer into the chunk indicating where we allocate next
} arena;

/** Returns a newly initialized area with the given (initial) size. */
arena arena_init (size_t initial_size); 

/** Deallocates the memory within the given arena */
void arena_release (arena ar);

/** Clears the arena, allowing for the arena to be reused from scratch. */
void arena_clear (arena *ar);

/**
  * Allocates a `sz` byte chunk from the given arena, or returns `NULL`
  * if the allocation is not possible, e.g., because the arena has been
  * exhausted and it cannot resize.
  */
void* arena_alloc (arena *ar, size_t sz);

Implement this header in an implementation file called arena.c. In memory, an arena simply keeps track of several pointers into a heap-allocated chunk from which we carve allocations.

  ---------------------------
  |///////|                 |
  ---------------------------
  ∧       ∧                 ∧
  |       |                 |
 base    cur              bound

In the diagram above, the region of memory between the base and cur pointer has already been used for allocations, and the region between cur and bound is free.

To allocate a chunk of memory from this arena, we bump cur by the size of the requested chunk, returning a pointer to the previous cur's location:

  ---------------------------
  |///////|***|             |
  ---------------------------
  ∧       ^   ∧             ∧
  |       |   |             |
 base    ret cur          bound

In the diagram above, the region marked with *s is newly allocated. cur now points past the end of this chunk and arena_alloc would return ret, i.e., where cur was previously pointing.

If an allocation request would move cur past bound, then we cannot service the request with the current chunk. At this point, we can either return NULL, indicating that we failed to allocate memory. Or we can dynamically grow the underlying chunk with realloc, taking care to reestablish all three pointers in our arena in this new chunk.

After you are done implementing arena.c, take one of your previous programs that uses dynamic memory management and retrofit your code to use your arena allocator as a test.

CSC 161 Readings (Fall 2023)