# 2025q1 Homework2 (quiz1+2)
contributed by < [`EricccTaiwan`](https://github.com/EricccTaiwan?tab=repositories) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## quiz1-1
### 解釋上方程式碼運作原理
#### `list_t` 和 `list_item_t`
結構體 `list_t` 和 `list_item_t` ，定義一個單向鏈結串列的資料結構 ，`list_item_t` 可以視為鏈結串列中的節點，包含 `value` 和指向下一個結構體(節點)的指標 `next`， `list_t` 代表整個鏈結串列，`head` 是指向此鏈結串列第一個 `list_item_t` 結構體的指標。
畫圖好難，還沒認真畫...
> 補
#### `list_insert_before`
這個函式和 [`hlist_add_before`](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.hlist_add_before) 作用相似，後者是針對 Linux Kernel 的 `hlist`(雙向鏈結)設計，可以在指定節點的前面插入新節點。
#### void hlist_add_before(struct hlist_node \*n, struct hlist_node \*next)
>add a new entry before the one specified
`list_insert_before` 是在單向鏈結串鏈中，在指定節點的前面插入新節點，走訪鏈結串列以找到 `@before` 所在位置的前一個節點，並將 `@item` 插入其中，透過節點 `list_item_t` 中的 `*next` 維持單向鏈結串列的關係。`@l` 是指向整個鏈結串列的指標，對應到 `list_t` 中的 `*head`。
#### 測試程式碼
`my_assert()` : 這個巨集會的 do-loop ，一旦 `test==false` 就會回傳 `message` 並結束。
`my_run_test()` : 持續測試 `test_list` 和計數器，一旦收到錯誤訊息，回傳並結束。
`static list_item_t items[N]` : 初始化 `items` 陣列，包含 `N` 個 `list_item_t` 節點。
`list_reset()` : 初始化所有節點的 value 和 next ，並將 `l.head` 設成 `NULL`，表示此鏈結串列為空，並回傳 `list_t *` (a pointer to `list_t`) 。
`test_list()` : 此測試函式若失敗回傳 `char *` (a pointer to char) ，測試成功則回傳 `NULL`。
#### test1: Test inserting at the beginning
> 補圖
首先建立一個 `value` 降冪排序的鏈結串列 (N-1, N-2, .... , 1, 0)。 `k` 初始化為 `N-1` 走訪 `l.heaad`，檢查此鏈結串列是降冪排序，此部份也就是在測試從頭節點操作 `list_insert_before` 是否正常。
#### test2: Test inserting at the end
> 補圖
清空鏈結串列，呼叫 `list_insert_before(&l, NULL, &items[i])` 根據此函數在 `@before` 的解釋，會將新的節點新增到鏈結串列的尾端，最後形成一個升冪排序的鏈結串列；並從 `k = 0` 開始確保節點的值是由小到大。
#### test3: Reset the list and insert elements in order (i.e. at the end)
跟 test2 差不多，再次確認從 `NULL` 插入是否正常運作。如果三個 test 都沒問題，回傳 `NULL` 。
`test_suite()` : `my_run_test` 會執行 `test_list()`，如果有錯會直接回傳 `message`；反之，回傳 `NULL` 。
`main()` : 可以看到關鍵 `char *result = test_suite();` ，若回傳為 `result == NULL` 就代表沒問題，並輸出測試次數和 `!!result`。
至此，邏輯梳理的差不多了，但 `main` 回傳的 `!!result` 是第一次看到，根據 C99 規格書的定義 (6.5.3.3.5)，當運算元 (operand) 非0，執行後 logical NOT (`!`) 的結果就是 0 。回到 `result = NULL` 的情境，根據 C99 (6.3.2.3))，`NULL` 是透過巨集
```c
#define NULL ((void *)0)
```
把 `0` 強制轉型成 `null pointer`，但理解上等同於 0 ; 因此, 當 `result = NULL` ，
```c
// 第一次 logical NOT
!result = !NULL = !(void *)0 = 1
// 第二次 logical NOT
!!result = !(!result) = !1 = 0
```
如此操作，就能將 `NULL` 轉換為 0 了。
#### C99 (6.5.3.3.5)
>The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int.
The expression !E is equivalent to (0==E).
#### C99 (6.3.2.3)
> 55\) The macro NULL is defined in <stddef.h> (and other headers) as a null pointer constant; see 7.17.
#### list_insert_before
```c
list_item_t **p; // pointer to pointer
// for (p = AAAA; *p != BBBB; p = CCCC)
for (p = &l->head; *p != before; p = &(*p)->next);
```
> 補圖
運用指針的指針技巧，尋找 `before` 節點，首先宣告 `**p` 指向 `l->head`，也就是結構體 `list_t` 中的 `*head` ，而這個指針 `head` 指向由 `list_item_t` 節點所構成的鏈結串列。 接著讓 `p` 持續向右移動，當 `*p == before` 時，代表此時 `**p` 是指向前一個節點的 `*next` ，因此 `*p = item` ，便能將 `item` 插到 `before` 前，再讓 `item->next` 指向 `before` ，以維持鏈結串列的關係，透過指針的指針，便不需要考慮像是頭節點的特判，這樣才有 good taste 。
### 在現有的程式碼基礎上，撰寫合併排序操作
## quiz1-2
### 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
`block_t` : 透過這個結構體，實現 BST ，每個節點都代表一個記憶體區塊。
`find_free_tree` : Locate the pointer to the target node in the tree
`find_predecessor_free_tree` : Find the in-order predecessor
`remove_free_tree` : 從 BST 中刪除節點，並確維持 BST 的結構。此函式的主要邏輯，
* 無子節點 : 直接刪除 `*node_ptr = NULL;`
* 只有一個子節點 : 指標的指標由指向父節點，轉成指向子節點。
* 兩個子節點 : 就是主要的處理部份，透過 `find_free_tree` 找到目標位置，並宣告 `**node_ptr` 指向目標位置，`**pred_ptr` 指向左子樹，接著要找出 `the rightmost node in the left subtree` ，找出左子樹中最大的節點，下方的 while-loop 便是在實現 `find_predecessor_free_tree` 。
```c
while ((*pred_ptr)->r)
pred_ptr = &((*pred_ptr)->r);
```
#### find_free_tree
`block_t **find_free_tree(block_t **root, block_t *target)`
這個函式也是運用了指標的指標的技巧，實現二分搜索，宣告`block_t **cur = root`，用 `cur` 來走訪這個 BST ，若當前節點的記憶體大小與目標所求一樣，直接返回即可，如果小於目標大小，則讓指針向右子樹移動，反之，移動到左子樹，並繼續從新的根節點開始遞迴尋找。
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
block_t **cur = root;
while (*cur)
{
if ((*cur)->size == target->size)
return cur;
else if ((*cur)->size < target->size)
cur = &(*cur)->r;
else
cur = &(*cur)->l;
}
return NULL;
}
```
#### find_predecessor_free_tree
`block_t *find_predecessor_free_tree(block_t **root, block_t *node)`
因為是找 `node` 的 in-order predecessor，因此如果 `node` 的左子樹存在，回傳左子樹最右邊的節點即可；但如果 `node` 沒有左子樹，則需要從 `root` 開始找，宣告 `block_t *cur = *root`，因為 BST 的特性，所以如果`cur->size < node->size` ，向右邊子樹移動，否則，向左子樹移動，同時也因為左子樹為空，所以當 `cur` 移動到目標節點，會進到 else-statement，`cur = NULL` 並跳出 while 迴圈。
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
if (!root || !node || !*root)
return NULL;
if (node->l)
{
block_t *pred = node->l;
while (pred->r)
pred = pred->r;
return pred;
}
block_t *pred = NULL;
block_t *cur = *root;
while (cur)
{
if (cur->size < node->size)
{
pred = cur;
cur = cur->r;
}
else
cur = cur->l; // NULL
}
return pred;
}
```
If the predecessor is the immediate left child.
else
### 參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
## quiz1-3
### prob1-3-1
> 解釋上述程式碼運作原理
> 再來就是利用 begin 與 end 作為堆疊，去儲存尚未排列好的序列，由於 pivot 目前在 array\[3] 的位置，所以就會有一組 begin 跟 end 為 0~2、一組為 4~5。之後會重複上述的行為，一次會以 5 為 pivot，另一次則會以 2 為 pivot，就可以得到排序好的陣列。
前面都還看的懂，到了這邊直接迷失，再接著往下看到 **操作鏈結串列的圖解**，透過 `L` `R` 指標，把比 `pivot` 小的 `node` 加進 `left` 的串列中，反之加到 `right` 的串列，最後 `begin[0]` 和 `end[0]` 會指向 `left` 串列的頭尾，`begin[1]` 和 `end[1]` 指向 `pivot`, `begin[2]` 和 `end[2]` 指向 `right` 的頭尾，因為 `i+=2`，所以會優先排序右側的鏈結串列 (大於 `pivot` 值)，排序完成才換左側。
一開始有點疑惑為何搬動的節點 `next` 沒有改變指向，看到 `list_add(n->value > value ? &right : &left, n);` 才又去看了 Linux Kernel API, 會把`&left / &right` 的 `n` 的後方，並改變指向維持雙向鏈結的關係。
```c
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
因此在 while 迴圈中，用 `*n` 指標指向當前要移出原鏈結串列的節點，所以 `p = p->next` 指標持續右移，以及用 `begin` 指向鏈結串列的開頭，`end` 則是指向結尾，因此 `end[i] = list_tail(&left)` 和 `end[i+2] = list_tail(&right)`。
```c
p = p->next; // CCCC
end[i] = list_tail(&left); // DDDD
end[i + 2] = list_tail(&right); // EEEE
```
接著使用 `list.h` 的標頭檔改寫 quicksort ，`node_t` 結構體透過 `list_head` 的結構體實現雙向鏈結串列，並用 `value` 存取當前節點的值。
```c
struct list_head {
struct list_head *next, *prev;
};
```
`list_construct()` : 建立新的節點，並插到鏈結串列的後方。
`list_free()` : 釋放記憶體 。
`list_is_ordered()` : 用 `list_for_each_entry` 走訪整個鏈結串列，並比較當前結點是否小於前一個節點。
`shuffle()` : shuffle array 。
`list_length()` : 計算鏈結串列的長度。
`list_tail()` : 走訪鏈結串列，持續右移，回傳指向尾端節點的 `list_head *` 指標。
`rebuild_list_link()` : 用來重建雙向鏈結串列的 `prev` 指標，用 while 迴圈走訪鏈結串列，直到 `node == NULL` 中止。
```
H <=> [A] <=> [B] <=> [C] <=> [D] -> NULL
```
此時已經建構好頭尾節點除外，中間節點的雙向關係，但頭尾的關係還沒建立。當前的 `prev` 在尾端 (`NULL`) 的前一個節點，再將 `prev->next` 指向 `head`，和 `head->prev` 指向 `head` ，以建立頭尾的雙向關係。
```c
prev->next = head;
head->prev = prev; // GGGG
```
```
H <=> [A] <=> [B] <=> [C] <=> [D]
↑ ↓ ↑ ↓
└─────────────────────────────┘
```
#### quick_sort
這部份的改寫是根據 [〈Optimized QuickSort — C Implementation (Non-Recursive)〉](https://alienryderflex.com/quicksort/) ，也就是[第一周測驗](https://hackmd.io/@sysprog/linux2025-quiz1)的圖解程式碼，一開始將 `begin[0]` 指向 list 的頭節點，接著是 `while(i>=0)` 迴圈，如果左右指標指向的節點不同，開始進行第一次的移位，宣告 pivot 和其 value ，`while(p)` 對於每個節點進行判斷，如果當前節點的 `n_value > value` ，`n->next = right` 加到 `right` 的前方，反之，加到 `left` 的前方。結束分割後，用 `begin[i]` 指向 `left`, `begin[i+1]` 指向 `pivot`, `begin[i+2]` 指向 `right`。 若左右指標代表同一個節點，將當前的節點加入 `result` 當中。最後 `list` 的頭指針指向 `result` ，並用 `rebuild_list_link` 重新建立節點間雙向關係。
```c
value = list_entry(pivot, node_t, list)->value; // HHHH
int n_value = list_entry(n, node_t, list)->value; // IIII
begin[i + 1] = pivot; // JJJJ
begin[i + 2] = right; // KKKK
```
### prob1-3-2
> 研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
## quiz2-1
### prob2-1-1
> 解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
`UINT16_C` 是我第一次見到的巨集，點開後才發現它透過巨集來定義 `unsigned int`。`UINT8_C` 和 `UINT16_C` 的展開結果與輸入值相同，因為編譯器會自動將其轉換為 `uint8_t` 和 `uint16_t`。然而，`UINT32_C` 則明確使用 `c ## U` 來確保常數為 `unsigned`，例如 `UINT32_C(1234)` 會展開為 `1234U`，這樣就能正確表示 `uint32_t` 型別的數值。
```c
// #include <stdint.h>
#define UINT8_C(c) c
#define UINT16_C(c) c
#define UINT32_C(c) c ## U
```
`getnum()` : 可以看出是回傳一個 8-bit 的值，但用意看不太懂，問了 ChatGPT 並得到亂數產生的回覆，是[線性同餘法 (Linear congruential generator, LCG) ](https://youtu.be/kRCmR4qr-hQ)的變體，主要的功能是產生偽隨機數，然而，在閱讀程式碼時，我注意到 `s1` `s2` 和 `s3` 這三個變數都被宣告為 `static`，不太明白其用意，因此查閱規格書 **C99 (6.2.4.3)** ，了解到 `static` 變數具有靜態儲存期 (static storage duration) ，代表會在程式啟動時只初始化一次，並在整個程式執行期間保持其值，這樣的設計確保了 `getnum()` 在每次呼叫時，都能基於先前的狀態來計算新值，而不會在每次函式呼叫時重新初始化變數，導致回傳值始終相同，從而失去隨機性的意義。所以這個函式的用意就是產生 8-bit 的隨機數。
#### C99 (6.2.4.3)
> An object whose identifier is declared with external or internal linkage, or with the storage-class specifier static has static storage duration. Its lifetime is the entire execution of the program and its stored value is initialized only once, prior to program startup.
`get_unsigned16()` : 根據剛剛的邏輯，這個函式是用來生成 16-bit 的隨機數。可以看到使用了 for 迴圈，因為宣告變數 `x` 為 16-bit 的無符號整數，因此 `sizeof(x) = 2` ，會將所以經過兩次 for 迴圈，便能得到 16-bit 的隨機數。
```c
x = 0x0000
i=1 :
x <<= 8 -> 0x0000 (假設 getnum() = AA)
x |= 0xAA -> 0x00AA
i=2 :
x <<= 8 -> 0xAA00 (假設 getnum() = AA)
x |= 0xBB -> 0xAABB
```
`random_shuffle_array()` : 這個函式的作用是對陣列進行隨機洗牌 (shuffle)，透過隨機生成的 index `j` ，將 `i` 和 `j` 的元素進行互換。然而，可以看到程式中的註解， WARNING biased shuffling ，是因為 `get_unsigned16() % (i + 1)` 取模的方式會造成某些 index 的選取機率不同，所導致的偏差。
若對隨機性要求較高，應考慮改用 Fisher-Yates 洗牌演算法來確保真正均勻的隨機排列。
#### list_quicksort
首先初始話兩個鏈結串列，分別存放比 pivot 小和比 pivot 大的節點，接著取第一個節點為 pivot 並將其移出，接著 `list_for_each_entry_safe` 走訪鏈結串列，如果當前結點的值比 pivot 小，移動至 `list_less` 的尾端，反之，移動至 `list_greater` 。 走訪結束，對 `list_less` 和 `list_greater` 進行快速排序，並將 `pivot` 、 `list_less` 和 `list_greater` 合併，先將 `pivot` 加回 `head` 的後方，接著將 `list_less` 置於 `head` 所指向的鏈節串列頭節點的前方，`list_greater` 則是放入 `head` 所指向的鏈節串列尾端的的後方。
```c
pivot = list_first_entry(head, struct listitem, list); // AAAA
list_del(&pivot->list); //BBBB
list_move_tail(&item->list, &list_greater); // CCCC
list_add_tail(&pivot->list, head); // DDDD
list_splice(&list_less, head); // EEEE
list_splice_tail(&list_greater, head); // FFFF
```
#### `lise_move_tail()` vs `list_move()`
參考 [Linux Kernel API](https://docs.kernel.org/core-api/kernel-api.html) 對於兩個 API 的功能解釋，
`list_move_tail(&item->list, &list_less)` : 將 `item` 移動到 `list_less` 的尾端，因此相同數值的元素能保持原始順序。
`list_move(&item->list,&list_less)` : 將 `item` 移動到 `list_less` 的開頭，會導致相同數值的相對順序顛倒，因此不滿足 stable sort 。
### prob2-1-2
> 將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋
## quiz2-2
### prob2-2-1
> 解釋上述程式碼，並探討擴充為 $\lceil \sqrt{x}) \rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
`clz2` : 計算 leading zeros 的個數 ，如果 x 和 c 都是 0 ，直接回傳 32 (代表 32 個 0 ) ， 計算上半部 (upper) 和下半部 (lower) ，並由 `mask[] = {0, 8, 12, 14}` 決定遮罩的大小，
> 反了
當 `c==3` 回傳，`return upper ? magic[upper] : 2 + magic[lower];` ，
```
10 | 00 => upper = 2 => return magic[2] = 0
01 | 00 => upper = 1 => return magic[1] = 1
00 | 10 => upper = 0 => return 2+ magic[2] = 2
00 | 01 => upper = 0 => return 2+ magic[1] = 3
00 | 00 => upper = 0 => return 2+ magic[0] = 4
```
最後遞迴計算，如果 upper != 0 ，則遞迴 `clz2(upper,c+1)` ，因為 leading zero 會在 upper 就結束，所以與 lower 無關；如果 upper = 0 ，則計算當前區間 `16>>c` 的零個數，再遞迴呼叫 `clz2(lower,c+1)`，計算 lower 的 leading zeros 個數。
```c
static const int mask[] = {0, 8, 12, 14}; // GGGG
static const int magic[] = {2, 1, 0, 0}; // HHHH, IIII
if (c == 3) // JJJJ
return upper ? magic[upper] : 2 + magic[lower]; // KKKK
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1); // LLLL
```
`clz64` : 如果高位不為 0 ，則計算 `clz32(high 32 bits)`；如果高 32 位為 0 ，計算 `clz32(low 32 bits) + 32 `，因為高 32 位都是 0 。
`sqrti` : 計算 64-bit 無符號整數的整數平方根，類似於 `floor(sqrt(x))` ，首先計算 `total_bits - 1 - clz64(x)` 代表 MSB 的位置，同時根據註解 `Rounding that index down to an even number` ，因此對 `~1` 做 bitwise AND，確保 shift 是偶數 ，`m` 代表的是從最高的有效為開始，如同下方從 $m=4$ 開始，逐步降低逼近平方根。
以 $N^2 = 17$ 為例，$N^2 = (17)_2 = (10001)_2=(b_4\times 2^3 + b_0\times2^0)$，最高位元是 $b_4$ ，所以從 $m=4$開始，
* $m=4$ ，$P_4^2 = a_4^2=(2^4)^2=256>17$，所以 $P_4=P_5$ 且 $a_4=0$ 。
* $m=3$ ，$P_3^2 = (a_4+a_3)^2=(2^3)^2=64>17$，所以 $P_3=P_4$ 且 $a_3=0$ 。
* $m=2$ ，$P_2^2 = (a_4+a_3+a_2)^2=(2^2)^2=16<17$，所以 $P_2=P_3+2^2$ 且 $a_2=2^2$ 。
* $m=1$ ，$P_1^2 = (a_4+a_3+a_2+a_1)^2=(2^2+2^1)^2=36>17$，所以 $P_1=P_2$ 且 $a_1=0$ 。
* $m=0$ ，$P_0^2 = (a_4+a_3+a_2+a_1+a_0)^2=(2^2+2^0)^2=25>17$，所以 $P_0=P_1$ 且 $a_0=0$ 。
故 $N=P_0=P_1=P_2=a_2=2^2=4$ ，因此 $17$ 的整數平方根為 $4$。
但有點看不太懂了...TBD
```c
int shift = (total_bits - 1 - clz64(x)) & ~1; // MMMM
y >>= 1; // NNNN
m >>= 2; // PPPP
```
### prob2-2-2
> 參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly
### prob2-2-3
> 參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能
## quiz2-3
Sign in with Wallet
Connect another wallet