---
# System prepended metadata

title: 2025q1 Homework2 (quiz1+2)
tags: [Linux2025q1]

---

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

## [第一週](https://hackmd.io/@sysprog/linux2025-quiz1)

### 測驗 1

#### Solution

- `AAAA` : `&l->head`
- `BBBB` : `before`
- `CCCC` : `&(*p)->next`
- `DDDD` : `item->next`

#### Description

本題中使用++單向鏈結串列++。

先從 `list_insert_before` 的解釋著手:

```bash
/**
 * Inserts a new item into the list before a specified item.
 *
 * This function traverses the list to locate the position immediately before
 * the item pointed to by @before and inserts @item in that position.
 * The time complexity is O(n), where n is the number of steps needed to
 * reach @before from the head of the list.
 *
 * Parameters:
 * @l      : Pointer to the list.
 * @before : Pointer to the item before which the new item should be inserted.
 *           - If @before is the head of the list, the new item is inserted
 *             at the front.
 *           - If @before is NULL, the new item is appended to the end of
 *             the list.
 *           - In all other cases, behavior is undefined if @before does not
 *             belong to @l.
 * @item   : The new list item to be inserted.
 */
static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item);
```

得知 `before` 指向的，是++當插入新節點 `item` 後， `item` 的下一個元素++。

當 `before` 是頭部節點，`item` 將被插入在最前方，如果是 `NULL` 則被插入在最尾端。

```c=
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
    ;
*p = item;
DDDD = before;
```

`list_insert_before` 做的事情是:

1. 找到 `before` 目前所在的位置 (第 2 - 3 行)
2. 將 `before` 用 `item` 替換 (第 4 行)
3. 將 `item` 的下個元素指向 `before` (第 5 行)

因此，`AAAA` - `DDDD` 的內容推論如下:

- 尋找 `before` 應當從頭部節點開始，`struct list_t` 中僅有成員 `head`，故 `AAAA` 為 `&l->head`。
- 停止尋找條件為 `*p` 指向的節點與 `before` 相同時，故 `BBBB` 為 `before`。應注意，`list_insert_before` 的註釋提到當 `before` 不存在於 `l` 中時，可能產生未定義行為，推測將因為對尾部節點的下一個，即 `NULL` 解引用導致 core dump。
- 對於每次循環，`p` 應該往下移動，故 `CCCC` 為 `&(*p)->next`。應注意運算子的優先級別，在此為 `->` > `*` > `&`，詳見 [C Operator Precedence](https://en.cppreference.com/w/c/language/operator_precedence)，故括弧應僅包含 `*p`。
- 將 `item` 的下一個節點換作 `before`，故 `DDDD` 為 `item->next`。

以 Graphviz 呈現:

- 當循環開始時，`*p` 指向 `head`

    ```graphviz
    digraph g {
        rankdir=LR;
        node [shape=record];
        
        head [label = "<name>head | {<data> 4 | <ref>}"];
        node1 [label = "<name>node1 | {<data> 7 | <ref>}"];
        node2 [label = "node2 | {<data> 10 | <ref>}"];
        target [label = "TARGET | {<data> 3 | <ref>}"];
        node3 [label = "node3 | {<data> 1 | <ref>}"];
        
        null [label = "NULL", shape = none];
        before [label = "before", shape = none];
        dref_p [label = "*p", shape = none];
        
        edge[weight=2];
        head:ref:c -> node1:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node1:ref:c -> node2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node2:ref:c -> target:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        target:ref:c -> node3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node3:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        edge[weight=1];
        before -> target:name:n
        dref_p -> head:name:n
    }
    ```
- 當 `*p` 指向的節點為 `before` 時，插入 `item`
    ```graphviz
    digraph g {
        rankdir=LR;
        node [shape=record];
        
        head [label = "<name>head | {<data> 4 | <ref>}"];
        node1 [label = "<name>node1 | {<data> 7 | <ref>}"];
        node2 [label = "node2 | {<data> 10 | <ref>}"];
        target [label = "TARGET | {<data> 3 | <ref>}"];
        node3 [label = "node3 | {<data> 1 | <ref>}"];
        item [label = "item | {<data> 5 | <ref>}"];
        
        null [label = "NULL", shape = none];
        before [label = "before", shape = none];
        p [label = "p", shape = none];
        
        edge[weight=3];
        head:ref:c -> node1:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node1:ref:c -> node2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node2:ref:c -> target:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        target:ref:c -> node3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node3:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        edge[weight=1];
        before:se -> target:name
        p -> node2:ref;
    }
    ```
    ```graphviz
    digraph g {
        rankdir=LR;
        node [shape=record];
        
        head [label = "<name>head | {<data> 4 | <ref>}"];
        node1 [label = "<name>node1 | {<data> 7 | <ref>}"];
        node2 [label = "node2 | {<data> 10 | <ref>}"];
        target [label = "TARGET | {<data> 3 | <ref>}"];
        node3 [label = "node3 | {<data> 1 | <ref>}"];
        item [label = "item | {<data> 5 | <ref>}"];
        
        null [label = "NULL", shape = none];
        before [label = "before", shape = none];
        p [label = "p", shape = none];
        
        edge[weight=3];
        head:ref:c -> node1:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node1:ref:c -> node2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node2:ref:c -> item:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        target:ref:c -> node3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node3:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        edge[weight=1];
        before:n -> target:name
        p -> node2:ref;
    }
    ```
- 將 `item->next` 指向 `before`
    ```graphviz
    digraph g {
        rankdir=LR;
        node [shape=record];
        
        head [label = "<name>head | {<data> 4 | <ref>}"];
        node1 [label = "<name>node1 | {<data> 7 | <ref>}"];
        node2 [label = "node2 | {<data> 10 | <ref>}"];
        target [label = "TARGET | {<data> 3 | <ref>}"];
        node3 [label = "node3 | {<data> 1 | <ref>}"];
        item [label = "item | {<data> 5 | <ref>}"];
        
        null [label = "NULL", shape = none];
        before [label = "before", shape = none];
        p [label = "p", shape = none];
        
        edge[weight=3];
        head:ref:c -> node1:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node1:ref:c -> node2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node2:ref:c -> item:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        item:ref:c -> target:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        target:ref:c -> node3:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node3:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        edge[weight=1];
        before -> target:name
        p -> node2:ref;
    }
    ```

注意 p 指向的是節點 `next` 的地址，從圖中看便是指向 `next`，而 `next` 再指向下一個節點，可以描述出 `p` 是 indirect pointer。之所以說優雅是因為頭部節點的地址實際存儲在 `&head` 記憶體中，「像是」一個 `next` 的存在，這使的操作得以一致化。

#### 延伸 : 運作原理
測試程式 `test_list` 的流程如下:

- 透過函式 `list_reset` 初始化全域串列與節點陣列，將每個節點的值設定為索引值並清除所有鏈結，對於所有測試前都會先執行。
- 測試第一種情況，傳入 `before` 為 `l.head` 以++逆序++方式將陣列中的內容插入到鏈結串列中，並確保測試後的鏈結串列數值是反向排列的。
- 測試第二種情況，傳入 `before` 為 `NULL`，以++順序++方式將陣列中的內容插入到鏈結串列中，並確保數值是順序的。
- 測試第三種情況，同上一條。

#### 延伸 : 合併排序

可以透過以下方式進行遞迴式單向鏈結串列排序:

- 透過快慢指標將鏈結串列分成兩段，第一段的頭部由 `head` 指標指向，第二段頭部則是 `slow->next` 指向的節點，注意要透過另一個指標(e.g., `mid` 儲存)。
- 切斷第一部分和第二部分的鏈結( `slow->next == NULL` )
- 將 `head` 和 `mid` 傳入 `merge_sort_list` (遞迴呼叫)
- 當 `head` 和 `mid` 已經排序完並返回後，呼叫 `merge_lists` 合併兩者為單個鏈結串列。

合併中，當兩個鏈結串列非空時，取出值較小者，放入要返回的鏈結串列尾部，並將被取出值的鏈結串列往下一個移動

實作如下:

```c
/**
 * @brief Merges two sorted linked lists into one sorted list.
 * @param a pointer to the first sorted list.
 * @param b pointer to the second sorted list.
 * @return pointer to the head of the merged sorted list.
 */
static list_item_t *merge_lists(list_item_t *a, list_item_t *b)
{
    list_item_t dummy;             // dummy node to simplify merge operation
    list_item_t *tail = &dummy;     // tail pointer for the merged list
    dummy.next = NULL;
    
    while (a && b) {
        if (a->value <= b->value) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a) ? a : b;
    return dummy.next;
}

/**
 * @brief Recursively sorts the linked list using merge sort.
 * @param head pointer to the head of the list.
 * @return pointer to the head of the sorted list.
 */
static list_item_t *merge_sort_list(list_item_t *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    
    // Find the middle of the list using slow and fast pointers
    list_item_t *slow = head;
    list_item_t *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Split the list into two halves
    list_item_t *mid = slow->next;
    slow->next = NULL;
    
    // Recursively sort each half
    list_item_t *left = merge_sort_list(head);
    list_item_t *right = merge_sort_list(mid);
    
    // Merge the two sorted halves
    return merge_lists(left, right);
}

/**
 * @brief Sorts the entire linked list in ascending order.
 * @param l pointer to the list structure.
 */
void list_sort(list_t *l)
{
    if (l == NULL)
        return;
    l->head = merge_sort_list(l->head);
}
```

藉由以下修改使 `merge_lists` 消除 if - else:

```c
static list_item_t *merge_lists(list_item_t *a, list_item_t *b)
{
    list_item_t dummy;
    list_item_t **last = &dummy.next;
    dummy.next = NULL;
    
    while (a && b) {
        list_item_t **min = (a->value <= b->value) ? &a : &b;
        *last = *min;
        last = &(*last)->next;
        *min = (*min)->next;
    }
    *last = a ? a : b;
    return dummy.next;
}
```

### 測驗 2

#### Solution

- `EEEE` : `(*pred_ptr)->r`
- `FFFF` : `&(*pred_ptr)->r`

#### Description

當要快速解題時，著重在以下內容:

```c
/* 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;
```

註釋提到要找左子樹中最右下角的節點，起始位置已經設定成左子樹，因此我們只需要確認每個節點是否具有右子節點。如果有則更新成該節點並繼續，反之結束。

- `EEEE` 要確認是否具有右子節點(非 `NULL` )，故用 `(*pred_ptr)->r`
- `FFFF` 是更新節點，`pred_ptr` 是 indirect pointer 故為 `&(*pred_ptr)->r`。
- ++注意 `*` 和 `->` 的優先級++。

#### 延伸 : 分析 & 解讀

先探討試題中的內容。

首先看到 `block_t` 定義:

```c
typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;
```

其中 `size` 用於紀錄該 block 的大小 (bytes)。

接著有兩個未提供的實作的函式，我們稍後探討這部分的實作:

```c
block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
```

關鍵函式 `remove_free_tree`:

```c
void remove_free_tree(block_t **root, block_t *target)
```

裡面用到幾個關鍵變數，如下表:



|  Variable  |    Type     | Description                                                                                                                                                                |
|:----------:|:-----------:| -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
|     `target`       |    `block_t*`         |   A pointer to the target node, i.e., the node that is intended to be removed from the tree.                                                                                                                                                                         |
| `pred_ptr` | `block_t**` | An indirect pointer to the field in the left subtree of the target node, used to locate its in-order predecessor (i.e. the rightmost node in the left subtree).            |
| `node_ptr` | `block_t**` | An indirect pointer pointing to the field (in the parent or root) that holds the target node's address, enabling direct modification of the tree structure during removal. |



`remove_free_tree` 可以分成三個階段:

- 在樹中找到 `target` ，並用其親代的左或右成員地址表達，並紀錄在 `node_ptr` 中。
- 根據 `target` 的左節點和右節點，在移除前更新親代的子節點，避免直接移除破壞樹結構。
- 移除 `target` 的子節點，避免被刪除的節點還能存取樹中的其他節點。

針對第二點，可以分為三種情況:

1. `target` 同時有左和右子節點。
2. `target` 僅具有單邊節點。
3. `target` 不具有任何子節點。

第二種情況只要將 `node_ptr` 指向唯一的子節點即可:

```c
*node_ptr = child;
```

第三種情況則更新成 `NULL` :

```c
*node_ptr = NULL;
```

> [!Note]
> 我認為第二種情況可以和第三種合併，因為第三種情況不論取左右子節點，都是 `NULL`。

針對第一種情況，要先尋找到++目標節點的中序前驅節點++。中序前驅中，中序是走訪方式(左 ➞ 中 ➞ 右)；前驅則指最靠近目標節點，但比目標節點小的節點。因此中序前驅可以理解為++前一個++。注意靠近並非路徑靠近，而是++值++靠近，例如此處應為 `size` 接近。

對於二元搜尋樹 (Binary Search Tree, BST) 而言，中序前驅節點位於左子樹最右下角的節點，反之中序後繼則在右子樹最左下角。

當找到中序前驅節點後，分兩種情況:

- 左子樹中沒有任何右節點 ( `*pred_ptr == (*node_ptr)->l` )
- 其他

對於++前者++:

1. 紀錄 `target` 右節點 ( `(*node_ptr)->r` )。
    - 不用紀錄 `target` 左節點的左子樹原因是，即將用 `target` 左節點替換掉 `target`，其本身的 `l` 成員已有該資訊，缺乏的僅是右側節點的資訊。
1. 將原本指向 `target` 的 `*node_ptr` 改指向中序前驅節點 `*pred_ptr`，注意不是 `node_ptr = pred_ptr` 而是 `*node_ptr = *pred_ptr`，後者才會改變樹結構。
1. 確保沒有顯而易見的環 (指向自身)。

對於++後者++:

1. 紀錄 `target` 左右節點資訊。
1. **用另一個指標保存中繼前驅節點**，用於解決下一步從樹中移除中繼前驅後，其 `l` 成員會被置 `NULL` 導致遺失左節點的問題，用 `pred_node` 紀錄。
1. 將中繼前驅從原位置移除(再次呼叫 `remove_free_tree` )
1. 變更 `*node_ptr` 指向 `pred_node` ++指向的節點++。注意不可用 `node_ptr = &pred_node` 因為 `pred_node` 是區域變數。
1. 檢查是否有顯而易見的環。


#### 延伸 : 實作 free tree

實作前可以思考以下問題:

> 為什麼 `find_free_tree` 需要返回 `block_t**` ?

如果只是要修改 `block_t` 內容，`block_t*` 就足夠了。但若要++更新其親代節點的子節點++，則應返回 `block_t**`，並透過以下方式進行更新:

```c
block_t **ptr = find_free_tree(root, target);
if (ptr) {
    // With an indirect pointer, we can directly modify the parent's pointer.
    
    // Get size
    size_t size = (*ptr)->size;
    
    // For example, remove target by updating the parent's pointer to point to target->l.
    *ptr = target->r; 
}
```

我們不用再特別尋找親代節點的指標再透過該指標去修改，而是直接返回親代的左子樹或右子樹 field 的地址 ( `&parent->l` or `&parent->r` )，如此便能直接藉由一次解引用更新裡面指向的節點。 `remove_free_tree` 中的使用方法便是如此 ( `*node_ptr = *pred_ptr` ) 。

下圖描述返回值 `block_t**` ( `ptr` ) 所指向的位置。

```graphviz
digraph g {
    rankdir=TD;
    node [shape=record];
    ranksep=0.3; 
    nodesep=0.4;

    parent [label="{Parent | Size: 2 | {<l_ref>| <r_ref>}}"];
    l_node [label="{LeftChild | Size: 1| {<l_ref> | <r_ref>}}"];
    target [label="{Target | Size: 3 | {<l_ref>| <r_ref>}}"];
    ptr [label="ptr", shape=none];

    // not show
    node [shape=none];
    none1 [label="", width=0.5, height=0, fixedsize=true, margin=0];
    none2 [label="", width=0.5, height=0, fixedsize=true, margin=0];
    none3 [label="", width=0.5, height=0, fixedsize=true, margin=0];
    none4 [label="", width=0.5, height=0, fixedsize=true, margin=0];
    
    edge[weight=2]

    // Parent's right field points to target.
    parent:r_ref:c -> target [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    parent:l_ref:c -> l_node [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    l_node:r_ref:c -> none1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    l_node:l_ref:c -> none2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    target:r_ref:c -> none3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    target:l_ref:c -> none4 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    
    edge[weight=1]
    ptr -> parent:r_ref [style=solid, headclip=false, arrowhead=vee];
     parent -> ptr [style=invis];
}
```

我們需要實作以下的函式:

- `create_block`
- `insert_free_tree`
- `remove_free_tree` (同上方實作，移除檢查部分)
- `find_free_tree`
- `free_free_tree`
- `find_predecessor_free_tree` (optional)
- `print_free_tree` (optional)

以下是實現方法，運行範例請見 [Compiler Explorer](https://godbolt.org/z/TfsEYrWrE):
- `create_block`
    
    ```c
    block_t *create_block(size_t size) {
        block_t *node = malloc(sizeof(block_t));
        if (!node) {
            perror("malloc");
            exit(EXIT_FAILURE);
        }
        node->size = size;
        node->l = node->r = NULL;
        return node;
    }
    ```
- `insert_free_tree`
    
    當找到 `NULL` 處即可插入，以下是迭代寫法:

    ```c
    void insert_free_tree(block_t **root, block_t *node) {
        if (root == NULL || node == NULL) return;

        while (*root != NULL) {
            if (node->size < (*root)->size)
                root = &(*root)->l;
            else
                root = &(*root)->r;
        }
        *root = node;
    }    
    ```
    遞迴寫法:
    ```c
    void insert_free_tree(block_t **root, block_t *node) {
        if (root == NULL) return;
        if (*root == NULL) {
            *root = node;
            return;
        }
        if (node->size < (*root)->size) {
            insert_free_tree(&((*root)->l), node);
        } else {
            insert_free_tree(&((*root)->r), node);
        }
    }
    ```

- `find_free_tree`

    採用迭代走訪子樹，可以善用 BST 的特性，以 size 為判斷條件決定繼續走訪左子節點(小於)還是右子節點(大等於)。當 `*root` 為 `target` 時就返回。

    ```c
    block_t **find_free_tree(block_t **root, block_t *target) {
        while (root && *root) {
            if (*root == target) {
                return root;
            }
            if (target->size < (*root)->size) {
                root = &(*root)->l;
            } else {
                root = &(*root)->r;
            }
        }
        return NULL;
    }
    ```
    
    當然也能透過遞迴作法實現:
    
    ```c
    block_t **find_free_tree(block_t **root, block_t *target) {
        if (root == NULL || *root == NULL)
            return NULL;
        if (*root == target)
            return root;
        block_t **found = find_free_tree(&(*root)->l, target);
        if (found != NULL)
            return found;
        return find_free_tree(&(*root)->r, target);
    }
    ```
- `free_free_tree`

    ```c
    void free_free_tree(block_t *root) {
        if (root == NULL)
            return;
        free_free_tree(root->l);
        free_free_tree(root->r);
        free(root);
    }
    ```

#### 延伸 : 參考 [memory-allocators](https://github.com/mtrebi/memory-allocators) 的效能比較與討論

要使當前程式為真正的記憶體配置器，要針對 `block_t` 結構體進行修改，例如需要紀錄真正可以讀寫的 buffer 地址。

##### 可改進

- BST 非常依賴 `root`，其決定該樹的平衡狀況，如果 `root` 為極端值，則操作速度會退化，是否能使用其他平衡樹?

#### Reference

- [charliechiu : linux2025-homework2](https://hackmd.io/@charliechiu/linux2025-homework2)

### 測驗 3

#### Solution

- `GGGG` : `head->prev=prev`
- `HHHH` : `list_entry(pivot,node_t,list)->value`
- `IIII` : `list_entry(n,node_t,list)->value`
- `JJJJ` : `pivot`
- `KKKK` : `right`

#### Description

先看到 `GGGG` 所在的輔助函式:

```c
static void rebuild_list_link(struct list_head *head)
```

只做以下流程:
1. 用 `prev` 紀錄目前 `head`。
2. 找到 `head->next` 用 `node` 紀錄。
3. 進入循環，由於目前是單向鏈結串列，故停止條件為 `node` 不是 `NULL` (走訪到尾)。
4. 循環內透過 `prev`, `node` 等操作，建立沿途每個元素的 `prev` 關係 ( `next`  已經被建立)。
5. 離開循環後，使鏈結串列構成環，即將最後一個元素 `prev` 的 `next` 指向 `head` ，而 `head->prev` 則指向最後一個元素 `prev`。故得 `GGGG` 為 `head->prev=prev`。

接著看到 `HHHH` 的關鍵程式:

```c
if (L != R) {
    struct list_head *pivot = L;
    value = /* HHHH */
    // ...
    if (n_value > value) {
        n->next = right;
```

可知 `value` 是比較的基準值，在快速排序中，我們以 `pivot` 的值作為基準，因此 `value` 是類似 `to_node_t_func(pivot)->value`，這可以透過 `list_entry` 巨集達成。由於 `list_head` 儲存在成員 `list` 中。故 `HHHH` 為 `list_entry(pivot,node_t,list)->value`。

接著移動到 `IIII` :
 
```c
struct list_head *n = p;
p = p->next;
int n_value = /* IIII */;
```

我們能夠推斷 `n_value` 實際上就是 `to_node_t(n)->value`，也就是 `list_entry(n,node_t,list)->value` 即 `IIII`。

最後的 `JJJJ` 和 `KKKK` 可以放在一起看。快速排序中，合併後的順序是 `left` ➜ `pivot` ➜ `right`。題目中的作法是從取出第 `begin[i]`，而 `i` 是遞減的 ( `i--` )，也就是實際合併時，會先將 `begin[i+2]` 處理後的放到 `result` 前面，之後是 `begin[i+1]` 處理後的，...。所以 `right` 應該要放置在第一個被拿取的地方，即:

```c
begin[i] = left;
begin[i + 1] = pivot; /* JJJJ */
begin[i + 2] = right; /* KKKK */
```

#### 延伸 : 解讀程式

在[〈Optimized QuickSort — C Implementation (Non-Recursive)〉](https://alienryderflex.com/quicksort/)提到的陣列快速排序流程分成作者自己提出的和本來就存在於 Wiki 百科上的，可以用以下文字解釋:

**Darel Rex Finley's Quick Sort**

- 將 `head` 指向的元素複製到 `pivot` 中，`L` 從++最左側++開始，`R` 從最++右側++開始

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">4</TD>
              <TD PORT="f1" WIDTH="25">5</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">6</TD>
              <TD PORT="f4" WIDTH="25">2</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">1</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        head_text [label="head", shape=plaintext];
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f0 -> L_text [style=invis]

            p_text->p;
            head_text->arr:f0

            L_text -> arr:f0
            R_text -> arr:f7
        }
    }
    ```

- `R` 往左側移動直到遇到比 `pivot` 小的值，此處為第七個元素 1，因此將該值++複製到++ `L` 指向的空間

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">5</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">6</TD>
              <TD PORT="f4" WIDTH="25">2</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">1</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        head_text [label="head", shape=plaintext];
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];
        four_text [label="4", shape=plaintext]
        
        arr:f0:w -> four_text [headlabel="remove  "]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f0 -> L_text [style=invis]

            p_text->p;
            head_text->arr:f0

            L_text -> arr:f0
            R_text -> arr:f6
        }
    }
    ```
- `R` 已經置換過，換成 `L` 往右邊移動直到遇到比 `pivot` 大的值，此處為第二個元素 `5`，將該值複製到 `R` 指向的地方

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">5</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">6</TD>
              <TD PORT="f4" WIDTH="25">2</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">5</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        head_text [label="head", shape=plaintext];
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        one_text [label="1", shape=plaintext]
        
        one_text -> arr:f6[dir=back taillabel="remove  "]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f1 -> L_text [style=invis]

            p_text->p;
            head_text->arr:f0

            L_text -> arr:f1
            R_text -> arr:f6
        }
    }
    ```

- 繼續往左移動 `R`，最終指到第五個元素 `2`

    ```graphviz
    digraph G {
        node [shape=none];
        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">6</TD>
              <TD PORT="f4" WIDTH="25">2</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">5</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        head_text [label="head", shape=plaintext];
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        five_text [label="5", shape=plaintext]
        
        five_text -> arr:f1[dir=back label="remove"]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f3 -> L_text [style=invis]
            arr:f4 -> R_text [style=invis]

            p_text->p;
            head_text->arr:f0

            L_text -> arr:f1
            R_text -> arr:f4
        }
    }
    ```    

- 接下來又換到 `L`，停在第四個元素 `6`

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">6</TD>
              <TD PORT="f4" WIDTH="25">6</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">5</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        head_text [label="head", shape=plaintext];
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        two_text [label="2", shape=plaintext]
        two_text -> arr:f4 [dir=back label="  remove"]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f3 -> L_text [style=invis]
            arr:f4 -> R_text[style=invis]

            p_text->p;
            head_text->arr:f0

            L_text -> arr:f3
            R_text -> arr:f4
        }
    }
    ```    

- 此時，換 `R`，但此時 `R` 碰到 `L` 故結束，將 `pivot` 的值複製進 `L` 指向的地方，並更新 `begin` 和 `end`

    - 第一輪開始前，`begin[i]` 是 `0`、`end[i]` 是 `8`
    - 第一輪結束後，`begin[i+1]` 是 `L+1 (4)`、`end[i+1]` 是 `end[i] (8)`、`end[i]` 被更新為 `L (3)`，且 `i` 往上遞增 1 為 `1`

     ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">6</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">5</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        head_text [label="head", shape=plaintext];
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        // begin
        beg [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">0</TD>
              <TD PORT="f1" WIDTH="25">4</TD>
            </TR>
          </TABLE>
        >];
        beg_text [label="begin", shape=plaintext];

        // end
        end [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">3</TD>
              <TD PORT="f1" WIDTH="25">8</TD>
            </TR>
          </TABLE>
        >];
        end_text [label="end", shape=plaintext];

        beg_text -> beg [style=invis]
        beg -> end_text [style=invis]
        end_text -> end [style=invis]

        // 為了對齊，讓 beg_text 在左邊與 arr 同一行
        { rank=same; beg_text; arr }

        // L、R 排在 arr 下方
        { rank=same; L_text; R_text }

        // connections
        {
            arr:f3 -> L_text [style=invis]
            arr:f3 -> R_text [style=invis]

            p_text -> p;
            head_text -> arr:f0

            L_text -> arr:f3
            R_text -> arr:f3
        }
    }
    ```     

- 繼續從 `i = 1` 開始，L 的新值為指向 index 為 4 的 `6`，`R` 指向 index 為 7 的 `7`，pivot 值改為 `6`

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">6</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">5</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="6", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f4 -> L_text [style=invis]
            arr:f7 -> R_text[style=invis]

            p_text->p;

            L_text -> arr:f4
            R_text -> arr:f7
        }
    }
    ```  

- 接著 `R` 往左移動到第七個元素 `5`，並將該值複製到 `L` 處

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">5</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">5</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="6", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        six_text [label="6", shape=plaintext]
        six_text -> arr:f4[dir=back label="  remove"]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f4 -> L_text [style=invis]
            arr:f6 -> R_text[style=invis]

            p_text->p;

            L_text -> arr:f4
            R_text -> arr:f6
        }
    }
    ```    

- `L` 往右移動到第六個元素 `8` 時，複製到 `R`

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">5</TD>
              <TD PORT="f5" WIDTH="25">8</TD>
              <TD PORT="f6" WIDTH="25">8</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="6", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        five_text [label="5", shape=plaintext]
        five_text -> arr:f5[dir=back label="  remove"]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f5 -> L_text [style=invis]
            arr:f7 -> R_text[style=invis]

            p_text->p;

            L_text -> arr:f5
            R_text -> arr:f6
        }
    }
    ```    

- 換 `R` 但碰到 `L`，將 `pivot` 複製到 `L` 後結束第二輪

    - 第二輪開始前，`begin[i]` 是 `4`、`end[i]` 是 `8`
    - 第二輪結束後，`begin[i+1]` 是 `L+1 (6)`、`end[i+1]` 是 `end[i] (8)`、`end[i]` 被更新為 `L (5)`，且 `i` 往上遞增 1 為 `2`

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">5</TD>
              <TD PORT="f5" WIDTH="25">6</TD>
              <TD PORT="f6" WIDTH="25">8</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="4", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        // begin
        beg [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">0</TD>
              <TD PORT="f1" WIDTH="25">4</TD>
              <TD PORT="f2" WIDTH="25">6</TD>
            </TR>
          </TABLE>
        >];
        beg_text [label="begin", shape=plaintext];

        // end
        end [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">3</TD>
              <TD PORT="f1" WIDTH="25">5</TD>
              <TD PORT="f2" WIDTH="25">8</TD>
            </TR>
          </TABLE>
        >];
        end_text [label="end", shape=plaintext];

        beg_text -> beg [style=invis]
        beg -> end_text [style=invis]
        end_text -> end [style=invis]

        // 為了對齊，讓 beg_text 在左邊與 arr 同一行
        { rank=same; beg_text; arr }

        // L、R 排在 arr 下方
        { rank=same; L_text; R_text }

        // connections
        {
            arr:f5 -> L_text [style=invis]
            arr:f5 -> R_text [style=invis]

            p_text -> p;

            L_text -> arr:f5
            R_text -> arr:f5
        }
    }
    ```  

- 第三輪，`L` 指向第七個元素 `8`，`R` 指向第八個元素 `7`。由於 `R` 當前指向的已經小於新的 `pivot` 值 `8`，因此將該值複製到 `L`。

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">5</TD>
              <TD PORT="f5" WIDTH="25">6</TD>
              <TD PORT="f6" WIDTH="25">7</TD>
              <TD PORT="f7" WIDTH="25">7</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="8", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        eight_text [label="8", shape=plaintext]
        eight_text -> arr:f6[dir=back label="  remove"]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f6 -> L_text [style=invis]
            arr:f7 -> R_text[style=invis]

            p_text->p;

            L_text -> arr:f6
            R_text -> arr:f7
        }
    }
    ``` 

- 而此時顯而易見的是，`L` 將會碰到 `R`，所以 `pivot` 的值將被放入最後一個元素中

    ```graphviz
    digraph G {
        node [shape=none];

        arr [label=<
          <TABLE BORDER="1" CELLBORDER="1" CELLSPACING="0">
            <TR>
              <TD PORT="f0" WIDTH="25">1</TD>
              <TD PORT="f1" WIDTH="25">2</TD>
              <TD PORT="f2" WIDTH="25">3</TD>
              <TD PORT="f3" WIDTH="25">4</TD>
              <TD PORT="f4" WIDTH="25">5</TD>
              <TD PORT="f5" WIDTH="25">6</TD>
              <TD PORT="f6" WIDTH="25">7</TD>
              <TD PORT="f7" WIDTH="25">8</TD>
            </TR>
          </TABLE>
        >];

        // pivot
        p [label="8", shape=box];
        p_text [label="pivot", shape=plaintext];

        // labels
        L_text [label="L", shape=plaintext];
        R_text [label="R", shape=plaintext];

        eight_text [label="7", shape=plaintext]
        eight_text -> arr:f7[dir=back label="  remove"]

        { rank=same; L_text; R_text }

        // connections
        {
            // force L under arr
            arr:f6 -> L_text [style=invis]
            arr:f7 -> R_text[style=invis]

            p_text->p;

            L_text -> arr:f7
            R_text -> arr:f7
        }
    }
    ``` 

- 達到該步驟後，剩下的就是更新 `begin`、`end` 並重走訪先前排序好的子陣列。剩下的過程中不會有任何除了 `L` 的值被替換(被 `pivot` 替換)，直到 `i < 0`

分析完陣列的作法後，結合原本題目的說明來看看鏈結串列的快速排序吧!
題目中一開始舉的例子省略中間步驟，導致有點難快速理解，其流程如下:

- `L` 一開始在 `array[0]`，`R` 在 `array[5]`，當 `R` 往左邊走一格就碰到了小於 `pivot` 的值，因此發生 `array[0] = array[4]`。
- 換 `L` 移動，到 `array[3]` 發現大於 `pivot` 的值，所以 `array[3] = array[4]`
- `L` 和 `R` 碰到，把 `pivot` 值給 `array[3]`

接著看到非 Linux Kernel list 的 `quick_sort` 實現，有幾點可以注意:

- `max_level` 設定成 `2n` 是確保在極端情況下，不發生數組越界。
- 透過 `list_tail` 獲得最後一個元素 (相當於 `R = end[i] - 1` )
- `L` 從 `pivot` 的下一個開始(和陣列不一樣)
- 鏈結串列不使用 `L` 和 `R` 的複製，因為交換成本高，而是拆分成兩個子鏈結串列，小於等於的放 `left`，大於的放 `right`
- 只有 `begin` 沒有 `end`，放置到 `begin` 的順序按照索引順序為 `left`、 `pivot`、`right`

這些部分也會在用 list 實作的 `quick_sort` 中。

實作中有++三處遮罩++:

- `CCCC` : `p->next`
- `DDDD` : `list_tail(&left)` (先放左邊)
- `EEEE` : `list_tail(&right)` (再放右邊)

最後看回使用 list 實作的 `quick_sort`，其測試的流程是透過 `shuffle` 先打亂有 100000 的鏈結串列，之後使用 `quick_sort` 排序並透過 `list_is_ordered` 驗證。

- `shuffle` 使用 `rand` 實作，這能透過先前實作 PRNG 進行改進。
- `list_tail` 在這邊沒有使用 `prev` 的作法是因為 `quick_sort` 過程中，會只維護單邊 ( `netx` 方向) 的鏈結，到最後才從新建立另一邊鏈結。


#### 延伸 : 雙向鏈結的排序演算法考量

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

----------------------------------------------------------

## [第二週](https://hackmd.io/@sysprog/linux2025-quiz2)

### 測驗 1

#### Solution

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

#### Description

該測驗延續上週的快速排序，差別是更改了 API 讓使用者能夠傳入自定義的比較函式指標。

觀察核心程式碼，在開始時檢查邊緣情況確認是否能提早返回。接著進行 `list_head` 的初始化，再往下碰到了 `AAAA`。快速排序通常取頭部節點作為 `pivot`，因此 `AAAA` 對應的操作是取出成員 `list` 為 `ad` 的節點地址操作，如此後續才能執行如 `pivot->list` 等操作。故 `AAAA` 為 `container_of`。而由於 `pivot` 要移出鏈結串列外，因此 `BBBB` 為 `list_del`。

接著來到比較大小的部分，比 `pivot` 小的放到 `list_less` 中，其它放到 `list_greater`，應注意題目要求符合 stable sorting，意謂要符合原鏈結串列順序。因此插入時應插入在++尾端++。故 `CCCC` 和另一分支都使用 `list_move_tail`。

分區完成後，透過遞迴方式呼叫 `list_quicksort`，並於遞迴結束後，按序將 `list_less`、`pivot`、`list_greater`，題目中首先操作的是 `pivot`，因此可以使用 `list_add` 將其先加入 `head` 中，同時也是 `head` 的唯一節點。接著透過 `EEEE` 和 `FFFF` 分別操作 `list_less`、`list_greater`，如前述 `EEEE` 要讓 `list_less` 在 `head` 唯一的節點前，因此是從頭部插入，相反 `FFFF` 則要從尾部插入。故 `EEEE` 為 `list_splice` 而 `FFFF` 為 `list_splice_tail`。

在此，我們記錄 `list_splice` 和 `list_cut_position` 的功能。前者用於拼接鏈結串列，注意拼接後的哨兵節點 (例如 `list_less`) 是++不能直接承接其他節點的++!需要進行初始化後才能繼續使用。或者使用 `list_splice_init` 來簡化該流程。

`list_cut_position` 是輔助使用者從 `head` 的第一個節點到指定節點(含)移動到另一個鏈結串列中，剩下的留在原鏈結串列中。

#### 延伸 : 改進 random_shuffle_array

在 `random_shuffle_array` 註釋提到:

```
/* WARNING biased shuffling */
```

所謂 biased shuffling 是指取樣時，由於使用取餘操作而結果非 0 時，會導致小於取餘結果的值有更高的機會被取樣。儘管機率很小，依然會降低隨機性。

可以藉由移除多出的尾端，使每種取餘結果出現的次數是相同的。

```c
static uint16_t uniform_rand(uint16_t n)
{
    uint32_t range = (uint32_t)UINT16_MAX + 1;
    uint32_t bound = range - (range % n);          /* upper bound */
    uint16_t x;
    do {
        x = get_unsigned16();                      
    } while ((uint32_t)x >= bound);                /* reject if in the “extra” tail */
    return x % n;
}
```

```c
static inline void random_shuffle_array(uint16_t *ops, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* unbiased shuffling */
        uint16_t j = uniform_rand(i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}
```

但要注意，目前的作法是拒絕取樣(rejection sampling)，極端情況下可能會經歷多論迴圈一直重新取樣，這種非常數的運行時間有被惡意偵測去猜測(只要猜測尾端)的可能性!

#### 延伸 : list_move_tail 換為 list_move 造成的影響

若將 `list_move_tail` 置換成 `list_move` 會使得原先在後的節點移動到新鏈結串列時被插入到頭部，最終得到的鏈結串列就會和原本的順序顛倒，也會使排序過程變成非穩定的。

穩定排序對於多重排序非常重要，例如 PCI 匯流排上的裝置被掃描時，會依照 bus number、device number、function number 等進行排序，若在排序第三種鍵時，發現兩個目標值相同而改變了兩者順序，可能導致依照第一、二種鍵的排序被破壞! 因此，應 `list_move_tail` 不能被 `list_move` 替換。

### 測驗 2

#### Solution

- `GGGG`：`14`
- `HHHH`：`2`
- `IIII`：`0`
- `JJJJ`：`3`
- `KKKK`：`2`
- `LLLL`：`1`
- `MMMM`：`~1`
- `NNNN`：
- `PPPP`： `2`

#### Description

首先觀察 `clz2`:

```c=
static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}
```

對照題目給的 step 1 - 3，其中:

- step 1 : line 9 - 10
- step 2 : line 13
- step 3 : line 11 - 12

step 1 中，根據 `#define clz32(x) clz2(x, 0)` 可知道 `c` 的初始值是 0。只要上半部非 0，`c` 每次遞增 1。因此 upper 的右移位數將會是 16、8、4、2 (根據 step 3，會在 2 bits 的情況時結束遞迴)。
對於 lower，遮罩 `0xFFFF >> mask[c]` 中，低位為 1 的數量與當前的 upper 位數 (也就是 upper 右移位數) 相同。也就是低為是 1 的數量也是 16、8、4、2。`mask` 陣列和上述數量的總和固定會是 16，所以 `mask` 如下:

```c
static const int mask[] = {0, 8, 12, 14}; // GGGG == 14
```

接著讓我們跳到 step 3，對於停止條件是 2 bits，也就是 `c` 等於 3 時。故 `JJJJ` 為 3。line 12 告訴我們，當 upper 非 0，返回 `magic[upper]`，否則返回 `KKKK + magic[lower]`。變相告訴我們:

- `magic[1:3]` 跟==高半段==有關 ( `upper` 為 0 會走另一個分支)。
- `magic[0]` 只跟==低半段==有關。

`magic` 陣列是針對 `0b00`、`0b01`、`0b10`、`0b11` 而言，各提供了幾個 leading zero，因此 `magic` 陣列為

```c
static const int magic[] = {2, 1, 0, 0}; // HHHH == 2, IIII == 0
```

對於 `KKKK`，當 2 bits 下，`upper` 是 0，代表 upper 固定提供兩個 leading zero，故 `KKKK` 為 2。

最終回到 step 2，重點在處理完 `upper` 後處理低半段的地方:

```c
(16 >> (c)) + clz2(lower, c + LLLL)
```

其中:

- `16 >> c` : 代表當前 upper 全是 0 會提供的 leading zero 數量。例如 `c` 是 0 也就是第一輪 `upper` 就都是 0，就會提供 `16 >> 0` 個 leading zero。
- `clz2(lower, c + LLLL)` : 代表繼續處理下半部，每次遞迴 `c` 都遞增，故 `LLLL` 為 1。

探討完 `clz2` 和 `clz32`，可以繼續擴展至 `clz64`，後者依照上半段是否全 0 分為兩種情況

- 上半段全 0，使用 `clz32` 處理下半段 + 32 (上半段全 0)。
- 上半段不是全 0，使用 `clz32` 處理上半段。

至此，輔助函式探討完畢，進入 `sqrti`，參數是 `x`。根據註解，我們要計算 `m`，該值由 `1 << shift` 表達，且 `m` 要是 4 的冪。而 `shift` 為 `fls(x) & MMMM`。首先，`fls` 代表 find last set，即最高為是 1 的位元索引。該部分可以由 `clz64` 改寫，即 line 2:

```c=
int total_bits = 64;
int fls = total_bits - 1 - clz64(x); /* here */
int shift = fls & MMMM;

int m = 1 << shift;
```

`m` 要求是 4 的冪代表了 `shift` 必須偶數，如此 `m` 就會是 $2^{shift} = 4^{shift/2}$，確保其為 4 的冪。進而推斷 bitwise and `MMMM` 會使 `fls` 向下取偶，例如 29 會變成 28。該過程可以透過將第 0 位放 0 其他放 1 達成。故 `MMMM` 為 `~1`，注意 `~` 的優先級比 bitwise and 高，因此不需要加上括號。

`NNNN` 和 `PPPP` 放在下節說明。

#### 延伸 : sqrti 原理 (手算平方根)

延伸我們手算平方根的原理，可以推導出以下方式:

**流程**
- **X**：待開平方的整數，例：十進制的 12312 或二進制的 `0b100101`  
- **n**：進制基底，十進制時 ($n=10$)，二進制時 ($n=2$)  
- **分組（group）**：將 ($X$) 的數位從最高位起，每次「兩位」作為一組；十進制即「兩個十進位位元」，二進制即「兩個 bit」  
- **P**：已經確定的高位部分的商（partial root）  
- **rem**：剩餘前綴（remainder），即還沒開平方的那部分  
- **d**：本輪要嘗試的下一位商，範圍 ($0 \le d<n$)  

逐位試商方法可在任意進制 $n$ 下高效求整數平方根。首先將整數 $X$ 從最高位起，每次成組（兩位）帶下作為前綴。假設已得高位商為 $P$，剩餘前綴為 $\mathrm{rem}$，我們在 $0 \le d < n$ 中找 ==最大== $d$，使得新商 $P\,n + d$ 的平方不超過前綴。

透過 **「帶下 → 試商 → 扣除 → 更新商」** 的迭代，直至所有組處理完畢，即可得到 $\lfloor\sqrt{X}\rfloor$。

根據平方和公式:

$$
(Pn + d)^2 = P^2n^2 + 2Pnd + d^2 = P^2n^2 + (2Pn + d)d
$$

由於每次計算都已經會從 $\mathrm{rem}$ 扣除 $P^2n^2$，因此我們在試商時使用的判斷式便是:

$$
(2Pn + d)d \le \mathrm{rem}
$$

$P$ 的更新則是

$$
P = Pn + d
$$

**範例**

讓我們以 10 進制開始示範，以 12312 為例子，此處 $2Pn$ 可以寫成 $20P$。

1. **分組**  
   $$12312 \;\longrightarrow\; (1)\,(23)\,(12)$$  

2. **處理第一組 $(1)$**  
   - 帶下：$\mathrm{rem} = 0 \times 100 + 1 = 1$  
   - 除數底數：$P=0$, $20P = 0$  
   - 試商：最大 $d = 1$，因 $(0+1)\times1 = 1 \le 1$  
   - 更新：$\mathrm{rem} = 1 - 1 = 0,\;\; P = 0 \times 10 + 1 = 1$

3. **處理第二組 $(23)$**  
   - 帶下：$\mathrm{rem} = 0 \times 100 + 23 = 23$  
   - 除數底數：$P=1$, $20P = 20$  
   - 試商：  
     $$d=1:\;(20+1)\times1 = 21 \le 23,\qquad
       d=2:\;(20+2)\times2 = 44 > 23$$  
     取 $d = 1$  
   - 更新：$\mathrm{rem} = 23 - 21 = 2,\;\; P = 1 \times 10 + 1 = 11$

4. **處理第三組 $(12)$**  
   - 帶下：$\mathrm{rem} = 2 \times 100 + 12 = 212$  
   - 除數底數：$P=11$, $20P = 220$  
   - 試商：  
     $$d=0:\;(220+0)\times0 = 0 \le 212,\qquad
       d=1:\;(220+1)\times1 = 221 > 212$$  
     取 $d = 0$  
   - 更新：$\mathrm{rem} = 212 - 0 = 212,\;\; P = 11 \times 10 + 0 = 110$

5. **結果驗證**  
   $$110^2 = 12100 \le 12312 < 111^2 = 12321$$  

因此答案是 110。

以 2 進制寫成 C code，$d \in \{0, 1\}$，$(4P + d)d$ 作為試除數，$P = 2P + d$ :

```c
uint64_t isqrt_direct(uint64_t X) {
    uint64_t P   = 0; // partial root (accumulated result)
    uint64_t rem = 0; // remainder after bringing down groups

    // Compute highest group index k (each group = two bits)
    // (63 - clz64(X)) gives the index of the top bit; >>1 to get group count
    int k = (63 - clz64(X)) >> 1;

    // Process each group from most significant (k) down to 0
    for (int i = k; i >= 0; --i) {
        // 1. Bring down the next group of two bits into rem:
        //    rem = rem * 4 + G_i, where G_i = (X >> (2*i)) & 0x3
        rem = (rem << 2) | ((X >> (2 * i)) & 0x3);

        // 2. Form the trial divisor t = 4*P + 1
        uint64_t t = (P << 2) | 1;

        if (rem >= t) {
            // d = 1 case: subtract t and set next root bit to 1
            rem -= t;           // rem -= (4*P + 1)
            P   = (P << 1) | 1; // P = 2*P + 1
        } else {
            // d = 0 case: set next root bit to 0
            P <<= 1;            // P = 2*P
        }
    }

    return P;
}
```

其中迴圈對 $P$ 的操作能夠更簡化些:

```c
for (int i = k; i >= 0; --i) {
    rem = (rem << 2) | ((X >> (2 * i)) & 0x3);

    uint64_t t = (P << 2) | 1;
    P <<= 1;
    if (rem >= t) {
        rem -= t;
        P |= 1;
    }
}
```

#### 延伸 : sqrti 原理 (多元平方和)

題目中的作法可以參考 [從 √2 的存在談開平方根的快速運算 - Digit-by-digit Method](https://hackmd.io/HUzAPdVVSACpsnaj5Omvgw?view#Digit-by-digit-Method)、 Hacker's Delight Edition 2 中 11-2 Hardware Algorithm 和 [2025-02-25 問答簡記](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg?view)。

- **$N^2$**：要開平方的整數。  
- **$n$**：最高位的索引。將 $N$ 在所選進制下展開為  
  $$
  N = a_n + a_{n-1} + \cdots + a_0
  $$
  後，最大的次方指標即為 $n$。  
- **$m$**：當前迴圈的位元指標，從 $n$ 依序遞減到 $0$，用以決定第 $m$ 位的貢獻。  
- **$a_m$**：第 $m$ 位的貢獻值。  
  - 二進制：$a_m \in \{0,\,2^m\}$  
  - 十進制：$a_m \in \{0,\,1\cdot10^m,\dots,9\cdot10^m\}$  
- **$P_{m+1}$**：已經「放入」的高位和， 
  $$
  P_{m+1} = \sum_{i=m+1}^n a_i.
  $$
  注意，我們計算時會從高位往低位計算，因此 $P_{m+1}$ 會比 $P_m$ 更早被計算。
- **$P_m$**：加入第 $m$ 位後的部分和
  $$
  P_m = P_{m+1} + a_m.
  $$  
- **$X_{m+1}$**：第 $m+1$ 輪結束後剩餘的餘量，初始為  
  $$
  X_{n+1} = N^2.
  $$  
- **$Y_m$**：若放入第 $m$ 位所產生的 ==增量==，  
  $$
  Y_m = (2P_{m+1} + a_m)\,a_m.
  $$  
- **$X_m$**：第 $m$ 輪結束後的新餘量，  
  $$
  X_m = X_{m+1} - Y_m.
  $$

老師推導中的核心被開根號數 ($N^2$) 可以被拆解成多項和 $(a_n + a_{n-1} + ... + a_0)^2$，且多元平方和中，如果多增加一項 ($a_m$)，則增量 ($Y_m$) 可以由下式表達:

$$
Y_m = (2P_{m+1} + a_m)\,a_m.
$$

此處 $P_{m+1}$ 是指從最前面的項往下加到 $a_m$ 前一項，例如對於 $N=a_n + ... + a_{m+1} + a_m$，注意此處 $m+1$ 代表的是 $m$ 的前一項而不是後一項:

$$
P_{m+1} = a_n + a_{n - 1} + ... + a_{m+2} + a_{m+1}
$$

這是很好的特性，因為能知道增加下一項 $a_m$ 會不會超過 $N^2$。將此概念套用到套用到 2 進制整數系統後，數字 $x$ 可表示成 :

$$
x \;=\;
\Bigl(\underbrace{00000}_{\text{leading zeros}}
\;\underbrace{b_n\,b_{n-1}\dots b_0}_{\text{value}}\Bigr)_2^2 = \lfloor N^2 \rfloor
$$

此時，$\lfloor N^2 \rfloor$ 可表示成:

$$
\begin{aligned}
\lfloor N^2 \rfloor &= (b_n \times 2^n + b_{n-1} \times 2^{n-1} + \dots + b_1 \times 2^1 + b_0 \times 2^0)^2 \\
                    &= (a_n + a_{n-1} + \dots + a_0)^2
\end{aligned}
$$

此時，誤差 $X_m$ 可表達為 :

$$
X_m = N^2 - P_m^2 = X_{m+1} - Y_m
$$

而 $Y_m$ 可進一步表達成

$$
    \begin{aligned}
    Y_m 
    &= (2P_{m+1} + a_m)\,a_m 
    = \bigl(2P_{m+1} + b_m\,2^m\bigr)\,\bigl(b_m\,2^m\bigr) \\[6pt]
    &= 2b_mP_{m+1}2^m + b_m^2 2^{2m}
       = 
       \begin{cases}
         0,       & b_m = 0,\\
         P_{m+1}2^{m+1} + 2^{2m},   & b_m = 1.
       \end{cases}
    \end{aligned}
$$


我們能將其拆解成 $C_m = P_{m+1}2^{m+1}$ 和 $Dm = 2^{2m}$

其中 $C_m$ 可寫成:

$$
\begin{align}
    C_m 
    &= P_{m+1}2^{m+1} \\
    &= (P_m-a_m)2^{m}2 \\
    &= 2P_m2^{m} - 2a_m2^{m} \\
    &= 2c_{m-1} - 2a_m2^m.
\end{align}
$$

移向後得:

$$
C_{m-1} = \frac{C_m}{2} + 2a_m2^m = \frac{C_m}{2} + D_m
$$

$D_m$ 的關係則如下:

$$
D_m = a_m 2^{2m} = a_m 2^{2(m-1) + 2} = a_m D_{m-1} \times 4
$$

移向後得 
$$
D_{m-1} = 
        \begin{cases}
        \frac{D_m}{4}, & a_m = 1 \\
        0, & a_m = 0
        \end{cases}
$$    

對應到題目中的實作可知:

- `b` : $Y_m = C_m + D_m$
- `y` : $C_m = \frac{C_{m+1}}{2} + D_m$
- `m` : $D_m$，不論如何持續右移 2 bits

故 `NNNN` 對應 1 ($C_{m-1} = C_m / 2$，右移 1)，`PPPP` 對應 2 ($D_{m-1} = D_m / 4$，右移 2)。

另外，若不希望分支存在，可以使用:

```c
t = (int64_t)(x | ~(x - b)) >> 63; // -1 (all set) if x >= b, else 0 (all unset).
x = x - (b & t);
y = y + (m & t);
```

#### 延伸 : sqrti 向上取整

向上取整的實作可以基於前述向下取整的實作，只需要判斷 `x` 殘留值是否大於 0。因此返回值更改為以下即可:

```c
return y + (x > 0);
```

根據 C11 §6.5.8 - 6

>Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) **shall yield 1 if the specified relation is true and 0 if it is
false**.$^{107)}$ The result has type **int**.

判斷大小的運算子只可能返回 0 或 1，因此可用來進行向上取整。

#### 延伸 : sqrtf

### 測驗 3


#### 延伸 : 證明 Theorem S

:::success
When we successively insert the points $\{\theta\}, \{2\theta\}, \dots$ into the interval $[0,1]$, **Theorem S** asserts that each new point always splits one of the largest remaining subintervals.

If the interval $[a,c]$ is thereby broken into two parts $[a,b]$ and $[b,c]$, we call it a *bad break* if one of these parts is more than twice as long as the other, namely if  
- $b - a > 2\,(c - b)$, or  
- $c - b > 2\,(b - a)$.

**Exercise 8 (Section 6.4):** Prove that bad breaks will occur for some $\{n\theta\}$ unless
$$
\theta \bmod 1 = \varphi^{-1}
\quad\text{or}\quad
\theta \bmod 1 = \varphi^{-2},
$$
and that for these latter values of $\theta$, no bad breaks ever occur.
:::



