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

不同長度的 linked list 是否可以合併？

jouae

從案例探討: LeetCode 21. Merge Two Sorted Lists 延伸，我們將討論文中程式碼對不同長度的單向鏈結串列可否做合併？可以的話怎麼做到的？

回顧 C99 規格書(ISO/IEC 9899:TC3)

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

$w h i l e$
$($
$e x p r e s s i o n$
$)$ statement

$d o$ statement
$w h i l e$
$($
$e x p r e s s i o n$
$)$ ;

$f o r$
$($
$e x p r e s s i o n_{o p t}$ ;
$e x p r e s s i o n_{o p t}$ ;
$e x p r e s s i o n_{o p t}$
$)$ statement

$f o r$
$($
$d e c l a r a t i o n$
$e x p r e s s i o n_{o p t}$ ;
$e x p r e s s i o n_{o p t}$
$)$ 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規格書中， 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 就像針線的針，會依據節點數值大小把針頭（指標）穿過比較後的節點：

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

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

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

能否使用 linked list 去實作 quicksort

joec1368

針對 Linux 核心的場景，強調是否可以達成 in-place algorithm

何時用到 bubble sort 或 insertion sort?

wilicw

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

Linus 提到的 bad taste

The mind behind Linux | Linus Torvalds | TED 中的程式碼為何是 bad taste？

避免 head 為 null。
使用 indirect pointer 來減少特殊案例的處理

排序程式碼練習

c24094031@gs.ncku.edu.tw

考慮以下程式碼，使用 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 */
}

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

上方程式碼不完整

為什麼不用在環狀鏈結串列中使用 swap 就可以做到交換？

jouae

最簡單實作的 swap 如下：

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

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

而在單向鏈結串列中，不用做到額外變數，只要使用間接指標（ indirect pointer ）。參見你所不知道的 C 語言: linked list 和非連續記憶體——Merge Sort 的實作：

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

Timsort 什麼時候用到 `list_splice`？

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 紀錄中，詳述 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 的功能。

為何 `list.h` 選定 0x00100100 與 0x00200200 作為無效的地址？

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 的註解:

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。

在《Linux Device Drivers 3/e》第四章 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 便是 Linux 核心中對應的除錯程式碼。

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

至於不直接釋放節點的原因，可參閱 Kernel Self-Protection 中 Memory poisoning 的部份得知：

When releasing memory, it is best to poison the contents, to avoid reuse attacks that rely on the old contents of memory. 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 週測驗題第 1 題

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的位置而已，可換成其他資料結構來實作。

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

不同長度的 linked list 是否可以合併？

回顧 C99 規格書(ISO/IEC 9899:TC3)

能否使用 linked list 去實作 quicksort

何時用到 bubble sort 或 insertion sort?

Linus 提到的 bad taste

排序程式碼練習

為什麼不用在環狀鏈結串列中使用 swap 就可以做到交換？

merge sort 實作何處可用 list_splice？

Timsort 什麼時候用到 list_splice？

為何 list.h 選定 0x00100100 與 0x00200200 作為無效的地址？

2024q1 第 2 週測驗題第 1 題

merge sort 實作何處可用 `list_splice`？

Timsort 什麼時候用到 `list_splice`？

為何 `list.h` 選定 0x00100100 與 0x00200200 作為無效的地址？