Advanced C Programming

Spring 2020 ECE 264 :: Purdue University

⚠ This is a PAST SEMESTER (Spring 2020).
Due 3/5

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 HW07, 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:

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

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

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 HW07 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.
      • This was clarified 3/3/2020. If you had finished this with a different interpretation, please send Prof. Quinn email with subject “HW07 is_names(…) ambiguity - ECE 264”.
    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:
    • 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 HW05
    clog.h macros
    from HW05
  2. Only the following externally defined functions/constants/macros are allowed.
    header functions/symbols allowed in…
    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 HW07 from within your hw07 directory, type 264submit HW07 cake.c test_cake.c warmup.c miniunit.h clog.h Makefile

Pre-tester

The pre-tester for HW07 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 HW07
        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 HW07 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

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*[].