2019q1 Homework1(list)

contributed by < st9540808 >

• F02: list

自我檢查事項

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

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

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];
};

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

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

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 的 cities.txt ，內含九萬多筆城市的字串，並分別對 30000、60000、90000 筆資料做排序，比較兩種演算法對亂序資料的排序效能。

可以看到 quick sort 比起 merge sort 有比較好的效能表現，但如果排序資料是已經排序好的，就會出現 worst case

$O(n^2)$ 的時間複雜度。

list_merge() 需要插入 n 個節點，每次比較都要呼叫 strcmp() ，但因為測試資料中字串的最大長度是固定的，所以每次比較需要

$\Theta (1)$。 list_merge_sort() 的時間複雜度可以用以下遞迴式表示:

$T(n)=2T(n/2)+\Theta (1)$

用 master theorem 可以解以上式子，得到

$T(n)=\Theta (nlogn)$