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

[作業解說](https://hackmd.io/s/BJA8EgFB4)
[C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

###### tags: DesignOfLinuxkernel-HW

## 題目要求

* #### By modifying the code in queue.h and queue.c to fully implement the following fuctions.

* **q_new :** Create a new, empty queue
> (Notice that An empty queue is one pointing to a valid structure, but the head field has value NULL.)
* **q.free :** Free all storage 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 :** Reorder the list so that the queue elements are reversed in order.
>(Noitce that this function should not allocate or free any list elements.)

-------

## 實作

### Queue Structure :
為了使 q_size 和 q_insert_tail 在 $O(1)$ 時間內完成，在 Queue Structure 內加入 tail 和 size 分別記錄尾端指標和大小。

/* Queue structure */
typedef struct {
    int size;
    list_ele_t *tail;
    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
                      */
} queue_t;

### q_new :
初始化queue

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

### q_free :
釋放 queue 所佔用的空間，若 queue 為空則 return，
否則利用 this 記錄 head，並逐步釋放每一個 node 的 value 及其空間。

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if (!q)
        return;
    list_ele_t *this = q->head;
    while (this) {
        list_ele_t *temp;
        temp = this;
        this = this->next;
        free(temp->value);
        free(temp);
    }
    /* Free queue structure */
    free(q);
}

### q_insert_head :
* 插入 node 於 queue_head
* 以下三種情況回傳false :
1. queue is NULL
2. malloc 失敗
3. input string 為 NULL

* 此外，若 queue 為 empty queue，則 head 和 tail 均指向 inserted node (newh)

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }
    if (!q->head) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

### q_insert_tail

* 插入 node 於 queue_tail，
* 同 q_insert_head，以下三種情況回傳 false :
1. queue is NULL
2. malloc 失敗
3. input string 為 NULL

* 若 queue 為 empty queue，則 head 和 tail 均指向 inserted node (newh)

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }
    newh->next = NULL;
    if (!q->head) {
        q->tail = newh;
        q->head = newh; /* if queue is empty */
    }
    q->tail->next = newh;
    q->tail = newh;
    q->size++;
    return true;
}

### q_remove_head
* 若 queue is NULL 或 queue is empty 則 return false
* 將 removed node 中的字串複製到 sp
* 若 q_size >= 2，將 head 指向 head 指的下一個 node，並釋放 removed node

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || !q->head)
        return false;
    list_ele_t *temp;
    temp = q->head;
    /* Copy removed value to sp */
    if (sp) {
        strncpy(sp, temp->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    /* If queue has only one node */
    if (q->size == 1) {
        q->head = NULL;
        q->tail = NULL;
    } else {
        q->head = q->head->next;
    }
    q->size--;
    /* Free temp */
    free(temp->value);
    free(temp);
    return true;
}

### q_size
若 queue is NULL 則 return 0，否則 return q->size 即可

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (!q)
        return 0;
    return q->size;
}

### q_reverse
將queue反轉，策略是利用 r 指標緊跟著 p 後面，並從 q_head 開始，循序將各個 node(即 p) 的 next 指向 r，最後再將 head 和 tail 互換即可

void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;
    list_ele_t *p, *r, *s, *temp; /* r follows p */
    p = NULL;
    s = q->head;
    while (s) {
        r = p;
        p = s;
        s = s->next;
        p->next = r;
    }
    /* Swap head and tail */
    temp = q->tail;
    q->tail = q->head;
    q->head = temp;
}

## 解釋自動評分系統運作的原理
未完成待補
## 提及 qtest 的行為和裡頭的技巧
未完成待補