# 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`
Sign in with Wallet
Connect another wallet