Spring 2021 ECE 264 :: Purdue University

⚠ This is a PAST SEMESTER (Spring 2021).
Due 5/8

Who Gets The Cake

Learning goals

You will learn:

1. Use linked lists (a dynamic data structure) to store data in memory.

Overview

On the first day of class, we played a game called Who gets the cake? Several people came to the front of the class. We counted off by some fixed number (k), eliminating every kth person until only one person remained. The survivor received some cupcakes.

In this example, k=3.

Round 1
Round 2
Round 3
Round 4
Round 4
Round 4

In EC01, you will create a simulation to find the winner for any set of names. To do this, you will use linked lists.

Linked lists let you store sequences of data (e.g., strings, ints, etc.). Like arrays on the heap, you can specify the size at runtime (i.e., as the program is running). The main advantage of linked lists over arrays is that you can add and remove items from the middle.

In class, you probably saw linear linked lists, that look like this:

head tail ▼ ▼ ┌───┐ ┌───┐ ┌───┐ │ 5 ├──»┤ 6 ├──»┤ 7 ├»─NULL └───┘ └───┘ └───┘

For this homework, you will use a different kind of linked list, called a circular linked list. A circular linked list can be thought of as a linear linked list with the tail linked to the head (i.e., `tail->next = head`).

head tail ▼ ▼ ┌───┐ ┌───┐ ┌───┐ ┌»┤ 5 ├──»┤ 6 ├──»┤ 7 ├»┐ │ └───┘ └───┘ └───┘ │ └───────────────────────┘

In practice, you don't need to keep track of any `head` or `tail` most of the time.

node ▼ ┌───┐ ┌───┐ ┌───┐ ┌»┤ 5 ├──»┤ 6 ├──»┤ 7 ├»┐ │ └───┘ └───┘ └───┘ │ └───────────────────────┘

Syntax

Some of the syntax in the homework may differ from what you have seen online or even in lecture.

Basic struct syntax.

There are 2-3 ways people define struct type definitions in C. See your reference sheet for examples of all of them. We are starting with the most basic. This is how the C language was designed to be used. The example below is for a point class. (This is intended only to illustrate the syntax, and is not directly related to EC01.)

```struct Point {
int x;
int y;
};
```

The type name is `struct Point`, not `Point`. To declare a variable with this type, you would use `struct Point p = { .x=5, .y=6 };` A function that returns this type would be declared as `struct Point getPoint(…) { … }`.

In future assignments, we will use the more concise syntax which uses `typedef`. That is essentially just an abbreviation for what we are doing here. It is more commonly used, but learning and using the basic syntax first will help you understand the `typedef` syntax much better when we start using that.

Named initializers.

When initializing a struct, use the named initializer syntax wherever possible. This is required by the Code Quality Standards.

 NEW (preferred) OLD struct Point p = { .x=5, .y=6 }; struct Point p; p.x = 5; p.y = 6;

Compound literals

The compound literal allows us to refer to an entire struct object at once as easily as you would refer to an integer. You can pass it to a function, return it to a function, or assign it to a variable—without ever giving it a name.

The basic form for struct objects is `(Type) { .field=value, .field=value }`

 NEW OLD doSomething((struct Point) {.x=5, .y=6}); struct Point p = {.x=5, .y=6}; doSomething(p); return (struct Point) {.x=5, .y=6}; struct Point p = {.x=5, .y=6}; return p; struct Point* a_p = malloc(sizeof(*a_p)); *a_p = (struct Point) { .x=5, .y=6 }; struct Point* a_p = malloc(sizeof(*a_p)); a_p -> x = 5; a_p -> y = 6;

Iterating through linked list with `for` loop

Where possible, prefer a `for` loop over a `while`.

 NEW OLD for(struct Node* curr=head; curr != NULL; curr=curr->next) { … } struct Node* curr = head while(curr != NULL) { … curr = curr -> next; }

size_t

`size_t` is a built-in C type that can hold unsigned integers. It is widely used to hold the number of object (e.g., number of words, number of bytes, etc.) or the size of an object (i.e., number of bytes required to store the object).

const

When a variable or parameter is declared as const, it cannot be modified. For example, in the following example, n may not be modified.

const int n = 5; n = 6; // COMPILER ERROR
Further, an address variable declared as const cannot be assigned to a variable that was not declared as `const`.
int n = 5; const int* a_n = &n; int* a_z = a_n; // COMPILER ERROR: "initialization discards ‘const’ qualifier" *a_z = 6; // This would be equivalent to *a_n = 6, which is not allowed.

We use this as a safety check to be sure that a function does not accidentally modify data when the function should only be reading it. For example, the `print_list(…)` function should read the values from the list, but should NOT modify anything about the list.

Warm-up exercises

This assignment includes a warm-up exercise to help you get ready. This accounts for 20% of your score for EC01. Scoring will be relatively light, but the usual base requirements apply.

1. `struct Rectangle create_rectangle_stack(int height, int width)`
Return a `struct Rectangle` object with the given dimensions. You create the struct type at the top of your warmup.c file. It should have two fields, called `.height` and `.width` (both `int`).
The body of the `create_rectangle_stack(…)` function must comprise just one line.
• Line 1: compound literal, like this: `return (Type) { .Field=Value, .Field=Value };`.
2. `create_rectangle_heap(int height, int width)`
Do like `create_rectangle_stack(…)`, but create it on the heap using `malloc(…)`. Return a `struct Rectangle*`.
The body of the `create_rectangle_heap(…)` function must comprise only three lines.
• Line 1: Declare and initialize using `malloc(…)`, like this: `StructType* Name = malloc(sizeof(*Name));`
• Line 2: Assign all fields using a compound literal, like this: `*Name = (StructType) { .Field=Value, .Field=Value };`
• Line 3: Return that object to the caller, like this: `return Name;`.
3. `destroy_rectangle(struct Rectangle* a_rectangle)`
Free the rectangle.
The body of this function should be just one line.
4. `print_rectangle(struct Rectangle rect)`
Print the rectangle using asterisks. Example: Calling `print_rectangle(create_rectangle_stack(2, 6))` should print the equivalent of `printf("******\n******\n");`, like this:
```****** ******```
5. `create_limerick(const char* lines[5])`
Create a linear linked list of five strings. These could be lines in a limerick (examples). Return a `struct LimerickNode*`.
This can be implemented in 9 lines while respecting the Code Quality Standards, but you may use more if you wish.
6. `print_limerick(struct LimerickNode* head)`
Print each line of the limerick (given as a linear linked list) followed by a newline (`'\n'`) after each line.
The body of this function must comprise only 3 lines. Use a `for` loop to iterate over the array, like this:
```for(StructType* curr = head; curr != NULL; curr = curr -> next) { ▒▒▒▒▒▒▒▒▒▒ }```
7. `destroy_limerick(struct LimerickNode* head)`
Detach and free every node of a linear linked list.
The body of this function should be only 5 lines. The basic procedure is to detach and free the head, repeatedly, until the list is empty. Here is an outline.
```while(list is not empty) {
Store the address of the second node (after head) in a temporary variable.
The second node that we saved becomes the new head.
}
```
8. `main(…)`
A `main(…)` function is included. You may modify it however you like—or not.
• Optional: Change the limerick to something else.

A skeleton warmup.c is included with the starter files, which you can obtain by typing `264get EC01`.

Opt out.

In a hurry, and don't need the practice? This warm-up is here to help you learn what you need to succeed on the rest of this assignment—not to add additional work. Therefore, we give you an option. Those who feel that they do not need the practice may "opt out". by modifying warmup.c so that it does nothing but print the following message exactly and then exit:

`I already know this and do not need to practice.`

If you do that, then your score for EC01 will be based solely on the rest of this assignment. If you leave the warmup.c undone, if you do not turn in a warmup.c, or if the message it prints does not match perfectly, then you will receive 0 for the warmup portion of this assignment (20%).

Requirements

1. Your submission must contain each of the following files, as specified:
file contents
cake.c functions
`choose winner(struct Node✶✶ a node, int n)`
return type: void
Remove nth node starting at `*a_node` repeatedly until just one node remains.
• This will modify the list.
• When `choose_winner(…)` returns, the list should contain only one node (the winner).
• In other words, `*a_node` should be the winner, and should be a circular list of size=1.
• If `*a_node` is `NULL`, then do nothing.
• Do not copy the strings (e.g., using `strdup(…)`.
• All nodes that are removed must be freed by this function.
• You may assume `n ≥ 1`.
`create list(const char✶ first name, ...)`
return type: struct Node✶
Create a circular linked list of `struct Node` objects.
• Names will be passed to `create_list(…)` as arguments.
• `create_list(…)` is a variadic function taking any number (≥0) of names as arguments
• Caller must pass `NULL` as the last argument to `create_list(…)`, to signify the end of THE Argument list.
• Do not create a list node for `NULL`.
• Do not copy the string using my_strdup(...) or anything else. malloc(..) should be called once per list node (i.e., once per name)..
• Example #1:    `struct Node* node = create_list("Avery", "Bob", "Chris", NULL);`
… should create a list with three nodes, like this:
Return address to this node │ ▼ ┌───────┐ ┌─────┐ ┌───────┐ ┌─»┤"Avery"├──»┤"Bob"├──»┤"Chris"├»─┐ │ └───────┘ └─────┘ └───────┘ │ └───────────────────────────────────┘
• Example #2:    `struct Node* node = create_list("Avery", NULL);`
… should create a list with one node (size=1), like this:
Return address to this node │ ▼ ┌───────┐ ┌─»┤"Avery"├»─┐ │ └───────┘ │ └─────────────┘
• Example #3:    `struct Node* node = create_list(NULL);` … should return `NULL` (empty list).
`has name(const struct Node✶ node, const char✶ name)`
Return `true` if and only if the list containing `node` includes a node having a string that matches `name`.
• Use `strcmp(…)` to compare the strings.
• If the list is empty (`node` is `NULL`), then return `false`.
• `name` is a non-empty string.
`count nodes(const struct Node✶ node)`
Return the number of nodes in the list containing `node`.
• If the list is empty (`node` is `NULL`), then return 0.
`is names(const struct Node✶ start node, size t num names, const char✶✶ names)`
Return `true` if and only if the given circular list contains nodes with strings that match every string in `names`.
• Use `strcmp(…)` to compare the strings.
• `names` is an array of ≥1 non-empty strings.
• `num_names` is the number of strings in `names`.
• If the list is empty (`node` is `NULL`), then return `false`.
• `names` does not end with `NULL`.
• This should match the nodes in order.
Example:
start_node ▽ ┌["Al"]─["Bo"]─["Cy"]┐ └────────────────────┘
• `is_names(start_node, 3, (char*[]) {"Al", "Bo", "Cy"})` should return true.
• `is_names(start_node, 4, (char*[]) {"Al", "Bo", "Cy", "Cy"})` should return false.
• `is_names(start_node, 2, (char*[]) {"Al", "Bo"})` should return false.
• `is_names(start_node, 2, (char*[]) {"Al", "Cy"})` should return false.
• `is_names(start_node, 3, (char*[]) {"Bo", "Cy", "Al"})` should return false.
`destroy list(struct Node✶✶ a node)`
return type: void
Detach and `free(…)` every node in the circular linked list containing `*a_node`.
• You must `free(…)` every node.
• `a_node` will not be `NULL`.
• `*a_node` might be `NULL`, if the list is empty.
`get nth node(struct Node✶ start node, int n)`
return type: struct Node✶
Return the nth node in a circular linked list, starting with start_node.
• `get_nth_node(node, 0)` should return `start_node`.
• `get_nth_node(node, 1)` should return `start_node -> next`.
• `get_nth_node(node, 2)` should return `start_node -> next -> next`.
• … and so on
• If `start_node` is `NULL`, then return `NULL` for any value of `n`.
• You may assume `n` ≥ 0.
`detach next node(struct Node✶✶ a node)`
return type: struct Node✶
Detach and return `(*a_node) -> next`.
• `*a_node` is the address of a node in a circular linked list.
• The returned node should be a circular list of size 1. (Its `->next` field should refer to itself.)
• If the given list was empty (i.e., `*a_node == NULL`), then return `NULL`.
• If the given list contains only one node (i.e., `(*a_node)->next == *a_node`), then set `*a_node` to a list of size 0 (i.e., `*a_node = NULL` and return the detached node.
• Otherwise, if `detach_next_node(…)` was called with an `*a_node` in a list of size n, then upon return, `*a_node` should be in a list of size n-1.
• Do not call free(…).
`print list(const struct Node✶ start node)`
return type: void
Print the circular linked list beginning with `start_node` in the format illustrated below.
• Examples:  1 node = create_list("Avery", "Bob", "Chris", NULL); print_list(node); ```┌["Avery"]─["Bob"]─["Chris"]┐ └───────────────────────────┘``` 2 node = create_list("Avery", NULL); print_list(node); ```┌["Avery"]┐ └─────────┘``` 3 print_list(NULL); `EMPTY`
• Format: First line consists of `'┌'` + `.name` field of each node wrapped in `["▒▒▒"]` and separated by horizontal lines (`'─'`) + `'┐'` + `'\n'`.  Second line consists of `'└'` + many horizontal lines `('─')` + `'┘'` + `\n`, using enough horizontal lines so the width is the same as the first line.
• A horizontal line (“─”) character is not the same as a hyphen (“-”), en dash (“–”), or em dash (“—”).
• If you are not using Vim, be sure your editor saves with UTF-8 encoding.
• A separate code file, print_array_like_circular_list.c is included to illustrate the format. You may copy/adapt any of that code if you understand it and think it will reduce your work.
• If the list is empty (`start_node == NULL`), print `EMPTY` and a newline (`\n`).
• Do not ⓐ call `malloc(…)`, ⓑ call `free(…)`, or ⓒ modify the list.
test_cake.c functions
`main(int argc, char✶ argv[])`
return type: int
• This should consist primarily of calls to `mu_run(_test_▒▒▒)`.
• You will also need some calls to `print_list(…)` in `main(…)` and/or `_test_▒▒▒(…)` functions.
• 100% code coverage is required.
` test ▒▒▒()`
return type: int
• Use your `mu_check(…)` to check that every required function in your cake.c works correctly.
• Split your tests into at least 5 `_test_▒▒▒(…)` functions
warmup.c functions As specified above.
miniunit.h macros
from miniunit
clog.h macros
from miniunit
2. Only the following externally defined functions/constants/macros are allowed.
stdio.h `printf`, `fputc` `cake.c`, `test_cake.c`, `warmup.c`
stdlib.h `malloc`, `free`, `EXIT_SUCCESS`, `EXIT_FAILURE` `cake.c`, `test_cake.c`, `warmup.c`
stdarg.h `va_start`, `va_arg`, `va_end` `cake.c`
string.h `strcmp`, `strlen` `cake.c`, `test_cake.c`, `warmup.c`
stdbool.h `bool`, `true`, `false` `cake.c`, `test_cake.c`, `warmup.c`
assert.h `assert` `cake.c`, `test_cake.c`, `warmup.c`
miniunit.h `anything` `test_cake.c`, `warmup.c`
clog.h `anything` `cake.c`, `test_cake.c`, `warmup.c`
Feel free to ask if there is something else you would like to use.
3. Do not modify cake.h.
4. Submissions must meet the code quality standards and other course policies on homework.

Submit

To submit EC01 from within your ec01 directory, type `264submit EC01 cake.c test_cake.c warmup.c miniunit.h clog.h Makefile`

Pre-tester ●

The pre-tester for EC01 has been released and is ready to use.

Q&A

1. What is `size_t`?

size_t is a built-in type for an unsigned integer. It is used in C programming in cases where you are referring to the number of objects (e.g., size of an array, number of nodes, number of characters in a string, etc.), or the size of an object (i.e., number of bytes required to store one). It is guaranteed to be large enough to hold the size of any object on the system.
Many standard functions return `size_t` (e.g., `strlen(…)`) or take parameters of type `size_t` (e.g., `malloc(…)`).
2. What is `assert(…)`?

`assert(condition)` is a function-like macro that ensures that some condition is always true. If condition is false, your program stops immediately with an error message telling you what went wrong and where.
If there is something that you expect to be always true—unless your program had a bug—then adding an `assert(…)` documents that assumption in a way that ensures it must be true.
Think of an `assert(…)` like a comment that cannot lie. For example, at the end of `destroy_list(…)`, you could add a comment like `// *a_head must be NULL upon return`, but if the code had a bug, that might not actually be true. In that case, the comment could even be misleading! A call to `assert(…)` (often called an assertion) serves a similar purpose as such a comment, but when you read the code, you can be sure that the condition must always be true, or else the program would have crashed.
3. What's the difference between `assert(…)` and `mu_check(…)`?

They both check that a condition is true. However, `mu_check(…)` is designed to be used only in your test code (e.g., test_cake.c), while `assert(…)` can be anywhere, but is especially useful right in your implementation code (e.g., cake.c). Also, `assert(…)` stops your program immediately if the condition is false, while `mu_check(…)` allows the program to proceed.
4. Won't this slow down the program?

Probably not, and even if it did, it wouldn't matter. If you do `assert(do_something_slow())`, the program will indeed run slower. However, all calls to `assert(…)` are disabled whenever the program is compiled with `-DNDEBUG`. (That is `-DNDEBUG`, not `-DDEBUG`.) When score your code, we use `-DNDEBUG`.
5. Can I add my own assertions (calls to `assert(…)`)?

Yes. In fact, you should! Be sure to follow a few guidelines:
• ✔ Use only to check things that must always be true (unless your program has a bug).
• ✔ Use to check range or appropriateness of return value.
• ✔ Use to check range or appropriateness of intermediate values in a calculation within your function.
• ✔ Use to check conditions that should always be true when entering a loop body or helper function.
• ✔ Use to check range or appropriateness of arguments to helper functions (i.e., name starts with “_”).
• ✘ Do not use to check external conditions.
• ✘ Do not use to check if a file exists or contains what you expect.
• ✘ Do not use to check range or appropriateness of arguments to public (non-helper) functions. `assert(…)` is only for checking if your code has bugs (coding mistakes).
• ✘ Do not use `assert(…)` to check return value of `malloc(…)` (i.e., do not write `assert(malloc(…))`).
6. Why does `detach_next_node(…)` say to not free the node?

This helps you test your code. You can build up a list using `create_node(…)`, do some operations on it, and then use `detach_next_node(…)` to gradually take it apart, verifying the contents of each node as you go.
If we freed the node, then we couldn't return it, and thus we couldn't inspect it.
In addition, detach is a common operation on linked lists. It allows you to split nodes and recombine them, something you will be doing in sorts.
7. GCC error: “incompatible types when assigning to type ‘struct ▒▒▒ *’ from type ‘struct ▒▒▒’”

You tried to set a variable to something that doesn't match its type.
You tried to assign to a variable of type `struct Node *`, but the thing on the rhs (right-hand side) is of type `struct Node`. Here's an example:
```struct Node* new_node = malloc(sizeof(*new_node));
struct Node other_node = { .value = 5, .next = NULL };
new_node = other_node;  // BAD!!!  lhs is struct Node* but rhs is struct Node.
```
“assigning to type ‘struct Node *’” refers to the lhs (`new_node`) which is of type `struct Node*`.
“from type ‘struct Node’” refers to the rhs. `other_node` is type `struct Node`.
Here is another way you could get that error.
```struct Node* new_node = malloc(sizeof(*node));
new_node = (struct Node) { .value = 5, .next = NULL };
```
Either way, we get the error because the lhs (left-hand side) has a type that doesn't match the rhs (right-hand side).
8. GCC error: “attempting to modify memory at address ▒▒▒”

This probably means you tried to write a value to an address that was marked as `const`.
Marking a parameter or variable as `const` is like a promise that you will not modify it. If it is an address variable (i.e., `const ▒▒▒*`), then it is a promise not to modify the memory at that address.
In this example, `node` is declared as `const struct Node*`, which means we promise not to write to the memory at address node. The line `node -> value = 999;` tries to write to the `.value` field of the `struct Node` object at that address, so GCC steps in to keep us from breaking the promise.
```void print_node_value(const struct Node* node) {  // not part of EC01
node -> value = 999;  // BAD!!!
}
```
9. GCC error: “initialization discards ‘const’ qualifier from …”

You probably tried to assign a const address variable to a non-const variable.
Example:
```void print_int_by_address(const int* a_n) {
printf("%d\n", *a_n);  // proper behavior of this function

// *a_n = 999;  // This would not be allowed since a_n is declared as const int*

// Someone might try to get around that by assigning to a non-const variable.
int* a_workaround = a_n; // BAD!!!
*a_workaround = 999;
}
```
To prevent the workaround shown above, you cannot assign a `const` address variable to a non-const address variable.
In the EC01 warmup, this may happen if the `.value` (or `.line` or whatever) field of your `struct LimerickNode` is declared as `char*`. It needs to be `const char*` because the parameter to `create_limerick(…)` is of type `const char*`.
Parameters are set as `const` to avoid bugs that result from accidentally modifying a parameter in a function that has absolutely no need to modify it.
10. GCC error: “assignment to expression with array type”

You cannot assign to a variable that was declared as an array (i.e., `▒▒▒[]`).
```int a[5] = {2, 3, 4, 5, 6};
int b[5] = {5, 6, 7, 8, 9};
b = a;
```
We get the error because the lhs (left-hand side) of the assignment (`b`) is of type `int[5]`. You may not assign to an array. Assigning to one element would be okay.
11. Why does `print_list(…)` take a `const struct Node*`?

Printing a list should not require making any modification to the nodes. This warns you if you are making a mistake.
12. Why are the parameters to `is_names(…)` of type `const char*`?

There is no need to modify the strings to compare them with a list. This warns you if you are doing something very wrong.
13. I got a segmentation fault. What should I do?

A segmentation fault happens when you attempt to write (or read) memory in a segment where you are not allowed to write (or read). Most often, this happens when you try to write or read to/from the `NULL` address. That address does not allow writing or reading.
Run the code in GDB. When it crashes, type `info locals` to see the values of every local variable. Look at the line of code that caused the problem. At some point, you were almost certainly either:
• writing to the data segment, by trying to write over a string initialized by a string literal.
`char* s = "abc"; s[0] = 'z';`
• writing the the NULL address (or other improper location in memory)
`char* s = NULL; s[0] = 'z';`
• reading from the the NULL address (or other improper location in memory)
`char* s = NULL; printf("%c\n", s[0]);`
You should know all of the GDB commands from memory by now. If you're not there, yet, take the time to learn them as soon as you can. You will need GDB for the duration of the semester. GDB is not going away.
It is best to give yourself some dedicated time—independent of the time you spend on the current homework—to go through each GDB command. HW03 was supposed to give you that opportunity.

15. How can I use `mu_check(…)` to test this code?

Here's a brief example.
```// Create a list of size 3.
struct Node* list = create_list("Al", "Bo", "Cy", NULL);

// Check the contents of the list against an array.
mu_check(is_names(list, 3, (const char*[]) {"Al", "Bo", "Cy"}));

// Detach the second node and free it.
struct Node* bo_node = detach_next_node(&list);
destroy_list(&bo_node);
mu_check(bo_node == NULL);

// Verify that the node is no longer in the list.
mu_check(!has_name(list, "Bo"));

// Verify that the list contains everything except the detached node.
mu_check(is_names(list, 2, (const char*[]) {"Al", "Cy"}));

// Destroy list so we can start over.
destroy_list(&list);
mu_check(list == NULL);

// Create the same list again.
struct Node* list = create_list("Al", "Bo", "Cy", NULL);

// Choose winner.
choose_winner(&list, 3);
mu_check(strcmp(list -> name, "Bo") == 0);
destroy_list(&list);
mu_check(list == NULL);
```
👌 Okay to copy/adapt the snippets in this Q&A item.
16. Can I test `print_list(…)` using `mu_check(…)`?

No. You can use an expected.txt and diff testing for that.
17. Do I need to submit an expected.txt (or similar)?

It might be helpful, but it is not required.
18. What does “stub mean”?

To make the starter files compile before you are finished, we add in a dummy `return` statement. When you are ready to implement a function, simply delete that dummy `return` statement and write the function normally.

 2/28/2020 Released Enhanced warmup. Added a section about syntax. 3/1/2020 Corrected syntax section to use the “basic” struct syntax (almost) everywhere. Corrected parameter order of `create_rectangle_stack(…)` and `create_rectangle_heap(…)` to be consistent with the function signatures in the starter code (warmup.c). For scoring, we will accept either order (either by inspecting your code or by testing only with squares). Corrected a few other minor typos. 3/3/2020 `is_names(…)` takes a `const char**` as the last argument. 3/5/2020 In Q&A #15, compound literal should have type `const char*[]`.