2025q1 Homework2 (quiz1+2)

contributed by: <Beethovenjoker> (章元豪) Github

2025q1 第 1 週測驗題

指標的指標

指標的指標（pointer to pointer），目的是讓插入新節點時的程式碼變得簡潔且不必特別處理串列頭或尾的特殊情況。

void list_insert_before(list_t *list, 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;
}

首先讓 p 指向鏈結串列的開頭（head 指標）。這樣的目的是，不論要插入的位置是串列的何處，都可以用同一套邏輯來處理，不需要額外寫多餘的判斷式。從 head 開始往後找，找到要插入節點的目標位置（before）。每一次迴圈，p 都會向後移動到下一個節點的 next 指標，直到找到我們想插入的位置。最後插入新節點，把新節點 item 放進我們找到的位置。然後讓新節點的next指向before。

管理樹狀結構的記憶體空間

這段程式的功能是從一個二元搜尋樹（Binary Search Tree, BST）中移除一個指定的節點，並且維持原本樹的結構不被破壞。

• 在移除節點時，樹的結構必須保持 BST 的特性:
  • 每個節點左子樹的元素都小於該節點。
  • 每個節點右子樹的元素都大於該節點。
• 移除節點時的三種情況:
  • 沒有子節點 → 直接移除。
  • 只有一個子節點 → 以該子節點取代該節點。
  • 有兩個子節點 → 用它的前驅（左子樹中最大的節點）取代它。

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

當移除節點有兩個子節點時，用前驅節點來取代被移除的節點。

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

先從左子節點開始，往右一直走訪，直到右子節點為 NULL，此時找到的節點就是前驅節點。

target->l = NULL;
target->r = NULL;

移除節點後，最後要清空移除節點的左右指標，防止dangling references。

非遞迴快速排序法

傳統的遞迴快速排序法透過選擇 pivot 並執行分割，將陣列切成左右兩部分，然後遞迴排序。但在非遞迴版本中，這些遞迴呼叫用堆疊模擬，以達到相同效果。

• 演算法步驟
  • 選擇 pivot（選擇鏈結串列最左側的值)。
  • 走訪串列，將小於 pivot 的值存入 left的串列，大於 pivot 的值存入 right串列。
  • 分割成三組：left、pivot、right。
  • 優先排序 right，存入 result。
  • 接著處理 left，最終完成排序。

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

在 Linux list.h 的 struct list_head 是循環鏈結串列，這表示最後一個節點的 next 會回到 head。prev->next = head 讓最後一個節點的 next 回到 head，但還需要將 head->prev 指向最後一個節點，讓 prev 能正確反向連結。

struct list_head *pivot = L;
value = list_entry(pivot, node_t, list)->value;

pivot 是 struct list_head *，但我們需要 pivot 對應的 node_t 結構體的value。因此，我們利用 Linux 核心提供的巨集list_entry(ptr, type, member)，從 list_head 結構中取得對應的container structure，最後從 node_t 的結構體存取value。

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

與前面類似，我們需要從 list_head 結構取得 node_t 的value，因此同樣使用 list_entry()。這樣 n_value 就是目前節點的值，能夠與 pivot 比較來決定該節點應該放入 left 或 right。

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

begin[i+1] 用來存放當前的 pivot 節點，因為 pivot 是分割的中間值，所以它自己就是一個獨立的部分。begin[i] 和 begin[i+2] 分別存放left和right。快速排序法會優先處理 right，確保先排序右邊。

2025q1 第 2 週測驗題

穩定快速排序法

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

這次以 Linux Kernel 的風格來實作穩定快速排序法。

首先，排序開始時，需要選擇 pivot，並且使用了新的巨集 list_first_entry 來取得串列中的第一個元素作為 pivot。這個巨集的效果等價於之前的寫法 list_entry(head->next, struct listitem, list)，它能直接取得節點內部的資料結構，而非單純的指標。

pivot 選定後，必須從原串列中移除，這個操作透過 list_del 巨集完成。list_del 會處理被移除節點前後的串列指標，並將移除節點的前後指標都設置為 NULL，以避免任何未定義的串列存取行為。

接著是將串列根據 pivot 的數值進行分割，這個過程採用的是 list_for_each_entry_safe 巨集。與一般的 list_for_each_entry 不同的是，list_for_each_entry_safe 在走訪串列時允許安全地移動或刪除當前的節點，因為它會事先保存下一個節點（即安全的參考節點）供後續走訪節點使用。

每次遍歷時會使用 cmpint 函式進行數值比較，比 pivot 小的節點使用 list_move_tail 巨集放入 list_less 串列，比 pivot 大或等於 pivot 的節點則放入 list_greater 串列中。這個步驟保證了快速排序法的穩定性，因為使用 list_move_tail 時節點始終被加到目標串列的末端，維持相同鍵值節點的原始相對順序。

完成分割後，list_less 和 list_greater 串列各自進行遞迴排序。

最後一步就是將排序完成的三個部分：list_less、pivot 和 list_greater 合併回主串列中。由於 pivot 只有單一節點，因此只要用 list_add 巨集將其重新接回到主串列 head 後方即可。而 list_less 和 list_greater 是完整的串列，合併時需要使用 list_splice 系列的巨集：

• 將 list_less 使用 list_splice 放在主串列 head 的前面。
• 將 list_greater 使用 list_splice_tail 接在主串列 head 的尾端。

這樣自然形成「less → pivot → greater」的排序結構，達成穩定的快速排序。

整數的開平方根運算

Leading zeros

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

#define clz32(x) clz2(x, 0)

c 代表目前遞迴的「切割層級」，從 0 開始，每次切割都會深入一層，直到對應的位元深度為止。程式會先將 x 分為 upper 與 lower 兩部分，其中 upper = x >> (16 >> c) 負責取得較高的一半 bits，例如當 c=0 時表示取 x 的高 16 bits，而當 c=1 時則表示取 16 bits裡面的更高 8 bits。
至於 lower = x & (0xFFFF >> mask[c])，則會透過 mask[c] 動態控制保留的低位範圍，像第一層保留低 16 bits、第二層保留低 8 bits 等。
若計算出來的 upper 不為 0，表示前導 0 不會全部落在高位都是 0 的情況，因此要繼續往高位這邊遞迴檢查；若 upper 為 0，代表那一半的 bits 全部都是 0，就可以一次略過這些位元並把它們全算進前導 0 的總數，再去檢查 lower 這一半。透過這種對半分割的遞迴方式，便能在較少層級內完成前導 0 的計算。

if (c == 3)
    return upper ? magic[upper] : KKKK + magic[lower];

這裡用一個小小表格 magic[ ] 去對應最末段的 bits。因為最後只剩 2 bits 時，其可能有 4 種情形：00, 01, 10, 11，而每種情形對應的 leading zero 數量不同。為了簡化判斷，就直接用查表的方式。

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

先檢查 64 位元整數 x 的upper 32 bits，如果不為 0，表示最高的 set bit 一定落在這部分，接下來只要對那 32 bits 呼叫 clz32() 即可得到結果。如果高 32 bits 為 0，則代表前 32 bits 全都是leading zeros，因此要先加上這 32 個零，然後再對lower 32 bits 呼叫 clz32()，將該部分的leading zeros 數量加總起來。

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

先透過 clz64(x) 找出 x 的最高位元，將其索引對齊到偶數（確保以 4 的冪次做初始試探），然後在 while 中，一邊將 y 右移 1（為新位騰空）並檢查「若 x 尚可扣除 y + m，則扣除後並把 m 加回 y」，並在每回合將 m 右移 2（往更低 2 bits 測試），最終累積得出的 y 即為

$\lfloor x\rfloor$。

Reference

• 2025q1 第 1 週測驗題
• 2025q1 第 2 週測驗題