# 2025q1 Homework2 (quiz1+2)
contributed by <`MikazukiHikari`>

## quiz1

### 測驗 `1`
這段程式碼建立了一個簡單的測試框架，專門用來測試 `list.h` 內的鏈結串列函式


定義鏈結串列節點 `list_item_t`、單向鏈結串列 (list_t)，`head` 指向鏈結串列的第一個節點。如上圖所示：

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

程式脈絡：
先看`main` ，它呼叫了 `test_suite`的巨集`my_run_test`，再呼叫`test_list`，之後便開始進行`list_insert_before`的測試，過程中透過巨集`my_assert`判斷是否有錯誤，若有則回傳對應的錯誤訊息；沒有的話回傳`NULL`，回傳的結果會給 `result` ，最後輸出`result`、其對應的 `PASS / ERROR` 以及總共跑的次數。
#### 巨集 my_assert, my_run_test
`my_assert` 用來檢查條件是否成立，如果條件 test 為 false，則回傳錯誤訊息 message。
`my_run_test` 用來執行測試函式，如果測試函式回傳錯誤訊息，就直接終止測試。
#### 初始化鏈結串列 list_reset
初始化1000個`list_item`；value設為1~1000
#### 測試函式list_insert_before
根據題目說明可知`list_insert_before`的參數(`l`, `before`, `item`)及其意義


使用`for`迴圈從 i = 0~999 執行 1000 次的 `list_insert_before`

for (size_t i = 0; i < N; i++)
        list_insert_before(&l, l.head, &items[i]);

也就是說會等於在有1000次的for迴圈，每次用`list_insert_before` 在鏈結串列的最前面插入 對應次數(0~999) 的`list_item`，預期可以得到鏈結串列為：


之後利用巨集`assert`檢查插入元素的`value`是否和預期相同。
第二次測試則也是1000個`list_item`，但是這次全插在鏈結串列最後面，其他同上，第三次同第二次。


接著開始解題，運用指針的指針技巧，`p` 是指向 list_item_t * 的指標，因此只有可能用於指向 `head` 或是 `next`，它也作為 for 迴圈的索引，根據描述，我們需要遍歷整個鏈結串列直到找到`before`，因此需要從頭開始，所以 `AAAA` 的答案一定是 `head` 的地址，因此答案為`&l->head`。
之後`item`必須插入`before`的前面，因此需要遍歷整個鏈結串列直到找到`before`然後跳出迴圈，因此`BBBB`的答案應為`before`。
而`CCCC` 為 `&(*p)->next`，如此可以使原本`p`指向下個節點。
`DDDD` = `before` ，確保新插入的 `item->next` 能指向`before`使鏈結串列完整連接。


#### 延伸問題：在現有的程式碼基礎上，撰寫合併排序操作
在 `merge_two_list` 使用間接指標，可以不用額外分配記憶體空間給 `head`

static inline list_item_t *merge_two_list(list_item_t *l1, list_item_t *l2)
{
    list_item_t *head = NULL, **ptr = &head;

    while (l1 && l2) {
        if (l1->value < l2->value) {
            *ptr = l1;
            l1 = l1->next;
        } else {
            *ptr = l2;
            l2 = l2->next;
        }
        ptr = &(*ptr)->next;
    }
    *ptr = l1 ? l1 : l2; //直接附加剩餘的部分
    return head;
}

static list_item_t *merge_sort_list(list_item_t *head) {
    if (!head || !head->next){
        return head; //空或單一節點的情況
    } 
    //使用快慢指標找出中點
    list_item_t *slow = head, *mid;
    for (list_item_t *fast = head; fast->next && fast->next->next; fast = fast->next->next) {
        slow = slow->next;
    }
    mid = slow->next;
    slow->next = NULL; //斷開鏈結，分成左右兩半

    //遞迴排序
    list_item_t *left = merge_sort_list(head);
    list_item_t *right = merge_sort_list(mid);

    //合併排序後的左右鏈結
    return merge_two_list(left, right);
}

### 測驗 `2`
`block_t` ： 實現二元搜尋樹的結構體，每個節點都代表一個記憶體區塊。
`find_free_tree`：是個搜尋函式，會回傳指向 `target` 的指標 `node_ptr`。
`find_predecessor_free_tree`：用來尋找某個節點的in-order predecessor，也就是在 BST 中小於某個節點的最大節點。
`remove_free_tree`：負責從 BST 中移除指定的節點，並確保樹的結構仍然維持 BST 的特性，也是這段程式碼的重點。
1. 刪除的節點沒有子節點 → 直接刪除`*node_ptr = NULL;`。
2. 刪除的節點只有一個子節點 → 讓它的子節點取代它的位置。
3. 刪除的節點有兩個子節點 → 透過 `find_free_tree` 找到目標的位置，`**node_ptr` 指向目標位置，`**pred_ptr` 指向左子樹的根節點。接下來，需要找出 in-order predecessor ，也就是左子樹中最大的節點。
下一行的 `while` 迴圈持續向右遍歷左子樹，直到找到最右側的節點。
因此`EEEE`為 `(*pred_ptr)->r` 才能在已經找不到右子節點時跳出迴圈；而`FFFF`則為 `pred_ptr` 所指向的節點的右子節點的地址，因此為`&(*pred_ptr)->r`，如此才能使迴圈不斷向右遍歷。
之後透過`find_predecessor_free_tree`再次搜尋，並使用`assert`巨集檢查找到的 in-order predecessor 是否相同，若不相同則終止程式。
最後，把 `target` 替換為 `pred_ptr`，有兩種情況：
1. `pred_ptr` 剛好是 `target` 的左子節點，此時用 `pred_ptr` 替換 `target `；保留 `target` 的右子樹 。
2. `pred_ptr` 在 `target` 左子樹的更深處，先遞迴刪除 `pred_ptr` ，因為需要從 predecessor 的左子樹尋找它的 predecessor 。

#### 延伸問題：解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
以下參考 [rota1001](https://hackmd.io/@rota1001/linux2025-homework2#%E6%B8%AC%E9%A9%97-2) 大大的實作並改寫
這裡只要去實作 `find_free_tree` 和 `find_predecessor_free_tree` 這兩個函式就好
首先是 `find_free_tree` ，它在二元搜尋樹中搜尋最適合的區塊來存放`target`，優先檢查左子樹，看看是否有更小但仍然符合需求的區塊，以提高記憶體利用率；如果左子樹沒有適合的區塊，則檢查目前的節點 `*root` 是否足夠大；如果當前節點仍不夠大，則遞迴往右子樹尋找更大的區塊。如果發現所有的節點都比 `target` 的 `size` 還要小的話，就會回傳一個指向值為 `NULL` 的指標的指標

block_t **find_free_tree(block_t **root, block_t *target)
{
    if (!(*root))
        return root;
    if ((*root)->l && ((*root)->l->size >= target->size))
        return find_free_tree(&(*root)->l, target);

    if ((*root)->size >= target->size)
        return root;
    
    return find_free_tree(&(*root)->r, target);
}

接下來是`find_predecessor_free_tree`，在二元搜尋樹中尋找指定節點的前驅節點 (predecessor)，若某節點存在左子樹，則其 predecessor 為左子樹最右邊的節點。

block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    if (!node || !node->l)
        return NULL;  // 沒有左子樹，沒有前驅節點

    block_t *pred = node->l;
    while (pred->r)  // 找左子樹中的最大值
        pred = pred->r;
    
    return pred;
}

除此之外，為了測試額外添加了 `insert_tree` (插入節點) 和 `print_tree` (以中序遍歷列印樹)

void print_tree(block_t *node)
{
    if (!node)
        return;
    print_tree(node->l);
    printf("%ld ", node->size);
    print_tree(node->r);
}

void insert_tree(block_t **root, size_t size)
{
    if (!(*root)) {
        *root = malloc(sizeof(block_t));
        if(!(*root))
            return;
        (*root)->size = size;
        (*root)->l = (*root)->r = NULL;
        return;
    }
    if ((*root)->size < size){
        insert_tree(&(*root)->r, size);
    }else if ((*root)->size > size){
        insert_tree(&(*root)->l, size);
    }else{
        return; // 若已存在相同值，直接返回
    }
}

`insert_tree`和`print_tree`之範例測試：

block_t *root = NULL;
insert_tree(&root, 50);
insert_tree(&root, 30);
insert_tree(&root, 70);
insert_tree(&root, 20);
insert_tree(&root, 40);
insert_tree(&root, 60);
insert_tree(&root, 80);

二元搜尋樹結構：

        [50]
       /    \
     [30]    [70]
     /  \    /  \
   [20] [40][60] [80]

`print_tree(root)`：

20 30 40 50 60 70 80

然後依序插入 `0,3,6,9,2,5,8,1,4,7`，然後依照`0,4,8,2,6,1,5,9,3,7`的順序一個一個刪除：

int main()
{
    block_t *root = NULL;
    for (int i = 0; i < 10; i++) {
        insert_tree(&root, (i * 3) % 10);
    }
    print_tree(root);
    puts("");
    block_t new_block;
    for (int i = 0; i < 10; i++) {
        new_block.size = (i * 4) % 10;
        remove_free_tree(&root, &new_block);
        print_tree(root);
        puts("");
    }   
}

結果如下：

0 1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9
1 2 3 5 6 7 8 9
1 2 3 5 6 7 9
1 3 5 6 7 9
1 3 5 7 9
3 5 7 9
3 7 9
3 7
7

### 測驗 `3`
程式碼定義了一個 `node_t` 結構體，用來表示一個鏈結串列中的節點。使用了 `list_head` 來管理節點的鏈結關係，並使用 `value` 來紀錄數值。

typedef struct __node
{
    long value;
    struct list_head list;
} node_t;

#### 測試程式碼
1. `list_construct`：一個指向動態分配的 `node_t` 結構體的指標`node`，設定數值 `value`，將其插入到 `list_head` 後面。
2. `list_free`：使用 `list_for_each_entry_safe` ，逐一走訪節點，並釋放其空間。
3. `list_is_ordered`：檢查是否為降序以排列符合` quick_sort` 排序結果，遍歷整個鏈結串列並確認順序，如果發現某個 `entry->value < value`，代表未排序，回傳 `false` 。
4. `shuffle`：隨機打亂陣列順序，它實現了一個Fisher-Yates Shuffle，運作方式是從陣列的開頭開始，然後將當前元素與一個隨機選中的元素交換，這樣就可以在 `O(n)` 的時間複雜度內隨機打亂陣列。
5. `main`：主要流程是，初始化 `list_head`，產生 `test_arr` 並打亂順序，然後插入到鏈結串列，執行 `quick_sort` 進行排序，再用 assert() 確保排序結果正確，最後釋放所有記憶體。

#### 輔助函式
1. `list_tail`：使用遞迴得到鏈結串列最後一個節點。
2. `list_length`：逐一走訪節點以計算整個鏈結串列有多少節點。
3. `rebuild_list_link`：在 quick_sort 排序完後對每個節點的 `prev` 進行重建，因為quick_sort 僅以節點的`next`排序，因此需透過遍歷全部的節點的重建 `prev` ，之後還需要再將鏈結串列的最後一個元素的`next`指向`head`並也將`head`的`prev`指向最後一個元素才能完成雙向循環鏈結串列，因此`GGGG`是`head->prev`。

#### quick_sort
由於每次分割都會產生兩個子列表需要做排序，最壞情況下為每次分割其中一邊只有一個元素，會導致需要分割 `n` 次，產生 `2 * n` 個需要分配的子列表，將`max_level`的值設為鏈結串列的2倍大小以確保有足夠的空間進行排序。並且將第一個需要排序的列表設定為 `list->next` 及把環狀鏈結串列打斷，轉換為非環狀結構。
以下參考[charliechiu](https://hackmd.io/@charliechiu/linux2025-homework2#%E6%B8%AC%E9%A9%97-3)大大的實作
接著便開始排序：


首先先將 `L` 及 `R` 兩指標指向頭及尾：


若 `L` 及 `R` 兩者不同，則將 `pivot` 指向 `L` 所指的節點，並將 `pivot` 的數值存於 `value`。


使用 `p` 指向 `pivot` 的下一個節點，並斷開 `pivot`。


使用 `p` 遍歷節點，將小於 `value` 的置於 `left` 中，大於 `value` 則置於 `right` 中。

if (n_value > value)
{
    n->next = right;
    right = n;
}
else
{
    n->next = left;
    left = n;
}


將 `begin[i]` 指向對應的位置。

begin[i]= begin[0] = left;
begin[i + 1]= begin[1] = pivot;
begin[i + 2]= begin[2] = right;
left = right = NULL;


在下一輪中同樣將 `L` 指向 `begin[i]` 即為 `begin[2]` (從較大子序列開始),而` R` 則指向 `begin[2]` 的尾端。


此時按照先前的步驟將` pivot` 設置在` L` 並將 `p` 指向 `pivot` 下一個節點
將串列上的元素與 pivot 比較後分成 left (小於等於 pivot) 和 right (大於 pivot)
同樣遍歷節點，將小於 value 的置於 left 中，大於 value 則置於 right 中，並將 begin[] 指向對應的位置。

begin[i]= begin[2] = left;
begin[i + 1]= begin[3] = pivot;
begin[i + 2]= begin[4] = right;
left = right = NULL;


`begin[0]`也是如此，以此類推，直到排序出整個鏈結串列中最大值的元素為止，這時，`L`才會第一次等於`R`。
若`L`和`R`相同，代表`begin[i]`指向的鏈結串列的元素只有一個，因此將它的`next`指標指向已經排序好的鏈結串列之中的最小元素`result`，再將`result`設為它自己後，再繼續對`begin[i-1]`指向的鏈結串列做排序，若`begin[i-1]`指向的鏈結串列不只一個元素則又會進入第一種狀況(`L` 及 `R` 兩者不同)。
因為`value`會持續的和遍歷串列的元素比大小，因此`HHHH`應該是 `pivot` 節點的數值，因此答案為`list_entry(pivot,node_t,list)->value`；`n_value`會透過`IIII`不斷更新然後和`value`做比較，因此答案為當前節點`n`的數值，為`list_entry(n,node_t,list)->value`；最後`JJJJ`和`KKKK`即為`pivot`或`right`才能將結果存在`begin`中並且符合題目說明的`quick_sort`。

## quiz2

### 測驗 `1`

測驗 `1` 的重點有別於尋常的快速排序，而是實現了stable sorting 的 quickSort 用於鏈結串列 。
一般的 quickSort 在陣列上運行時可能會破壞穩定性（因為相同鍵值的元素可能會因交換順序改變），但這裡可透過其他的操作來保持穩定性。

#### cmpint
用於實作 quicksort 的數字比較，強制將傳入參數轉型為 `uint16_t *` 才能比較數字大小，因為傳入的參數是void *無法存取。

* C99/C11 規格書6.3.2.3 (1) 提到：
> A pointer to void may be converted to or from a pointer to any object type. A pointer to any object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.

轉型後的數字為無號16位元整數，因此範圍為0~65535

#### getnum
用於產生亂數，宣告三個只會初始化一次的 `static` 無號16位元整數，之後每次呼叫此函式都會進行如下計算：

s1 = (s1 * 171) % 30269
s2 = (s2 * 172) % 30307
s3 = (s3 * 170) % 30323

再回傳只有最右邊8位元的 s1 ^ s2 ^ s3，如此產生 0~255 之間的亂數。

#### get_unsigned16
透過呼叫 `getnum` 函式兩次，生成16位元的亂數。

#### 延伸問題：改進後的 random_shuffle_array

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = len - 1; i > 0; i--) {
        uint16_t j = get_unsigned16() % (i + 1);
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
    }
}

* 根據Fisher-Yates Shuffle，`j` 必須在 [0, i] 之間選擇，而不是 [0, i+1] 。

#### main
這段程式碼的主要功能是 測試 `list_quicksort` 是否能正確對 `testlist` 進行排序，並且與標準的 `qsort` 結果做比對。
打亂 `values` 陣列，初始化 `testlist` ，並將` values` 陣列轉換成 `testlist`，再使用 `qsort` 排序 `values` 以作為正確答案，使用 `list_quicksort` 排序 `testlist`，最後檢查 `testlist` 與 `qsort` 結果是否匹配，且釋放記憶體並確認 `testlist` 為空。

#### list_quicksort
整段程式採遞迴呼叫，前面為基礎情況檢查和初始化 `list_less` 和 `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);
    }

* 選取 `pivot` 並將其從原串列中移除，根據 `pivot` 型別為元素的指針，以及選項中只有 `list_first_entry` 和返回元素的指針有關，可以判斷 `AAAA` 是 `list_first_entry` ；同時，前面提到需將其從原串列中移除，因此 `BBBB` 是 `list_del` 。
* 用 `list_for_each_entry_safe` 遍歷鏈結串列 ，根據比較大小的結果將元素移到 `list_greater` 或 `list_less`，且移動操作應該使元素保持原本的順序，故選 `list_move_tail`。

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

* 對分組後的結果進行遞迴呼叫。

    DDDD(&pivot->list, head);
    EEEE(&list_less, head);
    FFFF(&list_greater, head);

* 當做完上述的操作，我們應該要將結果添加回去。由於 `pivot` 現在是獨立元素(沒有 `head`)，所以使用 `list_add` 或 `list_add_tail` ，語意上沒差但前者短，故 `DDDD` 為 `list_add` 。
* `EEEE` 和 `FFFF` 是將排序好的兩個鏈結串列串回去 `head` ，由於 `qsort` 本身是按升冪排序，所以 `list_less` 接到 `pivot` 前，所以 `EEEE` 是 `list_splice` ；而 `list_greater` 應該接到 `pivot` 的後面，所以 `FFFF` 是 `list_splice_tail` 。

#### 延伸問題：若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
由於 `list_move` 會將元素插入到鏈結串列的開頭，而 `list_move_tail` 則會將元素插入到鏈結串列的尾端，接著， `list_for_each_entry_safe` 會從鏈結串列的開頭逐一與 `pivot` 進行比較，因此如果使用 `list_move`，較後面的元素將被放置在前面，造成兩相同數值的元素在排序後位置互換，無法滿足 **stable sorting** 的要求。

### 測驗 `2`
#### clz2
以下參考 [Dennis Liu](https://hackmd.io/@dennis40816/linux2025q1-quiz2-writeup#%E6%B8%AC%E9%A9%97-2) 大大的作答講解
主要用來計算 `x` 的前導零數量，將當前的數字以位元為單位，切成一半。若 `upper` 是 0，下一次檢查 `lower` 部分，且紀錄 upper 位元數 (16 >> c)，函式會在 `c` 不等於3時繼續遞迴呼叫，直到最後等於3時會利用`magic`陣列計算最後第 0~3 位元有幾個 0，如此即完成計算 `x` 的前導零數量。
根據規律，mask[c] 在第一步 ( `c=0` )為 0，下一步變成 8，再下一步會變成 12，即為之前累積的位移量加上這次的位移量 `16 >> c` ，因此 `GGGG` 應為 12 + 2 = 14。
前面說到：
>遞迴呼叫 clz2() 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。

說明 `c` 與 `JJJJ` 相等即為剩下 2 bits，`(16 >> c) == 2` ，`JJJJ` = 3 。
前面說到`magic`陣列用來計算最後第 0~3 位元有幾個前導 0 ， 而如果 `upper` 非 0，直接返回 `magic[upper]`，此時 upper 只可能有三種可能：
* 0b01: 有一個前導 0，對應到 `magic[1]` ➝ 1
* 0b10: 沒有前導 0，對應到 `magic[2]` ➝ 0
* 0b11: 沒有前導 0，對應到 `magic[3]` ➝ 0 ➝ `IIII`

而 `magic[0]` 只會在 `upper` 是 0 時，此時 `lower` 也是0，此時前導零數量為 4(剩下各兩 bits 都是 0)，然而還有一項 `KKKK`，代表的是 `upper` 固定貢獻的前導零數量，也就是 2，所以 `magic[0]` = `HHHH` 也是 2。
最後一部分，是遞迴呼叫 `clz2` 的過程：當 `upper` 非零，計算 `upper` 的 `clz2` 並返回； 若 `upper` 是零，則計算 `lower` 的 `clz2` 並加上 `upper` 全零的前導零數量並返回，由於 `lower` 也要切一半，所以 `LLLL` 同樣也是 1 。

#### sqrti
使用逐步逼近但在位元運算上更為高效的演算法，計算 64 位元無號整數的平方根的整數值，利用剛才的 `clz2` 建構出的 `clz64`，找出從左看第一個數值為1的位元的索引值(索引值從左到右是 64 ~ 0 )。
說明指出：
>(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.

強制一個數字變成偶數最好的方法就是和`~1` = `MMMM` 做邏輯 `&` 運算而把最低位強制變0，得到變數shift；之後設定64位元無號整數 `m` 往左移`shift`位，這樣 `m` 才能從 4 的冪次開始，接著利用二進制開平方法從最高位開始逐步逼近平方根。

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

* 從最大可能的平方根 `y` 開始，每次嘗試將 `m` 加到 `y` 上，看看 `x` 是否還夠大，如果 `x >= b`，說明 `b` 仍然是平方根的一部分，所以 `x -= b`，`y += m`，且逐步減小 `m`，使其從大到小逼近真正的平方根。`NNNN` = 1，表示 每次` y` 都要右移 1 位，以確保計算過程的進位；`PPPP` = 2，因為 `m` 代表的是平方值，因此每次 `m` 需要減半的平方根對應到 `m >>= 2`，因為奇數位所表達的數值無法開根號為整數且 $\sqrt2$ 不是整數。

參考執行結果：

輸入63 = 16 + 47 = 36 + 27 = 49 + 13 

* 在 x = 63 時，`(total_bits - 1 - clz64(x))`是 5，`shift` = 4，因此`m`為 16，因為`m< 63`，因此會繼續測試是否 $6^2 = (4+2)^2 <63$，再測試$7^2 = (4+2+1)^2 <63$ 後，可得出63的平方根的整數值`y = 7`。

#### 延伸問題 1
> 解釋上述程式碼，並探討擴充為 $⌈(\sqrt𝑥)⌉$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

絕大部分的情況只要將最後得出的`y` 再 +1 即可，唯獨當只有x剛好為完全平方數(x=b)時，將最後得出的`y` 再 +1會不等於$⌈(\sqrt𝑥)⌉$，因此可以在結束 while 迴圈後再補上：

if(x != 0){
  y++;
}

便可完成要求的實作。

### 測驗 `3`
題意是給定一個陣列 `nums` 和一個目標值 `target`，求找到 `nums` 的 2 個元素相加會等於 `target` 的索引值。題目確保必為單一解，且回傳索引的順序沒差異。例如給定輸入 `nums = [2, 7, 11, 15]`,` target = 9`，相加變成 9 的元素僅有 2 及 7，因此回傳這二個元素的索引值 `[0, 1]`

我們可用 hash table 記錄缺少的那一個值 (即 `target - nums[i]`) 和對應的索引，以降低時間複雜度。

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};


`hash table` 主要由一個 `hlist_head` 的動態陣列組成，每個 `entry` 指向一個由 `struct hlist_node` 構成的**非環狀**雙向鏈結串列。哈希表的大小依據 `bits` 設定，長度為 **2 的冪次方**。
可以發現`struct hlist_head` 只有一個 `struct hlist_node *` 成員，而 `struct hlist_node` 則包含一個 `struct hlist_node *` 及 `struct hlist_node **`。這樣的設計是因為 `hash table` 的鏈結串列為**非環狀**，只需指向鏈表的一端。如果直接使用 `struct hlist_node` 作為`head`，則無用的 `pprev` 指標將會浪費大量記憶體。
而 `struct hlist_node` 中的 `pprev` 為何使用「指標的指標」?
這是為了讓刪除節點時能夠統一處理 `head` 節點與非 `head` 節點的刪除邏輯，因此讓`pprev` 指向前一個節點的指標`next`的位置，除此之外也能節省額外的 `prev` 指標，減少記憶體使用。

#### struct map_t
`bits`：用來表示**雜湊表的大小**，通常 2^bits 會是實際的桶 (bucket) 數量。

#### hash_key
`hash_key`就是存放於雜湊表內的節點，其中`node`用來維護雜湊鏈表。
* `key`：此鍵值會用來計算 hash 值，決定存放在哪個 bucket。
* `data`：存放的實際數據。

#### map_init
分配 `map_t` 結構體，並設定 `bits`。分配 `hlist_head` 陣列存放節點，再初始化 hlist_head 陣列，確保所有 bucket 開始時都是空的 (`first = NULL`)。

#### hash
將輸入值`value`乘上 `0x61C88647` 後右移 `32-bits` 個位元以取得雜湊值，其中，0x61C88647轉成有號整數為 2654435769，剛好是除以黃金比例，這個數字的特性是能夠最大程度地分散輸入值，避免常見的雜湊衝突。

#### find_key & map_get
實作了一個基於 `hlist` 的雜湊表查找與獲取函數，用來尋找儲存在 `map_t` 雜湊表中的 `key`，並返回對應的 `data`，`AAAA` 應該是 `map->bits`，代表雜湊表的位元數，決定bucket 的數量 (2^bits)。
`find_key` 使用 `for` 迴圈遍歷該桶中的所有節點，尋找 `key`，若找到相符的 `key`，則返回該 `hash_key` 節點，否則返回 `NULL`。
`map_get`透過呼叫`find_key`，找出對應的`hash_key`以取得對應的 `data`。

#### map_add
將新的資料加入哈希表，不管是否有相同索引值的元素已在哈希表中，新的資料均會加入到鏈結串列的開頭(如果原本這個 bucket 裡面有節點的話，它會是`struct hlist_node first`)。
`BBBB` 應該和 `AAAA`相同都是`map->bits`，`hash`取得它在雜湊表的位置；由於`n->next = first`，因此`first`的上一個為`n`，故 `CCCC` 為 `first->pprev`，讓 `first` 的 `pprev` 指向 `n->next`的位置，如同前面說的；同理，`DDDD`為`n->pprev`，直接指向`h->first`的記憶體位址。


#### map_deinit
程式碼的主要目的是釋放與 map 相關的記憶體資源，並清理雜湊表中所有節點。
它會遍歷所有bucket 根據 `map->bits` 來計算需要執行多少次，接著遍歷桶中的所有節點，並判斷該節點是否已經從哈希表中移除，若節點還在則透過將該節點的`next`和`pprev`設為`NULL`並且調整上一個的`next`及下一個節點的`pprev`來從哈希表中移除節點，`EEEE` 為 `n->pprev`，讓我們可以更新它以便正確地移除節點 `n`，最後當這個 bucket 的節點都刪除後，會釋放`hash_key` 節點的資料和記憶體。

#### twoSum
在一個整數陣列中找到兩個數字，它們的和等於目標值 `target`。如果找到這樣的數字，則返回這兩個數字的索引。
先初始化 `map`，並動態分配一個包含兩個整數的陣列 `ret`，用來存儲找到的兩個索引，接著遍歷數字陣列，對於每一個`nums[i]`都會計算對應的 `target - nums[i]`，然後查詢 `map` 中是否有這個差值的數字。如果找到這個差值，說明這兩個數字的和為 `target`。此時將 `i` 和對應的索引`*p`存入 `ret`，並設定 `returnSize = 2` 表示找到了答案，跳出迴圈。
如果`map`中沒有找到符合條件的數字，則將當前數字 `nums[i]` 及其索引 `i` 存入`map`。
在函式結束之前，釋放 `map` 的資源並返回 `ret`。如果找到了符合條件的數字，`ret` 中將包含兩個索引；若沒有找到則 `ret` 將是 `NULL`，`returnSize` 為 0。

#### 延伸問題：提供測試程式碼

int main() {
    int nums[] = {9, 5, 7, 8};  // 測試輸入陣列
    int target = 16;
    int returnSize;
    
    // 呼叫 twoSum 函式
    int *result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);
    
    // 驗證結果
    if (returnSize == 2) {
        printf("Indices: [%d, %d]\n", result[0], result[1]);
        free(result);  // 釋放記憶體
    } else {
        printf("No valid pair found.\n");
    }
    
    return 0;
}

輸出：

Indices: [2, 0]

改成 `nums[] = {10, 5, 7, 8}`
輸出：

No valid pair found.