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，有兩種情況：
4. pred_ptr 剛好是 target 的左子節點，此時用 pred_ptr 替換 target ；保留 target 的右子樹 。
5. pred_ptr 在 target 左子樹的更深處，先遞迴刪除 pred_ptr ，因為需要從 predecessor 的左子樹尋找它的 predecessor 。

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

以下參考 rota1001 大大的實作並改寫
這裡只要去實作 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大大的實作
接著便開始排序：

首先先將 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 大大的作答講解
主要用來計算 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，因為奇數位所表達的數值無法開根號為整數且
  $\sqrt{2}$ 不是整數。

參考執行結果：

輸入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

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

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

絕大部分的情況只要將最後得出的y 再 +1 即可，唯獨當只有x剛好為完全平方數(x=b)時，將最後得出的y 再 +1會不等於

$\lceil (\sqrt{𝑥})\rceil$，因此可以在結束 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.