Project 2

Overview

This assignment is intended to serve as a warm-up assignment. It may have been a long time since you have written any code in C, so we will get warmed up by writing a circular doubly linked list. This will allow you to get up to speed using C and refresh your knowledge of pointers, structs, and manual memory management.

Learning Outcomes

This project measures the following course learning outcomes:

• 4.1 Produce code that is free of all memory leaks
• 4.2 Produce code without any out of bounds read/write errors
• 5.1 Compile your code with a build system
• 5.2 Use a unit test framework
• 5.3 Use a professional version control system (git)

Grading Rubric

Make sure and review the class grading rubric so you know how your project will be graded.

Circular Linked List with Sentinel Node

It is sometimes helpful to draw out what your data structure will look like in memory before you start coding anything up. Having a visual model to reference can aid in both development and testing. The diagram below shows a list with 3 elements and a sentinel node. You can see that the next pointer in node n3 points back to the sentinel node and the prev pointer of n1 points back to the sentinel node. Each node has a data pointer that will hold a reference to the data that is being stored in the list. Using a sentinel node allows us to write slightly simpler algorithms when manipulating the list.

Thinking in C

Java is an Object Oriented (OO) programming language while C is an imperative language. The purpose of both is to break large computing tasks into smaller ones. While pre-ANSI C (known as K&R C) had very strange function declarations, functions in ANSI C (C89 and greater) have a similar look and feel to Java.

One of the biggest differences between functions in C and methods in Java is that Java groups your functions and data together into a class. So in Java if you want to create a new linked list and then add something to it you would create a new list and then call the add method on that list:

Mylist list = new Mylist();
list.add(new Object());

In C the code above would be written as follows:

struct object *obj = create_object();
struct mylist *list = create_list();
list_add(list, obj);

So as you can see with the examples above any code that is written in Java using objects can be translated to C!

Task 1 - Setup

Follow the steps below to get your repository all set up and ready to use. The steps below show you how to use and set up GitHub Codespaces. You are not required to use Codespaces. All the steps below can be completed on Onyx (the CS lab machines) or on your personal machine if you prefer.

Create your repository from the template

The starter repository is a GitHub template, so you make your own copy of it instead of forking it.

1. Open the starter repository: https://github.com/shanep/makefile-project-starter
2. Click the green Use this template button and choose Create a new repository.
3. Pick your personal GitHub account as the owner and name the repository cs452-p2.
4. Click Create repository.

Your new repository is not a fork, so it has no upstream remote. That is on purpose: everything you need is already in your copy.

Start a new Codespace

We will use GitHub Codespaces to do most of our coding. Codespaces is just VS Code in the cloud. This makes it really easy to set up a developer environment and code from any computer that has a browser and internet connection! From your new repository click Code, then the Codespaces tab, then Create codespace on master.

If you are asked to install recommended extensions, click "install". You may not be asked to install extensions if you are already syncing your account.

INFO

If you work on Onyx or your own machine instead, clone your repository with git clone and make sure you have gcc (or clang), make, and gcovr installed. The Codespace comes with all of these. The file docs/onyx.md in your repository has notes on using Onyx.

Get to know the starter

Here is what you get in the starter repository.

• src/main.c - the main function for the executable
• src/lab.h and src/lab.c - the library code that both the executable and the tests use
• tests/lab-test.c - your unit tests, written with the Unity test framework
• tests/harness/ - the Unity framework itself, don't edit these files
• README.md - you will fill this out before you submit
• scripts/create-submission-report.sh and .github/workflows/ - continuous integration and the submission report

The Makefile builds every C file in src/ and tests/. The test build defines TEST, and src/main.c uses that to rename its main function so it does not clash with the main in tests/lab-test.c. Keep these lines at the top of src/main.c in every project.

#ifdef TEST
#define main main_exclude
#endif

These are the make targets you will use the most. Run make help to see them all.

Command	What it does
make all	Builds all four versions of the project listed below
make check	Runs the unit tests in build/tests/myapp_t
make leak	Runs the debug executable with Address Sanitizer leak checking on
make leak-test	Runs the unit tests with Address Sanitizer leak checking on
make report	Runs the unit tests and creates a code coverage report in build/report
make clean	Deletes the build directory

make all creates four programs.

• build/release/myapp - the optimized executable, compiled with all the warning flags
• build/debug/myapp_d - the executable compiled with Address Sanitizer
• build/tests/myapp_t - the unit tests compiled for code coverage
• build/debug-test/myapp_td - the unit tests compiled with Address Sanitizer

If there is no src/main.c then make all skips the executable and only builds the tests. That is how the projects that are 100% unit tests work.

WARNING

make check, make leak, make leak-test, and make report run whatever is already in build/. They do not recompile your code. Run make all after every change or you will be testing old code. Also, make all prints "Builds completed" even when one of the builds failed, so scroll up and read the output.

Task 2 - Prepare your repository

The starter repository is a bare bones template that you will need to update with the starter code below.

INFO

This project will be 100% unit tests. All your work will be done in src/lab.c and tests/lab-test.c, so delete the file src/main.c and the get_greeting function in src/lab.c. Without a src/main.c the make all command only builds the tests.

src/lab.h

#ifndef LAB_H
#define LAB_H
#include <stdlib.h>
#include <stdbool.h>

#ifdef __cplusplus
extern "C"
{
#endif

    /**
     * @brief A node in the list
     *
     */
    typedef struct node
    {
        void *data;
        struct node *next;
        struct node *prev;
    } node_t;

    /**
    * @brief Struct to represent a list. The list maintains 2 function pointers to help
    * with the management of the data it is storing. These functions must be provided by the
    * user of this library.
    */
    typedef struct list
    {
        void (*destroy_data)(void *);                  /*frees any memory that data allocated*/
        int (*compare_to)(const void *, const void *); /* returns 0 if data are the same*/
        size_t size;                                   /* How many elements are in the list */
        struct node *head;                             /* sentinel node*/
    } list_t;

    /**
    * @brief Create a new list with callbacks that know how to deal with the data that
    * the list is storing. The caller must pass the list to list_destroy when finished to
    * free any memory that was allocated.
    *
    * @param destroy_data Function that will free the memory for user supplied data
    * @param compare_to Function that will compare two user data elements
    * @return struct list* pointer to the newly allocated list.
    */
    list_t *list_init(void (*destroy_data)(void *),
                                 int (*compare_to)(const void *, const void *));

    /**
     * @brief Destroy the list and all associated data. This function will call
     * destroy_data on each node's data element.
     *
     * @param list a pointer to the list that needs to be destroyed
     */
    void list_destroy(list_t **list);

    /**
     * Adds data to the front of the list
     *
     * @param list a pointer to an existing list.
     * @param data the data to add
     * @return A pointer to the list
     */
    list_t *list_add(list_t *list, void *data);

    /**
     * @brief Removes the data at the specified index. If index is invalid
     * then this function does nothing and returns NULL
     *
     * @param list The list to remove the element from
     * @param index The index
     * @return void* The data that was removed or NULL if nothing was removed
     */
    void *list_remove_index(list_t *list, size_t index);

    /**
     * @brief Search for any occurrence of data from the list.
     * Internally this function will call compare_to on each item in the list
     * until a match is found or the end of the list is reached. If there are
     * multiple copies of the same data in the list the first one will be returned.
     *
     * @param list the list to search for data
     * @param data the data to look for
     * @return The index of the item if found or -1 if not
     */
    int list_indexof(list_t *list, void *data);



#ifdef __cplusplus
} //extern "C"
#endif

#endif

tests/lab-test.c

#include "harness/unity.h"
#include "../src/lab.h"


static list_t *lst_ = NULL;

static int *alloc_data(int i)
{
  int *rval = (int *)malloc(sizeof(int));
  *rval = i;
  return rval;
}

static void destroy_data(void *data)
{
  free(data);
}

static int compare_to(const void *a, const void *b)
{
  int fst = *(int *)a;
  int snd = *(int *)b;
  return fst - snd;
}

static void populate_list(void)
{
  for (int i = 0; i < 5; i++)
    {
      list_add(lst_, alloc_data(i));
    }
}


void setUp(void) {
  lst_ = list_init(destroy_data, compare_to);
}

void tearDown(void) {
  list_destroy(&lst_);
}


void test_create_destroy(void)
{
  list_t *lst = NULL;
  lst = list_init(destroy_data, compare_to);
  TEST_ASSERT_FALSE(lst == NULL);
  TEST_ASSERT_FALSE(lst->head == NULL);
  TEST_ASSERT_TRUE(lst->size == 0);
  TEST_ASSERT_TRUE(lst->head->data == NULL);
  //Make sure the function pointers are pointing to the correct functions
  TEST_ASSERT_TRUE(lst->destroy_data == destroy_data);
  TEST_ASSERT_TRUE(lst->compare_to == compare_to);

  //Make sure we are a circular linked list
  TEST_ASSERT_FALSE(lst->head->next == NULL);
  TEST_ASSERT_FALSE(lst->head->prev == NULL);
  TEST_ASSERT_TRUE(lst->head->next == lst->head->prev);

  list_destroy(&lst);
  TEST_ASSERT_TRUE(lst == NULL);
}


void test_add1(void)
{
  list_add(lst_, alloc_data(1));
  TEST_ASSERT_TRUE(lst_->size == 1);
  //With one node both next and prev should be equal
  TEST_ASSERT_TRUE(lst_->head->next == lst_->head->prev);
  //Make sure we didn't clobber our sentinel node
  TEST_ASSERT_FALSE(lst_->head == lst_->head->next);
  TEST_ASSERT_FALSE(lst_->head == lst_->head->prev);
  TEST_ASSERT_TRUE(lst_->head->data == NULL);

  //Check to make sure our data actually made it into the node
  TEST_ASSERT_TRUE(*((int *)lst_->head->next->data) == 1);
  TEST_ASSERT_TRUE(*((int *)lst_->head->prev->data) == 1);
}

void test_add2(void)
{
  list_add(lst_, alloc_data(1));
  TEST_ASSERT_TRUE(lst_->size == 1);
  list_add(lst_, alloc_data(2));
  TEST_ASSERT_TRUE(lst_->size == 2);

  //With two nodes both next and prev should NOT be equal
  TEST_ASSERT_FALSE(lst_->head->next == lst_->head->prev);
  //Make sure we didn't clobber our sentinel node
  TEST_ASSERT_FALSE(lst_->head == lst_->head->next);
  TEST_ASSERT_FALSE(lst_->head == lst_->head->prev);
  TEST_ASSERT_TRUE(lst_->head->data == NULL);

  //Check to make sure our next and prev have the correct data
  TEST_ASSERT_TRUE(*((int *)lst_->head->next->data) == 2);
  TEST_ASSERT_TRUE(*((int *)lst_->head->prev->data) == 1);
}


void test_removeIndex0(void)
{
  populate_list();
  int *rval = (int *)list_remove_index(lst_, 0);
  TEST_ASSERT_TRUE(lst_->size == 4);
  TEST_ASSERT_TRUE(*rval == 4);
  free(rval);

  node_t *curr = lst_->head->next;
  //List should be 3->2->1->0
  for (int i = 3; i >= 0; i--)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i);
      curr = curr->next;
    }
  curr = lst_->head->prev;
  for (int i = 0; i <= 3; i++)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i);
      curr = curr->prev;
    }
}

void test_removeIndex3(void)
{
  populate_list();
  int *rval = (int *)list_remove_index(lst_, 3);
  TEST_ASSERT_TRUE(lst_->size == 4);
  TEST_ASSERT_TRUE(*rval == 1);
  free(rval);

  node_t *curr = lst_->head->next;
  //List should be 4->3->2->0
  for (int i = 3; i >= 1; i--)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i + 1);
      curr = curr->next;
    }
  //Check the last one
  TEST_ASSERT_TRUE(*((int *)curr->data) == 0);

  //Set the curr back one node so we can check prev links
  curr = curr->prev;
  for (int i = 1; i <= 3; i++)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i + 1);
      curr = curr->prev;
    }
}


void test_removeIndex4(void)
{
  populate_list();
  int *rval = (int *)list_remove_index(lst_, 4);
  TEST_ASSERT_TRUE(lst_->size == 4);
  TEST_ASSERT_TRUE(*rval == 0);
  free(rval);

  node_t *curr = lst_->head->next;
  //List should be 4->3->2->1
  for (int i = 3; i >= 0; i--)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i + 1);
      curr = curr->next;
    }
  curr = lst_->head->prev;
  for (int i = 0; i <= 3; i++)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i + 1);
      curr = curr->prev;
    }
}


void test_invalidIndex(void)
{
  populate_list();
  void *rval = list_remove_index(lst_, 666);
  TEST_ASSERT_TRUE(rval == NULL);
  TEST_ASSERT_TRUE(lst_->size == 5);

  node_t *curr = lst_->head->next;
  //List should be 4->3->2->1->0
  for (int i = 4; i >= 0; i--)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) ==  i);
      curr = curr->next;
    }
  curr = lst_->head->prev;
  for (int i = 0; i <= 4; i++)
    {
      TEST_ASSERT_TRUE(*((int *)curr->data) == i);
      curr = curr->prev;
    }
}

void test_removeAll(void)
{
  populate_list();
  //List should be 4->3->2->1->0
  for (int i = 4; i >= 0; i--)
    {
      int *rval = (int *)list_remove_index(lst_, 0);
      TEST_ASSERT_TRUE(*rval == i);
      free(rval);
    }

  //Make sure we are back to default
  TEST_ASSERT_FALSE(lst_->head->next == NULL);
  TEST_ASSERT_FALSE(lst_->head->prev == NULL);
  TEST_ASSERT_TRUE(lst_->head->next == lst_->head->prev);
  TEST_ASSERT_TRUE(lst_->size == 0);
}

void test_indexOf0(void)
{
  populate_list();
  //List should be 4->3->2->1->0
  void *data = lst_->head->next->data;
  int idx = list_indexof(lst_, data);
  TEST_ASSERT_TRUE(idx == 0);
}

void test_indexOf3(void)
{
  populate_list();
  //List should be 4->3->2->1->0
  void *data = alloc_data(1);
  int idx = list_indexof(lst_, data);
  TEST_ASSERT_TRUE(idx == 3);
  free(data);
}

void test_notInList(void)
{
  populate_list();
  void *data = alloc_data(22);
  int idx = list_indexof(lst_, data);
  TEST_ASSERT_EQUAL_INT64(-1, idx);
  free(data);
}

int main(void) {
  UNITY_BEGIN();
  RUN_TEST(test_create_destroy);
  RUN_TEST(test_add1);
  RUN_TEST(test_add2);
  RUN_TEST(test_removeIndex0);
  RUN_TEST(test_removeIndex3);
  RUN_TEST(test_removeIndex4);
  RUN_TEST(test_invalidIndex);
  RUN_TEST(test_removeAll);
  RUN_TEST(test_indexOf0);
  RUN_TEST(test_indexOf3);
  RUN_TEST(test_notInList);
  return UNITY_END();
}

Once you have updated all the starter code let's make your first commit so everything is saved. Open up a terminal and let's make a commit!

git add --all
git commit -m "Added in starter code"

Task 3 - Implement the header file

Implement all the functions defined in src/lab.h in src/lab.c.

Task 4 - Write Unit tests

Open up the file tests/lab-test.c and add at least 4 new tests beyond what is already provided.

Final Task - Submit your code

Now that you have completed all the tasks, the only thing left to do is to create a submission report and upload it to Canvas so you can receive a grade for all your hard work.

Update your README

Open up README.md and fill in every section.

• Your name, email, and class section at the top
• Known Bugs or Issues - anything that does not work
• Experience - your struggles and breakthroughs with the project
• Analysis - only if the project asks for one, otherwise delete the section

Check your build

Run the same commands that the continuous integration (CI) workflow runs and make sure you get a clean build with no warnings, all tests passing, and no Address Sanitizer errors.

make clean
make all
make check
make leak-test

Then run make report and look at the coverage numbers at the bottom of the output. The grading rubric explains how coverage is graded.

Push and check CI

Commit and push all your work.

git add --all
git commit -m "Finished the project"
git push

Open your repository on GitHub, click the Actions tab, then Continuous Integration (CI), and confirm that the run for your last push is green. If it is not, open the run, read the output, and fix the problem.

Create the submission report

1. In the Actions tab click Create Submission Report Via GitHub Action.
2. Click Run workflow and run it on the master branch.
3. Wait for the run to finish and then refresh your repository. You will now have a file named submission-report.docx that contains your README, the build output, the test results, the coverage report, the Address Sanitizer report, and all your code.
4. The workflow added a commit to your repository, so run git pull in your Codespace (or wherever you cloned the repository) before you make any more changes. If you skip this, your next push will be rejected.

DANGER

Do NOT edit the generated report. The report ends with a hash of its contents and any changes will be reported as academic dishonesty. If something in the report is wrong, fix your code, push, and run the workflow again.

GitHub Actions is down

If GitHub Actions is down, or the workflow hangs for more than 5 minutes, you can generate the report on Onyx instead. Follow the steps in docs/onyx.md in your repository, which install gcovr and run scripts/create-submission-report.sh.

Submitting

Download submission-report.docx from GitHub and submit it to Canvas. You can view your own submission in Canvas, so open it and make sure everything looks right. Your grade will be updated after the due date (and late window) has passed.