2025q1 Homework2 (quiz1+2)

contributed by < EricccTaiwan >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

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 作用相似，後者是針對 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 是透過巨集

#define NULL ((void *)0)

把 0 強制轉型成 null pointer，但理解上等同於 0 ; 因此, 當 result = NULL ，

// 第一次 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

list_item_t **p; // pointer to pointer

// for (p = AAAA; *p != BBBB; p = CCCC)
for (p = &l->head; *p != before; p = &(*p)->next);

補圖

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

運用指針的指針技巧，尋找 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 。

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 ，若當前節點的記憶體大小與目標所求一樣，直接返回即可，如果小於目標大小，則讓指針向右子樹移動，反之，移動到左子樹，並繼續從新的根節點開始遞迴尋找。

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 迴圈。

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.

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

else

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

參閱 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 的後方，並改變指向維持雙向鏈結的關係。

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)。

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 存取當前節點的值。

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 ，以建立頭尾的雙向關係。

prev->next = head;
head->prev = prev; // GGGG

H <=> [A] <=> [B] <=> [C] <=> [D]
↑ ↓                           ↑ ↓
 └─────────────────────────────┘

quick_sort

這部份的改寫是根據〈Optimized QuickSort — C Implementation (Non-Recursive)〉，也就是第一周測驗的圖解程式碼，一開始將 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 重新建立節點間雙向關係。

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 型別的數值。

// #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) 的變體，主要的功能是產生偽隨機數，然而，在閱讀程式碼時，我注意到 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 的隨機數。

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 所指向的鏈節串列尾端的的後方。

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 對於兩個 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

解釋上述程式碼，並探討擴充為
$⌈ \sqrt{x}) ⌉$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

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 個數。

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} \times 2^{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

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 語言實作，並比較不同手法的整數開平方根效能

2025q1 Homework2 (quiz1+2)

quiz1-1

解釋上方程式碼運作原理

list_t 和 list_item_t

list_insert_before

void hlist_add_before(struct hlist_node *n, struct hlist_node *next)

測試程式碼

test1: Test inserting at the beginning

test2: Test inserting at the end

test3: Reset the list and insert elements in order (i.e. at the end)

C99 (6.5.3.3.5)

C99 (6.3.2.3)

list_insert_before

在現有的程式碼基礎上，撰寫合併排序操作

quiz1-2

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

find_free_tree

find_predecessor_free_tree

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

quiz1-3

prob1-3-1

quick_sort

prob1-3-2

quiz2-1

prob2-1-1

C99 (6.2.4.3)

list_quicksort

lise_move_tail() vs list_move()

prob2-1-2

quiz2-2

prob2-2-1

prob2-2-2

prob2-2-3

quiz2-3

Read more

2025 年 Linux 核心設計課程作業 - Eric

2025q1 Homework1 (lab0)

2025q1 Homework1 (ideas)

C語言 - LeetCode筆記

`list_t` 和 `list_item_t`

`list_insert_before`

void hlist_add_before(struct hlist_node n, struct hlist_node next)

`lise_move_tail()` vs `list_move()`