# 2025q1 Homework2 (quiz1+2)
contributed by < [fcu-D0812998](https://github.com/fcu-D0812998) >
## [第一週測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)
### 測驗一
#### 解釋程式碼運作原理
首先這個測驗是要考函數 `list_insert_before` 的運作流程， `list_insert_before` 的主要目標是在單向鏈結串列中，找到 ` before ` 節點，並將 item 節點插入在它的前面。這是一種間接修改鏈結串列的方法，因為 `list` 本身是單向鏈結串列，且這個函式的實作運用了「指標的指標」技巧，我們可以簡化對鏈結串列的操作，特別是在插入或刪除節點時。
``` c
p = &list->head;
```
首先 `p` 是一個「指標的指標」，它最開始指向 `list->head` 的位址，也就是 `head` 的記憶體位置。
```graphviz
digraph linkedlist{
rankdir=LR
p[shape=none,label=p]
before[shape=none,label=before]
head[shape=none,label=head]
null[shape=none,label=NULL];
a [shape=record,label="{ <data> 3 | <ref> }"];
b [shape=record,label="{ <data> 2 | <ref> }"];
c [shape=record,label="{ <data> 1 | <ref> }"];
d [shape=record,label="{ <data> 4 | <ref> }"];
{ rank = same; p -> head[arrowhead=vee, arrowtail=dot, dir=both,minlen=3] }
head -> a
before -> a
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
* 我們現在要將值為5的node插在2之前。
``` c
for (p = &l->head; *p != before; p = &(*p)->next)
```
* 迴圈的目標是找到指向 `before ` 的指標，讓` p` 能指向` before` 前一個節點的 ` next` 指標。剛開始不太理解 `*` 跟 `&` 的應用，看了幾次之後懂了。
1. 首先 `l->head` 指向第一個節點， `&l->head` 也就是取得 `l->head` 這個指標的地址，能讓p去指向這個位址。
2. 再來要讓 `p` 再回圈內在 `before` 前停下來，就必須取值去判斷，所以使用 `*p` 。
3. 再來如果判斷不成要指向下一個節點的話就要取址，首先先用`*p`取得目前所在的指標， `(*p)->next` 是目前指到的節點的下一個節點，再取址，就能讓 `p` 指向下一個指標的位址了。
``` c
*p = item;
item->next = before;
```
* `*p` 代表「目前的 next 指標」， `*p = item` 讓 next 指標改指向 item ，將新節點插入，根據圖例就是 `p = &([2]->next)` ，即 `*p ` 代表 [2] 的 next，此時 `item->next` 還沒設置，所以最後要將 `item->next` 指向 `before` 。
```graphviz
digraph linkedlist{
rankdir=LR
p[shape=none,label=p]
before[shape=none,label=before]
head[shape=none,label=head]
null[shape=none,label=NULL];
a [shape=record,label="{ <data> 3 | <ref> }"];
b [shape=record,label="{ <data> 5 | <ref> }"];
c [shape=record,label="{ <data> 2 | <ref> }"];
d [shape=record,label="{ <data> 1 | <ref> }"];
e [shape=record,label="{ <data> 4 | <ref> }"];
{ rank = same; p -> head[arrowhead=vee, arrowtail=dot, dir=both,minlen=3] }
head -> a
before -> a
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
* 解釋完 `list_insert_before` 的運作流程後，往測驗1上面的程式碼做運作流程解析，上述程式碼主要是在測試 `list_insert_before` 函式的正確性，確保鏈結串列的插入操作能夠正確運作。
一開始定義了兩個巨集:
1. `my_assert()` : 這是一個條件檢查巨集，如果 test 為false，則回傳 message，表示測試失敗。
2. `my_run_test()` : 這是一個測試執行巨集，用來執行一個測試函式並計數。
* 後面依序是
1. ` list_reset()` ：重設鏈結串列，確保每次測試前，鏈結串列都是空的狀態。
2. ` test_list()` ：測試` list_insert_before()` 是否能正確地在不同位置插入節點。
3. ` test_suite()` ：執行測試函式 ` test_list()` 。
4. ` main()` ：呼叫 `test_suite()` ，輸出測試結果，因為 `test_list()` 只測試 `list_insert_before()` ，所以最後 `tests_run = 1` 。
#### 在現有的程式碼進行合併排序
``` c
list_item_t *mergeTwo(list_item_t *left, list_item_t *right) {
list_item_t *head;
list_item_t **ptr = &head;
while (left && right) {
if (left->value < right->value) {
*ptr = left;
left = left->next;
} else {
*ptr = right;
right = right->next;
}
ptr = &(*ptr)->next;
}
if (left) {
*ptr = left;
} else {
*ptr = right;
}
return head;
}
```
``` c
list_item_t *mergeSort(list_item_t *head) {
if (!head || !head->next) return head;
list_item_t *slow = head;
list_item_t *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
list_item_t *left = head;
list_item_t *right = slow->next;
slow->next = NULL;
list_item_t *sort_left = mergeSort(left);
list_item_t *sort_right = mergeSort(right);
return mergeTwo(sort_left, sort_right);
}
```
* 概念跟作業1的`q_sort`想法一樣，只是這個是單向的鏈結串列，首先第一步先用快慢指標找出鏈結串列位於中間的值，將鏈結串列分成左半部分跟右半部分，利用遞迴的方式一直切成許多塊，再用 `mergeTwo` 函式比較傳入的兩個串列得 `value` 大小，比較小的話就輸入到暫存的 `ptr` 裡然後指向下一個節點繼續跟剛剛的值做比較，這樣就可以完成升序排列。
### 測驗二
#### 解釋上方程式碼運作的原理
* 這段程式碼的作用是利用二元搜尋樹( BST )動態記憶體分配器的空閒區塊，首先一開始以為 `node_ptr` 是指向 `target` 父節點的右子樹這個指標的指標，後來發現在刪除的節點沒有子節點的情況下，要將 `node_ptr` 設成 `NULL` 就能刪除預刪除的節點就應該不會是指向 `target` 這個指標的指標，而是指向 `target` 這個節點的父節點***指向 `target`*** 的指標。
* 首先先使用 `find_free_tree` 找到指向目標節點的指標，也就是 `target`，接下來判斷三種可能:
1. **如果要刪除的節點沒有子節點**
```graphviz
digraph 1{
node [fontname="Arial"];
5 -> 3;
5 -> 7;
3 -> 2;
3 -> 4;
null0 [shape=none,label=NULL];
7 -> null0
n[shape=none,label=node_ptr];
t[shape=none,label=target];
t -> 8
p[shape=none,label=pred_ptr];
p -> 3
{ rank = same; n; dummy }
dummy[ shape = point, width = 0 ];
7 -> dummy[ arrowhead = none ];
dummy -> n[ dir = back ];
dummy -> 8;
}
```
``` c
else {
*node_ptr = NULL;
}
```
* 這樣根據開頭的解釋，就將 `node_ptr` 指向預刪除節點的父節點指向預刪除節點的指標。
2. **如果預刪除節點只有一個子節點**
```graphviz
digraph 1{
node [fontname="Arial"];
5 -> 3;
3 -> 2;
3 -> 4;
n[shape=none,label=node_ptr];
t[shape=none,label=target];
c[shape=none,label=child];
null0 [shape=none,label=NULL];
7 -> null0
t -> 7
c -> 8
7 -> 8;
{ rank = same; n; dummy }
dummy[ shape = point, width = 0 ];
5 -> dummy[ arrowhead = none ];
dummy -> n[ dir = back ];
dummy -> 7;
}
```
``` c
else if ((*node_ptr)->l || (*node_ptr)->r) {
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
}
```
* 首先先判斷說預刪除節點` target `他是存在左子節點還是存在右子節點，圖中假設` target `是存在右子節點，那就將` child `指向右子節點，那跟剛剛一樣` node_ptr `是指向預刪除節點的父節點指向預刪除節點的指標，那如果直接將` *node_ptr = child `，就可以直接將父節點接到預刪除節點的唯一子節點。
**3.如果節點有兩個子節點**
``` c
if ((*node_ptr)->l && (*node_ptr)->r)
```
如果預刪除節點有兩個子節點，根據二元樹的定理，左子樹的值必須比父節點的值更小，而右子樹則須更大，所以必須抓取前驅節點，也就是左子樹的最大值來填補空缺。
``` c
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
```
* 此程式碼就是先將` pred_ptr` 指向預刪除節點指向左子樹的指標，再利用迴圈依序往右子樹的方向走，這樣就能找到左子樹的最大值。
```graphviz
digraph 1{
node [fontname="Arial"];
t -> 5
5 -> 3;
5 -> 7;
3 -> 2;
3 -> 4;
t[shape=none,label=target];
c[shape=none,label=child];
null0 [shape=none,label=NULL];
7 -> null0
c -> 8
7 -> 8;
}
```
* 根據圖的狀況，` pred_ptr` 是指向值為 4 的這個節點上，我們就先用` remove_free_tree `刪除值為 4 的這個節點的父子點指向他的指標，再將需要替換的節點接到` target `的位置。
``` c
remove_free_tree(&old_left, *pred_ptr);
*node_ptr = pred_node;
```
* 另一種情況就是左子樹的最大值就在原本要刪除節點的下一層，所以直接將` target `左子樹的右子樹指標指向` target `的右子樹指標就可完成刪除+替換。
``` c
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr;
(*node_ptr)->r = old_right;
```
#### 補完程式碼，使其可獨立執行
``` c
block_t **find_free_tree(block_t **root, block_t *target) {
while (*root && *root != target) {
if (target->size < (*root)->size)
root = &(*root)->l;
else
root = &(*root)->r;
}
return root;
}
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
block_t *pred = NULL;
if (node->l) {
pred = node->l;
while (pred->r)
pred = pred->r;
}
return pred;
}
```
* ` find_free_tree `就是用來在 BST 中找到` target `，從` root `開始找，比他小就往左子樹走，比他大就往右子樹走，直到找到為止。
* ` find_predecessor_free_tree `就是用來在 BST 中找到` target `的左驅節點，原理的話就是先指到` target `的左子樹，再依序往右子樹走就能找到` target `的左驅節點。
#### 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)
* 看了老師提供的網址，那該網址就是再說他提供了多種自訂的 C++ 記憶體配置器用來提升動態記憶體分配的效能。因為在 C++ 中，標準的` malloc `函數用於動態分配記憶體，但在某些情況下，標準的記憶體分配方式可能無法滿足特定的效能需求，像是當你需要頻繁的分配或釋放的話，就會導致大量的系統開銷。這個專案就展示了如何透過實作自訂的記憶體配置器，來優化記憶體分配的效能。
1. ` Linear Allocator ` : 線性配置器是一個最簡單且高效的記憶體管理策略，適用於批量分配記憶體但不需要個別釋放的場景，它的核心就是利用一個指標` offset `來追蹤記憶體的使用狀態，分配記憶體時，只需將指標` offset `向前移動，因此時間複雜度為` O(1) `，且因為` offset `只會向前移動，所以無法單獨釋放某一個記憶體區塊，只能透過` Reset `一次性釋放整塊記憶體，讓` Offset = 0`，重置配置器。
``` c
currentAddress = (std::size_t)m_start_ptr + m_offset
```
* 首先計算記憶體當前的位置。
``` c
if (alignment != 0 && m_offset % alignment != 0) {
// Alignment is required. Find the next aligned memory address and update offset
padding = Utils::CalculatePadding(currentAddress, alignment);
}
```
* 利用` alignment `變數確認是否對齊，若無則透過` Utils::CalculatePadding() `計算填充`（padding）`。
``` c
if (m_offset + padding + size > m_totalSize)
return nullptr;
```
* 這段就是用來檢查是否超過記憶體池大小。
``` c
m_offset += padding;
const std::size_t nextAddress = currentAddress + padding;
m_offset += size;
```
* 如果上述都通過，就更新指標與偏移量。
2. ` Stack Allocator ` : 是一種` LIFO `的記憶體管理方式，跟` Linear Allocator `一樣都是利用指標` offset `來追蹤記憶體的使用狀態，他與` Linear Allocator `的差異在於` Linear Allocator ` 只能` Reset() ` 整塊釋放，而` Stack Allocator ` 可以逐步釋放記憶體，這是因為` Stack Allocator `利用了` Header `這個結構體，每次分配記憶體時，會在記憶體區塊的前方存儲` Header `，時間複雜度為 O(1)。
3. ` Pool Allocator ` : `Pool Allocator` 跟傳統 `allocator` 例如 `malloc` 或 `free` 不同。它的想法是將一大塊連續記憶體，切成很多相同大小的記憶體區塊叫做 `chunk`，且每個 `chunk` 大小固定。而 `Pool allocator` 只負責這些固定大小的 `chunk` 。這樣做的好處是 `allocate` 和 `free` 速度極快，因為只要簡單操作 `linked list`，時間複雜度為 `O(1)` 。
4. ` Free List Allocator ` : ` Free List Allocator `: 是一種較通用型的記憶體配置器，適合處理不同大小的記憶體區塊，不像 `Pool Allocator` 僅處理固定大小。它的核心是利用一條 `linked list` 來追蹤哪些記憶體區塊尚未使用，每個空閒區塊通常包含兩個欄位區塊大小與下一個空閒區塊的指標。配置記憶體時，遍歷整條 `free list` 找到最合適的區塊，可根據策略選擇 `First Fit 、 Best Fit 或 Worst Fit` ，若區塊過大則可切割剩餘的部分繼續保留在 `free list` 中。釋放時則將該區塊重新插入 `free list`，並嘗試與前後相鄰區塊做合併以減少碎片化。由於分配時需遍歷 `free list` ，時間複雜度為 `O(n)`，但提供比 `Linear` 或 `Pool` 更大的彈性，適合記憶體需求多樣化的系統。
* `explicit allocator` 在平均的時間複雜度上為 `O(nlogn)` ，只比` Free List Allocator `來的好，但比起 `Linear Allocator` 或 `Stack Allocator` 只能依照順序配置與釋放，`explicit allocator` 更具通用性，能支援任意順序的配置與釋放，與 `Pool Allocator` 相比， `explicit allocator` 不限制區塊大小， `explicit allocator` 則能處理各種大小的配置需求。
### 測驗三
#### 解釋上述程式碼運作原理
* 測驗三利用非遞迴快速排序法，對一個以 `list_head` 結構串起來的鏈結串列排序，主要將資料不斷劃分為小於 pivot、等於 pivot、大於 pivot 的三段子序列，再逐步處理這些子序列直到完成排序。
* 解釋程式碼運作原理:
```c
struct list_head *L = begin[i], *R = list_tail(begin[i]);
if (L != R) {
struct list_head *pivot = L;
value = list_entry(pivot, node_t, list)->value;
struct list_head *p = pivot->next;
pivot->next = NULL; /* break the list */
}
```
* 取出堆疊中當前要排序的子串列開頭 L 和結尾 R
* 將第一個節點視為 pivot
* 用 p = pivot->next 逐個處理剩下的節點
* 利用 value 來將小於 pivot 的節點放入 left，大於的放入 right
```c
n->next = left/right;
...
begin[i] = left;
begin[i+1] = pivot;
begin[i+2] = right;
```
* 將目前的節點串列劃分為三個分割：left、pivot、right
* 將這三段 push 回 begin[] 模擬堆疊（下一回合先處理 right）
```c
if (L) {
L->next = result;
result = L;
}
i--;
```
* 若該段只剩一個節點（即無需再分割），加入已排序的 result
```c
list->next = result;
rebuild_list_link(list);
```
* 排序完成後，把 result 接回 list->next
* 並用 rebuild_list_link() 重新設定 prev 與尾端閉環回 head（保持 list_head 結構）
```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; /* GGGG */;
}
```
* 最後這邊要將原本單向的鏈結串列(只有 next )變成雙向的，最後在收尾時要將 head 的 prev 指回最後一個節點。
#### 研讀[〈A comparative study of linked list sorting algorithms〉](https://dl.acm.org/doi/pdf/10.1145/225890.225893)，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
此論文提及的兩種雙向鏈結串列分別為 `Sediment Sort` 跟 `Tree Sort`
* `Sediment Sort` : 本質為 `Bubble Sort` 的變形，差別只在於使用了 `new_tail` 來限制交換範圍，意思就是說當你利用迴圈跑完一次後，根據泡沫排序法的方法，最大值一定會被交換到最後一個位置，看似是去優化 `Bubble Sort` ，其實並不然，因為 `Sediment Sort` 是專為 `doubly linked list` 去做設計，但在新增了 `new_tail` 後其實並沒有到很有效的縮減時間複雜度
* `Tree Sort`
## [第二週測驗題](https://hackmd.io/@sysprog/linux2025-quiz2)
### 測驗一
如何使用 Linux 核心的 `list_head` API，實作一個穩定的 `quick sort`。
```c
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
* `AAAA` : 根據快速排序， pivot 應該要為雙向 queue 的第一個節點，而 `list_first_entry` 是用來從 list 頭取出第一個節點，當作 pivot。
* `BBBB` : 這邊要從原 list 中拿掉 pivot，避免在 partition 時重複處理它，所以使用 `list_del` 。
* `CCCC` : 將 `>= pivot` 的節點移到 `list_greater` 的尾端，利用 `move_tail` 可以穩定排序
* `DDDD` : 利用 `list_add` 把 pivot 插回 head 的最前面。
* `EEEE` : `list_splice()` 能把整個 list 插入到另一個 list 的開頭位置，把 `list_less` 全部插入 head 的「前面」 → 剛好在 pivot 前面
* `FFFF` : 同理，把 `list_greater` 插入到 head 的「尾端」
### 測驗二
實作一種高效的整數平方根 `sqrt(uint64_t)`
```c
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
if (c == 3)
return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 0);
}
```
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
/* clz64(x) returns the count of leading zeros in x.
* (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
* Rounding that index down to an even number ensures our starting m is a
* power of 4.
*/
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
函式 `clz2(uint32_t, int)` 用來計算他的 leading zeros ，也就是從最高位往最低位算有幾個連續 0 ，先估算我們要解的值最接近 2 的多少次方，首先將此二進位表示的值切成上下部分，看哪一半為非 0 ，如果上半為 0，就只看下半，並加上上半的位元數來累計前導零，當只剩下 2 bits 時，用 `magic[]` 查表得到最後的 leading zero 數。先用 shift 找出 x 最接近 2 的多少次方，在利用迴圈 y 每次右移 1 ， m 每次右移 2 ，這樣等到 m 變為 2 的 0 次方時， y 就會是 x 的整數平方根解。
Sign in with Wallet
Connect another wallet