---
# System prepended metadata

title: 2023q1 Homework1 (lab0)
tags: [linux kernel class]

---

---
tags: linux kernel class
---
# 2023q1 Homework1 (lab0)
contributed by < [`willwillhi1`](https://github.com/willwillhi1) >

## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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:                           142
Model name:                      Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
Stepping:                        12
CPU MHz:                         2100.000
CPU max MHz:                     4200.0000
CPU min MHz:                     400.0000
BogoMIPS:                        4199.88
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7
```

## 開發過程
先閱讀[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
![](https://i.imgur.com/vBvOdJ0.png)
可以發現程式中的 ```head``` 為上圖的 Head
Node0,1,2... 為 ```element_t```
### 完成 queue.c
#### q_new
利用 ```malloc``` 一個 ```list_head``` 並命名為 ```head```，接著判斷是否成功執行 ```malloc``` 後用 ```INIT_LIST_HEAD``` 來對 ```head``` 初始化，也就是把 ```head->next```,```head->prev``` 指向 ```head```
```c
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head == NULL) 
        return NULL;
    INIT_LIST_HEAD(head);
    return head; 
}
```

#### q_free
用迴圈走訪整個佇列，並且 free 掉走過的點。

:::warning
改進上述漢語表達
:notes: jserv
:::

```c
void q_free(struct list_head *l) 
{
    if (l)
        return;
    struct list_head *next = l->next;
    while (l != next) {
        //list_del(next);
        element_t *node = list_entry(next, element_t, list);
        next = next->next;
        free(node->value);
        free(node);
    }
    free(l);
}
```

#### q_insert_head
```malloc``` 一個 ```element_t``` 物件叫做 ```node```，然後用 ```strdup``` 配置空間給 ```node->value``` 後將 ```s``` 複製過去，最後用 ```list_add``` 把 ```node``` 插入到佇列的開頭
```c
bool q_insert_head(struct list_head *head, char *s)
{
    if (head == NULL) 
        return false;
    element_t *node = malloc(sizeof(struct element_t));
    if (node == NULL) 
        return false;
    node->value = strdup(s);
    if (node->value == NULL) {
        free(node);
        return false;
    }
    list_add(&node->list, head);
    return true;
}
```

#### q_insert_tail
與 ```q_insert_head``` 相似，把 ```list_add``` 改成 ```list_add_tail``` 
```c
bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL) 
        return false;
    element_t *node = malloc(sizeof(struct element_t));
    if (node == NULL) 
        return false;
    node->value = strdup(s);
    if (node->value == NULL) {
        free(node);
        return false;
    }
    list_add_tail(&node->list, head);
    return true;
}
```

#### q_remove_head
去除佇列的第一個元素，```sp``` 為一個已配置空間的字元陣列，```bufsize``` 為其長度。先用 ```list_del``` 去除第一個元素，再用 ```strncpy``` 把去除元素的 ```value``` 複製到 ```sp``` 中。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) 
        return NULL;
    element_t *node = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp != NULL) {
        strncpy(sp, node->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    return node;
}
```


#### q_remove_tail
與 ```q_remove_head``` 相似，把 ```head->next``` 改成 ```head->prev```
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) 
        return NULL;
    element_t *node = list_entry(head->prev, element_t, list);
    list_del(head->prev);
    if (sp != NULL) {
        strncpy(sp, node->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    return node;
}
```

#### q_size
如果佇列為空或只有 ```head``` 就回傳 0，之後用 ```list_for_each``` 走訪整個佇列計算 node 數量
```c
int q_size(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return 0;
    int size = 0;
    struct list_head *l;
    list_for_each(l, head)
        size++;
    return size;
}
```

#### q_delete_mid
宣告 ```first``` 為 ```head->next```, ```second``` 為 ```head->prev```，用 ```while``` 迴圈判斷 ```first``` 和 ```second``` 是否相遇，若還沒則兩個各走一步，直到相遇時 ```first``` 代表中間點，之後便用 ```list_del``` 把其從佇列中去除，然後再 ```free``` 掉該 ```node```
```c
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head == NULL || list_empty(head)) 
        return false;
    struct list_head *first = head->next;
    struct list_head *second = head->prev;
    while ((first != second) && (first->next != second)) {
        first = first->next;
        second = second->prev;
    }
    list_del(first);
    element_t *node = list_entry(first, element_t, list);
    free(node->value);
    free(node);
    return true;
}
```

#### q_delete_dup
先確認佇列是否為空。宣告兩個 ```element_t``` 指標 ```N1```,```N2```，```N1``` 代表目前沒有重複的最後一個點，```N2``` 代表目前重複的數的第一個點
```graphviz
digraph del_mid {
  {
    node [shape=circle]
    rankdir=LR
    //rank=same
    node0[label="head"]
    node1[label="1"]
    node2[label="2"]
    node3[label="2"]
    node4[label="3"]
    // backbone
    node0 -> node1 -> node2 -> node3 -> node4
    // mark
    N1 [shape=plaintext;label="N1"]
    N1 -> node1[]
    
    N2 [shape=plaintext;label="N2"]
    N2 -> node2[] 
    {rank=same node0 node1 node2 node3 node4}
  }
}
```

接著就是判斷 ```N2->value``` 是否等於 ```N2->next->value```，若是則刪除 ```N2->next``` 直到不相同為止，最後再把重複的 ```N2``` 刪除
```c
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    element_t *N1 = list_entry(head, element_t, list);
    element_t *N2 = list_entry(head->next, element_t, list);
    while (&N2->list != head) {
        char *value = list_entry(N2->list.next, element_t, list)->value;
        if (N2->list.next != head && strcmp(N2->value, value) == 0) {
            while (N2->list.next != head && strcmp(N2->value, value) == 0) {
                element_t *node = list_entry(N2->list.next, element_t, list);
                list_del(N2->list.next);
                q_release_element(node);
                value = list_entry(N2->list.next, element_t, list)->value;
            }
            list_del(&N2->list);
            element_t *node = list_entry(&N2->list, element_t, list);
            q_release_element(node);
            N2 = list_entry(N1->list.next, element_t, list);
        }
        else {
            N1 = list_entry(N1->list.next, element_t, list);
            N2 = list_entry(N2->list.next, element_t, list);
        }
    }
    return true;
}
```
:::warning
1. 留意程式碼風格，`N1` 和 `N2` 並非恰當的命名。
2. 將 `if (head == NULL)` 改為更簡短的 `if (!head)`
3. 將 `strcmp(..) == 0` 改為更剪短的 `!strcmp(...)`
4. 縮減迴圈內的分支指令數量

:notes: jserv
:::
* 改進後的版本
額外使用 ```isdup``` 判斷是否需要刪除目前的節點 ```first```
下圖可以看到因為 ```first->value``` 等於 ```second->value``` 所以把 ```first``` 刪除 以及把 ```isdup``` 設成 ```true```
```graphviz
digraph del_mid {
  {
    node [shape=circle]
    rankdir=LR
    //rank=same
    node0[label="head"]
    node1[label="1"]
    node2[label="1"]
    node3[label="2"]
    node4[label="3"]
    // backbone
    node0 -> node1 -> node2 -> node3 -> node4
    // mark
    first [shape=plaintext;label="first"]
    first -> node1[]
    
    second [shape=plaintext;label="second"]
    second -> node2[] 
    {rank=same node0 node1 node2 node3 node4}
  }
}
```
接著來因為 ```isdup``` 等於 ```true```，所以把 ```first``` 刪除後，再把 ```isdup``` 改回 ```false```
```graphviz
digraph del_mid {
  {
    node [shape=circle]
    rankdir=LR
    //rank=same
    node0[label="head"]
    node1[label="1"]
    node2[label="2"]
    node3[label="3"]
    // backbone
    node0 -> node1 -> node2 -> node3
    // mark
    first [shape=plaintext;label="first"]
    first -> node1[]
    
    second [shape=plaintext;label="second"]
    second -> node2[] 
    {rank=same node0 node1 node2 node3}
  }
}
```

```c=
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    
    element_t *first;
    element_t *second;
    bool isdup = false;
    list_for_each_entry_safe(first, second, head, list) {
        if (&second->list != head \
            && !strcmp(first->value, second->value)) {
            list_del(&first->list);
            q_release_element(first);
            isdup = true;
        }
        else if (isdup) {
            list_del(&first->list);
            q_release_element(first);
            isdup = false;
        }
    }
    return true;
}
```
#### q_swap
確認 ```head``` 是否為 ```NULL``` 或佇列是否為空，用 ```first```,```second``` 代表要交換的一組 ```node```，下方第 9 到 14 行進行交換，接著就把 ```first```,```second``` 指到下一組 ```node```，直到 ```first``` 或 ```second``` 等於 ```head``` 為止
```c=
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (head == NULL || list_empty(head))
        return;
    struct list_head *first = head->next;
    struct list_head *second = head->next->next;
    while (first != head && second != head) {
        first->prev->next = second;
        first->next = second->next;
        second->prev = first->prev;
        first->prev = second;
        second->next->prev = first;
        second->next = first;

        first = first->next;
        second = first->next;
    }
}
```

#### q_reverse
確認 ```head``` 是否為 ```NULL``` 或佇列是否為空。初始化 ```first = head```,```second = head->next```，接著互換 ```first``` 的 ```prev``` 和 ```next```(8, 9 行)，最後 11, 12 行是跳到下兩個節點，直到 ```first != head```，也就是佇列裡的 ```prev```,```next``` 都被換過
```c=
void q_reverse(struct list_head *head) 
{
    if (head == NULL || list_empty(head))
        return;
    struct list_head *first = head;
    struct list_head *second = head->next;
    do {
        first->next = first->prev;
        first->prev = second;
        
        first = second;
        second = first->next;
    } while (first != head);
}
```

#### q_reverseK
最初的想法是用之前實作的 ```q_reverse``` 來寫，也就是把整個佇列分成每次以 ```k``` 個點為單位進行反轉。
首先利用 ```q_size``` 找出佇列的長度，然後除以 ```k``` 得到 ```times``` 代表共要做幾次 ```q_reverse```。
在每次的反轉裡，都會從原佇列切出來長度為 ```k＋1``` 的佇列，```first```,```last``` 代表該切割出來的佇列的頭尾節點。```front```,```end``` 用來記錄該切割下來的佇列在原本佇列的前後節點，用來把反轉後的佇列接回去原佇列。
以下圖為例假設 k = 3，且要反轉點 ```1```,```2```,```3```，所以 ```first``` 會在 ```head``` 上，```last``` 在 ```3```，```front```,```end``` 分別記錄該切割下來的佇列的前後點是 ```6``` 跟 ```4```。

```graphviz
digraph del_mid {
  {
    node [shape=circle]
    rankdir=LR
    node0[label="head"]
    node1[label="1"]
    node2[label="2"]
    node3[label="3"]
    node4[label="4"]
    node5[label="5"]
    node6[label="6"]
    // backbone
    node0 -> node1
    node1 -> node2
    node2 -> node3
    node3 -> node4
    node4 -> node5
    node5 -> node6
    node6 -> node0[dir="both"]
    // mark
    first [shape=plaintext;label="first"]
    first -> node0[]
    
    last [shape=plaintext;label="last"]
    last -> node3[]
    
    end [shape=plaintext;label="end"]
    end -> node4[]
    
    front [shape=plaintext;label="front"]
    front -> node6[]
    //{rank=max N1 N2} 
    {rank=same node0 node1 node2 node3 node4 node5 node6}
    }
}
```

:::warning
改進你的漢語表達
:notes: jserv
:::

```c
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (head == NULL) 
        return;
    struct list_head *front = head;
    struct list_head *end = head;
    struct list_head *first = head;
    struct list_head *last = head;
    int times = q_size(head)/k;
    for (int i = 0; i < times; ++i) {
        for (int j = 0; j < k; ++j)
            last = last->next;
        front = first->prev;
        end = last->next;
        last->next = first;
        first->prev = last;
        q_reverse(first);
        first->prev->next = end;
        end->prev = first->prev;
        first->prev = front;
        // update first, last
        first = end->prev;
        last = first;
    }
}
```
* 改進後的版本
先宣告和初始化兩個 ```head_list```: ```tmp``` 和 ```result```，本來想用 ```malloc```，但是這次作業好像禁止用，所以改用 ```LIST_HEAD```。
接著與前一個實作想法相同一次對 ```k``` 個節點作反轉，只不過這次會先透過 ```list_cut_position``` 把這 ```k``` 個節點移到 ```tmp``` 上，反轉後把 ```tmp``` 用 ```list_splice_tail_init``` 接到 ```result``` 的尾端且初始化 ```tmp```。
最後把 ```result``` 用 ```list_splice_init``` 接到 ```head``` 開頭。
```c=
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head) 
        return;
    
    struct list_head *last = head->next;
    int times = q_size(head)/k;
    LIST_HEAD(tmp);
    LIST_HEAD(result);
    
    for (int i = 0; i < times; ++i) {
        for (int j = 0; j < k; ++j)
            last = last->next;
        list_cut_position(&tmp, head, last->prev);
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, &result);
    }
    list_splice_init(&result, head);
}
```

#### q_sort
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 的 ```merge sort``` 的實做。

實作共三個函式 ```q_sort```,```mergesort```,```mergelist```
對 ```mergesort``` 輸入的佇列如果只有一個節點或空則直接回傳，接著把輸入的佇列分成兩半，然後對這兩個佇列做 ```mergesort```，```mergesort``` 會把這兩個佇列排序。
```c=
struct list_head *mergesort(struct list_head *l) 
{
    if (l == NULL || l->next == NULL)
        return l;
    struct list_head *fast = l;
    struct list_head *slow = l;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct list_head *l1 = l;
    struct list_head *l2 = slow->next;
    slow->next = NULL;

    return mergelist(mergesort(l1), mergesort(l2));
}
```
最後對這兩個已排序的佇列用 ```mergelist``` 合併。
```mergelist``` 用 ```pointer to pointer``` 的概念來做合併，縮短程式碼長度。
```c=
struct list_head *mergelist(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head = NULL;
    struct list_head **cur = &head;
    while (l1 && l2) {
        element_t *e1 = list_entry(l1, element_t, list);
        element_t *e2 = list_entry(l2, element_t, list);
        if (strcmp(e1->value, e2->value) >= 0) {
            *cur = l2;
            l2 = l2->next;
        }
        else {
            *cur = l1;
            l1 = l1->next;
        }
        cur = &(*cur)->next;
    }
    *cur = (struct list_head *) ((u_int64_t)l1 | (u_int64_t)l2);
    return head;
}
```
:::warning
避免張貼過長的程式碼，畢竟 HackMD 是紀錄和討論的協作環境，你應該摘錄關鍵程式碼。實作後應提出改進事項。善用 `qtest` 內建的 `time` 命令，觀察你撰寫程式的行為。
`node` 的翻譯是「節點」，而非「點」
:notes: jserv
:::
`q_sort` 將原本被拆開的節點重新連結起來
```c=
void q_sort(struct list_head *head) 
{
    if (head == NULL || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = mergesort(head->next);

    struct list_head *cur = head;
    struct list_head *next = head->next;
    while (next) {
        next->prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = head;
    head->prev = cur;
}
```
再這之後我利用雙向鏈結串列的特性，改寫 ```mergesort``` 用快慢指標找中間節點的作法，改成從頭尾開始去找，這樣便可以從共需要走訪 `1.5` 次佇列到只需要 `1` 次即可。
```c=
struct list_head *mergesort(struct list_head *l)
{
    if (!l || !l->next)
        return l;
 
    struct list_head *first = l;
    struct list_head *last = l->prev;

    while (first != last && first->next != last) {
        first = first->next;
        last = last->prev;
    }
    struct list_head *l1 = l;
    struct list_head *l2 = first->next;
    l2->prev = l->prev;
    l1->prev = first;
    first->next = NULL;
    
    return mergelist(mergesort(l1), mergesort(l2));
}
```
接下來我用 `qtest time` 去作效能測試，可以發現效能有明顯的提高

|          | 改進前    | 改進後    |
| -------- | -------- | -------- |
| 100000 筆  | 1.140     | 0.123     |
| 200000 筆  | 0.288     | 0.277     |
| 300000 筆  | 0.472     | 0.449     |
| 400000 筆  | 0.652     | 0.622     |
| 500000 筆  | 0.824     | 0.797     |
| 600000 筆  | 1.024     | 0.968     |
| 700000 筆  | 1.219     | 1.189     |
| 800000 筆  | 1.409     | 1.351     |

#### q_descend
如果點 a 的右邊有比它的值還大的點就要把點 a 移除。
關於 ```q_descend``` 的回傳值可以去 ```qtest.c``` 找，在 ```do_descend``` 裡可以看到這行 
```c
if (exception_setup(true)) current->size = q_descend(current->q);
```
表示 ```q_descend``` 要回傳佇列的長度。
因為是雙向鏈結串列，所以可以從尾端開始走訪，在走訪的過程中若發現下一個點的值小於等於當前的點的值就移除。
用 ```make test``` 進行測試時，發現之前的實作有誤，移除的點還要用 ```q_release_element``` 釋放空間。
:::warning
改進漢語表達
:notes: jserv
:::

```c=
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/ 
    if (head == NULL || list_empty(head))
        return 0;
    element_t *first = list_entry(head->prev, element_t, list);
    element_t *second = list_entry(head->prev->prev, element_t, list);
    while (&second->list != head) {
        if (strcmp(first->value, second->value) < 0) {
            second = list_entry(second->list.prev, element_t, list);
            first = list_entry(first->list.prev, element_t, list);
        }
        else {
            list_del(&second->list);
            q_release_element(second);
            second = list_entry(first->list.prev, element_t, list);
        }
    }
    return q_size(head);
}
```
#### q_merge
```queue_contex_t``` 是用來管理與其他佇列連接的結構，這邊的輸入 ```list_head *head``` 代表 ```list_head chain``` 的 ```head```。
實作程式的想法是參考[你所不知道的 C 語言: linked list 和非連續記憶體: 案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 的 Merge k Sorted Lists 的部分。
因為在文中有提到直觀的想法是用第一條佇列接上剩下的佇列，這樣會導致第一條佇列愈來愈長，立即會遇到的問題是：多數的情況下合併速度會愈來愈慢。
所以我採用的方法是 分段合併
```graphviz
digraph G {
    {
        node[shape=none,label="interval = 1"]; i1
        node[shape=none,label="interval = 2"]; i2
        node[shape=none,label="interval = 4"]; i4
        node[shape=none,label="interval = 8"]; i8
    }
    
    interval1[label="<f0>L0|<f1>L1|<f2>L2|<f3>L3|<f4>L4|<f5>L5|<f6>L6|<f7>L7", shape=record, fixedsize=false,width=6]
    interval2[label="<f0>L01|<f1>|<f2>L23|<f3>|<f4>L45|<f5>|<f6>L67|<f7>", shape=record, fixedsize=false,width=6]
    interval4[label="<f0>L0123|<f1>|<f2>|<f3>|<f4>L4567|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=6]
    interval8[label="<f0>result|<f1>|<f2>|<f3>|<f4>|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=6]
    
    i1->i2[style=invis]
    i2->i4[style=invis]
    i4->i8[style=invis]

    
    interval1:f0 -> interval2:f0
    interval1:f1 -> interval2:f0
    interval1:f2 -> interval2:f2
    interval1:f3 -> interval2:f2
    interval1:f4 -> interval2:f4
    interval1:f5 -> interval2:f4
    interval1:f6 -> interval2:f6
    interval1:f7 -> interval2:f6
    interval1:f7 -> interval2:f7[style=invis]
    
    interval2:f0 -> interval4:f0
    interval2:f2 -> interval4:f0
    interval2:f4 -> interval4:f4
    interval2:f6 -> interval4:f4
    interval2:f7 -> interval4:f7[style=invis]
    
    interval4:f0 -> interval8:f0
    interval4:f4 -> interval8:f0
    interval4:f7 -> interval8:f7[style=invis]
}
```
第一層 ```for``` 迴圈數等同 $\lceil qsize(head)/2 \rceil$，裡面的 while 迴圈裡則是做兩兩合併的操作，```first``` 是第一個要合併的佇列，```second``` 是第二個要合併的佇列，```merge_two_list``` 會把兩個佇列合併，然後把結果存到 ```first``` 並回傳合併後佇列的長度，接下來把 ```NULL``` 賦值給空的 ```second``` 然後移到 ```head``` 的尾端，用來當作 ```while``` 迴圈的中止條件，最後 ```first``` 和 ```second``` 往下移一個節點繼續做合併。
```c=
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    else if (list_is_singular(head))
        return q_size(list_first_entry(head, queue_contex_t, chain)->q);
    int size = q_size(head);
    int count = (size%2) ? size/2+1 : size/2;
    int queue_size = 0;
    for (int i = 0; i < count; ++i) {
        queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
        queue_contex_t *second = list_entry(first->chain.next, queue_contex_t, chain);
        while (first->q && second->q) {
            queue_size = merge_two_list(first->q, second->q);
            second->q = NULL;
            list_move_tail(&second->chain, head); 
            first = list_entry(first->chain.next, queue_contex_t, chain);
            second = list_entry(first->chain.next, queue_contex_t, chain);
        }
    }
    return queue_size;
}
```
更新實作： 
因為 `second->q = NULL` 會造成 `memory leak` 所以改寫 `q_merge` 的 `while` 迴圈
```c=
while (!list_empty(first->q) && !list_empty(second->q)) {
    queue_size = merge_two_list(first->q, second->q);
    list_move_tail(&second->chain, head);
    first = list_entry(first->chain.next, queue_contex_t, chain);
    second = list_entry(first->chain.next, queue_contex_t, chain);
}
```
以及把 `merge_two_list` 函式裡面的 
```c=
list_splice_tail(second, &temp_head)
```
改成
```c=
list_splice_tail_init(second, &temp_head);
```
### 在 qtest 新增 shuffle 命令
在 `console.h` 可以發現以下
```c=
/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
`add_cmd` 會在命令列表中添加新命令，要新增一條新命令 `shuffle` 則要實作 `do_shuffle`，並在`qtest.c` 的  `console_init()` 替新命令加上 `ADD_COMMAND`。
```c=
ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");
```
`qtest` 裡的 `do_shuffle` :
目前只有檢查輸入的佇列是否為空或只有一個節點
`q_shuffle` 要去 `queue.h` 新增
```c=
static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();
    if (q_size(current->q) < 2)
        report(3, "Warning: Calling shuffle on single queue");
    error_check();
    if (exception_setup(true))
        q_shuffle(current->q);
    q_show(3);
    return !error_check();
}
```
shuffle 的實作分成兩個函式: `q_shuffle` 和 `swap`
在實作 `swap` 時要注意 :
1. ```node_1``` 總是在 ```node_2``` 之後 
2. 當兩個要交換的節點是相鄰時不要做 ```list_move(node_2, node_1_prev)```，因為 `node_1_prev` 等於 `node_2`，如果做了 ```list_move(node_2, node_1_prev)``` 會把 `node_2` 這個節點移除。
```c=
static inline void swap(struct list_head *node_1, struct list_head *node_2)
{
    if (node_1 == node_2)
        return;
    struct list_head *node_1_prev = node_1->prev;
    struct list_head *node_2_prev = node_2->prev;
    if (node_1->prev != node_2) list_move(node_2, node_1_prev);
    list_move(node_1, node_2_prev);
}
```
我的 `q_shuffle` 的想法是按照 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 提供的演算法：
`new = last->prev` 是最後一個未被抽到的節點，
`old` 是 `random` 出來的節點，
將 `old` 和 `new` 交換，再將 `size` 減一，直到 `size` 變為零為止。
```c=
void q_shuffle(struct list_head *head) 
{
    if (!head || list_is_singular(head)) 
        return;
    struct list_head *last = head;
    int size = q_size(head);
    while (size > 0) {
        int index = rand() % size;
        struct list_head *new = last->prev;
        struct list_head *old = new;
        while (index--) 
            old = old->prev;
        swap(new, old);
        last = last->prev;
        size--;
    }
    return;
}
```
接下來利用腳本去測試對 `[1, 2, 3]` 執行 `shuffle` 的結果
```c=
Expectation:  166666
Observation:  {'123': 166945, '132': 167113, '213': 166658, '231': 165775, '312': 166737, '321': 166772}
```
可以從結果看到 `shuffle` 的結果分佈大致上是 `Uniform distribution`。
### 研讀 Linux 核心原始程式碼的 lib/list_sort.c
先看到函式宣告的部分
```c=
/**
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
*/
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
* [```__attribute__((nonnull()))```](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html): `compiler` 提供的 `attribute function`，可以指定該函式傳入第幾個變數必須是 `non-null`，否則會發出警告。
* `prev`: `private data`，`cmp` 的參數。
* `head`: 整個 `list` 的 `head`。
* `cmp`: `compare function`， 用來決定 `sorting order`，是 `function pointer` 的型態。

`list_sort` 函式
註解的部分跟[老師的筆記](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e)大致相同
```
* This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
 *
 * Thus, it will avoid cache thrashing as long as 3*2^k elements can
 * fit into the cache.  Not quite as good as a fully-eager bottom-up
 * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
 * the common case that everything fits into L1.
 ```
 主要是在做 `merge` 時，會將走訪過的節點維持在 `2:1` 的比例，其中 `2` 代表兩個已經排序過的佇列， `1` 代表新進來尚未排序的節點，也就是走訪到 `3∗2^k` 個 node 時才合併前面的兩個 `2^k` `sub-list`。
這種作法在 `3∗2^k` 個節點能夠完全放進 `cache` 中的情況下能夠避免 `cache thrashing` 的發生。
接下來就是程式碼的部分:
先把整個 `list` 的最後一個點的 `next` 指向 `NULL`:
```c=
head->prev->next = NULL;
```
`count` 從零開始，代表 `pending list` 節點個數，每次加入一個節點到 `pending list` 就加一。
配合前面的 `merge` 時機，只要該次迴圈的`count` 到 `count+1` 時，若 `count+1` 為 2^k^ 就不做 `merge`，反之則要做 `merge`。
舉例來說:
1. count(二進位) 變化為 ```0011 -> 0100```，不做 `merge`。
2. count(二進位) 變化為 ```0010 -> 0011```，做 `merge`。

由上述可以歸納出(以 0 ~ 16 為例)只要 `count` = `0000, 0001, 0011, 0111, 1111` 都不做 `merge`。
接下來的程式用圖來舉例說明: 
* `pending`: 為 head of pending lists ，而 pending lists 是用於暫存待合併的 sub-list of lists，每一個 sub-list 的 size 都為 power of 2 的倍數，並且各個 sub-list 以 prev 連結。
* `tail`: 指標的指標，會指向 pending 裡準備要合併的 sub-list，要合併的 sub-list 是由 count 決定。
* `list`: 目前走訪到的 node。
```c=
do {
    size_t bits;
    struct list_head **tail = &pending;

    /* Find the least-significant clear bit in count */
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    /* Do the indicated merge */
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;

        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }

    /* Move one element from input list to pending */
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
} while (list);
```
這邊舉個例子，由於不熟 `grapgviz`，所以先用 `drawio` 畫圖，之後有空會補。
以實際例子來說，如果要排序一個佇列(4->1->2->3)，可以邊對照下方表格邊看圖解。
| count 變化 | count 二進位 | merge | pending 上的節點|
| -------- | -------- | -------- | -------- |
| 0 -> 1 | 0000 -> 0001 |  no（$2^0$）   | 1 |
| 1 -> 2 | 0001 -> 0010 |  no（$2^1$）   | 1 + 1 |
| 2 -> 3 | 0010 -> 0011 |  yes   | (2) + 1 |
| 3 -> 4 | 0011 -> 0100 |  no（$2^2$）   | 2 + 1 + 1 |
* 初始化 `count` 為零，所以第一個迴圈的 `count` 變化為 `0 -> 1`，看表可以知道不用做 `merge`，把 `pending` 和 `list` 往後讀一個節點。下圖為此次迴圈做到最後的結果。
![](https://i.imgur.com/rAE2WU1.png)
* 此次 `count` 變化為 `1 -> 2`，所以也不用做 `merge`，所以 `pending` 和 `list` 往後讀一個節點。最後整個佇列會如下圖:
![](https://i.imgur.com/8bueA7E.png)
* `count` 變化為 `2 -> 3`， 要做 `merge`。
這邊的 `tail` 會指向 `pending` 的 address，
    ```c=
    struct list_head **tail = &pending;
    ```
    所以在執行下程式時 `a` 會在==上一張圖==的在 `1`，`b` 在 `4`，之後便是做 `merge`。
    然後 `merge` 會回傳合併之後的 `head` 並指派給 `a`，在本例中就是==下圖==的 `1`。
    在 `a->prev = b->prev` 中 `b->prev` 就是指向下一個 `sub-list` 的 `head`，本例中因為這就是第一個了所以是 `NULL`。
    最後 `*tail = a` 就是把 `pending` 指到 `a`，也就是 `1`。
    ```c=
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;

        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }
    ```
    此時的 `list` 指向下圖的 `2`，`pending` 指向下圖的 `1`，經過以下的運算可以得到下圖:
    ```c=
    list->prev = pending
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
    ```
    ![](https://i.imgur.com/5Hr0mLf.png)
* `count` 的變化為 `3 -> 4`，不做 `merge`，所以跟前幾個相同，`pending` 和 `list` 往後讀一個節點。
![](https://i.imgur.com/H8rihtv.png)
* 由於 `list` 等於 `NULL`，所以跳出迴圈
    `list` 指到與 `pending` 相同的節點後，
    `pending` 往前移一個節點。
    ```c=
    list = pending;
    pending = pending->prev;
    ```
    ![](https://i.imgur.com/kWz5EmT.png)
* 進入 `for` 迴圈，`next` 指到 `pending->prev` 也就是下一個 `sub-list` 的 `head`，如果 `next != NULL` 就做對 `pending` 和 `list` 做 `merge`，然後 `pending` 指到 `next` 所指的節點也就是下一個 `sub-list` 的 `head`。
![](https://i.imgur.com/bzzvC2I.png)
* 下一次進入 `for` 迴圈因為 `next` 等於 `NULL`，所以跳出迴圈，對 `pending` 和 `list` 做 `merge_final`，此函式會先把最後的兩個佇列合併後，再把 `prev` 重建回來。
![](https://i.imgur.com/94dOLFf.png)
* 最後就可以得到整個排序的佇列了!
![](https://i.imgur.com/T6zcqi3.png)

### 比較 list_sort.c 與自己的 sort.c 效能差異
先在 `qtest.c` 用 `add_param` 新增 `parameter`
```c=
add_param("linux_sort", &enable_linux_list_sort, "Enable linux list sort", NULL);
```
`enable_linux_list_sort` 是在 `qtest` 宣告的全域變數
```c=
static int enable_linux_list_sort = 0;
```
接下來修改部份 `do_sort` 程式：
```c=
if (current && exception_setup(true)) {
    if (enable_linux_list_sort)
        list_sort(NULL, current->q, compare);
    else
        q_sort(current->q);
}
```
這樣就可以透過以下命令來切換要用哪個 `sort`
```c=
option linux_sort 0
option linux_sort 1
```
接下來先修改 `queue.h`
其中 `likely 和 unlikely` 可以在 [compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 找到
```c=
# define likely(x)      __builtin_expect(!!(x), 1)            
# define unlikely(x)	__builtin_expect(!!(x), 0)

typedef uint8_t u8;

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)();

/**
 * list_sort - use linux list sort
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 */
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);

/** 
 * Compare - this function must return > 0 if @a should sort after
 * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
 * sort before @b.
 */
int compare(void* priv, struct list_head *a, struct list_head *b);
```
接下來是 `queue.c` 中的 `compare` 函式
```c=
int compare(void* priv, struct list_head *a, struct list_head *b)
{
    element_t *ele_a = list_entry(a, element_t, list);
    element_t *ele_b = list_entry(b, element_t, list);
    return strcmp(ele_a->value, ele_b->value);
}
```
接下來比較的方式用 `perf` 來做測試
參考 [blueskyson](https://hackmd.io/@blueskyson/linux2022-lab0#%E6%B8%AC%E8%A9%A6%E8%85%B3%E6%9C%AC) 的方式
在 `lab0-c` 新增 `perf-traces` 目錄，裡面放了:
```
100000.cmd
200000.cmd
300000.cmd
400000.cmd
500000.cmd
```
前面的數字代表要幾個隨機字串，以 `100000.cmd` 為例
```c=
# sort 100000 random strings
option linux_sort 0
new
it RAND 100000
sort
free
```
以下是我的實驗結果: 
* 100000 筆
```c=
/* my merge sort */
 Performance counter stats for './qtest -v 0 -f perf-traces/100000.cmd' (10 runs):

         5,465,689      cache-misses              #   42.893 % of all cache refs      ( +-  3.47% )
        12,923,171      cache-references                                              ( +-  1.43% )
       430,796,599      instructions              #    1.26  insn per cycle           ( +-  0.05% )
       350,214,286      cycles                                                        ( +-  1.42% )

           0.21634 +- 0.00417 seconds time elapsed  ( +-  1.93% )
----------------------------------------------------------------------------------------------------
/* linux list sort */
 Performance counter stats for './qtest -v 0 -f perf-traces/100000.cmd' (10 runs):

         4,715,115      cache-misses              #   43.500 % of all cache refs      ( +-  0.66% )
        10,830,099      cache-references                                              ( +-  0.75% )
       434,026,705      instructions              #    1.42  insn per cycle           ( +-  0.02% )
       303,486,799      cycles                                                        ( +-  0.16% )

          0.193264 +- 0.000793 seconds time elapsed  ( +-  0.41% )             
```
* 200000 筆
```c=
/* my merge sort */
 Performance counter stats for './qtest -v 0 -f perf-traces/200000.cmd' (10 runs):

        14,711,476      cache-misses              #   50.953 % of all cache refs      ( +-  0.54% )
        28,758,512      cache-references                                              ( +-  0.16% )
       866,082,498      instructions              #    1.23  insn per cycle           ( +-  0.01% )
       703,121,988      cycles                                                        ( +-  0.16% )

          0.442772 +- 0.000732 seconds time elapsed  ( +-  0.17% )
----------------------------------------------------------------------------------------------------
/* linux list sort */            
 Performance counter stats for './qtest -v 0 -f perf-traces/200000.cmd' (10 runs):

        12,785,220      cache-misses              #   52.422 % of all cache refs      ( +-  0.66% )
        24,082,873      cache-references                                              ( +-  0.40% )
       876,536,039      instructions              #    1.33  insn per cycle           ( +-  0.06% )
       651,662,599      cycles                                                        ( +-  0.96% )

           0.41534 +- 0.00510 seconds time elapsed  ( +-  1.23% )            
```
* 300000 筆
```c=
/* my merge sort */
Performance counter stats for './qtest -v 0 -f perf-traces/300000.cmd' (10 runs):

        25,176,158      cache-misses              #   53.992 % of all cache refs      ( +-  0.40% )
        46,354,816      cache-references                                              ( +-  0.14% )
     1,306,457,419      instructions              #    1.18  insn per cycle           ( +-  0.01% )
     1,099,759,769      cycles                                                        ( +-  0.14% )

           0.69770 +- 0.00257 seconds time elapsed  ( +-  0.37% )
----------------------------------------------------------------------------------------------------
/* linux list sort */            
 Performance counter stats for './qtest -v 0 -f perf-traces/300000.cmd' (10 runs):

        21,191,601      cache-misses              #   53.300 % of all cache refs      ( +-  2.69% )
        38,848,369      cache-references                                              ( +-  0.91% )
     1,322,133,992      instructions              #    1.23  insn per cycle           ( +-  0.03% )
     1,016,682,373      cycles                                                        ( +-  1.69% )

            0.6824 +- 0.0115 seconds time elapsed  ( +-  1.69% )
            
```
* 400000 筆
```c=
/* my merge sort */
 Performance counter stats for './qtest -v 0 -f perf-traces/400000.cmd' (10 runs):

        36,354,050      cache-misses              #   56.179 % of all cache refs      ( +-  0.36% )
        64,409,386      cache-references                                              ( +-  0.20% )
     1,747,604,644      instructions              #    1.16  insn per cycle           ( +-  0.01% )
     1,498,409,395      cycles                                                        ( +-  0.13% )

           0.94878 +- 0.00400 seconds time elapsed  ( +-  0.42% )
----------------------------------------------------------------------------------------------------
/* linux list sort */            
 Performance counter stats for './qtest -v 0 -f perf-traces/400000.cmd' (10 runs):

        30,814,049      cache-misses              #   57.978 % of all cache refs      ( +-  0.11% )
        53,256,480      cache-references                                              ( +-  0.07% )
     1,771,579,815      instructions              #    1.29  insn per cycle           ( +-  0.00% )
     1,373,081,425      cycles                                                        ( +-  0.12% )

           0.86360 +- 0.00113 seconds time elapsed  ( +-  0.13% )            
```
* 500000 筆
```c=
/* my merge sort */
 Performance counter stats for './qtest -v 0 -f perf-traces/500000.cmd' (10 runs):

        47,344,165      cache-misses              #   56.546 % of all cache refs      ( +-  0.18% )
        83,221,177      cache-references                                              ( +-  0.18% )
     2,190,772,850      instructions              #    1.14  insn per cycle           ( +-  0.01% )
     1,905,805,048      cycles                                                        ( +-  0.13% )

           1.20848 +- 0.00371 seconds time elapsed  ( +-  0.31% )
----------------------------------------------------------------------------------------------------
/* linux list sort */            
 Performance counter stats for './qtest -v 0 -f perf-traces/500000.cmd' (10 runs):

        40,109,266      cache-misses              #   58.315 % of all cache refs      ( +-  0.27% )
        68,806,922      cache-references                                              ( +-  0.18% )
     2,219,682,272      instructions              #    1.27  insn per cycle           ( +-  0.00% )
     1,747,506,164      cycles                                                        ( +-  0.38% )

           1.09820 +- 0.00412 seconds time elapsed  ( +-  0.37% )            
```
* 可以發現 `linux list sort` 的效能因為 `cache miss` 的次數明顯低於我實作的 `merge sort`，所以執行時間也比較快。
### Valgrind 排除 qtest 執行時的記憶體錯誤
發現在使用兩次以上的 `new` 後再做 `free` 會進入無限迴圈。
利用 GDB+pwndbg 作測試，可以發現程式在 `is_circular` 這個函式無限迴圈
```c=
pwndbg> run 
Starting program: /home/will/linux2023/lab0-c/qtest 
cmd> new
l = []
cmd> new
l = []
cmd> free
^C
Program received signal SIGINT, Interrupt.
is_circular () at qtest.c:856
856	    while (cur != current->q) {
```
繼續往下看可以發現是在做 `do_free` 裡的 `q_show` 的 `is_circular` 進入無限迴圈的
```c=
 ► f 0   0x555555556acc q_show+67
   f 1   0x555555556acc q_show+67
   f 2   0x5555555572a2 do_free+252
   f 3   0x55555555a055 interpret_cmda+128
   f 4   0x55555555a625 interpret_cmd+353
   f 5   0x55555555b2e3 run_console+174
   f 6   0x5555555593e2 main+1601
   f 7   0x7ffff7c97083 __libc_start_main+243
```
最後仔細檢查可以發現 `q_free` 裡的
```c=
if (chain.size > 1) {
        qnext = ((uintptr_t) &current->chain.next == (uintptr_t) &chain.head)
                    ? chain.head.next
                    : current->chain.next;
    }
```
```&current->chain.next``` 不用加 `&`
結果發現 sysprog/lab0-c 已經修正該錯誤了。
* trace-03-ops 的錯誤
```c=
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
ERROR: Freed queue, but 2 blocks are still allocated
==7825== 112 bytes in 2 blocks are still reachable in loss record 1 of 1
==7825==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7825==    by 0x10F3F4: test_malloc (harness.c:133)
==7825==    by 0x10F8A0: q_new (queue.c:18)
==7825==    by 0x10CD91: do_new (qtest.c:151)
==7825==    by 0x10E066: interpret_cmda (console.c:181)
==7825==    by 0x10E636: interpret_cmd (console.c:201)
==7825==    by 0x10EA73: cmd_select (console.c:610)
==7825==    by 0x10F37E: run_console (console.c:705)
==7825==    by 0x10D3F3: main (qtest.c:1246)
==7825== 
---	trace-03-ops	0/6
```
實際去對 `trace-03-ops` 的每個指令去作測試，發現在對兩個 `new` 出來的佇列做 `merge` 時會跳出上述的問題，因此我推測是 `merge` 有什麼地方寫錯，後來發現 `q_merge` 裡的 `while` 迴圈的 `second->q = NULL` 是不對的。預期的輸出是若有兩個佇列 `a` 和 `b` 要和併到 `a`，把 `b` 的所有節點移到 `a` 時也要把 `b` 做初始化的動作，也就是要保留 `second->q`，所以如果直接做 `second->q ＝ NULL` 會造成 `memory leak` 的問題。
重新修改程式後順利排除記憶體的所有問題
```c=
will@will:~/linux2023/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/will/linux2023/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  CC	shannon_entropy.o
  CC	linenoise.o
  CC	web.o
  LD	qtest
make[1]: Leaving directory '/home/will/linux2023/lab0-c'
cp qtest /tmp/qtest.5cWFNg
chmod u+x /tmp/qtest.5cWFNg
sed -i "s/alarm/isnan/g" /tmp/qtest.5cWFNg
scripts/driver.py -p /tmp/qtest.5cWFNg --valgrind 
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100
```
### 論文閱讀：Dude, is my code constant time?
[論文連結](https://eprint.iacr.org/2016/1123.pdf)
[dudect Github](https://github.com/oreparaz/dudect)
[參考](https://hackmd.io/E8DJnIryRwCo48uVQnuNDA?view)
這篇論文的貢獻是，透過自己開發的 dudect，一個透過統計分析的程式判斷程式是否是 constant-time 在給定的平台之下。
實作可分為以下步驟:
* A. Step 1: Measure execution time
    - a) `Classes definition`: 給定兩種不同類別的輸入資料，重複對方法進行測量，最常見的就是 fix-vs-random tests
    - b) `Cycle counters`: 現今的 CPU 提供的 cycle counters 可以很精準的獲得執行的時間。
    - c) `Environmental conditions`: 為了減少環境的差異，每次測量都會對應隨機的輸入類別。
* B. Step 2: Apply post-processing
    - a) `Cropping`: 剪裁掉一些超過 threshold 的測量結果
    - b) `Higher-order preprocessing`: Depending on the statistical test applied, it may be beneficial to apply some higherorder pre-processing
* C. Step 3: Apply statistical test
    - a) `t-test`: Welch’s t-test，測試兩個平均數是否相同
    - b) `Non-parametric tests`:(無母數統計分析): Kolmogorov-Smirnov
### dudect
* 跟據作業說明：「在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 `percentile` 的處理，但在 `lab0-c` 則無。」。所以我去對照發現 `lab0-c` 的 `fixture.c` 確實沒有實作，造成極端值沒有被去除，導致判斷結果出錯。
* 將 [oreparaz/dudect](https://github.com/oreparaz/dudect) 處理 `percentile` 的部分加入 `lab0-c` 的 `fixture.c` 後便可以正確分析 `insert_head`, `insert_tail`, `remove_head`, `remove_tail` 的執行時間。
```c=
static int cmp(const int64_t *a, const int64_t *b)
{
    return (int) (*a - *b);
}

static int64_t percentile(int64_t *a, double which, size_t size)
{
    qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp);
    size_t array_position = (size_t)((double) size * (double) which);
    assert(array_position >= 0);
    assert(array_position < size);
    return a[array_position];
}

/*
 set different thresholds for cropping measurements.
 the exponential tendency is meant to approximately match
 the measurements distribution, but there's not more science
 than that.
*/
static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times)
{
    for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
        percentiles[i] = percentile(
            exec_times,
            1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),
            N_MEASURES);
    }
}
```

### 引入 treesort
[筆記連結](https://hackmd.io/@willwillhi/treesort)