---
# System prepended metadata

title: linux2025-homework2
tags: [linux 核心設計]

---

# 2025q1 Homework2 (quiz1+2)
contributed by < timsong1 >

## Review [第一周測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)

### 測驗 1
本題的 **單向鏈結串列**資料結構:
```cpp
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;
```
![linked_list](https://hackmd.io/_uploads/ByMZcSr3kx.png)

在這種資料結構中，會有一個 `head` 指標當作 [dummy node (或叫 sentinel node)](https://en.wikipedia.org/wiki/Sentinel_node)
這在鏈結串列是很常使用到的實作方式，主要原因：
1. 統一處理邊界條件，在沒有 dummy node 的情況下，對於頭節點的插入、刪除等操作常常需要額外判斷
2. 有了 dummy node，程式碼在走訪與修改串列時，就不需要再寫額外的 if 判斷來檢查當前節點是否為頭節點

這也是 Linus Torvalds 在[演講](https://www.youtube.com/watch?v=o8NPllzkFhE&t=850s)中提到的在程式設計中所謂 "good taste"

要實作的 `list_insert_before()` 如下:
![image](https://hackmd.io/_uploads/SJQmfUBh1e.png)


```cpp
static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item);
{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}
```
已知要使用[間接指標](https://stackoverflow.com/questions/72910521/what-difference-between-direct-pointer-and-indirect-pointer)，因此要使一個間接指標( 如 `list_item_t **p`) 直接指向某一個指標，透過直接修改`p`來達成"**間接**"修改被指向的指標所指向的位址
在程式碼中可看到 for 迴圈，因此可以知道`AAAA`為串列`l`的`head`指標位址
`AAAA = &l->head`
而`BBBB`為迴圈的中止條件，根據題意可知要停在`before`
`BBBB = before`
而`CCCC`則是要用來更新間接指標，指向下一個節點的`next`指標
`CCCC = &(*p)->next`
最後間接指標指到`before`時，透過改變`p`來"間接"改變原本的串列
再讓`item`節點接上`before`
`DDDD = item->next`

---
### 額外補充：assert marco

### 測驗 2
本題的二元樹資料結構：
```cpp
typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;
```
![linked_list](https://hackmd.io/_uploads/HJlwI3IShyl.png)

以下是要實作的程式碼片段:
```cpp
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
            .
            .
            .
/* 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;
```
透過註解可得知要透過這迴圈找到 in-order [predecessor](https://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/) (所以可以預設該樹為 BST)，
就是`node_ptr`指向的節點的 predecessor，也就是小於該節點的所有節點中，最大的節點：
`the rightmost node in the left subtree`

因為`pred_ptr`在進入迴圈前已經指向`node_ptr`的左子樹，在迴圈內則是要一直往右子樹走訪，最後會`pred_ptr`指向某個節點，其`r`指向`NULL`
`EEEE = (*pred_ptr)->r`
`FFFF = &(*pred_ptr)->r`

---
### 測驗 3

```cpp
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 */;
}
```
單從這函式看可以知道是在把雙向鏈結串列中的每個`prev`指標重新接上
while 迴圈結束後只剩下`prev`跟`head`互相鏈接
`GGGG = head->prev=prev`

資料結構:
```cpp
typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;
```

quick sort 主體：
```cpp=
{
    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);
}
```

這個 quick sort 是使用非遞迴方法，可以參考[詳細解說](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)
其實這題單看程式碼，如果理解 quick sort ，應該便能知道答案
13行得知算出`pivot`
14行可知要算出`pivot`的`value`，再搭配使用 list.h 的 marco
`HHHH = list_entry(pivot,node_t,list)->value`
`IIII = list_entry(n,node_t,list)->value`
`JJJJ = pivot`
`KKKK = right`

---
## Review [第二周測驗題](https://hackmd.io/@sysprog/linux2025-quiz2)
