---
# System prepended metadata

title: 2025q1 Homework2 (quiz1+2)

---

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

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   46 bits physical, 48 bits virtual
CPU(s):                          28
On-line CPU(s) list:             0-27
Thread(s) per core:              2
Core(s) per socket:              20
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           183
Model name:                      Intel(R) Core(TM) i7-14700 ＠ 1.50 GHz
Stepping:                        1
CPU MHz:                         1100.3190
CPU max MHz:                     5400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4224.00  
Virtualization:                  VT-x
L1d cache:                       768 KiB
L1i cache:                       1 MiB
L2 cache:                        28 MiB
L3 cache:                        33 MiB 
NUMA node0 CPU(s):               0-27
```


## [Quiz 1-1](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1)
### 單向鏈結串列
![graphviz (3)](https://hackmd.io/_uploads/HJW685pjJe.svg)
```
digraph foo {
	rankdir=LR;
	node [shape=record];
	a [shape=none, label="list_t"] 
	b [label="<name> list_item_t |{ <data> 99 | <ref> }"];
	c [label="<name> list_item_t |{ <data> 37 | <ref>  }"];
	d [shape=none, label="NULL"];
	a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both,  arrowsize=1.2];
	b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
	c:ref:c -> d      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

研讀完成程式碼和示意圖得知這題屬於單向鏈結串列的插入，因此和 `lab0-c/queue.c` 最主要的差別是不用管理 `prev` 指標也沒有 circular。
### assert
研讀測試程式碼時我發現 `my_assert` 使用 `do{...} while(0)` 但明明只執行一次，所以我特別針對這部分蒐集了一些資料：

- `my_assert` 為何使用 `do{...} while(0)`

先講結論，`#define assert` 即使時執行一次卻使用 `do{...} while(0)` 是因為**強制該區塊始終作為單一語句**即使是在**多行程式碼**的情況下，並且希望可以把宏定義的用法和**一般函式一致**。

以 `my_assert` 使用 `do{...} while(0)`舉例：
```c
#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)
```

以及如果定義 `my_assert` 不使用 `do{...} while(0)`：

```c
#define my_assert(test, message) if (!(test)) return message;
```

`my_assert` 在測試程式展開後，會出現 `x` 在 0~10 的區間無法正確顯示 `x is non-positive`。：

```diff
#define my_assert(test, message) if (!(test)) return message;

const char* check_value(int x) {
    if (x > 0)
-        my_assert(x > 10, "x is too small");
+        if (!(x > 10)) return "x is too small";  // <-- 這個 if 來自 my_assert macro
    else
        printf("x is non-positive\n");  // <-- 這個 else 與 my_assert 內的 if 錯誤匹配
    return "OK";
}
```

原因是基於 `C99 6.8.4.1p3` 中敘述 `else` 會最近的 `if` 配對，因此 `my_assert` 導致 if-else 區塊判斷錯誤:
> An else is associated with the lexically nearest preceding if that > is allowed by the
> syntax. [C99 6.8.4.1p3]

- `my_assert` 為何不使用 `{...}` 

使用 `{...}` 在上述例子中可以解決 `if-else` 問題但**處理包含多行語句**的情況會有額外的操作，以下假設 `my_assert` 變成多行語句：
```diff
define my_assert(test, message) \
    {                            \
        if (!(test))             \
            return message;      \
+        printf("ok");             \
    }
```

你在使用宏定義時就必需省略 `;` 而無法像一般的函式一樣呼叫：
```diff
const char* check_value(int x) {
    if (x > 0)
-        my_assert(x > 10, "x is too small");
+        my_assert(x > 10, "x is too small")
    else
        printf("x is non-positive\n");  // <-- 這個 else 與 my_assert 內的 if 錯誤匹配
    return "OK";
}
```

以上討論偏向**語法正確性**方面並且提供 [C99](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 的出處，還有更多關於**程式品味**的原因可見參考資料。

**參考資料：**
- [Why use do { } while (0) in macro definition? [duplicate]](https://stackoverflow.com/questions/9495962/why-use-do-while-0-in-macro-definition)


---

### list_insert_before

```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_t | list_item_t |
| -------- | -------- |
|![graphviz (14)](https://hackmd.io/_uploads/BykCLapi1e.svg)|![graphviz (13)](https://hackmd.io/_uploads/H1gcITTi1e.svg)|

測試程式如下：
```c
for (size_t i = 0; i < N; i++)
    list_insert_before(&l, l.head, &items[i]);
```
將所有的 `list_reset` 初始化的節點利用 `list_insert_before` 插入鏈結串列最後用 `my_assert` 確認鏈結串列長度正確，因此插入會面對兩種情況：
1. 空鏈結串列
![graphviz (2)](https://hackmd.io/_uploads/BkUYI9asyg.svg)
2. 非空鏈結串列
![graphviz (3)](https://hackmd.io/_uploads/HJW685pjJe.svg)

以下是`list_insert_before` 要求操作：
![image](https://hackmd.io/_uploads/BJbUohpoye.png)

根據要求 `list_insert_before` 可以看到 `@before`：
> If @before is the head of list, the new item is inserted at the front.

`head` 就是被 `list_t->head` 所指向的 `list_item_t`

![graphviz (4)](https://hackmd.io/_uploads/ByrxMapoyl.svg)
代表 `list_t` 不屬於 `head` 當 `@before` 指向 `head` 時就是在鏈結串列起點插入。
![graphviz (7)](https://hackmd.io/_uploads/BJep1GpTs1x.svg)
插入新的 `item` 後 `item` 變成新的 `head`
![graphviz (9)](https://hackmd.io/_uploads/BytBmTas1g.svg)

```diff
static inline void list_insert_before(list_t *l,
                                    list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
-   *p->next = before;
+   (*p)->next = before;
}
```
> The syntax specifies the precedence of operators in the evaluation of an expression, which is the same
as the order of the major subclauses of this subclause, highest precedence first[C99 6.5 footnote 74]

[C99](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 規格書中 6.5 註腳 74 提出表達式的運算子優先級和子標題順序一致故可知優先級 `&` > `->` > `*`。所以以上寫法並不等價。
## 延伸題目
### 程式運作
程式的運作如下圖所示:
![graphviz (15)](https://hackmd.io/_uploads/BybueUAskl.svg)
首先建立一個指標的指標指向 `list_t` 的 `head`。
![graphviz (18)](https://hackmd.io/_uploads/S1xu7U0jke.svg)
如果 `head` 指向的 `list_item_t` 就是 `@before` 所指
![graphviz (19)](https://hackmd.io/_uploads/BkiP4LRoyg.svg)
則使用解引用操控 `head` 指向 要加入的 `item`，然後操作 `item` 的 `next` 指向 `@before` 所指的 `list_item_t`。
![graphviz (20)](https://hackmd.io/_uploads/H1QyBLCokg.svg)
如果指標的指標指向還未指向 `@before` 所指的 `list_item_t`，則利用迴圈使指標的指標指向目前 `item` 的 `next` 所指的 `item` 的`next` 直到遇到 `@before` 所指的 `list_item_t`。

### 撰寫合併排序操作
以 `list_insert_before` 為基礎撰寫合併排序操作，合併排序主要利用分治法來操作，`q_sort` 利用遞迴將整個鏈結串列分成多個鏈結串列，`mergeTwoList` 再兩兩合併直到合併成一個完整的鏈結串列。
![image](https://hackmd.io/_uploads/SJL9s8Asyx.png)

將 `mergeTwoList` 改為使用 `list_insert_before` 操作。

```
void mergeTwoList(list_t result, 
                    list_t *left,
                    list_t *right)
{
    result->head = NULL;
    
    while (!left->head && !right->head) {
        if (left->head->value <= right->head->value) {
            list_item_t *item = left->head;
            left->head = item->next;

        } else {
            list_item_t *item = right->head->next;
            right->head = item->next;
        }
        item->next=NULL;
        list_insert_before(&result, result->head, item);
    }
    
    while (!left->head) {
        list_item_t *item = left->head;
        left->head = item->next;
        item->next=NULL;
        list_insert_before(&result, result->head, item);
    } 
    
    while (!right->head) {
        list_item_t *item = right->head->next;
        right->head = item->next;
        item->next=NULL;
        list_insert_before(&result, result->head, item);
    }
    
    return;
}
``` 
以升序排序為例：首先當合併 `left` 和 `right` 兩者都還有 `list_item_t` 時就要比較 `head->value` 的大小並取出 `head->value`。
![graphviz (22)](https://hackmd.io/_uploads/rJUTuw0oJl.svg)

比較 `head->value` 的大小並取出 `head->value` 較小的作為 `item`，然後使用 `list_insert_before` 將 `item` 插入暫存結果的 `result` 的尾端。
![graphviz (23)](https://hackmd.io/_uploads/S1OVoDRiJg.svg)

當 `left` 和 `right` 兩者其中之一已經為空則將剩下的所有元素依序插入 `result` 的尾端。
![graphviz (25)](https://hackmd.io/_uploads/ByND6vCoJg.svg)

## [Quiz 1-2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2)
基於註解說明可知道這一段程式碼希望找到左子樹的:
```
        /* 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;
```
![graphviz (27)](https://hackmd.io/_uploads/SyoCRSx2yg.svg)

首先我參考指標的指標的概念填寫答案，主要希望是可以找到上圖中黃色虛線的左子樹最右的節點：
- `EEEE` = (*pred_ptr)->r
- `FFFF` = &(*pred_ptr)->r

### 程式運作
`remove_free_tree` 的運作主要是為了找到 `malloc` 時所需的 free chunk (節點)這些節點由二元樹 `free_tree` 管理
- 首先使用 `find_free_tree` 找到符合我們的目標也就是尺寸符合需求的節點並且使用指標的指標 `node_ptr` 操作該節點。
- `remove_free_tree` 希望移除該節點，所以針對該節點的狀態決定操作：
    - 節點沒有子樹，直接移除該點
    - 節點只有左右子樹其一，該子樹的根直接變成 `node_ptr` 
    - 節點左右子樹要先利用 `find_predecessor_free_tree` 確保 `predecessor` 正確並進一步針對 `predecessor` 的狀態來做不同的操作
        - `predecessor` 是子樹的根
        - `predecessor` 在更深的位置

針對節點左右子樹都有，移除操作需要找到該節點 in-order 走訪順序的前者來代替該節點的位置稱為 `predecessor`。 
- 針對 `predecessor` 是子樹的根：
![graphviz (31)](https://hackmd.io/_uploads/H1scGPghkg.svg)
首先利用 `old_right` 指標紀錄原本的右子樹，並將要移除的節點移除，然後讓新的根也就是舊的左子樹的右子樹指標指向`old_right`：
![graphviz (32)](https://hackmd.io/_uploads/SJPYQwx2yl.svg)

- 針對 `predecessor` 在更深的位置：
![graphviz (28)](https://hackmd.io/_uploads/ryzukwg3Je.svg)
分別保存舊有的左右子樹
![graphviz (34)](https://hackmd.io/_uploads/S1mkrwghyl.svg)
並且將 `predecessor` 移出原本的位置
![graphviz (35)](https://hackmd.io/_uploads/H1cOBwg2yx.svg)
再將 `predecessor` 左右子樹的指標指向 `old_right` 和 `old_left`，並用 `assert` 確認左右子樹正確鏈結。
![graphviz (36)](https://hackmd.io/_uploads/HkZ2BDl21x.svg)

## 延伸題目
### 補齊獨立測試程式嗎
因為在[程式運作](https://hackmd.io/A9FKxN6WQN-9Yi4R723XBA?both#%E7%A8%8B%E5%BC%8F%E9%81%8B%E4%BD%9C10)中已經補齊程式碼並講解運作流程，此處提供以下 `assert` 測試所需的測試程式碼。
```c
block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
```
以下是測試程式碼的實作。
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
    if(*root == NULL) return NULL;
    block_t **ptr = root;

    if((*ptr)->size == target->size) 
        return ptr;
    else if ((*ptr)->size > target->size) 
        return find_free_tree(&(*ptr)->l, target);
    else if ((*ptr)->size < target->size) 
        return find_free_tree(&(*ptr)->r, target);
    

    return NULL;
}

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    block_t **ptr = find_free_tree(root, node);

    if (ptr == NULL || *ptr == NULL) {
        return NULL;
    }
    
    if ((*ptr)->l) {
        ptr = &(*ptr)->l;
        while((*ptr)->r){
            ptr = &(*ptr)->r;
        }
    }
    return *ptr;
}
```
[測試程式線上運作](https://onlinegdb.com/eVlsJrRAcC)以下是運行了 `remove_free_tree(&root, root)` 後的結果：


```c
Level 0:           4
Level 1:          2    5
Level 2:         1  3null  6
Level 3:        nullnullnullnullnullnull

Level Order Traversal with Spacing:
Level 0:           3
Level 1:          2    5
Level 2:         1nullnull  6
Level 3:        nullnullnullnull
```

我額外撰寫了 `create_tree` 和 `print_level_order_with_spacing` 來輸出和方便建立二元搜尋樹。

### 記憶體配置器
我參考 [Custom memory allocators](https://www.rastergrid.com/blog/sw-eng/2021/03/custom-memory-allocators/) 製作自訂記憶體配置器，內容資訊存放在 [Custom memory allocators 研讀筆記](https://hackmd.io/@Abel-Chu/Custom_memory_allocators)這邊只擷取用到的資訊。

首先我最擔心的即是整個記憶體配置器的複雜度，但研讀完文章發現其實現在記憶體配置器的分工十分明確，所謂的自訂記憶體配置器只是在記憶體配置器的階層中插入一個元件，這個元件負責接收上一層的記憶體配置器元件並作操作：
- `allocate`：預定子分區的地址範圍
- `deallocate`：釋放子分區的地址範圍
- `resize`：可選項，用於調整已 `allocate` 的子分區的地址範圍大小，較難作的有效率。
目標是針對特地的應用製作專屬的自訂記憶體配置器，而非製作通用的記憶體配置器。

![image](https://hackmd.io/_uploads/Skf4rUZ3yl.png)

#### 實作設計
我目前在這個 repo 實作了 `c_alloc`, `c_free`
> [custom-memory-allocator](https://github.com/CodeStone1125/custom-memory-allocator)

以下是我設計的配置器結構 `free_root` 用指向保存可用區塊的二元搜尋樹：
```c
typedef struct my_allocator {
    size_t total_size;
    size_t peak_size;
    size_t used_size;
    block_t *free_root;
} my_allocator_t;

```
並且我會在已分配的區塊額外分配一個標頭用來存放區塊資訊，例如：區塊大小，因此在 `c_free` 執行後就可以利用區塊資訊建立 `block_t` 插入 `free_root`。一開始實作的效果並不好和 `malloc` 的延遲差了100倍

```
100000 1.204823 0.012557
200000 8.246375 0.025077
300000 23.978644 0.037554
400000 48.674694 0.050032
500000 83.996539 0.062554
600000 134.000926 0.075077
700000 205.729124 0.087639
800000 308.384980 0.100142
900000 452.965177 0.112667
1000000 646.330178 0.125187


```

![image](https://hackmd.io/_uploads/BJPyg3M2kl.png)

**待辦**
需要進一步改善效能然後再次測量

## [Quiz 1-3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)

`GGGG` = head->prev=prev 
`HHHH` = list_entry(pivot,node_t,list)->value
`IIII` = list_entry(n,node_t,list)->value
`JJJJ` = pivot
`KKKK` = right
## 延伸題目
### 程式運作
> graphviz 改自 [Quiz 1-3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)

`list_head` 常用於維護雙向鏈結串列的結構，使用方法是在宣告一格結構 `list_head` 包含來管理鏈結，並利用 `list_entry` 來取得包含 `node_t` 的物件才可以取得物件的其他值。
```graphviz
digraph g1 {
    node[shape=plaintext];
    node[shape=box];
    rankdir=LR;
    n1 [label= "node_t"];
    val [label= "val"];
    subgraph cluster_sub1{
     label = "list_head";
     n1;
     val;
    }
    n1-> NULL[label= "prev"];
    n1-> NULL[label= "next"];
}

```


```
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};
```

考慮到 `list_head` 是雙向鏈結串列而 `quick_sort`，初始化 `begin[0]` `pivot` `L` `R` `end[0]` 等指標，並斷開鏈結串列尾端的鏈結讓他暫時變成單向鏈結串列， 
```c
list->prev->next = NULL;
```

在 `quick_sort` 中不會維護 `prev` 鏈結直到排序完成，所以為了方便呈現在圖片先移出，並且 `pivot` 所在的節點斷開。
    
```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 [label=next fontcolor="purple"]
        n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    "begin[0]" -> n3;
    "end[0]" -> n4;
    pivot -> n3;
    L -> n3;
    R -> n4;
    p -> n1;
}

```
```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 [label=next fontcolor="purple"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    "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 [label=next fontcolor="purple"]
    }
    pivot -> n3 -> l1;
    left -> l2;
    right -> l3;
    L -> n3;
    R -> n4;
    p -> n1;
}
```

`p` 從 `pivot->next` 走訪到尾端的所有的節點，將 `value` 大於 `pivot->value` 放在 `R`，`value` 小於 `pivot->value` 放在 `L` 
```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;
}

```
並且個別的 `begin` `end` 指向 `L` `R` `pivot`，並把 `L` `R` 指向 NULL
```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 -> NULL;
    R  -> NULL;
}

```
`right` 代表的是比 `pivot` 大的節點，然後下一個迴圈從比 `pivot` 大的節點作相同操作，直到找到只剩一個節點(L == R)代表這節點是最大的，將該節點加入 `result`。

```graphviz
digraph g6 {
    node[shape=plaintext];
    "begin[0]" [fontcolor="brown"];
    "end[0]" [fontcolor="brown"];
    "begin[1]" [fontcolor="brown"];
    "end[1]" [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;
    // pivot -> n3 -> l1;
    right -> n3;
    left -> n3;
    n1 -> n0 -> n2 -> l3;
    n4 -> l2;
    L -> NULL;
    R  -> NULL;
    result -> n4;
}

```

```graphviz
digraph g6 {
    node[shape=plaintext];
    "begin[0]" [fontcolor="brown"];
    "end[0]" [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;

    pivot -> n1;
    right -> n1;
    left -> n1;
    n1 -> n0 -> n2 -> l3;
    L -> NULL;
    R  -> NULL;
    result -> n4 -> n3 -> l2;
}

```
因為 `begin[0]` 不只有一個元素，所以重複上述的動作。
```graphviz
digraph g6 {
    node[shape=plaintext];
    // "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"];
   
    l4 [label ="NULL", fontcolor="black"];
    l5 [label ="NULL", fontcolor="black"];
    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }

    pivot -> n1 -> l3;
    // right -> n2;
    // left -> n0;
    // n1 -> n0 -> n2 -> l3;
    L -> n0 -> l4;
    R  -> n2 -> l5;
    result -> n4 -> n3 -> l2;
}

```
再次將節點加入 `result`，即可的到排序完成的結果，並將 `list` 接回來。
```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    // "left" [fontcolor="purple"];
    // "right" [fontcolor="purple"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }


    result -> n4 -> n3 -> n2 -> n1 -> n0 -> l1;
    list -> n4;
}

```

**rebuild_list_link(list)**
利用兩個指標 `prev` `_node` 將 `_node` 的 `prev` 指回 `_prev(節點)`
```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    "_prev" [fontcolor="red"];
    "_node" [fontcolor="blue"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    _prev-> list;
    _node -> n4;
    list -> n4 -> n3 -> n2 -> n1 -> n0 -> l1[label = next,fontcolor="purple"];
            n4 -> list[label=prev fontcolor="purple"]
}

```


```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    "_prev" [fontcolor="red"];
    "_node" [fontcolor="blue"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    _prev-> n4;
    _node -> n3;
    list -> n4 -> n3 -> n2 -> n1 -> n0 -> l1[label = next,fontcolor="purple"];
            n4 -> list[label=prev fontcolor="purple"]
}

```
```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    "_prev" [fontcolor="red"];
    "_node" [fontcolor="blue"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    _prev-> n4;
    _node -> n3;
    list -> n4 -> n3 -> n2 -> n1 -> n0 -> l1[label = next,fontcolor="purple"];
    n3-> n4 -> list[label=prev fontcolor="purple"]
}

```

```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    "_prev" [fontcolor="red"];
    "_node" [fontcolor="blue"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    _prev-> n0;
    _node -> l1;
    list -> n4 -> n3 -> n2 -> n1 -> n0 -> l1[label = next,fontcolor="purple"];
    n0 -> n1-> n2 -> n3-> n4 -> list[label=prev fontcolor="purple"]
}

```
直到 `_node` 指到 `NULL` ，代表 `_prev` 到最後一個節點，將最後一個節點的 `prev` 指向 `list`，`list` 的 `next` 指向最後一個節點。
```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    "_prev" [fontcolor="red"];
    "_node" [fontcolor="blue"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    _prev-> n0;
    _node -> l1;
    list -> n4 -> n3 -> n2 -> n1 -> n0 -> list[label = next,fontcolor="purple"];
    n0 -> n1-> n2 -> n3-> n4 -> list[label=prev fontcolor="purple"]
}

```

```graphviz
digraph g6 {
    rankdir=LR;
    node[shape=plaintext];
    "prev" [fontcolor="red"];
    "_node" [fontcolor="blue"];

    l1 [label ="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
    }
    prev-> n0;
    _node -> l1;
    list -> n4 -> n3 -> n2 -> n1 -> n0 -> list[label = next,fontcolor="purple"];
    n0 -> n1-> n2 -> n3-> n4 -> list[label=prev fontcolor="purple"]

    list  -> n0[label = prev,fontcolor="purple"];
}
```

### 研讀〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉

> Two doubly linked list sorting algorithms are included in this study, the sediment sort and the tree sort. There is no need to repeat the sediment sort here and the interested reader should refer to [2] for the details. 

基於文中提到雙向鏈結串列的排序演算法有 `sediment sort` 和 `tree sort` 所以我會針對這兩個演算法利用 Linux 核心風格的 List API 予以實作。
#### sediment sort
> Commit [f9f1493](https://github.com/sysprog21/lab0-c/commit/f9f1493f6ec69dbea5048a78c25258c152554574)

在這個 `commit` 中我實作了 `sediment sort`：
- 首先考慮到 `list_head` 是雙向鏈結串列斷開鏈結串列尾端的鏈結讓他暫時變成單向鏈結串列，因此同樣的 `prev` 先省略已簡化圖片。
- 初始化 `__prev` 用於交換節點，`new_tail` 用於設定新的迭代結束邊界
- 接下來執行迴圈執行多次迭代，直到一整次迭代中也沒有交換發生。
 
```graphviz
digraph g1 {
    node[shape=plaintext];
    __node [fontcolor="blue"];
    __prev [fontcolor="blue"];
    __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        head->n3 -> n1 -> n0 -> n2 -> n4 -> l0 [label=next fontcolor="purple"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    __node -> n3;
    __prev -> head;
    __next -> l1;
    last_swapped -> l2;
}

```

- 當迭代中交換發生時 `__next` 指向 `__node->next->next`，接下來交換節點。
```graphviz
digraph g1 {
    node[shape=plaintext];
    __node [fontcolor="blue"];
    __prev [fontcolor="blue"];
    __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        head->n3 -> n1 -> n0 -> n2 -> n4 -> l0 [label=next fontcolor="purple"]

        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    __node -> n3;
    __prev -> head;
    __next -> n0;
    last_swapped -> l2;
}

```

```graphviz
digraph g1 {
    node[shape=plaintext];
    __node [fontcolor="blue"];
    __prev [fontcolor="blue"];
    __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n3 -> n1 -> n0 -> n2 -> n4 -> l0 [label=next fontcolor="purple"]
        head-> n1 [color="red"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    __node -> n3;
    __prev -> head;
    __next -> n0;
    last_swapped -> l2;
}

```

```graphviz
digraph g1 {
    node[shape=plaintext];
    __node [fontcolor="blue"];
    __prev [fontcolor="blue"];
    __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n0 -> n2 -> n4 -> l0 [label=next fontcolor="purple"]
        head-> n1 [label=next fontcolor="purple"]
        n1 -> n3 [color="red"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    __node -> n3;
    __prev -> head;
    __next -> n0;
    last_swapped -> l2;
}

```

```graphviz
digraph g1 {
    node[shape=plaintext];
    __node [fontcolor="blue"];
    __prev [fontcolor="blue"];
    __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n0 -> n2 -> n4 -> l0 [label=next fontcolor="purple"]
        head-> n1 -> n3 [label=next fontcolor="purple"]
        n3 -> n0 [color="red"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    __node -> n3;
    __prev -> head;
    __next -> n0;
    last_swapped -> l2;
}

```

> Commit [e9b58b4](https://github.com/sysprog21/lab0-c/commit/e9b58b4759dcd25a4d7a943ae1dccda3c0e51d21)

原本設計每次迭代有交換發生該迭代結束 `new_tail` 向前一個代表最後一個元素不用再檢查代這樣不符合 sediment sort 定義且會增加無謂的檢查次數。這次提交修改設計每次迭代有交換發生該次迭代用 `last_swapped` 指向 `__next` 代表最後交換發生的地方。

```graphviz
digraph g1 {
    node[shape=plaintext];
    __node [fontcolor="blue"];
    __prev [fontcolor="blue"];
    __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        n0 -> n2 -> n4 -> l0 [label=next fontcolor="purple"]
        head-> n1 -> n3 [label=next fontcolor="purple"]
        n3 -> n0 [label=next fontcolor="purple"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    __node -> n3;
    __prev -> head;
    __next -> n0;
    last_swapped -> l2;
}

```

重複上述動作直到，迭代結束 `new_tail` 指向 `last_swapped` 所在位置代表這是新的結束邊界，走訪到那裏即可結束。


```graphviz
digraph g1 {
    node[shape=plaintext];
    // __node [fontcolor="blue"];
    // __prev [fontcolor="blue"];
    // __next [fontcolor="black"];
    last_swapped [fontcolor="red"];
    new_tail  [fontcolor="black"];
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    // l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        head-> n1 -> n0 -> n2 -> n3 -> n4   -> l0 [label=next fontcolor="purple"]
        // n3 -> n0 [label=next fontcolor="purple"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> l0;
    // __node -> n3;
    // __prev -> head;
    // __next -> n4;
    last_swapped ->n4;
}

```

```graphviz
digraph g1 {
    node[shape=plaintext];
    // __node [fontcolor="blue"];
    // __prev [fontcolor="blue"];
    // __next [fontcolor="black"];
    last_swapped [fontcolor="black"];
    new_tail  [fontcolor="red"]
    l0 [label ="NULL", fontcolor="black"];
    // l1 [label ="NULL", fontcolor="black"];
    // l2 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    head [fontcolor="blue"];
    n0 [label= "0"];
    n1 [label= "1"];
    n2 [label= "2"];
    n3 [label= "3"];
    n4 [label= "4"];
    {
        rank="same";
        head-> n1 -> n0 -> n2 -> n3 -> n4   -> l0 [label=next fontcolor="purple"]
        // n3 -> n0 [label=next fontcolor="purple"]
        // n4 -> n2 -> n0 -> n1 -> n3 -> n4[label=prev fontcolor="purple"]
    }
    new_tail -> n4;
    // __node -> n3;
    // __prev -> head;
    // __next -> n4;
    last_swapped ->n4;
}

```
重複以上動作直到整個鏈結串列在一次迭代中走訪完全沒有交換發生，代表排序完成即可用 `rebuild_list_link` 將鏈結串列回復成雙向。

#### tree sort
> Commit [25eab72](https://github.com/CodeStone1125/lab0-c/commit/25eab723379667f9430d267f21c02c28b3d26131)

利用 `list_head` 的 `prev` `next` 指標作為二元搜尋樹的左右指標，建立空二元搜尋樹，使用 `list_each_safe` 將每個節點加入插入二元搜尋樹，再利用參考 [A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893) 提供中序走訪法將所有節點依序插入原本佇列的 `head`。


## [Quiz 2-1](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1)

AAAA = `list_first_entry`
BBBB = `list_del`
CCCC = `list_move_tail`
DDDD = `list_add`
EEEE = `list_splice`
FFFF = `list_splice_tail`

## 延伸題目
### 程式運作
尋常的[快速排序程式碼運作](https://hackmd.io/A9FKxN6WQN-9Yi4R723XBA?view#%E7%A8%8B%E5%BC%8F%E9%81%8B%E4%BD%9C17)在前述內容已提到，這裡主要說明探討 `list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting。這邊已兩個相同值的元素為例：


```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= "2"];
    n1 [label= "1"];
    // n2 [label= "2"];
    // n3 [label= "3"];、
    n4 [label= "2*"];
    {
        rank="same";
        n0  -> n4 -> l0
    }
    pivot -> n1 -> l1;
    left -> l3;
    right -> l2;
    // L -> n3;
    R -> n4;
    p -> n0;
}

```
將 `list_move_tail` 換為 `list_move` 主要影響的就是 `right` 中的排序。
```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= "2*"];
    n1 [label= "1"];

    n2 [label= "2"];
    {
        rank="same";
        // n0  -> n4 -> l0
    }
    pivot -> n1 -> l1;
    left -> l3;
    right -> n0 -> n2 -> l2;
    // L -> n3;
    // R -> n4;
    // p -> n0;
}

```
這邊再次作拆分直到只剩一個元素，然後再將每個元素合併。
```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= "2*"];
    // n1 [label= "1"];
    // n2 [label= "2"];
    // n3 [label= "3"];、
    n4 [label= "2"];
    {
        rank="same";
        n0  -> n4 -> l0
    }
    pivot -> n0;
    left -> l3;
    right -> l2;
    // L -> n3;
    R -> n4;
    p -> n4;
}

```

```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= "2*"];
    // n1 [label= "1"];
    // n2 [label= "2"];
    // n3 [label= "3"];、
    n4 [label= "2"];
    {
        rank="same";
        n0   -> l0
    }
    pivot -> n0;
    left -> l3;
    right -> n4 -> l2;
    // L -> n3;
    // R -> n4;
    // p -> n4;
}

```
`right` 中的排序會影響到整理排序階段的插入順序導致錯誤。
```c
    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
```
```graphviz
digraph g3 {
    rankdir=LR;   
    node[shape=plaintext];
    "head" [fontcolor="blue"];
    l0 [label ="NULL", fontcolor="black"];
    
    node[shape=box];
    n0 [label= "2*"];
    n2 [label= "2"];
    
    head->n0->n2 -> l0


}

```
### 改進 random_shuffle_array
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* WARNING biased shuffling */
        uint16_t j = get_unsigned16() % (i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}
```



參考[統計方法驗證 shuffle](https://hackmd.io/lAzxkK61TAqjm7oVgrmdEQ?view#%E7%B5%B1%E8%A8%88%E6%96%B9%E6%B3%95%E9%A9%97%E8%AD%89-shuffle) 使用 Pearson's chi-squared test 驗證 shuffle 遵守 Uniform distribution。以下是 `random_shuffle_array` 針對三個元素打亂的測量結果： [demo](https://www.programiz.com/online-compiler/65xtOH0k7VrGW)
```
Expectation: 166666.666667
Observation:
123: 206345
132: 126985
213: 150798
231: 182539
312: 206343
321: 126990
Chi-square sum: 40807.197944
```
這是測量 1000000 次後的到的結果：
|| 觀察到的頻率 | 期待的頻率 | ${(O_i - E_i)^2 \over E_i}$ |
| -------- | -------- | -------- | --- |
| [1, 2, 3]    | 206345 | 166666 | 83960.92890363692 |
| [2, 1, 3]    | 126985 | 166666 | 84324.3907689059 |
| [2, 3, 1]    | 150798 | 166666 | 16395.24420533537 |
| [1, 3, 2]    | 182539 | 166666 | 14804.05225658245 |
| [3, 1, 2]    | 206343 | 166666 | 83961.07771676397 |
| [3, 2, 1]    | 126990 | 166666 | 84324.47782047899 |
| Total | | | 40807.197944 |

從[卡方分布表](https://en.wikipedia.org/wiki/Chi-squared_distribution)找合適的 P value，我們的自由度為 5，$X^2$ 為 40807.197944，因為 20.52 < 40807.197944，於是 P value 小於 0.001 。
![image](https://hackmd.io/_uploads/Hyz6btVh1x.png)



因為 P value（0.01）< alpha（0.05），統計檢定的結果拒絕虛無假說（$H_0$）
也就是樣本資料拒絕 shuffle 的結果遵循 Uniform distribution。

改進方法是使用 `Fisher–Yates shuffle` 以下實作及驗證內容我放在 [Fisher–Yates shuffle 實作](https://hackmd.io/gKRaBCWZR3abBEfS8jBlLg#Fisher%E2%80%93Yates-shuffle-%E5%AF%A6%E4%BD%9C)。

### 將程式碼整合進 [lab0](https://hackmd.io/@sysprog/linux2025-lab0) 提及的 `qtest`
我將這部分內容整合到[環狀雙向鏈結串列的排序效能](https://hackmd.io/gKRaBCWZR3abBEfS8jBlLg?view)。



## [Quiz 2-2](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1)
### Digit-by-digit Method
研讀 [Digit-by-digit Method](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method)，重新整理成方便自己理解的推論脈絡：
我們想要找到數字 $N^2$ 的平方根而 $N$ 就是我們要找到的答案是很多個位數組成的，例如：$1000=1*1000+0*100+0*10+0*1$，所以核心思想就是透過公式一個個位數逐步逼近找處接近 $N$ 的值。
$$
N^2 = (a_n+a_{n-1}+\dots+a_{1}+a_0)^2
$$
而 $m$ 元平方和可藉由 $1$ 到 $m-1$ 元平方和總和，同時加上一項兩平方和的差值 $Y_{m}$：
$$
(a_{m}+a_{m-1}+\dots+a_{1}+a_0)^2-(a_{m-1}+\dots+a_{1}+a_0)^2=Y_{m}
$$
$Y_{m}$的公式如下：
$$
Y_{m}=\left[\left(2\sum^{n}_{i=m+1} a_{i}\right) + a_{m}\right]a_{m} = \left( 2P_{m+1}+ a_{m}\right)a_{m}
$$

$Y_{m}$的公式是透過以下推導：
三元平方和
$\begin{align}
    (a+b+c)^2 
    &= ((a+b)+c)^2 \\
    &= (a+b)^2 + (a+b)c +c(a+b) + c^2 \\
    &= (a+b)^2 + (2(a+b)+c)c \\
    &= a^2 + (2a+b)b + (2(a+b)+c)c
\end{align}$

四元平方和
$\begin{align}
    (a+b+c+d)^2 
    &= ((a+b+c)+d)^2 \\
    &= (a+b+c)^2 + (a+b+c)d + d(a+b+c) + d^2 \\
    &= (a+b+c)^2 + (2(a+b+c)+d)d \\
    &= a^2 + (2a+b)b + (2(a+b)+c)c + (2(a+b+c)+d)d
\end{align}$

四元平方和 - 三元平方和
$\begin{align}
    (a+b+c+d)^2 - (a+b+c)^2
    &= ((a+b+c)+d)^2 - (a+b+c)^2 \\
    &= (a+b+c)d + d(a+b+c) + d^2 \\
    &= (2(a+b+c)+d)d \\
    &= (2P_{1}+a_{0})a_{0} \\
    &= Y_{0}
\end{align}$

 
其中 $P_{m+1}=a_n+a_{n-1}+\dots+a_{m+2}+a_{m+1}$ (最高位到低位)而 $P_0=N$（最高位到第 0 位） 且
$$
P_{m} = P_{m+1} + a_{m},\quad \text{for } 1\leq m<n
$$

總結上述兩個觀察，可知：
1. $n$ 元平方和可以藉由 $1$ 到 $n-1$ 元平方和總和，再加一項 $Y_{n}$
2. $Y_{n}=\left( 2P_{n-1}+ a_n\right)a_n$ 其中 $P_{n-1} = P_{n-2} + a_{n-1}$

上述提到的是十進位，但其實延伸到二進位（數值系統）也是同樣的道理：
$b_0$ 為最高位為 $1$ 之位元，二進位轉十進位如下：
$$
\sum_{i=0}^n a_{i}=\sum_{i=0}^n b_i\times 2^{n-i}
$$
假設 $N^2$ 可以用二進位系統逼近：
$$
\begin{align}
    N^2 
    &\approx (b_n\times 2^0 + b_{n-1}\times 2^{1}+\dots b_        1\times2^{n-1} +b_0\times2^n)^2 \\
    &= (a_n + a_{n-1} + \dots a_1 + a_0)^2
\end{align}
$$ 

所以如果在數值系統中，假設是從最高的位數為 $1$ 是第 $n$ 位元，所以套用以下公式從最高位決定每個位元的值，如果已確定 $n$ 到 $m+1$ 位元則判斷 $m$ 位元是否加入逼近值 $N$

$$
P_m=
\begin{cases}
    P_{m+1}+2^{m}, &\text{if }P_m^2 \leq N^2,\\
    P_{m+1}, &\text{otherwise.}
\end{cases}
$$

舉例來說，設 $N^2=10$ 則 $N^2=(10)_{10}=(1010)_2=(b_3\times2^3+b_1\times 2^1)$ ，最高位元 $b_3$ 從 $m=3$ 開始計算。
* $m=3$ 時 $(P_{3})^2 = (a_3)^2 = (2^3)^2 = 64> 10 = N^2$ ，因此 $P_3=P_4$ 且 $a_3=0$。
* $m=2$ 時 $(P_2)^2 = (a_3 + a_2)^2 = (2^2)^2 = 16 > 10 = N^2$ ，因此 $P_2 = P_3$ 且 $a_2=0$
* $m=1$ 時 $(P_1)^2 = (a_3+a_2+a_1)^2 = (2^1)^2 = 4 < 10 =N^2$ ，因此 $P_1=P_2+2^1$ 且 $a_1=2^1$
* $m=0$ 時 $(P_0)^2 = (a_3+a_2+a_1+a_0)^2 = (2^1 + 2^0)^2 = 3^2= 9 \leq 10 = N^2$ ，因此 $P_0=P_1+ 2^0$ 且 $a_0=2^0$

故 $N=P_0= a_1 + a_0 = 2^1+2^0= 3$ ，因此 $10$ 的整數平方根為 $3$。

令 $X_m=N^2-(P_m)^2$ 為差值表實際值與逼近值的誤差，其中 $Y_m=\left( 2P_{m+1}+ a_{m}\right)a_{m}$ 運用以下性質可以縮減上述計算過程：
1. $X_m=N^2-(P_m)^2=X_{m+1}-Y_m$
2. $Y_m=(P_m)^2-(P_{m+1})^2=(2P_{m+1}+a_m)a_m$

研讀後發現以下段落看不懂

$X_m=N^2-Y_m$ 且 $X_m=N^2-P_m^2$ 那不就代表 $P_m^2=Y_m$，這和上述的推論 $Y_m=P_m^2-P_{m+1}^2$ 矛盾而且後面的推導都沒有用到這個設定，因此我判斷此處是筆誤所以對 [Digit-by-digit Method](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method) 做了修改。

因為 $Y_m=(2P_{m+1}+a_m)a_m$ 而且 $a_m = 2^m$，因此 $Y_m=(2P_{m+1}+2^m)2^m=2^{m+1}P_m+(2^{m})^2$

令 $c_m =2a_{m}P_{m+1}= P_{m+1}2^{m+1}$ 與 $d_m = a_m^2=(2^{m})^2$ 。

重新將 $Y_m$ 表示為
$$
Y_m = 
\begin{cases}
    c_m+d_m, &\text{ if }a_m =2^m, \\
    0, &\text{ if } a_m = 0.
\end{cases}
$$

利用$P_m=a_m+P_{m+1}$
$$\begin{align}
c_m &= 2a_mP_{m+1} \\
    &= 2a_m(P_m-a_m) \\
    &= 2a_{m}P_m-2a_m^2 \\
    &= 2c_{m-1}-2a_m^2
\end{align}$$

同時
$$
    d_m = (2^m)^2 = (2\times2^{m-1})^2 = 4(2^{m-1})^2
$$

則 $d_{m-1} = d_m/4$。

所以可推論$\text{ if } a_m\neq 0$
$$
c_{m-1}= {c_m}/2 + a_m^2
$$

同時 $d_m = a_m^2=(2^{m})^2$ 所以
$$
c_{m-1}= {c_m}/2 + d_m
$$

總結迭代關係為
$$
c_{m-1} =
\begin{cases}
    c_m/2 +d_m, &\text{ if } a_m\neq 0, \\
    c_m/2,      &\text{ if } a_m = 0.
\end{cases}
$$
與
$$
    d_{m-1} = d_m/4
$$
帶入 $m=0$ 和 $c_m=2a_m
 P_{m+1}$ 則可以藉由 $c_{-1}$ 得知平方根為
$$
    c_{-1} = P_02^0 = P_0 = N.
$$

### 程式運作
在程式運作中需要找到最高的非 $0$ 位元，因此需要有一個計算  leading zero，例如在 $8$ 位元系統中：$(10)_{10}=(00001010)_2$，leading zero 為 $4$。

```c
#define clz32(x) clz2(x, 0)
```
首先 `clz32` 就是找出32位元的 leading zero 是利用遞迴呼叫 `clz2` 實作。
將此數值等分為兩部分：較高位（upper）與較低位（lower）。


|    Upper |    Lower |
| -------- | -------- |
| 0000 0000 0000 0001 | 1111 0000 0000 0000 |

- 如果 **Upper == 0** 代表只要判斷 Lower的 leading zero 加上 Upper 的位元數即可

- 如果 **Upper != 0** 代表要判斷 Upper 的 leading zero

直到遞迴切割到 Upper 和 Lower 都只剩兩個位元就可以利用查表的方式來得到 leading zero 的值。`clz2(uint32_t x, int c)` 中的 `c` 用來表示遞迴次數，因為 $32=2^5$，所以在對半切三次即可得到終止條件。
```c
static const int magic[] = {2, 1, 0, 0};

if (c == 3)
    return upper ? magic[upper] : 2 + magic[lower];
```
`magic` 用來查表 leading zero 的值，

|   十進位   | 0     | 1     | 2     | 3     |
| --------| -------- | -------- | -------- | -------- |
| 二進位 | 00 | 01 | 10 | 11 |
| leading zero | 2     | 1     | 0     | 0     |


`mask` 是用來控制切割位元大小用來得到該次 lower。
```c
static const int mask[] = {0, 8, 12, 14};
uint32_t lower = (x & (0xFFFF >> mask[c]));
```


```graphviz
digraph MaskShifting {
    rankdir=LR;
    node [shape=box];

    X [label="x (32-bit value)"];
    
    Mask0 [label="Mask: 0 (0xFFFF >> 0)\n0b1111111111111111"];
    Mask1 [label="Mask: 8 (0xFFFF >> 8)\n0b0000000011111111"];
    Mask2 [label="Mask: 12 (0xFFFF >> 12)\n0b0000000000001111"];
    Mask3 [label="Mask: 14 (0xFFFF >> 14)\n0b0000000000000011"];

    Lower0 [label="lower = x & 0b1111111111111111"];
    Lower1 [label="lower = x & 0b0000000011111111"];
    Lower2 [label="lower = x & 0b0000000000001111"];
    Lower3 [label="lower = x & 0b0000000000000011"];

    X -> Mask0 -> Lower0;
    X -> Mask1 -> Lower1;
    X -> Mask2 -> Lower2;
    X -> Mask3 -> Lower3;
}
```
接下來利用 `clz32` 得到最高位元的索引即可開始利用 [Digit-by-digit Method](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method) 計算逼近平方根

```
/* 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;
```
為了確保 `m` 是 **power of 4** 代表 `shift` 必須是**偶數**：



| shift | m |
| -------- | -------- |
| 0     | 1     |
| **1**     | **2 不是 power of 4**    |
| 2     | 4     |
| 3     | 8     |

這不是個很難的操作以下兩種都可以得到一樣的效果，難的是要用**最精簡的方式**寫

```diff
- int shift = (total_bits - 1 - clz64(x)) & (0x1f<<1);
+ int shift = (total_bits - 1 - clz64(x)) & ~1;
```
關於 `~` 根據 [C99](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)，6.5.3.3 Unary arithmetic operators：

> The result of the ~ operator is the bitwise complement of its (promoted) operand.
> If the promoted type of the operand is unsigned, the result is computed by subtracting the value from the largest value representable in the type plus 1.

```graphviz
digraph BitwiseOperation {
    rankdir=LR;
    node [shape=record];

    MSB [label="MSB Index | 010101"];
    Mask [label="Bitmask ~1 | 1111110"];
    Result [label="Result (Even) | 010100"];

    MSB -> Result [label="& ~1"];
    Mask -> Result;
}

```

意思是：

`~x` 會對 `x` 的每一位元執行 1 → 0 和 0 → 1 的翻轉（補數運算）。
如果 `x` 是無符號型別 (unsigned)，結果等同於 `UINT_MAX - x`。
如果 `x` 是有符號型別 (signed)，則是二補數的位元反轉。

```c
while (m) {
    uint64_t b = y + m;
    y >>= 1;
    if (x >= b) {
        x -= b;
        y += m;
    }
    m >>= 2;
}
```
> 總結迭代關係為
$$
c_{m-1} =
\begin{cases}
    c_m/2 +d_m, &\text{ if } a_m\neq 0, \\
    c_m/2,      &\text{ if } a_m = 0.
\end{cases}
$$
與
$$
    d_{m-1} = d_m/4
$$
帶入 $m=0$ 和 $c_m=2a_m
 P_{m+1}$ 則可以藉由 $c_{-1}$ 得知平方根為
$$
    c_{-1} = P_02^0 = P_0 = N.
$$

這迴圈就是利用了以上的迭代關係：
我們已知 $c_m =a_{m+1}P_{m+1}= P_{m+1}2^{m+1}$ 與 $d_m =(2^{m})^2$。
$$
\begin{align}
Y_m &= 2 ^{m+1}P_{m+1}+(2^m)^2 \\
    &= c_m+d_m
\end{align}
$$

`x` 代表當前的剩餘數值 $N−Y_m$ 又 $Y_m=(P_m)^2-(P_{m+1})^2$，所以所求的
$$\begin{align}
N^2 &=(P_0)^2 \\
    &=(P_1)^2 + Y_0 \\
    &=(P_2)^2 + Y_1 + Y_0 \\
    &=(P_m)^2 + Y_{m-1} + ... +  Y_0
\end{align}$$

$Y_m$ 則是 `y + b` 
- `y` = $c_m$
- `m` = $d_m$
 
```
if (x >= b) {
    x -= b;
    y += m;
}
```
`if (x >= b)` 代表目前剩餘的值還大於該回合的 $Y$，並且可以藉由這個條件得知該位元為一。
$$
Y_m = 
\begin{cases}
    c_m+d_m, &\text{ if }a_m =2^m, \\
    0, &\text{ if } a_m = 0.
\end{cases}
$$
$(P_{m})^2$ 的值則可以用以下公式得知：
$$
P_m=
\begin{cases}
    P_{m+1}+2^{m}, &\text{if }P_m^2 \leq N^2,\\
    P_{m+1}, &\text{otherwise.}
\end{cases}
$$
最後每個迴圈用位元運算完成遞迴的迭代：
```c
y >>= 1;
m >>= 2;
```

## 延伸問題
### 擴充為 $\lceil \sqrt{x}) \rceil$ (向上取整數) 實作
- 我的想法是單純的用得出的答案 `ｙ＾２`，和 `x` 比較即可。
- 因此需要實作只使用 bitwise 乘法，這需要用到 bitwise 加法和 bitwise 絕對值

```diff
+   if(multiply(y,y) < x) return y + 1;
```

#### bitwise 加法


| op1 | op2 | carry |
| -------- | -------- | -------- |
| 0     | 0     | 0     |
| 0     | 1     | 0     |
| 1     | 0     | 0     |
| 1     | 1     | 1     |

前三種情況可以透過 `XOR` 得到一樣的結果，而有 `carry` 產生則必須使用到 `&` 判斷及 `<<` 作位移。

```c
int add(int op1, int op2){
    int sum = op1;
    int carry = op2;

    while(carry){
        int temp = op1;
        sum = temp ^ carry;
        carry = (sum & op2) << 1;
    }
    return sum;
}
```
這段程式碼就是用 `XOR` 進行每個位元的加法後，並且用 `&` `判斷每個位元是否有`carry` 還有則要進一步做加法直到所有位元都沒有進位了。

```graphviz
digraph bitwise_addition {
    rankdir=TB;
    node [shape=plaintext fontname="Courier" fontsize=14];

    // Input values
    a [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD>0</TD><TD>1</TD><TD>0</TD><TD>1</TD><TD> (5) </TD></TR>
        </TABLE>
    >];

    b [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD>0</TD><TD>0</TD><TD>1</TD><TD>1</TD><TD> (3) </TD></TR>
        </TABLE>
    >];

    // XOR step
    xor_result [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD>0</TD><TD>1</TD><TD>1</TD><TD>0</TD><TD> (6) </TD></TR>
        </TABLE>
    >, color=blue];

    // AND then shift step
    and_result [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD>0</TD><TD>0</TD><TD>0</TD><TD>1</TD><TD> (1) </TD></TR>
        </TABLE>
    >, color=red];

    shift_result [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD>0</TD><TD>0</TD><TD>1</TD><TD>0</TD><TD> (2) </TD></TR>
        </TABLE>
    >, color=red];

    // Connections
    a -> xor_result [label=" XOR 運算", color=blue];
    b -> xor_result [color=blue];

    a -> and_result [label=" AND 運算", color=red];
    b -> and_result [color=red];

    and_result -> shift_result [label=" 左移 1 位", color=red];
}
```

#### bitwise 絕對值
如果是負數，將二補數負數轉為正數（取補數+1）

```c
int abs(int num)
{
  return num < 0 ? add(~num, 1) : num;
}
```
    
#### bitwise 乘法
參考 [位運算筆記(bitwise operation)](https://hackmd.io/@Ic7U7EO-QHquDHAz9KUksQ/S1Xpqqx9v) 
```c
int multiply(int a, int b)
{
  int multiplicand = abs(a), multiplier = abs(b);

  int product = 0;
  while (multiplier)
  {
    product = add(product, multiplicand);
    multiplier = sub(multiplier , 1);
  }

  if ((a ^ b) < 0)
  {
    product = add(~product, 1);
  }

  return product;
}
```

- 乘法就是多次的加法，先統一把 `multiplicand` 和 `multiplier` 都取絕對值然後就是不斷重複加法。
- `(a ^ b) < 0` 代表兩者的sign bit(Most Significant bit) 不同則將 Product 取負數。

**符號位 (MSB) 代表正負號**
在 **二補數 (Two's Complement)** 表示法中：
- **最高位 (MSB) = 0** → 正數
- **最高位 (MSB) = 1** → 負數

| 位元 A | 位元 B | A ^ B (XOR) |
|--------|--------|-------------|
|   0    |   0    |      0      |
|   0    |   1    |      1      |
|   1    |   0    |      1      |
|   1    |   1    |      0      |

此外乘法還有另一種使用左移右移實作：

$$
\begin{align}
乘數\times  被乘數 &= 積\\
(乘數\times\frac{1}{2}) \times (被乘數\times 2) &= 積
\end{align}
$$

```c
while(multiplier)
{
    if(multiplier & 1)
        add(product, multiplicand);
    multiplicand <<= 1;
    multiplier >>= 1;
}
```

### 撰寫不依賴除法指令的 `sqrtf`

**待補**

### 比較不同手法的整數開平方根效能
**待補**

## [Quiz 2-3](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-3)

`AAAA` = map->bits
 
`BBBB` = map->bits
 
`CCCC` = first->pprev

`DDDD` = n->pprev
 
`EEEE` = n->pprev
## 延伸題目
### 程式運作
```graphviz
digraph hlist {
    node [shape=record];
    hlist_head [label="map_t | { <b0> [0] | <b1> [1] | <b2> [2] | <b3> [3] | <b4> [4] | <b5> [5] | <b6> [6] | <b7> [7] }"];
    rankdir=LR;
    



    obj [label="{ hlist_head |<n> next}", shape=record];
    obj9 [label="{ key_t | { hlist_t | {<p> pprev|<n> next  } } }", shape=record];
    obj1 [label="{ key_t | { hlist_t | {<p> pprev|<n> next  } } }", shape=record];

    

    hlist_head:b2 -> obj;
    obj:n->obj9;
    obj9:p->obj:n;
    obj9:n -> obj1;
    obj1:n->NULL[ shape=plaintext];
    obj1:p->obj9:n;
}
```
分為幾個主要物件：
- `map_t` 管理雜湊表的 bucket，`bit` 用來決定雜湊表範圍
- 每個 bucket 的 `first` 指向 `hlist_head` hlist_head沒有 `pprev` 可以幫助在 bucket 時很多減輕記憶體負擔
- `key_t` 管理雜湊表中的值，具有 `next` 指向下一個 `key_t`， `pprev` 是指標的指標指向上一個 `key_t` 的 `next`。
