2025q1 Homework2 (quiz1+2)

contributed by < Jordymalone >

第一周測驗題

測驗 1

目標: 完成 list_insert_before 函式

以下程式碼運用〈你所不知道的 C 語言: linked list 和非連續記憶體〉提及的 "a pointer to a pointer" 技巧，撰寫鏈結串列的經典操作。

解釋程式碼運作原理

考慮以下程式碼:

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

TODO: 畫圖

可以知道當前定義了兩個結構 list_item_t 和 list_t

• list_item_t 有一個 int 儲存 value，及一個指向 list_item 結構的指標 next。
• list_t 則是有一個指向 list_item 結構的指標 head，可以知道他扮演著 dummy node 的角色。

一開始定義了一些巨集:

• my_assert(test, message) 這個巨集類似 assert()，他會返回錯誤訊息，而不是終止程式。
• my_run_test(test) 這個巨集則是在 while 迴圈中執行測試函式 test()，每做一次就將測量數量 test_run 加 1。
  • 如果 test() 返回錯誤訊息，則終止測試並回傳錯誤訊息。

再來是一些資料結構和函式:

#define N 1000

static list_item_t items[N];
static list_t l;

• 這邊定義了一個大小 N = 1000 的陣列 items，每個元素都是 list_item_t 的結構。
• l 是一個 list_t 型態的變數，代表一個鏈結串列。

1. static list_t *list_reset() 是做甚麼的?

用途是初始化鏈結串列，他會去重置 items 陣列，用個 for 迴圈把每個節點 value 設為 index 值，next 設為 NULL。最後把 l.head 設為 NULL，表示鏈結串列為空。

2. static char *test_list() 是做甚麼的?

此函式做了三個測試

為什麼要做這三個測試?

• Test inserting at the beginning
  • 呼叫 list_reset() 做初始化並建立一個 items[N] 的陣列 (降冪排序)，透過 for 迴圈呼叫 list_insert_before(&l, l.head, &items[i])，因為每次傳入的 before 都是目前的 head，所以每次插入新節點都會是新的 head。

• Test inserting at the end
  • 呼叫 list_reset() 重製，一樣使用 for 迴圈呼叫 list_insert_before(&l, NULL, &items[i])，當 before 為 NULL 時，

• Reset the list and insert elements in order
  • 在一次重置鏈結串列，以相同方式從尾端插入，並檢查鏈結串列長度是否為 N。

Test 2, 3 看來是做類似的操作，差別在於 Test 2 會去檢查每個插入的值是否正確，Test 3 則單純確認鏈結串列的長度

如果以上三個測試都沒問題，就回傳 NULL。

3. static char *test_suite() 是做甚麼的?

會呼叫定義好的 my_run_test 執行 test_suite() 函式，有錯就回傳 message

主函式 main() 首先 print 出標題，呼叫 test_suite() 並把他所回傳的結果賦值給指標變數 char *result。

list_insert_before 該怎麼實作呢?

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

• list_t *l - 指向 list 的指標 l
• list_item_t *before - 指向目標節點的指標 before
  • 如果 before 是鏈結的頭節點，則新節點就會插在最前面。
  • 如果 before 是 NULL，則新節點要插入鏈結串列的尾端。
  • 如果 before 不屬於 l，則是未定義行為。
• list_item_t *item - 指向要插入的節點的指標 item

我們運用 pointer of pointer 的技巧，首先宣告一個 **p

在現有的程式碼基礎上，撰寫合併排序操作

TODO

list_t *merge(list_t *l, list_t *r)
{
    if (!l->head && !r->head)
    {
        return NULL;
    }
    if (!l->head)
    {
        list_insert_before(l, l->head, r->head);
        return l;
    }
    if (!r->head)
    {
        return l;
    }

    list_t *tmp = malloc(sizeof(list_t));
    if (!tmp)
        return NULL;
    tmp->head = NULL;
    while (l->head && r->head)
    {
        if (l->head->value < r->head->value)
        {
            list_item_t *insertnode = l->head;
            l->head = l->head->next;
            list_insert_before(tmp, NULL, insertnode);
        }
        else
        {
            list_item_t *insertnode = r->head;
            r->head = r->head->next;
            list_insert_before(tmp, NULL, insertnode);
        }
    }
    // 如果 l->head 仍有剩餘，直接全部接到 result
    while(l->head) {
        list_item_t *insertnode = l->head;
        l->head = l->head->next;
        list_insert_before(tmp, NULL, insertnode);
    }
    while (r->head) {
        list_item_t *insertnode = r->head;
        r->head = r->head->next;
        list_insert_before(tmp, NULL, insertnode);
    }
    return tmp;
}

void mergeSort(list_t *l)
{
    if (!l->head || !l->head->next)
    {
        return;
    }

    list_item_t *slow = l->head;
    list_item_t *fast = l->head->next;

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

    list_t *tmp = malloc(sizeof(list_t));
    if (!tmp)
        return;

    tmp->head = slow->next;
    slow->next = NULL;

    mergeSort(l);
    mergeSort(tmp);
    // l = merge(l, tmp);
    list_t *sorted = merge(l, tmp);
    l->head = sorted->head;
}

測驗 2

mimalloc 是什麼?

解釋上方程式碼運作的原理，並嘗試補完程式碼

block_t 結構:

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

find_free_tree

Iterate version

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

Recursion version

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

find_predecessor_free_tree

block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    if(!node->l) return NULL;

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

補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

參閱 memory-allocators

測驗 3

第二周測驗題

測驗 1

解釋程式碼運作原理

測驗 2

解釋上述程式碼，並探討擴充為

$\lceil \sqrt{n}\rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

首先是 clz2 函式，主要目的是計算 32 位元整數 x 有幾個前導 0。

大致上講一下他的程式流程，他會將 32 位元的整數先切成一半，變成這樣的形式 16 (upper) / 16 (lower) ，再來依據 upper 的數值來判斷下一步遞迴呼叫哪個部分，也就是說假設 upper 並非 0，那我們就不用去考慮 lower 的部分，直接遞迴呼叫 clz2(upper, c + 1)，反之，upper 若為 0 就呼叫 (16 >> (c)) + clz2(lower, c + LLLL)，持續遞迴呼叫直到 2 (upper) / 2 (lower) 的情況即是最後一輪，再透過變數 c (記錄第幾輪，最多到第 3 輪)判斷是否至最後一輪，並返回 upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1)

一開始定義的兩個陣列:

1. mask[]: 用來決定在哪個階段要保留多少位元
2. magic[]: 用來查表，針對較小區域的數值快速得到該區域的前置零位數

以下談及的 clz32 是已先定義好的巨集

#define clz32(x) clz2(x, 0)

再來是 clz64 函式，是透過 clz32 來建構的，輸入的參數是 64 位元的 x，首先對 x 右移 32 位，目的是看 upper (32 位元) 是否為 0，若是的話就呼叫 clz(x>>32, 0) 去計算 upper 的前導 0，反之，則呼叫 clz32(x, 0) + 32 計算 lower 部分的前導 0，這邊的加 32 是因為 upper 全都是 0。

最後是 sqrti 函式，輸入參數是 unsigned integer 64 位元的 x

首先做特殊處理，若 x 為 1 或是 0，對他做平方根就是自己，所以直接回傳 x 即可。

根據註解敘述，我們要去找到最高位的 Set bit，同時要 Rounding that index down to even number 並對齊 4 的冪次方 (

$4^k$)，也可以把它想成

$2^m$ 且這個 m 次方需要為偶數，所以程式碼中的 & MMMM(~1) 用意是將 LSB 給清除，確保 shift 會是偶數，也就是

$2^{shift}$

看不懂 while 的部分，TODO

測驗 3