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 k^th person until only one person remained. The survivor received some cupcakes.

In this example, k=3.

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

About 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:

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).

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

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.

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 }

Iterating through linked list with for loop

Where possible, prefer a for loop over a while.

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.

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.
       Free the head
       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

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.

14. What is the purpose of has_name(…) and is_names(…)?

    Those exist to help you test. See the next item (↓).

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.

Updates