# 2024q1 Homework2 (quiz1+2)
contributed by <[`bclegend`](https://github.com/bclegend)>
## [第一週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
[程式碼](https://github.com/bclegend/2024q1hw2/tree/main/qsort)
#### 運作原理
實做 quick sort 演算法,並以以下 `node_t` 為 linked list 的基礎架構,排序 linked list 中數值的序列。
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
* 原始 linked list
由下圖所示,在開始時將陣列的最左方的元素紀錄為 `pivot`
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
begin
node[shape=box];
struct0 [label= "4"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "1"];
struct5 [label= "7"];
struct6 [label= "9"];
struct7 [label= "8"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
struct5 -> struct6
struct6 -> struct7
}
pivot -> struct0
L -> struct0
R -> struct7
}
```
* 首先,移動指標 `R` 往 linked list 左方移動,若 `R` 指向的位置儲存的數值小於 `pivot` ,將指標 `R`指向位置的數值與指標 `L` 指向位置的數值交換
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
node[shape=box];
structp [label="4"]
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
struct5 [label= "7"];
struct6 [label= "9"];
struct7 [label= "8"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
struct5 -> struct6
struct6 -> struct7
}
pivot -> structp
L -> struct0
R -> struct4
}
```
* 再來移動指標 `L` 的位置往右方移動,若 `L` 指向的位置儲存的數值大於 `pivot` ,將指標 `L`指向位置的數值與指標 `R` 指向位置的數值交換
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
node[shape=box];
structp [label="4"]
struct0 [label= "1"];
struct1 [label= "4"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "5"];
struct5 [label= "7"];
struct6 [label= "9"];
struct7 [label= "8"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
struct5 -> struct6
struct6 -> struct7
}
pivot -> structp
L -> struct1
R -> struct4
}
```
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
node[shape=box];
structp [label="4"]
struct0 [label= "1"];
struct1 [label= "2"];
struct2 [label= "3"];
struct3 [label= "4"];
struct4 [label= "5"];
struct5 [label= "7"];
struct6 [label= "9"];
struct7 [label= "8"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
struct5 -> struct6
struct6 -> struct7
}
pivot -> structp
L -> struct1
R -> struct3
}
```
* 重複以上動作直到 `L` 與 `R` 指向同一個位置
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
linkedlist_0 [fontcolor = "black"]
linkedlist_3 [fontcolor = "black"]
linkedlist_7 [fontcolor = "black"]
node[shape=box];
structp [label="4"]
struct0 [label= "1"];
struct1 [label= "2"];
struct2 [label= "3"];
struct3 [label= "4",fontcolor = "red"];
struct4 [label= "5"];
struct5 [label= "7"];
struct6 [label= "9"];
struct7 [label= "8"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
struct5 -> struct6
struct6 -> struct7
}
pivot -> structp
L -> struct3
R -> struct3
linkedlist_0 -> struct0
linkedlist_3 -> struct3
linkedlist_7 -> struct7
}
```
此時 linkedlist[0] 到 linkedlist[2] 為新的 linked list 1 ,linkedlist[3]為新的 linked list 2 , linkedlist[4] 到 linkedlist[7] 為新的 linked list 3
並將這三個新的 linked list 再繼續排列直到整個 linked list 排列完成
而在我們的實做中，我們利用 `struct __node *left, *right;` 進行堆疊,堆疊出左方的 linked list `left` 以及右方的 linked list `right`
這次的實做中，我們使用的是改變 `node` 中數值的方式
#### 改進
1. 是否需要在配置 linked list `node_t *begin[max_level], *end[max_level];` 時給 `max_level` 這麼多的空間？
#### 使用 Linux 核心風格的 List API 改寫上述程式碼
### 測驗二
## [第二週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
[Leetcode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
在二元樹的構建過程中，我們可以利用不同的排序方式來唯一確定一顆樹的結構。其中，`preorder` 採用的是"中->左->右"的順序，`inorder` 採用的是"左->中->右"的順序。如果我們知道這兩種排序方式，就足以建構出唯一的二元樹。
程式的實作方式是利用 Linux 核心的 hash table。在這個實作中，我們首先以preorder的順序找到根節點的值，接著在inorder中找到對應的左子樹和右子樹元素。然後，我們將左右子樹當作新的根節點，再次進行相同的過程，直到找不到對應的元素為止。
```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);
}
```
在 linux kernel 中 [`include/linux/types.h`](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 定義 `hlist_node` 以及 `hlist_head` 結構如下
```c
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
* `hlist_add_head`
在 hash table 中的 `head` 後新增節點
```diff
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->next = h->first;
n->pprev = &h->first;
h->first = n;
}
```
* `find`
```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;
}
```
* `node_add`
在 hash table 中新增節點
```diff
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);
+ hlist_add_head(&on->node, &heads[hash]);
}
```
### 測驗二
[Leetcode](https://leetcode.com/problems/lru-cache/description/)
### 測驗三
Sign in with Wallet
Connect another wallet