# 2025q1 Homework2 (quiz1+2)
contributed by < `yy214123` >
雖然這是我第二次修這門課，但我深刻意識到自己仍有許多不足。目前的隨堂測驗幾乎都拿了 0 分，在有限的時間內，我仍無法迅速找出正確答案，這表示我還需要更加努力。
相較於去年，有時我會依賴 ChatGPT 來幫助解題；但今年，我決定誠實面對自己的能力與弱點，缺什麼就補什麼。
## 2025 q1 第 1 週測驗題
### 測驗 `1`
```graphviz
digraph linked_list {
rankdir=LR; // 水平顯示
node [shape=record, style=rounded];
head [shape=circle, label="head", style=filled, fillcolor=lightblue];
A [label="A"];
B [label="B"];
C [label="C"];
null [shape=plaintext, label="NULL"];
head -> A;
A -> B;
B -> C;
C -> null;
}
```
根據 `list_insert_before` 的描述，會有下列幾種插入情況：
- [ ] 情況 1
`list_insert_before(list, A, new);`
此時新插入的節點會成為串列的新頭部節點：
```graphviz
digraph linked_list {
rankdir=LR; // 水平顯示
node [shape=record, style=rounded];
head [shape=circle, label="head", style=filled, fillcolor=lightblue];
new [label="new"];
A [label="A"];
B [label="B"];
C [label="C"];
null [shape=plaintext, label="NULL"];
head -> new;
new -> A;
A -> B;
B -> C;
C -> null;
}
```
- [ ] 情況 2
`list_insert_before(list, C, new);`
此時會在節點 `B` 與 節點 `C` 中間插入新節點：
```graphviz
digraph linked_list {
rankdir=LR; // 水平顯示
node [shape=record, style=rounded];
head [shape=circle, label="head", style=filled, fillcolor=lightblue];
new [label="new"];
A [label="A"];
B [label="B"];
C [label="C"];
null [shape=plaintext, label="NULL"];
head -> A;
A -> B;
B -> new;
new -> C
C -> null;
}
```
- [ ] 情況 3
`list_insert_before(list, NULL, new);`
此時新插入的節點會成為串列的最尾端節點：
```graphviz
digraph linked_list {
rankdir=LR; // 水平顯示
node [shape=record, style=rounded];
head [shape=circle, label="head", style=filled, fillcolor=lightblue];
new [label="new"];
A [label="A"];
B [label="B"];
C [label="C"];
null [shape=plaintext, label="NULL"];
head -> A;
A -> B;
B -> C;
C -> new;
new -> null;
}
```
我覺得這裡使用的串列和 lab0 之間最大的不同在於 `head` 節點。在這裡，`head` 只是一個指向第一個節點 `A` 的指標，而在 `lab0` 中的雙向環狀鍊結串列，`head` 節點本身也擁有 `next` 和 `prev` 這兩個指標，因此兩者的設計角度有所不同。
使用間接指標來實現遍歷佇列的節點，首先，間接指標所儲存的值是另一個指標的記憶體地址，因此可以用 `head` 指標的記憶體地址來初始化間接指標（假設叫做 `pp`）。此時的結構如下
| 記憶體位址 | 變數名稱 | 值 |
| -------- | -------- | -------- |
| 0x0000 | `pp` | head 的記憶體位址（即0x0001） |
| 0x0001 | `head` | Node A 的記憶體位址（即0x0002） |
| 0x0002 | `Node A` | value 及 next（0x0003）|
| 0x0003 | `Node B` | value 及 next（0x0004） |
| 0x0004 | `Node C` | value 及 next（NULL） |
接著進行串列的走訪。此處顯然無法直接使用 `pp = pp->next`來訪問下一個節點，因為 `pp` 並不是一個結構體，因此沒有名為 `next` 的成員。我們可以使用 你所不知道的 C 語言: linked list 和非連續記憶體 中提及的間接指標技巧，即每次將 `pp` 指向當前節點的 `next` 指標所在的記憶體地址。根據上述記憶體表格，這相當於將下一個節點（例如節點 `A` 的 `next` 欄位）的記憶體地址存入 `pp` 中。此時，透過對 `pp` 進行解引用操作（即 `*pp`），即可取得下一個節點的位址（例如節點 `B`），如此反覆即可實現完整的串列走訪。
不過，根據題目需求，我們必須在特定位置插入新的節點，因此需要設定適當的中止條件。前面已經提到，`*pp` 指向的是下一個節點的位址。若 `*pp` 恰好為指定的插入位置（`before`），此時 `pp` 即指向前一個節點的 `next` 指標。掌握此概念後，節點插入就非常直觀了：只需將 `*pp` 設為新插入節點，再將新插入節點的 `next` 指向原先 `*pp` 所表示的節點，即可完成插入操作。
### 測驗 `2`
程式一開始宣告了一個間接指標 `node_ptr`，並將其初始化為樹狀結構中 `root` 節點的記憶體位址。因此，對 `node_ptr` 解引用一次，即可取得對應的 `root` 節點。
```c
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
```
根據註解上下文可推測，題目要求填空處的目的在於尋找左子樹的最右側節點。因此，再次宣告一個間接指標 `pred_ptr`。此處與第一題採用的方法本質相同，差別僅在資料結構的不同：`pred_ptr` 會存放當前節點內 `r` 指標的記憶體位址（而在第一題是 next 指標）。透過對 `pred_ptr` 進行解引用，即可取得該節點的右子節點，然後持續往右側進行走訪，直至最右端的節點。因此，`while` 迴圈的中止條件即為檢查當前節點的右子節點是否為 `NULL`，若非 `NULL`，則持續走訪。
此處有兩個 helper function 還沒實作完成：
`find_free_tree`： 在 BST 中找到指定節點的位置
`find_predecessor_free_tree`：找出一個節點的 in-order predecessor，也就是左子樹裡的最大節點
> 這個會用來驗證 `while` 找出的節點是否正確。
首先先實作 `find_free_tree`，這邊可以看到傳入兩個參數：
```c
block_t **find_free_tree(block_t **root, block_t *target){};
```
首先要考慮 root 為 NULL 及 target 是 root 的情況：
```diff
block_t **find_free_tree(block_t **root, block_t *target)
{
+ if(!*root)
+ return NULL;
+ if(*root == target)
+ return root;
}
```
接下來，根據 binary search tree 的特性，我們需依據 target->size 與當前節點大小比較：
* 若 target 比當前節點大，則往右子樹遞迴。
* 若小於或等於（我預設大小相等時插入到左子樹），則往左子樹遞迴。
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
if(!*root)
return NULL;
if(*root == target)
return root;
if (target->size > (*root)->size)
find_free_tree(&(*root)->r,target);
else
find_free_tree(&(*root)->l,target);
}
```
上面的方法使用的是遞迴方式，`&(*root)->r` 及 `&(*root)->l` 會指向上一層節點的 `r` 及 `l` 指標，下一次遞迴時解引用就會是對應的右子節點或左子節點，此外，也可以使用迴圈版本來實作，以避免遞迴的額外堆疊開銷。邏輯上完全相同，只是改用 `while` 迴圈實現節點的搜尋與指標更新。
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
while(*root){
if(*root == target)
return root;
if (target->size > (*root)->size)
root = &(*root)->r;
else
root = &(*root)->l;
}
return NULL;
}
```
接著來實作 `find_predecessor_free_tree`，這邊可以看到傳入兩個參數：
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node){}
```
由於這個函式的主要用途是「作為驗證工具」，並不是實際邏輯的一部分，因此我們可以將它視為一個用來比對結果的對照組。
在這樣的前提下，它的角色比較像是「我們在建構測試用的 tree 時，透過紙筆追蹤或視覺化方式，事先知道某個節點的 predecessor 是誰」，並將該節點直接作為回傳值。
這樣做的目的，是為了驗證填空區的 while 迴圈是否正確地找出了與我們預期一致的 predecessor。
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
return known_predecessor_pointer;
}
```
### 測驗 `3`
## 2025 q1 第 2 週測驗題
### 測驗 `1`
首先會初始化兩個新的串列：
```c
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
> 一個用來存放比 `pivot`小的元素，另一個用來存放比 `pivot` 大的元素。
以第一個元素作為 `pivot`，這跟 lab0 一樣內嵌於其他結構體，所以需要使用對應的 `container_of` 來取得結構體內的數值成員，才能進行比較，並先將 `pivot` 從串列中移除。接著走訪整個串列，以 `pivot` 作為基準，決定各元素要放入哪一個新串列（`list_less` 和 `list_greater`），然後對這兩個新串列進行遞迴。遞迴完成後，首先將原本移除的 `pivot` 插入串列中，並在其左側插入遞迴完成的 `list_less` 串列，右側插入遞迴完成的 `list_greater` 串列，這樣便完成了排序的實作。
### 測驗 `2`
首先需要判斷輸入的數是否完全為 `0`，若輸入為 `0`，則不需要進行繁瑣的運算，可直接回傳 `32`；若不是 `0`，則需要對該數進行分割。接下來將函式的回傳部分展開為更易於理解的形式：
```c
return upper ? magic[upper] : KKKK + magic[lower];
//展開
if (upper)
return magic[upper];
else
return KKKK + magic[lower];
```
只有當遞迴執行到 `upper` 和 `lower` 都剩下 `2bits` 時，這樣的情況才會成立。考慮到 `2 bits` 共有四種組合：
> 00：（lower 有兩個 leading zero）
> 01：（lower 有一個 leading zero）
> 10：（lower 沒有 leading zero）
> 11：（lower 沒有 leading zero）
因此當 `upper` 為 `00` 時，`lower` 也可能會被考量進去，這就是 `magic` 陣列各個索引值的來源。反之，當 `upper` 不是 `00` 時，則不需要考慮 `lower` 的組成，直接返回 `lower` 的組成並找到對應的 `magic` 陣列元素即可。
另一個情況是：
```c
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
//展開
if (upper) {
return clz2(upper, c + 1);
} else {
return (16 >> c) + clz2(lower, c + LLLL);
```
這裡的道理也是一樣，只是這次 `upper` 和 `lower` 不是 2 bits，以 4bits 為例，假設 `upper` 為 0000，此時 `lower` 也可能貢獻 leading zero，透過將 16 右移分割次數來將 `upper` 的四個 leading zero 和 `lower` 的 leading zero 加總在一起。
以下舉例：
假設 0000 0100 0000 0000 0000 0000 0000 0000，先分割成兩個最大的 `upper` 與 `lower`：
> upper = 0000 0100 0000 0000
> lower = 0000 0000 0000 0000
此時 upper 非 0，會執行 `return clz2(upper, c + 1);`，從這邊可以看到 `lower` 的部分就不會再理他了，因為無論其組成方式如何，都不會貢獻 leading zero。
接著再分割 0000 0100 0000 0000：
> upper = 0000 0100
> lower = 0000 0000
同理，`lower` 也不再貢獻 leading zero，專注於 `upper` 即可，接著再分割 0000 0100
> upper = 0000
> lower = 0100
此時 `upper` 是 0，代表 `lower` 有貢獻 leading zero 的可能，所以會執行 `return (16 >> c) + clz2(lower, c + LLLL);`，此時是第三輪所以 c = 2，16 >> 2 = 4，這恰好就是 `upper` 的 4 個 leading zero。接著分割 `lower` 0100：
> upper = 01
> lower = 00
此時 c = 4，即先前提到 upper 與 lower 皆 2 bits 的情況，同時 upper 非 0，會 return magic[upper]（即 1），這是 `clz2(lower, c + LLLL)` 的結果，而上一層會回傳 `return (16 >> c) + clz2(lower, c + LLLL)`（即 4 + 1），所以最後得到共 5 個 leading zero。
這個演算法本質上是一種在位元層面的二分搜尋法，每次將待檢查的位元區間分成兩部分，先檢查上半部是否包含非零位元，若有則在上半部繼續搜尋，否則跳過上半部並累加其位元數後在下半部尋找。這種不斷縮小搜尋範圍、定位目標位元（第一個 1）的方式，就和二分搜尋在有序資料中查找目標元素的策略非常相似。
接著是開平方根實作，`sqrti` 函式的參數是一個 64 bits 無號數，也可以將其拆成 upper 與 lower，再用先前說明的遞迴來找出 leading zero 總數。有了 leading zero，我們也可以反推其最高位元 set bit 之索引。
我還無法理解這邊的後續實作邏輯
### 測驗 `3`
Sign in with Wallet
Connect another wallet