# 2024q1 Homework2 (quiz1+2)
contributed by <[marvin0102](https://github.com/marvin0102/lab0-c)>
# 第一周測驗
## 測驗 1:
### 結構體 `node_t`:
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph "__node"
{
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "node_t";
node1 [label="<head>value|next|{<left> left |<right> right}"];
}
}
```
此結構體作為陣列的單一節點 :
`*left` 、 `*right`的作用是當作為 pivot 時，分別記錄與比較比 pivot 大或小的節點。
`*next` 則是作為 linked list 的指標，指向下一個元素。
`value` 為該節點的值。
### 操作函式:
我們可以只用以下這些 API 來操作與建構陣列。
- `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)`
### 解題思路:
以知原始程式為非遞迴快速排序( quick sort )的實作。
```c
while (count--)
list = list_construct(list, test_arr[count]);
```
從函式`list_construct()`以及 main function 建構初始陣列的程式碼可知，此陣列為單向鏈接串列(linked list)。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
"*head";
subgraph cluster_a
{
label = "node_1";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_b
{
label = "node_2";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_c
{
label = "node_3";
node3 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
"*head"->node1:value [lhead=cluster_a];
node1:"*next"->node2:"*next" [lhead=cluster_b];
node2:"*next"->node3:"*next" [lhead=cluster_c];
}
```
---
函式`quick_sort()` 中的參數`list`為指標的指標，其指向的位置為指向串列第一個節點的指標 head 之地址。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
"**list"[fontcolor=red ,color=red];
"*head";
subgraph cluster_a
{
label = "node_1";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_b
{
label = "node_2";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_c
{
label = "node_3";
node3 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
"**list"->"*head" [color=red];
"*head"->node1:value [lhead=cluster_a];
node1:"*next"->node2:"*next" [lhead=cluster_b];
node2:"*next"->node3:"*next" [lhead=cluster_c];
}
```
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
函式`list_length()`回傳的是一串列的長度，因此需要逐一走訪整個串列聘記錄其節點的個數，而`node_t **left`為指標的指標，因此，每一次迴圈，需要將`left`的值更新為指向下一個節點的指標之地址，也就是指標`next`的地址。
```diff
- left = &(BBBB);
+ left = &((*left)->next);
```
loop 0
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
"**left"[fontcolor=red ,color=red];
"*head";
subgraph cluster_a
{
label = "node_1";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_b
{
label = "node_2";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_c
{
label = "node_3";
node3 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
"**left"->"*head" [color=red];
"*head"->node1:value [lhead=cluster_a];
node1:"*next"->node2:"*next" [lhead=cluster_b];
node2:"*next"->node3:"*next" [lhead=cluster_c];
}
```
loop 1
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
"**left"[fontcolor=red ,color=red];
"*head";
subgraph cluster_a
{
label = "node_1";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_b
{
label = "node_2";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_c
{
label = "node_3";
node3 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
"**left"->node1:"*next" [color=red];
"*head"->node1:value [lhead=cluster_a];
node1:"*next"->node2:"*next" [lhead=cluster_b];
node2:"*next"->node3:"*next" [lhead=cluster_c];
}
```
loop 2
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
"**left"[fontcolor=red ,color=red];
"*head";
subgraph cluster_a
{
label = "node_1";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_b
{
label = "node_2";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_c
{
label = "node_3";
node3 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
"**left"->node2:"*next" [color=red];
"*head"->node1:value [lhead=cluster_a];
node1:"*next"->node2:"*next" [lhead=cluster_b];
node2:"*next"->node3:"*next" [lhead=cluster_c];
}
```
---
快速排序法在排序過程中，會將尚未排序好的子序列做排序，以子序列的第一個節點作為 pivot 、 L 會從左邊開始掃，紀錄有多少值小於 pivot，R 從右邊開始，紀錄有多少值大於 pivot。
而第一次排序，L 必為串列的第一個節點，R 為串列的最後一個節點。
```c
begin[0] = *list;
end[0] = list_tail(list);
```
因此，`end[0]`為串列的最後一個節點，而函式`list_tail()`的作用即為回傳一串列最後一個節點的指標。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
與函式`list_length()`相同，函式`list_tail()`需要逐一走訪串列中的所有節點才能夠得到最後一個節點的地址。
```diff
-left = &(AAAA);
+left = &((*left)->next);
```
---
快速排序法在完成一次排序後，會形成三個子串列，分別為，比 pivot 小的序列、 pivot 、比 pivot 大的序列，下一次排序則會對比 pivot 小的序列與比 pivot 大的序列做排序。
排序前
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "4", group = g1];
n2[label = "1", group = g1];
n3[label = "3", group = g1];
n4[label = "5", group = g1];
n5[label = "2", group = g1];
n6[label = "7", group = g1];
n1->n2;
n2->n3;
n3->n4;
n4->n5;
n5->n6;
pivot[fontcolor=red,color=red];
pivot->n1;
head->n1;
L[fontcolor=green,color=green];
R[fontcolor=green,color=green];
L->n4;
R->n5;
}
```
排序後
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "4", group = g1];
n2[label = "1", group = g1];
n3[label = "3", group = g1];
n4[label = "5", group = g1];
n5[label = "2", group = g1];
n6[label = "7", group = g1];
n5->n2;
n2->n3;
n3->n1;
n1->n4;
n4->n6;
pivot[fontcolor=red,color=red];
pivot->n1;
head->n5;
L[fontcolor=green,color=green];
R[fontcolor=green,color=green];
L->n4;
R->n5;
}
```
從結果可以看到，排序後 L 與 R 會指向子序列的第一個節點，即成為子序列的起始指標。
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
而實作程式碼則運用這個結果，先建立兩個空字串`left`、`right`，並且將比 pivot 小的節點加至`left`，比 pivot 大的節點加入`right`中，最後的結果會與快速排序法一致。
由此可以知道，此迴圈須逐一走訪串列並且與 pivot 比大小。
```diff
-p = CCCC;
+p = p->next;
```
- `void list_add(node_t **list, node_t *node_t)`:
`list_add` 的功能是將額外的節點插置陣列的開頭。
其運作的方式為，將新節點指向陣列的第一個節點，並且將指向陣列頭部指標的 `list` 更新為指向新節點。
```c
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;
*list = node_t;
}
```
```graphviz
digraph add
{
node [shape="record"];
rankdir = "LR"
list;
subgraph cluster_b
{
label = "node_t";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_a
{
label = "head of list";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
list->node1:head;
node2:"*next"->node1:"*next";
}
```
```graphviz
digraph add
{
node [shape="record"];
rankdir = "LR"
list;
subgraph cluster_b
{
label = "node_t";
node2 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_a
{
label = "head of list";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
list->node2:head;
node2:"*next"->node1:"*next";
}
```
---
由於使用非遞迴的方式做快速排序，因此需要紀錄每個子序列的起始節點與結束節點，並用迴圈代替遞迴。
```c
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
```
此段程式碼即為紀錄每個子序列的起始與結束節點，因此
```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);
```
### 改進方案
以遞迴實作中，遞迴的最底層，即每個以序列只用一個元素，因此`begin[]`與`end[]`的記憶體分配至多只需要 `n`個空間。
此外，每個子序列的`end[i]`可由`list_tail(begin[i])`取得，因此不需要使用額外的儲存空間。
```diff
- int max_level = 2 * n;
+ int max_level = n;
- node_t *begin[max_level], *end[max_level];
+ node_t *begin[max_level];
```
```diff
while (i >= 0) {
- node_t *L = begin[i], *R = end[i];
+ node_t *L = begin[i], *R = list_tail(begin[i]);
if (L != R) {
...
```
```diff
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);
```
### 以 linux List API 改寫
```c
void quick_sort(struct list_head **list)
{
struct list_head *head = (*list);
int n = list_length(head);
int value;
int i = 0;
int max_level = 2*n;
struct list_head *begin[max_level];
struct list_head *result = new_head(), *left = new_head(), *right = new_head();
begin[0] = head;
for(int j=1 ; j<max_level ; j++){
begin[j] = new_head();
}
while (i >= 0) {
struct list_head *L = begin[i]->next, *R = begin[i]->prev;
if (L != R) {
struct list_head *pivot = begin[i]->next;
value = list_entry(pivot, node_t, list)->value;
list_del(pivot);
node_t *entry, *safe;
list_for_each_entry_safe (entry, safe, begin[i],list) {
list_move(&(entry->list),entry->value > value ? right : left);
}
list_splice_init(left, begin[i]);
list_add(pivot,begin[i + 1]);
list_splice_init(right, begin[i+2]);
i += 2;
} else {
if (list_is_singular(begin[i]))
list_splice_init(begin[i],result);
i--;
}
}
*list = result;
for(int j=1 ; j<max_level ; j++){
free(begin[j]);
}
free(right);
free(left);
}
```
程式細節見[commit](https://github.com/marvin0102/M02/commit/04a2572cd242bc2e4afe4d33f64e95a86fbac48c?diff=unified&w=0)
## 測驗 2:
### Timsort 程式運作原理：
Timsort 透過只合併 2 runs 中大小關係重疊的區域、將以序列中已排序的元素分在同一 run ，降低了傳統合併排序法（merge sort）的記憶體開銷與比較次數。
考慮以下序列
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "4", group = g1];
n8[label = "7", group = g1];
n9[label = "8", group = g1];
n1->n2;
n2->n3;
n3->n4;
n4->n5;
n5->n6;
n6->n7;
n7->n8;
n8->n9;
}
```
`find_run` 作用為找出序列中的下一個 run ，也就是需要合併的子序列。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", color = red, group = g1];
n2[label = "2", color = red, group = g1];
n3[label = "3", color = red, group = g1];
n4[label = "4", color = red, group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "4", group = g1];
n8[label = "7", group = g1];
n9[label = "8", group = g1];
n1->n2;
n2->n3;
n3->n4;
n4->n5[style=dashed,color=gray];
n5->n6;
n6->n7;
n7->n8;
n8->n9;
"result.head"[fontcolor=red,color=red];
"result.head"->n1;
"result.next"[fontcolor=red,color=red];
"result.next"->n5;
}
```
執行完第一次 `find_run` 後， `result.head` 會紀錄此 run ，並且將其餘的序列紀錄在 `result.next`。
指標 `tp` 負責紀錄所有待合併的 runs，作法是使用 linked list 串連所有 runs 的 `head` 指標。
`merge_collapse` 在接收 runs 的鍊接串列後，負責判斷需要合併哪些 runs ，合併串列須達成兩個條件：
- 當欲合併的 runs 超過三個時，須判斷 `tp->prev->prev` 的長度是否小於等於 `tp->prev` 、 `tp`長度之合
- `tp->prev` 的長度是否小於等於 `tp`
`merge_at` 則負責將 `tp` 、 `tp->prev` 合併，其中 `merge` 使用指標的指標將兩序列合併，好處是不需要額外的記憶體。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "4", group = g1];
n8[label = "7", group = g1];
n9[label = "8", group = g1];
n1->n2;
n2->n3;
n3->n4;
n6->n5;
n7->n8;
n8->n9;
"tp->prev->prev"[fontcolor=red,color=red];
"tp->prev->prev"->n1;
"tp->prev"[fontcolor=red,color=red];
"tp->prev"->n6;
"tp"[fontcolor=red,color=red];
"tp"->n7;
"tp"->"tp->prev";
"tp->prev"->"tp->prev->prev";
}
```
上圖為合併前 `tp`所紀錄的 runs
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "4", group = g1];
n8[label = "7", group = g1];
n9[label = "8", group = g1];
n1->n2;
n2->n3;
n3->n4;
n6->n5;
n5->n7;
n7->n8;
n8->n9;
"tp->prev"[fontcolor=red,color=red];
"tp->prev"->n1;
"tp"[fontcolor=red,color=red];
"tp"->n6;
"tp"->"tp->prev";
}
```
因為 `tp->prev->prev`<=`tp->prev`+`tp`，且`tp->prev`<`tp`，因此將`tp`、`tp->prev` 合併。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "4", group = g1];
n8[label = "7", group = g1];
n9[label = "8", group = g1];
n1->n2;
n2->n6;
n6->n3;
n3->n5;
n5->n4;
n4->n7;
n7->n8;
n8->n9;
"tp"[fontcolor=red,color=red];
"tp"->n1;
}
```
又，因為`tp->prev`<`tp` ，因此做合併
最後`merge_force_collapse`將剩餘的 runs 做合併。
### 改進實做：
此實作程式中的 `merge` 並不符合 Galloping mode 的方法敘述，而是依照linux merge的方法進行。
可以將 Galloping mode 進行實做，並比較其效率。
實驗結果：
在亂數測資的情況下，原始 merge 的比較次數為：
```c
==== Testing timesort ====
Comparisons: 9356
List is sorted
```
Galloping mode 的比較次數為：
```c
==== Testing timesort ====
Comparisons: 16855
List is sorted
```
在一般亂數的情況下， Galloping mode 的比較次數有明顯提昇。
---
# 第二周測驗
## 測驗 1
### 透過前序與中序建構樹程式運作原理
實作程式碼會使用到 hash table
[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
在 linux 核心的 hash table 實作中，節點的資料結構被定義為：
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
而 table 是由資料結構 `hlist_head` 型別的陣列所構成：
```c
struct hlist_head {
struct hlist_node *first;
};
```
:::info
其連接示意圖如下：
:::
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
---
在建構樹的時候，需要取得前序、中序、後序中的其中兩個，否則無法確定父節點與子節點的關係。
程式一開始需要建立一個空的 hash table ，並且使用`INIT_HLIST_HEAD()` 將 table 初始化。
`node_add()` 負責把樹的節點依照 inorder 順序插至 hash table 中
:::info
以 preorder: [3,9,20,15,7] ,inorder: [9,3,15,20,7] 為例：
:::
```graphviz
digraph G {
rankdir=LR;
node[fontsize="20" ,shape=record];
map [label="<ht0>hlist_head0.first |<ht1>hlist_head1.first |<ht2>hlist_head2.first |<ht3>hlist_head3.first |<ht4>hlist_head4.first "];
node[fontsize=""]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 9"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 15"
}
subgraph cluster_4 {
style=filled;
color=lightgrey;
node [shape=record];
hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 20"
}
subgraph cluster_5 {
style=filled;
color=lightgrey;
node [shape=record];
hn5 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 7"
}
map:ht0->hn3:hlist_node;
hn3:next->hn4:hlist_node;
hn4:pprev->hn3:next;
map:ht1->hn2:hlist_node;
map:ht2->hn5:hlist_node
map:ht4->hn1:hlist_node;
}
```
`dfs()` 使用遞迴重新建構樹，方法為：
將當前 preorder 的第一個數值作為 root ，並使用 `find()` 函式在 hash table 中找到此數值在 inorder 中的位置`idx`。
使用 `idx` 分割原前序、中序為左子樹與右子樹之前、中序，並呼叫 `dfs()`分別建構其左、右子樹。
### 改進想法：
在建構樹的過程中，hash table 中的每個節點只會只用一次，因此在節點被加數樹時，將節點從 hash table 中刪除可以有效降低每次的尋時間。
在原本的實作程式中，hash table 單純被用來查找 node index，在建構樹時仍須配置額外的記憶體，此過程明顯存在記憶體浪費，如果能將 hash table 的記憶體加以利用，移可增加記憶體的利用率。
```diff
struct order_node {
- struct hlist_node node;
- int val;
+ struct TreeNode node;
int idx;
};
```
基於這個想法，我將改變了原本 hash table 的資料結構，捨棄 `hlist_head` 、 `hlist_node` 改為使用建構樹時的資料結構 `TreeNode` 作為代替。
hash table 的建構改為與 linux linked list 相似的雙向鍊接串列進行實作。
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="TreeNode.right |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="val | {<prev>left | <next>right}"];
label="TreeNode 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="val | {<prev>left | <next>right}"];
label="TreeNode 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="val | {<prev>left | <next>right}"];
label="TreeNode 3"
}
map:ht1 -> hn1
hn1:next:s -> hn2:val
hn2:prev:s -> hn1:val
map:ht5 -> hn3
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
```diff
-static int find(int num, int size, const struct hlist_head *heads)
+static struct TreeNode* find(int num, int size, const struct TreeNode *heads)
{
- struct hlist_node *p;
+ struct TreeNode *p;
int hash = (num < 0 ? -num : num) % size;
- hlist_for_each (p, &heads[hash]) {
+ list_for_each (p, &heads[hash]) {
struct order_node *on = list_entry(p, struct order_node, node);
- if (num == on->val)
- return on->idx;
+ if (num == on->node.val){
+ list_del(p);
+ return p;
+ }
}
- return -1;
+ return NULL;
}
```
```diff
if (in_low > in_high || pre_low > pre_high)
return NULL;
- struct TreeNode *tn = malloc(sizeof(*tn));
- tn->val = preorder[pre_low];
- int idx = find(preorder[pre_low], size, in_heads);
+ struct TreeNode *tn = find(preorder[pre_low], size, in_heads);
+ int idx = list_entry(tn, struct order_node, node)->idx;
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);
```
這樣更改的優點為：
1. 將 hash table 作為 `TreeNode` 的存放陣列，當特定節點需要被用於建構樹時，可以直接從 hash table 中提取而不需要額外配置記憶體。
2. 由於樹的節點會從 hash table 中移出，可以有效提昇 hash table 的搜索效率
詳細的更改內容見[commit](https://github.com/marvin0102/M02/commit/e90d52a512b42ccd11da58e1c520d09de80b8696#)
### Linux 核心的 cgroups 相關原始程式碼
[include/linux/cgroup.h](https://elixir.bootlin.com/linux/latest/source/include/linux/cgroup.h#L239)
在 Linux 核心中定義了巨集 `css_for_each_descendant_pre` 以 pre-order 順序走訪 `*css`，其中 root 會是第一個走訪的節點。
```c
#define css_for_each_descendant_pre(pos, css) \
for ((pos) = css_next_descendant_pre(NULL, (css)); (pos); \
(pos) = css_next_descendant_pre((pos), (css)))
```
在此巨集中，會利用函式 `css_next_descendant_pre` 找尋 `pos` 節點的下一個 pre-order 節點。
```c
struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
struct cgroup_subsys_state *root)
{
struct cgroup_subsys_state *next;
cgroup_assert_mutex_or_rcu_locked();
/* if first iteration, visit @root */
if (!pos)
return root;
/* visit the first child if exists */
next = css_next_child(NULL, pos);
if (next)
return next;
/* no child, visit my or the closest ancestor's next sibling */
while (pos != root) {
next = css_next_child(pos, pos->parent);
if (next)
return next;
pos = pos->parent;
}
return NULL;
}
```
`css_next_descendant_pre` 找尋下一個節點的方法為：
- 若現在尚未走訪任何節點，則以 root 為第一個走訪的節點
- 若 `pos` 節點存在子節點，則利用 `css_next_child` 走訪第一個子節點
- 若 `pos` 節點不存在子節點，則找尋自己或是祖先的兄弟節點走訪
---
## 測驗 2
### LRU 資料結構:
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
`LRUCache` 資料結構可以當作 Cashe 本身，其中：
- capacity: Cache 的容量
- count: 目前在 Cache 內的資料個數
- dhead: 為 linux linked list ， 目的是紀錄 Cache 內各`LRUnode`的使用頻率
- hhead: 為 hash table，可以使用`key`來找尋欲寫入或讀取的`LRUnode`
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
`LRUNode`作為資料的存取單元，用於儲存放入 Cache 內的資料：
- key: hash table 的建值，用於在 hash table 中搜尋`LRUNode`
- value: 儲存於 Cache 內的數值
- node：連接於 hash table 中，用於在 hash table 中搜尋`LRUNode`
- link: 連接於 linked list 中，在寫入或讀取時，可以即時更新`LRUNode`的取用頻率
### LRU 程式運作原理:
`lRUCacheCreate()`函式的作用是創建一個容量為`capacity`的 `LRUCache` 並且初始化。
```graphviz
digraph G {
rankdir=LR;
subgraph cluster_LRU {
style=filled;
color=lightgrey;
node [shape=record];
hn5 [label="capacity |count | {<prev> *dhead | <next>*hhead}"];
label="LRUCache"
}
node[shape=record];
map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
hn5:next->map:head;
}
```
`lRUCacheFree()`則是負責釋放`LRUCache`裡所註冊的所有記憶體。
`lRUCacheGet()`取用目前已經在 cache 內的 `LRUnode`。
:::info
假設目前 cache 內已有三個 `LRUNode` 如下:
:::
```graphviz
digraph G {
graph [fontsize=12 compound=true];
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "LRUNode_key 3";
node1 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_b
{
label = "LRUNode_key 2";
node2 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_c
{
label = "LRUNode_key 1";
node3 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
"*dhead"->node1:head ;
node1:next->node2:head ;
node2:prev->node1:head ;
node2:next->node3:head ;
node3:prev->node2:head ;
rankdir=LR;
node[shape=record];
map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
"*hhead";
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
"*hhead"->map:head;
}
```
:::info
則當我們想要存取`LRUNode_key 2`的 value 時，呼叫`lRUCacheGet()`， `LRUCache`內的 linked list會被更新。
:::
```graphviz
digraph G {
graph [fontsize=12 compound=true];
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
color=red
label = "LRUNode_key 2";
node1 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_b
{
label = "LRUNode_key 3";
node2 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_c
{
label = "LRUNode_key 1";
node3 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
"*dhead"->node1:head ;
node1:next->node2:head ;
node2:prev->node1:head ;
node2:next->node3:head ;
node3:prev->node2:head ;
rankdir=LR;
node[shape=record];
map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
"*hhead";
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
"*hhead"->map:head;
}
```
:::info
`LRUNode_key 2`被移到了 list 的最前面，這表示`LRUNode_key 2`為我們最近一次使用的`LRUNode`
:::
`lRUCachePut()`更新 `LRUNode->value`的值，若 `LRUNode` 不存在且 Cache 未滿，則新增`LRUNode` ，但若 Cache 已滿，則須將被閒置最久的`LRUNode`從hash table 中移除，並且將`LRUNode->key`、`LRUNod->value`更新後再重新插入 hash table。
:::info
加入`LRUNode_key 4`
:::
```graphviz
digraph G {
graph [fontsize=12 compound=true];
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "LRUNode_key 2";
node1 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_b
{
label = "LRUNode_key 3";
node2 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_c
{
label = "LRUNode_key 1";
node3 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
subgraph cluster_d
{
color=red
label = "LRUNode_key 4";
node4 [label="<head>list_head|{<prev> *prev |<next> *next}"];
}
"*dhead"->node4:head ;
node4:next->node1 ;
// node1:prev:s->node4:head ;
node1:next->node2 ;
// node2:prev:s->node1:head ;
node2:next->node3 ;
// node3:prev:s->node2:head ;
rankdir=LR;
node[shape=record];
map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
"*hhead";
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 3"
}
subgraph cluster_4 {
style=filled;
color=lightgrey;
node [shape=record];
hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
label="LRUNode_key 4"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:prev:s -> hn1:next:s
map:ht5 -> hn4
hn4:next->hn3
hn1:prev:s -> map:ht1
hn4:prev:s -> map:ht5
hn3:prev:s -> hn4:next
"*hhead"->map:head;
}
```
### 改進方法:
將最後一次存取的 cache 在 hash table 中的位置一致最前面，這樣做的好處是可以提昇搜索 cache 時的效率。
但是，在 hash table size 為最佳時，搜尋的時間趨近於常數，此種改進方法並沒有辦法提昇搜尋效率。
程式請見[commit](https://github.com/marvin0102/M02/commit/f3c0695f82d8f8c570b4db19d89c39c79aedffb4)
### Linux 核心 lru 相關程式：
[include/linux/lru_cache.h](https://elixir.bootlin.com/linux/latest/source/include/linux/lru_cache.h#L166) 中定義了 LRU cache 的資料型別，其中包含 `lc_element`、`lc_cache`。
其中會使用到 `kmem_cache` ，`kmem_cache` 主要的作用是管理 slub 等對象。（[slub](https://en.wikipedia.org/wiki/SLUB_(software)))
而在 [lib/lru_cache.c](https://elixir.bootlin.com/linux/latest/source/lib/lru_cache.c#L40) 中，定義了 `lc_create()` 、 `lc_find()` 等新增及操作 lru cache 的函式。
---
## 測驗 3
考慮 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元 (即 1)
以下為程式的實作原理：
### 程式實作原理：
巨集`small_const_nbits(nbits)` 的作用是判斷欲查詢的記憶體是否為陣列，其中：
- `__builtin_constant_p(exp)`:
判斷 exp 在編譯時是否為常量。
:::info
[The use of the GNU compilers. 6.61](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
Built-in Function: int __builtin_constant_p (exp):
- You can use the built-in function `__builtin_constant_p` to determine if the expression exp is known to be constant at compile time and hence that GCC can perform constant-folding on expressions involving that value.
- The argument of the function is the expression to test. The expression is not evaluated, side-effects are discarded.
- The function returns the integer 1 if the argument is known to be a compile-time constant and 0 if it is not known to be a compile-time constant.
- Any expression that has side-effects makes the function return 0. A return of 0 does not indicate that the expression is not a constant, but merely that GCC cannot prove it is a constant within the constraints of the active set of optimization options.
:::
---
如果`small_const_nbits(nbits)` 通過即表示欲檢查的記憶體小於等於一個 unsigned long 大小，這時就可以在設定的範圍內尋找 Nth set bit。
巨集`GENMASK(h, l)`為限制函式的找尋範圍為從 l th 到 h th 個 bit ，低於或超出這個範圍的 bit 都會因被 mask 遮擋而設為 0。
```c
n = 0xAAAA /*0b1010 1010 1010 1010*/
val = GENMASK(15, 4) /*val = 0x0AA0 = 0b0000 1010 1010 0000*/
```
---
如果`small_const_nbits(nbits)` 未通過即表示欲檢查的記憶體大於一個 unsigned long 大小。
此時需要透過巨集 `FIND_NTH_BIT()` 先鎖定 Nth set bit 位於陣列中的第幾個元素中，再藉由 `fns()` 找出其位置。
作法是，逐一走訪陣列中的每個 unsigned long ，透過`hweight_long()`計算其中的 set bits 個數，當累積的 set bits 個數超過 N 時，即代表 Nth set bit 位於目前的 undigned long 中。
---
函式`fns(word, n)`的作用為，在`unsigned long word`中，找出 nth set bit 的位置。
方法為透過`__ffs(word)`找出目前`word`中，第一個 set bit 的位置，如果此 set bit 並非我們所需的 nth set bit ，則使用函式`__clear_bit()`設為0，並且做`n--`，當`n--==0`成立時，此時的 set bit 即為 nth set bit 。
- `__ffs()`:透過分區檢查的方式，找出 unsigned long 中的第一個 set bit 位置
```c
/* 假設 word 值 */
word = 0xABCDEF00
/*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
/* 檢查 first set bit 是否出現在前半*/
/*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
/* & */
/* 0b1111 1111 1111 1111 1111 1111 1111 1111*/
if ((word & AAAA) == 0) {
num += 32;
word >>= 32;
}
#endif
/*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
/* & */
/* 0b0000 0000 0000 0000 1111 1111 1111 1111*/
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
/*word = 0b1010 1011 1100 1101 1110 1111 0000 0000*/
/* & */
/* 0b0000 0000 0000 0000 0000 0000 1111 1111*/
/*如果 ＆ 結果為 0 ，代表檢查區域無 set bit 因此將 word
* 向右移清除此區域，並且 num 加上此區長度*/
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
/*word = 0b0000 0000 1010 1011 1100 1101 1110 1111 */
/* & */
/* 0b0000 0000 0000 0000 0000 0000 0000 1111*/
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
/*word = 0b0000 0000 1010 1011 1100 1101 1110 1111 */
/* & */
/* 0b0000 0000 0000 0000 0000 0000 0000 0011*/
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
/*word = 0b0000 0000 1010 1011 1100 1101 1110 1111 */
/* & */
/* 0b0000 0000 0000 0000 0000 0000 0000 0001*/
if ((word & 0x1) == 0)
num += 1;
return num;
}
```
- `__clear_bit(nr, addr)`:將 addr 中，第 nr 個 bit 設為 0
- `BIT_MASK(nr)`:回傳一段 bit mask ，只有第 nr 個 bit 為 1 ，用於改變第 nr 個 bit
- `BIT_WORD(nr)`:因為 addr 可能為陣列，因此需要計算 nr 位於陣列中的第幾個元素中。
最後只需要將 `p & ~mask`，就可以清除第 nr 個 bit。
### Linux 核心中 `find_nth_bit`的應用
在 [kernel/sched/core.c](https://elixir.bootlin.com/linux/latest/source/kernel/sched/core.c#L8436) 中分別定義了取得與設定 affinity 的函式，`sched_getaffinity` 、 `sched_setaffinity` 。
```c
extern long sched_setaffinity(pid_t pid, const struct cpumask *new_mask);
extern long sched_getaffinity(pid_t pid, struct cpumask *mask);
```
函式引數中的 `cpumask` 的每一個 bit 代表一個處理器，當第 n 個 bit 被設為 1 時，即代表此程式可以在第 n 個上運行，透過設定 `cpumask` 上的 bit 即可以指定程式可以在哪些固定的處理器上執行。([CPU Affinity](https://www.linuxjournal.com/article/6799))
位於 [/include/linux/cpumask.h](https://elixir.bootlin.com/linux/latest/source/include/linux/cpumask.h#L399) 的函式 `cpumask_nth()` 作用為取得 `cpumask` 當中第 n 個處理器
```c
static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpumask *srcp)
{
return find_nth_bit(cpumask_bits(srcp), small_cpumask_bits, cpumask_check(cpu));
}
```
其實作的原理即為，使用 `find_nth_bit` 找出 `cpu_mask` 中的第 n 個 bit。
提問
---
使用巨集（macro)定義寒是的好處是什麼？
因為巨集是由前製處理器（preprocessor)預處理的，本質上算是字串代換，因此使用巨集定義函式時，不需考慮傳入參數的資料型別。
但如果此函式的傳入參數型別是固定的，以 `find_nth_bit` 實作程式為例，`FIND_NTH_BIT(addr[idx], size, n)`中，`addr`、`size`、`n`的資料型別必定為`unsigned long *`、`unsigned long`、`unsigned long`，此時使用巨集定義函式就沒有了上述的優勢。且`FIND_NTH_BIT`中定義了新的變數，如果重複使用`FIND_NTH_BIT`，會造成變數重複定義的問題，引發編譯時的錯誤。
因此，在`find_nth_bit` 實作程式中，將`FIND_NTH_BIT`定義為一般函式應該會比較安全，也方便出現錯誤時追蹤程式，那麼使用巨集定義函式的優勢為何？
Sign in with Wallet
Connect another wallet