owned this note
owned this note
Published
Linked with GitHub
---
tags: Linux Kernel
---
# 2023q1 Homework1 (quiz1)
contributed by < [`chun61205`](https://github.com/chun61205) >
## 測驗 1
### 解釋程式碼運作原理
該程式碼使用 quick sort 來實作。
結構體如下：
```c
struct item {
uint16_t i;
struct list_head list;
};
```
因此可以判斷出 `AAA` 為 `item` ， `BBB` 為 `list` 。
首先，該程式碼使用串列的第一筆資料當作 `pivot` ：
```c
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
```
接著將值小於 `pivot` 值的資料放到 `list_less` ，並把大於 `pivot` 值的資料放到 `list_greater` 。
```c
struct item *itm = NULL, *is = NULL;
CCC (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
DDD (&itm->list, &list_less);
else
EEE (&itm->list, &list_greater);
}
```
因此從這裡我們便可以判斷出 `CCC` 為 `list_for_each_entry_safe` (因為資料會被移動，所以要使用有 safe 的版本)， `DDD` 和 `EEE` 都是 `list_move_tail` 。至於使用 `list_move_tail` 而不是使用 `list_move` 的原因參考[課堂問答簡記](https://hackmd.io/VIvUZemESvGUev4aCwOnWA?view)：
stable sort alg 指若有多個 elements 有相同的 key value，則 sort 前後其相對關係不變。
e.g
有一 list 5, 3, 3*, 4
其中有兩個 elements 有相同的 key value 3 ，這裡用 3 以及 3* 作為區別。他們兩個的相對關係為 3 在 3* 前面
則經過穩定排序後的結果必為：
3, 3*, 4, 5
若使用不穩定的 sort alg 排序，則結果可能為：
3*, 3, 4, 5
可以看到兩個 3 的相對關係發生改變了。
由於程式是取從開頭 pivot 後往後比較，所以用 list_move_tail 可以確保後面的 ele 被放在後面。
以剛剛提到的 list 5, 3, 3*, 4 為例，則若使用 list_move 的話程式執行會變為：
```
remained list: 3, 3*, 4
^
item
pivot (5)
less_list: 3
---
remained list: 3*, 4
^
item
pivot (5)
less_list: 3*, 3
---
remained list: 4
^
item
pivot (5)
less_list: 4, 3*, 3
---
```
可以看到 3* 和 3 的相對位置改變了。
最後使用 divide-and-conquer 。
配合遞迴排序 `list_less` 和 `list_greater` ：
```c
list_sort(&list_less);
list_sort(&list_greater);
```
並將排序好的兩個串列連接。
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
```
因此可以判斷這裡的 `FFF` 為 `list_splice_tail` 。
## 測驗 2
### 解釋程式碼運作原理
該程式碼使用迭代的方式實作 `quick_sort` 。
該程式碼使用 `stack` 來存取待排序的串列。
```c
struct list_head stack[MAX_DEPTH];
```
這裡的 `if` 代表，如果 `partition` 如果不是空或者只有一點，就把 `partition` 依照 `pivot` 分成 `list_less` 和 `list_greater` 。其中 `list_del(&itm->list)` 是多餘的，後面的 `list_move` 已經包含相同的效果。
同樣是使用第一筆資料當作 `pivot`
```c
struct item *pivot = list_first_entry(&partition, struct item, list);
```
同樣是再比較後將值小於 `pivot` 值的資料放到 `list_less` ，並把大於 `pivot` 值的資料放到 `list_greater` 。
```c
GGGG (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
```
因此可以判斷這裡的 `GGGG` 為 `list_for_each_entry_safe` 。
最後再將 `pivot` 放到 `list_less` 的最後，並將兩個串列放到 `stack` 中：
```c
HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
```
因此可以判斷 `HHHH` 為 `list_move_tail` ， `IIII` 和 `JJJJ` 都代表 `stack` 的頂端，因此為 `&stack[++top]` 。
另一方面
```c
else {
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp = list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(KKKK);
list_add_tail(&tmp->list, head);
}
}
```
代表如果 `stack` 的頂端只剩一筆資料，則向下合併，因此 `KKKK` 為 `&stack[top--]` 。
而這段程式碼，可以使用下面這段來代替：
```c
else {
while (top >= 0 && list_is_singular(&stack[top])) {
list_splice_tail_init(&stack[top--], head);
}
}
```
## 測驗 3
### 解釋程式碼運作原理
該程式碼利用 XOR 運算來找出下 linked list 的下一個節點。
其中，核心的巨集如下：
```c
#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))
```
其目的是以 `a` 和 `b` 進行 XOR 運算，因此 `LLLL` 為
`(uintptr_t)(a) ^ (uintptr_t)(b)`
另一個常用的函式如下：
```c
static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
assert(n1 && n2);
return XOR_COMP(n1, n2);
}
```
此函式的目的在於，再透過 `assert` 判斷 `n1` 和 `n2` 是否為 `NULL` 後再裡用 `XOR_COMP` 來獲得下一格地址。
XOR 運算可以透過前一個的地址以及這一格的 link 來獲得下一格的位址，因此當前位置的 link 可以透過前後兩個點的地址進行 xor 運算得到。
`xorlist_for_each`, `xorlist_for_each_prev`, `xorlist_for_each_from`, `xorlist_for_each_from_prev` 的功能大同小異，都是尋訪整個串列，因此這裡挑出 `xorlist_for_each` 說明。
```c
#define xorlist_for_each(node, rp, rn, list) \
for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
```
這個巨集透過 `address_of(rp, node->cmp)` ， `rp` 和 `node->cmp` ，也就是前一格的位置和目前格子的 `link` 進行 XOR 運算得到下一格的位置。
接者是 `xorlist_add`
此函式的目標是將 `n` 加入到 `list` 中。
```c
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
xor_node_t *real_next;
if (!n)
return ENOMEM;
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
if (node == &list->tail)
real_next = MMMM;
else
real_next = node;
real_prev->cmp = n;
n->cmp = XOR_COMP(real_prev, real_next);
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
list->count++;
return 0;
}
```
首先 `node` 儲存了 `real_prev->cmp` 也就是前一個節點的 `link` ，因此可以判斷出 `node` 會用在找出下一格位置的 XOR 運算中。
接著，判斷 `list` 是否為空的，如果是的話就將 `%list->tail` 指定給 `real_next`。
最後再計算和更新 `real_prev`, `real_next` ，先將 `real_prev->cmp` 設定為 `n` 代表插入新節點，並藉由 `n->cmp = XOR_COMP(real_prev, real_next)` 更新新節點的 `link` ，接著在更新 `real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP))` 就可以完成插入。因此這裡的 `PPPP` 為 `real_next->cmp` 。
值得注意的是，當 `list` 為空時 `head` 節點內的 `cmp` 就會是 `tail` 因此可以將程式碼改成：
```c
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
if (!n)
return ENOMEM;
xor_node_t *real_prev = &list->head;
xor_node_t *real_next = real_prev->cmp;
real_prev->cmp = n;
n->cmp = XOR_COMP(real_prev, real_next);
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
list->count++;
return 0;
}
```
這裡參考了 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-quiz1#2023q1-Homework1-quiz1) 的筆記。
## References
[2023q1 第 1 週測驗題 - HackMD](https://hackmd.io/@sysprog/linux2023-quiz1)
[第 1, 2 週課堂問答簡記 - HackMD](https://hackmd.io/VIvUZemESvGUev4aCwOnWA?view)
[2023q1 Homework1 (quiz1) contributed by < yanjiew1 >](https://hackmd.io/@yanjiew/linux2023q1-quiz1#2023q1-Homework1-quiz1)
Sign in with Wallet
