# 2025q1 Homework2(quiz1+2)
contribute by [dingsen-Greenhorn](https://github.com/dingsen-Greenhorn/lab0-c)
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
---
## Week1_Quiz
### 測驗1-1
#### 首先定義要用到的程式
```
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
```
#### 參考示意圖如下：
#### 此處實做 list_insert_before
```
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;
item->next = before;
}
```
list_insert_before在單向鏈結串鏈中，在指定節點的前面插入新節點
而迴圈中，讓 p 持續向右移動，當 *p == before 時，代表此時 **p 是指向前一個節點的 *next 也就是停止處。再讓 item->next 指向 before 此時示意圖如下便將節點插入指定節點之前。
---
假設我們有一個鏈結串列，如下所示：
```
head -> 0 -> 1 -> 2 -> 3 -> NULL
```
我們要在節點 2 之前插入一個新節點 99。
初始化指標 p：p 開始指向 head。
遍歷鏈結串列：p 依次指向節點 0, 1, 2，直到找到要插入的位（2）。
插入節點 99：當 p 指向節點 2 時，我們將 99 插入到它之前，將 p 指向 99，並將 99->next 指向原來的節點 2。
結果會變成：
```
head -> 0 -> 1 -> 99 -> 2 -> 3 -> NULL
```
這樣，99 節點就被成功插入到 2 節點之前了。
#### 在現有的程式碼基礎上，撰寫合併排序操作
---
### 測驗1-2
現在我們刪除 30：
```
[50]
/ \
[30]* [70]
/ \ / \
[20] [40] [60] [80]
```
#### 步驟 1：找到 30
使用 find_free_tree(&root, 30)：
```
block_t **find_free_tree(block_t **root, block_t *target) {
block_t **current = root;
while (*current) {
if (*current == target) {
return current; // 找到目標，返回指標
} else if (target->size < (*current)->size) {
current = &((*current)->l); // 向左子樹搜尋
} else {
current = &((*current)->r); // 向右子樹搜尋
}
}
return NULL; // 沒找到
}
```
延續以上的例子說明：
target = 30
current = &root（指向 50）
30 < 50，往左走 → current = &(50->l)（指向 30）
找到 30，返回 &(50->l)
#### 步驟 2：刪除 30
```
if ((*node_ptr)->l && (*node_ptr)->r)
若 target 節點同時有左、右子樹，則：
找到「中序前驅 (in-order predecessor)」，即左子樹中最大的節點。用這個前驅節點來取代 target。
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r != NULL)
pred_ptr = pred_ptr = &(*pred_ptr)->r;
```
30 有兩個子節點 (20 和 40)，所以需要找到 前驅節點（左子樹的最大值）。20 是 30 的左子樹，20 沒有右子節點，因此 20 就是 30 的前驅。
#### 步驟 3：用 20 取代 30
20 取代 30
40（原本 30 的右子節點）保持不變
刪除原本的 20 節點
```
[50]
/ \
[20] [70]
\ / \
[40] [60] [80]
```
30 成功被刪除，BST 結構仍然有效！
#### target 的前驅更深（在左子樹更深處）
當 target 左子樹更深時，我們需要找到左子樹最右側的節點：
```
else {
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* 先遞迴刪除前驅 */
remove_free_tree(&old_left, *pred_ptr);
/* 用前驅來替換 target */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
}
```
範例 （前驅節點更深）：
```
[50]
/ \
[30] [70]
/ \
[10] [40]
\
[20]
```
刪除 30：
target = 30
前驅 = 20（30 左子樹的最大值）
遞迴刪除 20
用 20 取代 30
#### 參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
### 測驗1-3
使用指標 L 和 R 指向當前串列分割區間的兩端，當 L 和 R 尚未交會時，進行內部排序。
將最左側的節點設為 pivot，並讓指標 p 指向 pivot 的下一個節點，同時將 pivot.next 設為 NULL，以切斷與後續節點的連結。
指標 p 向右移動，遍歷剩餘節點：
若 p 指向的值大於 pivot，則將該節點加入 right 子串列。
若 p 指向的值小於 pivot，則將該節點加入 left 子串列。
完成遍歷後，得到三個部分：left、pivot 和 right，其對應的分割編號分別為 i、i+1 和 i+2。
優先對 right（分割編號 i+2）進行排序，直至右側排序完成後，將排序結果存入 result。
最後，開始對 left（分割編號 i）進行排序，直到所有部分都排序完成。
#### 研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
---
### 測驗2-1
這是一個基於 Linux 核心 list.h API 的 穩定版快速排序 (QuickSort)，適用於雙向鏈表 (list_head)。
它的主要目標是 保持相同數值的順序 (stable sorting)，並且不需要額外的數組存儲資料，而是直接操作鏈表。
##### 1. 終止條件
這是一個基於 Linux 核心 list.h API 的 穩定版快速排序 (QuickSort)，適用於雙向鏈表 (list_head)。
```
if (list_empty(head) || list_is_singular(head))
return;
```
當 head 是空的 (list_empty(head)) 或只有一個節點 (list_is_singular(head))，則已經是排序好的，不需要繼續遞迴。
##### 2. 初始化兩個子鏈表
```
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
這兩個鏈表分別用來存放：
list_less → 存放小於 pivot 的節點。
list_greater → 存放大於或等於 pivot 的節點。
##### 3. 選擇 Pivot
```
pivot = list_first_entry(head, struct listitem, list);
```
使用 list_first_entry() 取得 head 的第一個節點作為 pivot (基準值)。
##### 4. 移除 Pivot
```
list_del(&pivot->list);
```
將 pivot 暫時移除，避免影響排序過程。
##### 5. 遍歷 head，將節點移動到 list_less 或 list_greater
```
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);
}
```
這裡使用 Linux 核心 list.h 提供的 宏函數 來遍歷 head，並根據 cmpint() 的比較結果：
小於 pivot 的節點移動到 list_less。
大於或等於 pivot 的節點移動到 list_greater。
這裡保持穩定排序：
cmpint() 只在 < 0 時才移動到 list_less，其餘情況都留在 list_greater。
這樣相同數值的元素會維持它們原本的順序。
##### 6. 遞迴排序
list_quicksort(&list_less);
list_quicksort(&list_greater);
將 list_less 和 list_greater 各自再進行 list_quicksort()，直到排序完成。
##### 7. 合併排序結果
```
list_add_tail(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
排序完成後，將 list_less、pivot、list_greater 按順序合併回 head：
list_splice(&list_less, head);
先把小於 pivot 的數值加回 head，這樣 pivot 仍然位於中間。
list_add_tail(&pivot->list, head);
加回 pivot，讓它處於正確的位置。
list_splice_tail(&list_greater, head);
最後把大於或等於 pivot 的數值加回 head。
執行流程範例
假設我們有一組隨機排列的鏈表：
```
[3] → [1] → [4] → [1] → [5] → [9] → [2] → [6] → [5]
```
選擇 pivot：
pivot = 3
重新分配：
list_less = [1] → [1] → [2]
list_greater = [4] → [5] → [9] → [6] → [5]
遞迴排序 list_less：
pivot = 1
重新分配：
list_less = []
list_greater = [1] → [2]
排序 list_greater：
pivot = 1
list_less = []
list_greater = [2]
list_less 和 list_greater 併入 head
遞迴排序 list_greater：
pivot = 4
重新分配：
list_less = []
list_greater = [5] → [9] → [6] → [5]
排序 list_greater
pivot = 5
list_less = []
list_greater = [9] → [6] → [5]
排序 list_greater
pivot = 9
list_less = [6] → [5]
list_greater = []
排序 list_less
pivot = 6
list_less = [5]
list_greater = []
最終合併，排序好的鏈表：
```
[1] → [1] → [2] → [3] → [4] → [5] → [5] → [6] → [9]
```
#### 延伸問題1
> 解釋上方程式碼運作原理，改進 `random_shuffle_array` 也探討 `list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting
#### 延伸問題2
> 將程式碼整合進 [lab0](https://hackmd.io/@sysprog/linux2025-lab0) 提及的 `qtest`，並探討環狀雙向鏈結串列的排序效能，並善用 [perf](https://hackmd.io/@sysprog/linux-perf) 一類的效能分析工具，探討包含 Linux 核心 [list_sort](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 在內排序實作的效能表現並充分解釋
### 測驗2-2
#### 首先我們需要深入了解『clz2』函式
目標是計算一個 32 位元整數的 leading zeros，即數字前面有多少個 0
```
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};
```
mask 和 magic 是靜態常數陣列，應該是用來輔助計算的，
mask 似乎與 c 相關，影響低位元的遮罩 (0xFFFF >> mask[c])。
magic 可能是查表用來快速計算特定位數的前導零。
```
clz2(uint32_t x, int c)
```
這是計算 x 的前導零數的遞迴函式：
```
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
```
如果 x == 0 並且 c == 0，則 x 完全沒有有效位，直接回傳 32 (32 位元的數字全為 0)。
```
uint32_t upper = (x >> (16 >> c));
```
取得 x 的高位部分。
16 >> c 的作用是根據 c 的不同，把 x 逐步切割，初始時取前 16 位，然後 8 位，4 位，直到最小單元。
```
uint32_t lower = (x & (0xFFFF >> mask[c]));
```
取得 x 的低位部分，mask[c] 控制低位遮罩。
```
if (c == JJJJ)
return upper ? magic[upper] :2+ magic[lower];
```
c == JJJJ 時，這應該是基底情況 (停止遞迴的條件)。
若 upper 不為 0，則回傳 magic[upper] (透過查表獲取結果)。
否則，回傳 2 + magic[lower] (可能是補充偏移量)。
```
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
```
若 upper 不為 0，則繼續對 upper 遞迴計算 clz2(upper, c + 1)。
若 upper == 0，則計算 (16 >> c) + clz2(lower, c + 1)，表示高位部分全為 0，所以加上對 lower 的遞迴結果。
#### 程式實做
```
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;
```
其中我自己的疑惑是以及我認為的關鍵是
```
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
```
clz64(x) 代表 "Count Leading Zeros"，是計算 64 位元整數 x 前面有幾個連續的 0。
例如，若 x = 0b0000...00101（即只有低位是 5），那麼 clz64(x) 會是 61，因為前面有 61 個 0。
```
total_bits - 1 - clz64(x) 是什麼？
```
total_bits 在 64-bit 系統通常是 64（或是根據 context 決定）。
total_bits - 1 是 63。
這樣子 63 - clz64(x)，會得到 x 中最高位的 1 所在的 bit index。
也就是說：
如果 x = 0b000...01000（只有第 3 位是 1），那麼 clz64(x) 是 60（因為前面 60 個 0），shift 中間的運算是 63 - 60 = 3。
所以這裡得到的數字就是 x 的最高 set bit 的位元位置。
```
& ~1 是什麼？
```
~1 就是將 1 的位元取反，也就是 0x...FE（二進位最後一位變 0，其他都是 1）。
& ~1 意思是「將結果強制成偶數」：如果 shift 是奇數，扣掉 1；如果是偶數，保持不變。
舉例：
如果 shift = 5（0b101），shift & ~1 = 4（0b100）
如果 shift = 6（0b110），shift & ~1 = 6（0b110）
簡單說：shift & ~1 = 讓 shift 變成最接近小一點或相同的偶數。
或我稱為偶數地板函數？
```
m = 1ULL << shift 是什麼？
```
1ULL 是無號 64-bit 整數 1（ULL = unsigned long long）。
<< shift 是「左移 shift 位元」，也就是做 2^shift。
所以 m 變成 一個只有一個 1，且在 shift 這個位子上的數字。
#### 小結論
整體來說，這段程式碼的目的是：
找出 x 的最高 set bit 的位置
把那個位置修正成「最接近的偶數」
產生一個數字 m，這個數字只有那個偶數位上是 1，其餘是 0。
以上這個技巧很常在其他地方看到
＊位元優化（bit manipulation）
＊快速搜尋（例如，找最接近 power-of-2 的值）
＊樹狀結構（比如 radix tree、prefix sum tree
#### m 的用途
逐位逼近計算平方根
```
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
```
初始化 m 為
4^k
，從最高位開始測試。
每次迴圈：
b = y + m，嘗試將 m 加到 y 中。
y >>= 1，將 y 右移一位，準備更新平方根的估計值。
如果 x >= b，說明 b*b 不超過 x，則：
x -= b，更新剩餘數值。
y += m，將 m 加到 y 中，表示這一位是有效的平方根部分。
m >>= 2，每次 m 右移 2 位，因為平方數每次變化是
4^n
。
#### 範例
範例分析
```
x = 36 (0b100100)
```
初始化
```
clz64(36) = 58 // 36 的二進位是 `0000...00100100`
shift = 4 // 64 - 1 - 58 = 5 // 5 & ~1 = 4`
m = 16 (0b10000) // m = 1 << 4 = 16
y = 0
```
第一輪
```
b = y + m // 0 + 16 = 16
y >>= 1 // y 仍為 0
x >= b // (36 >= 16) → x -= 16 → x = 20
y += m // y = 16
m >>= 2 // m = 4
```
第二輪
```
b = y + m // 16 + 4 = 20
y >>= 1 // y = 8
x >= b // (20 >= 20) → x -= 20 → x = 0
y += m // y = 12
m >>= 2 // m = 1
```
第三輪
```
b = y + m // 12 + 1 = 13
y >>= 1 // y = 6
x < b // (0 < 13) → x 不變
m >>= 2 // m = 0（迴圈結束）
```
最後 y = 6，即 sqrt(36) = 6
### 測驗2-3
Sign in with Wallet
Connect another wallet