# 2025q1 Homework2 (quiz1+2)

contributed by <`As7r1d`>
## [2025q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)
### 測驗1
`AAAA`：`&list->head`
`BBBB`：`before`
`CCCC`：`&(*p)->next`
`DDDD`：`item->next`
:::success
#### 解釋程式碼運作原理
:::
- 測試程式簡述
- 目的
- 執行針對 1000 個節點的插入測試
- 巨集
- 定義了一個大小為 1000 的節點陣列 items
- 主要有 2 個測試
- 測試將節點插入串列**尾端**且順序正確

            list_reset();
            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, l.head, &items[i]);
            my_assert(list_size(&l) == N, "Final list size should be N");
            size_t k = N - 1;
            list_item_t *cur = l.head;
            while (cur) {
                my_assert(cur->value == k, "Unexpected list item value");
                k--;
                cur = cur->next;
            }

- 測試將節點插入串列**最前端**且順序正確

            list_reset();
            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, "Final list size should be N");
            k = 0;
            cur = l.head;
            while (cur) {
                my_assert(cur->value == k, "Unexpected list item value");
                k++;
                cur = cur->next;
            }

- 在了解測試程式目的後，接下來了解**串列**架構：

    #include <stddef.h>
    typedef struct list_item {
        int value;
        struct list_item *next;
    } list_item_t;

    typedef struct {
        struct list_item *head;
    } list_t;

- `list_item_t` 表示串列的節點。其中 `value` 表示節點儲存的數值，`next` 則表示指向下一個 `list_item_t` 節點的指標（若為 NULL，表示是最後一個節點）。
- `list_t` 中 head 表示指向串列的第一個節點。如果 head 是 NULL，表示鏈結串列為空。

    digraph linked_list {
        rankdir=LR; // 讓鏈結串列從左到右排列
        node [shape=record];

        list_t [label="{  head }"];
        node1 [label="{  value | next }"];
        node2 [label="{  value | next }"];
        node3 [label="{  value | next }"];

        list_t -> node1 ;
        node1 -> node2 ;
        node2 -> node3 ;
        node3 -> 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; 
    }

- `list_insert_before` 目的：在這個函式中有一個單向鏈結串列 `l` ，將 item 插入 before 節點之前。
- `list_item_t **p`：p 是個變數指向 `list_item_t *` 指標的指標，一開始會指向 head。在 for loop 中，要找到要插入位置 before 節點，如果找到就離開迴圈，沒有找到就繼續尋找。這種指標的指標方法不需要透過特例判斷也可以正確處理插入在鏈結串列頭部或中間的情況。
- 接下來用圖解方式一步步解釋，使用指標的指標方式，設定情境是我要在 C 節點前插入節點 X：
- 初始單向鏈結串列

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];

            A [label="{<v> A | <n> next(&B)}"];
            B [label="{<v> B | <n> next(&C)}"];
            C [label="{<v> C | <n> NULL}"];

            l -> head;
            head -> A:v;
            A:n -> B:v;
            B:n -> C:v;
        }

- `p = &l->head` 一開始是 `p` 指向 head 這個指標變數本身的位址，對 p 取值是 A 節點。

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];

            A [label="{<v> A | <n> next(&B)}"];
            B [label="{<v> B | <n> next(&C)}"];
            C [label="{<v> C | <n> NULL}"];

            l -> head;
            head -> A:v;
            A:n -> B:v;
            B:n -> C:v;
            p ->head [style=dashed, color=red]; // p指向A的next
        }

- 於是 `p = &(*p)->next`。接著對 p 取值是 B 節點。

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];

            A [label="{<v> A | <n> next(&B)}"];
            B [label="{<v> B | <n> next(&C)}"];
            C [label="{<v> C | <n> NULL}"];

            l -> head;
            head -> A:v;
            A:n -> B:v;
            B:n -> C:v;
            p -> A:n [style=dashed, color=red]; // p指向A的next
        }

- 於是又 `p = &(*p)->next`。對 p 取值是 C 節點。找到before = C。

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];
            before [label="before", color=blue, fontcolor=blue];

            A [label="{<v> A | <n> next(&B)}"];
            B [label="{<v> B | <n> next(&C)}"];
            C [label="{<v> C | <n> NULL}"];

            l -> head;
            head -> A:v;
            A:n -> B:v;
            B:n -> C:v;
            p -> B:n [style=dashed, color=red];
            before -> C:v [style=dotted, color=blue];
        }

- 跳出迴圈，`*p = item;` 將 p 指向的值改成 &X。

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];
            before [label="before", color=blue, fontcolor=blue];

            A [label="{<v> A | <n> next(&B)}"];
            B [label="{<v> B | <n> next(&X)}"];
            X [label="{<v> X | <n> undefined}"];
            C [label="{<v> C | <n> NULL}"];

            l -> head;
            head -> A:v;
            A:n -> B:v;
            B:n -> X:v;
            p -> B:n [style=dashed, color=red];
            before -> C:v [style=dotted, color=blue];
        }

- `item->next = before;`，把 X->next 指向 before（即C）

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];

            A [label="{<v> A | <n> next(&B)}"];
            B [label="{<v> B | <n> next(&X)}"];
            X [label="{<v> X | <n> next(&C)}"];
            C [label="{<v> C | <n> NULL}"];

            l -> head;
            head -> A:v;
            A:n -> B:v;
            B:n -> X:v;
            X:n -> C:v;
            p -> B:n [style=dashed, color=red];
        }

- 接下來思考 edge case，如果`l`是空的，即 `l->head == NULL` 情況。
- 初始狀態

                digraph {
                    rankdir=LR;
                    node [shape=record, height=.1];

                    l [label="l"];
                    head [label="head(NULL)"];
                    p [label="p", color=red, fontcolor=red];

                    l -> head;
                    p -> head [style=dashed, color=red]; 
                }

- 因為 *p == NULL，如果呼叫 `list_insert_before(l, NULL, nodeA)`，那麼 before == NULL，所以 `*p == before`跳出 for 迴圈，執行 `*p = item;`，p 指向的值改為 &nodeA

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];
            nodeA [label="{<v> nodeA | <n> next(undefined)}"];

            l -> head;
            head -> nodeA:v;
            p -> head [style=dashed, color=red]; 
        }

- `item->next = before;`，把 `nodeA` 之 `next` 改成 NULL。

        digraph {
            rankdir=LR;
            node [shape=record, height=.1];

            l [label="l"];
            head [label="head"];
            p [label="p", color=red, fontcolor=red];
            nodeA [label="{<v> nodeA | <n> next(NULL)}"];

            l -> head;
            head -> nodeA:v;
            p -> head [style=dashed, color=red]; 
        }

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

static list_item_t* find_middle(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;
    }
    return slow; 
}


static list_item_t* merge_sorted_lists(list_item_t *l1, list_item_t *l2) {
    list_item_t dummy;
    list_item_t *tail = &dummy;
    dummy.next = NULL;

    while (l1 && l2) {
        if (l1->value < l2->value) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

static list_item_t* merge_sort_list(list_item_t *head) {
    if (!head || !head->next)
        return head; 

    list_item_t *mid = find_middle(head);
    list_item_t *right = mid->next;
    mid->next = NULL; 

    list_item_t *left_sorted = merge_sort_list(head);
    list_item_t *right_sorted = merge_sort_list(right);

    return merge_sorted_lists(left_sorted, right_sorted);
}

void list_merge_sort(list_t *l) {
    if (!l)
        return;
    l->head = merge_sort_list(l->head);
}

### 測驗2
`EEEE`：`(*pred_ptr)->r`
`FFFF`：`&(*pred_ptr)->r`
:::success
#### 解釋程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
:::
- 這題程式碼主要是二元搜尋樹（BST）中刪除節點的功能。
- 二元搜尋樹特性如下：
- left child node 的值小於 parent node。
- right child node 的值大於 parent node。
- 舉例如下圖：

    digraph BST {
        // 設定節點為圓形，背景為白色
        node [shape=circle, style=filled, fillcolor=white, fontname="Arial", fontsize=14];

        // 根節點設為特殊顏色
        root [label="50", fillcolor=white];

        // 定義所有節點
        node30 [label="30"];
        node70 [label="70"];
        node20 [label="20"];
        node40 [label="40"];
        node60 [label="60"];
        node80 [label="80"];

        // 構建樹結構，用不同顏色表示左右子樹的連線
        // 左子樹用綠色
        root -> node30 [color=black, arrowhead=vee, penwidth=1.5];
        node30 -> node20 [color=black, arrowhead=vee, penwidth=1.5];
        node30 -> node40 [color=black, arrowhead=vee, penwidth=1.5];

        // 右子樹用紅色
        root -> node70 [color=black, arrowhead=vee, penwidth=1.5];
        node70 -> node60 [color=black, arrowhead=vee, penwidth=1.5];
        node70 -> node80 [color=black, arrowhead=vee, penwidth=1.5];

        // 設定圖形布局
        rankdir=TB;
        splines=true;
        nodesep=0.5;
        ranksep=0.5;
    }    

- 節點架構如下：

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

    digraph binary_search_tree {
        rankdir=TB; // 樹從上到下排列
        node [shape=record];

        // 結構定義
        block_t_struct [label="{  size | { l | r } }"];
    }

    digraph binary_search_tree {
        rankdir=TB;
        node [shape=record];

        node10 [label="{10 | { <l> l | <r> r } }"];
        node5  [label="{5  | { <l> l | <r> r } }"];
        node15 [label="{15 | { <l> l | <r> r } }"];
        node3  [label="{3  | { <l> l | <r> r } }"];
        node7  [label="{7  | { <l> l | <r> r } }"];

        // 連接樹
        node10:l -> node5;
        node10:r -> node15;
        node5:l  -> node3;
        node5:r  -> node7;
        node7 [label="{7 (target) | { <l> l | <r> r } }", color=red, fontcolor=red];

    }

- `remove_free_tree()`：該函式目的是從樹中移除一個特定的記憶體區塊 `block_t *target`。刪除節點同時保持這棵樹的性質，主要有三種情況：
- 目標節點沒有 child node 時，直接移除。
- 目標節點只有一個 child node，將 child node 連接到 parent node。
- 目標節點有兩個 child node，從目前節點的左子樹開始，然後一直往右走，直到沒有右小孩了，就找出其左子樹中最右邊的節點來替代目標節點。

- 而我們需要完成 `find_free_tree()` 該函式

block_t **find_free_tree(block_t **root, block_t *target) {
    while (*root) { // 只要目前節點不是 NULL
        if (*root == target) {
            return root; // 找到 回傳指向它的指標
        }
        if (target->size < (*root)->size) {
            root = &(*root)->l; // 小的往左找
        } else {
            root = &(*root)->r; // 大的往右找
        }
    }
    return NULL; // 找不到
}

void remove_free_tree

:::success
#### 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
:::

### 測驗3

## [2025q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz2)