2025q1 Homework2 (quiz1+2)

contributed by < lumynou5 >

1-1

list_insert_before 函式巧妙地利用指標的指標來避免特例：

list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
    ;
*p = item;
(*p)->next = before;

由於 p 指向的是「節點指向下一個節點的指標」，因此可以用來判斷是否到達 before 和修改前一個節點的值，而不需要兩個 list_item_t *，且避免了 before 為 l->head 時的特例，因為 list_t 是不同的結構體，如果使用 list_item_t *，要將節點插入為第一個節點，就得額外處理。

一個簡單的合併排序實作是：

list_item_t const DUMMY_LIST_ITEM = { .value = INT_MAX };

static void list_merge_sort_impl(list_item_t **pbegin, list_item_t *end)
{
    if ((*pbegin)->next == end) // We have a single node in this sub.
        return;

    list_item_t *slow = *pbegin;
    for (list_item_t *fast = slow->next; fast != end && fast->next != end;) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_merge_sort_impl(pbegin, slow->next);
    list_merge_sort_impl(&slow->next, end);

    list_item_t *l = *pbegin, *r = slow->next, **p = pbegin;
    while (l != &DUMMY_LIST_ITEM || r != &DUMMY_LIST_ITEM) {
        if (l->value < r->value) {
            *p = l;
            l = l->next != slow->next ? l->next : &DUMMY_LIST_ITEM;
        } else {
            *p = r;
            r = r->next != end ? r->next : &DUMMY_LIST_ITEM;
        }
        p = &(*p)->next;
    }
    *p = end;
}

void list_merge_sort(list_t *l)
{
    if (!l)
        return;
    list_merge_sort_impl(&l->head, NULL);
}

首先以快慢指標找到第一段的結尾、第二段的開頭（slow->next），將兩段分別排序，然後再合併起來，很普通的遞迴式合併排序。

1-2

函式 remove_free_tree 的核心部分為：

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

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

    if (*pred_ptr == (*node_ptr)->l) {
        block_t *old_right = (*node_ptr)->r;
        *node_ptr = *pred_ptr;
        (*node_ptr)->r = old_right;
    } 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;
    }
} 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;
}

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

• 第 4 行：同樣利用間接指標來找到前導節點（左子樹中最右的節點），消除了可能是其親代節點的左或右子節點的差異。
• 第 8 行：若前導節點就是 target 的左子節點，表示前導節點沒有右子節點，直接以其替換 target，然後將原本的右子樹移過去即可。
• 第 12 行：若前導節點在更深處，則將其移到 target 的位置替換之。因為遞迴呼叫了 remove_free_tree，前導節點自身的子節點（若有）會替換到合適位置，然後直接將原本的左右子樹移過去即可。
• 第 21 行：若 target 只有一個子節點，以該子節點替換之即可。
• 第 24 行：若 target 沒有子節點，直接將指向它的指標設為 NULL，就將它從樹中移除了。

第 21 行與第 24 行的分支可以合併，因為如果 target 沒有子節點，(*node_ptr)->r 就是 NULL，刪除這個分支能夠省去 4 道指令（x86-64 gcc 14.2 -O3，Compiler Explorer 演示）。

第 15 行的 pred_node 似乎完全不必要，只在一處使用，完全可以用 *pred_ptr 替代。乍看之下像是儲存原本的值，避免函式呼叫中修改了，但 pred_ptr 指向哪實際上不可能被修改。而在一開始，*node_ptr 和 target 指向的是同一個物件，差別在於前者實際上是「在 target 原位的節點」，透過將程式碼中一些 *node_ptr 改為 target 能讓程式碼更簡短且意圖更清楚，old_left、old_right 也可以用 target->l、target->r 替換：

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

if (target->l && target->r) {
    block_t **pred_ptr = &target->l;
    while ((*pred_ptr)->r)
        pred_ptr = &(*pred_ptr)->r;

    if (*pred_ptr != target->l) {
        remove_free_tree(&target->l, *pred_ptr);
        (*node_ptr)->l = target->l;
    }
    (*node_ptr)->r = target->r;
    *node_ptr = *pred_ptr;
} else {
    block_t *child = target->l ? target->l : target->r;
    *node_ptr = child;
}

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

但我發現這樣修改後，-O3 下產生的組合語言反而更長。在閱讀過組合語言後，我發現是一些分支被展開了，事實上在 -O0 下以上程式碼產生的組合語言確實短非常多，-O1 下更短，但 -O2、-O3 卻都比各自的上一等級產生更長的組合語言。我認為這是因為編譯器判斷分支足夠短，直接重複部分指令兩次的收益高過膨脹的檔案大小。

TODO: 測試實際效能。

1-3

函式 quick_sort 的主體：

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;
        struct list_head *p = pivot->next;
        pivot->next = NULL;

        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;
    } else {
        if (L) {
            L->next = result;
            result = L;
        }
        i--;
    }
}
list->next = result;
rebuild_list_link(list);

流程（以最外層迴圈第一次迭代的視角描述）：

• 首先將串列的第一個節點作為軸節點，依次將剩餘的節點和其比較，分別放入 left 和 right 中。
• 將 left、pivot 和 right 分別推入堆疊。
• 重複以上流程，但對象的串列是剛剛推入堆疊的 right。這會對每個推入堆疊的串列重複，直到（不是直到所有串列都，而是「深度優先」地，因為堆疊先進後出）串列中只有零或一個節點。
• 若串列中只有零或一個節點，將那唯一的節點（若有）插到 result 的最前面，然後從堆疊彈出這個串列。

由於堆疊先進後出的特性，以及最後得到結果時是插到最前面，值相等的節點順序會反過來，因此排序並不是穩定的。

2-1

函式 list_quicksort 的主體：

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

迴圈是從前往後迭代，而 list_move_tail 將節點從串列移到子串列的最後面，因此值相等的節點順序維持不變。如果改為 list_move 移到最前面，那順序就會倒過來，並且因為遞迴，最終的順序其實不一定。