owned this note
owned this note
Published
Linked with GitHub
# 2025q1 Homework2 (quiz1+2)
contributed by < `liangchingyun` >
## 2025q1 第 1 週測驗題
### 測驗 [`1`](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1)
#### 延伸問題 1
> 解釋上方程式碼運作原理
---
巨集定義
```c
#define my_assert(test, message) \
do { \
if (!(test)) \
return message; \
} while (0)
#define my_run_test(test) \
do { \
char *message = test(); \
tests_run++; \
if (message) \
return message; \
} while (0)
```
* `my_assert()` : 如果測試條件 `test` 為 `false`，則返回 `message`。
* `my_run_test()` : 若測試失敗，則直接回傳錯誤訊息。
---
重設鏈結串列
```c
static list_t *list_reset(void)
{
for (size_t i = 0; i < N; i++) {
items[i].value = i;
items[i].next = NULL;
}
l.head = NULL;
return &l;
}
```
* 將 `items[i]` 的 `value` 設為 `i`，並將 `next` 設為 `NULL`。
* `l.head = NULL`; 清空鏈結串列。
---
測試函式
`test_list()` 包含三種測試情境
1. 在開頭插入
```c
/* Test inserting at the beginning */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k--;
cur = cur->next;
}
```
* `l.head` 表示插入在最前面。
* 逐個檢查 `cur->value` 是否符合預期的逆序 (從 `N-1` 到 `0`)。
2. 在結尾插入
```c
/* Test inserting at the end */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
k = 0;
cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k++;
cur = cur->next;
}
```
* `NULL` 表示插入在尾端
* 逐個檢查 `cur->value` 是否符合預期的正序 (從 `0` 到 `N-1`)。
3. 重設串列並插入
```c
/* Reset the list and insert elements in order (i.e. at the end) */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "list size should be N");
```
這部分與 2. 類似，但主要是確認插入結果仍然正確。
---
測試執行
```c
int tests_run = 0;
static char *test_suite(void)
{
my_run_test(test_list);
return NULL;
}
```
`test_suite()` 執行 `test_list()`，並計算測試數量。
---
主函式
```c
int main(void)
{
printf("---=[ List tests\n");
char *result = test_suite();
if (result)
printf("ERROR: %s\n", result);
else
printf("ALL TESTS PASSED\n");
printf("Tests run: %d\n", tests_run);
return !!result;
}
```
* `test_suite()` 若發生錯誤，則 `result` 為錯誤訊息。
* 測試通過則顯示 `ALL TESTS PASSED`，否則輸出 `ERROR` 訊息。
---
`list_insert_before` 函式:
```c
static inline 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;
}
```
以 `before = B` 為例:
1. `p` 初始指向鏈結串列的頭指標。
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
head [label="head"];
A [label="A"];
B [label="B"];
C [label="C"];
D [label="D"];
p [label="p"];
head -> A;
A -> B;
B -> C;
C -> D;
p -> head;
}
```
2. `for` 迴圈會遍歷鏈結串列，直到找到 `before` 節點。
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
head [label="head"];
A [label="A"];
B [label="B"];
C [label="C"];
D [label="D"];
p [label="p"];
head -> A;
A -> B;
B -> C;
C -> D;
p -> A[color=red];
}
```
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
head [label="head"];
A [label="A"];
B [label="B"];
C [label="C"];
D [label="D"];
p [label="p"];
head -> A;
A -> B;
B -> C;
C -> D;
p -> B[color=red];
}
```
3. `*p = item;` 將前一個節點的 `next` 指向 `item`，完成插入。
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
head [label="head"];
X [label="X"];
A [label="A"];
B [label="B"];
C [label="C"];
D [label="D"];
p [label="p"];
head -> A;
A -> B[style=dashed];
B -> C;
C -> D;
p -> B;
A -> X[color=red];
}
```
4. `item->next = before;` 讓 `item` 指向 `before`，確保鏈結不會斷開。
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
head [label="head"];
X [label="X"];
A [label="A"];
B [label="B"];
C [label="C"];
D [label="D"];
p [label="p"];
head -> A;
B -> C;
C -> D;
p -> B;
A -> X;
X -> B[color=red];
}
```
#### 延伸問題 2
> 在現有的程式碼基礎上，撰寫合併排序操作
### 測驗 [`2`](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2)
#### 延伸問題 1
> 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
這段程式碼的功能是從二元搜尋樹 (BST) 中移除特定的節點，這個 BST 用於管理記憶體分配中的「空閒區塊 (free blocks)」。
---
結構體
```c
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
```
`block_t` 代表一個記憶體區塊，具有：
* `size`：區塊大小
* `l`：指向左子節點（較小的區塊）
* `r`：指向右子節點（較大的區塊）
---
`remove_free_tree` 用來從 BST 中移除 `target` 節點，遵循標準的 BST 刪除操作。
1. 找到 `target` 節點
```c
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
```
* `find_free_tree()` 會在 BST 中找到 `target` 並返回它的指標。
* `node_ptr` 是指向 `target` 指標的指標，方便後續修改樹的結構。
2. 判斷 `target` 節點的子節點情況
* Case 1: `target` 有兩個子節點（同時擁有左、右子樹）
```c
/* 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 (EEEE)
pred_ptr = FFFF;
/* Verify the found predecessor using a helper function (for debugging).
*/
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
/* 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);
}
}
```
1. 找到前驅節點 `predecessor` ，就是 `target` 左子樹中最大（最右）的節點
2. 使用 `assert()` 來做驗證 `find_predecessor_free_tree()` 的，確保 `pred_ptr` 是正確的
3. 用 `pred_ptr` 替換 `target`
* 如果 `pred_ptr` 就是 `target->l`
* 用前驅節點取代 `target`
* 接回原本的右子樹
* 如果 `pred_ptr` 在 `target->l` 更深的位置
* 移除前驅節點
* 用前驅節點取代 `target`
* Case 2: `target` 只有一個子節點
```c
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
```
直接用 `target` 唯一的子節點取代它。
* Case 3: `target` 沒有子節點
```c
*node_ptr = NULL;
```
直接刪除該節點。
3. 清除 `target` 的指標
```c
/* Clear the removed node's child pointers to avoid dangling references. */
target->l = NULL;
target->r = NULL;
```
防止 `target` 仍然指向舊的子節點，避免潛在的 dangling pointer 問題。
範例：
```
[50]
/ \
[30] [70]
/ \ / \
[20] [40][60] [80]
```
Case 1：`20` 沒有子節點，直接刪除。
```
[50]
/ \
[30] [70]
\ / \
[40] [60] [80]
```
Case 2：`30` 只有一個右子節點 (`40`)，讓 `40` 直接取代 `30`。
```
[50]
/ \
[40] [70]
/ \
[60] [80]
```
Case 3：`50` 有左右子節點，找前驅節點 = `40`（左子樹的最大值）。用 `40` 替換 `50`，然後刪除 `40`
```
[40]
\
[70]
/ \
[60] [80]
```
#### 延伸問題 2
> 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
### 測驗 [`3`](https://hackmd.io/@sysprog/linux2025-quiz1?stext=8296%3A5%3A0%3A1742717039%3AaNQwCv)
#### 延伸問題 1
> 解釋上述程式碼運作原理
#### 延伸問題 2
> 研讀〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
## 2025q1 第 2 週測驗題
### 測驗 [`1`](https://hackmd.io/@sysprog/linux2025-quiz2?stext=497%3A5%3A0%3A1742053087%3AvGUhXy)
Stable Sorting：在排序過程中，若兩個元素的值相同，它們的原始相對順序不會改變。
```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 = list_first_entry(head, struct listitem, list);
list_del(&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
list_move_tail(&item->list, &list_greater);
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
此程式碼的核心概念是 「分割」+「遞迴排序」+「合併」，假設我們有以下的鏈結串列：
```c
[ 5 ] -> [ 3 ] -> [ 8 ] -> [ 2 ] -> [ 7 ]
```
1. 選擇基準點（Pivot）
* `list_first_entry(head, struct listitem, list)` 取得 `head` 串列中的第一個節點作為基準點 `pivot`。
```c
pivot = 5
```
* `list_del(&pivot->list);` 從 `head` 中移除 `pivot`。
```c
[ 3, 8, 2, 7 ]
```
2. 走訪串列並分割到 `list_less` 和 `list_greater`
遍歷 head 中的所有元素：
* 如果 `item` 的數值 小於 pivot，則將 `item` 移動到 `list_less`。
```c
list_less = [ 3, 2 ]
```
* 否則，將 `item` 移動到 `list_greater`。
```c
list_greater = [ 8, 7 ]
```
3. 使用 `list_quicksort` 函式，遞迴對 `list_less` 和 `list_greater` 進行排序
* 遞迴排序 `list_less`
```c
Pivot = 3
list_less = [2]
list_greater = []
```
* 遞迴排序 `list_greater`
```c
Pivot = 8
list_less = [7]
list_greater = []
```
4. 合併排序後的結果
* 將 `pivot` 放回 `head`：
`list_add(&pivot->list, head);` 將 `pivot` 放到 `head` 串列的開頭
* 合併 `list_less`（已排序）到 `head`
* 合併 `list_greater`（已排序）到 `head` 的尾端
```c
[ 2 ] -> [ 3 ] -> [ 5 ] -> [ 7 ] -> [ 8 ]
```
#### 延伸問題 1
> 解釋上方程式碼運作原理，改進 `random_shuffle_array` 也探討 `list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting
#### 延伸問題 2
> 將程式碼整合進 [lab0](https://hackmd.io/@sysprog/linux2025-lab0) 提及的 `qtest`，並探討環狀雙向鏈結串列的排序效能，並善用 [perf](https://hackmd.io/@sysprog/linux-perf) 一類的效能分析工具，探討包含 Linux 核心 [list_sort](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 在內排序實作的效能表現並充分解釋
### 測驗 [`2`](https://hackmd.io/@sysprog/linux2025-quiz2?stext=4504%3A5%3A0%3A1742130777%3AeEZNJj)
#### 理論分析
> [參考](http://hackmd.io/l4--gpsZQBiEI5LKS1lDvg?view#%E6%AA%A2%E8%A8%8E%E7%AC%AC%E4%BA%8C%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
二進位系統：
$(b_nb_{n-1}\dots b_1b_0)_2^2 = (b_n\times 2^n + b_{n-1}\times 2^{n-1}+\dots b_ 1\times2^{1} +b_0\times2^0)^2$
從最高位元開始，依序決定 $b_i$ 是 1 或 0
範例：
$(63)_{10} = (011111)_2 = (b_2\times 2^2 + b_{1}\times 2^{1}+b_0\times2^0)^2$
$(4)^2 < 63$，故 $b_2 = 1$
$(4 + 2)^2 < 63$，故 $b_1 = 1$
$(4 + 2 + 1)^2 < 63$，故 $b_0 = 1$
---
#### 程式實作 - clz
`clz2()`：計算一個 32 位元整數的 leading zeros，即數字前面有多少個 0。
```c
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};
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 == 3)
return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
```
範例分析：
```c
clz2(0x000003F0, 0)
```
**第一次遞迴(c == 0)**
```c
upper = (x >> (16 >> 0)); // x >> 16
lower = (x & (0xFFFF >> mask[0])); // x & 0xFFFF
```
* `upper = 0x0000`，取高 16-bit
* `lower = 0x03F0`，取低 16-bit
* `upper == 0`，所以走：
```c
(16 >> 0) + clz2(lower, 1) // 16 + clz2(0x03F0, 1)
```
**第二次遞迴(c == 1)**
```c
upper = (x >> (16 >> 1)); // x >> 8
lower = (x & (0xFFFF >> mask[1])); // x & (0xFFFF >> 8)
```
* `upper = 0x0003`，取高 24-bit
* `lower = 0x00F0`，取低 8-bit
* `upper != 0`，所以走：
```c
clz2(upper, 2) // clz2(0x0003, 2)
```
**第三次遞迴(c == 2)**
```c
upper = (x >> (16 >> 2)); // x >> 4
lower = (x & (0xFFFF >> mask[2])); // x & (0xFFFF >> 12)
```
* `upper = 0x0000`，取高 28-bit
* `lower = 0x0003`，取低 4-bit
* `upper == 0`，所以：
```c
(16 >> 2) + clz2(lower, 3) // 4 + clz2(0x0003, 3)
```
**第四次遞迴(c == 3)**
```c
upper = (x >> (16 >> 3)); // x >> 2
lower = (x & (0xFFFF >> mask[3])); // x & (0xFFFF >> 14)
```
* `upper = 0x0000`，取高 30-bit
* `lower = 0x0003`，取低 2-bit
* `upper == 0`，所以：
```c
return 2 + magic[0x0003] // magic[3] = 0
```
回推回去：
```c
clz2(0x000003F0, 0) = 16 + 4 + 2 = 22
```
結果是 22 個前導零。
---
`clz64()` 計算 64 位元 leading zeros
* 如果 x 的高 32 位元不為 0，就計算高 32 位的 `clz32()`。
* 若 x 的高 32 位元為 0，則計算低 32 位元的 `clz32()`，並加上 32。
```c
#define clz32(x) clz2(x, 0)
static inline int clz64(uint64_t x)
{
/* If the high 32 bits are nonzero, count within them.
* Otherwise, count in the low 32 bits and add 32.
*/
return (x >> 32) ? clz32((uint32_t) (x >> 32)) : clz32((uint32_t) x) + 32;
}
```
---
#### 程式實作 - sqrti
`sqrti()`：整數開平方根
參考 [`<rota1001>`](https://hackmd.io/@rota1001/linux2025-homework2#%E6%95%B4%E6%95%B8%E9%96%8B%E5%B9%B3%E6%96%B9%E6%A0%B9) 的作法，以改進程式的觀點來理解程式碼。
##### 初版程式
1. 平方根暫存
定義 $$p_i=\sum^{\frac{\text{shift}}{2}}_{j=i}a_j$$
其中 $a_j$ 是 $2^j$ 或 $0$，取決於第 $j$ 個位元是不是 $1$。
假設 $\text{shift} = 4$，則
\begin{align}
&p_2 = a_2 \\
&p_1 = a_1 + a_2 = p_2 + a_1 \\
&p_0 = a_0 + a_1 + a_2 = p_1 + a_0
\end{align}
可推得一般式 $$p_i = p_{i+1} + a_i$$
因此 $p$ 的更新式可寫為 $$p_i = p_{i+1} + 2^i$$
對應程式碼為 `p += (1 << i)`
2. 檢查條件
每次更新都檢查 $N\geq p_i^2$ 有沒有成立，令 $$x_{i+1} = N - p_{i+1}^2$$
又 $$p_i^2 = (p_{i+1} + 2^i)^2 = p_{i+1}^2 + 2^{i+1}\cdot p_{i+1} + 2^{2i}$$
則可以改成檢查: $$x_{i+1} + p_{i+1}^2\geq p_{i+1}^2 + 2^{i+1}\cdot p_{i+1} + 2^{2i}$$
左右消去 $p_{i+1}^2$ 得 $$x_{i+1}\geq 2^{i+1}\cdot p_{i+1} + 2^{2i}$$
對應程式碼為 `x >= b`，其中 `b = (p << (i + 1)) + (1 << (2 * i))`
3. 待處理數的更新
\begin{align}
x_{i}
&= N - p_{i}^2 \\
&= N - p_{i+1}^2 - 2^{i+1}\cdot p_{i+1} - 2^{2i} \\
&= x_{i+1} - (2^{i+1}\cdot p_{i+1} + 2^{2i})
\end{align}
對應程式碼為 `x -= b`
此部分的完整程式碼為:
```c
uint64_t sqrti_simple(uint64_t x)
{
uint64_t p = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
for(int i = (shift / 2); i >= 0; i--) {
uint64_t b = (p << (i + 1)) + (1 << (2 * i));
if (x >= b) {
x -= b;
p += (1 << i);
}
}
return p;
}
```
##### 改進位移運算
假設新的變數
$$y_i = p_i \times 2^i$$
1. 平方根暫存
$$p_i = p_{i+1} + 2^i$$
同乘 $2^i$
$$2^ip_i=2^ip_{i+1}+2^{2i}$$
則可以改寫成
$$y_i=2^{-1}y_{i+1}+2^{2i}$$
對應程式碼為 `y = (y >> 1) + (1 << (2 * i))`
2. 檢查條件
$$x_{i+1}\geq 2^{i+1}\cdot p_{i+1} + 2^{2i} = y_{i+1} + 2^{2i}$$
對應程式碼為 `x >= b`，其中 `b = y + (1 << (2 * i))`
此部分的完整程式碼為:
```c
uint64_t sqrti_simple(uint64_t x)
{
uint64_t y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
for(int i = (shift / 2); i >= 0; i--) {
uint64_t b = y + (1 << (2 * i));
y >>= 1;
if (x >= b) {
x -= b;
y += (1 << (2 * i));
}
}
return y;
}
```
##### 改寫成原題目的程式碼
將 `(1 << (2 * i))` 替換成 `m`
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while(m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
* `clz64(x)` ：計算 `x` 前導零的數量
* `total_bits - 1 - clz64(x)` ：取得 `x` 最高有效位的索引
* `& ~1` ：將數值的最右邊一位 (最低位) 清零，確保結果為偶數
* `m = 1ULL << shift` ：將 `m` 的值令為 $2^{\text{shift}}$
* `1ULL`：代表 1，且是 `uint64_t` 類型 (unsigned long long)
* `shift`：是一個偶數，確保 `m` 是 4 的次方數（即 1, 4, 16, ...）
#### 延伸問題 1
>解釋上述程式碼，並探討擴充為 $\lceil \sqrt{x}) \rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
第一次實作:
```c
uint64_t ceil_sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
if (y*y != x)
y += 1;
}
return y;
}
```
上面的程式碼無法正確處理 `ceil_sqrti(64)` 的狀況
```
ceil_sqrti(64) = 9
```
原因是 `x` 已經不是最初的值，因此使用 `y*y != x` 來判斷會發生錯誤。作以下改變即可得到正確答案:
```diff
uint64_t ceil_sqrti(uint64_t x)
{
+ uint64_t origin = x;
...
- if (y*y != x)
+ if (y*y != origin)
y += 1;
}
return y;
}
```
```
ceil_sqrti(64) = 8
```
然而，原本的 sqrti 「沒有」用到乘法，因此改寫過的程式碼也「不該用乘法」。
因為 $x$ 的更新式為 $x_{i} = N - p_{i}^2$，故若 $x$ 為完全平方數，最終值會是 $0$ 。判斷式則改為:
```diff
uint64_t ceil_sqrti(uint64_t x)
{
...
- if (y*y != origin)
+ if (x != 0)
y += 1;
}
return y;
}
```
如此一來即可避免使用成本較高的乘法計算。
#### 延伸問題 2
>參照[計算機結構測驗題 C](https://hackmd.io/@sysprog/arch2024-quiz3-sol#Problem-C) 及其[注釋](https://hackmd.io/@sysprog/HJKRbSAVJl#Problem-C30)，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 `sqrtf`，確保符合 IEEE 754 規格。對照 [sqrtf, rsqrt, reciprocal implementations in Arm assembly](https://github.com/picolibc/picolibc/issues/956)
#### 延伸問題 3
>參照[從 √2 的存在談開平方根](從 √2 的存在談開平方根的快速運算)的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能。一旦發現效能改進的機會，可準備提交改進 `int_sqrt` 程式碼到 Linux 核心
### 測驗 [`3`](https://hackmd.io/@sysprog/linux2025-quiz2?stext=7569%3A5%3A0%3A1742185627%3AeBp3ey)
> [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
實作 [Two Sum](https://leetcode.com/problems/two-sum/)
使用 [hash table](https://en.wikipedia.org/wiki/Hash_table) (以下簡稱 HT) 記錄缺少的那一個值 (即 `target - nums[i]`) 和對應的索引。考慮以下案例:
```c
nums = [2, 11, 7, 15]
target = 9
```
| Index `i` | `nums[i]` | `target - nums[i]` | HT 是否有 `nums[i]` ? | 操作 | HT 狀態 |
| --------- | --------- | ------------------ | --------------------- | -------------------------- | ------------------ |
| 0 | 2 | 9-2=7 | No | 加入 `HT[7] = 0` | `{ 7:0 }` |
| 1 | 11 | 9-11=-2 | No | 加入 `HT[-2] = 1` | ` { 7: 0, -2: 1 }` |
| 2 | 7 | 9-7=2 | Yes | 回傳 `[2, HT[7]] = [2, 0]` | `{ 7: 0, -2: 1 }` |
參考 Linux 原始碼中 [type.h](https://elixir.bootlin.com/linux/v6.13.4/source/include/linux/types.h#L194-L204) ：
```c
struct list_head {
struct list_head *next, *prev;
};
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
* `hlist_head` 只有 `first`，節省空間
* `hlist_node` 使用 `pprev`（指向指標的指標）
#### 檢索程式碼
1. `find_key()`：在 hash table 中查找 key
```c
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
// 遍歷 bucket 中的 hlist 鏈結串列
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
// 比對 key，找到則返回 kn
if (kn->key == key)
return kn;
}
return NULL;
}
```
* 使用 `hash()` 計算 key 應該存放的 bucket（即 `hlist_head`）。
* `map->ht` 是 哈希表的 bucket 陣列，透過 `hash()` 計算索引，取得對應的 `hlist_head *head`。
* `p` 只是 `hlist_node`，但 `hash_key` 是：
```c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
2. `map_get()`：查找 key 並返回 data
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key); //利用 find_key() 找到 key
return kn ? kn->data : NULL; // 如果 kn 存在，返回 kn->data，否則返回 NULL
}
```
#### 新增操作
`map_add()`：將 `(key, data)` 新增至哈希表 (`map_t`) 中
```c
void map_add(map_t *map, int key, void *data)
{
// 檢查 key 是否已存在（避免重複）
struct hash_key *kn = find_key(map, key);
if (kn)
return;
// 分配記憶體 儲存新的 (key, data)
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)]; // 取得對應的 bucket
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;
}
```
* `h`： key 應該存放的 bucket
* `n`： 新節點 (`hlist_node`)
* `first`： 當前 bucket (`hlist_head`) 的第一個節點
Graphviz 練習：
> 新增 test.dot
> `$ dot -Tpng test.dot -o output.png`
(To be done...)
#### 釋放記憶體的操作
```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);
}
```
#### 主體程式碼
```c
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
// 如果 malloc 失敗，則跳轉到 bail 進行清理
if (!ret)
goto bail;
// 走訪 nums ，查找匹配的數
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found, 其索引存於 p */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
// 若 target - nums[i] 不在哈希表中，則存入 nums[i]
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map); // 清理哈希表，釋放記憶體
return ret;
}
```
* `10`：哈希表的 bit 數，意即 bucket 大小為 $2^{10} = 1024$
* `ret`：用來存放找到的索引值，最多只有兩個數，所以分配 2 個整數大小的記憶體
* `ret[0] = i`：目前數字的索引
* `ret[1] = *p`：匹配數的索引，來自哈希表
#### 延伸問題 1
> 解釋上述程式碼運作原理，應提供測試程式碼
針對 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)，提供更多圖例並揣摩 Linux 核心開發者
#### 延伸問題 2
> 進行《[The Art of Computer Programming](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S
注意: Linux 核心內部大量使用 hash table，但並非每處的雜湊函數都滿足減少碰撞及避免 clustering 現象的原則，也就是存在若干改進空間
#### 延伸問題 3
> 探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素
Google Drive
Gist
Clipboard
Sign in with Wallet
