2025q1 Homework2 (quiz1+2)

contributed by < salmoniscute >

Q1-1

兩個巨集測試框架：
my_assert(test, message)
參數 test 是一個 expression，為 true 才會通過測試。
參數 message 是當 test 為 false 時所回傳的字串。

my_run_test(test)
參數 test 是一個回傳 char * 的函式，當測試成功時回傳 NULL，失敗時回傳錯誤訊息字串。
測試失敗的話可以馬上回報錯誤資訊

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)

為什麼要使用 do { ... } while (0)？這段程式碼看起來只需要執行一次，卻使用了 do-while 這種結構，乍看之下或許有些奇怪，但在 C 語言的巨集中相當常見。
我去看了相關教材〈你所不知道的 C 語言：前置處理器應用篇〉其中提到這種寫法的主要目的，是為了避免 dangling else 問題。
舉例來說，以下定義了一個不使用 do { ... } while (0) 的巨集：

#define BAD_ASSERT(test, message) if (!(test)) return message

如果直接在 test_list 函式內新增：

BAD_ASSERT(list_size(&l) == 0, "Size error");

這樣執行程式是不會有問題的。
然而，如果改成以下寫法：

int some_condition = 0;
if (some_condition)
    BAD_ASSERT(list_size(&l) == 1, "Size error");
else
    printf("Some condition is false\n");

這段程式碼經過巨集展開後會變成：

int some_condition = 0;
if (some_condition)
    if (!(list_size(&l) == 0)) return "Size error";
else
    printf("Some condition is false\n");

這樣的寫法在編譯時會產生警告：

test.c:80:5: warning: add explicit braces to avoid dangling else [-Wdangling-else]
    else

實際執行程式後會發現 printf("Some condition is false\n"); 根本不會被執行。
為什麼呢？根據規格書：

C99 6.8.4
An else is associated with the lexically nearest preceding if that is allowed by the syntax.

這表示 else 會與距離最近、且尚未匹配 else 的 if 配對，所以不是透過對齊來決定應該匹配哪個 if。
在這個例子中，else 會與 BAD_ASSERT 巨集內的 if 配對，而不是與外層的 if。因此，當 some_condition = 0 時，程式執行流程會直接跳過整個 if-else 結構，導致 printf("Some condition is false\n"); 完全沒有被執行，影響程式的預期行為。
根據教材中的延伸閱讀的解釋：

The whole idea of using 'do/while' version is to make a macro which will expand into a regular statement, not into a compound statement.

也就是說，使用 do { ... } while (0) 的目的，是讓多行的巨集展開後仍然是單一語句，而不是一個複合語句。這樣的寫法可以確保程式執行流程符合預期，並避免 dangling else 問題。

test_list 函式以三種方式測試鏈結串列：

從頭插入：
- 驗證元素以相反的順序出現（從 N-1 到 0）
從尾插入：
- 驗證元素以相反的順序出現（從 N-1 到 0）
- 透過指定 NULL 作為 before 參數
重新插入：
- 驗證鏈結串列的大小是否正確

最後，main 函式執行測試並回報結果，如果所有測試都通過則返回 NULL，如果有任何測試失敗則返回錯誤內容的字串。

為什麼 list_insert_before 要用指標的指標來實作？

static inline void 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;
}

使用指標的指標可以統一處理插入頭部和中間位置的情況，而不需要額外的處理。這是因為我們可以使用相同的邏輯來操作。具體來說，*p = item; 可以直接修改指向當前節點的指標本身。透過操作指標的指標，我們可以直接更新前一個節點的 next 指標，來達到插入的效果。

延伸問題

Q1-2

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

size 記憶體區塊的大小
l r 指向左邊子樹和右邊子樹的指標

void remove_free_tree(block_t **root, block_t *target);

以下圖示會基於這個結構來移除節點

狀況一 - If the target node has two children, we need to find a replacement. ：找到 in-order predecessor 來替代被刪除的節點。
這又可進一步分為兩種情況：

目標節點的左子節點即為其 in-order predecessor
- find_free_tree(root, target); 回傳指向節點 3 的指標，in-order predecessor 會是節點 2
- 直接用 2 替換 3，並調整指標來完成移除操作。
- 移除節點後：

目標節點的 in-order predecessor 不是他的左邊子節點，即為目標節點的左邊子節點存在右邊子節點
- find_free_tree(root, target); 回傳指向節點 8 的指標，in-order predecessor 會是節點 6
- 先把 predecessor 從原來的位置移除，再將 predecessor 往上拉，替換掉目標節點
- 移除節點後：

狀況二 - If the target node has one child：用子節點直接替代被刪除的節點

find_free_tree(root, target); 回傳指向節點 10 的指標
透過 *node_ptr = child;，直接讓指向目標節點的指標改為指向其唯一的子節點。
移除節點後：

狀況三 - If the target node has no children：直接移除目標節點，無需進一步調整樹的結構。

find_free_tree(root, target); 回傳指向節點 15 的指標
透過 *node_ptr = NULL;，直接將指向目標節點的指標設為 NULL，將其從樹中移除。
移除節點後：

延伸問題

首先，需要補全 find_free_tree 與 find_predecessor_free_tree 這兩個函式的實作：

block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);

find_free_tree 的目標是找到大小最適合的區塊，也就是大於等於 target size 的最小區塊，並回傳該節點的位置。
至於 find_predecessor_free_tree，我先採用跟主程式一樣的邏輯，即為找左邊子樹的最右邊節點，這樣的實作會是重複執行相同的搜尋過程，沒有真正做到 verify。目前有加上數筆 assert 來協助 dubug。

todo：完善 helper function 的行為

我希望測試程式能夠涵蓋所有先前介紹的刪除節點情況，並在找不到合適大小的空間時提供相應的輸出。
目前，已新增以下函式：

bool check_has_two_children(block_t *root);
bool check_has_one_child(block_t *root);
bool check_has_left_child_predecessor(block_t *root);
bool check_has_left_deeper_predecessor(block_t *root);
void insert_tree(block_t **root, block_t *node);
block_t *create_block(size_t size);
void print_tree(block_t *root);

並且調整 remove_free_tree 為：

block_t *remove_free_tree(block_t **root, size_t target);

int main()
{
    srand((unsigned int) time(NULL));
    int count = 0;
    block_t *root = NULL;
    size_t value = 0;
    do {
        assert(count < MAX_COUNT);
        value = rand() % 200 + 1;
        insert_tree(&root, create_block(value));
        count++;
    } while (!(check_has_left_child_predecessor(root) &&
               check_has_left_deeper_predecessor(root) &&
               check_has_one_child(root) && check_has_two_children(root)));

    while (root) {
        value = rand() % 200 + 1;
        block_t *remove = remove_free_tree(&root, value);
        print_tree(root);
        printf("\n");
    }
    return 0;
}

我沒有特別檢查第三種情況（刪除沒有子節點的節點），因為一定會有葉子節點。
為了避免把樹的結構寫死，會先跑迴圈直到二元搜尋樹的結構符合預期。我覺得這個方法蠻愚蠢的，而且就算生成了一顆預期的樹，後續在移除節點的時候，樹的結構還是可能會改變，所以不一定所有移除節點的情況都有機會測試到。

todo：或許改成判斷是否所有狀況都執行過的方法會比較好。不然就是一旦出現其中一種情況，就馬上把節點刪掉。

以下是範例輸出：

19 29 42 55 56 126 155 164 
19 29 42 55 56 155 164 
19 29 42 55 56 164 
19 29 42 55 56 
Node not found in the tree
19 29 42 55 56 
Node not found in the tree
19 29 42 55 56 
29 42 55 56 
Node not found in the tree
29 42 55 56 
Node not found in the tree
29 42 55 56 
29 55 56 
55 56 
Node not found in the tree
55 56 
Node not found in the tree
55 56 
56

當輸出 "Node not found in the tree" 時，表示目前沒有合適的可用空間。

todo

二元搜尋樹有個缺點就是節點可能會一直往左邊或右邊延伸
ex. 輸入資料已經排序好
樹會變成一條直線的感覺會退化成鏈結串列的結構
所以真實世界ㄉ記憶體管理系統或是檔案管理系統不太會用最一般 BST 會是變體
比如樹在插入節點之後可以調整結構保持樹的平衡

參考嗨
基於 1-2 原始程式碼
新增 main.c benchmark.c benchmark.h bst_allocator.c bst_allocator.h

typedef struct block {
    size_t size;
    bool is_free;
    struct block *l, *r;
} block_t;

void init_allocator();
void clean_allocator();
void coalesce_free_blocks(block_t **root, block_t *block);
void split_free_block(block_t **root, block_t *block, size_t size);
void *bst_malloc(size_t size);
void bst_free(void *ptr);

可以看到 free 比 bst_free 還要慢
猜測是因為我還做不出來 coalesce，所以目前的 bst_free 會直接 insert node，沒有做相鄰空閒的記憶體合併操作。目前 free 的比較沒有什麼參考價值。

https://hackmd.io/@sysprog/linux-perf

Q1-3

main 函式：
shuffle 一個 0 - 99999 的整數陣列
藉由 list_construct 一個一個新增到 list head
然後 quick_sort
quick_sort 函式：
以下介紹主要變數可搭配圖示服用

pivot
- 用於比較大小
- 選擇當前子序列的第一個節點
- 其值用於與其他節點比較，決定節點應該放入 left 還是 right
left
- 小於等於 pivot 的所有節點
right
- 大於 pivot 的所有節點
i
- 初始值為 0，表示從堆疊底部開始
- 當需要處理新的子問題時增加（i += 2）
- 當完成一個子問題的處理時減少（i–）
- 當 i < 0 時，表示堆疊為空，所有子問題都已處理完畢
begin
- 一開始 begin[0] 存整個待排序鏈結串列的第一個節點
- 每次分割後，將三個部分（left、pivot、right）的起始位置依次存入堆疊
- 操作 i
result
- 當發現某個子序列只有一個節點時，將那個節點插入到 result 的頭部

以下都忽略 prev 指標

第一次迭代結束：

第二次迭代結束：

第三次迭代結束：

第四次迭代結束：

其他省略，直到 i < 0 迭代結束且函式結束：

在 quick_sort 函式中不會針對 prev 指標做操作，所以在最後必須再呼叫以下函式來重建整個環狀鏈結串列結構：

static void rebuild_list_link(struct list_head *head);

為什麼 begin 堆疊的長度要是兩倍？
在 worst case 下，意即要排序的是已經排序好的鏈結串列。這時候演算法的運作方式會使 begin 堆疊的使用量達到最大。
第一次切割時，鏈結串列為升序，所有節點都大於 pivot，所以 left 為空，其餘節點全部進入 right。由於程式碼的寫法會是從 left 以及 right 的頭來插入新節點：

if (n_value > value) {
    n->next = right;
    right = n;
} else {
    n->next = left;
    left = n;
}

這會導致 right 中的節點順序變為降序。因此在下一次切割時，right 會變成空的，left 包含所有剩餘節點，按照這樣的規律交替進行，直到完成全部 n-1 次切割。

堆疊初始時會放入一個節點：begin[0] = list->next;，而每次切割會在堆疊中新增兩個位置（第 i 個 index 僅僅是替換）：

begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;

因此在 worst case 情況下，堆疊最大使用量會是 1 + 2(n-1) = 2n - 1。

每次分割都會多兩個節點這點可以理解，但實際上，left、right之中一定會有一個NULL，在執行過程中，right是NULL的話會被忽略，不會長期的占用空間，所以實際上不會真的用到2(n-1)+1個格子。
是這樣嗎？
horseface1110

Q2-1

從原鏈結串列中取第一個元素作為 pivot
逐一走訪其他的元素，比 pivot 小的移到 list_less，其餘的移到list_greater
遞迴對 list_less 和 list_greater 排序
最後將排序好的 list_less 、pivot 和 list_greater 按順序合併在一起

延伸問題

目前的 random_shuffle_array 函式中的註解
/* WARNING biased shuffling */

uint16_t j = get_unsigned16() % (i + 1);

問題出在這一行

list_move 與 list_move_tail 對排序穩定性的影響
stable sorting 是指當兩個元素的排序值相同時，它們在排序後的相對順序也要與排序前相同。

舉例來說：
這是一個尚未經過排序的鏈結串列，其中 A、A' 、A'' 是相同的值，所以他們在排序後的相對順序應該也要是 A、A' 、A''。

假設我們用 list_move ，執行完 quicksort

可以看到相對順序變了。
如果有多個與 pivot 值相等的元素，它們在 list_greater 中的順序會被反轉
每個新元素被移到鏈結串列的開頭，所以最後一個走訪到的元素反而會變成第一個元素

2-2

clz2 函式計算一個 32 位無號整數中，從最高位開始連續出現的 0 的個數。例如，數字 1 的二進制表示為 00000000 00000000 00000000 00000001，因此它的結果為 31。
參數說明：

x：要計算的32位無號整數
c：可視為遞迴深度，並對應到 mask 的索引

如果 x 為 0 且 c 為 0，則回傳 32，表示該數的 32 個位元皆為 0：

if (!x && !c)
    return 32;

每次遞迴時，x 會被切成高低兩半。遞迴過程的長度依次為 32 → 16 → 8 → 4 → 2，因此最大遞迴深度為 3。

uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));

upper：透過右移取得 x 的高位部分。
lower：透過 AND，將 x 的高位部分清零，保留低位不變。

return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);

先判斷 upper 是不是 0：

若 upper 不為 0，表示從最高位開始的連續 0 一定出現在 upper，因此對 upper 進行遞迴，並將遞迴深度 c 增加 1。
若 upper 為 0，則表示 upper 的所有位元都是 0，因此從高位開始的連續 0 一定出現在 lower。這時除了對 lower 進行遞迴外，還需加上當前已確定的 leading zeros，即 upper 的位數 (16 >> c)。

if (c == 3)
    return upper ? magic[upper] : 2 + magic[lower];

當 c == 3 時，表示目前要處理的位元數只剩 2 位，因此 upper 和 lower 的值僅可能為 00、01、10、11。
一樣根據 upper 的值，計算 leading zeros：

若 upper 不為 0（即 01、10、11）
使用 upper 對應 magic 陣列，取得 leading zero 的數量。
若 upper 為 0（即 00）：
這表示 upper 全為 0，因此需要先加上 2 個 leading zero，然後再使用 lower 的值對應 magic 陣列，計算額外的 leading zeros。

static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};

看到這裡就可以來填空 mask 以及 magic 了。
mask 是用來處理 lower ，會留下每次待切割段（x）的右半邊。已知切割後的長度會是 16 -> 8 -> 4 -> 2，因此 mask[c] 的值是 0 -> 8 -> 12 -> 14，會決定 0xFFFF 右移的位數。

magic 則是上一部份所對應到的，代表目前兩位元的二進制表示有幾個 leading zero。

n	n to binary	magic[n]
0	00	2
1	01	1
2	10	0
3	11	0

以下舉例說明，省略沒意義的 0：
x = 00000000 00000001 11110000 00001010

c	x	upper	lower	返回值	計算過程
0	00000000 00000001 11110000 00001010	(x >> 16) = 00000000 00000001	(x & 0xFFFF) = 11110000 00001010	0	upper 不為 0，遞迴處理 upper
1	00000000 00000001	(x >> 8) = 00000000	(x & 0xFF) = 00000001	8 + ?	upper 為 0，返回 `(16 >> 1) + clz2(lower, 2)`，遞迴處理 lower
2	0000 0001	(x >> 4) = 0000	(x & 0xF) = 0001	4 + ?	upper 為 0，返回 `(16 >> 2) + clz2(lower, 3)`，遞迴處理 lower
3	00 01	(x >> 2) = 00	(x & 0x3) = 01	2 + 1 = 3	遞迴終止，upper 為 0，返回 `2 + magic[1]`
2	-	-	-	4 + 3 = 7	-
1	-	-	-	8 + 7 = 15	-
0	-	-	-	15	結束

uint64_t sqrti(uint64_t x);

參考檢討第二週測驗題

2025q1 Homework2 (quiz1+2)

Q1-1

延伸問題

Q1-2

延伸問題

Q1-3

Q2-1

延伸問題

2-2

Read more

EEVDF 論文研讀

2025q1 Homework5 (assessment)

2025q1 Homework3 (kxo)

2025q1 Homework4 (quiz3+4)