2025q1 Homework2 (quiz1+2)

contributed by < bevmmf >

quiz1

測驗 `1`

singly linked list struct

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

typedef struct {
    struct list_item *head;
} list_t;

在 list_reset 中，l.head 被設為 NULL => linked list 結構無dummy node

這份程式是一 singly linked list 的測試程式。主要用來測試 list_insert_before 。程式使用 macro 來進行斷言（assertion）和測試執行，並驗證 singly linked list 在不同插入情境下的行為。

巨集定義 :

巨集（macro）是由前處理器（preprocessor）處理的一種機制，它會在編譯之前將程式碼中的巨集名稱替換為你定義的內容。這種替換是純粹的文字替換，不涉及函式呼叫的開銷

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

my_assert：如果條件 test 不成立，返回錯誤訊息 message，否則繼續執行。

assert 是一種放在程式中的一階邏輯，目的是為了標示與驗證程式開發者預期的結果－當程式執行到斷言的位置時，對應的斷言應該為真。若斷言不為真時，程式會中止執行，並給出錯誤訊息。
while(0) 條件永遠為假，因此loop只執行一次

#define my_run_test(test)       \
    do {                        \
        char *message = test(); \
        tests_run++;            \
        if (message)            \
            return message;     \
    } while (0)

my_run_test ：用來執行測試函數，並追蹤測試次數。如果測試失敗，會輸出錯誤訊息。

全局變數
items[N] ：一個包含 N(1000) 個 list_item_t 結構的陣列，用於測試中插入的項目。
l ：一個 list_t 結構的實例，表示鏈結串列。
tests_run ：追蹤測試次數，初始為 0。
主要函數

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

list_reset ：重置 items 陣列和鏈結串列 l，確保每次測試從乾淨的狀態開始。

static char *test_list(void)
{
    /* 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;
    }

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

    /* 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");

    return NULL;
}

test_list ：核心測試函數，測試 list_insert_before 在不同情況下的行為。

分為三部分 :
1. 測試在 l 開頭插入 (每次插入都在 l 開頭（prepend），導致最後插入的元素（items[999]）成為頭部)
  - 迴圈執行 list_insert_before(&l, l.head, &items[i]) 1000 次：
    - 初次插入時，l.head 為 NULL，假設 list_insert_before 將 items[0] 設為新頭。
    - 第二次插入 items[1] 在 l.head（即 items[0]）之前，更新頭為 items[1]，items[1].next = items[0]。
  - 確認最終大小為 1000。
  - 檢查順序：從頭開始，值應為 999, 998, …, 0（逆序）。
2. 測試在 l 結尾插入 (每次插入都在串列結尾（append）)
  - 重置串列，確認初始大小為 0。
  - 迴圈執行 list_insert_before(&l, NULL, &items[i]) 1000 次：
    - 假設 position == NULL 表示插入到結尾。
    - 初次插入時，串列為空，items[0] 成為頭。
    - 第二次插入 items[1] 在結尾，items[0].next = items[1]。
  - 確認最終大小為 1000。
  - 檢查順序：從頭開始，值應為 0, 1, …, 999（正序）。
3. 重複測試在結尾插入（僅檢查大小）
  - 確保多次插入到結尾的穩定性
  - 若所有assert通過，返回 NULL，表示測試成功

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

test_suite ：使用 my_run_test 執行 test_list ，執行所有測試案例。若無錯誤，返回 NULL。

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

main ：

輸出測試標題。
運行 test_suite，儲存結果。
若 result 非空，輸出錯誤訊息；否則輸出成功訊息。
顯示測試次數（應為 1）。
返回值：0（成功）或 1（失敗）。

static inline void list_insert_before(List_t *l,   //function signature
                                      list_item_t *before,
                                      list_item_t *item);
{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

首先必須知道函式 list_insert_before 每個parameter的定義

@l : 指向欲操作list的pointer
@before :

Pointer to the item before which the new item should be inserted

以上句子which指the item，因此before指向插入之new item之後的item位置
@item :　要插入的new item

再來是函式運作邏輯 :
以 before = C 為例:

for loop會遍歷 l，直到找到 before item

*p = item; 將before前一個item的 next 指向 new item，完成插入

item->next = before; 讓 new item 指向 before 所指向，確保 l 完整性

再來是解題部分 :
AAAA : &l->head,因為是從頭開始遍歷，所以為指向head。又因p為指向指向item的pointer，因此除了取 l 的 head 之外還要取 & 。

BBBB : before,根據此函式signature comment可知欲插入的new item在before之前，因此遍歷的停止點應設在 p 指向 before 指向的item即跳出

CCCC : &(*p)->next,此好品味地函式使用指向指標的指標，目的是能夠不用判斷是否head條件。此寫法的核心即是讓指標的指標持續指向 next。

DDDD : item->next,根據此函式定義，將new item下一個指向before即完成

測驗 `2`

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

解釋程式碼運作的原理

此題背景為 dyynamic memory allocator 的實現，特別是顯式配置器（explicit allocator）。allocator 必須滿足多個條件，包括處理任意請求序列、立即滿足需求、僅使用heap空間、確保地址對齊（例如 32 位系統為 8 位元組對齊，64 位系統為 16 位元組對齊），並且不得修改已配置的區塊。目標是在吞吐率（單位時間內完成的配置和釋放請求數量）和空間利用率（

U_{k} = \frac{m a x_{i < k} P_{i}}{H_{k}}

，其中

𝑃_{i}

是過去請求的有效荷載總和，

𝐻_{k}

是目前heap大小）之間找到平衡。為了提升空間區域性（spatial locality），allocator利用分頁（paging）特性，確保每個分頁僅存放特定大小類別（size-class）的空間，避免自由區塊地址分散導致效能下降。

為什麼選擇 BST 架構實作allocator?

能夠快速搜尋合適區塊
當程式請求分配某個大小的記憶體時，分配器需要在自由區塊中找到一個足夠大的區塊。BST 的結構允許從根節點開始，根據請求大小快速決定向左還是向右搜尋，效率遠高於線性搜尋。
支援動態操作
記憶體分配和釋放是動態的過程，自由區塊會不斷被加入或移除，而 BST 支援高效的插入和刪除操作
可擴展性
當系統中的自由區塊數量變多時，BST 的搜尋時間只隨節點數量對數增長（𝑂(log𝑛)），比起逐一檢查所有區塊的線性結構（如linked-list，O(n)）更具優勢。

#include <assert.h>
#include <stddef.h>

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

block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);

/*
 * Structure representing a free memory block in the memory allocator.
 * The free tree is a binary search tree that organizes free blocks (of type block_t)
 * to efficiently locate a block of appropriate size during memory allocation.
 */
void remove_free_tree(block_t **root, block_t *target)
{
    /* Locate the pointer to the target node in the tree. */
    block_t **node_ptr = find_free_tree(root, 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);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    } else {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

此題程式碼實現了一個基於二元搜尋樹（BST）的記憶體區塊管理系統
記憶體區塊 block_t 結構定義如下：

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

size：block的大小。
l：左子節點pointer。
r：右子節點pointer。

以下為未完成函式 :

block_t **find_free_tree(block_t **root, block_t *target)

block_t *find_predecessor_free_tree(block_t **root, block_t *node)

以下為函式 remove_free_tree :
目的是從 BST 中移除 target 節點，以下是函式signature

void remove_free_tree(block_t **root, block_t *target)

block_t **root：指向樹根的指標的指標，允許函數修改樹的根。
block_t *target：要移除的目標節點。

尋找目標節點

block_t **node_ptr = find_free_tree(root, target);

返回指向 target 的指標，若 target 不存在，則undefined behavior（程式碼未處理此情況）

處理有兩個子節點的情況

if ((*node_ptr)->l && (*node_ptr)->r) {

特別處理的原因是 :
在 BST 中，移除有兩個子節點的節點需要找到一個替換節點，以維持 BST 的性質（左子樹所有節點小於根，右子樹所有節點大於root）
替換節點通常是中序前驅（左子樹的最大節點）或中序後繼（右子樹的最小節點） tree學習

尋找中序前驅(inorder predecessor)
- EEEE : (*pred_ptr)->r, 因為它會走訪 target 節點的左子樹，找到其中的最右節點。
- FFFF : &(*pred_ptr)->r , 因為它代表如何向右子樹移動，即應該指向 pred_ptr 的右子節點，直到找到最右節點。

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

驗證中序前驅
- 調用 find_predecessor_free_tree 獲取中序前驅，並與 pred_ptr 指向的節點比較
- 使用 assert 進行調試，確保找到的中序前驅正確

block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);

替換目標節點

case1 中序前驅是目標節點的直接左子節點

if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; // 將目標節點替換為其左子節點 
(*node_ptr)->r = old_right; // 將原右子樹附加到新節點 
assert(*node_ptr != (*node_ptr)->l); //assert 確保新節點不指向自己，避免循環引用。
assert(*node_ptr != (*node_ptr)->r);
}

case2 中序前驅在左子樹的更深處

else {
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* 從原位置移除中序前驅 */
remove_free_tree(&old_left, *pred_ptr);
/* 將目標節點替換為中序前驅 */
*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);
}

處理有一個子節點或無子節點的情況
```
else if ((*node_ptr)->l || (*node_ptr)->r) {
    block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
    *node_ptr = child;
} else {
    *node_ptr = NULL;
}
```
- 有一個子節點：
  - 使用三元運算子選擇唯一的子節點（child）
    - 三元運算子（Ternary Operator）: 用來簡化簡單的 if-else
```
condition ? valueIfTrue : valueIfFalse
```
    1. 一個條件（condition）
    2. 條件為真的結果（value if true）
    3. 條件為假的結果（value if false）
  - 用子節點替換目標節點（*node_ptr = child）
- 無子節點
清除被移除節點的指標
```
target->l = NULL;
target->r = NULL;
```
- 將被移除節點（target）的左右子節點指針設為 NULL。避免懸空指針（dangling pointers），確保被移除的節點不再引用樹中的其他部分

fin

補完程式碼並測試

find_free_tree

block_t **find_free_tree(block_t **root, block_t *target) {
    block_t **current = root; // Start from the root node
    while (*current != NULL) { // Continue until the current node is NULL
        if (target->size < (*current)->size) {
            current = &(*current)->l;
        } else if (target->size > (*current)->size) {
            current = &(*current)->r;
        } else {
            if (*current == target) { // Check if the nodes are the same (same memory address)
                return current;
            } else {
                return NULL; // Sizes are equal but not the same node, return NULL
            }
        }
    }
    return NULL; // Target node not found, return NULL
}

根據比較 target 與 root subtree大小往下找，直到size相同、address也同
find_predecessor_free_tree

block_t *find_predecessor_free_tree(block_t **root, block_t *node) { //`node` 即 `target`
    if (node == NULL || node->l == NULL) {  // If the node is NULL or has no left child
        return NULL;  // Return NULL as there is no predecessor
    }
    block_t *pred = node->l;  // Start from the left child
    while (pred->r != NULL) {  // Find the rightmost node in the left subtree
        pred = pred->r;  // Move to the right child
    }
    return pred;  // Return the inorder predecessor
}

在 node 的left subtree 持續往右下找到底

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

// 查找target node
block_t **find_free_tree(block_t **root, block_t *target) {
    block_t **current = root;
    while (*current != NULL) {
        if (target->size < (*current)->size) {
            current = &(*current)->l;
        } else if (target->size > (*current)->size) {
            current = &(*current)->r;
        } else {
            if (*current == target) {
                return current;
            } else {
                return NULL;
            }
        }
    }
    return NULL;
}

// 查找inorder predecessor
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    if (node == NULL || node->l == NULL) {
        return NULL;
    }
    block_t *pred = node->l;
    while (pred->r != NULL) {
        pred = pred->r;
    }
    return pred;
}

// 移除target node
void remove_free_tree(block_t **root, block_t *target)
{
    /* Locate the pointer to the target node in the tree. */
    block_t **node_ptr = find_free_tree(root, 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 ((*pred_ptr)->r)
            pred_ptr = &(*pred_ptr)->r;

        /* 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);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    } else {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

// auxiliary_func1：insert node
void insert_free_tree(block_t **root, block_t *node) {
    if (*root == NULL) {
        *root = node; //insert
        node->l = NULL;
        node->r = NULL;
    } else if (node->size < (*root)->size) {
        insert_free_tree(&(*root)->l, node);
    } else {
        insert_free_tree(&(*root)->r, node);
    }
}

//  auxiliary_func2：：inorder traverse and print
void inorder_print(block_t *root) {
    if (root != NULL) {
        inorder_print(root->l);
        printf("%zu ", root->size);
        inorder_print(root->r);
    }
}


int main() {
    // create node
    block_t *node1 = malloc(sizeof(block_t)); node1->size = 10;
    block_t *node2 = malloc(sizeof(block_t)); node2->size = 5;
    block_t *node3 = malloc(sizeof(block_t)); node3->size = 15;
    block_t *node4 = malloc(sizeof(block_t)); node4->size = 3;
    block_t *node5 = malloc(sizeof(block_t)); node5->size = 7;

    // build BST
    block_t *root = NULL;
    insert_free_tree(&root, node1);
    insert_free_tree(&root, node2);
    insert_free_tree(&root, node3);
    insert_free_tree(&root, node4);
    insert_free_tree(&root, node5);

    // print tree_org
    printf("Original tree (in-order): ");
    inorder_print(root);
    printf("\n");

    remove_free_tree(&root, node1);
    printf("Tree after removing size 10: ");
    inorder_print(root);
    printf("\n");

    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(node5);

    return 0;
}

測試程式為插入節點 3, 5, 7, 10, 15，形成如下結構
假設 target 為10

移除 size = 10 的節點（root 有兩個子節點）。remove_free_tree 會用中序前驅（7）替換 10，結果如下：

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

測驗 `3`

延伸問題1
解釋上述程式碼運作原理

這題要求補全一個非遞迴的快速排序演算法實現，該實現基於鏈結串列，並使用堆疊模擬遞迴過程。

先了解 non-recursive quick sort 運作

首先是所需的變數

pivot : 基準點
每次分割時選出來的一個節點，用來當作比較的基準(總是選當前子串列的第一個節點（也就是 L）)
- 此為 quick sort 的核心。每次分割完後，pivot 會被放在正確的位置(左邊都比它小，右邊都比它大)
left : 左邊子串列
是一個臨時的鏈結串列，用來裝所有比 pivot 小或等於 pivot 的節點
right : 右邊子串列
是一個臨時的鏈結串列，用來裝所有比 pivot 大的節點
L : 當前子串列的開頭
是當前正在處理的子串列的第一個節點
在每次分割開始時，L 從堆疊（begin[]）裡取出，然後被設為 pivot。L 告訴我們「從哪開始排序」
R : 當前子串列的結尾
begin[] : stack(記錄子串列開頭)
begin[] 是一個數組，當作堆疊用，裡面存的是每個待排序子串列的開頭節點。因為不用遞迴，我們需要一個地方記錄還沒處理完的子串列。begin[] 就像一個待辦清單。
每次分割後：
- begin[i] 存 left 的開頭。
- begin[i+1] 存 pivot。
- begin[i+2] 存 right 的開頭。
end[] : stack(記錄子串列結尾)
它搭配 begin[]，幫我們知道每個子串列的範圍（從哪到哪）

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = CCCC;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = DDDD;
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = EEEE;

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

參數：node_t **list 是一個指向鏈結串列頭部指針的指針
變數 :
n：串列的節點數量，通過 list_length(list) 計算。
value：用來儲存基準點（pivot）的值。
i：堆疊的索引，指的是當前正在處理的子串列位置。
max_level：堆疊的最大容量，設為 2 * n。這個值確保堆疊有足夠空間處理最壞情況下的分割。
begin[] 和 end[]：兩個陣列模擬堆疊，分別儲存每個待排序子串列的開頭和結尾節點。
result：最終排序完成的串列頭部，初始為 NULL。
left 和 right：用來暫存分割後的子串列，分別存放小於和不大於 pivot 的節點

stack初始化

begin[0] = *list;
end[0] = list_tail(list);

將整個list作為第一個待排序的子串列

主循環

while (i >= 0) {
    node_t *L = begin[i], *R = end[i];
    if (L != R) {
        // 分割
    } else {
        // 合併
    }
}

循環條件：當 i >= 0 時，表示stack中還有待處理的子串列。
L 和 R：從堆疊中取出當前子串列的開頭（begin[i]）和結尾（end[i]）。

分支：

如果 L != R，子串列有多於一個節點，需要進行分割。

分割

node_t *pivot = L; //選基準點（pivot）：選擇子串列的開頭 L 作為 pivot。
    - 斷開 pivot：將 pivot->next 設為 NULL，使 pivot 
value = pivot->value;
node_t *p = pivot->next;  //準備遍歷：p 指向 pivot 後面的節點，作為分割的起點
pivot->next = NULL; //斷開 pivot：將 pivot->next 設為 NULL，使 pivot 成為獨立節點

//分割子串列至left or right
while (p) {
node_t *n = p; //當前處理節點
p = p->next;
list_add(n->value > value ? &right : &left, n);
}

更新堆疊
- 放入新子串列
- 重置：left = right = NULL，為下一次分割準備。
- 移動索引：i += 2，跳到 right 子串列的位置，下一次循環會先處理它。
每組子串列會佔用 begin[] 的三個位置

begin[i] = left;
end[i] = list_tail(left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(right);
left = right = NULL;
i += 2;

如果 L == R，子串列只有一個節點（或為空），直接處理並加入結果。
- 合併
```
if (L)
list_add(&result, L);
i--;    
```
- 處理單節點：
  - 如果 L != NULL，表示這個子串列只有一個節點，將其加入 result。
  - 如果 L == NULL，則跳過（空子串列）。
- 回退：i--，返回堆疊中上一個待處理的子串列。

最終更新

*list = result;

將排序後的串列頭部 result 令 list 指向

接下來將以上quick sort 改寫成以Linux 核心風格的doubly linked list 實作

測試程式

list_construct
創建一個新的節點並將其插入到指定的鏈結串列中

void list_construct(struct list_head *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->value = n;
    list_add(&node->list, list);
}

list_free

    void list_free(const struct list_head *head)
{
    node_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        free(entry);
    }
}

釋放lsit中的所有節點記憶體

list_is_ordered
檢查list是否ascend

static bool list_is_ordered(const struct list_head *head)
{
    int value = list_entry(head->next, node_t, list)->value;
    node_t *entry;
    list_for_each_entry (entry, head, list) {
        if (entry->value < value)
            return false;
        value = entry->value;
    }
    return true;
}

shuffle
將整數陣列的元素隨機打亂

void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

使用 Fisher-Yates 演算法

從索引 i = 0 到 n - 2 遍歷陣列。
計算隨機索引 j，範圍從當前索引 i 到陣列末尾（n - 1）。
- j 的計算公式 i + rand() / (RAND_MAX / (n - i) + 1) 確保隨機選擇是均勻的
交換 array[i] 和 array[j] 的值。

main

int main(int argc, char **argv)
{
    struct list_head *list = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(list);

    size_t count = 100000;
    int *test_arr = malloc(sizeof(int) * count);
    for (int i = 0; i < count; ++i)
        test_arr[i] = i;
    shuffle(test_arr, count);

    while (count--)
        list_construct(list, test_arr[count]);
    quick_sort(list);
    assert(list_is_ordered(list));
    list_free(list);
    free(test_arr);
    return 0;
}

初始化 list
準備100000筆測試數據放入 test_arr
將 test_arr 中測試數據放入插入 list
quick_sort(list) 排序
assert(list_is_ordered(list) 驗證升序結果
釋放 list 、 test_arr中的所有節點。

quick_sort

auxiliary funciton

list_tail
返回鏈結串列的尾部節點

struct list_head *list_tail(struct list_head *head)
{
    while (head && head->next)
        head = head->next;
    return head;
}

list_length
計算鏈結串列的長度

int list_length(struct list_head *left)
{
    int n = 0;
    struct list_head *node;
    list_for_each(node, left) n++;
    return n;
}

rebuild_list_link
重建之前被斷開之雙向鏈結串列，重接回成circular雙向鏈結串列

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

quick_sort 主體

void quick_sort(struct list_head *list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;

    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = list_entry(pivot, node_t, list)->value;  // HHHH
            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;  // IIII
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            begin[i] = left;
            begin[i + 1] = pivot;  // JJJJ
            begin[i + 2] = right;  // KKKK
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}

初始化
int n = list_length(list)：計算鏈結串列長度。
int max_level = 2 * n：設置堆疊最大層級為 2 * n，以應對最壞情況（完全不平衡的分割）。
struct list_head *begin[max_level]：堆疊數組，儲存待處理的子串列開頭。
result, left, right：分別用於儲存最終結果和分割後的左右子串列，初始化為 NULL。
begin[0] = list->next：將整個鏈結串列的開頭放入堆疊。
list->prev->next = NULL：斷開循環鏈結串列，轉為單向鏈結串列，便於後續操作。
主循環
while (i >= 0)，表示堆疊中仍有待處理的子串列。
L = begin[i]：當前子串列的開頭。
R = list_tail(begin[i])：當前子串列的結尾。
- 分支：
  - 如果 L != R，執行分割過程。
    - 選 pivot
    - 分割子串列
    - 更新堆疊
  - 如果 L == R，執行合併過程。
    - 條件：if (L)，表示子串列只有一個節點。
    - L->next = result; result = L：將單節點加入 result（頭插法）。
    - i--：回退到堆疊中的上一個子串列。

quiz2

測驗`1`

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

背景

通常傳統的quick sort為unstable(相同元素的相對順序可能改變)。此題目的為用linux 核心風格linked list做出stable的quick sort

解釋

list struct

#include <stdint.h>

struct listitem {
    uint16_t i;
    struct list_head list;
};

比較用的函式 cmpint

用來比較兩個 uint16_t 值，返回負數（< 0）、零（= 0）或正數（> 0），表示大小關係

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

auxiliary func

ARRAY_SIZE macro
計算陣列 x 的元素個數

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))

getnum 函式
生成一個偽隨機的 8 位元無符號整數（uint8_t），範圍在 0 到 255 之間
```
static inline uint8_t getnum(void)
{
    static uint16_t s1 = UINT16_C(2);
    static uint16_t s2 = UINT16_C(1);
    static uint16_t s3 = UINT16_C(1);

    s1 *= UINT16_C(171);
    s1 %= UINT16_C(30269);

    s2 *= UINT16_C(172);
    s2 %= UINT16_C(30307);

    s3 *= UINT16_C(170);
    s3 %= UINT16_C(30323);

    return s1 ^ s2 ^ s3;
}
```
首先要先了解什麼是 線性同餘生成器（LCG）
線性同餘生成器（Linear Congruential Generator, LCG）是一種簡單的偽隨機數生成演算法
- 偽隨機（Pseudo-random）的定義 : 指生成的隨機數序列並不是真正的隨機，而是通過確定性演算法（deterministic algorithm）生成的。也就是給定相同的初始種子（seed），每次執行程式生成的隨機數序列是完全相同的
它的核心是使用一個遞迴公式來生成隨機數序列，公式如下：

$X_{n + 1} = (a \cdot X_{n} + c) m o d m$
- $X_{n}$ : 第 n 次生成的隨機數（種子，也就是getnum所設定的171、172、170）
- a：乘數（multiplier），一個整數。
- c：增量（increment），一個整數。
- m：模數（modulus），決定隨機數的範圍。
- $X_{n + 1}$ : 下一個隨機數
再回來看函式即為
使用三個靜態變數 s1、s2、s3 作為隨機數種子，初始值分別為 2、1、1
每次調用時，根據線性同餘生成器（LCG）的變形更新種子：
s1 = (s1 * 171) % 30269
s2 = (s2 * 172) % 30307
s3 = (s3 * 170) % 30323
將更新後的 s1、s2、s3 進行xor（^）運算，返回結果作為隨機數。
get_unsigned16
生成一個 16 位元無符號整數（uint16_t）的偽隨機數，範圍在 0 到 65535 之間
```
static uint16_t get_unsigned16(void)
{
    uint16_t x = 0;
    size_t i;

    for (i = 0; i < sizeof(x); i++) {
        x <<= 8;
        x |= getnum();
    }

    return x;
}
```
- 初始化 x = 0，x 是 uint16_t 類型，佔 2 bytes。
- 迴圈執行 sizeof(x) 次（這裡 sizeof(x) = 2），每次：
  - x <<= 8：將 x 左移 8 位元（相當於乘以 256），為新的隨機數騰出空間。
  - x |= getnum()：調用 getnum() 獲取一個 8 位元隨機數，通過按位或（OR）添加到 x 的低 8 位。
- loop1：x 的低 8 位被填入第一個 getnum() 結果。
- loop2：x 左移後，低 8 位再填入第二個 getnum() 結果，形成完整的 16 位元數。
random_shuffle_array
將給定陣列 operations（長度為 len）的元素順序隨機打亂

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

我認為此src有誤，應為swap，因此不應該為 operations[j] = i;

測試程式

int main(void)
{
    struct list_head testlist;
    struct listitem *item, *is = NULL;
    size_t i;

    random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values)); //values 為array

    INIT_LIST_HEAD(&testlist);

    assert(list_empty(&testlist));

    for (i = 0; i < ARRAY_SIZE(values); i++) { //build linked-list with values
        item = (struct listitem *) malloc(sizeof(*item));
        assert(item);
        item->i = values[i];
        list_add_tail(&item->list, &testlist);
    }

    assert(!list_empty(&testlist));

    qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint); //對 values array進行 C 標準庫之quick sort
    list_quicksort(&testlist);

    i = 0;
    //驗證排序結果並free
    list_for_each_entry_safe (item, is, &testlist, list) {
        assert(item->i == values[i]);
        list_del(&item->list);
        free(item);
        i++;
    }

    assert(i == ARRAY_SIZE(values));
    assert(list_empty(&testlist));

    return 0;
}

準備數據：隨機打亂 values 數組，模擬無序輸入。
構建串列：根據打亂後的數組創建一個無序鏈結串列。
排序與驗證：
- 使用標準 qsort 對array排序，作為正確結果的參考。
- 使用 list_quicksort 對linked list排序。
- 逐一比較排序後的linked list與array，確保結果一致。
free 所有node

`list_quicksort` 主體

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_tail(&list_less, head);
    list_splice_tail(&list_greater, head);
}

檢查edge condition
初始化臨時串列 list_less、list_greater
選取並移除pivot
pivot 通常從串列頭部獲取第一個節點

分割串列

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_move_tail
src def

/**
 * list_move() - Move a list node to the beginning of the list
 * @node: pointer to the node
 * @head: pointer to the head of the list
 *
 * The @node is removed from its old position/node and add to the beginning of
 * @head
 */
static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

/**
 * list_move_tail() - Move a list node to the end of the list
 * @node: pointer to the node
 * @head: pointer to the head of the list
 *
 * The @node is removed from its old position/node and add to the end of @head
 */
static inline void list_move_tail(struct list_head *node,
                                  struct list_head *head)
{
    list_del(node);
    list_add_tail(node, head);
}

因為 stable sorting 定義為兩相等值在排序後相對順序不會改變。若出現兩個與pivot相等的node使用list_move，相對順序會被顛倒。

遞迴呼叫自己排序子串列
將被移光的list開始合併所有子串列(先接pivot，再左子list，最後右子list)

測驗`2`

首先了解 digit by digit，單純加減位移求平方根法

clz32

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

edge check 一開始x就是空的case
依照c遞迴層數將 x 分為高位部分 upper 和低位部分 lower
- lower 取的部分應隨c增加，取 16、8、4、2。因此 mask[] 為 {0,8,12,14}
  - c = 0：mask[0] = 0，遮罩 0xFFFF >> 0 = 0xFFFF（16 位）。
  - c = 1：mask[1] = 8，遮罩 0xFFFF >> 8 = 0x00FF（8 位）。
  - c = 2：mask[2] = 12，遮罩 0xFFFF >> 12 = 0x000F（4 位）。
  - c = 3：應提取 2 位元，0xFFFF >> 14 = 0x0003，故 GGGG = 14
- upper 亦隨c增加，取 16、8、4、2
當c == 3時upper、low取的是2 bit的值，也就是我們設計切割的最小單位。且magic[]為根據數值給leading zero數的查表
若 upper 不為 0，遞迴處理 upper；若 upper 為 0，則累加高位的前導零數 (16 >> c)，並遞迴處理 lower (有upper就整場只看upper，否則看lower)

驗證

以 0x0001F000 為例：

c = 0：upper = 0x0001, lower = 0xF000，因 upper != 0，呼叫 clz2(0x0001, 1)。
c = 1：upper = 0x00, lower = 0x01，因 upper == 0，返回 16 >> 1 + clz2(0x01, 2) = 8 + clz2(0x01, 2)。
c = 2：upper = 0x00, lower = 0x01，因 upper == 0，返回 16 >> 2 + clz2(0x01, 3) = 4 + clz2(0x01, 3)。
c = 3：upper = 0x00, lower = 0x01，因 upper == 0，返回 0 + magic[1] = 0 + 1 = 1。
總計：8 + 4 + 1 = 13，符合 0x0001F000 的前導零數。

clz64

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

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

返回值y : x的整數平方根，即

[\sqrt{x}]

m : mask，用於測試當前位元的貢獻
y：累積的平方根結果，初始值為 0
shift：用於計算初始遮罩 m 的位移量

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

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^{s h i f t}$

逐位逼近計算平方根

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}$ 。

節錄自 liangchingyun
範例分析

x = 36 (0b100100)

初始化

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

第一輪

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

第二輪

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

第三輪

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

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

測驗 `3`

背景

LeetCode 的 Two Sum 問題要求在給定陣列 nums 和目標值 target 中，找到兩個元素的索引，使得它們的和等於 target。題目保證有且僅有一個解，且索引順序無關緊要。使用暴力法時間複雜度為

O (n^{2})

，顯然效率不高，因此我們採用 hash table 來優化至 O(n)

hash table struct

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

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

ht 是包含多個 hlist_head 的陣列。每個 hlist_head.first 是對應 bucket 的開頭，指向該 bucket 的第一個 hlist_node
- bucket 就像一個「籃子」，裡面裝的是具有相同 hash 值的資料，在 hash table（雜湊表）中，bucket 是一個存儲單元（可以想像成一個「槽位」）。
- bits : 存儲 hash table 的位元數，用來計算 bucket 的總數。例如，若 bits 為 4，則 bucket 數量為
  $2^{4} = 16$
hash_key 代表 hash table 中的一個鍵值對節點(bucket 內linked list中的一個節點)

auxiliary function

`map_init` : 創建並初始化 hash table

map_t *map_init(int bits)
{
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

使用 malloc 分配 map_t 結構的記憶體。若分配失敗，返回 NULL 表示錯誤。
設置參數：
- map->bits = bits，記錄 hash table 大小的位元數（後續用於計算 bucket 數量）。
- 分配 ht 陣列（hash table 的主結構），大小為 MAP_HASH_SIZE(map->bits)，通常定義為
  $2^{b i t s}$
初始化 bucket：
- 若 ht 分配成功，遍歷每個 bucket，將其 first 指針設為 NULL，表示該 bucket 初始為空。
- 若 ht 分配失敗，釋放已分配的 map 記憶體，並將 map 設為 NULL。
返回值：
返回指向初始化好的 map_t 結構的指針，或在失敗時返回 NULL。

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

輸入是key(val)輸出是索引

檢索 `find_key` : 查找特定 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;
}

功能 :

在 hash table 中查找特定鍵 key，返回對應的 hash_key 結構指針，若未找到則返回 NULL

流程 :

定位 bucket：
使用 hash(key, map->bits) 計算 key 的 hash 值，獲取對應 bucket 的 hlist_head。
遍歷一bucket linked list：
從 head->first 開始，沿著 hlist_node 的 next 指針遍歷該 bucket 的鏈表。
對於每個節點，使用 container_of 宏從 hlist_node 獲取包含它的 hash_key 結構。
比對鍵：
若某個 hash_key 的 key 與輸入的 key 相等，返回該結構的指針。
未找到的情況：
若遍歷結束仍未找到匹配的鍵，返回 NULL。

`map_add` : 插入新 key 值對並維護 map

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_add 將一個新的鍵值對 (key, data) 加入 hash table。

實現細節

檢查重複：
先調用 find_key 檢查 key 是否已存在，若存在則直接返回，不插入重複鍵。
分配節點：
若 key 不存在，分配一個新的 hash_key 結構，設置 kn->key = key 和 kn->data = data。
定位 bucket：
使用 hash(key, map->bits) 計算 bucket 索引，獲取對應的 hlist_head。
插入bucket linked list開頭：
將新節點 n（即 kn->node）插入到 bucket 的linked list開頭：
- n->next 指向原來的 first。
- 若 first 不為空，更新 first->pprev 指向 n->next 的地址。
- 更新 h->first 為新節點 n。
- 設置 n->pprev 指向 h->first 的地址，維護雙向鏈接。

map_deinit : 釋放所有記憶體

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->ht);
    free(map);
}

功能

map_deinit 釋放 hash table 及其所有節點的記憶體。

實現細節

空檢查：
若 map 為 NULL，直接返回。
遍歷所有 bucket：
遍歷 map->ht 的每個 bucket（總數為 MAP_HASH_SIZE(map->bits)）。
釋放每個節點：
對於每個 bucket，從 head->first 開始遍歷鏈表：
- 使用 container_of 獲取 hash_key 結構。
- 記錄當前節點 n，並移動指針 p 到下一個節點。
- 若 n->pprev 為空（表示未被 hash），跳到 bail 直接釋放。
- 否則，執行移除操作：
  - 更新前一節點的 next 指針（*pprev = next）。
  - 若 next 存在，更新 next->pprev 指向 pprev。
  - 將 n->next 和 n->pprev 設為 NULL，完成移除。
- 釋放 kn->data 和 kn 的記憶體。
釋放 hash table：
最後釋放 map->ht 陣列和 map 結構。

主程式

twoSum

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;

    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

功能

twoSum 解決 Two Sum 問題，找到陣列 nums 中和為 target 的兩個元素的索引，返回包含這兩個索引的陣列。

實現細節

初始化：
- 使用 map_init(10) 創建 hash table（大小為
  $2^{10} = 1024$ )
- 設置 *returnSize = 0，初始化返回陣列大小。
- 分配返回陣列 ret（大小為 2），若失敗則跳到 bail。
遍歷陣列：
對於每個 nums[i]：
- 計算 target - nums[i]，並使用 map_get（假設存在，返回 data）查找是否有匹配的鍵。
- 若找到（p 不為 NULL），表示存在 nums[j] 使得 nums[i] + nums[j] == target：
  - 設置 ret[0] = i（當前索引），ret[1] = *p（之前存儲的索引）。
  - 設置 *returnSize = 2，結束循環。
- 若未找到：
  - 分配一個 int 記憶體，存儲當前索引 i。
  - 將 (nums[i], p) 插入 hash table。
清理：
無論是否找到解，跳到 bail 釋放 map。

2025q1 Homework2 (quiz1+2)

quiz1

測驗 1

測驗 2

解釋程式碼運作的原理

補完程式碼並測試

測驗 3

先了解 non-recursive quick sort 運作

接下來將以上quick sort 改寫成以Linux 核心風格的doubly linked list 實作

測試程式

quick_sort

auxiliary funciton

quick_sort 主體

quiz2

測驗1

背景

解釋

auxiliary func

測試程式

list_quicksort 主體

測驗2

首先了解 digit by digit，單純加減位移求平方根法

驗證

測驗 3

背景

hash table struct

auxiliary function

map_init : 創建並初始化 hash table

linux hash function

檢索 find_key : 查找特定 key 的節點

功能 :

流程 :

map_add : 插入新 key 值對並維護 map

功能

實現細節

功能

實現細節

主程式

功能

實現細節

Read more

研讀 linux 核心之 bloom filter

2025/04/23 一對一討論問答簡記

2025q1 Homework5 (assessment)

2025q1 Homework3 (kxo)

測驗 `1`

測驗 `2`

測驗 `3`

測驗`1`

`list_quicksort` 主體

測驗`2`

測驗 `3`

`map_init` : 創建並初始化 hash table

檢索 `find_key` : 查找特定 key 的節點

`map_add` : 插入新 key 值對並維護 map