# 2025q1 Homework2 (quiz1+2)
contributed by < TonyLinX >
## 2025q1 第 1 週測驗題
### 測驗 `1`
這段程式碼定義單向 linklist 的 `node` 以及串列整個 `linklist` 的 `list_t` :
```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;
```
測試函式 `list_insert_before`
這個函式的功能是在指定的 `before` 節點前插入新的 `node`，並且會遍歷 `linklist` 來找到 `before` 節點的位置。
先來討論另個想法，實際上如果只是要遍歷整個 `linklist` 不需要 `**p`，只需要 `*p`，因為只要創建一個指向 `list_item_t` 的指標並讓它指向 `l->head`，並一路透過 `next` 即可往後遍歷。
```c
void list_traverse(list_t *l) {
list_item_t *p = l->head;
while (p != NULL) {
printf("%d\n", p->value);
p = p->next;
}
}
```
那為什麼我們需要雙重指標 (`**p`)，因為我們要修改結構，如果說是單指標就會在 `p = item` 的地方出問題。因為 `p` 本身是局部變數，`p = item` 只是讓 `p` 去指向另個位址，但是整個 `linklist` 結構並不會改變，所以說我們需要 `**p`。
> 這裡其實可以想像成，如果傳送過去的指標是要被改變去指向另一個位址，那就必須要用雙重指標，因為你需要去改變這個指標的值，但是如果你只是要透過指標操作它所指向的內容，而不需要改變它本身的值（指向位址），那只需要單指標就夠了。
```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;
}
```
假設鏈結串列是：`head -> A -> B -> C -> NULL`，而 `before` 是 `B`，你想在 `B` 前插入 `item`，目標是讓鏈結串列變成：`head -> A -> item -> B -> C -> NULL`。
`list_insert_before` 的流程會先透過 `for loop` 尋找到 `before` 前面的節點，所以先初始化 `p` 為 `l->head` 的地址，然後比對 (*p) 是否為 `before`，如果不是 `before` 就往下一個節點移動， `p = &(*p)->next` 中的 `*p` 代表的是指向某一個 `node` 的指標，所以我們可以用他的成員 `next` 進行移動。 當遇到 `before` 時，p為 `A->next` 的地址，所以 `*p` 就是 `A->next`，那我們就可以透過 `*p = item` 插入 `item`，最後再讓 `item` 的 `next` 指向 `before` 就可完成這個 `linklist`。
```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;
}
```
:::spoiler 詳細步驟
* 初始化: `p = l->head`，所以 `p` 指向 `A`（地址 `0x1000`）。
* 迴圈執行：
* 第一次：`*p != before（0x1000 != 0x2000）`，`p = &((*p)->next)`：
* `*p` 是` A（0x1000）`，`(*p)->next` 是 `A->next`，也就是 `B（0x2000）`。
* `&((*p)->next)` 是 `A->next` 的地址（假設是 `0x1004`，因為 `next` 是 `A` 結構中的成員）。
* 所以` p` 更新為` &A->next（0x1004）`。
* 第二次：`*p == before（0x2000 == 0x2000）`，條件不成立，離開迴圈。
* 結果：迴圈結束時，`p` 指向 `A->next` 的地址`（0x1004）`。
* `*p = item`：
* `p` 是 `&A->next（0x1004）`，`*p` 是 `A->next` 的值（原本是` 0x2000`，指向 `B`）。
* `*p = item` 把 `A->next` 修改成 `item` 的地址（`0x4000`）。
* 現在：`l->head -> A -> item`，鏈結串列結構改變了！
* `item->next = before`：
* `item->next` 被設為 `B（0x2000）`。
* 結果：`l->head -> A -> item -> B -> C`，插入成功！
:::
#### 撰寫合併排序操作 : Commit [`2b418c3`](https://github.com/TonyLinX/linux_hw2/commit/2b418c3aa138831fd42de9cbe40b26dcfc24b019)
首先，設計 `merge sort` 的 `test case`，這邊的設計方式透過 `list_insert_before` 創建一個 `999 -> 998 -> ... -> 0` 的 `linklist`，期望再透過 `merge sort` 之後可以變成 `0 -> 1 -> ... -> 999`。而 `merge sort` 的方式採用 `top-down` 的方式實現，也就是遞迴的方式。
### 測驗 `2`
這段 code 主要是在做，當某個 free block 被 malloc() 拿去用了，要將 BST 上的 free block 移除。
```c
// 先從 BST 上找到 target node.
block_t **node_ptr = find_free_tree(root, target);
```
由於要維護 BST 的順序，在刪除上會有三種 case，每一種 case 要做的事情都不同，分成以以下三種：
- 有左右子樹 `if ((*node_ptr)->l && (*node_ptr)->r)` =>
- 找目標節點的左子樹中最大的值
```c
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE) pred_ptr = FFFF;
```
:::info
所以說 `EEEE` 為 `(*pred_ptr)->r` ， `FFFF` 為 `&(*pred_ptr)->r`
:::
- 找目標節點的右子樹中最小的值
- 只有左子樹或右子樹 `else if ((*node_ptr)->l || (*node_ptr)->r) {}` => 直接把左子樹或右子樹補上去
- 沒有任何子樹 => 直接設定成 `NULL`
下面這段 code 主要的設計是考慮到 `pred_ptr` 的位置，如果說 `pred_ptr` 是目標節點左子樹的根，那可以直接替換上去，但如果是在非常深處的 leaf ，由於沒辦法得知 `pred_ptr` 的父節點，所以只能透過遞迴的方式把它找出來並且移除，然後再把它拿去替換。
```c
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
} else {
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* Remove the predecessor from its original location. */
remove_free_tree(&old_left, *pred_ptr);
/* Replace the target node with the predecessor. */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
}
```
### 測驗 `3`
這個題目主要是在做 QuickSort，常見的 QuickSort 是會透過 swap 以及 recursive 的方式實現排序。在這裡不會使用以往 recursive 的方法，而是改成 stack 來模擬原本的遞迴呼叫。
* begin[i], end[i] 分別用來存放單一排序分割的起始點和終點，i 為分割編號
* left 用來存放小於等於 pivot 的節點
* right 用來存放大於 pivot 的節點
* result 用來存放排序完的分割
具體來說，他會先找一個 `pivot`，並取比較剩下的 `node_t` 的 value，如果比 `pivot` 還小就接在`left`的尾部，如果比較大就分給 `right` 的尾部，所以當處理完所有的 `node_t`，你就會得到三組分割 `left`,`pivot`, `right`。接下來，這三組分別對應 `i`,`i+1`,`i+2`，各自將自己的第一個 `node_t` 加入到 `begin[i]`, `begin[i+1]`, `begin[i+2]`，並也將自己的最後一個 `node_t` 加入到 `end[i]`, `end[i+1]`, `end[i+2]`。 最後，就從最後面的部分開始排序。
這段 code 主要是當不只一個 `node_t`，必須根據 `pivot` 將所有的 `node_t` 分成 `left` 以及 `right`，
:::info
* `value` 代表的是 `pivot` 的值，由於 `pivot` 是 `list_head`，所以要先用 `list_entry` 找到 `node_t`，才可以得到 `value`，所以 `HHHH` = `list_entry(pivot,node_t,list)->value`。
* `n_value`代表的是 `n` 的值，所以 `IIII` = `list_entry(n,node_t,list)->value`
* `begin[i]`,`begin[i + 1]`,`begin[i + 2]`，對應到的是三組分割 `left`,`pivot`,`right`，所以 `JJJJ` = `pivot`, `KKKK` = `right`。
:::
```c
if (L != R) {
struct list_head *pivot = L;
value = /* HHHH */
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 = /* IIII */;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
begin[i] = left;
begin[i + 1] = /* JJJJ */;
begin[i + 2] = /* KKKK */;
left = right = NULL;
i += 2;
}
```
這段 code 主要是維護環狀的 double-linklsit。
:::info
`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;
/* GGGG */;
}
```
## 2025q2 第 2 週測驗題
### 測驗 `1`
這段 code 主要是在對 `values` 進行賦值以及打亂。`j` 代表是 index
```c
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
static uint16_t values[256];
static inline uint8_t getnum(void)
{
static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);
s1 *= UINT16_C(171);
s1 %= UINT16_C(30269);
s2 *= UINT16_C(172);
s2 %= UINT16_C(30307);
s3 *= UINT16_C(170);
s3 %= UINT16_C(30323);
return s1 ^ s2 ^ s3;
}
static uint16_t get_unsigned16(void)
{
uint16_t x = 0;
size_t i;
for (i = 0; i < sizeof(x); i++) {
x <<= 8;
x |= getnum();
}
return x;
}
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
/* WARNING biased shuffling */
uint16_t j = get_unsigned16() % (i + 1);
operations[i] = operations[j];
operations[j] = i;
}
}
```
這個部分是實作 `quicksort`，這裡的 code 跟第一周測驗三有點雷同，因為都會切成三塊，這裡的 `less`, `pivot`, `greater` 對應到那第一周測驗三的 `left`, `pivot`, `right`，整體流程為:
- 先提取 `pivot` 的 `listietm`，並將 `pivot` 分割出來。
- 根據 `pivot` 將小於的點接在 `list_less` 後面，而大於的點接在 `list_greater` 後面。
- 各自將 `list_less` 以及 `list_greater` 進行遞迴排序。
- 最後，再將這三塊接回 head。
:::info
- 用第一個 `listitem` 做為`pivot`，所以 `AAAA` = `list_first_entry` 。
- 將 `pivot` 分割出來，所以 `BBBB` = `list_del`。
- 將大於的 `pivot` 的 `listitem` 接在 `list_greater` 後面，所以 `CCCC` = `list_move_tail`。
- 由於 `pivot` 是一個點，所以一定是 `list_add`，所以 `DDDD` = `list_add` (但我覺得 `list_add_tail` 也可以)。
- 由於 `list_less` 是比 `pivot` 還小的值，且可能為多個點，所以 `EEEE` = `list_splice`。
- 由於 `list_greater` 是比 `pivot` 還大的值，且可能為多個點，所以 `FFFF` = `list_splice_tail`。
:::
```c
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = AAAA(head, struct listitem, list);
BBBB(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
CCCC(&item->list, &list_greater);
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
DDDD(&pivot->list, head);
EEEE(&list_less, head);
FFFF(&list_greater, head);
}
```
#### 待完成
延伸問題
### 測驗 `2`
clz2() 這支函式用遞迴的方式計算 32 bit 無號整數 x 的前導零個數：它把輸入逐層一分為二，c = 0 代表先把 32 bit 切成高 16 bit (upper) 與低 16 bit (lower)，若 upper 全為 0，就可以直接把 16 累加到答案並改遞迴處理 lower；反之，若 upper 非 0，表示那 16 bit 內尚未遇到 1，就只遞迴 upper 繼續細分成 8/4/2 bit 區段。這個過程隨 c 增大而重複，區段長度依序是 16, 8, 4, 2 bit（所以 c 最大值為 3）；到最底層 (c == 3) 時，upper 只剩 2 bit，可能是 00, 01, 10, 11，對應要加的前導零個數可透過 magic[] 查表一次取得，同時若 upper 為 0 則還需把 magic[lower] 加進去。mask[] 是遮罩，是為了從 x 取出正確長度的 lower；magic[] 是當 lower 只剩下 2 bit 用來查表，由於只會是 00, 01, 10, 11，剛好可以對應為 {2, 1, 0, 0}。如果最一開始 x == 0 且 c == 0，代表 32 bit 全零，直接回傳 32。
:::info
- 由於 `lower` 最後只需要 2 bit，所以 `GGGG = 14`。
- 00, 01, 10, 11 對應 {2, 1, 0, 0}，所以`HHHH = 2`， `IIII = 0`。
- 因為是 32 bit，區段長度依序是 16, 8, 4, 2 bit，所以 `JJJJ = 3`。
- 當 `upper` 以及 `lower` 為 2 bit 的時候，在 `upper == 0` ，才會觸發 `KKKK + magic[lower];`，所以 `KKKK = 2`。
- 當 `c != 3`，不管 `upper` 是不是 0，c 都要加 1，繼續計算 `clz`，所以 `LLLL = 1`。
:::
```c
static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
if (c == JJJJ)
return upper ? magic[upper] : KKKK + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}
```
這支 `sqrti()` 函式透過「二進位長除法」計算 64 bit 整數平方根。流程如下：先用 `clz64(x)` 找出最高的 1 所在位元索引 h = `63 - clz64(x)`，再把 LSB 清 0（`shift = h & ~1ULL`），確保起始位階是偶數，因為開平方一次處理的是 2 bit ，所以起始位置一定要是偶數。
在迴圈中，每回合先計算出除數 `b = y + m`，接著把 `y` 右移 1（從 2 r 還原為 r）；若 `x ≥ b` 就說明這個 bit 應設 1 ，把 `x -= b` 並將 `y += m`；無論成敗，移到下一組 2 bit，繼續判斷。當 `m` 減到 0，`y` 即為 ⌊√x⌋。
:::info
- 由於起始位置要是偶數，所以要將 LSB 清成 0 ，所以 `MMMM` = `~1`
- 由於這裡 `y` 代表的是 2r，要變成 r ，所以 `NNNN` = `1`。
- 每次做完移到下組 2 bit，所以 `PPPP` = `2`。
:::
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
/* clz64(x) returns the count of leading zeros in x.
* (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
* Rounding that index down to an even number ensures our starting m is a
* power of 4.
*/
int shift = (total_bits - 1 - clz64(x)) & MMMM;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= NNNN;
if (x >= b) {
x -= b;
y += m;
}
m >>= PPPP;
}
return y;
}
```
#### 待完成
延伸問題
### 測驗 `3`
測驗 3 是要用 hash table 的方式完成 Two sum 這個題目。
這段 code 是在建立一個 hash table，假設 `bits` = $10$，代表這個表會有 $2^{10}$ = $1024$ 個 buckets。每一個 bucket 對應一個 `struct hlist_head`，它的結構中包含一個 `struct hlist_node *first`，這是該 bucket 所屬 double linklist 的開頭指標，用來儲存碰撞時的多個 key-value 節點。我們透過 `malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(bits))` 一次配置出整塊 bucket 陣列的空間。雖然 `map->ht` 是一個指標，但它實際上指向的是一段連續的記憶體空間，因此可以使用陣列方式操作（例如 `map->ht[i]`）。接下來透過迴圈逐一初始化每個 bucket 的 `first` 成員為 `NULL`，表示目前所有 buckets 都是空的、尚未儲存任何資料。
```c
map_t *map_init(int bits)
{
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
`map_deinit()` 是用來釋放整個雜湊表 `map_t` 所使用的記憶體資源，其核心流程如下：
- 每個 bucket 是一個 `struct hlist_head`，其中的 `first` 成員指向該 bucket 的鏈結串列起點。
- 使用 `MAP_HASH_SIZE(bits)` 計算出雜湊表大小（實際上是 $2^{\text{bits}}$ 個 buckets）。
- 若 bucket 為空（`first == NULL`），代表此 bucket 沒有資料，會被自動略過。
- 若 bucket 非空，則遍歷整條鏈：
- 使用 `container_of()` 從 `hlist_node` 取回對應的 `struct hash_key`。
- 將節點從 `hlist` 中移除：這透過 `next` 與 `pprev` 指標操作來實現。
- 若 `n->pprev == NULL`，代表此節點尚未被插入（unhashed），會直接跳過斷鏈處理。
- 每個節點的 `data` 與節點本身都會被 `free()` 掉。
- 迴圈結束後，釋放 `map` 本身的記憶體
```c
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
這段 code 主要是去搜尋 hash table 中有沒有該 `key` 值。
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
有了 `key` 值，先透過 hash function 計算出是哪一個 bucket，得到 bucket 的 index 後，用 for 迴圈去走訪整個 hlist，這個 hlist 是由一堆 `hash_key` 組成，不是 `hlist_node`，`hlist_node` 是 `hash_key` 的成員，用來串接所有 `hash_key`，所以為了知道該 `hash_key` 中的 `key`值，必須先透過 `container_of` 得到該 `hash_key` 。若有找到就回傳該 `hash_key`，沒有就回傳 `NULL`。
```c
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
```
這個 hash function 的設計方式是將 key 值乘上黃金比例常數，藉此打亂其位元分布、減少碰撞，這是來自 Donald Knuth 在《The Art of Computer Programming》中的建議。`bits` 則用來控制雜湊表的大小，決定 bucket 的數量。例如當 `bits = 10` 時，雜湊表會有 $2^{10} = 1024$ 個 buckets。整個 hash 的結果會將 key 乘上黃金比例後，再將 32-bit 結果**右移** $(32 - \text{bits})$ 位，也就是右移 22 位，讓 index 落在 `[0, 1023]` 的範圍內。
```c
// Hash function
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
如果沒有在 hash table 中找到，在 hash table 中建立該 key 值的 hash_key。
```c
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
```
:::info
* 由於都是呼叫 hash function 得到 bucket index，所以 `AAAA = map->bits` 以及 `BBBB = map->bits`。
* 為了維護整個 double linklist 的結構，所以 `CCCC = first->pprev` 以及 `DDDD = n->pprev`。
* 為了從 hlist 上移除 `n`，要先取得 `n` 的前一個以及下一個 `hash_key`，`EEEE = n->pprev`。
:::
#### 待完成
延伸問題
Sign in with Wallet
Connect another wallet