---
# System prepended metadata

title: 2024q1 Homework2 (quiz1+2)

---

# 2024q1 Homework2 (quiz1+2)
contributed by < [youjiaw](https://github.com/youjiaw/lab0-c) >

## 第 1 週測驗題
### 測驗 `1`
鏈結串列結構體如下:
```c
typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;
```
```graphviz
digraph
{
    node [shape="record"];
    rankdir = "LR"
    subgraph cluster_node
    {
        label = "node_t";
        node_t [label="<v>value|<n>next|{<l>left|<r>right}"];
    }
}
```
<!-- 對應的操作函式有以下五個：
* `void list_add(node_t **list, node_t *node_t)`
* `node_t *list_tail(node_t **left)`
* `int list_length(node_t **left)`
* `node_t *list_construct(node_t *list, int n)`  
* `void list_free(node_t **list)` -->

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

* 經由迴圈不斷將 `left` 指向下一個節點，最後回傳鏈結串列的最後一個節點，因此 `AAAA` 為 `(*left)->next`。
```diff
node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
-       left = &(AAAA);
+       left = &((*left)->next);
    return *left;
}
```

**`list_length`**

* 與前者相同，使用迴圈逐一走訪每個節點來計算長度，因此 `BBBB` 同為`(*left)->next`。
```diff
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`。
```diff
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)`。

```diff
    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。
1. 依照陣列的值，依序建立鏈結串列的節點。
1. 進行非遞迴的快速排序法，最後檢查排序結果。

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

* 一開始，用來記錄範圍的指標 `L` 與 `R` 分別為鏈結串列的開頭與結尾， `pivot` 為開頭節點，用來走訪節點的 `p` 則是 `pivot->next`。
* 將 `value` 設為 `pivot` 的值，並把 `pivot->next` 指向 NULL。
```graphviz
digraph g_1 {
    node [shape=box, fontsize=15, fontcolor=black];
    2 -> 5 [style=dashed];
    5 -> 3 -> 4 -> 1;
    value [shape=plaintext, fontsize=15, label="value",fontcolor=cadetblue];
    v [label="2", color=cadetblue, fontcolor=cadetblue];
    value -> v [style=invis];
    value -> v [style=invis];
    v -> 2[style=invis];

    node [shape=plaintext, fontsize=15];
    pivot [fontcolor=red];
    L [fontcolor=blue];
    R [fontcolor=blue];
    pivot -> 2 [color=red];
    L -> 2 [color=blue];
    R -> 1 [color=blue];
    p -> 5 ;
    
    { rank=same; v 4 5 3 2 1; };
    { rank=same; value pivot L R;};
}
```

* 用指標 `n` 指向 `p` 並逐一走訪節點。
    * 若 `n->value` > `value`：將此節點新增至 `right`。
    * 若 `n->value` <= `value`：將此節點新增至 `left`。
```graphviz
digraph g_3 {
    node [shape=box, fontsize=15, fontcolor=black];
    1;
    2;
    4 -> 3 -> 5;
    
    node [shape=plaintext, fontsize=15];
    left [fontcolor=blue];
    pivot [fontcolor=red]
    right [fontcolor=blue];
    left -> 1;
    pivot -> 2;
    right -> 4;

    // {rank=same; left 1;}
    // {rank=same; right 3 4 5;}
}
```
* 最後，將 `left`, `pivot` 及 `right` 的範圍記錄在 `begin` 與 `end`。
* 迴圈會不斷排序 `right`，直到剩下一個節點，並將其加到 `result` 的開頭，再向左邊進行排序，因此 `result` 中的節點最後會是由小排到大。

#### 改進方案：

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

**決定 `begin` 與 `end` 的空間**

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

但是若有 worst case 出現，就會需要 **2 * n - 1** 的空間，以下為 n = 10 時的 worst case，此時 `begin` 與 `end` 的最大深度為 19。
```c
int arr[] = {0,2,4,6,8,9,7,5,3,1};
```

**檢查 malloc 是否成功**

參照 [tools/perf/util/intlist.c](https://elixir.bootlin.com/linux/latest/source/tools/perf/util/intlist.c#L18) 的程式碼，加入 malloc 的檢查。
:::info
查閱 Linux 核心程式碼時，發現 [scripts/kconfig/lxdialog/checklist.c](https://elixir.bootlin.com/linux/latest/source/scripts/kconfig/lxdialog/checklist.c#L21) 並沒有在 malloc 後進行檢查，這是為什麼？
:::



**使用雙向鏈結串列**
雙向鏈結串列可以改善以下的函式：
* `*list_tail(node_t **left)` 的時間複雜度由 O(N) 變為 O(1)。
* `quick_sort(node_t **list)` 的 `end` 可以移除。

:::warning
TODO: 改為雙向鏈結串列
:::

#### 3. 使用 Linux 核心風格的 List API 改寫上述程式碼。
於 commit [0286652](https://github.com/youjiaw/linux2024-homework/commit/028665250ff73d965896de6102e8273615b785cf) 改寫。

---
### 測驗 `2`
#### 1. 補完程式碼，使其得以符合預期運作
**`*merge`**
                               
`merge` 會把兩個已排序的鏈結串列，合併成一個新的已排序鏈結串列，用 `*head` 與 `**tail` 紀錄。
* 一開始鏈結串列是空的，所以將 `**tail` 初始化為 `&head`。

```diff
    struct list_head *head;
-   struct list_head **tail = AAAA;
+   struct list_head **tail = &head;
```
* 接著比較 `a` 與 `b` 的第一個節點，將比較小的節點加到新的鏈結串列尾部，因此 `BBBB` 為 `&a->next`，`CCCC` 則為 `&b->next`。

<!-- :::spoiler `merge` 程式碼 -->
```diff
        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`，走訪到尾部就會跳出迴圈，因此最後要將頭尾相連。

<!-- :::spoiler `build_prev_link` 程式碼 -->
```diff
-   DDDD = head;
-   EEEE = tail;
+   tail->next = head;
+   head->prev = tail;
```
<!-- ::: -->

**`timsort`**

Timsort 最後會確認是否有剩下的節點，如果有就會做 `merge_final`，因此 `FFFF` 為1。
```diff
-   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](https://github.com/sysprog21/lab0-c)

---
## 第 2 週測驗題
### 測驗 `1`
#### 1. 補完程式碼，使其得以符合預期運作
**`hlist_add_head`**

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

```diff
    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]`。

```diff
    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。

```diff
    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`。
```diff
    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`。


```diff
    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`
