# 2020q1 Homework1 (lab0)
contributed by < `kylekylehaha` >
###### tags: `linux2020`

## 開發環境

$ uname -a
Linux kyleD 5.3.0-40-generic

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

---
## 實做 queue 需求
利用 singly-linked list 來實做 FIFO & LIFO queue，並滿足下列功能：
- q_new: 建立新的「空」佇列
- q_free: 釋放 queue 所佔用的記憶體，其中包含 header & 所有 list elements
- q_insert_head: 在 head 加入 element，並採用LIFO準則
- q_insert_tail: 在 tail 加入 element，並採用FIFO準則
- q_remove_head: 從 head 移除一 element
- q_size: 計算 queue 中的 element 個數
- q_reverse: 將 queue 反轉
- q_sort: 利用 bubble sort 的方式，將 queue 做遞增排列

### q_new
平常沒有習慣檢查 malloc 是否成功，經過這次作業開始養成這種好習慣。

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

### q_free
free 的時候記得要先 free 裡面的資料後，再 free 整個 element。

void q_free(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *current_ptr = q->head;
    while (current_ptr) {
        list_ele_t *tmp = current_ptr;
        current_ptr = current_ptr->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
    return;
}

### q_insert_head
須注意的地方仍和前面一樣，每當 malloc 時，都要檢查是否 malloc 成功。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    int len = strlen(s);
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char) * len + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, 0, len);
    strncpy(newh->value, s, len);
    newh->value[len] = '\0';
    //  Maintain queue structure
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0) {
        q->tail = newh;
    }
    q->size += 1;
    return true;
}

### q_insert_tail
概念和 q_insert_head 相同，兩者不同只在於 maintain queue structure 的部份。

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    int len = strlen(s);
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char) * len + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, 0, len);
    strncpy(newh->value, s, len);
    newh->value[len] = '\0';
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    q->tail = newh;
    q->size += 1;
    return true;
}

### q_remove_head
目前有bug:
`ERROR: Corruption detected in block with address 0x5616328dad80 when attempting to free it
`
目前發現是由於 free(tmp->value) ，也就是 free list_element 內的字串所產生的error

已解決：後來我發現原來是我在放置 '\0'位置時，忘了 len 已經加一，不再等於 strlen(s)。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    list_ele_t *tmp = q->head;
    int len = strlen(q->head->value);
    if (sp) {
        memset(sp, 0, bufsize);
        strncpy(sp, tmp->value, len);
    }
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size -= 1;
    return true;
}

### q_size
由於在前面的 q_insert_head, q_insert_tail, q_remove_head 中，當有增加/減少 element 時，就以調整過 q->size，故這裡只須回傳 q->size 值。須注意仍要檢查 q 是否為 NULL。

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

### q_reverse
在這裡，我參考 [Reverse a linked list](https://www.geeksforgeeks.org/reverse-a-linked-list/) 裡的gif，讓我更快速理解 linked list reverse 的機制。

void q_reverse(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *next, *curr, *prev;
    prev = NULL;
    next = NULL;
    curr = q->head;
    q->tail = q->head;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    q->head = prev;
}

### q_sort
* 採用本週測驗的 merge sort with single linked list。然而須注意的是經過 sort 後，原本為 q->tail 所指的 element 不一定仍為 queue tail，故再重新走一次 queue 來找到真正的 tail。
* Time complexity: O(nlogn + n), n為 q->size。
* 但發現跑不過 trace-15-perf & trace-16-perf

list_ele_t *sort(list_ele_t *start)
{
    if (!start || !start->next)
        return start;
    list_ele_t *left = start;
    list_ele_t *right = start->next;
    left->next = NULL;

    left = sort(left);
    right = sort(right);

    for (list_ele_t *merge = NULL; left || right;) {
        if (!right || (left && strnatcmp((left->value), (right->value)) < 0)) {
            if (!merge) {
                start = merge = left;
            } else {
                merge->next = left;
                merge = merge->next;
            }
            left = left->next;
        } else {
            if (!merge) {
                start = merge = right;
            } else {
                merge->next = right;
                merge = merge->next;
            }
            right = right->next;
        }
    }
    return start;
}

void q_sort(queue_t *q)
{
    if (!q || !q->head)
        return;
    q->head = sort(q->head);
    //  Find new q->tail after sort
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

## 開發問題
* problem1
利用 Valgrind 去分析 trace-08-robust.cmd，發現在做 q_sor t時沒有檢查到 empty queue 的 case。

void q_sort(queue_t *q)
{
-    if (!q)
+    if (!q || !q->head)
        return;
    q->head = sort(q->head);
    //  Find new q->tail after sort
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

* problem2
由於課堂練習的 merge sort 沒有從中間開始切，導致整體時間太長，跑不過trace-16，故必須製作 split，從中間開始切，才能縮短整體時間。
利用slow & fast，速度 1:2 來找尋中間值。

void split(list_ele_t *source, list_ele_t **left, list_ele_t **right)
{
    if (!source || !source->next) {
        *left = source;
        *right = NULL;
        return;
    }
    list_ele_t *slow = source;
    list_ele_t *fast = source;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    *left = source;
    *right = slow->next;
    slow->next = NULL;
    return;
}

## 論文研讀 Dude, is my code constant time?
## 解釋 select 系統呼叫在本程式的使用方式
## Reference
- [Queue: Intro(簡介)，並以linked list 實做](https://alrightchiu.github.io/SecondRound/queue-introjian-jie-bing-yi-linked-listshi-zuo.html)
- [Reverse a linked list](https://www.geeksforgeeks.org/reverse-a-linked-list/)