# 2020q1 Homework1 (lab0)
contributed by < `pingsutw` >

## 開發環境

$ uname -a
Linux kevin 5.0.0-38-generic #41-Ubuntu SMP Tue Dec 3 00:27:35 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 8.3.0-6ubuntu1) 8.3.0

$ lsb_release -a
No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 19.04
Release:	19.04
Codename:	disco

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
Address sizes:       39 bits physical, 48 bits virtual
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               60
Model name:          Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping:            3
CPU MHz:             1527.846
CPU max MHz:         3600.0000
CPU min MHz:         800.0000
BogoMIPS:            5188.08
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7

## 作業要求
* `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`==: 「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程所新增，以==遞增順序==來排序鏈結串列的元素，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;

## 開發過程
### `queue_t`
- 因為 `q_insert_tail` 和 `q_size` 需要將原本 $O(n)$ 時間複雜度的實作改寫為 $O(1)$ 時間複雜度，所以加了 `*tail` 和 `qsize` 來紀錄最後一個節點和 `queue` 大小

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int qsize;
} queue_t;

### `q_new`
- 回傳一個空的 `queue_t`, 如果 malloc 失敗回傳 NULL

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

### `q_free`
- 當 `queue_t` 為 NULL 時直接 return，當 `queue_t` 不為 NULL 時，依序拜訪個節點並釋放記憶體空間

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

### `q_insert_head`
- `queue_t` 為 NULL 時，直接 return false
- `queue_t` 不為 NULL 時, 先 malloc 記憶體空間給 `list_ele_t` 還有 `list_ele_t->value`，如果失敗 return false，如果成功再將字串寫到節點裡，注意字串最後一個字元需為 `\0` 表示字串結束
- 新節點指向 queue head

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    strncpy(newh->value, s, strlen(s));
    (newh->value)[strlen(s)] = '\0';
    newh->next = q->head;

    q->head = newh;
    (q->qsize)++;
    if (q->qsize == 1)
        q->tail = newh;
    return true;
}

### `q_insert_tail`
- `queue_t` 為 NULL 時，直接 return false
- `queue_t` 不為 NULL 時, 先 malloc 記憶體空間給 `list_ele_t` 還有
`list_ele_t->value`，如果失敗 return false，如果成功再將字串寫到節點裡，注意字串最後一個字元需為 `\0` 表示字串結束
- queue tail 指向新節點
- 必須使用 `strncpy` 而不是 `strcpy`, 因為 `strcpy` 沒有限制字串寫入 buffer 的大小，可能因為程式疏失，而導制記憶體使用過量

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    strncpy(newh->value, s, strlen(s));
    (newh->value)[strlen(s)] = '\0';
    newh->next = NULL;

    if (q->tail != NULL)
        q->tail->next = newh;
    q->tail = newh;
    (q->qsize)++;

    if (q->qsize == 1)
        q->head = q->tail;

    return true;
}

### `q_remove_head`
- 當 `queue` 為 NULL 或 `queue size` 為 0 時，return 0
- 當 `queue` 不為 NULL，複製自傳到 `buffer`，`buffer` 的最後一個字元需為 `\0` 代表字串結束

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->qsize == 0)
        return false;
    if (sp != NULL) {
        memset(sp, '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *prev = q->head;
    q->head = q->head->next;

    free(prev->value);
    free(prev);
    (q->qsize)--;
    return true;
}

### `q_size`
`queue_t` 的大小已經紀錄在 `queue_t` 裡面可以直接取得，如果 `queue_t` 為空時 return 0.

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

### `q_reverse`
- 當 `queue` 為 NULL 或 `queue size` 為 0 時，直接 return
- 建立三個指標分別指向當前節點, 前一個節點，下一個節點，依序拜訪各界點，再將當前節點指向前一個節點

void q_reverse(queue_t *q)
{
    if (q == NULL || q->qsize == 0)
        return;

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

- step 1 `next = cur->next;`

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    NULL1 [label="{ <data> NULL | <ref>  }"];
    NULL2 [label="{ <data> NULL | <ref>  }"];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL1 :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    Next [shape=box];
    Next -> b;
    Cur [shape=box];
    Cur -> a;
    Prev [shape=box];
    Prev -> NULL2
}

- step 2 `cur->next = prev;`

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    NULL1 [label="{ <data> NULL | <ref>  }"];
    NULL3 [label="{ <data> NULL | <ref>  }"];
    a:ref:c -> NULL3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL1 :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    Next [shape=box];
    Next -> b;
    Cur [shape=box];
    Cur -> a;
    Prev [shape=box];
    Prev -> NULL3
}

- step 3 `prev = cur;`

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    NULL1 [label="{ <data> NULL | <ref>  }"];
    NULL3 [label="{ <data> NULL | <ref>  }"];
    a:ref:c -> NULL3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL1 :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    Next [shape=box];
    Next -> b;
    Cur [shape=box];
    Cur -> a;
    Prev [shape=box];
    Prev -> a
}

- step 4 `cur = next;`

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    NULL1 [label="{ <data> NULL | <ref>  }"];
    NULL3 [label="{ <data> NULL | <ref>  }"];
    a:ref:c -> NULL3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL1 :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    Next [shape=box];
    Next -> b;
    Cur [shape=box];
    Cur -> b;
    Prev [shape=box];
    Prev -> a
}

### `q_sort`
- 對 `queue` 中的元素進行排序
- 需用 merge sort，滿足時間複雜度 $O(nlogn)$
- 遞迴的方式先將 `queue` 分兩半，在進行合併

void q_sort(queue_t *q)
{
    if (!q || q->qsize < 2)
        return;

    queue_t left, right;
    left.qsize = q->qsize / 2 + (q->qsize & 1);
    right.qsize = q->qsize / 2;

    list_ele_t *cur = left.head = q->head;
    right.tail = q->tail;

    for (int i = 0; i < left.qsize - 1; i++)
        cur = cur->next;

    left.tail = cur;
    right.head = cur->next;
    left.tail->next = right.tail->next = NULL;
    q->head = q->tail = NULL;

    q_sort(&left);
    q_sort(&right);
    merge(&left, &right, q);
}

### `is_less_then`
- 比較兩個字串的大小
- 需判斷字串為空的狀態

//  compares two strings character by character.
static bool is_less_then(list_ele_t *x, list_ele_t *y)
{
    if (!x)
        return true;
    if (!y)
        return false;

    if (strcmp(x->value, y->value) < 0)
        return true;
    else
        return false;
}

### `merge`
- 對兩個 `queue` 進行合併

queue_t *merge(queue_t *left, queue_t *right, queue_t *q)
{
    q->qsize = left->qsize + right->qsize;
    list_ele_t *l = left->head, *r = right->head;
    list_ele_t *tmp = NULL;

    if (is_less_then(left->head, right->head))
        q->head = left->head;
    else
        q->head = right->head;

    q->tail = q->head;
    for (int i = 0; i < q->qsize; i++) {
        if (!r || (l && is_less_then(l, r))) {
            tmp = l;
            l = l->next;
        } else {
            tmp = r;
            r = r->next;
        }
        q->tail->next = tmp;
        q->tail = tmp;
    }
    tmp->next = NULL;
    return q;
}

## [Pull Request](https://github.com/sysprog21/lab0-c/commit/af0d7a9493676f7c542f2ebc915fc06a07a3e109)
- 為了讓輸出更醒目，提了一個 pr，成功會顯示綠色，失敗會顯示紅色

## 參考資料
- [Linux 核心設計: 線上/實體課程說明 (2020 年春季)](https://www.youtube.com/watch?v=9VlOpKWdIVU&t=6269s)
- [H01: lab0](https://hackmd.io/@sysprog/linux2020-lab0#-%E9%96%8B%E7%99%BC%E7%92%B0%E5%A2%83%E8%A8%AD%E5%AE%9A)
- [Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl)
- [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list?type=view)
- [What is size_t in C?](https://stackoverflow.com/questions/2550774/what-is-size-t-in-c)
- [深入理解c语言——‘\0’ ，‘0’， “0” ，0之间的区别](https://blog.csdn.net/supreme42/article/details/7300451)
- [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
- [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml)
- [Is the function strcpy always dangerous?](https://stackoverflow.com/questions/5317440/is-the-function-strcpy-always-dangerous)
- [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)

###### tags: `sysprog2020`