# 2025q1 Homework2 (quiz1+2)
contributed by < `chensheep` >
## 2025q1 第 1 週測驗題
### 測驗 `1`
參考 `list_insert_before` 說明如上圖，是要在給定的 `before` 前加入新的 `item`。
考慮以下情形，目前 list 中有三個 items。
```graphviz
digraph DoublyLinkedList {
rankdir=LR;
// node [shape=record, fontname="Arial", style=filled, fillcolor=lightgray];
node [shape=box, fontname="Arial", style=filled, fillcolor=lightgray];
// start [label="head", color=green, fontcolor=green, fillcolor=lightblue];
nodehead [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">head</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node1 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p0" bgcolor="lightyellow">1</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node2 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">2</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node3 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">3</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
end [label="NULL", color=black, fontcolor=black, fillcolor=lightyellow];
nodehead:p1 -> node1;
node1:p1 -> node2;
node2:p1 -> node3;
node3:p1 -> end;
}
```
假設目標是在 1 之前加入一個新的 item 4 ，可以觀察到需要修改部份標注成紅色。
```graphviz
digraph DoublyLinkedList {
rankdir=LR;
// node [shape=record, fontname="Arial", style=filled, fillcolor=lightgray];
node [shape=box, fontname="Arial", style=filled, fillcolor=lightgray];
// start [label="head", color=green, fontcolor=green, fillcolor=lightblue];
nodehead [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">head</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node1 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p0" bgcolor="lightyellow">1</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node2 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">2</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node3 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">3</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node4 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">4</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
end [label="NULL", color=black, fontcolor=black, fillcolor=lightyellow];
nodehead:p1 -> node1;
node1:p1 -> node2;
node2:p1 -> node3;
node3:p1 -> end;
}
```
因此這邊拿一個指針 p 指到要修改的記憶體位置，如下圖，這樣可以同時擁有要修改的位置 p 與指到當前需被比較的 *p。
```graphviz
digraph DoublyLinkedList {
rankdir=LR;
// node [shape=record, fontname="Arial", style=filled, fillcolor=lightgray];
node [shape=box, fontname="Arial", style=filled, fillcolor=lightgray];
// start [label="head", color=green, fontcolor=green, fillcolor=lightblue];
nodehead [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">head</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node1 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p0" bgcolor="lightyellow">1</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node2 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">2</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node3 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">3</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node4 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">4</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
end [label="NULL", color=black, fontcolor=black, fillcolor=lightyellow];
p [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightblue"><font color="black">p</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
nodehead:p1 -> node1;
node1:p1 -> node2;
node2:p1 -> node3;
node3:p1 -> end;
p:p1 -> nodehead:p1;
}
```
觀察 `list_insert_before` 函式
```c=
{
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
```
第 5 行對應流程如下
```graphviz
digraph DoublyLinkedList {
rankdir=LR;
// node [shape=record, fontname="Arial", style=filled, fillcolor=lightgray];
node [shape=box, fontname="Arial", style=filled, fillcolor=lightgray];
// start [label="head", color=green, fontcolor=green, fillcolor=lightblue];
nodehead [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">head</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node1 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p0" bgcolor="lightyellow">1</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node2 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">2</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node3 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">3</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node4 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">4</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
end [label="NULL", color=black, fontcolor=black, fillcolor=lightyellow];
p [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightblue"><font color="black">p</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
nodehead:p1 -> node1 [style=dotted];
node1:p1 -> node2;
node2:p1 -> node3;
node3:p1 -> end;
p:p1 -> nodehead:p1;
nodehead:p1 -> node4 [color=red];
}
```
第 6 行對應流程如下，所以 DDDD 為 item->next
```graphviz
digraph DoublyLinkedList {
rankdir=LR;
// node [shape=record, fontname="Arial", style=filled, fillcolor=lightgray];
node [shape=box, fontname="Arial", style=filled, fillcolor=lightgray];
// start [label="head", color=green, fontcolor=green, fillcolor=lightblue];
nodehead [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">head</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node1 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p0" bgcolor="lightyellow">1</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node2 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">2</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node3 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">3</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightyellow"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node4 [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td bgcolor="lightyellow">4</td>
</tr>
<tr>
<td PORT="p1" bgcolor="lightpink"><font color="black">next</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
end [label="NULL", color=black, fontcolor=black, fillcolor=lightyellow];
p [label=<
<table border="0" cellborder="1" cellpadding="5">
<tr>
<td PORT="p1" bgcolor="lightblue"><font color="black">p</font></td>
</tr>
</table>
>, fillcolor=lightyellow];
node1:p1 -> node2;
node2:p1 -> node3;
node3:p1 -> end;
p:p1 -> nodehead:p1;
nodehead:p1 -> node4;
node4:p1 -> node1 [color=red];
}
```
回到 `list_insert_before` 函式第 3 行， p 一開始指到 list 存放指到第一個 item 指標的位置，因此為 AAAA &l->head。
*p 表示當前的 item 當當前的 item 為目標 before 則離開迴圈，因此 BBBB 為 before。
最後要更新 `p` 為當前 item 存放指向下一個節點指標的位址，所以 CCCC 為 &(*p)->next。
#### 延伸問題
##### 解釋上方程式碼運作原理
##### 在現有的程式碼基礎上，撰寫合併排序操作
### 測驗 `2`
針對本段程式碼
```c=
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE)
pred_ptr = FFFF;
```
閱讀註解可知目標是找到左子樹中最右邊的節點。
所以當此節點沒有右邊的節點即為目標，因此 EEEE 為 (*pred_ptr)->r。
當此節點有右節點時，更新 pred_ptr 為當前節點指向右邊節點的位址，因此 FFFF 為 &(*pred_ptr)->r。
嘗試編譯 [memory-allocators](https://github.com/mtrebi/memory-allocators)
```shell
sudo apt install cmake
cmake -S memory-allocators -B build
cmake --build build
```
### 測驗 `3`
題目中 rebuild_list_link 的目的為給定一個 list 重新將這個 list 中每個節點的 prev 指針重建指向正確的節點。
因為在進行 quick_sort 排序時，我們忽略維護每個節點的 prev 指針，所以排序完成後需對此函式 list 重建 prev 指針。
rebuild_list_link 函式中使用 node 與 prev 去紀錄當前的節點與其前一個節點，以此每次將 node 的 prev 更新，並移動到下一個節點。
最後 node 為 NULL 時離開迴圈，此時 prev 紀錄最後一個節點，因此將其 next 指向 head，並將 head 的 prev 指向其。
即 GGGG 為 head->prev=prev。
接著分析 quick_sort 函式，begin[i] 為目前要排序的 list。
假如 L 等於 R 表示 0 個或 1 個節點，代表排序完成，將這個成果放到 result list 中。
反之代表這個 list 未完成排列，取出其第一個節點作為 pivot，
在透過 list_entry 取出值，因此 HHHH 為 list_entry(pivot,node_t,list)->value。
接著將剩餘的節點依序跟 pivot 的值相比，小於的放到 left 大於的放到 right 相反的放到 left。
分別紀錄這三個 list 到 begin[i]，begin[i+1]，begin[i+2]，因此 JJJJ 與 KKKK 分別為 pivot 與 right。
將 i + 2 表示我們先選擇 begin[i+2] 為下輪要排序的 list。
以下進行簡單的演示
9 5 8 6 1 10
0 1 6 8 5
1 9
2 10
result 9 10
0
1 1
2 5 8 6
0
1 1
2
3 5
4 6 8
0
1 1
2
3 5
4
5 6
6 8
1 5 6 8 9 10
GGGG 為有效 C 語言表示式，不含 ; 或 , 字元
HHHH 和 IIII 包含 list_entry 巨集，不含 ; 字元
JJJJ 和 KKKK 為有效 C 語言表示式，不含 ; 或 , 字元
以最精簡的方式撰寫，不包含空白
list_entry(head->next, node_t, list)->value;
GGGG: head->prev=prev
HHHH: list_entry(pivot,node_t,list)->value
IIII: list_entry(n,node_t,list)->value
JJJJ: pivot
KKKK: right
延伸問題:
解釋上述程式碼運作原理
研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
針對 rebuild_list_link
```c
static void rebuild_list_link(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *prev;
prev = head;
node = head->next;
while (node) {
node->prev = prev;
prev = node;
node = node->next;
}
prev->next = head;
head->prev = prev;
}
```
## 2025q1 第 2 週測驗題
### 測驗 1
快速排序函式的原型宣告如下
```c
static void list_quicksort(struct list_head *head);
```
在 list_quicksort 中本次透過 recursive 方式實現。
在函式 list_quicksort 我們宣告 list_less 與 list_greater 分別用來放置比 pivot 小與大的節點。
如果傳入的 list 為空的或是只有一個節點表示排序完畢。
反之進行排序，這邊取出第一個節點，可以透過 list_first_entry ，因此 AAAA 為 list_first_entry。
取出第一個節點後將其從 list 移除，因此 BBBB 為 list_del。
接著針對剩餘的節點與 pivo 的值進行比較，較小者加入到 list_less 中，反之加入到 list_greater 中。
這邊 CCCC 為 list_move_tail 主要是考量到為符合 stable sorting ，所以先被比較到的節點，其應該放置在 list_greater 前面，所以後來被比較到的節點 list_move_tail 放置到 list_greater 的尾端，可以維持其原本的相對位置。
最後將排序完成的 pivot->list，list_less 與 list_greater 重新放回 head 中。
因為 pivot 為單一節點，所以使用 list_add 即可，因此 DDDD 為 list_add。
list_less 與 list_greater 中有可能有多個節點，因此要透過其他方式。
list_less list 需要放置到 head 的前端，因此透過 list_splice 可以將一個 list 的所有節點放到另一個 list 的前端，EEEE 為 list_splice。
list_less list 需要放置到 head 的後端，因此透過 list_splice_tail 可以將一個 list 的所有節點放到另一個 list 的後端，FFFF 為 list_splice_tail。
EEEE: list_splice()
FFFF: list_splice_tail()
延伸問題：
解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋
MMMM: ~1ULL
1
2
### 測驗 2
### 測驗 3
對應到
find_key 函式實做如下
```c
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
```
hash 的 bit 大小在初始化 map_t 結構時即已經帶入，因此從 map_t 結構中可以取出 AAAA 為 map->bits。
相對應的 BBBB 同樣為 map->bits。
新增操作： (部分遮蔽)
```c
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, BBBB)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
CCCC = &n->next;
h->first = n;
DDDD = &h->first;
}
```
這邊的目標是將新增的 hlist_node 放置到這個 list 的最前方。
因此首先將新增的 node 其 next 指向目前的 first，進一步判斷 first 存在的話，需將期 pprev 修改為新增的 node 的 next 位址。
因此 CCCC 為 first->pprev。
另外需將新增的 node 其 pprev 指到 hlist_head.first 因此 DDDD 為 n->pprev。
接著觀察釋放記憶體的操作:
```c
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = EEEE;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
## Reference
Sign in with Wallet
Connect another wallet