# 2024q1 Homework2 (quiz1+2)
contributed by < `Shawn531` >
## 第一週題目
### 測驗一
在這個測驗中，參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)，實作非遞迴 (non-recursive; iterative) 的快速排序法。
#### 資料型態
這一支程式使用的鏈結串結構體如下，使用了單向串列，有別於 `list.h` 的雙向串列，而結構體中的 `left` `right` 並未使用，因此在此不討論。
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
#### 程式說明
`max_level = 2 * n` 為堆疊的最大深度，而呼叫這個函式的一開始就會先宣告兩個深度為 2n 的陣列，來保存每個堆疊的開始結束節點，也就是說不管事甚麼情況，這隻程式皆會開出兩個大小為 2n 的空間來做堆疊。
```c
int n = list_length(list);
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
```
進到 while 迴圈後，首先用 L 和 R 獲取當前堆疊的開始和結束節點。之後我們選定基準值 `pivot` 並保存到 `value` 中，最一開始的 pivot 都會以最左邊的節點當作 pivot，但這樣或許對部分排序的 list 會造成浪費，因此我認為能夠在 sorting 前加入判斷是否有部分排列的函式來去選擇 pivot，不過也需要對結束條件一起做考慮。
爾後利用 `while (p) {...}` 處理剩餘的節點，若是大於 `value` 則放進 `right`，反之則放進 `left`。
我們可以將整個 list 依大小分為三個部分，一個是大於 `pivot->value` 的集合 `right` 、 `pivot` 和小於 `pivot->value` 的集合。這一步驟後我們即可以獲得三個集合。之後`left = right = NULL; i += 2;` 重置 left 和 right，並移動到下一層次。
可以看到從原本的 [4 1 3 5 2 7] 可以分成 left, pivot, right三堆。
```graphviz
digraph G {
rankdir=LR;
// size="10"
node [shape = square, width=1, height=1];
S1 [label = 4];
S2 [label = 1];
S3 [label = 3];
S4 [label = 5];
S5 [label = 2];
S6 [label = 7];
node [shape = none];
P [label = "*list"];
S1 -> S2 -> S3 -> S4 -> S5 -> S6;
P -> S1;
}
```
```graphviz
digraph G {
label="First Iteration";
labelloc=top;
rankdir=td;
node [shape = square];
s2 [label = 1];
s3 [label = 3];
s4 [label = 5];
s5 [label = 2];
s6 [label = 7];
pivot [label = 4];
node [shape = none];
// n1 [label = head];
ppivot [label = pivot_i1];
left [label = left_i1];
right [label = right_i1];
null1 [label = NULL];
null2 [label = NULL];
null3 [label = NULL];
left -> s2 -> s3 -> s5 -> null2;
right -> s4 -> s6 -> null1;
ppivot -> pivot -> null3;
s5 -> pivot [color=transparent];
{rank=same; s2; s3; s5; pivot; s4; s6}
}
```
由於 `i = i + 2;` 因此我們從上一個 iteration 的 right 開始解析，同樣可以在拆成 left, pivot, right，然後到下一個 iteration 時，由於剛剛的 pivot, right 都只有一個節點，因此會依序加到 result 中。
之後我們從 right 解析來看，上一輪的 right 在這一輪又可以分堆成 left, pivot, right，這邊的 left 雖然為 NULL，但在後面步驟會檢查因此不用擔心。
```graphviz
digraph G {
rankdir=LR;
// size="10"
node [shape = square, width=1, height=1];
S5 [label = 5];
S7 [label = 7];
node [shape = none];
P [label = "right_i1"];
NULL [label = "NULL"];
P -> S5 -> S7 -> NULL;
}
```
```graphviz
digraph G {
rankdir=TD;
// size="10"
node [shape = square, width=1, height=1];
S5 [label = 5];
S7 [label = 7];
node [shape = none];
P [label = "pivot_i2"];
R [label = "right_i2"];
NULL1 [label = "NULL"];
NULL2 [label = "NULL"];
P -> S5 -> NULL1;
R -> S7 -> NULL2;
}
```
所以整個 list 目前就會像下方這樣，會看到有一個 3 個元素的串列和 3 個 1 個 元素的串列，下一次 iteration 的時候，就會把這一些只有一個元素的串列處理並依序加入 `result` 中:
```graphviz
digraph G {
label="second iteration";
labelloc=top;
node [shape = square];
s2 [label = 1];
s3 [label = 3];
s4 [label = 4];
s5 [label = 2];
s6 [label = 7];
pivot [label = 5];
node [shape = none];
// n1 [label = head];
ppivot [label = pivot];
left [label = left];
right [label = right];
null1 [label = NULL];
null2 [label = NULL];
null3 [label = NULL];
s2 -> s3 -> s5
left -> null1;
ppivot -> pivot -> null2;
right -> s6 -> null3;
s5 -> s4 -> null1 -> pivot -> s6 [color=transparent];
{rank=same; s2; s3; s5; pivot; s4; s6; null1}
}
```
其實在一般遞迴版本的 quiksort 裡面，到目前為止的步驟都是相似的，差別就是一般是使用遞迴方式實作，而在這段程式碼則使用了 stack 來代替，我認為使用 stack 來代替遞迴的優勢在於，雖然在一開始就必須先開 2 個 2n 的陣列讓他放，而遞迴版本實際上也是用 stack ，只不過它是由 assembler 所產生，因為程式遞迴而產生的組語的大小我認為會比使用 stack 代替的陣列來的小很多，而在運行時間也會優化許多雖然說這取決於編譯器。
回到程式說明的部分，之後我們就會回到迴圈一開始然後 `node_t *L = begin[i], *R = end[i];`，然後檢查 L 和 R 是不是指向同一個位置，如果不是，就繼續做上述步驟，也就是繼續拆解的意思。如果他們是同一個，那就代表這是最後一個了，該把這個節點加進 result 裡面了，然後 i--，做到最後就可以完成整個排序。如下圖，`result` 是已經排序好的結果，因此我們只需針對尚未處理過的照著上面的流程走過一遍，即可完成排序。
我們發現發現 `4` `5` `7` 現在都是自己一堆了，因此他會被依序加入 result 中，然後我們就可以繼續處理最一開始遺留下來的 left ，接下來的步驟就跟剛剛完全一模一樣了。
```graphviz
digraph G {
rankdir=TD;
node [shape = square];
s1 [label = 1];
s2 [label = 2];
s3 [label = 3];
s4 [label = 4];
s5 [label = 5];
s7 [label = 7];
node [shape = none];
// n1 [label = head];
ppivot [label = pivot];
right [label = right];
null1 [label = NULL];
null2 [label = NULL];
Result [label = Result];
ppivot->s1->null1
right->s3->s2->null2
Result -> s7 -> s5 -> s4
{rank=same; s1; s3; s2; Result; s7;s5; s4}
}
```
```c
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = head->prev;
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_tail(n, n->value > value ? &right : &left);
}
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
} else {
if (L)
list_add_tail(L, result);
i--;
}
}
*list = result;
}
```
`list_tail` 要找串列的最後一個元素，理所當然的 `AAAA`會是 `(*left)->next`。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
`list_length` 透過走訪整條串列計算長度，因此 `BBBB` 也會是 `(*left)->next`。
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
#### 使用 Linux 核心風格的 List API 改寫上述程式碼
在測驗一使用到的操作函式 `list_add` `list_tail` `list_length` `list_construct` `list_free` 在 `list.h` 皆有相同功能的操作函式。因此我們可以直接改寫 `quick_sort`。在此須特別注意的是單向與雙向鏈結串列的處理。
再新增串列陣列時，有遇到以下問題，C90 標準不允許使用 variable length array，因此我將程式碼改為用 `malloc`配置記憶體。我也試過將 Makefile 的 `CFLAGS` 改成 C99 的標準，但後來想想這好像不符合規範，因此採用動態配置記憶體的方式。
```bash
addop.c:37:5: error: ISO C90 forbids variable length array ‘begin’ [-Werror=vla]
37 | element_t *begin[max_level];
| ^~~~~~~~~
```
```diff
- element_t *begin[max_level];
- element_t *end[max_level];
+ element_t **begin = malloc(max_level * sizeof(element_t *));
+ element_t **end = malloc(max_level * sizeof(element_t *));
```
```
# Emit a warning should any variable-length array be found within the code.
# CFLAGS += -Wvla
CFLAGS = -std=c99
```
目前是將`q_quicksort`整合進 `lab0-c` 的專案中，額外開了一個檔案`addop.c`來存放額外的函式如 `shuffle`。我有參閱其他同學的作法，很多人的實作方式是將 quicksort 會引用到的 funciton 進行改寫，我的作法是因為舊功能來說，`list.h`的功能已經相當完善，因此我是針對 quicksort 這個函式做修改，然而在實作方面遇到了一些記憶體洩漏的問題尚未解決，因此先在此記錄，未來待改善。
```c
void q_quicksort(struct list_head *head)
{
int n = q_size(head);
char *value;
int i = 0;
int max_level = 2 * n;
// element_t *begin[max_level];
// element_t *end[max_level];
element_t **begin = malloc(max_level * sizeof(element_t *));
element_t **end = malloc(max_level * sizeof(element_t *));
struct list_head *result = NULL, *left = NULL, *right = NULL;
// list_entry(head->next, element_t, list)
begin[0] = list_entry(head->next, element_t, list);
end[0] = list_entry(head->prev, element_t, list);
while (i >= 0) {
element_t *L = begin[i], *R = end[i];
if (L != R) {
element_t *pivot = L;
value = pivot->value;
struct list_head *p = (&pivot->list)->next;
(&pivot->list)->next = NULL;
while (p) {
struct list_head *n = p;
p = p->next;
element_t *node_e = list_entry(n, element_t, list);
list_add_tail(n,
strcmp(node_e->value, value) == 1 ? left : right);
}
begin[i] = list_entry(left->next, element_t, list);
end[i] = list_entry(left->prev, element_t, list);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = list_entry(left->next, element_t, list);
end[i + 2] = list_entry(left->prev, element_t, list);
left->next = right->next = NULL;
i += 2;
} else {
if (L)
list_add_tail(&L->list, result);
i--;
}
}
head = result;
free(begin);
free(end);
}
```
### 測驗二
#### Timsort
Tim Peters注意到在現實世界的資料中，通常存在著部分已經排序的子序列，這些子序列被稱為 "run"。他的排序策略是先識別這些已排序的子序列，然後通過不斷地合併這些 run 來實現對整個資料範圍的排序。
通過尋找 run 來實現資料的分堆效果，同時注意到單調遞減的 run 會在合併過程中被反轉成遞增的序列。
為了提高合併過程的均衡性，Timsort 定義了一個參數 minrun，表示每個 run 的最小長度。然而在這次的實作中，我們暫時不考慮 minrun，未來可能會引入以進一步提升效能。最佳的效能通常在 run 的數量等於或者略小於 2 的冪時實現，而在 run 數量略大於 2 的冪時，效能會下降。
也不考慮 Galloping mode 的問題，gallping 的特點就是不用從頭開始比對，假設有 A B 兩個排列好的數列，首先尋找 B 的首個元素在 A 中的排序位置，從而確定 A 中有一段是小於 B 的第一位，可以將這部分放回 A，接著尋找剩餘 A 的首個元素在 B 中的位置，如此反覆進行，直到完成排序。這次實作也沒有實現這一個功能，因此會於未來嘗試改進。
#### 程式實作
直接看到主要的函式 `timsort` ，首先會先檢查 head 並將其轉換為以 null 結尾的單向鏈表，之後開始查找 run 的步驟。`find_run`的主要功能就是將 run 進行分堆，會先找尋升序的元素直到不再升序為止，此時則會開始找尋降序的元素直到升序為止，如此交替進行便可以找到每一個 run。更新 run 開始節點的 prev 指針，使用 `tp` 指向的前一個 run 的結束節點，將下一個 run 的開始節點的 prev 指向它。更新 tp 指針使 `tp` 指向當前 run 的開始節點。然後將 `list` 指向當前 run 的結束節點的下一個節點，以繼續尋找下一個 run。增加堆疊大小 stk_size。最後使用 `merge_collapse` 函數對遞增的 run 堆疊進行合併。
```c
do {
/* Find next run */
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
```
值得注意的是，若此串列是降序的排列，我們需要將它反轉成升序排列，做法是先初始化一個指針 `prev` 用於記錄反轉後的前一個節點。do-while 在遞減的 run 中遍歷，將目前節點 list 的 next 指向 prev，然後更新 prev 和 list。最後再將一個`list->next` 設置為 prev，完成反轉。
```c
if (cmp(priv, list, next) > 0) {
/* decending run, also reverse the list */
struct list_head *prev = NULL;
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;
} else {
do {
len++;
list = next;
next = list->next;
} while (next && cmp(priv, list, next) <= 0);
list->next = NULL;
}
```
`merge_collapse`簡單來說就是在讓堆疊中的 run 進行合併操作，而其中必須符合演算法中的一些規範，才會進行合併，利用這個函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：
1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。
若不符合則有相對應的 A+(B+C) 或 (A+B)+C 的合併操作，一邊進行 run 的劃分一邊進行 merge 是 Timsort 的獨特設計。
```c
while ((n = stk_size) >= 2) {
if ((n >= 3 &&
run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
(n >= 4 && run_size(tp->prev->prev->prev) <=
run_size(tp->prev->prev) + run_size(tp->prev))) {
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
} else {
tp = merge_at(priv, cmp, tp);
}
} else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
} else {
break;
}
}
```
`merge_at`用於在指定的位置 at 合併兩個相鄰的 run。該函數首先計算兩個 run 的大小總和，然後使用 merge 執行實際的合併操作，最後將結果更新到鏈表中。
`merge` 函数的目的是將兩個已排序的 run 合併成一个更大的有序 run。`AAAA` 是指向指標的指標，最初指向合併結果的 `head` 指標，因此`AAAA = &head`。當比較 `a` 和 `b` 的首元素大小時，如果 `a` 的首元素小於等於 `b` 的首元素，則將 `*tail` 設置為 `a`，並更新 `tail` 為 `&a->next`，即指向 `a` 的下一個節點的指針。這樣做是為了追蹤 run 的尾部。
`a` 的首元素小於等於 `b` 的首元素時，`BBBB = &a->next`，以追蹤 run a 的尾部。`a` 的首元素大於 `b` 的首元素時，`CCCC = &b->next`，以追蹤 run b 的尾部。
```c
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
{
struct list_head *head;
struct list_head **tail = AAAA;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = CCCC;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
之後會進到 `tp = merge_force_clollapse(priv, cmp, tp);`這段程式碼的主要用意是要把剩餘的 run 合併到一起，會強制合併成 1 個或 2 個 run，其基本也是呼叫 `merge_at`做合併，只是條件不同罷了。
往下看程式碼，主要的功能就是在重建 `prev` links，但當 `stk_size` 若是只有一個的話，那他就可以跳過最後的`merge_final`，直接使用`build_prev_link`，所以`FFFF = 1`。`build_prev_link`的功用在於建立一個雙向鏈結串列，首先將傳入的 tail 的 next 指標連接到 list，建立鏈表的初始連結，之後透過迴圈遍歷整個列表，對每個節點進行處理。而最後的兩行設定了循環列表的頭尾相連。因此`DDDD = tail->next`，`EEEE = head->prev`。簡單來說就是將 `list`連接到`tail`，因為若`stk_size <= 1`那就不會有剩餘的狀況，因此將`stk0`連到`head`中。
```c
/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);
/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= FFFF) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
```
```c
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
DDDD = head;
EEEE = tail;
}
```
最後來解析`merge_final`的目的是將兩個已排序的雙向鏈表合併成一個更大的已排序雙向鏈表（head），基本上跟`merge`大同小異，差異就是最後的一段`build_prev_link`，可以透過這個函式將後面剩餘的串列直接加到`tail`後面。
```c
/* Finish linking remainder of list b on to tail */
build_prev_link(head, tail, b);
```
## 第二週題目
### [測驗一](https://hackmd.io/@sysprog/linux2024-quiz2)
#### Binary Tree
Binary Tree 是一種樹狀結構，其中每個節點最多有兩個子節點，分別稱為左子樹和右子樹。
preorder：
首先訪問根節點，然後遍歷左子樹，最後遍歷右子樹。在遍歷過程中，節點的訪問順序是「root-left-right」。
inorder：
首先遍歷左子樹，然後訪問根節點，最後遍歷右子樹。在遍歷過程中，節點的訪問順序是「left-root-right」。
因此我們就可以利用 preorder 和 inorder 跟在不同的位置，得知目前左子樹和右子樹的範圍，只要走訪完整兩個 order，便可以完整建構一個 binary tree。在這個測驗主要是透過 dfs 深度優先搜索來建立。
#### 資料型態
在這個程式中的結構體主要是利用單向鏈結串列實現，可以看到下圖的圖示說明。
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first;
};
struct TreeNode {
int val;
struct TreeNode *left, *right;
};
struct order_node {
struct hlist_node node;
int val;
int idx;
};
```
```graphviz
digraph hlist_add_head {
rankdir = LR;
node [shape = record];
labelloc=top;
head0 [label = "hlist_head | <f> first"];
node15 [label = "<h> hlist_node | {<p> pprev | <x> next}"];
value15 [label = "value"];
index15 [label = "idx"];
subgraph cluster_15 {
label = "order_node ";
node15;
value15;
index15;
};
node20 [label = "<h> hlist_node | {<p> pprev | <x> next}"];
value20 [label = "value"];
index20 [label = "idx"];
subgraph cluster_20 {
label = "order_node ";
node20;
value20;
index20;
};
node [shape = none];
null0 [shape = none, label = "NULL"];
head0:f -> node15:h;
node15:p -> head0;
node15:x -> node20:h;
node20:p -> node15:x;
node20:x -> null0;
}
```
除了上面的基本結構外，此測驗也加入了 Hash Table 的概念，基本上就是就是將 `hlist_head`結構體變成 array，以空間換取時間，圖示說明如下:
```graphviz
digraph G {
rankdir=LR;
label = "Hash Table";
labelloc=top;
// size="10"
node [shape = rect, width=1, height=0.5];
S0 [label = "hlist_head[0]"];
S1 [label = "hlist_head[1]"];
S2 [label = "hlist_head[...]"];
S3 [label = "hlist_head[n]"];
node [shape = none];
}
```
#### binary tree 實作
首先先看到 `hlist_add_head`，這段程式碼的功用在於加入節點到串列的第一位，因此首先檢查 `h->first`是否存在，若不存在需要手動初始化，由於我們要把節點 n 加入到第一個，因此我們要將`n->next`指向原本串列的第一個，所以`AAAA = h->first`，再來將`n->pprev`指向原本的`&h->first`，最後將 n 放到 `h->first`。
```c
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
n->next = AAAA;
n->pprev = &h->first;
h->first = n;
}
```
`node_add`的功能是將節點加入 Hash Table 中對應值的鏈結串列的頭部，`hlist_head_add`可以理解為將節點加入串列頭部的基本操作，而`node_add`則需要先透過 Hash Table 找到想要操作的串列，因此 `DDDD = &heads[hash]`
```c
static inline void node_add(int val,
int idx,
int size,
struct hlist_head *heads)
{
struct order_node *on = malloc(sizeof(*on));
on->val = val;
on->idx = idx;
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, DDDD);
}
```
`find`主要用來在 Hash Table 查找特定數字的函式。首先計算 Hash Value，決定我們要在哪一個串列做搜索。接著透過 hlist_for_each 遍歷欲搜索的鏈結串列，`BBBB = &head[hash]`。為了由`struct hlist_node *p`這個型態映射到`order_node`，可以使用`container_of`達到目的，也可以使用`list_entry`，因此`CCCC = container_of`。這裡值得注意的是，不同於以往的遍歷鏈結串列搜索 O(n)，透過 Hash Table 的方式進行搜尋可以將搜索時間減少到常數時間 O(1)。
```c
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);
if (num == on->val)
return on->idx;
}
return -1;
}
```
接下來看到最主要建構 binary tree 的函式 `dfs`，使用遞迴的方式來操作，傳入的參數有:
* `int *preorder` 為 preorder list 的第一個位址。
* `int pre_low` 指該次遞迴的 preorder 下限。
* `int pre_high` 指該次遞迴的 preorder 上限。
* `int *inorder` 為 inorder list的第一個位址。
* `int in_low` 指該次遞迴的 inorder 下限。
* `int in_high` 指該次遞迴的 inorder 上限。
* `stuct hlist_head *in_heads` Hash Table 結構體的位址。
* `int size` Hash Table 的欄位總數
在函式的一開始先決定了中止條件，若上限小於下限則會 `return NULL`。
```c
if (in_low > in_high || pre_low > pre_high)
return NULL;
```
現在開始建構 binary tree，以範例為例，preorder 為 `[3, 9, 20, 15, 7]`，inorder 為 `[9, 3, 15, 20, 7]`。首先配置記憶體給要加入的節點，並把 `preorder[pre_low]` 加入 `tn->val`，初始的 `pre_low`為 0，因為 preorder 的順序為 中-左-右，因此第一個元素一定代表了 root，所以我們可以透過`find(preorder[pre_low], size, in_heads)
`到 inorder list 查找 root 的位置，如此一來在這一遞迴就可以劃清左子樹以及右子數。
```c
struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);
```
然後就可以進到下一次左子樹的遞迴，`tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);`，說明一下裡面的參數，preorder 的下限會加一，搜尋範圍則會透過`idx - in_low`決定，意義就是透過 inorder 的 root 位置和 inorder 下限所形成的範圍，也就是說上一次遞迴左子樹的部分，inorder 則會透過原先的下限 `in_low` 和上一次遞迴的 root 位置 -1 所決定。當左子樹找完就可以找右子樹。上下限的表示如下圖所示，只要根據目前的位置以及範圍就可以準確圈出上下限。
```c
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
return tn;
```
```graphviz
digraph example {
label = "Preorder";
labelloc=top;
subgraph cluster_idx {
label=<idx>;
3;
}
subgraph cluster_left {
label=<idx - in_low>;
9;
}
subgraph cluster_right {
label=<in_high - idx - 1>;
15;
20;
7;
{rank=same; 15; 20; 7}
}
20->15->7[color=transparent];
}
```
```graphviz
digraph example {
label = "Inorder";
labelloc=top;
subgraph cluster_left {
label=<idx - in_low>;
9;
}
subgraph cluster_idx {
label=<idx>;
3;
}
subgraph cluster_right {
label=<in_high - idx - 1>;
15;
20;
7;
{rank=same; 15; 20; 7}
}
15->20->7[color=transparent];
}
```
最後建構 binary tree 的函式，先定義以及初始化 preorder list 和 inorder list，然後再進行 `dfs`。
```c
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
in_heads, inorderSize);
}
```
### [測驗二](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-2)
#### LRU Cache
LRU（Least Recently Used） Cache 是一種實作 Cache 的策略，由於 Cache 的容量並不是無限大，因此需要針對元素的使用模式來決定哪些元素應該被保留或丟棄。
簡單來說，LRU Cache 的原則是保持最近使用的元素，淘汰最久未使用的元素。實作方法就是將使用過元素記錄到串列中，如此一來便可實現淘汰最久未使用的元素。通常使用雙向鏈結串列和雜湊表 Hash Table 的結合，在這邊 Hash Table 使用單向鏈結串列實作。雙向鏈結串列用於維護元素的使用順序，而哈希表則用於實現快速的查找和刪除操作，因此可以看到兩種不同的串列型態。
#### 單向鏈結串列 for Hash Table
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
不同於雙向鏈結串列的，`**pprev` 是一個指標的指標的方式呈現，通常用於在修改鏈表結構時更新前一個節點的next指標。這樣設計的目的是為了能夠在操作中修改前一個節點的next指標，而不需要返回上一個節點，若一樣寫成 `*prev` 的話，那他在 function 就會變成透過 pass by value 傳遞，造成效率不彰。
下方的 function `hlist_add_head` 可以看到如果 list 裡面沒有東西的話，則更新 head 的 pprev pointer，將新節點的 next 指標指向原串列的第一個節點，並將新節點的 pprev 指標指向鏈表的頭部指標的地址，最後更新串列的 head pointer，使其指向新的節點 n。
```c
void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
n->next = h->first;
n->pprev = &h->first;
h->first = n;
}
```
接下來看到 hlist_del function，一開始先從節點 n 中取得下一個節點 `next` 以及前一個節點的 `next` 指標的地址 `pprev`，之後更新前一個節點的 `next` 指標，將其指向下一個節點，就是跳過節點 `n`的意思，最後如果下一個節點存在，需要把下一個節點的 `pprev` 指標指向前一個節點的 next 指標的地址。因此`EEEE = next->pprev`。
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
}
```
#### LRU 實作
雙向串列的部分基本與 lab0-c 一樣，在這邊就不多加討論。
直接看到結構體的部分，定義了兩個結構體，分別是 `LRUCache` 和 `LRUNode`。
`LRUCache` 裡包括了 `capacity` 表示 LRUCache 的最大容量，`count` 則表示當前已儲存的 key-value pair 數量。`dhead` 用來記錄 key-value pair 的使用順序，這個雙向串列的節點就是 `LRUNode` 的 `link` 成員。`hhead[]`是一個 Hash Table 的 hlist_head array，可以加速查找 value。而每個 hhead 大小皆為 capacity。
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
`LRUNode` 裡面包括了 `key` 和 `value`，主要會透過他們去做映射，`node` 是用於 Hash Table 的節點，`link` 則是用來記錄 LRU 順序的節點。
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
了解基本結構體後就可以來看函式操作了，有四個函式分別是 `lRUCacheCreate` `lRUCacheFree` `lRUCacheGet` `lRUCachePut`，比較特別的操作是 `lRUCacheGet` 和 `lRUCachePut`。`lRUCacheGet`的功用是透過傳遞 key 取值，需要判斷 key-value 有沒有在 cache 裡面，有的話 return value ，沒有的話 return -1。`lRUCachePut`則是要放進去，如果有這對 key-value pair 的話，那麼直接更新 value 即可，如果沒有的話則要從記憶體存取並更新。
`lRUCacheCreate`首先會根據`LRUCache`結構體去分配記憶體，使用`INIT_HLSIT_HEAD`來初始化`LRUCache`的 head array `hhead`。
```c
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
capacity * sizeof(struct list_head));
cache->capacity = capacity;
cache->count = 0;
INIT_LIST_HEAD(&cache->dhead);
for (int i = 0; i < capacity; i++)
INIT_HLIST_HEAD(&cache->hhead[i]);
return cache;
}
```
利用`list_for_each_safe`走訪已使用過的`&obj->dhead`雙向鏈結，可以透過 n (下一個節點)來安全的刪除節點，因此 `list_del(GGGG)` 裡面應為 `n->prev` 確保不會因為刪除了當前節點而造成斷裂。由於 `pos` 的資料型態為 `list_head`，因此在 LRUNode 中`pos`屬於`link`成員，`list_entry(pos, LRUNode, FFFF)`應該填入`link`。
```c
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, FFFF);
list_del(GGGG);
free(cache);
}
free(obj);
}
```
接下來來到了最關鍵的兩個 function，先來分析`lRUCacheGet`，這個函式是用來讀值，首先先計算 key 的 Hash value，接下來使用 `hlist_for_each` 走訪 `obj->hhead[hash]` Hash Table 中的 key-value pair。使用`list_entry(pos, LRUNode, HHHH)`來獲取 pos 在 LRUNode 的結構，跟上一個函式大同小異，可以透過觀察 `pos` 資料型態來判斷`HHHH = node`。若傳入的 key 與 cache->key 相同的話則將此節點移到`obj->dhead`，用來記錄使用的順序，因此`IIII = &cache->link`，若已走訪整條串列還沒有找到相同的 key 值，則 `return -1`。
```c
int lRUCacheGet(LRUCache *obj, int key)
{
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *cache = list_entry(pos, LRUNode, HHHH);
if (cache->key == key) {
list_move(IIII, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
`lRUCachePut`的功能為更新和寫 cache，一開始同樣要計算 Hash value，一樣透過 `hlist_for_each` 走訪 `obj->hhead[has]`，同樣的邏輯`JJJJ = node`，如果 `c->key` 和傳入的 `key`匹配到的話，則同樣的將此節點加入`obj->dhead`紀錄使用順序，所以`KKKK = &c->link`，到這為止基本上與`lRUCacheGet`差不多，然而如果`key`不匹配的話，我們則要另外做處理。
此時會有兩種狀況，第一種是 cache 還有尚未使用的空間，這邊是使用`count`和`capacity`互相比較，若`count < capacity`，就可以直接將傳入的 `key` `value` 新增至串列中，所以我們需要先分配一個節點，把`key` `value` 加入，並將他記錄到 `obj->dhead`中。
第二種狀況則是 cache 已滿，那這時候我們就要考慮要刪除誰了，Least Recently Used 的節點就變成我們需要刪除的對象，如此才有空間把新的加進來，因此可以透過`cache = list_last_entry(&obj->dhead, LRUNode, link);`將最少用到的節點抓出來，然後把它移到 dhead 的最前面，代表最近被使用過了，然後從 Hash 串列刪除，然後再將新的節點加入 hhead 中。如此一來則可以完成 LRU Cache 的實作。
```c
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *cache = NULL;
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *c = list_entry(pos, LRUNode, JJJJ);
if (c->key == key) {
list_move(KKKK, &obj->dhead);
cache = c;
}
}
if (!cache) {
if (obj->count == obj->capacity) {
cache = list_last_entry(&obj->dhead, LRUNode, link);
list_move(&cache->link, &obj->dhead);
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
} else {
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
}
cache->key = key;
}
cache->value = value;
}
```
### [測驗三](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)
考慮 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元。
#### fns
首先先來看到`fns`，要如何在一個 unsigned long 的長度的 `word` 找到第 N 個設定的位元。傳遞的參數有兩個:
* word: The word to search
* n: Bit to find
首先當然是先檢查這個 word 是不是有效的，再來我們可以透過`__ffs`來去尋找第一個被設定的位元，然後我們再透過一個 `n--`的機制就可以找到第 N 個被設定的位置。值得注意的是我們在找到每一個 1 後，需要用`__clear_bit`將找到的 bit 清除掉，否則他永遠會找到第一個 bit。
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
接下來看到 `__ffs`，這邊就是在尋找一個 word 的第一個被設定的位元，從最低位開始找會有幾個 0。會先從最低的 32 位開始檢查，若成立 num += 32，word 會右移 32 位，再檢查最低的 16 位，一直檢查到 1 位。檢查的方式是透過與 2 的冪位全 1 做且運算，因此 `AAAA = 0xffffffff`。
```c
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
if ((word & AAAA) == 0) {
num += 32;
word >>= 32;
}
#endif
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
if ((word & 0x1) == 0)
num += 1;
return num;
}
```
`__clear_bit`的共用是將第 `nr` 位的 bit 設為 0。使用到了兩個巨集`BIT_MASK`和`BIT_WORD`，`BIT_WORD`的用意在於獲取 `nr / BITS_PER_LONG`的商數，若`nr`大於`BITS_PER_LONG`的話，我們就需要使用獲取的商數對`addr`做偏移，才能取到我們想要的地方。
```c
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= BBBB;
}
```
舉例來說，我們要操作的函式為 `__clear_bit(66, addr)`，所以我們要處理的數字應該是`010...100000...000`，65 個 0。
```graphviz
digraph G {
rankdir=TB;
// size="10"
node [shape = square, width=1, height=1];
S1 [label = "000...000"];
S2 [label = "010...100"];
node [shape = none];
P1 [label = "*addr"];
P2 [label = "*addr+1, *p"];
P1 -> S1
P2 -> S2;
}
```
```graphviz
digraph G {
label = "mask";
labelloc=top;
rankdir=LR;
node [shape = square];
node [shape = record];
in [label = "{0 | 0 |0 | ... | 1 | 0 | 0 }", width=5];
node [shape = none];
}
```
所以`p`會存取到下方這張圖的值。
```graphviz
digraph G {
label = "*p";
labelloc=top;
rankdir=LR;
node [shape = square];
node [shape = record];
in [label = "{0 | 1 |0 | ...|1 |0| 0}", width=5];
node [shape = none];
}
```
就可以與 `~mask`做且運算，如此一來可以精準的清除掉第 66 個位元的 1 而不會動到其他位元的值，因此`BBBB = ~mask`。
```graphviz
digraph G {
label = "*p &= ~mask";
labelloc=top;
rankdir=LR;
node [shape = square];
node [shape = record];
in [label = "{0 | 1 |0 | ...|0 |0| 0}", width=5];
node [shape = none];
}
```
#### find_nth_bit
對比 `fns` 只是在一個 word 內尋找，接下來我們要將範圍擴增到 memory region。說明一下傳遞的參數:
* addr: The address to start the search at
* size: The maximum number of bits to search
* n: The number of set bit, which position is needed, counting from 0
首先若要找的 `n` 大於 `size`則會直接 `return size`。然後會根據`small_const_nbits(size)`來區分成兩種情況，簡單來說`small_const_nbits`其實就是在判斷 `size`是不是小於`BITS_PER_LONG`，如果 `size`小於`BITS_PER_LONG`的話會進到 if statement 裡面，首先我們會使用 `*addr & GENMASK(size - 1, 0)`讓`val`只在第 0 bit到第`size`bit的位元數為原本的值，範圍外的皆為 0。然後就可以使用`fns`去尋找。
```c
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
{
if (n >= size)
return size;
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
}
return FIND_NTH_BIT(addr[idx], size, n);
}
```
但若是`size`大於`BITS_PER_LONG`則會使用另外一個巨集`FIND_NTH_BIT`處理，裡面使用一個 for loop 處理，一次處理一個 unsigned long 的長度，也可以分做幾種情況:
`if (idx * BITS_PER_LONG + nr >= sz) ` 代表我們要找的目標已經超出 size，所以會跑到 out 的地方，return sz。
`if (w > nr)` 其中`w = hweight_long(tmp)`代表我們再`tmp`總共觀察到了幾個 1，`tmp = addr[idx]`，因此可以理解為如果觀察到的 1 的數量大於我們要找的 `nr`的話，代表我們的目標一定在這個區段內，因此可以直接跳到 `found`，然後利用 `fns`再加上已經偏移的地址就可以得到 sz。如果`w < nr` 代表目標不再這個區段，因此`nr -= w`。
這一段在說的是如果我們的 `sz` 不能夠被 `BITS_PER_LONG` 整除的話，代表最後會有剩餘的 bits，因此我們需要將他擴充為 64 bits，所以`CCCC = %`。
```c
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);
```
```c
#define FIND_NTH_BIT(FETCH, size, num) \
({ \
unsigned long sz = (size), nr = (num), idx, w, tmp; \
\
for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
if (idx * BITS_PER_LONG + nr >= sz) \
goto out; \
\
tmp = (FETCH); \
w = hweight_long(tmp); \
if (w > nr) \
goto found; \
\
nr -= w; \
} \
\
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
Sign in with Wallet
Connect another wallet