# 2024-02-{20,27} 問答簡記

## 不同長度的 linked list 是否可以合併？
> [jouae](https://github.com/jouae)

從 [案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 延伸，我們將討論文中程式碼對不同長度的單向鏈結串列可否做合併？可以的話怎麼做到的？

### 回顧 [C99 規格書(ISO/IEC 9899:TC3)](https://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf)

* 6.5.13 Logical AND operator
>The && operator shall yield 1 if both of its operands compare unequal to 0; otherwise, it yields 0. The result has type *int*.

這邊要注意的是經由 && 邏輯運算子後，得到的型態是 *int*
* 6.8.5 Iteration statements
>$while$ $($ $expression$ $)$ statement
$do$ statement $while$ $($ $expression$ $)$ ;
$for$ $($ $expression_{opt}$ ; $expression_{opt}$ ; $expression_{opt}$ $)$ statement
$for$ $($ $declaration$ $expression_{opt}$ ; $expression_{opt}$ $)$ statement

C99規格書中描述 controlling expression 的限制為
>The controlling expression of an iteration statement shall have *scalar type*.

這邊 *scalar type* 根據 C99 6.2.5 Type 第 21 項 (page 36) 定義為
>Arithmetic types and pointer types are collectively called *scalar types*. Array and structure types are collectively called *aggregate types*.

而 Arithmetic types 在同個 section 下，第 18 項定義為
>Integer and floating types are collectively called arithmetic types.

* 有意思的是在[C++11規格書](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf)中， 5.14 Logical AND operator 下的規定是 `bool` 型態
>The && operator groups left-to-right. The operands are both contextually converted to type bool.

可以看到文中 `mergeTwoLists(*L1, *L2)` 輸入只有兩個 `ListNode` 結構體的指標。而內部實作的部分則由 `while(L1 && L2)` 實踐，所以當兩者皆非 null pointer 時，比較完大小順序就可以將兩者合併。

考慮其控制表達式的否命題即為：

L1 or L2 is a null pointer

說明停止條件為 L1 或是 L2 指向 null。兩者同時指向 null 的情形只會發生在傳入函式的 L1 和 L2 皆是 null pointer 。

以下圖例簡易說明兩不同長度的單向串列是如何合併的，`L1=[4, 5]` ， `L2=[1, 6, 7]`， `ptr` 就像針線的針，會依據節點數值大小把針頭（指標）穿過比較後的節點：

  digraph structs {
        node[shape=record]
        rankdir=LR
        ptr [label="<data> ptr"]
        L2_a [label="<data> 1|<header> L2"];
        L2_b [label="<data> 6"];
        L2_c [label="<data> 7"];
        
        L1_a [label="<data> 4|<header> L1"];
        L1_b [label="<data> 5"];
        
        
        L1_a -> L1_b -> null1;
        L2_a -> L2_b -> L2_c -> null2;
}

比較 L1 和 L2 大小。 `ptr->next` 指向 4 ， `ptr` 串接後的數列為 `[4]`

  digraph structs {
        node[shape=record]
        rankdir=LR
        ptr [label="<data> ptr"]
        L2_a [label="<data> 1|<header> L2"];
        L2_b [label="<data> 6"];
        L2_c [label="<data> 7"];
        
        L1_a [label="<data> 4"];
        L1_b [label="<data> 5|<header> L1"];
        
        ptr->L1_a -> L1_b -> null1;
        L2_a -> L2_b -> L2_c -> null2;
}

比較 L1 和 L2 大小。 `ptr->next` 指向 5 ， `ptr` 串接後的數列為 `[4, 5]`

  digraph structs {
        node[shape=record]
        rankdir=LR
        ptr [label="<data> ptr"]
        L2_a [label="<data> 1|<header> L2"];
        L2_b [label="<data> 6"];
        L2_c [label="<data> 7"];
        
        L1_a [label="<data> 4"];
        L1_b [label="<data> 5"];
        null1 [label="<data> null1|<header> L1"]
        
        L1_a -> L1_b -> null1;
        L2_a -> L2_b -> L2_c -> null2;
        ptr -> L1_a
}

跳出迴圈，判斷 `ptr->next` 該接到哪裡。由於 L1 目前為 null ， `ptr->next` 指向 L2 串接後的數列為 `[4, 5, 1, 6, 7]` 合併完成。

## 能否使用 linked list 去實作 quicksort
> joec1368

針對 Linux 核心的場景，強調是否可以達成 [in-place algorithm](https://en.wikipedia.org/wiki/In-place_algorithm)

## 何時用到 bubble sort 或 insertion sort?
> wilicw

* 已經接近排序好的 list。
* 任務優先權沒有顯著變化

## Linus 提到的 bad taste
[The mind behind Linux | Linus Torvalds | TED](https://youtu.be/o8NPllzkFhE?feature=shared&t=870) 中的程式碼為何是 bad taste？
* 避免 `head` 為 `null`。
* 使用 indirect pointer 來減少特殊案例的處理

## 排序程式碼練習
> [e-mail]

考慮以下程式碼，使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)

#include <stddef.h>
#include <stdint.h>

#include "list.h"

struct listitem {
    uint16_t i;
    struct list_head list;
};

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

static void list_insert_sorted(struct listitem *entry, struct list_head *head)
{
    struct listitem *item = NULL;

    if (list_empty(head)) {
        list_add(&entry->list, head);
        return;
    }

    list_for_each_entry (item, head, list) {
        if (cmpint(&entry->i, &item->i) < 0) {
            list_add_tail(&entry->list, &item->list);
            return;
        }
    }

    list_add_tail(&entry->list, head);
}

static void list_insertsort(struct list_head *head)
{
    struct list_head list_unsorted;
    struct listitem *item = NULL, *is = NULL;

    INIT_LIST_HEAD(&list_unsorted);
    list_splice_init(head, &list_unsorted);
    /* Put your code here */
}

> :warning: 上方程式碼不完整

## 為什麼不用在環狀鏈結串列中使用 swap 就可以做到交換？
> [jouae](https://github.com/jouae)

最簡單實作的 swap 如下：

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *a = tmp;
}

可以看到上述的部分需要額外一個變數 `tmp` 來暫存交換的值。

而在單向鏈結串列中，不用做到額外變數，只要使用間接指標（ indirect pointer ）。參見[你所不知道的 C 語言: linked list 和非連續記憶體——Merge Sort 的實作](https://hackmd.io/@owlfox/BJkrdnExL/https%3A%2F%2Fhackmd.io%2Fs%2FSkE33UTHf#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)：

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->val < L2->val) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

## merge sort 實作何處可用 `list_splice`？
> [a1157857220](https://github.com/a1157857220)

## Timsort 什麼時候用到 `list_splice`？
> [jouae](https://github.com/jouae)

在 Python 官方文件中 listsort.txt 紀錄這個由 Peters, Tim 開發的 Timsort 跟實驗內容，以下摘入自開頭片段：
> This describes an adaptive, stable, natural mergesort, modestly called timsort.

在 Timsort 中，討論的基本單位稱作為 run ，為一非遞減或是嚴格遞減的數列。例如：

[60, 50, 40, 1, 2, 3]

可以拆解成兩個 run：

run 1: [60, 50, 40]
run 2: [1, 2, 3]

而向上述原始數列就已經有排序的子數列，這些子數列稱作為 natural run ，而其餘沒有排序過的元素，會先蒐集起來至一定數量後，藉由插入排序（ insert sort ）來排序成為一個 run 。同時為避免比較次數過多， Tim 在實作的過程中有限制每個 run 的上限為 64。

在過往學員 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-timsort#Timsort-%E9%81%8B%E4%BD%9C%E6%96%B9%E5%BC%8F) 紀錄中，詳述 Timsort 流程。

回頭來看 `list_splice(*list, *head)`，由兩個輸入組成 `*list` 跟 `*head` ，兩者皆是 `list_head` 結構體的指標，作用為將 `list` 這個節點包含其後續節點，繫（ splice ）於 `head` 之後。所以在進行合併各個 run 的過程中， `list_splice` 就在此時上場。

在 Linux list_sort.c 中合併的實踐是由 `*merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)` 達成。由於並非環狀鏈結串列的合併，跟我們預期 `list_splice` 的運作不一樣， `list_splice` 針對環狀結構操作。

**注意**：在此的 `*a` 和 `*b` 為 null-terminated singly-linked list 。詳見原始碼中 `list_sort()` 的部分。

在 `merge_final()` 部分中，則還原了原本串列的環狀結構。

在函數的一開始先把單向串列改成雙向串列

// 將 a 鏈結在 tail 之後
// 並將 a 的前一個節點指向 tail 形成 doubly linked
tail->next = a;
a->prev = tail;

// 更新 tail 位置為 a
tail = a;
a = a->next;

函式的最後將雙向串列頭尾相連形成環狀結構

/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;

整個過程簡化的話，就是 `list_splice` 的功能。

* [Jserv. 你所不知道的 C 語言: linked list 和非連續記憶體——Linux 核心的 list_sort 實作](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-list_sort-%E5%AF%A6%E4%BD%9C)
* [visitorckw. Linux 核心專題: 改進 `lib/list_sort.c`](https://hackmd.io/@sysprog/Hy5hmaKBh)
* [yanjiew1. Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)
* [yanjiew1. linux23q1-timsort](https://github.com/yanjiew1/linux23q1-timsort/blob/main/timsort.c)
* [Peters, Tim. listsort.txt](https://svn.python.org/projects/python/trunk/Objects/listsort.txt)
* [Peters, Tim. [Python-Dev] Sorting. Python Developers Mailinglist.](https://mail.python.org/pipermail/python-dev/2002-July/026837.html)

## 為何 `list.h` 選定 0x00100100 與 0x00200200 作為無效的地址？
> [Jimmy01240397](https://github.com/Jimmy01240397)

我在做 `git log | grep <address>` 之類的操作後依然沒有詳細說明。只知道該 address 第一次出現是在 commit `9a69abf80edf2ea0dac058cab156879d29362788` "menuconfig: Add "breadcrumbs" navigation aid" 的位置

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

[linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 的註解:
> These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.

當 `list_del` 執行時，會將節點的的 prev 和 next 指向一個特定的地址，當存取到該地址時，會觸發 [page fault](https://en.wikipedia.org/wiki/Page_fault)。

在《[Linux Device Drivers 3/e](https://lwn.net/Kernel/LDD3/)》第四章 Debugging Techniques 的引言提到，Linux 核心的程式碼不易在除錯器中運作、錯誤也不易重現，不過一旦引發錯誤時，可能會讓整個系統崩潰，而造成錯誤的證據則隨之消失。

除錯的的其一手法就是將這種有毒 (poison) 的值設在使用前後，當該數值變更時，我們就會知道非預期的狀況發生。
> 諺語: One man's meat is another man's poison

有了這樣的設計，我們便可在除錯時知道 : 若 `node->next` 與 `node->prev` 分別指向 `LIST_POISON1` 與 `LIST_POISON2` 的話，就代表發生 use-after-free 的情況，像是 [lib/list_debug.c](https://github.com/torvalds/linux/blob/master/lib/list_debug.c) 便是 Linux 核心中對應的除錯程式碼。

若無 `LIST_POISONING` 的設計，在 `list_del()` 時將 `node->next` 和 `node->prev` 都指向 NULL，除錯階段就無法得知此時的 NULL 代表的是 uninitialized 抑或被釋放後才指派的。

至於不直接釋放節點的原因，可參閱 [Kernel Self-Protection](https://www.kernel.org/doc/html/latest/security/self-protection.html) 中 Memory poisoning 的部份得知：
> When releasing memory, it is best to poison the contents, to **<font color="#000">avoid reuse attacks that rely on the old contents of memory</font>**. E.g., clear stack on a syscall return (`CONFIG_GCC_PLUGIN_STACKLEAK`), wipe heap memory on a free. This frustrates many uninitialized variable attacks, stack content exposures, heap content exposures, and use-after-free attacks.

## [2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)第 1 題
> [weihsinyeh](https://github.com/weihsinyeh)

建立二元樹需要有透過得知中序（in-order）與前序 (pre-order) 或是後序 （post-order)才能具體說明一個獨一無二的二元樹的原因說明舉例如下。

前序是 `[A B C]`
透過前序知道 `A` 是 中間的那個點，但卻無法透過前序知道 `B` `C` 相對於A的左邊還是右邊。
因此產生的二元樹可能如下中序分別是 `[B C A]`, `[B A C]` , `[A B C]`

   A         A     A
  /         / \     \
 B         B   C     B
  \                   \
   C                   C
 (1)       (2)      (3)

第一個樹：由中序知道 `A` 是 中間的那個點，`B` `C` 相對於`A`在左邊。所以都在 `A` 的左子樹中。
第二個樹：由中序知道 `A` 是 中間的那個點，`B` 相對於 `A` 在左邊，所以在 `A` 的左子樹中。`C` 相對於`A`在右邊，所以在 `A` 的右子樹中。
第三個樹：由中序知道 `A` 是 中間的那個點，`B` `C` 相對於`A`在右邊。所以都在 `A` 的右子樹中。
所以 DFS 中的實作是透過 preorder 會藉由 `find` 找到`preorder[pre_low]` 在`inorder`中的位置 `idx`。

由圖得知在 `idx` 左邊的都會被放到左子樹，在`idx`右邊的都會被放到右子樹。

因此對應到左子樹的在中序涵蓋的範圍 ： `[in_low,idx-1]`，右子樹在中序涵蓋的範圍 ： `[idx+1,in_high]`

tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size);

而觀察剛剛的前序可以知道他的分佈的規則就是 `[中點 左子樹 右子樹]`，從這裡就可以看到只要知道左子樹有多少個，右子樹有多少個，就可以知道在前序的範圍了。

而因為 `pre_low` 是中點
左子樹在前序的涵蓋範圍 ： `[pre_low + 1, pre_low + (idx - in_low)]` 其實就是`pre_low`往後左子樹的在中序涵蓋的範圍 ： `[in_low,idx-1]`
右子樹在前序的涵蓋範圍 ： `[pre_high - (in_high - idx - 1), pre_high]` 其實就是`pre_high`往前右子樹的在中序涵蓋的範圍 ： `[idx+1,in_high]`

也因此從這樣的分析其實知道如果題目提供的只有後序與中序，我只要從後序的最後一個往前讀。
改變範圍即可因為後序的分佈是 `[左子樹 右子樹 中點]`，`post_high`是中點。
所以左子樹在後序的涵蓋範圍：`[post_low, post_low + (idx - 1 - in_low)]`
右子樹在後序的涵蓋範圍：`[post_high - 1 - (in_high - (idx+1)) , post_high-1]`

所以這樣也就明白中序在建立二元樹中缺一不可的角色，而前序與後序則是可以只挑其中一個。
而 `find` 函式則是用 hash table 去紀錄`in-order`的位置而已，可換成其他資料結構來實作。