2025q1 Homework2 (quiz1+2)

contributed by < Andrewtangtang >

quiz1-1

運作原理

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

根據該函式的的註解可以得知 item 在經過操作之後會被插入在 before 的前方。

• 初始化指標: 因此在一開始我們將 indirect pointer 初始化為指向(l->head) 的位址 (&l->head)，假設 before 是 head 則不會進入迴圈，可以直接將 item 設為新的 head ，因此 AAAA 應填入 &l->head。
• 尋找插入位置:在迴圈的內部，我們的目標是找到 before 這個節點來做執行插入，因此終止條件應該是 *p== before ，因此 BBBB 應填入 before。如果還未找到 before，則將 p 移動到下一個節點的 next 指標位址，也就是 p = &(*p)->next。
• 插入新節點: 離開迴圈後，*p 會指向 before 節點，因此可以直接將 *p 指向 item，這樣前一個節點就成功指向了新的節點 item。最後，將 item->next 設為 before，確保 item 正確地連接到 before。

這邊要特別注意c語言 precedence of operators
Structure and union member access through pointer->> indirection (dereference)*->Address-of&
C Operator Precedence

合併排序操作

quiz1-2

運作原理

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

這段程式碼主要是想找到 空的 Block 將其從樹狀結構中移除，而移除前我們必須找到一個 Block 來填補他的位子，在二元樹中尋找替代 node 的的策略可以分為以下幾個 case。

• 要刪除的節點是 Leaf Node

  • 處理機制:直接刪除
    

• 要刪除的節點只有一其中一邊有 child

  • 處理機制:將該 child 替代原本要刪除的 node
    

• 刪除的節點同時有左、右兩個 child

  • 處理機制:該題的處理機制是使用尋找 Inorder Predecessor 即找到左子樹中最大的節點，並以相同方式替換和刪除
    

該題的填空部分主要是處理第三種情況，即尋找 Inorder Predecessor 的過程。程式中使用了間接指標（indirect pointer）的方式，最初將 pred_ptr 指向 &(*node_ptr)->l，也就是待刪除節點的 left 的記憶體位址。接下來的 while 迴圈則負責尋找左子樹中最右邊的節點。在這個過程中，while 迴圈的條件應為 (*pred_ptr)->r，即當當前節點的右子節點不為空時，代表尚未找到最右邊的節點，應持續往右搜尋。迴圈內的動作則是 pred_ptr = &(*pred_ptr)->r，將 pred_ptr 更新為指向當前節點的右子節點的記憶體位址，持續深入到最右側。如此，當 while 迴圈結束時，*pred_ptr 就會正確指向左子樹中最大的節點，該節點即為Inorder Predecessor，可以作為替代節點繼續執行後續的替代策略。

quiz1-3

該題想撰寫一個基於 Linux 核心風格的鏈結串列來改寫程式碼。首先定義了結構體。

#include "list.h"
typedef struct __node {
    long value;
    struct list_head list;
} node_t;

以及相關輔助函式

• rebuild_list_link(struct list_head *head)：
  遍歷鏈表，設置每個節點的 prev 指針指向前一個節點，並將最後一個節點的 next 指針設為 head，並將 head->prev 設為最後一個節點(即 prev)，因此 GGGG 應該要填入 head->prev=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;
    /* GGGG */;
}

• struct list_head *list_tail(struct list_head *head)：
  通過遍歷 next 指針找到 next 為 NULL 的節點，返回非循環鏈表的尾節點。
• int list_length(struct list_head *left)：
  使用 list_for_each 宏遍歷鏈表，計算並返回節點數量，適用於循環鏈表。

接著我們來看 QuickSort 的本體實作，為了模擬遞迴，這裡使用了一個名為 begin 的陣列來儲存每個尚未排序子鏈結串列的起始位置。首先在初始化時，因為 QuickSort 最多可能產生約兩倍於 n 個子問題，所以我們將 begin 的大小設定為原鏈結串列長度 n 的兩倍。另外也建立了三個鏈結串列頭指標：left、right 及 result，其中 left 存放小於 pivot 的節點，right 存放大於 pivot 的節點，而 result 則用於逐步連接已排序好的結果串列。

    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;

在完成初始化後，會進入主要排序迴圈，持續執行直到所有子串列都完成排序。迴圈的第一步會檢查 i 是否大於 0，以確認還有尚未完成排序的子串列需要處理。接著會從 begin 陣列中取出當前要排序的子鏈結串列起始點，標記為 pivot。

• 如果此子串列只有一個節點（也就是已排序好），則直接將其接到 result 串列後方。
• 如果子串列有兩個以上節點，就會進入上方的 partition 分割過程。

接下來是程式 partition 分割，首先先確認 i 是不是大於0判斷確保還有未排序的鍊結串列，接著檢查下 L 是否等於 R 若相同則跳到下方的部分將該單一節點接在 result 的後方，如果不同的話則進入上方的 partition 過程。在做分割的過程中，會先取出 begin 的 top 作為 pivot 來進行比較，因此在此處我們需要將 value 設為list_entry(pivot,node_t,list)->value 用以儲存目前 pivot 的值。接著開始去 traverse 鏈結串列去做切割，假設 n 的值比我們 pivot 的值大，我們就把他加入 right 的鏈結串列，反之加入 left 鏈結串列，因此 IIII 的地方，我們應該要填入 list_entry(n,node_t,list)->value 來取出當前這個節點的數值。

    while (p) {
        struct list_head *n = p;
        p = p->next;
        int n_value = /* IIII */;
        if (n_value > value) {
            n->next = right;
            right = n;
        } else {
            n->next = left;
            left = n;
        }
    }

完成 partition 之後，會把此次分割出的子串列依序存回 begin 陣列內，以模擬遞迴呼叫的特性。在這個實作中，我們會先處理右側的子鏈結串列，因此，存入 begin 陣列的順序應該是：左側鏈結串列 left 、pivot 自身、右側鏈結串列 right。如此一來，下次迴圈取出子串列來處理時，便會先從 right 開始執行，完成後再繼續處理 pivot 與 left 子鏈結串列。

    begin[i] = left;
    begin[i + 1] = /* JJJJ */;
    begin[i + 2] = /* KKKK */;
    left = right = NULL;
    i += 2;

quiz2-1

運作原理

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

    

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

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

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

根據 quicksort 的邏輯，一開始會使用第一個元素當做是 pivot 因此在 AAAA 中我們應該要填入 list_first_entry 來取出第一個鏈結串列中第一個元素。為了能夠將 pivot 作為基準點來劃分鏈結串列，我們必須先將 pivot 從鏈結串列中移除，因此 BBBB 應填入 list_del，以確保 pivot 不會影響後續的排序操作。

    pivot = AAAA(head, struct listitem, list);
    BBBB(&pivot->list);

為何要選擇list_move_tail而非list_move

在 traverse 鏈結串列時，我們會將 pivot 之外的元素與其比較，並根據比較結果將元素分別移動至 list_less（小於 pivot）或 list_greater （大於或等於 pivot）。由於此實作必須滿足穩定排序（stable sort） 的特性，即相同的元素在排序後仍應維持原有相對順序，因此 CCCC 應選擇 list_move_tail，確保較晚 traverse 到的元素被放置在對應區段的尾端，若選擇 list_move 則會將比較晚 traverse 到的元素放在鏈結串列的前方，那麼最後在做合併的時候，結果就會變成原本相同元素的順序會因此改變。

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

接下來就是將 list_less 與 list_greater 去遞迴呼叫 list_quicksort 直到剩一個元素或者是鏈結串列為空時，而在最後要做合併的操作，因為原本是以 pivot 為中心去做切割的，所以在合併時，我們先將 pivot 加回原本的鏈結串列，接著將已經排序完成的 list_less 接回串列的頭部，而在最後將 list_greater 接在最後完成這個區段的合併，因此 DDDD 應填入 list_add，EEEE 應填入 list_splice，FFFF 則是 list_splice_tail。

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

quiz 2-2

程式運作原理

clz2

static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};

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 == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

程式的目的是想計算出要根據該32位元的數字前面有幾個 leading zero，而使用的方法是利用遞回呼叫的方式不停地去將目前關注的位元分成 upper 和 lower 兩個部份來進行檢查直到剩下 2 bit為止。而處理的機制可分為以下兩種方法

• 當目前 upper==0，則回傳目前檢查的位元數加上遞迴檢查 lower part 的結果
• 如果目前 upper!=0，則持續遞迴呼叫檢查 upper 部分直到剩下2 bits 或遇到第一個情況。

每次遞迴呼叫時，關注的位元數會減半：第一次關注 16 位、第二次 8 位、第三次 4 位、第四次 2 位。而我們要計算 leading zero 的個數，因此 mask 的作用就是用來去除 lower 中較高的無關位元。從比較的位元數來看，在第四次遞迴時，我們只關注最後 2 位元，因此需要將遮罩設為 14，以確保只保留必要的位元範圍，讓比較過程更有效率。

先針對遞迴的終止的條件來看，當該函式遞迴呼叫三次後 upper 和 lower 會各自剩下 2bits ，因此 JJJJ 應該填入3，這時候假設 upper 不等於0，我們就必須使用 magic 陣列來查表，因為2進位 0、1、2、3 對應的 leading 分別為 2(00)、1(01)、0(10)、0(11)，因此觀察期中 leading 的 zero HHHH 填入2、IIII 填入0。

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

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

quiz 2-3

程式運作邏輯

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
    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;
}

在 find_key 這個函式中，我們要使用對應的 key 來找到其在 map 這個struct 中 ht 的位置在哪裡將其記憶體位址賦值給 head，因此我們在 AAAA 應該要填入 map->bits ，在使用 hash 這個函數查找在 key 在映射到大小為 map->bits 中對應的 bucket 在哪邊。

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, BBBB)];
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first;
    if (first)
        CCCC = &n->next;
    h->first = n;
    DDDD = &h->first;
}

同理在新增操作的地方，假設我們可以在 hash_table 找到該 key 的data 則返回，而假設未找到，則分配一個新 hash_key struct 給他，同時找到該 key 所屬於的 bucket 的 bucket 並將其插入到鏈結串列的起始點，因此 BBBB 在此處我們要填入的是 map->bits 。在教材Linux 核心的 hash table 實作中可以得知，Linux 核心實作中是使用 pointer to pointer 的技巧來指向前一個節點 next 指標的記憶體位址，這樣在做刪除的動作時，可以不用特別去對開頭的節點做例外的處理。所以 CCCC 要填入 first->pprev 使原本起始點 pprev 的指標可以指向新加入節點 next 的記憶體位址，最後，我們將 bucket 本身的起始節點指標更新為新節點 (h->first = n)，並同時設定新節點的 pprev 指標，使其指向 bucket 中的起始指標 (&h->first)，代表新節點現在是該 bucket 的第一個節點。因此，DDDD 要填入 &h->first;，維持鏈結串列中 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 = EEEE;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

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

在這段程式碼的刪除操作中，需要從鏈結串列中移除一個節點，並確保串列在移除後仍維持正確的結構。當要移除節點 n 時，會先取得它的下一個節點 next，並透過 n->pprev 這個 pointer to pointer 取得前一個節點中指向自己的指標位置，因此 EEEE 應填入 n->pprev。接著將 *pprev 設為 next，斷開目前節點與前一節點的連結；若 next 存在，則更新 next->pprev 指向原本的 pprev，讓其指向前一個節點指向自己這個節點的指標記憶體位址。最後將 n 的指標清空，並釋放該節點，即可正確地將節點從鏈結串列中移除，並保持整體結構的完整。