Lab 3: Dynamic Memory & Priority Queue

You will complete three problems on a worksheet, followed by an implementation of a priority queue. Please attend the section you are registered for to receive your lab checkoff.

For this week’s lab work, there are three files:

In the first part of the lab, you will review basic concepts of C memory management, completing the three worksheet problems to reinforce your understanding as you go along.

In the second half of the lab, you’ll build a priority queue that accepts a “generic” data type (more details in the supplementary material). This is accomplished by storing a pointer to an arbitrary piece of memory that can store anything by using void*. We’ve defined the PQNode type as well as the function declarations for the functions you are required to implement in lab3.c:

PQNode *pq_enqueue(PQNode **a_head, void *a_value, int (*cmp_fn)(const void *, const void *)) : Add a new node with a_value to the priority queue located at a_head using the function cmp_fn to determine the ordering of the priority queue.
PQNode *pq_dequeue(PQNode **a_head) : Detach the head of the priority queue located at a_head and return it.
PQNode *stack_push(PQNode **stack, void *a_value): Add a new node with value a_value to the top of the stack located at stack.
PQNode *stack_pop(PQNode **stack): Remove the top node from the stack located at stack and return it.
void destroy_list(PQNode **a_head): Deallocate all nodes in the linked list starting at a_head. Of these, the trickiest one is probably destroy_list, in which you must deallocate an entire linked list. Don’t forget to also deallocate each list node’s value!

lab3.c has detailed comments to help you with the implementation. Here is the implementation overview for each function:

pq_enqueue:
- Correctly initialize a new node (by setting next to NULL).
- Correctly implement list traversal.
- Find the right spot to insert the node in the PQueue—right spot is between some adjacent nodes a and b such that a’s priority is lower than the node being inserted and b’s priority is greater than the node being inserted.
- Understand that idea of passing function cmp_fn as a parameter.
- Edge case 1: when there is no a? insert the new node at the head.
- Edge case 2: when there is no b? insert the new node after the last node (or at the tail).
- Special case: cmp_fn = NULL should be used to insert the new node at the head of the queue, i.e., in the increasing order of recency.
pq_dequeue:
- Edge case 1: when the PQueue is empty, there is no update.
- After deleting a node, remember to update the new head of the PQueue.
stack_push:
- since pushing to the top of the stack is analogous to enqueueing in the increasing order of recency, pass appropriate cmp_fn to pq_enqueue.
stack_pop: is same as pq_dequeue
destroy_list:
- Remember to free the a_value and the node itself.

You can test your code with an invocation of our container and only two lines:

    rv gcc -Wall -Wpedantic -Wshadow -std=c17 -o test_lab3 lab3.c
    rv qemu test_lab3

We have provided more details about priority queue and generic datatypes in the following section.

Supplemetary Material

Generic data types

You might notice some strange looking syntax in the function declarations in lab3.c. This is to enable generic data types. The PQNode struct contains a void*, which you can think of as a memory address to any type. This allows you to use the same code for linked lists of any type.

You can assign a void* to an address of any type. This is why you can write code like:

char* s = malloc(...);

even though malloc(...) returns a void*, not a char*. This is also similar to the way functions such as qsort(...) allow you to sort arrays of any type. Just to reiterate, this is just an example - you will be using malloc(...) instead in the assignment.

Function addresses

Code that deals with generic data types often needs to pass functions as parameters. To do this, you need to specify the address to a function as an argument. In other words, you are declaring the parameter of the function (in this case cmp_fn) as the address to a function that takes in some parameter(s) of specified types and returns a value of a specified type. For the compare function, you’ll always return an integer, and the arguments to the compare function can be anything, depending on the underlying data in the nodes of the priority queue.

Let’s look at an example:

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

void _print_cube(int n) {
    printf("%d cubed 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_fn(4, _print_square); // Prints 16
    _call_print_fn(4, _print_cube); // Prints 64
}

In the above code, the type of parameter print_fn is void(*)(int). In other words, print_fn is the address to a function taking an int and returning void. Generalizing this to our priority queue, notice that the type of parameter cmp_fn is int(*)(const void*, const void*). This is the address to a function taking two addresses to memory locations of any type and returning an int.

Implementing `pq_enqueue`

You might recall from CS 2110 that priority queues can be implemented with binary heaps. In our implementation, however, we will be implementing our priority queue as a linked list that we will keep sorted by priority. This means that inserting a node will be an \(O(n)\) time operation, and removing from the priority queue will be a constant time operation. This is fine for our purposes.

In pq_enqueue, *a_head refers to the head of the linked list. If *a_head is NULL, then the list is empty. a_value is the address of whatever value is associated with this node. Allocate a new PQNode and insert it into the list in sorted order, according to the cmp_fn function. Since cmp_fn(...) is a black box right now, here is how you will interpret its output. If cmp_fn(a, b) < 0, then a is ordered before b (or a is less than b, in a sense), else otherwise. That is, everything before the new PQNode should be less than the new one, and everything to the right should be bigger than (or equal to) the new one.

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

This function should call malloc exactly once. You should not call free in this function.

Implementing `pq_dequeue`

Like the previous function, *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). Upon return, *a_head must be a valid linked list (although possibly empty). For our purposes, NULL is a valid linked list of size 0. Thus, *a_head will be set to NULL if the list is empty, and upon removing the last node, you should set *a_head to NULL.

You must also set the next field of the removed node to NULL. The caller is responsible for freeing the detached node, and any memory it refers to. For this reason, this function should not call free, directly or indirectly.

Implementing `destroy_list`

This function should completely destroy the linked list referred to by *a_head, freeing any memory that was allocated for it. This function should set the head to NULL in the caller’s stack frame (i.e. *a_head = NULL).

CS 3410 Spring 2026