2025q1 Homework2 (quiz1+2)

第一周測驗 1

整段程式碼是用來測試 list_insert_before() 及 list_size() 函式的正確性

1. 測試 list_insert_before() 是否正確插入節點
2. 測試 list_size() 是否回傳正確的 list 長度

根據函式的語意，list_insert_before 是將新的 item 插入 list 中某個特定的 item 之前，並且當 before 參數指向整個 list 的 head，則會將新的 item 插入在最前面，如果指向 NULL，則插入到 list 的最後面

程式碼解析

1. Macro

   • my_assert(test, message): 測試條件是否為 true，否則回傳錯誤訊息
   • my_run_test(test): 執行測試函式 test()，如果有錯誤則回傳訊息

2. 全域變數

   • items[N]: 預先分配 N 個 list_item_t 節點。
   • l: 鏈結串列的頭部

3. Function

   • list_reset()
     • 重置 items 陣列，使 value 依序設為 0 ~ N-1
     • 將 l.head 設為 NULL
   • test_list()
     • 檢查 list_insert_before() 及 list_size() 函式的正確性
   • test_suit()
     • 執行 test_list()
   • main()
     • 執行測試並輸出結果。

由於 list_insert_before 是將新的 item 插入到 before 之前，搭配指標的指標 p，函式內容應為：

void list_insert_before(list_t *l, list_item_t *before, list_item_t *item) {
    if (!l || !item)
        return;
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}

第一周測驗 2

依據註解，要找到左子樹中的最右節點，因此 EEEE 及 FFFF 應為：

void remove_free_tree(block_t **root, block_t *target)
{
    ...
    /* 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_pre->r)
            pred_ptr = &(*pred_pre)->next;
    ...

程式碼解析

remove_free_tree 負責從二元搜尋樹 (BST) 中刪除節點 target，其中 root 是樹的根節點指標，而 target 是要刪除的記憶體區塊

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

首先找到目標節點

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

第一周測驗 3

由於題目解說中提到 「指標 p 會一直往右走，將大於 pivot 的節點存入 right ， 小於的存入 left ，接著可得到三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2 」，begin 與 end 的用意是在保存 left pivot right 的邊界資訊

根據以上所以 CCCC 應為 p->next ，DDDD 應為 list_tail(left) ，EEEE 應為 list_tail(right)

void quick_sort(node_t **list)
{
    ...
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add(n->value > value ? &right : &left, n);
    }
    begin[i] = left;
    end[i] = DDDD;
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
    end[i + 2] = EEEE;
}

由於先前的排序破壞了雙向鏈結串列的結構，rebuild_list_link 的作用是重建雙向鏈結串列的鏈接關係，使其變為一個頭尾相連的環狀雙向鏈結串列
因此，GGGG 應為 head->prev = prev

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev = prev;
}

程式碼中第 11 行針對 n_value 與 value 進行比大小，所以 HHHH 及 IIII 應為

{
    struct list_head *pivot = L;
    value = list_entry(pivot, node_t, list)->value; // IIII
    struct list_head *p = pivot->next;
    pivot->next = NULL; /* break the list */

    while (p) {
        struct list_head *n = p;
        p = p->next;
        int n_value = list_entry(n, node_t, list)->value; // HHHH
        if (n_value > value) {
            n->next = right;
            right = n;
        } else {
            n->next = left;
            left = n;
        }
    }
}

而 begin 與改寫之前相同，主要是用於紀錄 left pivot 及 right 的邊界資訊，所以 JJJJ = pivot 跟 KKKK = right 。

    begin[i] = left;
    begin[i + 1] = pivot;
    begin[i + 2] = right;
    left = right = NULL;
    i += 2;

第二周測驗 1

struct listitem {
    uint16_t i;
    struct list_head list;
};

結構體 listitem 中包含一個 uint16_t 的變數 i ，及一個 list_head ，其中 list_head 又包含兩個指標，分別是 prev 與 next，整體結構應如下圖

cmpint 用於比較傳入參數的大小

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

輔助函式

ARRAY_SIZE(x) ：計算陣列中有幾個元素
getnum ：利用三個靜態變數，個別進行乘積與模除，接著透過 xor 運算得到一個 8 位元的隨機數
get_unsigned16 ：將兩個 8 位元的數值組合成一個 16 位元的數值
random_shuffle_array ：對於傳入的陣列進行洗牌

測試程式 main

首先是隨機填入數值到陣列 values 中，對 testlist 進行初始化，並且檢查 testlist 是否是空的，接著透過 list_add_tail() 將元素逐一加入 testlist 的尾端

    random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));

    INIT_LIST_HEAD(&testlist);

    assert(list_empty(&testlist));

    for (i = 0; i < ARRAY_SIZE(values); i++) {
        item = (struct listitem *) malloc(sizeof(*item));
        assert(item);
        item->i = values[i];
        list_add_tail(&item->list, &testlist);
    }

再來是對 values 及 testlist 中的元素進行排序，檢查排序結果，並釋放記憶體

    qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
    list_quicksort(&testlist);

    i = 0;
    list_for_each_entry_safe (item, is, &testlist, list) {
        assert(item->i == values[i]);
        list_del(&item->list);
        free(item);
        i++;
    }

最後檢查串列是否已清空

    assert(i == ARRAY_SIZE(values));
    assert(list_empty(&testlist));

依據 quiz1-3，quick sort 的流程會將整個串列拆成三組，分別是 left pivot right，首先會將 pivot 從串列中移除，接著將串列中的元素逐一與 pivot 進行比對，如果串列中的元素小於 pivot ，則移動到 list_less，反之則移動到 list_greater，因此我們可以推測：

    pivot = list_entry(head, struct listitem, list); // AAAA
    list_del(&pivot->list); // BBBB

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move_tail(&item->list, &list_greater); // CCCC
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

    list_add(&pivot->list, head); // DDDD
    list_splice(&list_less, head); // EEEE
    list_splice_tail(&list_greater, head); // FFFF

第二周測驗 2

根據題意「每次呼叫 clz2() 函式時，代表將目前關注的位元（bits）「切成一半」，以檢查 leading zero 的數量」，再加上 mask 陣列中的元素是有規律的，從一開始(c = 0)的 0 ，接著(c = 1)是 8 ，再來(c = 2)是 12，此可以推得

$$mask[i]=mask[i-1]+(16\gg c)$$ 因此 GGGG 應為 14

程式碼解析

若 c 與 x 皆為 0 ，則直接回傳 0

if (!x && !c)
    return 32;

使用兩個變數 upper 和 lower 把 x 切成兩半

uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));

c == JJJJ 為終止條件，依據題意 step3 「遞迴呼叫 clz2() 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果」，當 16 >> c == 2 ，c 會等於 3，因此 JJJJ 應為 3

if (c == JJJJ)
    return upper ? magic[upper] : KKKK + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);