# 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`。
* 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 該怎麼實作呢?**
```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
Sign in with Wallet
Connect another wallet