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

1. 在開頭插入

   ​​​​/* 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. 在結尾插入

   ​​​​/* 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. 重設串列並插入

   ​​​​/* 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 為例:

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

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

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

4. 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 刪除操作。

1. 找到 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 指標的指標，方便後續修改樹的結構。

2. 判斷 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);
     ​​​​​​​​    }
     ​​​​​​​​}
     

     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 只有一個子節點

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

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

   • Case 3: target 沒有子節點

     ​​​​​​​​*node_ptr = NULL;
     

     直接刪除該節點。

3. 清除 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

       [40]
         \
         [70]
        /   \
      [60]  [80]

延伸問題 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 ]

1. 選擇基準點（Pivot）

   • list_first_entry(head, struct listitem, list) 取得 head 串列中的第一個節點作為基準點 pivot。
     ​​​​​​​​pivot = 5
     

   • list_del(&pivot->list); 從 head 中移除 pivot。
     ​​​​​​​​[ 3, 8, 2, 7 ]
     

2. 走訪串列並分割到 list_less 和 list_greater
   遍歷 head 中的所有元素：

   • 如果 item 的數值 小於 pivot，則將 item 移動到 list_less。
     ​​​​​​​​list_less = [ 3, 2 ]
     

   • 否則，將 item 移動到 list_greater。
     ​​​​​​​​list_greater = [ 8, 7 ]
     

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

   • 遞迴排序 list_less
     ​​​​​​​​Pivot = 3
     ​​​​​​​​list_less = [2]
     ​​​​​​​​list_greater = []
     

   • 遞迴排序 list_greater
     ​​​​​​​​Pivot = 8
     ​​​​​​​​list_less = [7]
     ​​​​​​​​list_greater = []
     

4. 合併排序後的結果

   • 將 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

理論分析

參考

使用 Digit-by-digit 方法，單純加減與位移運算來開平方根。先觀察其規律

$(a+b{)}^2=a^2+(2a+b)b$

$\begin{array}{rl}(a+b+c{)}^2& =((a+b)+c{)}^2\\ & =(a+b{)}^2+(a+b)c+c(a+b)+c^2\\ & =(a+b{)}^2+(2(a+b)+c)c\\ & =a^2+(2a+b)b+(2(a+b)+c)c\end{array}$

$\begin{array}{rl}(a+b+c+d{)}^2& =((a+b+c)+d{)}^2\\ & =(a+b+c{)}^2+(a+b+c)d+d(a+b+c)+d^2\\ & =(a+b+c{)}^2+(2(a+b+c)+d)d\\ & =a^2+(2a+b)b+(2(a+b)+c)c+(2(a+b+c)+d)d\end{array}$

考慮一般化的平方和

$\begin{array}{rl}{N}^2& =(a_n+a_{n-1}+\cdots +a_2+a_1+a_0{)}^2\\ & =(a_n+a_{n-1}+\cdots +a_2+a_1{)}^2+Y_0\\ & =(a_n+a_{n-1}+\cdots +a_2{)}^2+Y_1+Y_0\\ & =Y_n+Y_{n-1}+\cdots +Y_1+Y_0\end{array}$

其中

$Y_m=[\left(2\sum _{i=m+1}^n{a}_i\right)+a_m]a_m=(2P_{m+1}+a_m)a_m$

$P_m=P_{m+1}+a_m,\text{for }1\le m<n$

---

數值系統在二進位表示下為：

$x=(00b_0{b}_2\dots b_{n-1}{b}_n{)}_2^2$

轉十進位如下：

$\sum _{i=0}^n{b}_i\times 2^{n-i}$

假設

$N^2$ 可以用二進位系統逼近：

$\begin{array}{rl}{N}^2& \approx (b_n\times 2^0+b_{n-1}\times 2^1+\dots b_1\times 2^{n-1}+b_0\times 2^n{)}^2\\ & =(a_n+a_{n-1}+\dots a_1+a_0{)}^2\end{array}$

(To be done…)

---

程式實作

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)

第一次遞迴

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)

第二次遞迴

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)

第三次遞迴

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)

第四次遞迴

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(0x03F0, 1) = 4 + 2 = 6
clz2(0x000003F0, 0) = 16 + 6 = 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;
}

---

實作整數開平方根：

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)) & ~1;
    m = 1ULL << shift;

    while (m) {
        uint64_t b = y + m;
        y >>= 1;
        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }
    return y;
} 

• m ：一個暫存變數，負責控制當前測試的平方數。
• y ：最終結果（平方根），最初設為 0。

找出最高位元 (最高的 1-bit 位置) 並對齊至偶數位

int shift = (total_bits - 1 - clz64(x)) & ~1;

• clz64(x) ：計算 x 前導零的數量
• total_bits - 1 - clz64(x) ：取得 x 最高有效位的索引
• & ~1 ：將數值的最右邊一位 (最低位) 清零，確保結果為偶數
• m = 1ULL << shift ：初始化變數 m 為一個 4 的次方數
  $4^k$
  • 1ULL：代表 1，並確保它是 uint64_t 類型 (unsigned long long)
  • shift：是一個偶數，確保 m 是
    $4^k$（平方數）
  • 1ULL << shift：將 1 左移 shift 位，等於
    $2^{shift}$

逐位逼近計算平方根

while (m) {
    uint64_t b = y + m;
    y >>= 1;
    if (x >= b) {
        x -= b;
        y += m;
    }
    m >>= 2;
}

• 初始化 m 為
  $4^k$，從最高位開始測試。
• 每次迴圈：
  • b = y + m，嘗試將 m 加到 y 中。
  • y >>= 1，將 y 右移一位，準備更新平方根的估計值。
  • 如果 x >= b，說明 b*b 不超過 x，則：
    • x -= b，更新剩餘數值。
    • y += m，將 m 加到 y 中，表示這一位是有效的平方根部分。
  • m >>= 2，每次 m 右移 2 位，因為平方數每次變化是
    $4^n$。

範例分析

x = 36 (0b100100)

1. 初始化
   ​​​​clz64(36) = 58 // 36 的二進位是 `0000...00100100`
   ​​​​shift = 4 // 64 - 1 - 58 = 5  // 5 & ~1 = 4`
   ​​​​m = 16 (0b10000) // m = 1 << 4 = 16
   ​​​​y = 0
   

2. 第一輪
   ​​​​b = y + m // 0 + 16 = 16
   ​​​​y >>= 1 // y 仍為 0
   ​​​​x >= b // (36 >= 16) → x -= 16 → x = 20
   ​​​​y += m // y = 16
   ​​​​m >>= 2 // m = 4
   

3. 第二輪
   ​​​​b = y + m // 16 + 4 = 20
   ​​​​y >>= 1 // y = 8
   ​​​​x >= b // (20 >= 20) → x -= 20 → x = 0
   ​​​​y += m // y = 12
   ​​​​m >>= 2 // m = 1
   

4. 第三輪
   ​​​​b = y + m // 12 + 1 = 13
   ​​​​y >>= 1 // y = 6
   ​​​​x < b // (0 < 13) → x 不變
   ​​​​m >>= 2 // m = 0（迴圈結束）
   

最後 y = 6，即 sqrt(36) = 6。

延伸問題 1

解釋上述程式碼，並探討擴充為

$\lceil \sqrt{x})\rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

延伸問題 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（指向指標的指標）

檢索程式碼

1. 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;
     ​​​​​​​​};
     

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

釋放記憶體的操作

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 核心開發者變更程式碼的考量因素