Homework 04: Nodes, Queues, Tail, Tac

The goal of this homework assignment is to allow you to explore building a queue using a doubly linked list and then using this data structure to implement two Unix utilities: tail and tac. The first two activities involve implementing a queue which internally uses a doubly linked list with a sentinel node. Once you have a working data structure library, you will then use it to implement both the tail and tac utilities, which shows the last few N lines or reverses the contents of an input stream (respectively). After these coding activities, there is a quiz where you will have an opportunity to reflect on the code you have written for this homework assignment.

For this assignment, you are to do your work in the homework04 folder of your assignments GitHub repository and push your work by noon Wednesday, September 20.

Activity 0: Preparation

Before starting this homework assignment, you should first perform a git pull to retrieve any changes in your remote GitHub repository:

$ cd path/to/repository                   # Go to assignments repository

$ git switch master                       # Make sure we are in master branch

$ git pull --rebase                       # Get any remote changes not present locally

Next, create a new branch for this assignment:

$ git checkout -b homework04              # Create homework04 branch and check it out

Task 1: Skeleton Code

To help you get started, the instructor has provided you with the following skeleton code:

# Go to assignments repository
$ cd path/to/assignments/repository

# -----------------------------------------------------
# MAKE SURE YOU ARE NOT INSIDE THE homework04 DIRECTORY
# -----------------------------------------------------
# MAKE SURE YOU ARE AT THE TOP-LEVEL DIRECTORY
# -----------------------------------------------------

# Download skeleton code tarball
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20312.fa23/static/tar/homework04.tar.gz

# Extract skeleton code tarball
$ tar xzvf homework04.tar.gz

Once downloaded and extracted, you should see the following files in your homework04 directory:

homework04
    \_ Makefile             # This is the Makefile for building all the project artifacts
    \_ bin                  # This contains the project binary executables and test scripts
        \_ test_node.sh     # This is the shell script for testing the Node structure
        \_ test_queue.sh    # This is the shell script for testing the Queue utility
        \_ test_tac.sh      # This is the shell script for testing the tac program
        \_ test_tail.sh     # This is the shell script for testing the tail program
    \_ include              # This contains the project header files
        \_ ds               # This contains the project data structure header files
            \_ node.h       # This is the C header file for the Node structure
            \_ queue.h      # This is the C header file for the Queue structure
    \_ lib                  # This contains the project library files
    \_ src                  # This contains the project source code
        \_ node.c           # This is the C source code for the Node structure
        \_ queue.c          # This is the C source code for the Queue structure
        \_ tac.c            # This is the C source code for the tac program
        \_ tail.c           # This is the C source code for the tail program
    \_ tests                # This contains the project unit tests
        \_ unit_node.c      # This is the unit test for the Node structure
        \_ unit_queue.c     # This is the unit test for the Queue structure

Task 2: Initial Import

Now that the files are extracted into the homework04 folder, you can commit them to your git repository:

# Go into homework04 folder
$ cd homework04

# Add and commit initial skeleton files
$ git add Makefile                            # Mark changes for commit
$ git add bin/*.sh                            # Mark changes for commit
$ git add include/ds/*.h                      # Mark changes for commit
$ git add lib/.gitkeep                        # Mark changes for commit
$ git add src/*.c                             # Mark changes for commit
$ git add tests/*.c                           # Mark changes for commit
$ git commit -m "Homework 04: Initial Import" # Record changes

The details on what you need to implement are described in the following sections.

Task 3: Makefile

The Makefile contains all the rules or recipes for building the project artifacts (e.g. tail, tac, libds.a, unit_node, unit_queue, etc.):

CC=   gcc
CFLAGS=   -Wall -std=gnu99 -g -Iinclude
AR=   ar
ARFLAGS=  rcs
LD=   gcc
LDFLAGS=  -Llib

all:    bin/tail bin/tac

test:
        @$(MAKE) -sk test-all

test-all: test-node test-queue test-tail test-tac

# TODO: Pattern rule for object files

# TODO: Rule for lib/libds.a

# TODO: Rule for bin/tail

# TODO: Rule for bin/tac

bin/unit_node:  tests/unit_node.o lib/libds.a
        $(LD) $(LDFLAGS) -o $@ $^

bin/unit_queue: tests/unit_queue.o lib/libds.a
        $(LD) $(LDFLAGS) -o $@ $^

test-node:  bin/unit_node
        bin/test_node.sh

test-queue: bin/unit_queue
        bin/test_queue.sh

test-tail:  bin/tail
        bin/test_tail.sh

test-tac: bin/tac
        bin/test_tac.sh

clean:
        rm -f bin/unit_* bin/tail bin/tac lib/*.a src/*.o tests/*.o

For this task, you will need to add rules for building the static library lib/libds.a and the programs bin/tail and bin/tac. Be sure to have a recipe for any intermediate object files that libraries require as shown in the DAG below:

Makefile Variables

You must use the CC, CFLAGS, LD, LDFLAGS, AR, and ARFLAGS variables when appropriate in your rules. You should also consider using automatic variables such as $@ and $< as well.

Once you have a working Makefile, you should be able to run the following commands:

# Build all TARGETS
$ make
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/tail.o src/tail.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/node.o src/node.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/queue.o src/queue.c
ar rcs lib/libds.a src/node.o src/queue.o
gcc -Llib -o bin/tail src/tail.o lib/libds.a
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/tac.o src/tac.c
gcc -Llib -o bin/tac src/tac.o lib/libds.a

# Run all tests
$ make test
Testing node...
...

# Remove generated artifacts
$ make clean
rm -f bin/unit_* bin/tail bin/tac lib/*.a src/*.o tests/*.o

Note: The tests will fail if you haven't implemented Node or Queue structures, or the tail or tac programs.

Warnings

You must include the -Wall flag in your CFLAGS when you compile. This also means that your code must compile without any warnings, otherwise points will be deducted.

After completing the Makefile and verifying that you can produce all the specified artifacts, you may begin implementing the data structures and applications for this assignment.

Activity 1: Node Library (1 Point)

For the first activity, you are to implement a Node structure to be used in a doubly linked list. Each Node structure will have the following attributes:

  1. data: This is a pointer to a string allocated on the heap.

  2. next: This is a pointer to the next Node struct in the sequence.

  3. prev: This is a pointer to the previous Node struct in the sequence.

Task 1: include/ds/node.h

The include/ds/node.h file is the header file for the Node structure, which contains the following structs and function prototypes:

/* node.h: Node Structure */

#pragma once

/* Structures */

typedef struct Node Node;
struct Node {
    char *data;     // String value
    Node *next;     // Pointer to next Node
    Node *prev;     // Pointer to previous Node
};

/* Functions */

Node *  node_create(const char *data, Node *next, Node *prev);
void    node_delete(Node *n);

Other programs will #include this file in order to use the functions we will be implementing in this library.

Note: For this task, you do not need to modify this file. Instead, you should review it and ensure you understand the provided code.

Task 2: src/node.c

The src/node.c file contains the C implementation for the Node structure. For this task, you will need to implement the following functions:

  1. Node * node_create(const char *data, Node *next, Node *prev)

    This function allocates a new Node struct and initializes its attributes: data, next, prev as described above.

    Hint: Use malloc, calloc, or strdup to allocate data on the heap.

  2. void node_delete(Node *n)

    This function deallocates the given Node struct along with its internal data string.

    Hint: Use free to release data allocated on the heap.

Task 3: Testing

As you implement the functions in src/node.c, you should use bin/test_node.sh to test each function:

# Build unit-test
$ make bin/unit_node
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_node.o tests/unit_node.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/node.o src/node.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/queue.o src/queue.c
ar rcs lib/libds.a src/node.o src/queue.o
gcc -Llib -o bin/unit_node tests/unit_node.o lib/libds.a

# Run test script manually
$ ./bin/test_node.sh
Testing node...
 node_create                              ... Success
 node_delete                              ... Success

   Score 1.00 / 1.00
  Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test-node
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_node command directly:

# Display usage message
$ ./bin/unit_node
Usage: ./bin/unit_node NUMBER

Where NUMBER is right of the following:
    0  Test node_create
    1  Test node_delete

# Run test for node_create
$ ./bin/unit_node 0

# Run test for node_create using GDB
$ gdb ./bin/unit_node
...
(gdb) run 0

# Run test for node_create using Valgrind
$ valgrind --leak-check=full ./bin/unit_node 0

Of course, you are free to create your own test programs to debug and test your Node structure.

Iterative Development

You should practice iterative development. That is, rather than writing a bunch of code and then debugging it all at once, you should concentrate on one function at a time and then test that one thing at a time. The provided unit tests allow you to check on the correctness of the individual functions without implementing everything at once. Take advantage of this and build one thing at a time.

Activity 2: Queue Library (6 Points)

In high-level languages such as Python, we have built-in implementations of deques which support a variety of methods:

# Load library
>>> import collections

# Define a deque (unbounded)
>>> queue = collections.deque([4, 6, 6, 3, 7])

# Add a new value to the back of deque
>>> queue.append(9)
>>> queue
deque([4, 6, 6, 3, 7, 9])

# Remove value at the front of deque
>>> queue.popleft()
4
>>> queue
deque([6, 6, 3, 7, 9])

# Define a deque (bounded, no more than 5)
>>> queue = collections.deque([4, 6, 6, 3, 7], maxlen=5)

# Add a new value to the back of deque
>>> queue.append(9)
>>> queue
deque([6, 6, 3, 7, 9], maxlen=5)

As can be seen, deques in Python can behave like the queues discussed in class with efficient push operations to the back of the structure via append and efficient pop operations to the front of the structure via popleft.

Moreover, deques in Python can also be bounded, that is they will maintain a maximum capacity once it is reached. If the user adds another value to a structure that is at its capacity, then the current value at the front of the structure is removed to make room for the new value to be added at the back.

For the second activity, you are to use the Node structure from the previous activity to construct a Queue structure that implements a doubly linked list with a sentinel node to mimic the functionality of deques in Python.

The Queue struct you are to implement has the following attributes:

  1. sentinel: This is a sentinel Node struct embedded inside the Queue struct. It is used to simplify our internal Queue methods by ensuring that there will always be an allocated Node in the doubly linked list.

  2. capacity: This is the maximum capacity of the Queue structure. If this value is set to 0, then the Queue is considered to be unbounded and may have any number of values. If this value is not 0, however, then you must ensure the Queue never has more than this number of values.

  3. size: This is the number of values in the Queue structure. It should not exceed the capacity if it the capacity is not 0.

Note: The sentinel node is not considered part of the actual queue. It does not store any data nor does it contribute to the size of the Queue.

Instead, it is there so that its next pointer is the head of the doubly linked list and its prev pointer is the tail of the doubly linked list.

With this Queue struct in mind, you are to complete the queue library, lib/ds.a., which contains functions such as queue_push and queue_pop that implement some of the functionality present in Python but missing in C.

Task 1: include/ds/queue.h

The include/ds/queue.h file is the header file for the queue library, which contains the following structs and function prototypes:

/* queue.h: Queue Structure */

#pragma once

#include "ds/node.h"

#include <stdbool.h>
#include <stdio.h>

/* Structures */

typedef struct {
    Node   sentinel;      // Sentinel Node
    size_t capacity;      // Capacity or maximum size of Queue
    size_t size;          // Current size of Queue (how many Nodes)
} Queue;

/* Functions */

Queue * queue_create(size_t capacity);
void    queue_delete(Queue *q);

void    queue_push(Queue *q, const char *s);
char *  queue_pop(Queue *q);

bool    queue_empty(Queue *q);

void    queue_dump(Queue *q, FILE *s);

void    queue_reverse(Queue *q);

Note: For this task, you do not need to modify this file. Instead, you should review it and ensure you understand the provided code.

Task 2: src/queue.c

The src/queue.c file contains the C implementation for the queue library.

For this task, you will need to implement the following functions:

  1. Queue * queue_create(size_t capacity)

    This function allocates a new Queue struct and initializes its attributes: sentinel, capacity, size as described above.

    Hint: Use malloc, calloc, or strdup to allocate data on the heap. Be sure to initialize the next and prev pointers of sentinel.

  2. void queue_delete(Queue *q)

    This function deallocates the given Queue struct along with its internal Node structs.

    Hint: Use node_delete to delete the internal Node struct`s.

    To loop through the internal Node structures, you will want to start with the first Node the sentinel points to and then stop once you return to the sentinel.

  3. void queue_push(Queue *q, const char *s)

    This function creates a new Node struct with the given string s and adds it to the back of the internal doubly linked list (e.g. q.append(s) in Python).

    Hint: Use node_create and take advantage of the sentinel in the Queue struct. Likewise, be sure to not exceed the capacity of the Queue if it is not 0.

    Note: The queue_capacity test verifies whether or not you ensure that queue_push does not exceed the capacity of the Queue if it is not 0.

    It is tested separately because you can use queue_pop to implement this functionality.

  4. char * queue_pop(Queue *q)

    This function removes the Node struct at the front of the internal doubly linked list and returns the associated string data from the Node struct (e.g. q.popleft() in Python).

    Hint: Use node_delete and take advantage of the sentinel in the Queue struct.

    Consider using strdup to ensure the returned string is safely allocated on the heap.

  5. bool queue_empty(Queue *q)

    This function returns true if the Queue struct has no values, otherwise false.

  6. void queue_dump(Queue *q, FILE *s)

    This function prints every value in the Queue struct to the given stream (one value per line).

  7. void queue_reverse(Queue *q)

    This function reverses the internal doubly linked list in the Queue struct.

    Hint: Draw a picture and determine which next and prev pointers needed to be updated and when.

Task 3: Testing

As you implement the functions in src/queue.c, you should use bin/unit_queue.sh to test each function:

# Build unit-test
$ make bin/unit_queue
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_queue.o tests/unit_queue.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/node.o src/node.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/queue.o src/queue.c
ar rcs lib/libds.a src/node.o src/queue.o
gcc -Llib -o bin/unit_queue tests/unit_queue.o lib/libds.a

# Run test script manually
$ ./bin/test_queue.sh
Testing queue...
 queue_create                             ... Success
 queue_delete                             ... Success
 queue_push                               ... Success
 queue_pop                                ... Success
 queue_capacity                           ... Success
 queue_empty                              ... Success
 queue_dump                               ... Success
 queue_reverse                            ... Success

   Score 6.00 / 6.00
  Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_queue command directly:

# Display usage message
$ ./bin/unit_queue
Usage: ./bin/unit_queue NUMBER

Where NUMBER is right of the following:

# Run test for queue_create
$ ./bin/unit_queue 0

# Run test for queue_create using GDB
$ gdb ./bin/unit_queue
...
(gdb) run 0

# Run test for queue_create using Valgrind
$ valgrind --leak-check=full ./bin/unit_queue 0

Of course, you are free to create your own test programs to debug and test your queue library.

Activity 3: Tail (2 Points)

Once you have a working queue library, you are to complete the src/tail.c program, which is a simplified version of the tail utility:

# Show last 10 items by default
$ seq 100 | bin/tail
91
92
93
94
95
96
97
98
99
100

# Show last 5 items
$ seq 100 | bin/tail -n 5
96
97
98
99
100

As can be seen, the bin/tail program reads [standard input] line by line and only emits the last 10 lines by default.

If the user specifies another limit via the -n flag, then only that number of lines is shown.

Task 1: src/tail.c

The src/tail.c file contains the C implementation of the bin/tail program described above. You will need to implement the following functions:

  1. int main(int argc, char *argv[])

    This function parses command line options and then reads one line at a time from stdin, and emits only the last N lines (where N is 10 by default).

    Hint: To parse command line options, use the slice program from Homework 02 as a reference.

Memory Management

In addition to meeting the functional requirements of the assignment (as described above), your program must not exhibit any memory leaks or invalid memory accesses as would be detected by Valgrind.

Be sure to free any memory that has been allocated on the heap and to initialize any allocate memory appropriately.

Task 2: Testing

As you implement src/tail.c, you can test it by running the test-tail target:

# Build artifact and run test
$ make test-tail
Testing tail ...
 Makefile (output)                        ... Success
 Makefile (valgrind)                      ... Success
 Makefile -n 5 (output)                   ... Success
 Makefile -n 5 (valgrind)                 ... Success
 Makefile -n 20 (output)                  ... Success
 Makefile -n 20 (valgrind)                ... Success
 seq 100 (output)                         ... Success
 seq 100 (valgrind)                       ... Success
 seq 100 -n 5 (output)                    ... Success
 seq 100 -n 5 (valgrind)                  ... Success
 seq 100 -n 20 (output)                   ... Success
 seq 100 -n 20 (valgrind)                 ... Success

   Score 2.00 / 2.00
  Status Success

Activity 4: Tac (1 Point)

Once you have a working queue library, you are to complete the src/tac.c program, which is a simplified version of the tac utility:

# Show lines in reverse order
$ seq 5 10 | bin/tac
10
9
8
7
6
5

As can be seen, the bin/tac program reads [standard input] line by line and emits the lines in reversed order.

Task 1: src/tac.c

The src/tac.c file contains the C implementation of the bin/tac program described above. You will need to implement the following functions:

  1. int main(int argc, char *argv[])

    This function reads one line at a time from stdin, and emits all the lines in reversed order.

Task 2: Testing

As you implement src/tac.c, you can test it by running the test-tac target:

# Build artifact and run test
$ make test-tac
Testing tac ...
 Makefile (output)                        ... Success
 Makefile (valgrind)                      ... Success
 seq 100 (output)                         ... Success
 seq 100 (valgrind)                       ... Success

   Score 1.00 / 1.00
  Status Success

Activity 5: Quiz (2 Points)

Once you have completed all the activities above, you are to complete the following reflection quiz:

As with Reading 01, you will need to store your answers in a homework04/answers.json file. You can use the form above to generate the contents of this file, or you can write the JSON by hand.

To check your quiz directly, you can use the check.py script:

$ ../.scripts/check.py
Checking homework04 quiz ...
      Q1 0.50
      Q2 0.50
      Q3 0.60
      Q4 0.40
   Score 2.00 / 2.00
  Status Success

Leet Point (1 Extra Credit Point)

For extra credit, you are to solve the following LeetCode problem in C.

1700. Number of Students Unable to Eat Lunch

To receive credit, you must pass on LeetCode and achieve an Accepted submission.

Verification

To get credit for this Leet Point, show your solution and the LeetCode acceptance page to a TA to verify (or attached a screenshot with both to your Pull Request). You have up until two days after this assignment is due to verify your Leet Point.

Self-Service Extension

Remember that you can always forgo this Leet Point for two extra days to do the homework. That is, if you need an extension, you can simply skip the Leet Point and you will automatically have until Friday to complete the assignment for full credit.

Just leave a note on your Pull Request of your intentions.

Submission

To submit your assignment, please commit your work to the homework04 folder of your homework04 branch in your assignments GitHub repository:

#-----------------------------------------------------------------------
# Make sure you have already completed Activity 0: Preparation
#-----------------------------------------------------------------------
...
$ git add Makefile                            # Mark changes for commit
$ git commit -m "Homework 04: Activity 0"     # Record changes
...
$ git add src/node.c                          # Mark changes for commit
$ git commit -m "Homework 04: Activity 1"     # Record changes
...
$ git add src/queue.c                         # Mark changes for commit
$ git commit -m "Homework 04: Activity 2"     # Record changes
...
$ git add src/tail.c                          # Mark changes for commit
$ git commit -m "Homework 04: Activity 3"     # Record changes
...
$ git add src/tac.c                           # Mark changes for commit
$ git commit -m "Homework 04: Activity 4"     # Record changes
...
$ git add answers.json                        # Mark changes for commit
$ git commit -m "Homework 04: Activity 5"     # Record changes
...

$ git push -u origin homework04               # Push branch to GitHub

Pull Request

Remember to create a Pull Request and assign the appropriate TA from the Reading 04 TA List.

DO NOT MERGE your own Pull Request. The TAs use open Pull Requests to keep track of which assignments to grade. Closing them yourself will cause a delay in grading and confuse the TAs.