2024q1 Homework2 (quiz1+2)

contributed by < youjiaw >

第 1 週測驗題

測驗 1

鏈結串列結構體如下:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

1. 補完程式碼，使其得以符合預期運作

*list_tail

• 經由迴圈不斷將 left 指向下一個節點，最後回傳鏈結串列的最後一個節點，因此 AAAA 為 (*left)->next。

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
-       left = &(AAAA);
+       left = &((*left)->next);
    return *left;
}

list_length

• 與前者相同，使用迴圈逐一走訪每個節點來計算長度，因此 BBBB 同為(*left)->next。

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
-       left = &(BBBB);
+       left = &((*left)->next);
    }
    return n;
}

quick_sort

• 下方程式碼會將鏈結串列中，大於 pivot 的節點加到 right，小於等於 pivot 的節點加到 left，因此 CCCC 為 p->next。

while (p) {
    node_t *n = p;
-   p = CCCC;
+   p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

• 走訪所有節點後，將 left, pivot 及 right 的範圍資訊存放在 begin 及 end。
• 因此，DDDD 為 list_tail(&left)，EEEE 為 list_tail(&right)。

    begin[i] = left;
-   end[i] = DDDD;
+   end[i] = list_tail(&left);
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
-   end[i + 2] = EEEE;
+   end[i + 2] = list_tail(&right);

2. 解釋程式碼的運作原理，提出改進方案並予以實作

運作流程：

1. 將長度為 count，值為 0 至 count-1 的陣列進行 shuffle。
2. 依照陣列的值，依序建立鏈結串列的節點。
3. 進行非遞迴的快速排序法，最後檢查排序結果。

其中，非遞迴的快速排序法是用堆疊模擬遞迴呼叫。

• 一開始，用來記錄範圍的指標 L 與 R 分別為鏈結串列的開頭與結尾， pivot 為開頭節點，用來走訪節點的 p 則是 pivot->next。
• 將 value 設為 pivot 的值，並把 pivot->next 指向 NULL。

• 用指標 n 指向 p 並逐一走訪節點。
  • 若 n->value > value：將此節點新增至 right。
  • 若 n->value <= value：將此節點新增至 left。

• 最後，將 left, pivot 及 right 的範圍記錄在 begin 與 end。
• 迴圈會不斷排序 right，直到剩下一個節點，並將其加到 result 的開頭，再向左邊進行排序，因此 result 中的節點最後會是由小排到大。

改進方案：

我的想法為：

• begin 與 end 是否真的需要兩倍的空間？
• 目前是假設 malloc 總是成功，因此需要加入檢查的程式碼。
• 使用雙向鏈結串列。

決定 begin 與 end 的空間

經過測試，在有 shuffle 的狀況下，list 的長度每增加十倍，begin 與 end 的最大深度只增加不到一倍。

但是若有 worst case 出現，就會需要 2 * n - 1 的空間，以下為 n = 10 時的 worst case，此時 begin 與 end 的最大深度為 19。

int arr[] = {0,2,4,6,8,9,7,5,3,1};

檢查 malloc 是否成功

參照 tools/perf/util/intlist.c 的程式碼，加入 malloc 的檢查。

查閱 Linux 核心程式碼時，發現 scripts/kconfig/lxdialog/checklist.c 並沒有在 malloc 後進行檢查，這是為什麼？

使用雙向鏈結串列
雙向鏈結串列可以改善以下的函式：

• *list_tail(node_t **left) 的時間複雜度由 O(N) 變為 O(1)。
• quick_sort(node_t **list) 的 end 可以移除。

TODO: 改為雙向鏈結串列

3. 使用 Linux 核心風格的 List API 改寫上述程式碼。

於 commit 0286652 改寫。

---

測驗 2

1. 補完程式碼，使其得以符合預期運作

*merge

merge 會把兩個已排序的鏈結串列，合併成一個新的已排序鏈結串列，用 *head 與 **tail 紀錄。

• 一開始鏈結串列是空的，所以將 **tail 初始化為 &head。

    struct list_head *head;
-   struct list_head **tail = AAAA;
+   struct list_head **tail = &head;

• 接著比較 a 與 b 的第一個節點，將比較小的節點加到新的鏈結串列尾部，因此 BBBB 為 &a->next，CCCC 則為 &b->next。

        if (cmp(priv, a, b) <= 0) {
            *tail = a;
-           tail = BBBB;
+           tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
-           tail = CCCC;
+           tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }

build_prev_link

在走訪所有節點的同時建立 prev，走訪到尾部就會跳出迴圈，因此最後要將頭尾相連。

-   DDDD = head;
-   EEEE = tail;
+   tail->next = head;
+   head->prev = tail;

timsort

Timsort 最後會確認是否有剩下的節點，如果有就會做 merge_final，因此 FFFF 為1。

-   if (stk_size <= FFFF) {
+   if (stk_size <= 1) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);

2. 解釋程式碼的運作原理，提出改進方案並予以實作

3. 將改進過的 Timsort 實作整合進 sysprog21/lab0-c

---

第 2 週測驗題

測驗 1

1. 補完程式碼，使其得以符合預期運作

hlist_add_head

把節點加入到開頭位置，要將新節點的指標指向"原本的開頭節點"和"指向原本開頭節點的指標"。

    if (h->first)
        h->first->pprev = &n->next;
-   n->next = AAAA;
+   n->next = h->first;
    n->pprev = &h->first;
    h->first = n;

node_add

依照節點的值，對 size 取餘數得到相對應的 hash 值，並呼叫 hlist_add_head 將該節點加到該雜湊表中，即 &heads[hash]。

    int hash = (val < 0 ? -val : val) % size;
-   hlist_add_head(&on->node, DDDD);
+   hlist_add_head(&on->node, &heads[hash]);

find

find 的目的是找出節點在中序的位置，因此取得 hash 值後，會用迴圈找尋對應的雜湊表 &heads[hash] 是否有符合該節點值的 order_node，並返回該節點的 index。

    static int find(int num, int size, const struct hlist_head *heads)
    {
        struct hlist_node *p;
        int hash = (num < 0 ? -num : num) % size;
-    hlist_for_each (p, BBBB) {
-           struct order_node *on = CCCC(p, struct order_node, node);
+       hlist_for_each (p, &heads[hash]) {
+           struct order_node *on = list_entry(p, struct order_node, node);
            if (num == on->val)
                return on->idx;
        }
        return -1;
    }

2. 解釋程式碼的運作原理，提出改進方案並予以實作

運作流程：

1. 建立一個與中序長度相同的雜湊表，並初始化指向第一個節點的指標 first 為 NULL。
2. 依照中序的順序，將每個節點加到對應的雜湊表，分為兩個步驟。
   1. 將節點的值（val）與其在中序的位置（idx）紀錄在 order_node 結構中。
   2. 取得該節點的 hash 值後，更改節點與對應雜湊表的指標，將節點加在雜湊表的開頭。
3. 使用 dfs 建構二元數。
   1. 依照前序的順序，使用 find 找出該節點在中序的 idx。
   2. 使用遞迴依次建構左、右子樹，直到節點均被走訪完。

3. 在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

---

測驗 2

1. 補完程式碼，使其得以符合預期運作

hlist_del

刪除傳入的節點 n。

    void hlist_del(struct hlist_node *n)
    {
        struct hlist_node *next = n->next, **pprev = n->pprev;
        *pprev = next;
        if (next)
-           EEEE = pprev;
+           next->pprev = pprev;
    }

lRUCacheFree

此函式會走訪所有節點並將其刪除，由於 pos 是 list_head 結構， list_entry 的 member 應傳入 link。

    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
-       LRUNode *cache = list_entry(pos, LRUNode, FFFF);
-       list_del(GGGG);
+       LRUNode *cache = list_entry(pos, LRUNode, link);
+       list_del(&cache->link);
        free(cache);
    }

lRUCacheFree

2. 解釋程式碼的運作原理，提出改進方案並予以實作

運作流程：

3. 在 Linux 核心找出 LRU 相關程式碼並探討

---

測驗 3