2025q1 Homework2 (quiz1+2)

contributed by < fcu-D0812998 >

第一週測驗題

測驗一

解釋程式碼運作原理

首先這個測驗是要考函數 list_insert_before 的運作流程， list_insert_before 的主要目標是在單向鏈結串列中，找到 before 節點，並將 item 節點插入在它的前面。這是一種間接修改鏈結串列的方法，因為 list 本身是單向鏈結串列，且這個函式的實作運用了「指標的指標」技巧，我們可以簡化對鏈結串列的操作，特別是在插入或刪除節點時。

p = &list->head;

首先 p 是一個「指標的指標」，它最開始指向 list->head 的位址，也就是 head 的記憶體位置。

我們現在要將值為5的node插在2之前。

for (p = &l->head; *p != before; p = &(*p)->next)

迴圈的目標是找到指向 before 的指標，讓 p 能指向 before 前一個節點的 next 指標。剛開始不太理解 * 跟 & 的應用，看了幾次之後懂了。
1. 首先 l->head 指向第一個節點， &l->head 也就是取得 l->head 這個指標的地址，能讓p去指向這個位址。
2. 再來要讓 p 再回圈內在 before 前停下來，就必須取值去判斷，所以使用 *p 。
3. 再來如果判斷不成要指向下一個節點的話就要取址，首先先用*p取得目前所在的指標， (*p)->next 是目前指到的節點的下一個節點，再取址，就能讓 p 指向下一個指標的位址了。
```
*p = item;
item->next = before;
```
*p 代表「目前的 next 指標」， *p = item 讓 next 指標改指向 item ，將新節點插入，根據圖例就是 p = &([2]->next) ，即 *p 代表 [2] 的 next，此時 item->next 還沒設置，所以最後要將 item->next 指向 before 。

解釋完 list_insert_before 的運作流程後，往測驗1上面的程式碼做運作流程解析，上述程式碼主要是在測試 list_insert_before 函式的正確性，確保鏈結串列的插入操作能夠正確運作。
一開始定義了兩個巨集:
1. my_assert() : 這是一個條件檢查巨集，如果 test 為false，則回傳 message，表示測試失敗。
2. my_run_test() : 這是一個測試執行巨集，用來執行一個測試函式並計數。
後面依序是
1. list_reset() ：重設鏈結串列，確保每次測試前，鏈結串列都是空的狀態。
2. test_list() ：測試 list_insert_before() 是否能正確地在不同位置插入節點。
3. test_suite() ：執行測試函式 test_list() 。
4. main() ：呼叫 test_suite() ，輸出測試結果，因為 test_list() 只測試 list_insert_before() ，所以最後 tests_run = 1 。

在現有的程式碼進行合併排序

list_item_t *mergeTwo(list_item_t *left, list_item_t *right) {
    list_item_t *head;
    list_item_t **ptr = &head;
    while (left && right) {
        if (left->value < right->value) {
            *ptr = left;
            left = left->next;
        } else {
            *ptr = right;
            right = right->next;
        }
        ptr = &(*ptr)->next;
    }
    if (left) {
        *ptr = left;
    } else {
        *ptr = right;
}

    return head;
}

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

    list_item_t *slow = head;
    list_item_t *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_item_t *left = head;
    list_item_t *right = slow->next;
    slow->next = NULL;

    list_item_t *sort_left = mergeSort(left);
    list_item_t *sort_right = mergeSort(right);
    
    return mergeTwo(sort_left, sort_right);
}

概念跟作業1的q_sort想法一樣，只是這個是單向的鏈結串列，首先第一步先用快慢指標找出鏈結串列位於中間的值，將鏈結串列分成左半部分跟右半部分，利用遞迴的方式一直切成許多塊，再用 mergeTwo 函式比較傳入的兩個串列得 value 大小，比較小的話就輸入到暫存的 ptr 裡然後指向下一個節點繼續跟剛剛的值做比較，這樣就可以完成升序排列。

測驗二

解釋上方程式碼運作的原理

這段程式碼的作用是利用二元搜尋樹( BST )動態記憶體分配器的空閒區塊，首先一開始以為 node_ptr 是指向 target 父節點的右子樹這個指標的指標，後來發現在刪除的節點沒有子節點的情況下，要將 node_ptr 設成 NULL 就能刪除預刪除的節點就應該不會是指向 target 這個指標的指標，而是指向 target 這個節點的父節點指向 target 的指標。
首先先使用 find_free_tree 找到指向目標節點的指標，也就是 target，接下來判斷三種可能:

如果要刪除的節點沒有子節點

else {
    *node_ptr = NULL;
}

這樣根據開頭的解釋，就將 node_ptr 指向預刪除節點的父節點指向預刪除節點的指標。

如果預刪除節點只有一個子節點

else if ((*node_ptr)->l || (*node_ptr)->r) {
    block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
    *node_ptr = child;
}

首先先判斷說預刪除節點target他是存在左子節點還是存在右子節點，圖中假設target是存在右子節點，那就將child指向右子節點，那跟剛剛一樣node_ptr是指向預刪除節點的父節點指向預刪除節點的指標，那如果直接將*node_ptr = child，就可以直接將父節點接到預刪除節點的唯一子節點。

3.如果節點有兩個子節點

if ((*node_ptr)->l && (*node_ptr)->r)

如果預刪除節點有兩個子節點，根據二元樹的定理，左子樹的值必須比父節點的值更小，而右子樹則須更大，所以必須抓取前驅節點，也就是左子樹的最大值來填補空缺。

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

此程式碼就是先將 pred_ptr 指向預刪除節點指向左子樹的指標，再利用迴圈依序往右子樹的方向走，這樣就能找到左子樹的最大值。

根據圖的狀況， pred_ptr 是指向值為 4 的這個節點上，我們就先用remove_free_tree刪除值為 4 的這個節點的父子點指向他的指標，再將需要替換的節點接到target的位置。

remove_free_tree(&old_left, *pred_ptr);
*node_ptr = pred_node;

另一種情況就是左子樹的最大值就在原本要刪除節點的下一層，所以直接將target左子樹的右子樹指標指向target的右子樹指標就可完成刪除+替換。

block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr;
(*node_ptr)->r = old_right;

補完程式碼，使其可獨立執行

block_t **find_free_tree(block_t **root, block_t *target) {
    while (*root && *root != target) {
        if (target->size < (*root)->size)
            root = &(*root)->l;
        else
            root = &(*root)->r;
    }
    return root;
}

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

find_free_tree就是用來在 BST 中找到target，從root開始找，比他小就往左子樹走，比他大就往右子樹走，直到找到為止。
find_predecessor_free_tree就是用來在 BST 中找到target的左驅節點，原理的話就是先指到target的左子樹，再依序往右子樹走就能找到target的左驅節點。

參閱 memory-allocators

看了老師提供的網址，那該網址就是再說他提供了多種自訂的 C++ 記憶體配置器用來提升動態記憶體分配的效能。因為在 C++ 中，標準的malloc函數用於動態分配記憶體，但在某些情況下，標準的記憶體分配方式可能無法滿足特定的效能需求，像是當你需要頻繁的分配或釋放的話，就會導致大量的系統開銷。這個專案就展示了如何透過實作自訂的記憶體配置器，來優化記憶體分配的效能。

Linear Allocator : 線性配置器是一個最簡單且高效的記憶體管理策略，適用於批量分配記憶體但不需要個別釋放的場景，它的核心就是利用一個指標offset來追蹤記憶體的使用狀態，分配記憶體時，只需將指標offset向前移動，因此時間複雜度為 O(1)，且因為offset只會向前移動，所以無法單獨釋放某一個記憶體區塊，只能透過Reset一次性釋放整塊記憶體，讓 Offset = 0，重置配置器。

currentAddress = (std::size_t)m_start_ptr + m_offset

首先計算記憶體當前的位置。

if (alignment != 0 && m_offset % alignment != 0) {
        // Alignment is required. Find the next aligned memory address and update offset
        padding = Utils::CalculatePadding(currentAddress, alignment);
}

利用alignment變數確認是否對齊，若無則透過Utils::CalculatePadding()計算填充（padding）。

if (m_offset + padding + size > m_totalSize)
        return nullptr;

這段就是用來檢查是否超過記憶體池大小。

m_offset += padding;
const std::size_t nextAddress = currentAddress + padding;
m_offset += size;

如果上述都通過，就更新指標與偏移量。

Stack Allocator : 是一種LIFO的記憶體管理方式，跟Linear Allocator一樣都是利用指標offset來追蹤記憶體的使用狀態，他與Linear Allocator的差異在於Linear Allocator 只能 Reset() 整塊釋放，而Stack Allocator 可以逐步釋放記憶體，這是因為Stack Allocator利用了Header這個結構體，每次分配記憶體時，會在記憶體區塊的前方存儲Header。
Pool Allocator
Free List Allocator