---
# System prepended metadata

title: 2025q1 Homework2 (quiz1+2)

---

# 2025q1 Homework2 (quiz1+2)

contributed by < `Jordymalone` >

## 第一周測驗題

### 測驗 1

**目標: 完成 `list_insert_before` 函式**

以下程式碼運用〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉提及的 "a pointer to a pointer" 技巧，撰寫鏈結串列的經典操作。

#### 解釋程式碼運作原理

考慮以下程式碼:
```c
#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()` 返回錯誤訊息，則終止測試並回傳錯誤訊息。

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

```c
#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`。

![image](https://hackmd.io/_uploads/ByYqOHV2yx.png)

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

![image](https://hackmd.io/_uploads/ryfOqrV2Jl.png)

* 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 該怎麼實作呢?**

```c
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

```c
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` 結構:
```c
typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;
```

**find_free_tree**

Iterate version
```c
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
```c
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**
```c
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](https://github.com/mtrebi/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` 是已先定義好的巨集
```c
#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

