# 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;
}

* 插入節點 32, 16, 64
* 插入節點 48, 8, 128
* 移除節點 32
* 移除節點 16
* 移除節點 8

透過上圖所示，`remove_free_tree` 符合預期，在移除目標節點後，仍維持住 BST 資料結構。