Skip to content

HW4 - Thread-Safe Doubly-Linked Playlist

Due Date: August 5th 2026, 05:00 PM

In this final assignment you'll build a playlist as a doubly-linked list of songs that is kept sorted, and then make it safe for several threads to share at once. It pulls together the back half of the course:

  • linked lists (Lecture 9): a list of heap nodes you splice together by pointer, now doubly-linked so each node knows both its next and its prev,
  • function pointers (Lecture 11): the playlist is kept in order by a comparator you hand it at creation time, exactly the way we made the hash table pick its hash function, and
  • threads and mutexes (Lectures 11 and 12): several threads add and remove songs from one shared playlist, and a single mutex per playlist keeps the concurrent pointer surgery from corrupting the list.

A pre-written main.c runs a small "listening party": several listener threads add songs to one shared playlist at the same time, and then the final playlist is printed in order.

  • Starter code: hw4/ - implement your code in playlist.c.
  • Language standard / flags: clang -Wall -Wextra -Werror -std=c17 -pthread
  • Submission: see Submitting below.

Getting Started

You already created your homework repository for the earlier assignments, so there is no new setup. Pull the HW4 starter files from the upstream repository:

$ cd cmsc14300-sum-2026/homework-GITHUB_USERNAME
$ git pull upstream main

This adds an hw4/ directory alongside your earlier work. If git pull upstream main reports a merge or a conflict, do not force anything - post on Ed and we will help.

Background

A song is a doubly-linked node

Recall the linked list from Lecture 9: each node held a value and a next pointer to the following node. A doubly-linked list adds a second pointer, prev, back to the node before it, so the list can be walked in either direction. Each song also owns a heap copy of its title, the way a struct owned a heap string in Lecture 7:

typedef struct song {
    char        *title;     /* heap-owned copy of the title */
    int          duration;  /* length in seconds */
    struct song *prev;      /* the song before this one (NULL at the head) */
    struct song *next;      /* the song after this one  (NULL at the tail) */
} song_t;

A single node holds its data between the two links that chain it to its neighbours:

          +-------------------------------+
          |            song_t             |
          +-------------------------------+
          |  char *title   (heap pointer) |
          |  int   duration               |
          +---------------+---------------+
  prev <--| song_t *prev  | song_t *next  |--> next
 (or NULL)+---------------+---------------+ (or NULL)

Strung together, three nodes look like this, with the playlist holding both ends:

    head                                tail
     |                                   |
     v                                   v
  +--------+       +--------+       +--------+
  |  prev  |<------|  prev  |<------|  prev  |
  |  NULL  |       |        |       |        |
  +--------+       +--------+       +--------+
  |  next  |------>|  next  |------>|  next  |
  |        |       |        |       |  NULL  |
  +--------+       +--------+       +--------+

The playlist keeps a pointer to both ends and a running count:

typedef struct playlist {
    song_t         *head;   /* first song in order, NULL if empty */
    song_t         *tail;   /* last song in order,  NULL if empty */
    int             size;
    song_cmp_t      cmp;    /* the order this playlist is kept in */
    pthread_mutex_t lock;   /* one mutex per playlist (Part 3) */
} playlist_t;

Inserting and removing are the usual pointer surgery, but with two links to keep straight instead of one. When you splice a node in or cut a node out, fix the next of the node before it and the prev of the node after it, and update head or tail when you touch either end. Drawing the four cases (empty list, insert at the head, in the middle, at the tail) on paper first is well worth it.

Kept sorted by a comparator you are given

Rather than hardcode one order, the playlist stores a comparator function pointer and calls it on every insert. This is the same move as Lecture 11's customizable hash table: the list's logic (walk, splice, count) is separate from the order it is kept in, and the two vary independently.

typedef int (*song_cmp_t)(const song_t *a, const song_t *b);

A comparator returns a negative number if a should come before b, a positive number if it should come after, and 0 if they order equally - the same convention as strcmp. playlist_create takes one and stores it; playlist_insert walks from the head and puts the new song before the first song s for which cmp(new, s) < 0, so songs that compare equal keep their insertion order. Hand the list a by-title comparator and it stays alphabetical; hand it a by-duration comparator and the very same code keeps it ordered shortest-first.

Reading forward and backward

Because the list is doubly-linked, you can reach a song from either end. playlist_title_at takes an index: a non-negative index counts forward from the head using next (index 0 is the first song), and a negative index counts backward from the tail using prev (index -1 is the last song, -2 the one before it). The backward case is what the prev links are for.

Sharing a playlist between threads

So far every program did one thing at a time. Now main.c starts several listener threads that all call playlist_insert on the same playlist at the same time. Recall from Lecture 12 why that is dangerous: splicing a node in is a read-modify-write of head, tail, size, and neighbouring pointers, and if two threads interleave their steps they can lose a node, build a cycle, or leave size wrong - a race condition. Nothing crashes on the line that looks wrong; the list just quietly corrupts.

The fix is the one from Lecture 12: mutual exclusion. Each playlist carries its own pthread_mutex_t lock. Every operation locks it, does its work, and unlocks it, so only one thread is ever inside the list at a time. One lock per playlist means there is never more than one lock to hold, so there is no lock-ordering or deadlock puzzle here - just remember that every lock needs exactly one matching unlock on every path, including early returns. Keep the locked region small: do the malloc and strcpy for a new node, or the free of a removed one, outside the lock, since they touch no shared state.

How Part 3 is graded

Thread-safety is checked by a stress test, hammer.c (included in the starter). It launches many threads that pound on one shared playlist and then checks that the list is still intact (the forward and backward node counts match size, the links agree, it is still sorted, and the expected number of songs remain). You run it two ways:

make hammer        # prints "INVARIANTS OK" when the list survived
make hammer-tsan   # the same test under ThreadSanitizer

ThreadSanitizer is a tool that reports a data race directly, even on a run where the timing happened to come out right, so it is the real test of your locking. A report looks like WARNING: ThreadSanitizer: data race followed by the two conflicting accesses and their stacks; each one points at a line that touched shared state without holding the lock. A correctly locked playlist produces no warning at all.

Homework 4 Tasks

Implement every function in starter/playlist.c. The exact prototype and contract for each is in starter/playlist.h. You may add static helper functions.

Part 1 - Build the doubly-linked playlist (35 pts)

Function Does
playlist_t *playlist_create(song_cmp_t cmp) malloc an empty playlist, store cmp, set head/tail/size, and pthread_mutex_init the lock. Return NULL on allocation failure.
void playlist_free(playlist_t *p) Free every node and its title, pthread_mutex_destroy the lock, then free the playlist (NULL is fine).
int playlist_insert(playlist_t *p, const char *title, int duration) Insert a new song into sorted position using p->cmp, with a heap copy of the title. Return 1 on success, 0 on allocation failure.
int playlist_length(playlist_t *p) Return the number of songs.

Part 2 - Navigate and remove (25 pts)

Function Does
int playlist_remove(playlist_t *p, const char *title) Unlink and free the first song with this title, fixing the neighbouring links and head/tail. Return 1 if removed, 0 if no song matched.
int playlist_title_at(playlist_t *p, int index, char *buf, int bufsize) Copy the title at index into buf (forward from the head for index >= 0, backward from the tail for index < 0). Return 1 on success, 0 if out of range.

Part 3 - Make it thread-safe (30 pts)

Go back through the operations you wrote in Parts 1 and 2 and protect each one so that several threads may share one playlist. Wrap the body of every operation that touches the list in pthread_mutex_lock(&p->lock) and pthread_mutex_unlock(&p->lock), remembering to unlock on every path out.

This part is graded by hammer.c, run directly and under ThreadSanitizer (see above): 15 points for keeping the list's invariants intact under many threads, and 15 points for being free of data races under ThreadSanitizer.

Once everything works, main.c becomes a working listening party:

$ ./app
Final playlist (9 songs, alphabetical):
   1. Africa
   2. Blue in Green
   3. Bohemian Rhapsody
   4. Clair de Lune
   5. Giant Steps
   6. Hotel California
   7. Redbone
   8. So What
   9. Take Five
Last song (reached backward from the tail): Take Five

Building and testing

cd hw4/starter
make          # build the app
./app         # run the Listening Party

make test     # build & run the public Criterion test suite (Parts 1 and 2)
make hammer   # stress-test thread-safety (Part 3)
make hammer-tsan   # the same, under ThreadSanitizer
make clean

Trying one function at a time

While you are still building things up, it is much easier to call a single function by hand than to run the whole app. Create your own scratch driver named try.c in hw4/starter/ with its own main() that calls whichever playlist.c functions you want to exercise, then:

make try      # compiles try.c against playlist.c into ./try
./try

A minimal try.c might look like:

#include <stdio.h>
#include <string.h>
#include "playlist.h"

static int by_title(const song_t *a, const song_t *b) {
    return strcmp(a->title, b->title);
}

int main(void) {
    playlist_t *p = playlist_create(by_title);
    playlist_insert(p, "Redbone", 357);
    playlist_insert(p, "Africa", 295);

    char buf[PLAYLIST_MAX_TITLE];
    playlist_title_at(p, 0, buf, sizeof buf);
    printf("first song = %s\n", buf);

    playlist_free(p);
    return 0;
}

try.c is just for you: you do not submit it, and the grader never builds it, so make try fails harmlessly until you create the file. make clean removes it along with the others.

The public tests in test_playlist.c are a subset of what we grade with - passing them is necessary but not sufficient. Write your own tests and try edge cases: inserting at the head, middle, and tail; removing the only song; duplicate titles; and negative indices.

Memory and thread safety

Because you manage memory by hand, check for leaks and invalid accesses:

valgrind ./app
valgrind ./test_playlist

A correct solution reports no leaks and no errors. Separately, make hammer-tsan must run with no ThreadSanitizer warning. valgrind and ThreadSanitizer only work on Linux and WSL; on a Mac, run on the CS cluster to check.

Rules & academic integrity

  • Do not use qsort to keep the list ordered. Insert each song into its sorted position yourself. (<stdlib.h> and <string.h> are fine and needed.)
  • Part 3 must use a pthread_mutex_t, not <stdatomic.h>, and the mutex must live inside the playlist struct (one lock per playlist), not a single global lock shared by all playlists.
  • Your code must compile with no warnings under -Wall -Wextra -Werror.
  • One free for every malloc, and one unlock for every lock. No leaks, no use-after-free, no double-free. This is part of your grade and is checked with valgrind.
  • Do not change playlist.h, main.c, hammer.c, or the Makefile. You submit only playlist.c, and it must build against the unmodified reference files.
  • Generative AI policy (from the syllabus): do not use an LLM to write or fix your CS143 code, and do not paste course materials or your code into one. The work you submit must be your own. Cite any outside sources you consult (even small ones) in a code comment. If you find yourself stuck, reach out to the instructor on Ed or in person to get unstuck - do not spend more than an hour fighting a problem without asking for help.

Grading

Component Points
Part 1 - build the doubly-linked playlist 35
Part 2 - navigate and remove 25
Part 3 - make it thread-safe 30
Manual Grading 10
Total 100

The manual grading portion is for code style, comments, and memory safety (no leaks under valgrind). Please see the UChicago CS Style Guide for C for additional details.

Manual Grading of Mutex Usage: As part of the manual grading, we will also look at your locking discipline. Make sure that you are locking and unlocking the mutex in all of the functions that access shared state, and that you are not holding the lock longer than necessary.

Submitting

Submit playlist.c (the only file you change) to Gradescope under "HW4". Make sure it builds against the unmodified playlist.h, main.c, hammer.c, and Makefile. Remember the late policy from the syllabus (3 late days total for the quarter).