2025q1 Homework2 (quiz1+2)

contributed by <I-Ying-Tsai>

quiz1

測驗 1

這題要求我們利用 list_insert_before 涵式來測試好品味的 linked list 結構

#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_insert_before 涵式的要求，可以得到：
AAAA : &l->head , 因為涵式接受的是 Node** head <所以我們需要傳入的是 head 的地址，而 head 又是第一個節點的地址，這也是指標的指標的應用。

BBBB : before , 因為在 list_insert_before 函式中，我們希望在 entry 之前插入新節點 new_node，因此我們需要確保 new_node 指向 entry，而前一個節點（prev）指向 new_node。

CCCC : &(*p)->next , 因為我們希望透過 pointer to pointer (Node** p) 來修改鏈結串列的結構，特別是當 entry 不是 head 的情況下，我們需要找到 entry 的前一個節點，並調整它的 next 指標，讓 new_node 正確插入。

DDDD : item->next , 因為 *p = item; 讓 prev->next 指向 item。 item->next = before; 讓 item 連接到 entry。

延伸問題 : 解釋上方程式碼運作原理

這段程式碼的目的是 在單向鏈結串列中，找到 entry ，並在其之前插入 item。

延伸文題 : 在現有的程式碼基礎上，撰寫合併排序操作

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 找到鏈結串列的中間點並拆分
void split_list(Node* source, Node** front, Node** back) {
    Node* slow = source;
    Node* fast = source->next;

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

    *front = source;
    *back = slow->next;
    slow->next = NULL;
}

// 合併兩個排序後的鏈結串列
Node* sorted_merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;

    Node* result = NULL;
    if (a->data <= b->data) {
        result = a;
        result->next = sorted_merge(a->next, b);
    } else {
        result = b;
        result->next = sorted_merge(a, b->next);
    }
    return result;
}

// 合併排序主函式
void merge_sort(Node** head_ref) {
    Node* head = *head_ref;
    if (!head || !head->next) return;

    Node *a, *b;
    split_list(head, &a, &b);

    merge_sort(&a);
    merge_sort(&b);

    *head_ref = sorted_merge(a, b);
}

// 插入新節點到鏈結串列
void push(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

// 列印鏈結串列
void print_list(Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// 測試
int main() {
    Node* head = NULL;
    push(&head, 4);
    push(&head, 2);
    push(&head, 7);
    push(&head, 1);
    push(&head, 9);
    push(&head, 3);

    printf("原始鏈結串列:\n");
    print_list(head);

    merge_sort(&head);

    printf("排序後的鏈結串列:\n");
    print_list(head);

    return 0;
}

---

測驗 2

block_t :

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

size_t size; :
記錄當前記憶體區塊的大小。
struct block *l; :
指向 左子節點（left child），即 小於當前區塊大小的記憶體區塊。
struct block *r; :
指向 右子節點（right child），即 大於當前區塊大小的記憶體區塊。

---

find_free_tree() :

block_t **find_free_tree(block_t **root, block_t *target);

搜尋 target 在 free tree 中的位置，回傳指向該區塊的指標。這個函式的作用是幫助 remove_free_tree() 定位到 target 在 二元搜尋樹（BST） 中的節點，以便進行刪除或合併。

---

find_predecessor_free_tree() :

block_t *find_predecessor_free_tree(block_t **root, block_t *node);

尋找小於 node->size 的最大節點。這個函式的結果用於 刪除 target 節點時，找到適合替換 target 的節點。

---

remove_free_tree()

void remove_free_tree(block_t **root, block_t *target)

從二元搜尋樹（BST）中移除 target，並確保 BST 結構保持完整。
刪除一個節點時，可能發生三種情況：
1.target 沒有子節點 → 直接刪除。
2.target 只有一個子節點 → 讓 target 的父節點直接指向 target 的子節點。
3.target 有兩個子節點 → 找到 target 的 predecessor 來替代 target，保持 BST 屬性。

---

EEEE : (*pred_ptr)->r , 因為它會走訪 target 節點的 左子樹，找到其中的最右節點。

FFFF : pred_ptr , 因為它代表如何向右子樹移動，即應該指向 pred_ptr 的 右子節點，直到找到最右節點。

延伸閱讀 : 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

這段程式碼的目的是 管理樹狀結構的記憶體區塊，其中 block_t 作為 二元搜尋樹（BST）節點，用來管理空閒記憶體區塊（free block）。主要功能包括：

find_free_tree()：在樹中尋找 指定大小的記憶體區塊。

find_predecessor_free_tree()：尋找 指定節點的 predecessor。

remove_free_tree()：從 BST 中 移除記憶體區塊，並維持 BST 屬性。

補完程式碼：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

// 在二元搜尋樹中尋找適合大小的 free block
block_t **find_free_tree(block_t **root, block_t *target) {
    block_t **current = root;

    while (*current) {
        if ((*current)->size == target->size) {
            return current;
        } else if ((*current)->size > target->size) {
            current = &(*current)->l;
        } else {
            current = &(*current)->r;
        }
    }
    return NULL;
}

// 找到左子樹的最右節點
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    if (!node || !node->l) return NULL;

    block_t *pred = node->l;
    while (pred->r) {
        pred = pred->r;
    }
    return pred;
}

// 從 free tree 中移除一個節點
void remove_free_tree(block_t **root, block_t *target) {
    block_t **node_ptr = find_free_tree(root, target);
    if (!node_ptr || !*node_ptr) return;

    // 如果節點有兩個子節點
    if ((*node_ptr)->l && (*node_ptr)->r) {
        block_t **pred_ptr = &(*node_ptr)->l;
        while ((*pred_ptr)->r) // EEEE
            pred_ptr = &(*pred_ptr)->r; // FFFF

        block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
        assert(expected_pred == *pred_ptr);

        if (*pred_ptr == (*node_ptr)->l) {
            block_t *old_right = (*node_ptr)->r;
            *node_ptr = *pred_ptr;
            (*node_ptr)->r = old_right;
        } else {
            block_t *old_left = (*node_ptr)->l;
            block_t *old_right = (*node_ptr)->r;
            block_t *pred_node = *pred_ptr;
            remove_free_tree(&old_left, *pred_ptr);
            *node_ptr = pred_node;
            (*node_ptr)->l = old_left;
            (*node_ptr)->r = old_right;
        }
    }
    // 只有一個子節點
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    }
    // 沒有子節點
    else {
        *node_ptr = NULL;
    }

    target->l = NULL;
    target->r = NULL;
}

// 插入新節點到 free tree
void insert_free_tree(block_t **root, block_t *node) {
    if (!*root) {
        *root = node;
        node->l = node->r = NULL;
        return;
    }

    if (node->size < (*root)->size) {
        insert_free_tree(&(*root)->l, node);
    } else {
        insert_free_tree(&(*root)->r, node);
    }
}

// 輔助函式：中序走訪列印二元搜尋樹
void inorder_traversal(block_t *root) {
    if (root) {
        inorder_traversal(root->l);
        printf("%zu ", root->size);
        inorder_traversal(root->r);
    }
}

---

延伸閱讀 : 參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

i-ying-tsai@i-ying-tsai-G5-KF5:~/quiz1/memory-allocators/build$ cmake ..
-- The CXX compiler identification is GNU 13.3.0
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- The C compiler identification is GNU 13.3.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Configuring done (0.4s)
-- Generating done (0.0s)
-- Build files have been written to: /home/i-ying-tsai/quiz1/memory-allocators/build
i-ying-tsai@i-ying-tsai-G5-KF5:~/quiz1/memory-allocators/build$ make
[ 25%] Building C object CMakeFiles/quiz2.dir/quiz2.c.o
[ 50%] Building CXX object CMakeFiles/quiz2.dir/src/StackAllocator.cpp.o
/home/i-ying-tsai/quiz1/memory-allocators/src/StackAllocator.cpp: In member function ‘virtual void* StackAllocator::Allocate(std::size_t, std::size_t)’:
/home/i-ying-tsai/quiz1/memory-allocators/src/StackAllocator.cpp:39:39: warning: narrowing conversion of ‘padding’ from ‘std::size_t’ {aka ‘long unsigned int’} to ‘char’ [-Wnarrowing]
   39 |     AllocationHeader allocationHeader{padding};
      |                                       ^~~~~~~
[ 75%] Building CXX object CMakeFiles/quiz2.dir/src/PoolAllocator.cpp.o
[100%] Linking CXX executable quiz2
[100%] Built target quiz2
i-ying-tsai@i-ying-tsai-G5-KF5:~/quiz1/memory-allocators/build$ ./quiz2
原始 free tree: 5 10 15 20 30 
移除 size 10
更新後 free tree: 5 15 20 30 
移除 size 20
更新後 free tree: 5 15 30 

---

測驗 3

node_t :

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

value：儲存節點的值（數值）。
list：使用 Linux Kernel list_head 來管理鏈結串列。

---

list_entry :

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

ptr：指向 struct list_head 的指標（即 next 或 prev）。
type：包含 struct list_head 的結構體類型（如 node_t）。
member：struct list_head 在 type 結構中的成員名稱（如 list）。

它會從 list_head 的指標 ptr，計算出 type 結構體的起始位置。

---

GGGG : head->prev , 因為需要確保雙向鍊結串列可以閉合。

HHHH : list_entry(pivot,node_t,list)->value , 因為它要取出 pivot 節點的 value。

IIII : list_entry(n,node_t,list)->value , 因為它要取出 n 節點的 value。

JJJJ : pivot , 因為當快速排序拆分鏈結串列時，pivot 作為 新的中間點，用來重新組合。

KKKK : right , 因為這個快速排序是從 right 部分開始排序，所以 right 需要先被放到 begin[i + 2]。

---

延伸閱讀 : 解釋上述程式碼運作原理

---

延伸閱讀 : 研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

---

quiz 2

測驗 1