Homework 07: Seqit, Tailit

The goal of this homework assignment is to allow you to practice memory management in C by building a linked list. The first activities involve implementing a doubly linked list with a sentinel node, while the last two activities requires you to use this data structure to implement your own versions of seq and tail.

For this assignment, you are to do your work in the homework07 folder of your assignments GitHub repository and push your work by noon Saturday, March 29.

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 homework07              # Create homework07 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 homework07 folder
$ cd homework07

# Download Makefile
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/Makefile

# Download C skeleton code
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/list.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/list.h
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/list.unit.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/node.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/node.unit.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/seqit.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp25/static/txt/homework07/tailit.c

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

homework07
    \_ Makefile     # This is the Makefile for building all the assignment artifacts
    \_ list.c       # This is the List structure C source file
    \_ list.h       # This is the List library C header file
    \_ list.unit.c  # This is the List structure C unit test source file
    \_ node.c       # This is the Node structure C source file
    \_ node.unit.c  # This is the Node structure C unit test source file
    \_ seqit.c      # This is the seqit utility C source file
    \_ list.c       # This is the tailit utility C source file

Task 2: Initial Import¶

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

$ git add Makefile                            # Mark changes for commit
$ git add *.c *.h                             # Mark changes for commit
$ git commit -m "Homework 07: Initial Import" # Record changes

Task 3: Unit Tests¶

After downloading these files, you can run make test to run the tests.

# Run all tests (will trigger automatic download)
$ make test

You will notice that the Makefile downloads these additional test files and scripts:

homework07
    \_ list.unit.sh   # This is the List structure unit test shell script
    \_ node.unit.sh   # This is the Node structure unit test shell script
    \_ seqit.test.sh  # This is the seqit utility test shell script
    \_ tailit.test.sh # This is the tailit utility test shell script

You will be using these unit tests to verify the correctness and behavior of your code.

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

Task 4: Makefile¶

The Makefile contains all the rules or recipes for building the project artifacts (e.g. node.unit, list.unit, seqit, tailit, etc.):

CC=       gcc
CFLAGS=   -Wall -g -std=gnu99
LD=       gcc
LDFLAGS=  -L.
TARGETS=  seqit tailit

all:      $(TARGETS)

#-------------------------------------------------------------------------------
# TODO: Add rules for node.o, list.o, seqit.o, tailit.o, seqit, tailit
#-------------------------------------------------------------------------------

node.o:

list.o:

seqit.o:

tailit.o:

seqit:

tailit:

#-------------------------------------------------------------------------------
# DO NOT MODIFY BELOW
#-------------------------------------------------------------------------------

...

For this task, you will need to add rules for building the programs seqit and tailit. Be sure to have a recipe for any intermediate object files that programs require as shown in the DAG below:

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

# Build all TARGETS
$ make
gcc -Wall -g -std=gnu99 -c -o seqit.o seqit.c
gcc -Wall -g -std=gnu99 -c -o node.o node.c
gcc -Wall -g -std=gnu99 -c -o list.o list.c
gcc -L. -o seqit seqit.o node.o list.o
gcc -Wall -g -std=gnu99 -c -o tailit.o tailit.c
gcc -L. -o tailit tailit.o node.o list.o

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

# Remove generated artifacts
$ make clean

Task 5: list.h¶

The list.h file is the header file for the doubly linked list library, which contains the following structs and function prototypes:

/* list.h: Doubly Linked List Library */

#pragma once

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

/* Value Union */

typedef union {
    int64_t number;     // Value as number
    char   *string;     // Value as string
} Value;

/* Node Structure */

typedef struct Node Node;
struct Node {
    Value   value;      // Value
    Node   *next;       // Pointer to next Node
    Node   *prev;       // Pointer to previous Node
};

Node *  node_create(Value v, Node *next, Node *prev);
void    node_delete(Node *n, bool release);

/* List Structure */

typedef struct {
    Node    sentinel;   // Sentinel Node at head and tail of List
    size_t  size;       // Number of Nodes in List
} List;

List *  list_create();
void    list_delete(List *l, bool release);

void    list_append(List *l, Value v);
Value   list_pop(List *l, size_t index);

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

Value Union¶

The Value union is used by the Node structure to store either an integer or a string:

// Declare a Value union with an integer
Value v = (Value)10L;

// Alternatively
Value v = {.number = 10};

// Access number
printf("%ld\n", v.number);

// Declare a Value union with a string
Value v = (Value)"reasonable";

// Alternatively
Value v = {.string = "reasonable"};

// Access string
puts(v.string);

The details of the Node structure and List structure, and what you need to implement are provided in the following sections.

Activity 1: Node Structure (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. value: This is a union that can either be a number (ie. int64_t) or a string (ie. char *).

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: node.c¶

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

1. Node * node_create(Value v, Node *next, Node *prev)

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

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

2. void node_delete(Node *n, bool release)

   This function deallocates the given Node struct along with its internal value as a string if release is true.

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

Task 2: Testing¶

As you implement the functions in node.c, you should use the node.unit executable with the node.unit.sh script to test each of your functions:

# Build test artifacts and run test scripts
$ make test-node
Testing node ...
 node_create                              ... Success
 node_delete                              ... Success

   Score 1.00 / 1.00
  Status Success

You can also run the testing script manually:

# Run Shell unit test script manually
$ ./node.unit.sh
...

To debug your Node functions, you can use gdb on the node.unit executable:

# Start gdb on node.unit
$ gdb ./node.unit
(gdb) run 0     # Run node.unit with the "0" command line argument (ie. node_create)
...

You can also use valgrind to check for memory errors:

# Check for memory errors on node_create test case
$ valgrind --leak-check=full ./node.unit 0

Activity 2: List Structure (2 Points)¶

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

# Declare a list
>>> data = [5, 7, 4]

# Add a new value to the back of list
>>> data.append(0)
>>> data
[5, 7, 4, 0]

# Remove value from front of list
>>> data.pop(0)
5
>>> data
[7, 4, 0]

# Remove value from middle of list
>>> data.pop(1)
4
>>> data
[7, 0]

As you already know, lists in Python provide an append method to add values to the back of the list and a pop method to remove a value at a specified index from the list.

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

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

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

2. size: This is the number of values in the List structure.

With this List struct in mind, you are to complete the doubly linked list library, which contains functions such as list_append and list_pop that implement some of the functionality present in Python but missing in C.

Task 1: list.c¶

The list.c file contains the C implementation for the List structure described above. For this task, you will need to implement the following functions:

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

1. List* list_create()

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

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

2. void list_delete(List *l, bool release)

   This function deallocates the given List 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 list_append(List *l, Value v)

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

   Hint: Use node_create and take advantage of the sentinel in the List struct.

4. Value list_pop(List *l, size_t index)

   This function removes the Node struct at the specified index from the internal doubly linked list and returns the associated Value from the Node struct (e.g. l.pop(index) in Python).

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

   If the index is beyond the bounds of the List, then return -1L as the `Value.

Task 2: Testing¶

As you implement the functions in list.c, you should use the list.unit executable with the list.unit.sh script to test each of your functions:

# Build test artifacts and run test scripts
$ make test-list
Testing list ...
 list_create                              ... Success
 list_delete                              ... Success
 list_append                              ... Success
 list_pop                                 ... Success

   Score 2.00 / 2.00
  Status Success

You can also run the testing script manually:

# Run Shell unit test script manually
$ ./list.unit.sh
...

To debug your list functions, you can use gdb on the list.unit executable:

# Start gdb on list.unit
$ gdb ./list.unit
(gdb) run 0     # Run list.unit with the "0" command line argument (ie. list_create)
...

You can also use valgrind to check for memory errors:

# Check for memory errors on list_create test case
$ valgrind --leak-check=full ./list.unit 0

Activity 3: Seqit (2 Points)¶

Once you have implemented both doubly linked list library, you are to complete the seqit.c program, which is a simplified version of the seq utility:

# Show usage
$ ./seqit
Usage: seqit LAST
       seqit FIRST LAST
       seqit FIRST INCREMENT LAST

# Show sequence of numbers start from 1 through 10
$ ./seqit 10
1
2
3
4
5
6
7
8
9
10

# Show sequence of numbers start from 5 through 10
$ ./seqit 5 10
5
6
7
8
9
10

# Show sequence of odd numbers start from 5 through 10
$ ./seqit 5 2 10
5
7
9

As can be seen, the seqit program emits a sequence of numbers (one number per line) based on the specified FIRST, INCREMENT, and LAST arguments. By default, FIRST is 1 and INCREMENT is 1.

Task 1: seqit.c¶

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

1. List *generate_sequence(ssize_t first, ssize_t increment, ssize_t last)

   This function generates a sequence of numbers going from first to last using the specified increment by building a List with these numbers and returning it.

   Hint: Take advantage of the list_create and list_append functions you wrote above.

   Think carefully how you should handle negative increment parameters.

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

   This function parses command line arguments for FIRST, INCREMENT, or LAST, generates a sequence of numbers, and then prints out that sequence (one number per line).

   Hint: Take advantage of the list_create, list_pop, list_delete functions you wrote above.

Task 2: Testing¶

As you implement seqit.c, you can test it by running the test-seqit target:

# Build artifact and run test
$ make test-seqit
Testing seqit ...
 seqit 1                                  ... Success
 seqit 10                                 ... Success
 seqit 100                                ... Success
 seqit 1 100                              ... Success
 seqit 1 2 100                            ... Success
 seqit 100 -3 1                           ... Success
 seqit 1 2 3 4                            ... Success

   Score 2.00 / 2.00
  Status Success

Activity 4: Tailit (2 Points)¶

Once you have implemented both doubly linked list library, you are to complete the tailit.c program, which is a simplified version of the tail utility:

# Show usage
$ ./tailit -h
Usage: tailit [-n NUMBER]

    -n NUMBER  Output the last NUMBER of lines (default is 10)

# Show last 10 lines
$ ./seqit 100 | ./tailit
91
92
93
94
95
96
97
98
99
100

# Show last 5 lines
$ ./seqit 100 | ./tailit -n 5
96
97
98
99
100

As can be seen, the tailit 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: tailit.c¶

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

1. List *tail_stream(FILE *stream, size_t limit)

   This function reads the stream line by line and returns a List containing the last limit number of lines from the stream.

   Hint: Take advantage of the list_create, list_append, and list_pop functions you wrote above.

   Think carefully how you should handle storing only the limit number of lines in your List.

   Consider using strdup to ensure the [strings] you read with [fgets] persist between function calls.

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

   This function parses the command line arguments, creates a list of the last NUMBER of lines, and then prints out the items in the list.

   Hint: Take advantage of the list_create, list_pop, list_delete functions you wrote above.

Task 2: Testing¶

As you implement tailit.c, you can test it by running the test-tailit target:

# Build artifact and run test
$ make test-tailit
Testing tailit ...
 tailit -h                                ... Success
 tailit -p                                ... Success
 tailit                                   ... Success
 tailit -n 1                              ... Success
 tailit -n 5                              ... Success
 tailit -n 10                             ... Success
 tailit -n 25                             ... Success
 tailit -n 100                            ... Success

   Score 2.00 / 2.00
  Status Success

Activity 5: Quiz (3 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 homework07/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 homework07 quiz ...
     Q01 0.20
     Q02 0.20
     Q03 1.50
     Q04 0.60
     Q05 0.25
     Q06 0.25

   Score 3.00 / 3.00
  Status Success

Code Review (Optional, 1 Point)¶

For one point of extra credit, you may perform a code review with either an AI agent (of your choice) or with a TA by Wednesday, April 2:

1. AI Code Review: Once the whole assignment is completed, pick one or two of the most challenging functions and ask the AI agent to review your original code by suggesting improvements, optimizations, or alternative implementations.

   Test and verify these suggestions and then decide whether or not you wish to keep them. Discuss in the README.md what you think of the AI code review and explain your decision.

   AI Code Review: Verification¶

   To receive credit for the AI Code Review, you must:

   1. Link a transcript or include sufficient screenshots of the code review in the Pull Request of your conversation with the AI agent.

   2. This conversation must show your original code and the suggested improvements by the AI agent.

   3. Discuss the code review and explain your decision in the README.md.

   4. Update your Pull Request based on the feedback.

2. TA Code Review: Once the whole assignment is completed, meet with one of the teaching assistants from the course in-person and have them review your whole assignment.

   To document this process, make the teaching assistant who is reviewing your code a reviewer on your Pull Request and have them record their suggestions as they discuss them with you in-person.

   After the code review, you can decide whether or not you wish to incorporate this feedback into your implementation and update your Pull Request.

   Note: The TA performing the code review does not need to be the same TA responsible for grading your assignment.

   TA Code Review: Verification¶

   To receive credit for the TA Code Review, you must:

   1. Meet with a teaching assistant in-person.

   2. Make this teaching assistant a reviewer in your Pull Request.

   3. Have the teaching assistant record their suggestions on the Pull Request.

   4. Update your Pull Request based on the feedback.

Guru Point: Zines (Optional, 1 Point)¶

For one point of extra credit, you may create an original zine (ala Julia Evans) related to the topics for Exam 03 by Wednesday, April 2:

• Compiling and Building: Compiler pipeline, dynamic vs static executables, Makefiles
• Pointers, Arrays, Strings: Declaration, initialization, dereferencing, accessing, iterating
• Memory Allocation: Address space, stack vs heap, structs, unions
• Bitsets: Integer sizes, boolean operations
• Linked Lists: Construction, destruction, iteration, inserting, deletion, access
• Data Representation: Signed vs Unsigned, Little vs Big Endian

Some examples from Julia Evans:

Submission¶

To submit your assignment, please commit your work to the homework07 folder of your homework07 branch in your assignments GitHub repository. Your homework07 folder should only contain the following files:

• Makefile
• answers.json
• list.c
• list.h
• list.unit.c
• node.c
• node.unit.c
• seqit.c
• tailit.c

#-----------------------------------------------------------------------
# Make sure you have already completed Activity 0: Preparation
#-----------------------------------------------------------------------
...
$ git add Makefile                            # Mark changes for commit
$ git commit -m "Homework 07: Makefile"       # Record changes
...
$ git add node.c                              # Mark changes for commit
$ git commit -m "Homework 07: node.c"         # Record changes
...
$ git add list.c                              # Mark changes for commit
$ git commit -m "Homework 07: list.c"         # Record changes
...
$ git add seqit.c                             # Mark changes for commit
$ git commit -m "Homework 07: seqit.c"        # Record changes
...
$ git add tailit.c                            # Mark changes for commit
$ git commit -m "Homework 07: tailit"         # Record changes
...
$ git add answers.json                        # Mark changes for commit
$ git commit -m "Homework 07: Quiz"           # Record changes
...
$ git push -u origin homework07               # Push branch to GitHub