# linux2025-homework2
contributed by <[``Ian-Yen``](https://github.com/Ian-Yen/lab0-c)>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 2025q1 第 1 週測驗題
### 測驗一
這邊先把答案填上：
`AAAA : &l->head`
`BBBB : before`
`CCCC : &(*p)->next`
`DDDD : (*p)->next`
:::success
解釋上方程式碼運作原理
:::
```c
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
(*p)->next = before;
}
```
根據題目敘述，這個函式希望能夠把 `item` 放在 `l` 這個 `list` 的 `before` 之前。
而這個list最前面的節點就是 `head` 。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
before [label = "<name>before"]
node1 [label = "item"]
node2 [label = "..."]
node3 [label = "<name>..."]
null [label = "NULL"]
p->head
head->node3:name
node3-> before
before->node2
node2->null
}
```
先把 `p` 指向 `head`
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
before [label = "<name>before"]
node1 [label = "item"]
node2 [label = "..."]
node3 [label = "<name>..."]
null [label = "NULL"]
head->node3:name
p->node3
node3-> before
before->node2
node2->null
}
```
往後面一個一個找
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
before [label = "<name>before"]
node1 [label = "item"]
node2 [label = "..."]
node3 [label = "<name>..."]
null [label = "NULL"]
head->node3:name
node3-> before
p->before
before->node2
node2->null
}
```
找到 `before` 這時跳出迴圈。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
before [label = "<name>before"]
node1 [label = "item"]
node2 [label = "..."]
node3 [label = "<name>..."]
null [label = "NULL"]
head->node3:name
node3-> node1
p->node1
before->node2
node2->null
}
```
把 `item` 塞進去。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
before [label = "<name>before"]
node1 [label = "item"]
node2 [label = "..."]
node3 [label = "<name>..."]
null [label = "NULL"]
head->node3:name
node3-> node1
p->node1
node1->before
before->node2
node2->null
}
```
把 `before` 接回去。
下面是如果 `before` 是 `head` 。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
item
p->head
}
```
`p` 指向 `head` 然後跳出去。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
p->item->head
}
```
`item` 變到前面了。
下面是如果 `before` 是 `NULL`。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
node1 [label = "..."]
node2 [label = "NULL(before)"]
item
head->node1->node2
p->node2
}
```
`p` 找到最後一個的 `next` 也就是 `NULL`。
```graphviz
digraph linked_list {
node [shape=record];
rankdir=LR;
p [label = "p"]
head [label = "head"]
node1 [label = "..."]
node2 [label = "NULL(before)"]
item
head->node1->item
p->item->node2
}
```
`item` 跑到最後一個了。
其他行為都是為定義的行為。
:::success
在現有的程式碼基礎上，撰寫合併排序操作
:::
```c
static int list_size(list_t *l)
{
if(!l || !l->head)
return 0;
int ret = 1;
for(struct list_item *h = l->head;h->next;h = h->next, ret++)
;
return ret;
}
```
先補上裡面沒有的 `list_size`。
#### `merge`。
```c
static inline list_item_t *merge(list_item_t *l, list_item_t *r)
{
list_item_t *h = NULL;
list_item_t **node = &h;
for(;l && r;){
if(l->value <= r->value) {
*node = l;
node = &l->next;
l = l->next;
} else {
*node = r;
node = &r->next;
r = r->next;
}
}
*node = l ? l : r;
return h;
}
```
先判斷要先放 `l` 或是 `r` 的下一個值，然後使用到指標的指標來把他放進去，並先找到下一個值應該要被放在哪裡，一直循環直到某一邊空了，就直接把另一邊放進去然後回傳。
##### 例外處理
如果 `l` 與 `r` 只有一個不是 `NULL` 或是兩個都是 `NULL` ，就會直接跳過迴圈，然後先找有沒有不是 `NULL` 的那個回傳，都是的話就隨便傳一個，我這邊用 `l` 判斷所以都是 `NULL` 就會回傳 `r` 。
#### `sort`
這邊原本要用 `linux` 核心風格的 `list_sort` ，但是單向鍊結串列沒有雙向鍊結串列的優點，少一邊不能串在一起，所以在這邊使用陣列來做，擷取他的想法，用 `count` 來判斷要合併幾個，雖然少了保證合併時大小的比值至多為 `2` 的優勢 ，但這樣可以不用在合併的時候多耗費 $O(log_2n)$ 的時間來把所有的東西往前移一格，且也能盡量作到合併時大小為 `1:1` 的優勢。
```c
static inline void sort(list_t *l)
{
if(!l || !l->head)
return;
list_item_t *stack[12] = {NULL};
int count = 0, pos = 0;
for (list_item_t *p = l->head, *safe;p; p = safe) {
safe = p-> next;
p->next = NULL;
stack[pos++] = p;
for (int tmp = count; tmp & 1; tmp >>= 1, pos--)
stack[pos - 2] = merge(stack[pos - 1], stack[pos - 2]);
count++;
}
for (;pos > 1 ;pos--)
stack[pos - 2] = merge(stack[pos - 1], stack[pos - 2]);
l->head = stack[0];
}
```
### 測驗二
這邊先把答案填上
`EEEE : (*pred_ptr)->r`
`FFFF : &(*pred_ptr)->r`
:::success
解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
:::
這邊的 `remove_free_tree` 是希望找到一個擁有大於等於 `target` 的 `size` 的所有位置裡面的最小值，然後把它從樹裡面移除，如果這棵數裡面所有的節點都比 `target` 的 `size` 小，就回傳NULL。
而因為這棵數是一棵 `binary search tree` 所以要找到目標位置，可以先看這個節點的 `size` 有沒有大於 `target` ，如果沒有的話，就往右邊的子節點去找，如果有的話，就先看看往左邊的子節點的 `size` 有沒有大於等於 `target` 要的 `size` ，有救往左邊的子節點找，沒有的話就回傳現在的節點。
:::success
解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
:::
要讓這邊的程式碼能動，只要補足 `find_free_tree` 即可。
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
if(!(*root))
return root;
if((*root)->l && (*root)->l->size >= target->size)
return find_free_tree(&(*root)->l, target);
else if((*root)->size >= target->size)
return root;
else
return find_free_tree(&(*root)->r, target);
}
```
:::success
參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
:::
待辦
### 測驗三
這邊先把答案填上：
`GGGG : head->prev = prev`
`HHHH : list_entry(pivot, node_t, list)->value`
`IIII : list_entry(n, node_t, list)->value`
`JJJJ : pivot`
`KKKK : right`
:::success
解釋上述程式碼運作原理
:::
#### 分析quick_sort實做細節
首先把第一個節點當作 `pivot` ，並用他的值來當作 `value` 從左邊往右邊找，當一個節點的值小於等於 `value` 就把它丟進 `left` 其他丟進 `right`。
然後把 `left` , `pivot` , `right` 分別照順序丟進 `begin` ， `begin` 裡面紀錄的值的值域可以很明顯的發現是排序後的 `(begin[i]的最大值 < begin[i + 1]的最小值)` 然後往右找，先把右邊的做好了，再做左邊。
:::success
研讀〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
:::
從這篇裡面可以看到，他利用雙向 `link_list` 做了一個 `tree_sort` 作法是將 `prev` 與 `next` 拿去當成 `l` 與 `r` 然後用遞迴的方式再把它變回一個雙向 `link_list` 的形式。
```c
static struct void traverse(struct list_head *root,
struct list_head *head)
{
struct list_head *work;
if(!root){
traverse(root->prev);
work = root->next;
list_add(root, head);
traverse(work);
}
}
static void tree_sort(struct list_head *head)
{
if(!head)
return;
struct list_head *result = NULL, **p = &result, *h = NULL, *t = NULL;
element_t *pos, *safe;
list_for_each_entry_safe (pos, safe, head, list) {
p = &result;
while(*p) {
if(strcmp(pos->value, list_entry(*p, element_t, list)->value) >= 0)
p = &(*p)->next;
else
p = &(*p)->prev;
}
*p = &pos->list;
(*p)->next = NULL;
(*p)->prev = NULL;
}
head->next = head;
head->prev = head;
traverse(result, head);
}
```
## 2025q1 第 2 週測驗題
### 測驗一
這邊先把答案填上：
`AAAA : list_first_entry`
`BBBB : list_del`
`CCCC : list_move_tail`
`DDDD : list_add`
`EEEE : list_splice`
`FFFF : list_splice_tail`
:::success
解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
:::
他的運作原理跟上面的測驗3很像，只是把迴圈的部份改成遞迴，這邊就不多贅述了。
把 `list_move_tail` 改成 `list_move` 不能滿足 `stable sorting` 的原因是因為這樣順序會顛倒，如果有兩個相同的 `value` 他們的順序會跟初始的不一樣。
#### 改進 random_shuffle_array
用 `hw1` 提到過的 `Fisher-Yates Shuffle` 改進 `random_shuffle_array`
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
uint16_t j = i + get_unsigned16() % (len - i);
uint16_t temp = operations[i];
operations[i] = operations[j];
operations[j] = temp;
}
}
```
:::success
將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋
:::
### 測驗二
Sign in with Wallet
Connect another wallet