# 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`，函式內容應為：
```c
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` 應為：
```c
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 是要刪除的記憶體區塊
```c
void remove_free_tree(block_t **root, block_t *target)
```
首先找到目標節點
```c
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)`
```c
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`
```c
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 應為
```c=
{
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 。
```c
begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;
left = right = NULL;
i += 2;
```
## 第二周測驗 1
```c
struct listitem {
uint16_t i;
struct list_head list;
};
```
結構體 `listitem` 中包含一個 `uint16_t` 的變數 `i` ，及一個 `list_head` ，其中 `list_head` 又包含兩個指標，分別是 `prev` 與 `next`，整體結構應如下圖
```graphviz
digraph listitem {
rankdir=LR
node[shape=record]
node1 [label="listitem|i|{<left>prev|<right>next}", style="bold"]
}
```
`cmpint` 用於比較傳入參數的大小
```c
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 的尾端
```c
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 中的元素進行排序，檢查排序結果，並釋放記憶體
```c
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++;
}
```
最後檢查串列是否已清空
```c
assert(i == ARRAY_SIZE(values));
assert(list_empty(&testlist));
```
依據 quiz1-3，quick sort 的流程會將整個串列拆成三組，分別是 left pivot right，首先會將 pivot 從串列中移除，接著將串列中的元素逐一與 `pivot` 進行比對，如果串列中的元素小於 `pivot` ，則移動到 `list_less`，反之則移動到 `list_greater`，因此我們可以推測：
```c
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
```c
if (!x && !c)
return 32;
```
使用兩個變數 upper 和 lower 把 x 切成兩半
```c
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
```c
if (c == JJJJ)
return upper ? magic[upper] : KKKK + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
```
Sign in with Wallet
Connect another wallet