contributed by <`Shiang1212`>
## [第一週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 `1`
#### 先輩知識
結構體與函式介紹：
```C
typedef struct __node {
struct __node *left, *right; // Doubly linked list
struct __node *next;
long value;
} node_t;
```
* `void list_add(node_t **list, node_t *node_t)`
將 `node_t` 加入至 `list` 的前端。
* `node_t *list_tail(node_t \*\*left)`
回傳一個指向 left 最末節點的指標。
* `int list_length(node_t \*\*left)`
回傳輸入串列的長度。
* `node_t *list_construct(node_t *list, int n)`
建立一個 `value` 為 `n` 的節點，並將其 `next` 指向 `list`。
* `void list_free(node_t \*\*list)`
走訪每個節點，並將釋放其記憶體，直到 `list` 內沒有結點。
* `void shuffle(int *array, size_t n)`
隨機交換 `array` 裡的值，完成亂序。
其中，`shuffle` 的程式碼如下：
```C=
void shuffle(int *array, size_t n)
{
if (n <= 0)
return;
for (size_t i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
```
第 6、7 行可見，宣告一個 `size_t i` 走訪每個元素，並用第 `i` 個元素跟第 `i ~ n` 個元素交換，完成亂序操作。
介紹完基本操作，接下來介紹 `main` 函式在做什麼：
```c
int main(int argc, char **argv)
{
node_t *list = NULL;
size_t count = 100000;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);
while (count--)
list = list_construct(list, test_arr[count]);
quick_sort(&list);
assert(list_is_ordered(list));
list_free(&list);
free(test_arr);
return;
}
```
建立一個陣列 `test_arr`，大小為 100000，內容為 0, 1, 2, ..., 100000， `shuffle` 對其進行亂序操作後，用 `list_construct` 建立一個亂序內容的鏈結串列，最後使用 `quick_sort`，對該鏈結串列進行排序。
#### 如何實作 quick_sort
此處為用於排序鏈結串列的非遞迴 (non-recursive; iterative) 快速排序法 (QuickSort)，以下為程式碼：
```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] = list_tail(list);
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(n->value > value ? &right : &left, n);
}
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(&result, L);
i--;
}
}
*list = result;
}
```
1. 挑選第一個節點作為 pivot，並將 `list` 的首尾節點分別指派給 `begin[0]` 和 `end[0]`。
(此圖修改自 [vestata](https://hackmd.io/@tony268596/linux2024-homework2))
```graphviz
digraph S{
rankdir=LR
node[shape=box]
head[color=white, fontcolor=red]
null[label="NULL", color=white]
4->1->3->5->2->null
head->4{rank=same;head;4}
}
```
(此圖修改於 [YangYeh-PD](https://hackmd.io/-iW9qu9MQYuaky39rwBi3A#Problem-1-Quicksort-Non-recursive))
```graphviz
digraph "Linked List" {
node3[shape = circle, label = "3"];
node5[shape = circle, label = "5"];
node4[shape = circle, label = "4"];
node1[shape = circle, label = "1"];
node2[shape = circle, label = "2"];
begin [shape = none, label=<
<TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="a0"> begin[0]</TD>
</TR> </TABLE>>];
end[shape = none, label=<
<TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="a0"> end[0]</TD>
</TR> </TABLE>>];
end:a0 -> 2;
begin:a0 -> node4 -> node1-> node3 -> node5 -> node2;
}
```
3. 走訪每個節點，將小於 pivot 的節點存進 `left`，大於 pivot 的節點存進 `right`。
4. `begin[i]` 存放 `left`，`begin[i + 1]` 存放 pivot，`begin[i + 2]` 存放 `right`。`end[i]` ~ `end[i + 2]` 存放 `begin[i]` ~ `begin[i + 2]` 的末端節點。
```graphviz
digraph "Linked List" {
node3[shape = circle, label = "3"];
node5[shape = circle, label = "5"];
node4[shape = circle, label = "4"];
node1[shape = circle, label = "1"];
node2[shape = circle, label = "2"];
begin [shape = none, label=<
<TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="a0"> begin[0]</TD>
<TD PORT="a1"> begin[1]</TD>
<TD PORT="a2"> begin[2]</TD>
</TR> </TABLE>>];
end[shape = none, label=<
<TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="a0"> end[0]</TD>
<TD PORT="a1"> end[1]</TD>
<TD PORT="a2"> end[2]</TD>
</TR> </TABLE>>];
end:a0 -> 1;
end:a1 -> 3;
end:a2 -> 5;
begin:a0 -> node2 -> node1;
begin:a1 -> node3;
begin:a2 -> node4 -> node5;
}
```
5. 從 `begin[i + 2]` 開始，也就是 `begin[]` 最末端的串列，繼續找 pivot 切割成 `left` 和 `right`。
```graphviz
digraph "Linked List" {
node3[shape = circle, label = "3"];
node5[shape = circle, label = "5"];
node4[shape = circle, label = "4"];
node1[shape = circle, label = "1"];
node2[shape = circle, label = "2"];
null[shape = none, label = "Null"];
begin [shape = none, label=<
<TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="a0"> begin[0]</TD>
<TD PORT="a1"> begin[1]</TD>
<TD PORT="a2"> begin[2]</TD>
<TD PORT="a3"> begin[3]</TD>
<TD PORT="a4"> begin[4]</TD>
</TR> </TABLE>>];
begin:a0 -> node2 -> node1;
begin:a1 -> node3;
begin:a2 -> null;
begin:a3 -> node4;
begin:a4 -> node5;
}
```
6. 當 `begin[i]` == `end[i]` 時，代表串列已經無法再切割，就可以把該節點加入 `result`，當作排序完成的節點。
```graphviz
digraph "Linked List" {
node1[shape = circle, label = "1"];
node2[shape = circle, label = "2"];
begin [shape = none, label=<
<TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="a0"> begin[0]</TD>
</TR> </TABLE>>];
begin:a0 -> node2 -> node1;
}
```
```graphviz
digraph S{
rankdir=RL
node[shape=box]
result[color=white, fontcolor=red]
null[label="NULL", color=white]
5->4->3->null
result->5
}
```
:::warning
問題
1. why max_level = 2 * n
:::
### 測驗 `2`
> 待完成
---
## [第二週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
用 preoreder 和 inorder 的排序，要求回傳重建的二元樹。
#### Hash Table
使用雙向鏈結串列處理 Hash Table 發生碰撞 (collision) 的情況。
```c
struct hlist_head {
struct hlist_node *first;
}
```
```c
struct hlist_node {
struct hlist_node *next, **pprev;
}
```
```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];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
map:ht1 -> hn1
hn1:next -> null1
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
參考 [Linux 核心的 hash table 實作](https://hackmd.io/rpIi8FeqQ9eBJ-UTFgb--A)
`next` 指向相鄰的**節點本身**，而 `pprev` 指向**指著自身節點的指標**。
+ `hlist_add_head`
```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 = h->first;
n->pprev = &h->first;
h->first = n;
}
```
這個函式執行 hash table 中，將 `n` 插入雙向鏈結串列。將 `hlist_node n` 插入於 `hlist_head h` 的前端。
```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, color = red];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key new"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
map:ht1 -> hn1[color = red]
hn1:next -> hn2[color = red]
hn2:next -> null1
hn2:prev:s -> hn1:next:s[color = red]
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1[color = red]
hn3:prev:s -> map:ht5
}
```
#### TreeNode、order_node
```c
struct TreeNode {
int val;
struct TreeNode *left, *right;
}
```
```c
struct order_node {
struct hlist_node node;
int val;
int idx;
}
```
#### 建樹以及相關操作
+ `find`
```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, &heads[hash]) {
struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
用傳入的 `num` 值尋找 hash table 中的位置索引。宣告 `hash` 得知該節點放於 hash table 中的哪個槽，用 `hlist_for_each` 走訪每個節點，尋找節點並回傳索引。
+ dfs
```c
static struct TreeNode *dfs(int *preorder,
int pre_low,
int pre_high,
int *inorder,
int in_low,
int in_high,
struct hlist_head *in_heads,
int size)
{
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);
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;
}
```
> 待完成
+ `node_add`
```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, &head[hash]);
}
```
這裡執行的是建立一個 node 並將其存放至 hash table。建立一個新節點，宣告 `hash` 決定該節點要存放於 hash table 的哪個槽裡，最後使用 `hlist_add_head` 將該節點加入 hash table
### 測驗 `2`
> 待完成
### 測驗 `3`
實作 `find_nth_bit` 可在指定的記憶體空間找出第 N 個設定的位元。
+ `__ffs`
find first bit set in a word
```c
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
if ((word & 0xffffffff) == 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;
}
```
依循 binary search 的概念，用 mask 做 bit-wise and 找出首個 bit 為 1 的位置 (由右至左)，有了這個函式就可以往下繼續做 fns。
+ `fns`
find N'th bit set in a word
```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;
}
```
使用 `__fns` 從 LSB 找出首個 bit 為 1 的位置，並判斷是否為該 word 中第 `n` 個 1 (由右至左)，若不是的話就把該 bit 清除掉，用 `__fns`繼續找下一個 bit 為 1 的位置。
+ `__clear_bit`
clear certain bit
```c=
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 &= ~mask;
}
```
功能：將 `addr` 的第 `nr` 個 bit 改成 0。
```
清除第 4 個 bit
p = 0111 1011
mask = 0000 1000
~mask = 1111 0111
p & ~mask = 0111 0011
```
其中的 `BIT_MASK(nr)` 和 `BIT_WORD(nr)` 巨集程式碼如下：
```c
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
```
`1UL` 代表無號長整數 1，也就是
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 000**1**
`1UL << ((nr) % BITS_PER_LONG)` 將 `1UL` 向左位移 `(nr) % BITS_PER_LONG` 個 bit。
例如：`BIT_MASK(5)` 的結果
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00**10 0000**
```c
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
```
計算 word 的 offset。
:::warning
不知道第 4 行為什麼要加 `BIT_WORD(nr)`，如果想要清除大於 64 的 bit，那不就代表要清除到該 word 以外的 bit 嗎？為什麼要允許這樣的行為？
:::
+ `small_const_nbits(size)`
判定 `size` 是否為正常的常數且長度大於 0、小於 BIT_PER_LONG (64)。
```c
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
```
+ `GENMASK(h, l)`
產生一個第 `l+1` 到 `h+1` 個 bit 皆為 1，其餘為 0 的遮罩。
```c
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
用一個例子快速了解 `GENMASK` 在幹嘛：
```
BIT_PER_LONG = 8
GENMASK(5, 2):
left : 1111 1111 - (0000 0001 << 2) + 1
=1111 1111 - 0000 0100 + 1
=1111 1100
right : 1111 1111 >> (8 - 1 - 5)
=0011 1111
left & right : 0011 1100
```
+ `FIND_NTH_BIT(FETCH, size, num)`
用來在指定的 bitmap 中，找尋第 n 個 set bit的 index。
```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 % BITS_PER_LONG)
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);
found:
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);
out:
sz;
})
```
#### `find_nth_bit`
find N'th set bit in a memory region
```c=
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);
}
```
輸入參數：
+ addr：欲搜尋的起始記憶體位置
+ size：最大搜尋範圍 (bit)
+ n：欲查找的設定位元個數 (set bit)
接下來讓我們逐行檢視：
第 3~4 行：若欲查找的設定位元數超出最大搜尋範圍，則判定為尋找失敗，回傳 `size`。
第 8~15 行：透過 `small_const_nbits(size)` 檢查 `size` 是否為正常的常數且長度大於 0、小於 BIT_PER_LONG (64)。
+ 若成立，代表要尋找的 index 就落在該字節內。
+ 用 `GENMASK()` 設定一個遮罩，找出要處理的範圍。然後將遮罩後的值傳進 `fns()` 來找第 n 個被設置的位元的索引位置。
+ 若不成立，則代表要尋找的 index 就不在該字節內。
+ 呼叫 `FIND_NTH_BIT()`，來處理跨字節邊界的情況。
> 待完成
Sign in with Wallet
Connect another wallet