2025q1 Homework2 (quiz1+2)

contributed by < hahaB7 >

2025q1 quiz1

測驗 1

要快速理解整份程式碼的運作邏輯，首先應該掌握其資料結構及組成。以本題為例，程式中定義了兩種結構體：list_item_t 和 list_t。

#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_t 則作為鏈結串列的頭部結構，內部維護了一個指向串列首個節點的指標 ( head )。

為了更清楚理解整體架構，可以搭配以下示意圖：

根據此示意圖，我們可以得出以下幾點觀察：

• 指標與結構體的區別：圖中以圓點表示指標，而以方塊包裝的則是結構體，方塊最左方標示的是對應的結構體名稱。
• 結構體的關聯：list_t 結構體僅包含一個指標 head，指向 list_item_t 結構；而 list_item_t 結構則存放一個整數值 value，並透過 next 指標指向下一個 list_item_t 節點。若無後續節點，則 next 指標為 NULL，表示串列的結尾。

接著，分析應如何對上述結構體進行操作。根據本題的要求，需實作以下函式：

/**
 * Inserts a new item into the list before a specified item.
 *
 * This function traverses the list to locate the position immediately before
 * the item pointed to by @before and inserts @item in that position.
 * The time complexity is O(n), where n is the number of steps needed to
 * reach @before from the head of the list.
 *
 * Parameters:
 * @l      : Pointer to the list.
 * @before : Pointer to the item before which the new item should be inserted.
 *           - If @before is the head of the list, the new item is inserted
 *             at the front.
 *           - If @before is NULL, the new item is appended to the end of
 *             the list.
 *           - In all other cases, behavior is undefined if @before does not
 *             belong to @l.
 * @item   : The new list item to be inserted.
 */
static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item);

操作說明

根據函式的定義，其目標是在 list_t 所維護的單向鏈結串列中，找到 before 節點，並將 item 插入於其前方。

具體實作

函式的第一步是走訪 list_t 維護的單向鏈結串列，以尋找 before 節點。
以下程式碼透過指標 p 走訪串列，直到找到 before 節點後，再執行插入操作：

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

函式的第二步便是將 item 插入 before 的前方。

*p = item;
item->next = before;

需要特別注意的是，在此情境中我們處理的是單向鏈接串列，且要在指定節點的前方插入新節點。因此，在原有的單向鏈接串列中，我們需要調整的是 before 節點的前一個節點的 next 指標。這也是為什麼 p 需要宣告為指向指標的指標，接下來將對此進行更詳細的分析。

若是 p 僅是指向 list_item_t 的指標

考慮以下對應的程式碼範例：

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 時，這樣的操作並不會達成預期的結果。以下先以一個簡單的例子對這個問題進行鋪陳：

int a = 5;
int b = a;
int b = 3;
printf("a: %d\n");
/*
a = 5
 */

在這個例子中，我們可以很容易知道，這樣的操作無法改變 a 的值，因為在執行 b = a 時，我們只是將 a 的值複製到 b，因此修改 b 並不會影響到 a 的值。如果我們希望能夠改變 a 的值，正確的做法應該是：

int a = 5;
int *b = &a;
*b = 3;
printf("a: %d\n");
/*
a = 3 
 */

因此，當我們要修改 before 節點前一個節點的 next 指標時，我們也需要通過獲取該指標的地址，然後修改其內容，才能真正改變串列的結構。

經過以上的導入，現在重新分析實際應用於我們的場景時會是如何並搭配示意圖

• 若是 p 僅是指向 list_item_t 的指標

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

  經過 for 迴圈後 p 成功找到 before

  ​​​​p = item;
  ​​​​item->next = before;
  

  由此可以發現經過 p = item; 後不會改變串列結構，只會將 p 變成指向item，並造成最後不如預期的串列結構。

• 若是 p 是指向 list_item_t 的指標的指標

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

  經過 for 迴圈後 *p 會指向 before，也就是 p 所指向的指標將會指向 before。

  ​​​​*p = item;
  ​​​​item->next = before;
  

  這時，我們將 *p 指向 item，也就是將 p 所指向的指標 ( 即 before
  前一個節點的 next 指標 ) 改成使其指向 item，可以發現正確改變了串列的結構。

除此之外，在上述的描述中，還特別強調了將 p 宣告成指標的指標也與單向鏈接串列有關，因此接下來進一步探討雙向鏈接串列的情況。首先，假設我們將 list_item_t 結構體修改為如下形式：

typedef struct list_item {
    int value;
    struct list_item *next, *prev;
} list_item_t;

這時，如果將 p 宣告為指向 list_item_t 的指標，是否仍會出現問題呢？接下來，將對應的函式進行修改，如下所示：

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)
    ;
item->prev = p->prev;
p->prev->next = item;
p->prev = item;
item->next = before;
}

在這個情況下，我們所處理的是雙向鏈接串列。因此，對於 before 節點的 prev 指標以及 before 節點的前一個節點的 next 指標，我們都需要進行相應的修改。

可以注意到，由於是雙向鏈接串列，我們可以利用 next 和 prev 指標直接取得需要修改的節點，並進一步修改該節點內部的指標。因此，不會像上述情況那樣，雖然進行了修改，卻是對錯誤的地址進行了無效操作。

了解完 list_insert_head 便可開始逐步分析測試機制的流程，以下我將測試函式進行拆分並進行分段說明及分析。

測試封包

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)
#define my_run_test(test)       \
    do {                        \
        char *message = test(); \
        tests_run++;            \
        if (message)            \
            return message;     \
    } while (0)

static char *test_suite(void)
{
    my_run_test(test_list);
    return NULL;
}

首先定義兩個巨集 my_assert 、 my_test_run ，以及一個測試套件 test_suite

• my_assert ( 單元測試 )
  此巨集會在功能測試函式如：test_list 中展開以進行單元測試，檢查條件 test 是否成立ㄏ如果條件不成立（即test 為 false），則中止當前功能函式的執行，並立刻回傳指定的錯誤訊息以及早發現錯誤，也防止錯誤影響後續操作。

• my_test_run ( 測試執行管理 )
  這個巨集會在 test_suite 中展開以執行指定的功能測試 test，一旦功能測試回傳錯誤訊息，會立刻使 test_suite 回傳錯誤訊息到主函式以停止 test_suite 繼續進行其他功能測試，如果功能測試函式成功執行，也就是沒有回傳錯誤訊息，則會進行繼續下一個功能測試直到出錯或是全部功能測試結束。

• test_suite ( 測試總管 )
  根據函式名稱，test_suite 是一個測試套件，用來包裝所有的功能測試。這樣設計的目的在於集中管理所有功能測試，便於擴展和維護。當需要新增不同的功能測試時，只需在加入新的功能測試函式，並在 test_suite 中增加該功能測試即可。如果新增的測試與某些已有的測試功能相關，則可以直接在該測試函式內進行擴展或調整，以下是兩種情況的範例。

  1.新增不同功能測試

  ​​​​static char *test_stack(void)
  ​​​​{
  ​​​​    ...
  ​​​​}
  ​​​​static char *test_suite(void)
  ​​​​{
  ​​​​    my_run_test(test_list);
  ​​​​    my_run_test(test_stack);
  ​​​​    return NULL;
  ​​​​}
  

  2. 擴展原有功能測試

  ​​​​static char *test_list(void)
  ​​​​{
  ​​​​    ...
  ​​​​    // new unit test
  ​​​​    my_assert(condition, "Error Message");
  ​​​​}
  ​​​​static char *test_suite(void)
  ​​​​{
  ​​​​    my_run_test(test_list);
  ​​​​    return NULL;
  ​​​​}
  

定義變數及輔助函式

#define N 1000

static list_item_t items[N];
static list_t l;

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

定義了測試過程所需的變數，並提供 list_reset 作為輔助函式，用於重置鏈結串列的狀態。該函式會斷開所有節點之間的連結，並根據索引值為每個節點設定對應的數值，確保測試在相同的初始條件下執行。

功能測試函式

static char *test_list(void)
{
    /* Test inserting at the beginning */
    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;
    }

    /* Test inserting at the end */
    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;
    }

    /* Reset the list and insert elements in order (i.e. at the end) */
    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, "list size should be N");

    return NULL;
}

該功能測試分為以下三部分：

1. 從鏈結串列開頭插入元素
   此部分首先透過 list_reset 重置鏈結串列，確保起始狀態為空。接著，透過 list_insert_before 函式將元素依序插入至串列的開頭，使新元素不斷成為 head，最終串列應為倒序排列。最後，透過 my_assert 檢查串列大小是否為 N，並遍歷串列，驗證節點值是否依預期順序遞減。
2. 測試從鏈結串列末尾插入元素
   與第一部分類似，此處同樣先將鏈結串列重置為空，並驗證初始長度是否為零。不同的是，這次使用 list_insert_before(&l, NULL, &items[i]) 在串列末端插入元素，導致串列最終呈現正序排列。透過 my_assert 驗證串列大小，並逐一檢查節點值是否與索引值對應，以確保插入邏輯正確。
3. 準備進行進一步測試
   最後，程式碼再次重置串列並執行與第二部分相同的插入操作，但未執行值驗證 ( 已於 2. 驗證 )。這表示該部分的目的並非驗證插入功能，而是為後續測試（如合併排序操作）準備資料，使串列處於適當狀態。

主函式

int main(void)
{
    printf("---=[ List tests\n");
    char *result = test_suite();
    if (result)
        printf("ERROR: %s\n", result);
    else
        printf("ALL TESTS PASSED\n");
    printf("Tests run: %d\n", tests_run);
    return !!result;
}

主函式 main 負責執行測試流程，首先輸出測試開始的訊息，接著呼叫 test_suite 執行所有測試，並根據結果決定輸出 "ALL TESTS PASSED"或錯誤訊息，最後顯示執行的測試數量，並返回適當的狀態碼，以利後續檢查測試結果。

加入合併排序操作

1. 加入合併排序之函式

2. 擴充 test_list 函式，使其具有測試合併排序能力

3. 加入合併排序後輸出結果

---

測驗 2

在分析此題的程式碼之前，我認為應先對 Customer Allocator 有基本的了解。以下是我參考 memory-allocators 以及 Custom memory allocators 所整理的筆記：

為何需要自定義記憶體分配器？

自定義記憶體分配器是在特定場景下為了優化記憶體管理而設計的工具。以下是為何需要它的主要原因：

• 性能優化
  在某些應用場景中，例如遊戲引擎或實時系統，對性能的要求極高。標準的記憶體分配器（如 C 語言的 malloc 和 free）通常是通用的，無法針對特定使用模式進行優化。自定義分配器可以根據應用需求設計，減少分配和釋放記憶體的開銷，提高執行效率。
• 記憶體碎片管理
  頻繁的記憶體分配與釋放可能導致記憶體碎片（memory fragmentation），使得可用記憶體分散成小塊，難以滿足後續的大塊分配需求。自定義分配器可以採用特定策略（如記憶體池或塊管理），有效減少碎片，提升系統穩定性。

Customer Allocator 的共同點

因為每個程式都有特定的需求，所以使用一般用途的記憶體配置器並不合理。我們可以選擇最適合我們的記憶體配置器，這樣可以提高效能。

一般來說，客製化的記憶體配置器有一些共同的特點：

• 較少的 malloc 次數：任何客製化的記憶體配置器都會嘗試保持 malloc 次數較少。為此，它們會分配大塊的記憶體，然後在內部管理這些大塊記憶體來提供較小的配置。
• 資料結構：像是鏈接串列、樹、堆疊等次級資料結構，用來管理這些大塊的記憶體。通常，它們會用來追蹤已分配或已釋放的記憶體區域，以加速操作。
• 限制條件：某些記憶體配置器是非常特定的，對於資料或可執行的操作有一些限制。這使得它們能夠達到高效能，但只能用於某些特定的應用場景。

Free List Allocator

鏈結串列分配
當請求分配記憶體時，我們會查找一個可以容納我們資料的記憶體區塊。這意味著我們必須遍歷鏈結串列，直到找到一個大小等於或大於請求大小的區塊（它可以儲存資料及分配標頭），並將其從鏈結串列中移除。這種方式稱為「首次適配」分配，因為它會在找到第一個能夠容納資料的區塊時停止。還有一種稱為「最佳適配」的搜尋方法，它會查找較小的可用區塊來容納資料。後者操作可能會花更多時間，因為它會遍歷所有元素，但可以減少記憶體碎片。

在 Free list Allocator 中進行分配
複雜度：O(N)，其中 N 是空閒區塊的數量。

鏈結串列釋放
首先，我們從標頭中獲取有關分配的資訊。然後，我們遍歷鏈結串列，將空閒區塊插入正確的位置（因為是依地址排序的）。插入後，我們會合併相鄰的區塊。我們能夠在 O(1) 時間內進行合併，因為我們的鏈結串列是排序過的。我們只需要查看鏈結串列中的前一個和下一個元素，看是否可以合併這些相鄰的區塊。這個操作稱為「合併」（Coalescence）。如果我們使用一個已排序的空閒和已分配區塊的雙向鏈結串列，則複雜度會是 O(1)，但分配的複雜度會是 O(N)，其中 N 是空閒和已分配區塊的數量，且空間複雜度會更高。當我們釋放一個記憶體區塊時，我們也會檢查前後區塊，看看是否能將它們合併成一個更大的區塊。

在 Free list Allocator 中釋放
複雜度：O(N)，其中 N 是空閒區塊的數量。

紅黑樹資料結構
使用紅黑樹的目的是加速分配和釋放操作。在鏈結串列（或順序）實現中，每次執行操作時，我們都需要遍歷整個鏈結串列，這樣的複雜度在所有情況下都是 O(N)。

使用紅黑樹後，我們可以將其複雜度降低到 O(log N)，同時保持較低的空間複雜度，因為樹形結構的資料是儲存在空閒記憶體區塊中的。此外，這種結構允許使用最佳適配算法，減少碎片並保持效能。然而，這樣的實現需要額外的排序雙向鏈結串列來儲存已分配和空閒的元素，以便能夠進行 O(1) 的合併操作。這種實現是最常見且在真實系統中使用最廣泛的，因為它提供了高彈性，同時保持非常高的效能。

二元搜索樹結構
而在此測驗題，則是使用二元搜索樹而非紅黑樹進行實作，若是使用二元搜索樹，雖不像紅黑樹可以透過平衡的操作確保每次搜索空閒區塊都能具有O(log N)的時間複雜度，但仍可以具有相對 Linked List 來說更好的效率，只不過對於合併操作卻需要進一步的設計使其能夠正確的與前後空閒區塊合併，雖在上述紅黑樹的段落表示此目的可以透過額外的雙向鏈接串列來達成，但在我的實作採取了別的方案，我的方案透過使每一個 block 不僅記錄該區塊大小，同時也去紀錄其前方區塊大小，如此一來便可以透過自身的區塊大小以及前方區塊的大小去取得前方區塊的開頭地址以及後方區塊的開頭地址，以此來進行合併的相關操作，相 觀的細節說明參閱後方的實作說明。

在對我的實作說明之前，以下先對測驗 2 之程式碼進行拆解分析，之後在進行關於實作的解說，這邊同上先對結構體進行分析

結構體分析

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

該結構體為 Free List 中的節點，包含兩個主要成員：

• size：該空閒區塊的大小。
• l、r：指向該節點的左右子節點。

本測驗利用二元搜索樹來加速空閒區塊的查找與管理。

主要函式說明

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

上述三個函式的用途分別如下：

• find_free_tree
  找到合適的空閒區塊節點
• find_predecessor_free_tree
  尋找 target 的前驅節點（即左子樹中的最大節點）。
• remove_free_tree
  從 free list `移除指定節點。

remove_free_tree 函式拆解

1. 定位目標節點

   ​​​​/* Locate the pointer to the target node in the tree. */
   ​​​​block_t **node_ptr = find_free_tree(root, target);
   

   這行程式碼找到 target 在 free list 中的位置，並返回指向該節點的指標。

2. 目標節點有兩個子節點

   ​​​​/* If the target node has two children, we need to find a replacement. */
   ​​​​if ((*node_ptr)->l && (*node_ptr)->r) {
   ​​​​    /* Find the in-order predecessor:
   ​​​​     * This is the rightmost node in the left subtree.
   ​​​​     */
   ​​​​    block_t **pred_ptr = &(*node_ptr)->l;
   ​​​​    while ((*pred_ptr)->r)
   ​​​​        pred_ptr = &(*pred_ptr)->r;
   

   • pred_ptr 指向 target 左子樹中的最大節點。
   • 使用 while ((*pred_ptr)->r)`` 迴圈找到 target` 的前驅節點。
   ​​​​    /* Verify the found predecessor using a helper function (for debugging).
   ​​​​     */
   ​​​​    block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
   ​​​​    assert(expected_pred == *pred_ptr);
   

   確認找到的前驅節點正確：
   替換 target：

   • 如果 pred_ptr 是 target 的 直接左子節點，則簡單替換。
   • 否則，需要先將前驅節點從原樹移除，然後將 target 替換為該節點。

3. 目標節點只有一個子節點或沒有子節點

   ​​​​/* If the target node has one child (or none), simply splice it out. */
   ​​​​else if ((*node_ptr)->l || (*node_ptr)->r) {
   ​​​​    block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
   ​​​​    *node_ptr = child;
   ​​​​} else {
   ​​​​    /* No children: remove the node. */
   ​​​​    *node_ptr = NULL;
   ​​​​}
   

4. 清除 target 的指標

   ​​​​/* Clear the removed node's child pointers to avoid dangling references. */
   ​​​​target->l = NULL;
   ​​​​target->r = NULL;
   

以下開始針對以二元搜索樹實作的 Free Tree Allocator，並與 memory-allocators 中的 Free List Allocator 進行效能比較，但因此 repository 以 cpp 進行撰寫，故以下實作同樣以 cpp 完成，並利用其中已定義好的 Benchmark 分析工具進行比較。因 Free List Allocator 與 Free Tree Allocator 皆是較通用的自定義記憶體配置器，且 Free Tree Allocator 所能帶來的效益在於當使用 Find Best 策略所能帶來時間複雜度降低，故最終的比較結果會顯示其是否能夠完全此目的。

首先要透過二元搜索樹來實作 Free Tree Allocator，勢必需要優先完成此資料結構，其完整程式碼請參照參照，此處僅針對其所具有之函式進行說明。

insert
remove
findTarget
findPredecessor

接著便是FreeTreeAllocator之實作，主要 API 有

上述提及本實作欲透過紀錄 prevBlockSize 來進行合併前方空閒節點，以下將重點說明該如何維護此參數，已知會造成此參數變動僅來自兩操作，一是配置，二則是合併。

Allocate

配置時會造成 prevBlockSize的更動，我的實作過程中分析可知有以下三種狀況。

1. 被配置時所拆出剩餘空閒區塊
2. 若發生拆分，會影響後方區塊的 prevBlockSize 發生變動

Free

釋放時

分析結果

---

測驗 3

2025q1 quiz2

測驗 1

測驗 2

測驗 3