Homework 8 - Simple File System

From now on, we’ll assume that you work on homework by connecting to the CS portal and that you are familiar with the command line environment. If you have not been practicing with the terminal, we strongly encourage reviewing Lab 1.

We will also assume that you ran the setup script from that lab and have all modules (including clang and git) by default.

In this homework, you will implement a simplified file system consisting of directories and files. You will need to use malloc and free to store the nodes for both files and directories on the heap, using a linked list data structure in C.

Getting the starter code

In order to get our starter code for this homework, you’ll need to copy our starter code into your home directory. Use cd to enter your cso1-code directory, then issue the following command to copy our code.

gethomework8

Now you have two files, a filesystem.c file containing functions to implement and a filesystem.h header file declaring the structs and functions with documentation.

Writing your code

For this assignment, we are expecting that you will write your code in a command-line editor (vim, nano, etc) on the portal. If you need to refresh, please review Lab 1.

Using an IDE (such as Visual Studio Code, IntelliJ IDEA, etc), an online editor or compiler, or Generative AI will result in an immediate 0 on the assigment. Sorry to be strict on this, but one of the goals of this course is to gain familiarity with command-line tools. We’ll get to VSCode very soon.

Why a CLI editor?

It is common to interact with servers that do not have their own monitors. In these cases, you typically attach to the server via ssh and have access only to a terminal, not a full windowing environment. The more comfortable you are with doing common programming tasks in the terminal, the better these experiences will be.

Compiling your code

Since the header file filesystem.h should be included in your C file, you only need to compile the C file with clang.

Task

Edit the C file named filesystem.c that contains implementations of functions for manipulating the lists of files and directories as described and declared in the header file filesystem.h.

A linked list is a collection of nodes (typically defined in C using structs) where each node has a pointer to the next node in the list. The tail node (i.e., the next pointer of the last node in the linked list) has a NULL next pointer indicating that there is nothing after it.

Your code in filesystem.c should begin by including the given header file, #include "filesystem.h". We will assume you use this exact filesystem.h when testing your code; if you change it, we will not use those changes in our compilation and testing of your code. Comments in filesystem.h describe what each function is supposed to do.

To get you started, here is one of the functions required for the simplified file system implementation, fully and correctly implemented for you; it has also been included in the filesystem.c file. This function is recursive, which means it calls itself as it traverses each sub-directory. That is, this code prints out the subdirectories and files in the filesystem starting at the directory node provided as a parameter, and it calls itself to print out the subdirectories and files of each of its subdirectories (and so on).

/* reference solution provided with assignment description */
void directory_list(dir_node *root, int indent) {
  // Stop if the root is null (nowhere to go)
  if (root == NULL)
    return;

  // If indent is 0, we need to start at 4 for correct indentation
  if (!indent)
    indent = 4;
  
  // Print the current directory node
  printf("%*s %s (%ld entries)\n", indent, "-(D)", root->name, dir_entries(root));

  // Recursively print the subdirectories and their contents
  indent += 4;
  for (dir_node *i = root->subdirs; i != NULL; i = i->next) {
    directory_list(i, indent);
  }

  // Print out the files (no recursion needed)
  for (file_node *i = root->files; i != NULL; i = i->next) {
    printf("%*s %s (%d bytes)\n", indent, "-(F)", i->name, i->size);
  }
}

Note: we are not asking you to write recursive functions for this assignment, however you may want to write a similar function to this one that also prints out additional information for debugging, such as pointers.

Testing your code

You should manually test your code, including using the lldb debugger and/or the debugging function provided below. Test all of the corner cases (NULL arguments; first-, last-, and middle-node arguments, finding files and directories not in the system, etc). Do NOT rely on Gradescope to be your compiler and tester! The Gradescope submission site will open on Wednesday and will only allow a total of 15 submissions.

Example testing code

We have also provided an example of some test code in the provided main function. Once everything is implemented correctly, this code:

int main(int argc, const char *argv[]) {

  //TODO: test your code more than this
  dir_node *d = create_dir("Top");
 
  dir_node *fd = insert_dir(d, "First Dir", NULL);
  dir_node *sd = insert_dir(d, "Second Dir", "First Dir"); 

  insert_file(d, "First File", 42, NULL);
  insert_file(fd, "Second File", 67, NULL);
  insert_file(fd, "Third File", 21, "Second File");
  insert_file(sd, "Fourth File", 0, NULL);

  // print the directory listing starting at the root for sd
  directory_list(root_dir(sd), 0);
  
  return 0;
}

should display:

-(D) Top (3 entries)
    -(D) First Dir (2 entries)
        -(F) Second File (67 bytes)
        -(F) Third File (21 bytes)
    -(D) Second Dir (1 entries)
        -(F) Fourth File (0 bytes)
    -(F) First File (42 bytes)

Example (and Real) Test

One of the more difficult functions to implement will be the remove_dir function, which must update quite a few pointers correctly. To help you with testing that, we’re providing (most) of the actual code from the autograder. You absolutely should test your code with this before uploading it to Gradescope.

void test_remove_dir() {
    dir_node *first = remove_dir(NULL, NULL);
    dir_node *f0 = ref_create_dir("example");

    dir_node *d = ref_create_dir("Dir A");
    dir_node *second = remove_dir(d, NULL);
    dir_node *third = remove_dir(d, f0);
    
    dir_node *e = ref_create_dir("Dir B");
    dir_node *f1 = ref_insert_dir(e, "f1", NULL);
    dir_node *fourth = remove_dir(e, f0);
    dir_node *fifth = remove_dir(e, f1);

    puts("remove_dir zero or one:");
    
    if (first != NULL) puts("- wrong value on NULL directory");
    else if (second != NULL) puts("- wrong value on NULL dir");
    else if (third != NULL) puts("- wrong value on dir not in list");
    else if (fourth != NULL) puts("- wrong value on dir not in list 2");
    else if (fifth != NULL) puts("- wrong value when removing only dir");
    else if (e->subdirs != NULL) puts("- did not update directory");
    else puts("+ passed all tests");
}

Tips

  1. I have yet to see a student implement their first correct linked list without drawing box-and-arrow pictures.

  2. Debugging can be easier if you can see all of the pointers involved. You may want to write your own directory_list function similar to the one above that also prints the addresses of each node and its pointers.

  3. Don’t use after free! We will test your code with the address sanitizer enabled and may also manually check for additional memory errors.

Grading

For this assignment, the grade will consist of an autograded component (for correctness) and a code style grade. The breakdown is as follows:

  • 85% code correctness (passing Gradescope tests)
  • 5% well indented (readable) code
    • You should indent your code as if it were Python; that is, indent whenever you would use curly braces.
  • 5% good variable names
    • Use names that express your code’s meaning.
  • 5% comments
    • Document your code with comments so that you (and we) can better read what you wrote.
    • Write comments that explain any tricky sections as well as tell us (in English) what each section of your code is intended to do.
    • Hint: it might be helpful to write the comments first so that you have a rough sketch of your algorithm before implementation.

Submission

Submit your filesystem.c to Gradescope. You may only submit a maximum of 15 times to the autograder, so you should test your code extensively by calling your functions in main(). After the 15th attempt, Gradescope will accept submissions, but the autograder will not run; Gradescope will only report the score of the 15th attempt.

Note: The submission site will be available beginning on Wednesday.

Copyright © 2025 John Hott, portions Luther Tychonievich.
Released under the CC-BY-NC-SA 4.0 license.
Creative Commons License