2025q1 Homework2 (quiz1+2)

contributed by < liangchingyun >

2025q1 第 1 週測驗題

測驗 `1`

延伸問題 1

解釋上方程式碼運作原理

巨集定義

#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() : 若測試失敗，則直接回傳錯誤訊息。

重設鏈結串列

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() 包含三種測試情境

在開頭插入

/* 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)。

在結尾插入

/* 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)。

重設串列並插入

/* 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. 類似，但主要是確認插入結果仍然正確。

測試執行

int tests_run = 0;

static char *test_suite(void)
{
    my_run_test(test_list);
    return NULL;
}

test_suite() 執行 test_list()，並計算測試數量。

主函式

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 函式:

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 為例:

p 初始指向鏈結串列的頭指標。

for 迴圈會遍歷鏈結串列，直到找到 before 節點。

*p = item; 將前一個節點的 next 指向 item，完成插入。

item->next = before; 讓 item 指向 before，確保鏈結不會斷開。

延伸問題 2

在現有的程式碼基礎上，撰寫合併排序操作

測驗 `2`

延伸問題 1

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

這段程式碼的功能是從二元搜尋樹 (BST) 中移除特定的節點，這個 BST 用於管理記憶體分配中的「空閒區塊 (free blocks)」。

結構體

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

block_t 代表一個記憶體區塊，具有：
* size：區塊大小
* l：指向左子節點（較小的區塊）
* r：指向右子節點（較大的區塊）

remove_free_tree 用來從 BST 中移除 target 節點，遵循標準的 BST 刪除操作。

找到 target 節點
```
/* 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 指標的指標，方便後續修改樹的結構。

判斷 target 節點的子節點情況

Case 1: 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 (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);
    }
}

找到前驅節點 predecessor ，就是 target 左子樹中最大（最右）的節點
使用 assert() 來做驗證 find_predecessor_free_tree() 的，確保 pred_ptr 是正確的
用 pred_ptr 替換 target
- 如果 pred_ptr 就是 target->l
  - 用前驅節點取代 target
  - 接回原本的右子樹
- 如果 pred_ptr 在 target->l 更深的位置
  - 移除前驅節點
  - 用前驅節點取代 target

Case 2: target 只有一個子節點

block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;

直接用 target 唯一的子節點取代它。

Case 3: target 沒有子節點
```
*node_ptr = NULL;
```
直接刪除該節點。

清除 target 的指標

/* 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

延伸問題 2

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

測驗 `3`

延伸問題 1

解釋上述程式碼運作原理

延伸問題 2

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

2025q1 第 2 週測驗題

測驗 `1`

Stable Sorting：在排序過程中，若兩個元素的值相同，它們的原始相對順序不會改變。

{
    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);
}

此程式碼的核心概念是「分割」+「遞迴排序」+「合併」，假設我們有以下的鏈結串列：

[ 5 ] -> [ 3 ] -> [ 8 ] -> [ 2 ] -> [ 7 ]

選擇基準點（Pivot）
- list_first_entry(head, struct listitem, list) 取得 head 串列中的第一個節點作為基準點 pivot。
```
pivot = 5
```
- list_del(&pivot->list); 從 head 中移除 pivot。
```
[ 3, 8, 2, 7 ]
```
走訪串列並分割到 list_less 和 list_greater
遍歷 head 中的所有元素：
- 如果 item 的數值小於 pivot，則將 item 移動到 list_less。
```
list_less = [ 3, 2 ]
```
- 否則，將 item 移動到 list_greater。
```
list_greater = [ 8, 7 ]
```

使用 list_quicksort 函式，遞迴對 list_less 和 list_greater 進行排序

遞迴排序 list_less

Pivot = 3
list_less = [2]
list_greater = []

遞迴排序 list_greater

Pivot = 8
list_less = [7]
list_greater = []

合併排序後的結果
- 將 pivot 放回 head：
  list_add(&pivot->list, head); 將 pivot 放到 head 串列的開頭
- 合併 list_less（已排序）到 head
- 合併 list_greater（已排序）到 head 的尾端
```
[ 2 ] -> [ 3 ] -> [ 5 ] -> [ 7 ] -> [ 8 ]
```

延伸問題 1

解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

延伸問題 2

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

測驗 `2`

理論分析

參考

二進位系統：

(b_{n} b_{n - 1} \dots b_{1} b_{0})_{2}^{2} = (b_{n} \times 2^{n} + b_{n - 1} \times 2^{n - 1} + \dots b_{1} \times 2^{1} + b_{0} \times 2^{0})^{2}

從最高位元開始，依序決定

b_{i}

是 1 或 0

範例：

(63)_{10} = (011111)_{2} = (b_{2} \times 2^{2} + b_{1} \times 2^{1} + b_{0} \times 2^{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。

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);
}

範例分析：

clz2(0x000003F0, 0)

第一次遞迴(c == 0)

upper = (x >> (16 >> 0));  // x >> 16
lower = (x & (0xFFFF >> mask[0]));  // x & 0xFFFF

upper = 0x0000，取高 16-bit
lower = 0x03F0，取低 16-bit
upper == 0，所以走：

(16 >> 0) + clz2(lower, 1)  // 16 + clz2(0x03F0, 1)

第二次遞迴(c == 1)

upper = (x >> (16 >> 1));  // x >> 8
lower = (x & (0xFFFF >> mask[1]));  // x & (0xFFFF >> 8)

upper = 0x0003，取高 24-bit
lower = 0x00F0，取低 8-bit
upper != 0，所以走：

clz2(upper, 2)  // clz2(0x0003, 2)

第三次遞迴(c == 2)

upper = (x >> (16 >> 2));  // x >> 4
lower = (x & (0xFFFF >> mask[2]));  // x & (0xFFFF >> 12)

upper = 0x0000，取高 28-bit
lower = 0x0003，取低 4-bit
upper == 0，所以：

(16 >> 2) + clz2(lower, 3)  // 4 + clz2(0x0003, 3)

第四次遞迴(c == 3)

upper = (x >> (16 >> 3));  // x >> 2
lower = (x & (0xFFFF >> mask[3]));  // x & (0xFFFF >> 14)

upper = 0x0000，取高 30-bit
lower = 0x0003，取低 2-bit
upper == 0，所以：

return 2 + magic[0x0003]  // magic[3] = 0

回推回去：

clz2(0x000003F0, 0) = 16 + 4 + 2 = 22

結果是 22 個前導零。

clz64() 計算 64 位元 leading zeros

如果 x 的高 32 位元不為 0，就計算高 32 位的 clz32()。
若 x 的高 32 位元為 0，則計算低 32 位元的 clz32()，並加上 32。

#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> 的作法，以改進程式的觀點來理解程式碼。

初版程式

平方根暫存
定義
$p_{i} = \sum_{j = i}^{\frac{shift}{2}} a_{j}$
其中
$a_{j}$ 是
$2^{j}$ 或
$0$ ，取決於第
$j$ 個位元是不是
$1$ 。

假設
$shift = 4$ ，則

$\begin{aligned} 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{aligned}$

可推得一般式
$p_{i} = p_{i + 1} + a_{i}$
因此
$p$ 的更新式可寫為
$p_{i} = p_{i + 1} + 2^{i}$
對應程式碼為 p += (1 << i)
檢查條件
每次更新都檢查
$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^{2 i}$
則可以改成檢查:
$x_{i + 1} + p_{i + 1}^{2} \geq p_{i + 1}^{2} + 2^{i + 1} \cdot p_{i + 1} + 2^{2 i}$
左右消去
$p_{i + 1}^{2}$ 得
$x_{i + 1} \geq 2^{i + 1} \cdot p_{i + 1} + 2^{2 i}$
對應程式碼為 x >= b，其中 b = (p << (i + 1)) + (1 << (2 * i))
待處理數的更新

$\begin{aligned} x_{i} & = N - p_{i}^{2} \\ = N - p_{i + 1}^{2} - 2^{i + 1} \cdot p_{i + 1} - 2^{2 i} \\ = x_{i + 1} - (2^{i + 1} \cdot p_{i + 1} + 2^{2 i}) \end{aligned}$

對應程式碼為 x -= b

此部分的完整程式碼為:

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}

平方根暫存

$p_{i} = p_{i + 1} + 2^{i}$

同乘
$2^{i}$

$2^{i} p_{i} = 2^{i} p_{i + 1} + 2^{2 i}$

則可以改寫成

$y_{i} = 2^{- 1} y_{i + 1} + 2^{2 i}$

對應程式碼為 y = (y >> 1) + (1 << (2 * i))
檢查條件

$x_{i + 1} \geq 2^{i + 1} \cdot p_{i + 1} + 2^{2 i} = y_{i + 1} + 2^{2 i}$

對應程式碼為 x >= b，其中 b = y + (1 << (2 * i))

此部分的完整程式碼為:

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

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^{shift}$
- 1ULL：代表 1，且是 uint64_t 類型 (unsigned long long)
- shift：是一個偶數，確保 m 是 4 的次方數（即 1, 4, 16, …）

延伸問題 1

解釋上述程式碼，並探討擴充為
$⌈ \sqrt{x}) ⌉$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

第一次實作:

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 來判斷會發生錯誤。作以下改變即可得到正確答案:

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

。判斷式則改為:

uint64_t ceil_sqrti(uint64_t x)
{
	...

-   if (y*y != origin)
+   if (x != 0)
        y += 1;
    } 
    return y;
}

如此一來即可避免使用成本較高的乘法計算。

延伸問題 2

參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly

延伸問題 3

參照[從 √2 的存在談開平方根](從 √2 的存在談開平方根的快速運算)的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能。一旦發現效能改進的機會，可準備提交改進 int_sqrt 程式碼到 Linux 核心

測驗 `3`

Linux 核心的 hash table 實作

實作 Two Sum

使用 hash table (以下簡稱 HT) 記錄缺少的那一個值 (即 target - nums[i]) 和對應的索引。考慮以下案例:

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 ：

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（指向指標的指標）

檢索程式碼

find_key()：在 hash table 中查找 key

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 是：

struct hash_key {
int key;
void *data;
struct hlist_node node;
};

map_get()：查找 key 並返回 data

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) 中

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…)

釋放記憶體的操作

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);
}

主體程式碼

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 實作，提供更多圖例並揣摩 Linux 核心開發者

延伸問題 2

進行《The Art of Computer Programming》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S
注意: Linux 核心內部大量使用 hash table，但並非每處的雜湊函數都滿足減少碰撞及避免 clustering 現象的原則，也就是存在若干改進空間

延伸問題 3

探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素

2025q1 Homework2 (quiz1+2)

2025q1 第 1 週測驗題

測驗 1

延伸問題 1

延伸問題 2

測驗 2

延伸問題 1

延伸問題 2

測驗 3

延伸問題 1

延伸問題 2

2025q1 第 2 週測驗題

測驗 1

延伸問題 1

延伸問題 2

測驗 2

理論分析

程式實作 - clz

程式實作 - sqrti

初版程式

改進位移運算

改寫成原題目的程式碼

延伸問題 1

延伸問題 2

延伸問題 3

測驗 3

檢索程式碼

新增操作

釋放記憶體的操作

主體程式碼

延伸問題 1

延伸問題 2

延伸問題 3

Read more

2025q1 Homework1 (lab0)

2025q1 Homework5 (assessment)

kxo

2025q1 Homework4 (quiz3+4)

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `1`

測驗 `2`

測驗 `3`