---
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" 技巧，撰寫鏈結串列的經典操作。
考慮以下程式碼：
```c
#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` 函式的語意如下：
對應的測試程式碼如下：
```c
#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` 函式
```c
{
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。
下方程式碼嘗試管理樹狀結構的記憶體區塊： (部分遮蔽)
```c
#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
```graphviz
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]
```graphviz
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，就可以得到排序好的陣列。
```graphviz
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 的操作：
```c
node_t *top = stk[i--];
```
依照相對於 `pivot` 大小整理節點的步驟沒有不同。而分類完 `left` 和 `right` 之後，本來應該各自遞迴計算的部分換成「放進堆疊中」，換言之，這份程式碼嘗試用堆疊模擬原本的遞迴呼叫。
考慮以下的鏈結串列結構體:
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
操作鏈結串列的圖解：
```graphviz
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;
}
```
```graphviz
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，並開始進行左邊分割的排序。
```c
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;
}
```
操作鏈結串列的圖解：
```graphviz
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;
}
```
```graphviz
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;
}
```
```graphviz
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;
}
```
```graphviz
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;
}
```
```graphviz
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;
}
```
```graphviz
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) 來改寫快速排序程式碼。首先是結構體：
```c
#include "list.h"
typedef struct __node {
long value;
struct list_head list;
} node_t;
```
快速排序實作的函式原型宣告:
```c
void quick_sort(struct list_head *list);
```
以下是測試程式碼:
```c
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;
}
```
為了便於實作，我們準備以下輔助函式：
```c
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;
}
```
另一個輔助函式: (部分)
```c
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` 主體:
```c
{
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 予以實作
:::
Sign in with Wallet
Connect another wallet