2025q1 Homework2 (quiz1+2)

contributed by < JeepWay >

quiz1 測驗1

主要差異部分如下

/* Test inserting at the beginning */
for (size_t i = 0; i < N; i++)
    list_insert_before(&l, l.head, &items[i]);

/* Test inserting at the end */
for (size_t i = 0; i < N; i++)
    list_insert_before(&l, NULL, &items[i]);

可以發現兩種函式的差異在於傳入的第二個參數，分別是 l.head 和 NULL，故可以推測第二個參數是要插入的節點的新 next。

list_insert_before 函式如下

void list_insert_before(list_t *l, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

因為是單向鏈結串列，所以 p 是 list 的 head。而 item 也就是插入的節點。
*p = item; 是在 assign 新的 head，也就是插入的 item。
list_item_t **p; 這種操作是指標的指標，方便之處在於可以不用回傳的新 head 的地址，所以該函式的回傳型態才會是 void。如果不使用指標的指標，就要向 LeetCode 的題目一樣回傳新 head 的地址。

p = AAAA; 目的是初始化 p 傳入的 head 的地址，所以 AAAA 是 &l->head。

*p != BBBB 是在偵測是否到達要插入的位置，也就是傳入的 before，所以 BBBB 是 before

DDDD = before 是在更新 head->next，所以 DDDD 是 (*p)->next 或者 item->next。

CCCC 一定式移動 p 到下一個節點，所以是 &(*p)->next。

名稱	程式碼
AAAA	&l->head
BBBB	before
CCCC	&(*p)->next
DDDD	(*p)->next 或者 item->next

視覺化展現

當使用 list_insert_before(&l, l.head, &items[i]); 把節點插入到含有一個節點的鏈結串列的 head 時，各指標與節點的關係圖如下。

在插入完成後，各指標與節點的關係圖如下。

當使用 list_insert_before(&l, NULL, &items[i]); 把節點插入到含有一個節點的鏈結串列的 head 時，各指標與節點的關係圖如下。

在插入完成後，各指標與節點的關係圖如下。

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

• main() -> test_suite() -> my_run_test() 巨集 -> test_list()
  1. list_reset() 重節節點
  2. 將重置後的 N 個節點依序插入到鏈結串列 l 的 head，然後檢查插入節點數和節點順序是否符合預期。
  3. list_reset() 重節節點
  4. 將重置後的 N 個節點依序插入到鏈結串列 l 的 tail，然後檢查插入節點數和節點順序是否符合預期。
  5. list_reset() 重節節點
  6. 將重置後的 N 個節點依序插入到鏈結串列 l 的 tail，檢查檢查插入節點數是否為 N。

延伸問題 : 撰寫合併排序操作

使用 top-down 方法實作 merge sort

quiz1 測驗2

• 0x0（最低地址）：這部分通常是未使用的（標記為 "UNUSED"），因為操作系統通常會將地址 0 保留為無效地址，以捕捉 null pointer error。
• 0x400000：表示虛擬記憶體空間中的某個起始點（通常 Linux 系統中可執行文件的地址從 0x400000 開始）。
• Read-only segment：存放進程的可執行程式碼和唯讀數據
  • .text：存放程式碼，如機器碼。
  • .rodata：存放唯讀數據，例如字符串（string literals）。
  • .init：存放程式初始化相關的數據。
• Read/write segment：存放行程（process）的全局變數和靜態變數：
  • .data：存放已初始化的全局變數和靜態變數。
  • .bss：存放未初始化的全局變數（這些變數在程式啟動時會被初始化為 0）。
• Run-time heap：這部分記憶體是用來動態分配的（通過 malloc 函數創建）。
  • heap 從低地址往高地址增加。
  • heap 的當前頂端由一個指標 brk 標記，這是 OS kernel 用來追踪 heap 邊界的地址。當程式需要更多空間時，會通過系統調用（如 sbrk 或 brk）來移動這個邊界。
• Memory-mapped region for shared libraries：用於映射共享函式庫（C 標準函式庫 libc）的記憶體。
  • 共享函式庫包含程式運行時需要的函數和數據（例如 printf 函數）。
  • 這部分的記憶體空間允許 process 訪問這些共享資源，而無需將整個函式庫複製到 process 的記憶體中。
• User stack：
  • stack 從高地址向低地址增加。
  • stack 用於存放函數調用的局部變數、返回地址等。
  • stack pointer (%rsp) 指向 stack 的當前頂部 (往低地址)。
• Kernel virtual memory：保留給 OS kernel 使用的，普通用戶 process 無法直接訪問（標記為 "Memory invisible to user"），若要使用則須使用 kernel 提供出來的 api 來間接操作，例如系統呼叫。

/* Find the in-order predecessor:
 * This is the rightmost node in the left subtree.
 */
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE)
    pred_ptr = FFFF;

in-order predecessor (中序前繼節點) 即目標節點的左子樹中最右邊的節點。所以 pred_ptr 就是一直往右子節點移動，直到 pred_ptr 為 leaf 為止。

名稱	程式碼
EEEE	(*pred_ptr)->r
FFFF	&(*pred_ptr)->r

程式碼解釋

• remove_free_tree(block_t **, block_t *)：從二元樹中移除指定節點。
  • find_free_tree(root, target)：找到目標節點 target 在二元樹中的地址，返回指向該節點的指標的指標（node_ptr）。
  • 移除時有分三種情況，(1) 目標節點有兩個子節點：
    1. 找到中序前繼節點 pred_ptr。並使用 find_predecessor_free_tree 檢查 pred_ptr 是否為預期的中序前繼節點。
    2. 找到合適的子節點來替換目標節點的在二元樹中地址。
       • 如果中序前繼節點是目標節點的左子節點，則直接替換，並更新原本右子樹的鏈結。
       • 如果中序前繼節點不是目標節點的左子節點，則先使用 remove_free_tree() 移除把中序前繼節點從二元樹中移除，再把它替換到目標節點所在的位置，然後再重新連接原本的左右子樹。
  • (2) 日標節點有一個子節點：將目標節點在二元樹中的地址替換為左右節點的其中一個。
  • (3) 日標節點沒有子節點：設定目標節點在二元樹中的地址為 NULL。
  • 設定目標節點的左右節點指標為 NULL，避免非預期的 reference。

嘗試補完程式碼

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

block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    block_t *current = node->l;
    while (current->r)
        current = current->r;
    return current;
}

quiz1 測驗3

quiz2 測驗1