# 2019q3 Homework2 (lab0)
###### contributed by < `tommywang0tw` >
###### tags: 王志瑋

## Homework Requirement
###### reference: [C programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
### Task
1. Modify the code in `queue.h` and `queue.c` to fully implement the following functions:
* q_new: Create a new, empty queue.
* q_free: Free all sorage used by a queue.
* q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
* q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
* q_remove_head: Attempt to remove the element at the head of the queue.
* q_size: Compute the number of elements in the queue.
* q_reverse: Recorder the list so that the queue elements are reversed in order (It should rearrange the existing elements).
2. Test
* Compile the code using this command: `linux> make`
* Implement the executable file which is generated by the compiler by using `linux> ./qtest`
* Test the effect of the code and debug
* Evaluate the program by using `linux> make test`
* Try to get the perfect score

### Skills Tested:
* Explicit memory management, as required in C.
* Creating and manipulating pointer-based data structures.
* Working with strings.
* Enhancing the performance of key operations by storing redundant information in data structures.
* Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

## Functions Implementation
### Queue structure
In order to efficiently implement `q_size` and `q_insert_tail`, we add a pointer called **tail** to point the end of the queue and a integer called **size** to record the size of this queue.
##### Code:

typedef struct {
    list_ele_t *head; /* Linked list of elements */
                      /*
                        You will need to add more fields to this structure
                        to efficiently implement q_size and q_insert_tail
                      */
    list_ele_t *tail;
    int size;
} queue_t;

### `q_new`
#### Expected functionality
* Set the initial condition
* Allocate space for this queue structure, and it should be able to handle malloc failure
#### Code
We allocate space for this queue structure and make the head pointer point to NULL. If the malloc fails, the pointer q would be assigned NULL. We use this attribute to detect malloc failure.

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
    {
      printf("can't allocate space for the queue.\n");
      return NULL;
    }
    q->head = NULL;
    return q;
}

### `q_free`
#### Expected functionality
* Handle if the input queue doesn't exist
* Free all storage used by queue, including the queue structure, every elements, and those strings pointed by each element
#### Code
In this code, we use two pointer(temp, prev) to go through this queue. Prev points to the element temp just went through. Everytime when temp goes through a element, we free the string that element points to. After that, prev will go through this element and free it.

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /*Do nothing if the queue doesn't exist*/
    if (q == NULL) {
        return;
    }
    /*Use pointer temp to go through the whole
     queue and free the strings*/
    /*Use prev pointer to access the elements which 
    temp just deleted their value, then we free the element*/
    list_ele_t *prev = q->head;
    list_ele_t *temp = q->head;
    while (temp != NULL) {
        free(temp->value);
        prev = temp;
        temp = temp->next;
        free(prev);
    }
    free(q);
}

### `q_insert_head`
#### Expected Functionality
* Allocate space for the element and the string which is going to be pointed by that element
* copy the input string to the allocated space
* Handle queue non-existing situation
* Handle empty queue situation
* Handle malloc failure
#### Code
First, we handle the special conditions like: queue doesn't exist(q == NULL), malloc failure when allocating space for string or element. Note that, at line 29, we need to free the space we just allocated or it would be memory leak.
Then we need to do the right move corresponding two situations: queue is empty or not. If it is, we need to point both the head and tail pointer to this new element. Also, the new element should point to NULL. If it's not, we make the new element point to the old head element, then point the head point to the new element. (after line 35)

bool q_insert_head(queue_t *q, char *s)
{
    /*Handle q not-existing situation*/
    if (q == NULL) {
        printf("This queue doesn't exist!\n");
        return false;
    }
    list_ele_t *newh;
    int str_size;
    char *copy_s;
    /* If q is NULL, we new a queue and then
    insert the element to the head of this queue*/

    /*Allocate space for the string*/
    str_size = strlen(s) + 1;
    copy_s = malloc(str_size * sizeof(char));
    /*Handle malloc failure*/
    if (copy_s == NULL) {
        printf("Couldn't allocate space for the string!\n");
        return false;
    }
    /*Allocate space for the element*/
    newh = malloc(sizeof(list_ele_t));
    /*Handle malloc failure*/
    if (newh == NULL) {
        printf("Couldn't allocate space for the element!\n");
        /*If this function fails here, we need to
        free the space we allocated above*/
        free(copy_s);
        return false;
    }
    strcpy(copy_s, s);

    newh->value = copy_s;
    /*Handle empty queue situation*/
    if (q->head == NULL) {
        q->tail = newh;
        newh->next = NULL;
    } else /*General situation*/
    {
        newh->next = q->head;
    }
    q->head = newh;

    /*Count size of queue*/
    q->size++;
    return true;
}

### `q_insert_tail`
`q_insert_tail` is highly similar to `q_insert_head`, the functionality is the same and also the special conditions and situations need to be handled. In order to keep this note short, I won't elaborate this function here because the content would be almost the same.

Note: we are required to implement this function in **O(1)**. The key point to do so is in the queue structure declaration. We declared the tail pointer in this structure so that we can easily use the same method as `q_insert_head` and implement this function in constant time.

#### Code

bool q_insert_tail(queue_t *q, char *s)
{
    /*Handle queue not-existing situation*/
    if (q == NULL) {
        printf("This queue doesn't exist!\n");
        return false;
    }
    list_ele_t *newt;
    char *copy_s;
    int str_size;
    str_size = strlen(s) + 1;

    /*Allocate space for the new element and the string will be pointed to*/
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        printf("Couldn't allocate space for the element!\n");
        return false;
    }
    copy_s = malloc(str_size * sizeof(char));
    if (copy_s == NULL) {
        printf("Couldn't allocate space for the string!\n");
        /*If the function fails here, we need to free the space we allocate
        above to avoid memory leaking*/
        free(newt);
        return false;
    }
    strcpy(copy_s, s);
    newt->value = copy_s;
    newt->next = NULL;
    /*Handle empty queue situation*/
    if (q->head == NULL) {
        q->head = newt;
        q->tail = newt;
        q->size++;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

### `q_remove_head`
#### Expected Functionality
* Attempt to remove the element from head of queue, return true if successful, false if queue is NULL or empty
* If the passed pointer sp is non-NULL and the remove is implemented successfully, copy the removed string to it
* Free the space used by the removed element and string

#### Code
First, we use a simple if statement to handle the situations that q is empty or doesn't even exist(`q==NULL or q->head==NULL`). Then we check if sp is non-NULL. If it is, we need to copy the string we are about to remove to sp.
(**Note: we need to put the terminator at the end of string in sp manually because if the size of the removed string is equal or larger than bufsize-1, `strncpy` won't copy the terminator to sp.**)
Then, we can free the space and adjust the pointers to make the linked list still works properly.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /*If queue is empty or NULL*/
    if (q == NULL || q->head == NULL)
        return false;
    /*If sp is non-NULL, copy the string about to be removed to it*/
    /*the maximum copied string size is bufsize-1*/
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    /*Free the space*/
    list_ele_t *temp = q->head;
    q->head = q->head->next;
    free(temp->value);
    free(temp);
    q->size--;
    return true;
}

### `q_size`
#### Expected Functionality
* Calculate and return the current size of this queue
* Return 0 if queue is empty or non-existing
* This function should be implemented in **O(1)**
#### Code
Instead of calculating the size in this function, we **record** the size of the queue everytime we insert or remove an element. To do so, we need to declare an integer called **size** in the queue structure.
You can go and check the code above, there is a line `q->size--;` or `q->size++;` everytime we remove or insert an element.
In this case, the code is so simple as below:

int q_size(queue_t *q)
{
    if (q == NULL) {
        return 0;
    }
    return q->size;
}

### `q_reverse`
#### Expected Functionality
* Reverse the element sequence in queue
* The function should not allocate or free any list element
#### Code
First, we handle the special cases, empty queue and non-existing queue. In this two cases, we don't need to do anything.
Then, we use three pointers here, which are `prev`, `temp`, and `next`. `prev` holds the element previous to `temp`, and `next` holds the one next to `temp`. We go through the whole list from the head and make the element holded by `temp` point to previous one, then move to the next element by using `next`. This move will keep being implemented until `temp` reaches NULL.

void q_reverse(queue_t *q)
{
    /*Handle empty queue and non-existing queue*/
    if (q == NULL || q->head == NULL)
        return;

    list_ele_t *temp, *prev, *next;
    prev = q->head;
    temp = prev->next;
    next = temp;
    q->head->next = NULL;
    q->tail = q->head;
    while (temp != NULL) {
        next = temp->next;
        temp->next = prev;
        prev = temp;
        temp = next;
    }
    q->head = prev;
    return;
}

## Result

e24046616@tommywang-MacBookPro:~/lab0-c$ make test
scripts/driver.py
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---     trace-05-ops    6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
This queue doesn't exist!
This queue doesn't exist!
---     trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
can't allocate space for the queue.
can't allocate space for the queue.
---     trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
Couldn't allocate space for the string!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
---     trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the element!
---     trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---     trace-15-perf   7/7
---     TOTAL           100/100

## How does the testing system work
I'm new to linux, so all these stuff are totally unfailliar for me. I'm not sure I can really well elaborate how this system work, but I'll write down what I learned and try my best to explain it.
### Makefile
###### Reference: [Linux make command](https://www.computerhope.com/unix/umake.htm)
We use the command `make` to compile and genenrate the executable code. This command is a utility for building and maintaining groups of programs from source code. The **make** program uses the makefile data base and the last-modification times of the files to decide which of the files need to be updated. For those files, it issues the commands recorded in the database. **make** executes commands in the makefile, if no -f is present, **make** will look for the makefiles **GNUmakefile**, **makefile**, **Makefile**, in that order.
:::info
Note: The **Makefile** is recommended becasue it appears prominently near the beginning of a directory listing, right near other improtant files such as **README**.
:::
#### Compile the source code
When we do `make` without any arguments like this in terminal:

make

**make** builds the first target that appears in its makefile, which is traditionally a target named **all**. In the Makefile of the homework, it is:

all: $(GIT_HOOKS) qtest

From this target, **make** will compile the source code and build the executable file **qtest** by running the command from this line in the Makefile:

qtest: qtest.c report.c console.c harness.c queue.o
	$(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o

We can know it will also generate the Git Hooks if we expand the macro (GIT_HOOKS) and look at the rule:

GIT_HOOKS := .git/hooks/applied
$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

#### Evaluation
According from the [pdf file](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) of the homework requirement, the driver program `driver.py` runs the qtest and computes the score. When we do make with argument test following like this:

make test

**make** build this target in the Makefile:

test: qtest scripts/driver.py
	scripts/driver.py

That is how **make** invoke the driver.