# 2019q1 Homework1(list)
contributed by < `st9540808` >

* [F02: list](https://hackmd.io/s/S12jCWKHN)

## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

有一些操作只能用 macro 實作像是 `list_for_each` ，需要展開成 for 才能支援這種循序走訪。
一般的 function call，caller 需要把引數放到 stack 中，新增一段新的 stack，並在回傳時收回，macro 沒有這些操作的成本
參考: [x86 calling convention](https://en.wikibooks.org/wiki/X86_Disassembly/Calling_Conventions)

### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
> v4.20.13 kernel/sched/sched.h, line 228
`struct rq` 是 linux 中的 runqueue，裡面有兩個成員 `struct cfs_rq cfs` CFS 的排程器和 `struct rt_rq rt` 即時排程器的 runqueue，即時任務總共有 100 個優先級 (0-99)，所以在 `struct rt_rq rt` 中有一個 `struct rt_prio_array` 的實體 `active`，對應的 runnable 及時任務會被放在相對應優先級的 runqueue 中

struct rt_prio_array {
	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
	struct list_head queue[MAX_RT_PRIO];
};

:::warning
列出 Linux 核心版本並 **解說**
只有列出結構體，不能算是解說，而要廣泛提及針對該結構體做了哪些 linked list 操作，又考量點為何
:notes: jserv
:::

### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

## merge sort 實作
### function prototype:

list_ele_t *get_middle(struct list_head *list);
void list_merge(struct list_head *lhs,
                struct list_head *rhs,
                struct list_head *head);
void list_merge_sort(queue_t *q);

`queue_t` 和 `list_ele_t` 的定義是從 lab0 引入，在兩者中都加入 `struct list_head` ，以便最終能夠支援 qtest

merge sort 需要兩個輔助的函式以便實作 `list_merge_sort()` ，兩個函式的說明如下:
* `get_middle()`: 回傳一個 list 中，位於中間節點的位址
* `list_merge()`: 合併兩個已排序的 list

### 實作細節
#### `get_middle()`
使用兩個指標 `fast slow` 來走訪 list，`fast` 一次會前進 2 個節點，`slow` 一次會前進 1 個。
參考: [Floyd Cycle Detection Algorithm](https://zh.wikipedia.org/wiki/Floyd%E5%88%A4%E5%9C%88%E7%AE%97%E6%B3%95)

list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast, *slow;
    fast = list->next;
    list_for_each (slow, list) {
        if (fast->next != list && fast->next->next != list)
            fast = fast->next->next;
        else
            break;
    }
    return list_entry(slow, list_ele_t, list);
}

#### `list_merge()`
將兩個已排序好的 list `lhs rhs` 合併在一起並傳給 `head`，因為排序對象是字串，排序完要變成字典序，所以用 `strcmp()` 比較兩個字串在字典中的順序，

void list_merge(struct list_head *lhs,
                struct list_head *rhs,
                struct list_head *head)
{
    struct list_head *temp;

    INIT_LIST_HEAD(head);
    if (list_empty(lhs)) {
        list_splice_tail(lhs, head);
        return;
    }
    if (list_empty(rhs)) {
        list_splice_tail(rhs, head);
        return;
    }

    while (!list_empty(lhs) && !list_empty(rhs)) {
        if (strcmp(list_entry(lhs->next, list_ele_t, list)->value,
                   list_entry(rhs->next, list_ele_t, list)->value) <= 0)
            temp = lhs->next;
        else
            temp = rhs->next;
        list_del(temp);
        list_add_tail(temp, head);
    }
    list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}

#### `list_merge_sort()`
合併排序的主演算法，全部使用 `list_*` 的操作
1. 檢查 list 是否只有一個節點 (遞迴的中止條件)
2. 將 list 切成兩份，左邊的在 `left` ，右邊的在 `q`
3. 遞迴呼叫 ```list_merge_sort(&left); list_merge_sort(q); ```
4. 將左右兩個 list 合併，並將合併後的 list 放入 `q`

void list_merge_sort(queue_t *q)
{
    struct list_head sorted;
    queue_t left;

    if (list_is_singular(&q->list))
        return;

    INIT_LIST_HEAD(&left.list);
    list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
    list_merge_sort(&left);
    list_merge_sort(q);
    list_merge(&left.list, &q->list, &sorted);
    INIT_LIST_HEAD(&q->list);
    list_splice_tail(&sorted, &q->list);
}

merge sort 與 quick sort 的效能比較，資料來自 [dict](https://github.com/sysprog21/dict) 的 [cities.txt](https://github.com/sysprog21/dict/blob/master/cities.txt) ，內含九萬多筆城市的字串，並分別對 30000、60000、90000 筆資料做排序，比較兩種演算法對**亂序資料**的排序效能。

可以看到 quick sort 比起 merge sort 有比較好的效能表現，但如果排序資料是已經排序好的，就會出現 worst case $O(n^2)$ 的時間複雜度。

`list_merge()` 需要插入 n 個節點，每次比較都要呼叫 `strcmp()` ，但因為測試資料中字串的最大長度是固定的，所以每次比較需要 $Θ(1)$。 `list_merge_sort()` 的時間複雜度可以用以下遞迴式表示:

$T(n) = 2T(n/2) + Θ(1)$

用 master theorem 可以解以上式子，得到 $T(n) = Θ(nlogn)$