---
tags: linux2025
---

# [2025q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 1 週測驗題

:::info
目的: 檢驗學員對間接指標、[鏈結串列](https://hackmd.io/@sysprog/c-linked-list)及記憶體配置的認知
:::

==[作答表單: 測驗 `1` 和測驗 `2`](https://docs.google.com/forms/d/e/1FAIpQLSe2f0puSOzUwczblrK0rqQVVhM0VShl4ztaztR4mqUS6sTQPg/viewform)==
==[作答表單: 測驗 `3`](https://docs.google.com/forms/d/e/1FAIpQLScZ91gyJQcxyGbicz0TStEIIi5nll8Kf_-9BxJrSOzsf3n9eQ/viewform?usp=dialog)==

### 測驗 `1`

以下程式碼運用〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉提及的 "a pointer to a pointer" 技巧，撰寫鏈結串列的經典操作。

考慮以下程式碼：

#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_insert_before` 函式的語意如下：

對應的測試程式碼如下：

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

#include "list.h"

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

#define N 1000

static list_item_t items[N];
static list_t l;

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

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

int tests_run = 0;

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

預期執行時期不會遇到 [assert](https://man7.org/linux/man-pages/man3/assert.3.html) 錯誤。參考執行輸出：

---=[ List tests
ALL TESTS PASSED
Tests run: 1

`list_insert_before` 函式

{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

補完程式碼，使其符合預期。
作答規範:
* AAAA, BBBB, CCCC, DDDD 皆為 C 語言表示式，不含 `;` 或 `,` 字元
* 以最精簡的方式撰寫，不包含空白

:::success
延伸問題:
* 解釋上方程式碼運作原理
* 在現有的程式碼基礎上，撰寫合併排序操作
:::

---

### 測驗 `2`

下圖展示常見的虛擬記憶體架構，其中有些資料結構的大小（如陣列）是在程式執行期間動態決定的，所以必須有個可以動態成長的區域，稱作 heap。對於每一個行程（process），作業系統核心會維護一個指標 brk 用來指向 heap 的頂部。

以下嘗試實作動態記憶體配置器，包含 `malloc`, `free` 及 `realloc`。這類配置器我們稱為顯式配置器（explicit allocator），程式必須明確呼叫 `free` 來釋放記憶體空間。顯式配置器必須符合以下條件：
- 處理任意請求序列
- 立即處理需求
- 只能使用 heap 空間
- 地址對齊：提高記憶體存取效率，例如 `malloc` 在 32 位元系統上為 8 Byte 對齊，64 位元系統則為 16 Byte 對齊 $\to$ [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
- 不得修改已配置的區塊

配置器的實作必須在這些限制條件下，盡可能地在吞吐率 (throughput) 與空間利用率 (ttilization) 之間找到平衡。

- [ ] 吞吐率 (Throughput)

單位時間內（通常為秒）可完成的配置 + 釋放請求數量。

- [ ] 空間利用率 (Utilization)

$$
U_k = \frac{\max_{i \leq k} P_i}{H_k}
$$
其中：
- $\max_{i \leq k} P_i$：過去 $k$ 個請求中，最大的有效荷載(payload) 總和
- $H_k$：目前 heap 的大小

要處理好吞吐率與空間利用率的平衡，配置器的實作必須考慮以下問題：
- free block 結構：如何紀錄 free block
- allocate：如何選擇合適的 free block 來放置新配置的 block
- split：放置新配置的 block 後，如何處理剩餘的空間
- coalesce：剛釋放的 block 前後是否有其他 free block 可合併成一個更大的 free block


以往的實作中，每種類別大小（size-class）的空間都有一個 Free list，。隨著程式的執行，相同大小的空間地址可能會分散在整個記憶體的各個位置，長期下來會導致空間區域性 (spatial locality) 變差。

以下是一個 8 Bytes 的 Free list 在程式執行一段時間後的狀況：

此時，若配置（allocate）一個 8 Bytes 的鏈結串列，將會形成一個空間區域性很差的鏈結串列。

於是，我們利用分頁 (paging) 特性，確保每個分頁僅存放特定大小類別 (size-class) 的空間，藉此提升空間區域性。

下圖為一個 8 Bytes 的 `mimalloc` Free list。

下方程式碼嘗試管理樹狀結構的記憶體區塊： (部分遮蔽)

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

請依據程式碼註解，補完程式碼以符合預期。

作答規範:
* EEEE 和 FFFF 為 C 語言表示式，不含 `;` 或 `,` 字元
* 以最精簡的方式撰寫，不包含空白

延伸閱讀:
* [Custom memory allocators](https://www.rastergrid.com/blog/sw-eng/2021/03/custom-memory-allocators/)

:::success
* 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
* 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
:::

---

### 測驗 `3`

〈[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)〉提出非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 `L` 與 `R` 去紀錄需交換的數量，再用 `begin[]` 與 `end[]` 作為堆疊，用來紀錄比較的範圍。

假定下方是起始的陣列內容。採取 head 作為 pivot，並且 L 會從左邊開始掃，紀錄有多少值小於 pivot，R 從右邊開始，紀錄有多少值大於 pivot。(R 一開始會定義為陣列的 length，以減法的方式紀錄)
> 這裡的 L 就會是 3，而 R 就會是 5

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        pivot[shape=plaintext,fontcolor=red]
        L[shape=plaintext,fontcolor=green]
        R[shape=plaintext,fontcolor=green]
        rankdir=LR
        {
            rankdir = LR
            P[label=4]
            A[label=4]
            B[label=1]
            C[label=3]
            D[label=5]
            E[label=2]
            F[label=7]
            NULL1[label=NULL,shape=plaintext]
        }
        
        {
            rank="same"
            pivot->P
            head->A
        }
        {
            rank="same"
            L->D 
        }
        {
            rank="same"
            R->E
        }
        A->B->C->D->E->F->NULL1
	}

於是會把 array[4] 放到 array[0]，array[3] 放到 array[4]，再把 pivot 放入 array[3]

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        pivot[shape=plaintext,fontcolor=red]
        rankdir=LR
        {
            rankdir = LR
            P[label=4]
            A[label=2]
            B[label=1]
            C[label=3]
            D[label=4]
            E[label=5]
            F[label=7]
            NULL1[label=NULL,shape=plaintext]
        }
        
        {
            rank="same"
            head->A
            pivot->P
        }
        A->B->C->D->E->F->NULL1
	}

再來就是利用 begin 與 end 作為堆疊，去儲存尚未排列好的序列，由於 pivot 目前在 array[3] 的位置，所以就會有一組 begin 跟 end 為 0~2、一組為 4~5。之後會重複上述的行為，一次會以 5 為 pivot，另一次則會以 2 為 pivot，就可以得到排序好的陣列。

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        rankdir=LR
        {
            rankdir = LR
            A[label=1]
            B[label=2]
            C[label=3]
            D[label=4]
            E[label=5]
            F[label=7]
            NULL1[label=NULL,shape=plaintext]
        }
        
        {
            rank="same"
            head->A
        }
        A->B->C->D->E->F->NULL1
	}

用變數 `i` 紀錄現在的 `stack` 在什麼位置，每次迴圈的開始都進行 pop 的操作：

node_t *top = stk[i--];

依照相對於 `pivot` 大小整理節點的步驟沒有不同。而分類完 `left` 和 `right` 之後，本來應該各自遞迴計算的部分換成「放進堆疊中」，換言之，這份程式碼嘗試用堆疊模擬原本的遞迴呼叫。

考慮以下的鏈結串列結構體:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

操作鏈結串列的圖解：

digraph g1 {
    node[shape=plaintext];
    left [fontcolor="brown"];
    p0 [fontcolor="black"];
    p1 [fontcolor="black"];
    p2 [fontcolor="black"];
    p3 [fontcolor="black"];
    p4 [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        p3 -> n3 -> p1 -> n1 -> p0  -> n0 -> p2 -> n2 -> p4 -> n4 -> l0; 
    }
    left -> p3;
    
}

digraph g2 {
    node[shape=plaintext];
    left [fontcolor="brown"];
    p0 [fontcolor="black"];
    p1 [fontcolor="black"];
    p2 [fontcolor="black"];
    p3 [fontcolor="black"];
    p4 [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        p3 -> n3 -> p1 -> n1 -> p0  -> n0 -> p2 -> n2 -> p4 -> n4 -> l0;
    }
    left -> p1;
    
}

以下運用 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。
* begin[i], end[i] 分別用來存放單一排序分割的起始點和終點，i 為分割編號
* left 用來存放小於等於 pivot 的節點
* right 用來存放大於 pivot 的節點
* result 用來存放排序完的分割

其流程為
* 以 L R 指向`串列分割 i` 之兩端，當 L R 尚未交會則進行內部排序
* 最左邊的數設為 pivot，p 則指向 pivot 隔壁的節點，pivot 的 next 指向 NULL
* 指標 p 會一直往右走，將大於 pivot 的節點存入 right ， 小於的存入 left
* 接著可得到三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2
* 下一回合將進行 `串列分割 i+2` 之內部排序（也就是先排右邊）
* 直到右邊都排序完成後，才會將排序完的分割存入 result，並開始進行左邊分割的排序。

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

操作鏈結串列的圖解：

digraph g1 {
    node[shape=plaintext];
    "begin[0]" [fontcolor="brown"];
    "end[0]" [fontcolor="brown"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    p [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n3 -> n1 -> n0 -> n2 -> n4 -> l0
    }
    "begin[0]" -> n3;
    "end[0]" -> n4;
    pivot -> n3;
    L -> n3;
    R -> n4;
    p -> n1;
}

digraph g2 {
    node[shape=plaintext];
    "left" [fontcolor="purple"];
    "right" [fontcolor="purple"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    p [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    l3 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n1 -> n0 -> n2 -> n4 -> l0
    }
    pivot -> n3 -> l1;
    left -> l2;
    right -> l3;
    L -> n3;
    R -> n4;
    p -> n1;
}

digraph g3 {
    node[shape=plaintext];
    "left" [fontcolor="purple"];
    "right" [fontcolor="purple"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    p [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    l3 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n0 -> n2 -> n4 -> l0
    }
    pivot -> n3 -> l1;
    left -> n1 -> l2;
    right -> l3;
    L -> n3;
    R -> n4;
    p -> n0;
}

digraph g4 {
    node[shape=plaintext];
    "left" [fontcolor="purple"];
    "right" [fontcolor="purple"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    p [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    l3 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n2 -> n4 -> l0
    }
    pivot -> n3 -> l1;
    left -> n1 -> n0 -> l2;
    right -> l3;
    L -> n3;
    R -> n4;
    p -> n2;
}

digraph g5 {
    node[shape=plaintext];
    "left" [fontcolor="purple"];
    "right" [fontcolor="purple"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    p [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    l3 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    left -> n1 -> n0 -> n2 -> l0;
    pivot -> n3 -> l1;
    right -> l2;
    L -> n3;
    R -> n4;
    p -> n4;
}

digraph g6 {
    node[shape=plaintext];
    "begin[0]" [fontcolor="brown"];
    "end[0]" [fontcolor="brown"];
    "begin[1]" [fontcolor="brown"];
    "end[1]" [fontcolor="brown"];
    "begin[2]" [fontcolor="brown"];
    "end[2]" [fontcolor="brown"];
    "left" [fontcolor="purple"];
    "right" [fontcolor="purple"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    l3 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    "begin[0]" -> n1;
    "end[0]" -> n2;
    "begin[1]" -> n3; 
    "end[1]" -> n3;
    "begin[2]" -> n4;
    "end[2]" -> n4;
    pivot -> n3 -> l1;
    left -> n1 -> n0 -> n2 -> l3;
    right -> n4 -> l2;
    L -> n3;
    R -> n4;
}

接著我們使用 Linux 核心風格 List API 的簡化標頭檔 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 來改寫快速排序程式碼。首先是結構體：

#include "list.h"

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

快速排序實作的函式原型宣告:

void quick_sort(struct list_head *list);

以下是測試程式碼:

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

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

/* Verify if list is order */
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 array, only work if n < RAND_MAX */
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;
    }
}

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

為了便於實作，我們準備以下輔助函式：

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

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

另一個輔助函式: (部分)

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

接著是 `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 = /* 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 = /* IIII */;
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

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

預期執行時期不會遇到 [assert](https://man7.org/linux/man-pages/man3/assert.3.html) 錯誤。補完程式碼，使其符合預期。

作答規範：
* `GGGG` 為有效 C 語言表示式，不含 `;` 或 `,` 字元
* `HHHH` 和 `IIII` 包含 `list_entry` 巨集，不含 `;` 字元
* `JJJJ` 和 `KKKK` 為有效 C 語言表示式，不含 `;` 或 `,` 字元
* 以最精簡的方式撰寫，不包含空白

:::success
延伸問題:
* 解釋上述程式碼運作原理
* 研讀〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
:::