2025q1 Homework2 (quiz1+2)

contributed by < yy214123 >

雖然這是我第二次修這門課，但我深刻意識到自己仍有許多不足。目前的隨堂測驗幾乎都拿了 0 分，在有限的時間內，我仍無法迅速找出正確答案，這表示我還需要更加努力。

相較於去年，有時我會依賴 ChatGPT 來幫助解題；但今年，我決定誠實面對自己的能力與弱點，缺什麼就補什麼。

2025 q1 第 1 週測驗題

測驗 1

根據 list_insert_before 的描述，會有下列幾種插入情況：

• 情況 1

list_insert_before(list, A, new);
此時新插入的節點會成為串列的新頭部節點：

• 情況 2

list_insert_before(list, C, new);
此時會在節點 B 與 節點 C 中間插入新節點：

• 情況 3

list_insert_before(list, NULL, new);
此時新插入的節點會成為串列的最尾端節點：

我覺得這裡使用的串列和 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 節點。

/* 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，這邊可以看到傳入兩個參數：

block_t **find_free_tree(block_t **root, block_t *target){};

首先要考慮 root 為 NULL 及 target 是 root 的情況：

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 比當前節點大，則往右子樹遞迴。
• 若小於或等於（我預設大小相等時插入到左子樹），則往左子樹遞迴。

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 迴圈實現節點的搜尋與指標更新。

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，這邊可以看到傳入兩個參數：

block_t *find_predecessor_free_tree(block_t **root, block_t *node){}

由於這個函式的主要用途是「作為驗證工具」，並不是實際邏輯的一部分，因此我們可以將它視為一個用來比對結果的對照組。

在這樣的前提下，它的角色比較像是「我們在建構測試用的 tree 時，透過紙筆追蹤或視覺化方式，事先知道某個節點的 predecessor 是誰」，並將該節點直接作為回傳值。

這樣做的目的，是為了驗證填空區的 while 迴圈是否正確地找出了與我們預期一致的 predecessor。

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    return known_predecessor_pointer;
}

測驗 3

2025 q1 第 2 週測驗題

測驗 1

首先會初始化兩個新的串列：

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，則需要對該數進行分割。接下來將函式的回傳部分展開為更易於理解的形式：

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 陣列元素即可。

另一個情況是：

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