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 get up to speed using C and refresh your knowledge of pointers, struct's, 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 Use a cross platform build system
• 5.2 Use a professional 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 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 setup and ready to use. The steps below show you how to use and setup GitHub codespaces. You are not required to use codespaces, all the steps below can be completed in the CS Lab or on your personal machine if you prefer.

Fork the starter repository

1. Fork the starter repository into your personal GitHub account: https://github.com/shanep/makefile-project-starter

2. In the new fork name the repository cs452-p2

Start a new Codespace

We will use GitHub Codespaces to do most of our coding. Codespaces is just VSCode in the cloud. This makes it really easy to setup a developer environment and code from any computer that has a browser and internet connection!

1. 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.

You now should have a new repository (forked from the starter template) that is ready to use.

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 test. You will not need to use the file app/main.c all your work will be done int src/lab.c and tests/test-lab.c

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 *);                  /*free's 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
    * 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 and all associated data. This functions will call
     * destroy_data on each nodes 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/test-lab.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 fuctions
  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_invaidIndex(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;
    }

  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 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;
  size_t 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);
  size_t 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_invaidIndex);
  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 lets make your first commit so everything is saved. Open up a terminal and lets 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/test-lab.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 submit your code as a patch so you can receive a grade for all your hard work.

Turn on Two Factor

Turn on Two factor authentication for your Boise State provided email account

DANGER

Do NOT skip this step. Boise State University uses Gmail as their email provider and Gmail requires you to use two factor authentication in order to generate an app password.

You need to use your Boise State University issued email account to send the email and you must have two factor authentication turned on.

Generate an app password

INFO

If you are working in GitHub codespaces you will need to setup SMTP for EACH project. This is because each codespace is tied to a specific repository and the settings are not shared. However, if you are working on your own personal machine or in the CS Lab then you will only have to setup SMTP once!

In order to use git send-email you will need to generate an app password. Navigate to https://security.google.com/settings/security/apppasswords and generate a new app password. Make sure and copy the password before you close the window because you will not be able to see it again.

I can't generate a password

If you get the error shown below it typically means that you have not enabled two factor authentication. Follow these steps to resolve the issue:

1. Go back and ensure you have two factor authentication enabled.
2. Log out of your Gmail account
3. Log back into your Gmail account and make sure you did have to use two factor authentication
4. If the steps above fail then open an incognito tab and go back to the first step
5. If you still have issues reboot your machine and go back to the first step

Setup SMTP

1. Open up a terminal in codespaces

2. In the terminal type git config --global --edit and modify the file with the info listed below. You will need to change the info listed below to match your own name, email and App Password that you generated in the previous step.

[User]
	name =  YOUR NAME
	email = YOURNAME@u.boisestate.edu
[sendemail]
	smtpserver = smtp.gmail.com
	smtpuser = YOURNAME@u.boisestate.edu
	smtpPass = xxxx xxxx xxxx xxxx
	smtpencryption = ssl
	smtpserverport = 465

Congrats you should be all setup to send code patch's over email. Now lets create a patch!

Create a patch file

We are now going to do what is called a squash merge and then create a patch file with all our changes in one commit.

1. First lets fetch the upstream branch. This is the branch that you originally forked from at the start of the project

git fetch upstream

2. Checkout a new branch named submit from the upstream/master branch.

git checkout upstream/master -b submit

3. Now we will do a squash merge all the commits we did onto our new submit branch.

git merge --squash master

4. Now commit those new changes to your submit branch

git commit -m "Submit project"

5. Push your submit branch to GitHub

git push -u origin

6. Open up a web browser and navigate to your repository on GitHub and confirm that your submit branch is correctly pushed. Open up the files and make sure that everything looks good before going to the next step.

Install Libraries

If you are working on codespaces you will need to install the required dependencies before you attempt to email out your patch file.

make install-deps

Email Patch File

First make sure you are still on the submit branch that you created. If you type git branch you should see a star next to the submit branch that indicates you are currently on the submit branch.

$ git branch
  master
* submit

WARNING

You MUST test your patch by emailing it to yourself first! You will go through all the steps below with your own email. After you have sent the email to yourself and tested it you can then email your submission to the class mailing list!

Finally we can create our patch to email out!

git send-email --to youremail@u.boisestate.edu HEAD^

You should see results similar to what is show below.

$ git send-email --to youremail@u.boisestate.edu HEAD^
/tmp/T/NWEw4f1sIj/0001-Submit-project-2.patch

From: youremail@u.boisestate.edu
To:  youremail@u.boisestate.edu
Subject: [PATCH] Submit project
Date: Thu,  7 Dec 2023 20:31:55 -0700
Message-Id: <20231208033155.83099-1-shanepanter@boisestate.edu>
X-Mailer: git-send-email 2.39.3 (Apple Git-145)
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

The Cc list above has been expanded by additional
addresses found in the patch commit message. By default
send-email prompts before sending whenever this occurs.
This behavior is controlled by the sendemail.confirm
configuration setting.

For additional information, run 'git send-email --help'.
To retain the current behavior, but squelch this message,
run 'git config --global sendemail.confirm auto'.

Send this email? ([y]es|[n]o|[e]dit|[q]uit|[a]ll): y
OK. Log says:
Server: smtp.gmail.com
MAIL FROM:  youremail@u.boisestate.edu
RCPT TO:  youremail@u.boisestate.edu
RCPT TO:  youremail@u.boisestate.edu
From: youremail@u.boisestate.edu
To:  youremail@u.boisestate.edu
Subject: [PATCH] Submit project 2
Date: Thu,  7 Dec 2023 20:31:55 -0700
Message-Id: <20231208033155.83099-1-shanepanter@boisestate.edu>
X-Mailer: git-send-email 2.39.3 (Apple Git-145)
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

Result: 250

You should now be able to check your email and see your patch. Be aware that sometimes email delivery is slightly delayed so you may have to wait a few minutes for it to show up. Make sure and check your spam folder if you don't see any mail.

Test your patch

You can now get your patch from Gmail and test it to make sure that everything works and your patch was correct.

1. Checkout a new branch named test-patch from the upstream/master branch

git checkout upstream/master -b test-patch

2. Push your new test-patch branch to your repo instead of the upstream

 git push -u origin

3. Get the patch file from Gmail

4. Copy the email to your clip board

5. Create a new file and paste the contents that you just copied and save it in the root folder in a file named my-patch.txt.

6. Make sure you saved the file correctly. It should show up in the file explorer as shown below.

7. Now apply that patch to your new test-patch branch

git am my-patch.txt

8. Commit your patch

git commit -m "Testing my email patch"

9. Push your test patch branch to your Github Account

git push

10. After you have successfully applied the patch you can delete the file my-patch.txt. Don't commit the file my-patch.txt it is just a temporary file that you don't want to save.

11. Finally open up the browser again and make sure you have 3 branches master, submit, and test-patch. The submit and test-patch branches should be identical. Each should have exactly 1 commit from you with all your changes.

Submit your Patch for grading

Assuming you have successfully completed all the steps above with your own email and everything looked good you can now submit your patch for grading.

DANGER

Do not use the class mailing list to test your patch. You should only send an email to email is in the syllabus after you have tested the process with your own email. Spamming the mailing list with excessive patches will result in a lower grade.

When you submit to the mailing list you will automatically be cc'd on the email so you will have a copy in your own email as proof that you completed the assignment.

You are allowed to submit up to 3 times without penalty.

Open a terminal and submit your patch.

git checkout submit
git send-email --to email is in the syllabus HEAD^

Assuming all went well you are now complete! You have created a patch file from a squash merge, emailed it and tested the resulting patch. You are well on your way to becoming an advanced git user!

Submitting

You do not need to submit anything to canvas for this assignment. Your email is your submission, your grade will be updated after the due date (and late window) have passed.