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

## quiz1
### 測驗一
- 此為一單向鍊節串列測試程式，需完成 `list_insert_before` 函式實做。
- 首先觀察巨集 `my_run_test` 可知在 `main` 函式所執行的函式為 `test_list` ，測試程式執行藉由 `my_assert` 巨集判斷節點順序以及數量是否正確，回傳錯誤訊息給 `result`。

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)

- 主函式中， `result` 被宣告為一 `char *` ，程式執行結束時返回 `!!result` ，根據 C99 規格書 6.5.3.3 (5)，透過 `!` 將回傳值轉換成 `int` 型態。
> The result of the logical negation operator ! is 0 if the value of its operand comparesunequal to 0.

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

- `list_insert_before` 要插入一節點至 `before` 節點之前，操作如圖：
走訪並搜尋 `before` 節點，使用雙重指標技巧紀錄 `before` 節點位址的位址，將其位址的值更改為 `item` 位址，並連接 `next` 至 `before` 的位址完成插入。

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

- 合併排序串列 `merge_two_list`
用 `head` 紀錄串列開頭，使用迴圈將元素依序加入 `head` 串列，直到一串列為空，即可將另一串列全部元素加入。

static inline list_item_t *merge_two_list(list_item_t *p1, list_item_t *p2)
{
    list_item_t *head = NULL, **ptr = &head;
    while(!p1 || !p2){
        if (p1->value < p2->value){
            *ptr = p1;
            p1 = p1->next;
        }
        else{
            *ptr = p2;
            p2 = p2->next;
        }
    }
    *ptr = p2 ? p2 : p1;
    return head;
}

### 測驗二
- 此程式維護二元搜尋樹配置記憶體結構，首先補全 `remove_free_tree` 函式以及其他輔助函式。
- 根據二元搜尋樹的儲存節點規則， `target` 會儲存在 `size` 最匹配的位置（minmax），需要實做 `find_free_tree` 找尋目標位址。

block_t **find_free_tree(block_t **root, block_t *target)
{
    block_t **best = NULL;
    while(*root) {
        if ((*root)->size >= target->size) {
            best = root;
            root = &(*root)->l;
        } else {
            root = &(*root)->r;
        }
    }
    return best;
}

- `remove_free_tree` 中缺失片段如下，迴圈會去尋找 `target` 的親節點位址，用於提供刪除時使用：

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

- 測試程式包括 `insert_free_tree` , `print_tree` (inorder) 以及主函式。
- `insert_free_tree` 使用遞迴實做：

void insert_free_tree(block_t **root, block_t *node)
{
    if (!*root) {
        *root = node;
        node->l = node->r = NULL;
        return;
    }
    if (node->size < (*root)->size)
        insert_free_tree(&(*root)->l, node);
    else
        insert_free_tree(&(*root)->r, node);
    return;
}

- 主函式依序插入不同 size 的節點，並且用 inorder 顯示結果，測試程式如下：

int main()
{
    block_t *root = NULL;
    block_t blocks[7] = {{50}, {30}, {70}, {20}, {40}, {60}, {80}};

    // 插入節點
    for (int i = 0; i < 7; i++) {
        insert_free_tree(&root, &blocks[i]);
    }

    printf("Initial tree (in-order):\n");
    print_tree(root);

    // 移除部分節點
    printf("\nRemoving block size 70...\n");
    remove_free_tree(&root, &blocks[2]);  // 70
    print_tree(root);
    return 0;
}

結果如下：
### 測驗三
- 本題實做非遞迴的雙向鍊結串列 `quick_sort` ，使用 `begin` 陣列紀錄每次分割後的三個串列開頭，一個串列為相較 `pivot` 較小元素的串列，一個是只包含 `pivot` 的串列，一個是比 `pivot` 值大的串列。分別為 `begin[i] begin[i+1] begin[i+2]`
- 迴圈內使用 `begin` 模擬遞迴中 stack 功能儲存下個要處理的串列，分以下兩種情況：
1. 串列 size > 1 ，會走訪整個串列根據 `pivot->value` 決定將串列分割成上述三段，存入 stack:

if (L != R) {
    struct list_head *pivot = L;
    value = list_entry(pivot, node_t, list)->value;
    struct list_head *p = pivot->next;
    pivot->next = NULL; /* break the list */

    while (p) {
        struct list_head *n = p;
        p = p->next;
        int n_value = list_entry(n, node_t, list)->value;
        if (n_value > value) {
            n->next = right;
            right = n;
        } else {
            n->next = left;
            left = n;
        }
    }

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

2. 串列 size <= 1， 由於最後被拆分開時，單個元素串列一定是遞增派列在 stack 中，因此當 stack pop 出來的必定為 stack 中的最大值，直接加入 result 串列:

else {
    if (L) {
        L->next = result;
        result = L;
    }
    i--;
}
list->next = result;
rebuild_list_link(list);

- 完成後需要將原先單向鍊結串列 `rebuild` 成雙向，走訪整個串列並每次紀錄前一個，當走到下一個時更新，並且更新 `prev` 值：

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev = prev;
}

## quiz2
### 測驗一
此題實做雙向鍊結串列遞迴版本 `quicksort` ，走訪串列並依據與 `pivot` 的大小關係使用 `list_move_tail` 插入 `less` 或 `greater` 串列，遞迴完成後再使用 `list_splice` 以及 `list_splice_tail` 將全部串列合併起。
- 使用 `list_move` 會造成 sort 的結果不 stable 是因為 `list_for_each_entry_safe` 是順向走訪，若 `list_move` 會將順序前面的先加入 `less`，後走訪的反而會在 `less` 前面。

static void list_quicksort(struct list_head *head)
{
    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);
}

`TODO` 改良 random shuffle: Fisher–Yates Shuffle
### 測驗二
`TODO` 暫時還在理解中 $sqrti$ 演算法
### 測驗三
使用 hash table 解決 twoSum 問題，可以拆解成兩個部份：
1. hash table 資料解構：
- bucket 數量由要存入的元素數量決定

 #define MAP_HASH_SIZE(bits) (1 << (bits))

- 此題使用連續記憶體空建配置，每個 bucket 為 `hlist_head` 結構，指向 bucket 內第一個 `hlist_node` 結構。

struct hlist_head {
    struct hlist_node *first;
};

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

- `hlist_node` 為 `hash_key` 內成員， `hlist_head` 並非雙向考量點在於節省記憶體空間，以及 hash table 對於走訪的效率並無較大的要求。
- 構建出的 hash table 如下圖所示：

digraph G {

    rankdir=LR;
    node[shape=record];

    map [label="hash table |<ht0>hlist_head_0 |<ht1>hlist_head_1 |<ht2>hlist_head_2 |<ht3>hlist_head_3 |. |hlist_head_9 "];


    node[shape=none]
    null1 [label=NULL]

    subgraph cluster_3 {
        node [shape=record];
        hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="hash_key y"
    }
    subgraph cluster_1 {
        node [shape=record];
        hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="hash_key x"
    }
    
    subgraph cluster_2 {
        node [shape=record];
        hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="hash_key z"
    }


    
    map:ht0 -> hn3
    map:ht3 -> hn2
    hn1:prev:s -> hn3:next:s
    hn1:next -> null
    hn2:next -> null1
    hn3:next-> hn1
}

2. hash function
- 傳入參數數 bits 為想要保留之位元數，$h(K) = \lfloor m * (KA - \lfloor KA \rfloor) \rfloor$ 等價於 $h(K) = K \times 2^w \times A >> (w - p)$ ，利用 golden ratio 的與其倒數小數部份相同，且分母接近 $2^{32}$ 代替 $* 2^w$ ，分子神密數字相當於 $*A$ ，實做出 hash function

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

`find_key`
先得到 key 對應到 bucket 的位址，再走訪該串列查找使否有 key 值存在。

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

`map_add`
先查找出 bucket 後，插入至第一個元素，`pprev` 為指標的指標，值要設為 `&hlist_head->first`

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    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;
}

`map_deinit`
走訪每個 bucket 並走訪內部串列，`pprev` 使用雙重指標排除再移除第一個節點時的特例，讓程式碼較為簡潔。

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->next;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

以下為測試程式及結果：

int main() {
    int nums[] = {2, 7, 11, 15};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int target = 17;
    int returnSize = 0;

    // 調用 twoSum 函數
    int *result = twoSum(nums, numsSize, target, &returnSize);

    // 輸出結果
    if (returnSize == 2) {
        printf("Indices: [%d, %d]\n", result[0], result[1]);
    } else {
        printf("No solution found.\n");
    }

    // 釋放動態分配的內存
    free(result);

    return 0;
}

Indices: [3, 0]

`TODO` : 證明 Theorem S, 探討 Linux 核心中使用 hash table 的應用案例