2025q1 Homework2 (quiz1+2)

contributed by <leowu0411>

quiz 1-1

此題透過完成以下函式點出 a pointer to a pointer 的技巧

static inline void list_insert_before(
    list_t *l,
    list_item_t *before,
    list_item_t *item
);

list_insert_before 函式負責在單向鏈結串列中的指定節點前插入新節點

list_t *1：指向單向鏈結串列開頭
list_item_t *before：指定節點
list_item_t *item：欲插入之節點
以下為利用 a pointer to a pointer 之實作

{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}

在單向鏈結串列中，插入節點時通常需要知道前一個節點 (prev)，透過 list_item_t **p 能夠直接操作該節點的指標變數，無需額外存儲 prev

傳統寫法 (需要 prev)

list_item_t *prev = NULL, *cur = l->head;
while (cur != before) {
    prev = cur;
    cur = cur->next;
}
if (prev) {
    prev->next = item;
} else {
    l->head = item;
}
item->next = before;

測試邏輯

在初始化測資 items 時，使 items[i] 的值與索引值一致 (items[i].value = i)，使插入後的順序清楚且可預測

static list_t *list_reset(void)
{
    for (size_t i = 0; i < N; i++) {
        items[i].value = i;
        items[i].next = NULL;
    }
    l.head = NULL;
    return &l;
}

因上述初始方法，在測試插入到開頭的狀況時只需（檢驗插入結尾同理）：
1. 使用一變數 k = N - 1
2. 遍歷 l.head 應為 N-1, N-2, ..., 1, 0
3. 依序 k-- 檢查 cur->value == k，確保順序符合預期
能夠在少量的程式碼改動下，確保 list_insert_before() 的正確性。

merge sort

static list_item_t *merge_sorted_lists(list_item_t *a, list_item_t *b) {
    list_item_t **p = &a, **head = &a;
    while (*p && b) {
        if ((*p)->value > b->value) {
            list_item_t *temp = b;
            b = b->next;
            temp->next = *p;
            *p = temp;
        }
        p = &(*p)->next;
    }
    if (b) *p = b;
    return *head;
}

static list_item_t *merge_sort(list_item_t *head) {
    if (!head || !head->next) return head;
    list_item_t *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_item_t *mid = slow->next;
    slow->next = NULL;
    list_item_t *left = merge_sort(head);
    list_item_t *right = merge_sort(mid);
    return merge_sorted_lists(left, right);
}

static void list_merge_sort(list_t *l) {
    l->head = merge_sort(l->head);
}

以上實作之 merge_sorted_lists 使用 list_item_t **p 來追蹤合併點，避免額外 prev 變數
條件插入：
- 若 b->value < (*p)->value，則將 b 自合併點插入（*p = temp），並更新 b 為 b->next。
- 反之，移動 p 到 next，直到找到適合的插入點。
確保 b 插入完畢：最後如果 b 還有節點，直接連接到合併點 *p。

測試方式

#define SHUFFLE true
list_reset(SHUFFLE);
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
    list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "list size should be N");
list_merge_sort(&l);
size_t k = 0;
list_item_t *cur = l.head;
while (cur) {
    my_assert(cur->value == k, "List is not sorted correctly.");
    k++;
    cur = cur->next;
}

與原程式之測試方式相同，但稍微改動 list_reset 函式，使其能夠根據 shuffle 參數決定是否初始化隨機值。

static list_t *list_reset(bool shuffle)
{
    srand(time(NULL));
    
    for (size_t i = 0; i < N; i++) {
        items[i].value = shuffle ?  rand() : i;
        items[i].next = NULL;
    }
    l.head = NULL;
    return &l;
}

quiz 1-2

此題主要展示以 binary serch tree 實作的記憶體管理器，用來管理空閒區塊 (free block)，允許在釋放時維護記憶體區塊的組織結構，以利之後的分配 (malloc) 和合併 (coalesce) 操作。

函式解釋

remove_free_tree()
- 負責從二元搜尋樹中移除一個空閒區塊 target。
- 若 target 有兩個子節點，則需要找到中序前驅節點 (predecessor) 來替代 target，確保 BST 結構維持完整。
- 若 target 只有一個子節點或沒有子節點，則直接將 target 從樹中移除。

find_free_tree()

負責在 BST 中找到指向 target 之指標
實作如下：

block_t **find_free_tree(block_t **root, block_t *target)
{
    while (*root) {
        if (taget->size == (*root)->size)
            return root
        else if (target->size > (*root)->size)
            root = &(*root)->right;
        else
            root = &(*root)->left;
    }
    return root;
}

找到指向含有符合要求空間大小之節點之指標並回傳

find_predecessor_free_tree()

尋找中序前驅節點，即左子樹中的最右節點
此節點之 size 必小於所有 root 右子樹節點之 size
此節點之 size 必大於等於所有 root 左子樹節點之 size
使用此節點替換將被移出 BST 之 target
實作如下：

block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    block_t *pred = NULL;
    if (node->l) {
        pred = node->l;
        while (pred->r)
            pred = pred->r;
    }
    return pred;
}

測試程式

首先實作 insert_free_tree() 以將新節點加入 BST
如果 find_free_tree() 回傳的 target 不是 NULL，表示已經存在相同大小的節點
因此直接以新的 block 取代 target，並將 target 的原始子樹變成 block 的左子樹，確保 BST 結構仍然維持。

void insert_free_tree(block_t **root, block_t *block) {
	block_t **target = find_free_tree(root, block);
    if (!(*target)) {
        *target = block;
		return;
    }
    block->r = (*target)->r;
    (*target)->r = NULL;
    block->l = (*target);
    *target = block;
}

將 BST 利用 Graphviz 視覺化

遞迴呼叫 export_dot 將 BST 之結構寫入 Graphviz .dot 之檔案

void export_dot(block_t *root, FILE *file) {
    if (!root) return;
    if (root->l)
        fprintf(file, "    %zu -> %zu;\n", root->size, root->l->size);
    if (root->r)
        fprintf(file, "    %zu -> %zu;\n", root->size, root->r->size);
    export_dot(root->l, file);
    export_dot(root->r, file);
}

產生 .dot 檔案

void generate_dot_file(block_t *root, int step) {
    char filename[50];
    snprintf(filename, sizeof(filename), "tree_step_%d.dot", step);
    FILE *file = fopen(filename, "w");
    if (!file) {
        perror("Failed to open file");
        return;
    }
    fprintf(file, "digraph BST {\n");
    fprintf(file, "    node [shape=circle, style=filled, fillcolor=lightblue];\n");
    export_dot(root, file);
    fprintf(file, "}\n");
    fclose(file);
}

下一步利用 Graphviz 視覺化樹狀結構，較易驗證實作是否正確
利用以下 python script 產生 .png

import os
import glob
import subprocess
def generate_images():
    dot_files = sorted(glob.glob("tree_step_*.dot"))
    
    for dot_file in dot_files:
        png_file = dot_file.replace(".dot", ".png")
        print(f"Generating {png_file}...")
        subprocess.run(["dot", "-Tpng", dot_file, "-o", png_file])

if __name__ == "__main__":
    generate_images()

測試程式主函式如下：

int main() {
    block_t *root = NULL;
    int step = 0;

    block_t b1 = {32, NULL, NULL};
    block_t b2 = {64, NULL, NULL};
    block_t b3 = {16, NULL, NULL};
    block_t b4 = {48, NULL, NULL};
    block_t b5 = {8, NULL, NULL};
    block_t b6 = {128, NULL, NULL};  

    // 插入節點 32, 64, 16
    insert_free_tree(&root, &b1);
    insert_free_tree(&root, &b2);
    insert_free_tree(&root, &b3);
    generate_dot_file(root, ++step);
    // 插入節點 48, 8, 128
    insert_free_tree(&root, &b4);
    insert_free_tree(&root, &b5);
    insert_free_tree(&root, &b6);
    generate_dot_file(root, ++step);
    printf("Initial Tree:\n");
    print_tree(root);
    // 移除節點 32
    remove_free_tree(&root, &b1);
    generate_dot_file(root, ++step);
    printf("After removing 32:\n");
    print_tree(root);
    // 移除節點 16
    remove_free_tree(&root, &b3);
    generate_dot_file(root, ++step);
    printf("After removing 16:\n");
    print_tree(root);
    // 移除節點 8
    remove_free_tree(&root, &b5);
    generate_dot_file(root, ++step);
    printf("After removing 8:\n");
    print_tree(root);
    return 0;
}