Homework 08: Findit

The goal of this homework assignment is to allow you to practice managing dynamic memory in C by building a linked list and navigating the file system using low-level functions and system calls. The first two activities involve implementing a singly linked list with a tail pointer and then a few filter functions that check various attributes about files, while the last activity requires you to use these structures and functions to build a file system search utility similar to find named findit.

For this assignment, record your source code and any responses to the following activities in the homework08 folder of your assignments GitHub repository and push your work by noon Saturday, April 13.

Frequently Asked Questions

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

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

# Download C skeleton code
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp24/static/txt/homework08/filter.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp24/static/txt/homework08/filter.unit.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp24/static/txt/homework08/findit.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp24/static/txt/homework08/findit.h
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp24/static/txt/homework08/list.c
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20289.sp24/static/txt/homework08/list.unit.c

Once downloaded, you should see the following files in your homework08 directory:

homework08
    \_ Makefile       # This is the Makefile for building all the assignment artifacts
    \_ filter.c       # This is the filter functions C source file
    \_ filter.unit.c  # This is the filter functions C unit test source file
    \_ findit.c       # This is the findit utility C source file
    \_ findit.h       # This is the findit utility C header file
    \_ list.c         # This is the linked list C source file
    \_ list.unit.c    # This is the linked list C unit test source file

Task 2: Initial Import

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

$ git add Makefile                            # Mark changes for commit
$ git add *.c *.h
$ git commit -m "Homework 08: 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 data and scripts:

homework08
    \_ filter.unit.sh   # This is the filter functions unit test shell script
    \_ find.test.sh     # This is the findit utility test shell script
    \_ list.unit.sh     # This is the linked list unit test shell script

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

Automatic Downloads

The test scripts are automatically downloaded by the Makefile, so any modifications you do to them will be lost when you run make again. Likewise, because they are automatically downloaded, you do not need to add or commit them to your git repository.

Task 4: Makefile

The Makefile contains all the rules or recipes for building the project artifacts (e.g. findit):

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

all:    $(TARGETS)

#-------------------------------------------------------------------------------
# TODO: Add rules for object files
#-------------------------------------------------------------------------------

list.o:

filter.o:

findit.o:

#-------------------------------------------------------------------------------
# TODO: Add rules for executables
#-------------------------------------------------------------------------------

findit:

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

...

For this task, you will need to add rules for building the intermediate object files (ie. list.o, filter.o, findit.o) and the findit executable with the appropriate dependencies as shown 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 -g -std=gnu99 -c -o findit.o findit.c
gcc -Wall -g -std=gnu99 -c -o list.o list.c
gcc -Wall -g -std=gnu99 -c -o filter.o filter.c
gcc -L. -o findit findit.o list.o filter.o

# Run all tests
$ make test
Testing list ...
 node_create                                                  ... Success
 node_delete                                                  ... Success
 list_append                                                  ... Success
 list_filter                                                  ... Success
 list_output                                                  ... Success

   Score 4.00 / 4.00
  Status Success

Testing filter ...
 filter_by_type                                               ... Success
 filter_by_name                                               ... Success
 filter_by_mode                                               ... Success

   Score 3.00 / 3.00
  Status Success

Testing findit utility...
 findit                                                       ... Success
 findit (valgrind)                                            ... Success
 findit /etc                                                  ... Success
 findit /etc  (valgrind)                                      ... Success
 findit /etc -type f                                          ... Success
 findit /etc -type f (valgrind)                               ... Success
 findit /etc -type d                                          ... Success
 findit /etc -type d (valgrind)                               ... Success
 findit /etc -name '*.conf'                                   ... Success
 findit /etc -name '*.conf' (valgrind)                        ... Success
 findit /etc -readable                                        ... Success
 findit /etc -readable (valgrind)                             ... Success
 findit /etc -writable                                        ... Success
 findit /etc -writable (valgrind)                             ... Success
 findit /etc -executable                                      ... Success
 findit /etc -executable (valgrind)                           ... Success
 findit /etc -type d -name '*.d'                              ... Success
 findit /etc -type d -name '*.d' (valgrind)                   ... Success
 findit /etc -type d -name '*.d' -executable                  ... Success
 findit /etc -type d -name '*.d' -executable (valgrind)       ... Success
 findit . -name '*.c'                                         ... Success
 findit . -name '*.c' (valgrind)                              ... Success
 findit . -writable                                           ... Success
 findit . -writable (valgrind)                                ... Success
 findit . -type f -name '*.unit' -executable                  ... Success
 findit . -type f -name '*.unit' -executable (valgrind)       ... Success

   Score 3.00 / 3.00
  Status Success

# Remove generated artifacts
$ make clean

Note: The tests will fail if you haven't implemented all the necessary functions appropriately.

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.

Task 5: findit.h

The findit.h file is the header file for the findit utility, which means it contains the type definitions and function prototypes:

/* findit.h: Search for files in a directory hierarchy */

#pragma once

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

/* Options Structure */

typedef struct {
    int   type;         // File type (-type)
    char *name;         // File name pattern (-name)
    int   mode;         // Access modes (-executable, -readable, -writable)
} Options;

/* Filter Functions */

typedef bool (*Filter)(const char *path, Options *options);

bool  filter_by_type(const char *path, Options *options);
bool  filter_by_name(const char *path, Options *options);
bool  filter_by_mode(const char *path, Options *options);

/* Data Union */

typedef union {
    char *  string;     // String data
    Filter  function;   // Filter function
} Data;

/* Node Structure */

typedef struct Node Node;
struct Node {
    Data    data;       // Data value
    Node   *next;       // Pointer to next Node
};

Node *  node_create(Data data, Node *next);
void    node_delete(Node *n, bool release, bool recursive);

/* List Structure */

typedef struct {
    Node   *head;       // Pointer to first Node
    Node   *tail;       // Pointer to last Node
} List;

void    list_append(List *l, Data data);
void    list_filter(List *l, Filter filter, Options *options, bool release);
void    list_output(List *l, FILE *stream);

Other C source files will #include this file in order to use the functions we will be implementing in this assignment.

Options Structure

The Options structure is used by the Filter functions to check the attribute of various files and directories encountered in the findit program. It has the following fields:

  1. type: This is used to store the file type (ie. S_IFREG, S_IFDIR) to match against.

  2. name: This is used to store the glob pattern to match against the basename of a path string.

  3. mode: This is used to store the access mode to match against.

Data Union

The Data union is used by the List structure to store either a string or a Filter function pointer:

// Declare a Data union with a string
Data dp = (Data)"file path";

// Access string
puts(dp.string)

// Declare a Data union with a Filter function pointer
Data df = (Data)filter_by_type;

// Access Filter function
df.function(path, options);

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

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

Activity 1: Linked List (4 Points)

The findit utility works by first walking a directory recursively and adding any entries it encounters to a singly linked list of file paths. For the first activity, you are to implement a singly linked list with both a head and tail pointer as show below:

The List structure consists of two pointers to Node structures:

  1. head: This points to the first Node in the singly linked list.
  2. tail: This points to the last Node in the singly linked list.

If the List is empty, then both head and tail should be NULL.

Each Node structure contains a Data union to store either a string or a Filter function pointer, and a pointer to the next Node in the singly linked list.

Task 1: list.c

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

  1. Node * node_create(Data data, Node *next)

    This function allocates a new Node structure on the heap, initializes its data and next attributes, and returns a pointer to this new Node structure.

    Hint: Consider using malloc or calloc.

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

    This function deallocates the given Node structure. If recursive is true, then the function will call node_delete on the next item in the singly linked list. Likewise, if release is true then the data string will also be deallocated (before deallocating the Node itself).

    Hint: Consider using free.

  3. void list_append(List *l, Data data)

    This function adds a new Node structure with the given data to the tail of the given List structure.

    Hint: Consider using node_create and make sure you update the head and tail of the List appropriately.

  4. void list_filter(List *l, Filter filter, Options *options, bool release)

    This function filters the given List by applying the Filter function to each Node's Data string and the given Options structure. If the Filter function returns true, then the Node is kept. Otherwise, it is removed from the List. If release is true, then the Data string should also be deallocated when removing a Node.

    Hint: Consider using node_delete when removing a Node. Draw a picture and consider how many pointers you need to effectively traverse the List and to remove a Node in the middle of the List. Moreover, make sure you update the head and tail of the List appropriately.

  5. void list_output(List *l, FILE *stream)

    This function prints the Data string of each Node in the given List to the specified stream.

    Hint: Consider using fprintf.

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 ...
 node_create                                                  ... Success
 node_delete                                                  ... Success
 list_append                                                  ... Success
 list_filter                                                  ... Success
 list_output                                                  ... Success

   Score 4.00 / 4.00
  Status Success

You can also run the testing script manually:

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

To debug your linked 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. node_create)
...

You can also use valgrind to check for memory errors:

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

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: Filters (3 Points)

As with the conventional find command, the findit utility will allow for filtering the list of file paths by their individual attributes. For instance, to only display the regular files in a directory, you can do the following with find:

# Only display regular files in the current directory
$ find . -type f

Internally, findit will support this feature by calling a Filter function on each entry in its singly linked list of file paths to check whether or not to keep it. In this specific example, findit would call filter_by_type with an Options structure that has its type attribute set to S_IFREG on each Data string in its List.

To support filtering the list of file paths in findit, you are to implement three Filter functions that return true if the file path should be kept in the list.

Task 1: filter.c

The filter.c file contains the C implementation for the Filter functions. For this task, you will need to implement the following functions:

  1. bool filter_by_type(const char *path, Options *options)

    This function returns true if the file at the specified path has the corresponding type specified in the Options structure.

    Hint: Consider using lstat and S_IFMT.

  2. bool filter_by_name(const char *path, Options *options)

    This function returns true if the basename of the specified path has matches the glob pattern specified in the Options structure.

    Hint: Consider using basename and fnmatch.

  3. bool filter_by_mode(const char *path, Options *options

    This function returns true if the file at the specified path has the access mode specified in the Options structure.

    Hint: Consider using access.

Task 2: Testing

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

# Build test artifacts and run test scripts
$ make test-filter
Testing filter ...
 filter_by_type                                               ... Success
 filter_by_name                                               ... Success
 filter_by_mode                                               ... Success

   Score 3.00 / 3.00
  Status Success

You can also run the testing script manually:

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

To debug your Filter functions, you can use [gdb] on the filter.unit executable:

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

You can also use valgrind to check for memory errors:

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

Activity 3: Findit (3 Points)

Once you have implemented the singly linked list and the Filter functions, you can complete the findit utility:

# Display usage message
$ ./findit
Usage: findit PATH [OPTIONS]

Options:

   -type [f|d]    File is of type f for regular file or d for directory
   -name pattern  Name of file matches shell pattern
   -executable    File is executable or directory is searchable by user
   -readable      File is readable by user
   -writable      File is writable by user

# Display only files
$ ./findit .
./list.c
./list.unit
./Makefile.template
./filter.c.template
...

# Display only .c files
$ ./findit . -name '*.c'
./list.c
./filter.unit.c
./findit.c
./filter.c
./list.unit.c

# Display only executable files
$ ./findit . -type f -executable
./list.unit
./findit
./list.unit.sh
./findit.test.sh
./filter.unit.sh
./filter.unit

As with the find program, findit takes the PATH of the directory to recursively search as its first argument and then any options the user wishes to specify to filter the found entries. For findit, you only need to support the options shown above, which should correspond to a Filter function you implemented in Activity 2.

Task 1: findit.c

The findit.c file contains the C implementation for the findit program. For this task, you will need to implement the following functions:

  1. void find_files(const char *root, List *files)

    This function recursively walks the given root directory and adds any entries it finds to the given List of files.

    Hint: Consider using opendir, readdir, and closedir as you did for walk in Reading 11. When recursing on a directory, make sure to use the full path.

    When adding the full path to the List of files, consider using strdup.

    Moreover, consider when to add the root itself to files.

  2. void filter_files(List *files, List *filters, Options *options)

    This function applies each Filter function in filters with the given Options to the List of files.

    Hint: Consider using list_filter.

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

    This function parses the command line options, finds the files recursively, applies any filters, and then prints out the found files.

    Hint: Consider creating a List of files, a List of filters, and an Options structure. As you parse the command line options, set the appropriate attributes in the Options structure and add the corresponding Filter function to your List of filters.

    After parsing the command line options, you should then use find_files, filter_files, and then list_output.

    Be sure to deallocate any resources you allocated on the heap.

Task 2: Testing

To test your findit utility, you can use the provided findit.test.sh script:

# Build test artifacts and run test scripts
$ make test-findit
Testing findit utility...
 findit                                                       ... Success
 findit (valgrind)                                            ... Success
 findit /etc                                                  ... Success
 findit /etc  (valgrind)                                      ... Success
 findit /etc -type f                                          ... Success
 findit /etc -type f (valgrind)                               ... Success
 findit /etc -type d                                          ... Success
 findit /etc -type d (valgrind)                               ... Success
 findit /etc -name '*.conf'                                   ... Success
 findit /etc -name '*.conf' (valgrind)                        ... Success
 findit /etc -readable                                        ... Success
 findit /etc -readable (valgrind)                             ... Success
 findit /etc -writable                                        ... Success
 findit /etc -writable (valgrind)                             ... Success
 findit /etc -executable                                      ... Success
 findit /etc -executable (valgrind)                           ... Success
 findit /etc -type d -name '*.d'                              ... Success
 findit /etc -type d -name '*.d' (valgrind)                   ... Success
 findit /etc -type d -name '*.d' -executable                  ... Success
 findit /etc -type d -name '*.d' -executable (valgrind)       ... Success
 findit . -name '*.c'                                         ... Success
 findit . -name '*.c' (valgrind)                              ... Success
 findit . -writable                                           ... Success
 findit . -writable (valgrind)                                ... Success
 findit . -type f -name '*.unit' -executable                  ... Success
 findit . -type f -name '*.unit' -executable (valgrind)       ... Success

   Score 3.00 / 3.00
  Status Success

# Run test script manually $ ./findit.test.sh

Activity 4: 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 homework08/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 test your quiz, you can use the check.py script:

$ ../.scripts/check.py
Checking homework08 quiz ...
    Q01 0.20
    Q02 1.20
    Q03 0.20
    Q04 0.40
  Score 2.00 / 2.00
 Status Success

Guru Point: Open Source Software Development (2 Points)

For extra credit, you most make a reasonable contribution to one of the following open source projects:

Note: The groups will soon provide videos describing their projects, which will be embedded below.

Likewise, some links are broken... they will be updated and fixed soon.

WISSH

DocuDump

Creativity Optional

Odyssey

Babel World

Branches of Fate

AdVisor

Bookworm

Human Resources

Atlas

Cardtorium

Note: These are student projects from CSE 40677 Open Source Software Development.

Each of the projects above has a GitHub repository that you can explore. To make a contribution, you will need to fork a repository and try to tackle one of the issues marked as "good first issue".

You will receive one point for making a reasonable attempt at contributing to one of the projects above (ie. a bug report or a pull request). You will receive a second point if the project maintainers acknowledge or approve of your contribution (may require responding to some feedback).

Verification

To get credit for this Guru Point, you must show a proof of (1) your reasonable attempt at a contribution (ie. bug report or pull request)., (2) acknowledgment from the project maintainers of your contribution (ie. verified bug report or merged pull request). You have up until two weeks after this assignment is due to verify your Guru Point.

Submission

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

Note: You do not need to commit the test scripts because the Makefile automatically downloads them.

#-----------------------------------------------------------------------
# Make sure you have already completed Activity 0: Preparation
#-----------------------------------------------------------------------
...
$ git add Makefile                        # Mark changes for commit
$ git add list.c                          # Mark changes for commit
$ git commit -m "homework08: Activity 1"  # Record changes
...
$ git add Makefile                        # Mark changes for commit
$ git add filter.c                        # Mark changes for commit
$ git commit -m "homework08: Activity 2"  # Record changes
...
$ git add Makefile                        # Mark changes for commit
$ git add findit.c                        # Mark changes for commit
$ git commit -m "homework08: Activity 3"  # Record changes
...
$ git add answers.json                    # Mark changes for commit
$ git commit -m "homework08: Activity 4"  # Record changes
...
$ git push -u origin homework08           # Push branch to GitHub

Pull Request

Remember to create a Pull Request and assign the appropriate TA from the Reading 11 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.