# 2020q3 Homework1 (lab0)
contributed by < `CW-B-W` >
[github](https://github.com/CW-B-W/sysprog2020q3-lab0-c)

###### tags: `sysprog2020`

## Outline
[TOC]

## 作業要求
在 ``queue.[c/h]`` 中完成以下實作

* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素

## 實作流程

### queue.h
* 1 `hehe`
* 1 `hehe`

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* points to the tail element, if q_size=1, then head=tail. */
    size_t      size;
} queue_t;

### queue.c
* **q_new**
* queue為空時，head, tail 都必須是 NULL，size 必須為 0

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

* **q_free**
* `rm_node` 指向此次 iteration 需要 free 的 Node

    void q_free(queue_t *q)
    {
        if (!q) {
            return;
        }

        while (q->head) {
            list_ele_t* rm_node = q->head;
            q->head = q->head->next;
            free(rm_node->value);
            free(rm_node);
        }
        free(q);
    }

* **q_insert_head**
* 注意邊界情況: `當 q_size 為 0 時`
* 需要在 `newh = malloc` 前先檢查 `q == NULL`，否則可能多一次 `malloc`的成本，並容易忘記 `free` 而導致 `memory leak`
* `strlen` 不會將 `'\0'`算入，故需另外保留一個`sizeof(char)`給`'\0'`
* 當 `newh->value` `malloc`失敗後，要記得刪除 `newh = malloc(...)` 分配的記憶體
* 注意當 queue 為空時，要特別設置 `q->head` 與 `q->tail`

    bool q_insert_head(queue_t *q, char *s)
    {
        list_ele_t *newh;

        /*
         * DO NOT do this check after malloc
         * Memory leak is prone to happen
         */
        if (!q) {
            return false;
        }

        newh = malloc(sizeof(list_ele_t));
        if (!newh) {
            return false;
        }
        newh->next = NULL;
        newh->value = NULL;

        /*
         * Extra 1 bytes for '\0'
         * Is calling strlen(s) bad for performance ??
         */
        size_t copy_size = (sizeof(char) * strlen(s)) + (sizeof(char) * 1);
        newh->value = (char*) malloc(copy_size);
        if (!newh->value) {
            /* Failed to construct newh, free it! */
            free(newh);
            return false;
        }
        memcpy(newh->value, s, copy_size);

        if (!q->head) {
            q->head = q->tail = newh;
        } else {
            newh->next = q->head;
            q->head = newh;
        }
        q->size += 1;
        return true;
    }

* **q_insert_tail**
* 同 `q_insert_head(...)` 注意事項

    bool q_insert_tail(queue_t *q, char *s)
    {
        list_ele_t* newt;

        if (!q) {
            return false;
        }

        newt = malloc(sizeof(list_ele_t));
        if (!newt) {
            return false;
        }
        newt->next = NULL;
        newt->value = NULL;

        /*
         * Extra 1 bytes for '\0'
         * Is calling strlen(s) bad for performance ??
         */
        size_t copy_size = (sizeof(char) * strlen(s)) + (sizeof(char) * 1);
        newt->value = (char*) malloc(copy_size);
        if (!newt->value) {
            /* Failed to construct newt, free it! */
            free(newt);
            return false;
        }
        memcpy(newt->value, s, copy_size);

        if (!q->tail) {
            q->head = q->tail = newt;
        } else {
            q->tail->next = newt;
            q->tail = newt;
        }
        q->size += 1;
        return true;
    }

* **q_remove_head**
* 注意邊界情況: `當 q_size 為 1 時`
* 若 `sp != NULL`，須將移除內容複製到buffer
* 注意 bufsize 大小限制。大小不足也須複製，但只可複製部分

    bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
    {
        if (!q || !q->head) {
            return false;
        }

        list_ele_t* rm_node = q->head;
        q->head = q->head->next;
        q->size -= 1;
        if (!q->head) {
            q->tail = NULL;
        }

        size_t copy_size = (sizeof(char) * strlen(rm_node->value)) + (sizeof(char) * 1);
        if (sp)
        {
            memcpy(sp, rm_node->value, copy_size <= bufsize ? copy_size : bufsize);
            sp[bufsize-1] = '\0';
        }

        free(rm_node->value);
        free(rm_node);
        return true;
    }

* **q_size**
* 直接在 struct 裡面新增 `size`

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

* **q_reverse**
* 反轉過程只需用到 `q->head`，故可先 `q->tail = q->head;`
* 反轉完記得 `q->tail->next = NULL;`

    void q_reverse(queue_t *q)
    {
        if (!q || !q->head) {
            return;
        }

        q->tail = q->head;

        list_ele_t* cur = q->head->next;
        while (cur) {
            list_ele_t* prev = q->head;
            q->head = cur;
            cur = cur->next;
            q->head->next = prev;
        }
        q->tail->next = NULL;
    }

* **q_sort**
* 使用 Merge sort 排序
* 利用兩個 step(步距) 不同的 Cursor ，找出 list 中央點
* 將一個 list 斷成兩段(`stp1->next = NULL;`)，並 recursively 求解
* Merge 時，若其中一段 List 以完全用完，可直接將剩下的另一段 List 直接接到 Tail
* 用自己寫的 Naive strcmp (i.e., 逐 char 慢慢比對)，會 Time Limit Exceeded
* 需減少"不必要" Function call 數量，不然也會 Time Limit Exceeded

    static list_ele_t* q_sort_mergesort(list_ele_t* p1)
    {
        if (!p1->next)
            return p1;
        list_ele_t* stp1 = p1;
        list_ele_t* stp2 = p1->next;
        while (stp2 && stp2->next) {
            stp1 = stp1->next;
            stp2 = stp2->next->next;
        }
        list_ele_t* p2 = stp1->next;
        stp1->next = NULL;

        p1 = q_sort_mergesort(p1);
        p2 = q_sort_mergesort(p2);

        /* make *p1 < *p2, i.e., make p1 be the head of list */
        if (strcmp(p1->value, p2->value) > 0) {
            list_ele_t* tmp = p1;
            p1 = p2;
            p2 = tmp;
        }
        list_ele_t* ret_head = p1;
        list_ele_t* p3 = p1->next;

        /* p1 is the smallest among the three, p2 or p3 is p1's successor */
        while (p2 && p3) {
            int res = strcmp(p2->value, p3->value);
            if (res < 0) {
                p1->next = p2;
                p1 = p2;
                p2 = p2->next;
            }
            else {
                p1->next = p3;
                p1 = p3;
                p3 = p3->next;
            }
        }
        p1->next = p2 ? p2 : p3;

        return ret_head;
    }

* sort 完用 O(n) 搜 `q->tail`
* 因為整條 list 已經 sorted，故可由任一個 Node 直接往下搜即可，不必先 `q->tail = q->head` 在開始搜

    void q_sort(queue_t *q)
    {
        if (q_size(q) <= 1)
            return;

        q->head = q_sort_mergesort(q->head);

        /* O(n) reconstruct q->tail */
        while (q->tail->next)
        {
            q->tail = q->tail->next;
        }
    }