# 2019q1 Homework1 (lab0)
contributed by < `wang0630` >

:::danger
認真看作業要求，除了提及如何逐步達到要求，還需要進行:
1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標，請繼續付出！
:notes: jserv
:::

## Goal
According to the pdf file, we need to implement the following core operations of queue:
1. Create a queue
2. Free all spaces allocated for the queue
3. Insert a new node at the head of the queue
4. Insert a new node at the tail of the queue
5. Pop out the node at the head of the queue
6. Return the number of nodes in the queue

## Implementation

1. Create a new queue:

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        fprintf(stderr, "Malloc call returns null");
    else { 
        q->head = q->tail = NULL;
        q->qsize = 0;
    }
    return q;
}

2. Free all spaces allocated for the queue:

void q_free(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *prev = NULL;
    if (q->qsize) {
        for (list_ele_t *iter = q->head; iter;) {
            free(iter->value);
            prev = iter;
            iter = iter->next;
            free(prev);
        }
    }
    free(q);
}

3. Insert a new node at the head of the queue:

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);  // free the new node since it is allocated spaces
        return false;
    }
    memset(newh->value, 0, strlen(s) + 1);
    if (s)
        strcpy(newh->value, s);
    newh->next = q->head;  // new node's next to first element or to null if the
                           // queue is empty
    q->head = newh;        // insert new node
    // if queue is empty before insertion, q->tail should be pointed to the newh
    // as well
    q->tail = !q->qsize ? newh : q->tail;
    q->qsize++;
    return true;
}

4. Insert a new node at the tail of the queue:

bool q_insert_tail(queue_t *q, char *s)
{
    // maintain a tail field in the queue_t structure to achieve O(1) insertion
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, 0, strlen(s) + 1);
    if (s)
        strcpy(newh->value, s);
    newh->next = NULL;  // tail node's next must be null
    if (q->qsize)
        q->tail->next = newh;
    q->tail = newh;
    // if queue is empty before insertion, q->head should be pointed to the newh
    // as well
    q->head = q->qsize ? q->head : newh;
    q->qsize++;
    return true;
}

5. Pop out the node at the head of the queue:

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->qsize)
        return false;
    if (sp) {                    // if sp is non-NULL
        memset(sp, 0, bufsize);  // clear sp to safely contain the string
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *tmp = q->head;  // hold the target node
    q->head = q->head->next;    // remove the head
    q->qsize--;
    // if queue is empty after the removal, q->tail should be null as well
    q->tail = q->qsize ? q->tail : NULL;
    // free the target node
    free(tmp->value);
    free(tmp);
    return true;
}

6. Return the number of nodes in the queue:

int q_size(queue_t *q)
{
    return !q ? 0 : q->qsize;
}

7. Reverse the queue:

void q_reverse(queue_t *q)
{
    if (!q || !q->qsize || q->qsize == 1)
        return;
    list_ele_t *prev, *cur, *nextele;
    prev = q->head;
    cur = nextele = q->head->next; // q->head->next must exist, there is at least two nodes
    while (cur) {
        nextele = nextele->next;
        cur->next = prev;
        prev = cur;  // move prev
        cur = nextele;
    }
    list_ele_t *tmpHead = q->head;
    q->head->next = NULL;
    q->head = q->tail;
    q->tail = tmpHead;
}

## Tools I learned in this assignment:
1. valgrind:
A analysis tool to discover the partial errors.
Useful flags:
* `--track-fds`: track open file fds
* `--leak-check`: track partial memory leak