Advanced C Programming

Spring 2023 ECE 264 :: Purdue University

Alchemy details (also sent last week)
Due 3/29

Priority queue

This homework will eventually be a part of a future sequence of assignments about data compression using a method called Huffman coding. The first step is to create a module for storing data. While we plan to use it for Huffman coding, this first part can stand on its own; it could be used for storing any kind of data.

You will use linked lists to implement a priority queue data structure and a stack data structure. Those are just linked lists with some rules about how elements are added and removed.

Learning goals

You should learn or practice how to:

  1. Create and manipulate linked lists.
  2. Avoid memory faults associated with linked lists.
  3. Use function addresses to make your data structures work with any type of values.

Getting Started

Get the starter code

Start by getting the files. Type 264get hw12 and then cd hw12 from bash. This will give you priority_queue.h (header file) and priority_queue.c skeleton implementation file.

We have also added in a demostration file, demo_priority_queue.c, which simply illustrates how the pieces fit together. Do not copy that code. However, you may test in your account, if you wish. (demo_priority_queue.c was added to the starter files the morning of Mon 3/30/2020.)

Copy in your Makefile, miniunit.h and log_macros.h from a previous homework.

you@ecegrid-thin1 ~ $ cd 264
you@ecegrid-thin1 ~ $ 264get hw12
This will write the following files: 1. hw12/demo_priority_queue.c 2. hw12/priority_queue.c 3. hw12/priority_queue.h Ok? (y/n)
you@ecegrid-thin1 ~/264/hw12 $ cp ../▒▒▒/{Makefile,miniunit.h,log_macros.h} ./

… where ▒▒ is the previous homework from which you want to copy your Makefile, miniunit.h, and log_macros.h.

The curly braces in the command above are just a shorthand. That will expand into three arguments. That command is equivalent to…
cp ../▒▒▒/Makefile ../▒▒▒/miniunit.h ../▒▒▒/log_macros.h ./

Don't forget the ./ at the end of the cp command!

Update your Makefile

The variables at the top of your file should contain the following:
ASG_NICKNAME HW12
SRC_C priority_queue.c
SRC_H priority_queue.h miniunit.h log_macros.h
TEST_C test_priority_queue.c
EXECUTABLE test_priority_queue

Adjust your submit rule to ensure than whenever you run make submit, the following command is executed:

264submit hw12 priority_queue.c priority_queue.h test_priority_queue.c miniunit.h log_macros.h Makefile
… but your rule should use the variables wherever possible (i.e., 264submit $(ASG_NICKNAME) $(SRC_C) $(SRC_H) $(TEST_C) Makefile))

Double-check your $(EXECUTABLE) rule. Running make or make test_priority_queue rule should result in the following command (but using your variables wherever possible):

gcc -o test_priority_queue -g -std=c11 -Wall -Wshadow -Wvla -Werror -pedantic priority_queue.c test_priority_queue.c

Overview

In this exercise, you will use a linked list to implement a priority queue or a stack.

A priority queue is implemented as a linked list where the objects stored in the list are actually ordered. For example, if we want to store a linked list of numbers 5, 10, 4, 3, 1, and the linked list is used to implement a priority queue, the linked list should appear as follows:

1→3→4→5→10→NULL

Here, we assume that "→" is a link to the next node in the list. We also assume that a smaller number has a higher priority, and it is therefore listed first. If we now want to get number 7 to join the priority queue, we should have the list updated to:

1→3→4→5→7→10→NULL

We call this the enqueue operation. To remove an item from a priority queue, we always remove the item with the highest priority. This is call the dequeue operation. In this case, a dequeue operation will remove 1 from the list:

3→4→5→7→10→NULL

When a stack is implemented as a linked list, the object that is pushed onto the stack always appears as the first item on the list. Therefore, if we push the list of numbers 5, 10, 4, 3, 1 onto a stack successively, we have the following linked list:

1→3→4→10→5→NULL

If we pop from the stack, we have

3→4→10→5→NULL
If we now push 7 onto the stack, we have
7→3→4→10→5→NULL
In both priority queue and stack, we always remove an item from the beginning of the list because that is the most convenient place to remove an item from a list.

You will also write a function to destroy a linked list and free all memory associated with it.

Generic data types

In previous assignments with linked lists, you always specified the type of data that would be stored. In this homework, the Node will contain a void* (memory address to any type). This allows you to use the same code for linked lists of any type.

This is simlar to the way that qsort(…) allows you to sort arrays of any type.

Function addresses

Code that deals with generic data types often needs to pass functions as parameters. However, the declarations are UGLY.

We will start with a couple examples.

Example #1: Declare local variable of type “address to function taking parameter types and returning return type

In the snippet below, we have two functions, _print_square(…) and _print_cube(…). Instead of calling them directly, we will assign the address of each function to a local variable and then call them by way of that local variable, just to demonstrate the syntax.

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

void _print_square(int n) {
    printf("%d² is %d\n", n, n*n);
}

void _print_cube(int n) {
    printf("%d³ is %d\n", n, n*n*n);
}

int main(int argc, char* argv[]) {

    // Declare variable «fn» of type "address to function taking an int and returning void"
    void (*fn)(int);

    // Initialize fn to the address of _print_square(…).  Normally we delcare and initialize
    // on the same line, but we have separated the two for the clarity of this explanation.
    fn = _print_square;

    // Call _print_square(…) by way of variable «fn».
    fn(7);

    // Now set «fn» to the address of _print_cube.
    fn = _print_cube;

    // Call _print_cube(…) by way of variable «fn».
    fn(7);

    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */

The type of variable fn is void(*)(int). In words, we will say, “«fn» is the address to a function taking an int and returning void.”

Example #2: Declare parameter of type “address to function taking parameter types and returning return type

Instead of creating a local variable, we can also use that same type (void(*fn)(int)) as a parameter to a function. In the example below, we call a function _call_print_fn(…) which then calls another function, specified by the second argument.

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

void _print_square(int n) {
    printf("%d² is %d\n", n, n*n);
}

void _print_cube(int n) {
    printf("%d³ is %d\n", n, n*n*n);
}

void _call_print_fn(int n, void (*print_fn)(int)) {
    print_fn(n);
}

int main(int argc, char* argv[]) {

    // Call _print_square(…) by way of the helper function.
    _call_print_fn(7, _print_square);

    // Call _print_cube(…) by way of the helper function.
    _call_print_fn(7, _print_cube);

    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */

Like the previous example, the type of parameter print_fn is void(*)(int). In words, we will say, “«print_fn» is the address to a function taking an int and returning void.”

Basic form for function address variables

The basic form for declaring a variable called Nameof type “address to function taking Parameter Types and returning Return Type” is:

Return Type(*Name)(Parameter Types)

Yes, it's UGLY. The name of that variable is in the middle!!!

Do not use parentheses when passing a function address or assigning it to a variable. In the code above, _call_print_fn(7, _print_cube(…)) will not work.

Passing a function address is totally different from invoking your mu_run(…) macro with a function (e.g., mu_run(_test_empty_list)). Although mu_run(…) looks like a function, it is really just transorming your code so that function can be called elsewhere and/or its name can be printed. In contrast, passing a function address is passing an actual address. It is a number that can be printed using printf(…), if you wish.

Use static in definitions of helper functions

Reminder: All internal helper functions must be declared as static in any assignment that involves compiling ≥2 files together. In addition, the name of internal functions must begin with an '_'. Exception: This is optional for test_▒▒▒(…) functions in a test_▒▒▒.c file. See the Code Quality Standard for more details on this.

void _know_your_worth() { ▒▒▒▒▒▒ } static void _know_your_worth() { ▒▒▒▒▒▒ }

That tells the compiler the function should only be available from the current file. Code in other files won't be able to call it.

Requirements

  1. Your submission must contain each of the following files, as specified:
    file contents
    priority_queue.c functions
    stack push(Node✶✶ a top, void✶ a value)
    return type: Node✶
    • *a_top stores the address of the first Node in the linked list.
    • a_value stores the address of the generic type.
    • The a_value field of the newly allocated Node should store a_value.
    • The newly allocated Node should become the first Node of the list, and *a_top should be updated. The function returns the address of the new Node.
    • Hint: You will call malloc(…) exactly once. You will not call free(…) in this function.
    stack pop(Node✶✶ stack))
    return type: Node✶
    Detach and return the head of the linked list.
    • Follow the specification for pq_dequeue(…); they do exactly the same thing.
    pq dequeue(Node✶✶ a head)
    return type: Node✶
    Detach and return the head of the linked list.
    • *a_head refers to the head (first node) of a valid linked list.
    • If the list is empty, return NULL (since there is nothing to dequeue).
    • Otherwise…
      • Detach the head of the list.
      • Return the detached head as a single-node linked list (i.e., size==1).
      • Set *a_head to the rest of the list (i.e., whatever came after the head, prior to detaching it).
      • The caller is responsible for freeing the detached node, and any memory it refers to.
        • Do not call malloc(…) or free(…) in this function.
    • Reminders:
      • A single-node linked list is just a node with its .next field set to NULL.
      • An empty linked list is represented simply as NULL. Thus…
        • If *a_head is initially NULL, that means the list is already empty.
        • If the list was initially a single-node list, then after detaching that node and returning, the list will be empty (i.e., *a_head set to NULL).
    pq enqueue(Node✶✶ a head, void✶ a value, int(✶cmp fn)(void const✶, void const✶)))
    return type: Node✶
    Add a new node with value a_value to a priority queue, using function cmp_fn(…) to determine the ordering of the priority queue.
    • *a_head refers to the head of the linked list.
    • a_value is the address of whatever value is associated with this node.
    • cmp_fn(void const* a_lhs, void const* a_rhs) is a comparison function used to determine where in the list the new node should be inserted.
      • cmp(a_lhs, a_rhs) should return a value less than 0 if the object at a_lhs is considered less than the object at a_rhs.
      • cmp(a_lhs, a_rhs) should return 0 if the object at a_lhs is considered equal to the object at a_rhs.
      • cmp(a_lhs, a_rhs) should return a value greater than 0 if the object at a_lhs is considered greater than the object at a_rhs.
    • The newly allocated Node should be inserted into the linked list such that…
      • All Nodes before the new Node in the list contain objects that are less than or equal to the new Node (according to cmp_fn(…)).
      • All Node's after the new Node in the list contain objects that are considered greater than the new Node (according to cmp_fn(…)).
    • Thus, if item A and item B are considered equal, and item A is inserted before item B is inserted, then when dequeing the items, item A will be returned (dequeued) before item B.
      • Example: Suppose you had a priority queue of strings with a compare function that did a case insensitive compare (e.g., "DANDELION" considered equal to "dandelion"), and you inserted "DANDELION" before "dandelion", then when dequeuing items, "DANDELION" would come before "dandelion".
    • *a_head should be updated if the new Node becomes the first item in the list. The function should return the address of the new Node.
    • Hint: You will call malloc(…) exactly once. Do not call free(…) in this function.
    destroy list(Node✶✶ a head, void (✶destroy fn)(void✶))
    return type: void
    • *a_head stores the address of the first Node in the list.
    • destroy_fn(…) is a function that deallocates *a_value, as needed.
    • Set the head to NULL in the caller's stack frame (i.e., *a_head = NULL;).
    test_priority_queue.c functions
    main(int argc, char✶ argv[])
    return type: int
    Test all of the required functions in your priority_queue.c.
    • 100% code coverage is required.
    • Use miniunit.h.
  2. Note: The names of parameters in the function definition do not need to match the declaration. Don't worry if you see a parameter listed as a_head in one place and a_top in another.
  3. Do not modify priority_queue.h.
  4. Submissions must meet the code quality standards and the course policies on homework and academic integrity.
    • Reminder: All helper functions in your priority_queue.c should be declared as static and have a name that begins with '_'. (See the Code Quality Standards.)

Examples of cmp_fn(…)

Here are some examples of cmp_fn(…) (for the pq_enqueue(…) function) and print_fn(…).

Comparing integers (int)

If we store the addresses of int (i.e., int*) as the addresses of the generic type (void*) in .a_value, we can use the following comparison function:
static int _compare_ints(void const* a_lhs, void const* a_rhs) {
    int const* a_lhs_int = a_lhs;  // Convert a_lhs from void* to int*
    int const* a_rhs_int = a_rhs;  // Convert a_rhs from void* to int*

    if(*a_lhs_int < *a_rhs_int) {
        return -1;
    }
    else if(*a_lhs_int == *a_rhs_int) {
        return 0;
    }
    else {
        assert(*a_lhs_int > *a_rhs_int);  // Requires #include <assert.h>
        return 1;
    }
}

Comparing strings (char*)

If we store the addresses of char (i.e., char*) as the addresses of the generic type (void*) in .a_value, and each address of char is actually the address of the first character of string, we can use the following comparison function:

static int _compare_strings(void const* a_lhs, void const* a_rhs) {
    return strcmp(a_lhs, a_rhs);
}

We can leverage the strcmp(…) standard library function, which compares two strings. It has the same semantics as our compare functions. It takes two strings (char*), and returns a number less than, equal to, or greater than zero, if the first string should be considered less than, equal to, or greater than the second string, for purposes of sorting order.

Submit

To submit HW12 from within your hw12 directory, type

make submit

That should result in the following command: 264submit HW12 priority_queue.c test_priority_queue.c miniunit.h log_macros.h Makefile priority_queue.h

Pre-tester

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

Q&A

  1. How much work is this?

    The instructor's solution (shown below) occupies 42 sloc (source lines of code, excluding comments and blank lines). We sometimes use the size of the "shortest defensible solution" as a rough (and certainly imperfect) measure of difficulty.

    👌 Okay to copy/adapt anything you find in the screenshot above (in this Q&A item). Granted there is almost nothing to copy, but you may find the comments helpful to steer you away from needlessly complicated approaches. There are many other completely correct ways to solve this.
  2. What is the hardest part?

    The pq_enqueue(…) function is the most difficult.
  3. Can I make this easier?

    Yes! Use TDD to test and build in lockstep. Write a test. Then, write just enough implementation code to pass that test (and any prior tests).
    Do not try to code it all at once. Start by getting it working for the simplest possible test. This is probably adding a single node (i.e., adding a node to an empty list). Test that it works before you move on. Next, get it working and tested for a list of size two, where the items are assumed to be added in descending order (so that no reordering is necessary). Get it working before you move on.
    Once you get into the longer test cases that require placing the new node in the right position in the list, you should draw pictures. Walk through how the connections need to change on paper before attempting to do it in code.
  4. How do the compare and destroy functions fit together with the rest of this code?

    Here's a code example.
    DO NOT COPY CODE FROM THIS FILE INTO YOUR OWN CODE. We are providing this only to clarify how the pieces are supposed to fit together. It would not be a good basis for your test_priority_queue.c. However, you may run this code in your account. It has been added to the starter code.
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "priority_queue.h"
    
    static int _cmp_strings_by_length(void const* a_lhs, void const* a_rhs) {
        size_t len_lhs = strlen(a_lhs); // No typecast needed!  Never use typedcast unless:
        size_t len_rhs = strlen(a_rhs); // (a) necessary, (b) safe, and (c) well-understood.
        return len_lhs - len_rhs; // shortest string comes forst
    }
    
    static void _destroy_string(void* string) {
        free(string);
    }
    
    static char* _copy_string(const char* src_string) {
        size_t num_chars = strlen(src_string);
        char* dst_string = malloc(sizeof(*dst_string) * (num_chars + 1));
        return strcpy(dst_string, src_string);
    }
    
    int main(int argc, char* argv[]) {
        // Create a priority queue of four strings, ordered by length (ascending).
        Node* head = NULL;  // size 0
        pq_enqueue(&head, _copy_string("Reginald"), _cmp_strings_by_length);  // size 1
        pq_enqueue(&head, _copy_string("was"),      _cmp_strings_by_length);  // size 2
        pq_enqueue(&head, _copy_string("a"),        _cmp_strings_by_length);  // size 3
        pq_enqueue(&head, _copy_string("hatter"),   _cmp_strings_by_length);  // size 4
    
        // Print contents of the list:  a was hatter Reginald
        for(Node* curr = head; curr != NULL; curr = curr -> next) {
            printf("%s\n", (char*)(curr -> a_value));
        }
    
        // Deallocate all memory used by the list, including each node's payload.
        destroy_list(&head, _destroy_string);
    
        return EXIT_SUCCESS;
    }
    
    /* ______
     * Output
     * ‾‾‾‾‾‾
     * a
     * was
     * hatter
     * Reginald
     */
    
    /* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
    

Updates

Updates may be posted here.