# 2021q1 Homework1 (quiz1)
contributed by < `XDEv11` >

> [GitHub](https://github.com/XDEv11/Linux_Kernel_Internals/tree/main/homework1/quiz1)
> [第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)

### 1.解釋上述程式運作原理

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

首先我們可以看到，根據 __node 的結構定義，一個無環的 singly-linked list 如下。

digraph SLL {
    rankdir=LR
    head [shape="cds", label="head"]
    nodeA [shape=record, label="{A | {<value>value | <next>next}}"];
    nodeB [shape=record, label="{B | {<value>value | <next>next}}"];
    nodeC [shape=record, label="{C | {<value>value | <next>next}}"];
    
    head:e -> nodeA:w;
    nodeA : next:s -> nodeB:w;
    nodeB : next:s -> nodeC:w;
}

static inline void list_add_node_t(node_t **list, node_t *node_t) {
    node_t->next = *list;
    *list = node_t;
}

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

void quicksort(node_t **list)
{
    if (!*list)
        return;

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    CCC;
    *list = result;
}

接著，在上面 quicksort 的程式碼中，可以看到許多 `node_t **` (指標的指標)，在進入問題前，我們需要先了解它在此處的用途。

操作一個 singly-linked list 時，最為直觀的方式就是透過一個 `node_t *` 型態的指標，來指向目前的節點，但是這會導致我們無法改動它。因此我們可以思考，一個節點是如何存在一個 singly-linked list 中的這個位置的呢？是根據前一個節點的 `next` (或是 `head`) 來決定的。
因此當我們今天處理一個節點 A 時，透過一個 `node_t **` pp 來指向前一個節點的 `next` (或是 `head`)，一方面當我們需要節點 A 時，可以透過 `*pp` 來得到節點 A 的指標，另一方面需要把目前位置的節點 A 做替換時，也可藉由指定數值到 `*pp` 來完成。

下圖以操作節點 B 為例，紅色箭頭表示操作節點 B 的方式，`*pp` 可得到節點 B 的指標，`**pp` 可得到節點 B，`*pp = ??`則可把節點 B 替換掉。

digraph SLL {
    rankdir=LR
    head [shape="cds", label="head"]
    nodeA [shape=record, label="{A | {<value>value | <next>next}}"];
    nodeB [shape=record, label="{B | {<value>value | <next>next}}"];
    nodeC [shape=record, label="{C | {<value>value | <next>next}}"];
    pp [shape=box3d, label="pp"]
    
    head :e -> nodeA :w;
    nodeA:next :s -> nodeB :w [color="red"];
    nodeB:next :s -> nodeC :w;
    
    pp:n -> nodeA:next:w [color="red"];
}

#### LLL = ?

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

根據上述解釋， `while` 敘述的成立條件 `*left`，即在判斷目前的節點 X 是否為空，若不為空，則推進到下一個節點。
`left` 是指向 X 的前一個節點的 `next`，顯而易見的，在推進後，`left` 會轉為記錄 X 的 `next`，因此`*left` 得到 X 的指標，再把 X 的 `next` 取位址，答案為`left = &((*left)->next)`。

而在 `while` 敘述之後，目前的節點 (singly-linked list 的尾端) 的下一個位置為空，根據上述解釋，`*left = right;` 即可把這個空位置替換成 `right`，完成 `list_concat()` 的工作。

#### AAA / BBB = ?

    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

先判斷 AAA (BBB) 的型態，由 `list_add_node_t()` 的原型可得知是 `node_t **`，再綜合下面 `list_concat(&result, left);` 以及依據遞增順序排序，可以得知 `left` 是存放數值比較小的節點，因此 `list_add_node_t(n->value > value ? &right : &left, n);`

#### CCC = ?

quicksort 的原理是透過一個基準 (pivot)，每次把元素分成大於以及小於二個部分，因此基準節點最後當然是接在中間。
答案為 `list_concat(&result, pivot); list_concat(&result, right);`

#### random

測試程式中的 [random()](https://linux.die.net/man/3/random)，我們可以看到，
> The random() function uses a nonlinear additive feedback random number generator employing a default table of size 31 long integers to return successive pseudo-random numbers in the range from 0 to RAND_MAX.

代表程式每次執行都會得到相同結果。
我們可以透過 [srandom()](https://linux.die.net/man/3/srandom)，給予不同的種子來改善。
> The srandom() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned by random().

為了每次執行可以得到不同的種子，我們這邊使用時間。

[time()](https://en.cppreference.com/w/cpp/chrono/c/time) 函式，根據 [C11 standard](http://open-std.org/JTC1/SC22/WG14/www/docs/n1570.pdf) 7.27.2.4，
> The time function determines the current calendar time. The encoding of the value is unspecified.

但在作為亂數用途上，編碼方式不影響我們使用。

程式碼:
`srandom(time(NULL));`

:::warning
留意 `time(NULL)` 的輸出由於刻度只到秒級，容易預測，倘若挪作 PRNG 的種子，會有潛在的資訊安全風險。
:notes: jserv
:::

---

### 2.重寫上述 quick sort 程式碼，避免使用遞迴呼叫

[quick sort](https://en.wikipedia.org/wiki/Quicksort) 與 [merge sort](https://en.wikipedia.org/wiki/Merge_sort) 都是透過 divide-and-conquer 的技巧來解決問題，不同的是，merge sort 合併時還需要進行額外處理，而 quick sort 只需要單純的把 `left`, `pivot`, `right` 三部分擺好而已。參考 [array 版本的 quick sort 實作](https://alienryderflex.com/quicksort/)，可以發現到在 array 上，`left`, `pivot`, `right` 自然而然就會維持這個順序，由於沒有其他需要處理的工作，子問題遞迴很正常的就是 tail recursion，因此我們能夠輕易改寫成非遞迴版本。

再觀察測驗題中，singly-linked list 版本的 quicksort 顯然不是這麼回事，因為我們會動到其中的鏈結，最後必須把他們接回來。

下圖為示意圖，假設我們現在處理的區間稱為 X，

digraph SLL {
    rankdir=LR
    list [shape="cds", label="list"]
    subgraph cluster {
    label=X
        nodes [shape=record, label="{A|B|C|...}", style=bold];
    }
    cont [shape="none", label=""]
    
    list ->  nodes;
    nodes -> cont;
}

分成子問題之後，X 會變成三個散落的部分，彼此並沒有透過鏈結連在一起。

digraph SLL {
    rankdir=LR
    subgraph cluster {
    label=X
        nodesl [shape=record, label="{B|D|...}", style=bold];
        nodep [shape=record, label="A (pivot)", style=bold]
        nodesr [shape=record, label="{C|...}", style=bold];
    }
    left [shape="cds", label="left"]
    right [shape="cds", label="right"]
    
    left -> nodesl;
    right -> nodesr;
}

而我們希望的是，他跟 array 一樣，在切分成子問題後，就透過鏈結連在一起了。
此外，把 X 視作一個整體的話，可以發現原本左右也都有鏈結，我們也要維持它們，換句話說，也就是要讓 X 待在整個串列中原本的這個位置。

digraph SLL {
    rankdir=LR
    list [shape="cds", label="list"]
    subgraph cluster {
    label=X
           nodesl [shape=record, label="{B|D|...}", style=bold];
        nodep [shape=record, label="A (pivot)", style=bold]
        nodesr [shape=record, label="{C|...}", style=bold];
    }
    cont [shape="none", label=""]
    
    list -> nodesl;
    nodesl -> nodep;
    nodep -> nodesr;
    nodesr -> cont;
}

因此 stack `L` 的型態為 `node_t **`，就是為了要能夠修改誰待在這個位置，而 stack `R` 的型態只需要為 `node_t *`，因為是透過 X 指過去。
同時，子問題採許左閉右開區間表示 (`[*L[i]:R[i])`)，不僅僅易於走訪串列上的所有節點，同時也可以改變 X 該放在哪 (透過修改 `*L[i]`) 以及 X 該接上誰 (指向 `R[i]`)。

這邊優先處理長度較短的區間，可以看到，現在處理的區間為 X，stack 如下圖，

digraph SLL {
    stack [shape=record, label="{X|...|...}", style=bold];
}

處理完後分成 Y 與 Z 二部分，假設較短的區間為 Z，stack 如下圖，

digraph SLL {
    stack [shape=record, label="{Z|Y|...|...}", style=bold];
}

由 `len(Y) + len(Z) = len(X) - 1` 和 `len(Z) <= len(Y)` 可以得知，stack 每多一層，處理的區間長度至少會減半，深度為 O($\log n$)。
在一台 64 位元的電腦上，定義 `MAX_LEVELS` 為 64 即可，因為資料長度不可能超過 $2^{64}$。

void quicksort_nr(node_t **list) {
    // non-recursive version of quicksort
    #define MAX_LEVELS 64
    node_t **L[MAX_LEVELS], *R[MAX_LEVELS]; // stack

    int i = 0;
    L[0] = list, R[0] = NULL;
    while (i >= 0) {
        // pop from stack
        node_t **LL = L[i], *RR = R[i--];
        if (*LL == RR)
            continue;

        // choose first element as pivot
        // partition [pivot->next:RR)
        node_t *pivot = *LL;
        *LL = NULL;
        node_t *p = pivot->next;
        pivot->next = NULL;

        node_t *left = NULL, *right = NULL;
        while (p != RR) {
            node_t *n = p;
            p = p->next;
            list_add_node_t(n->value > pivot->value ? &right : &left, n);
        }
        // keep list linked together
        list_concat(&right, RR);
        list_concat(&pivot, right);
        list_concat(&left, pivot);
        list_concat(LL, left);

        // push into stack
        L[++i] = LL, R[i] = pivot; // [*LL:pivot)
        L[++i] = &(pivot->next), R[i] = RR; // [pivot->next:RR)
        // handle shorter segment
        if (cntl < cntr) {
            {
                node_t **tmp = L[i - 1];
                L[i - 1] = L[i];
                L[i] = tmp;
            }
            {
                node_t *tmp = R[i - 1];
                R[i - 1] = R[i];
                R[i] = tmp;
            }
        }
    }
}

---

### 3.[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心內部 linked list 的實作並予以簡化，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫

程式碼主要差異在於，只需要在自己定義的結構中納入一個 `list_head` 的成員，即可使用 `list.h` 中的 API，也可透過 `list_entry()` 得到整個物件。
這樣的好處是，不需要自行維護一個鏈結串列，同時也可以降低程式碼的[耦合性](https://en.wikipedia.org/wiki/Coupling_(computer_programming))，增加可維護性。

延續上面第 2 部分的概念，改寫成非遞迴版本，這邊 stack 選擇放入左開右開區間有幾個好處，

* 程式碼簡潔，區間容易表示
* (head:head)
* (L:pivot)
* (pivot:R)
* 容易把節點放到基準的左邊
* `list_move(node->next, L)`

比較特別的是，這邊直接將數值較小的節點接到 `L` 之後，而數值較大的節點則不需要移動，整個結構隨時維持為一個 circular doubly-linked list，

static void list_qsort_nr(struct list_head *head)
{
#define MAX_LEVELS 64
    struct list_head *sl[MAX_LEVELS], *sr[MAX_LEVELS];
    int i = 0;
    sl[0] = head, sr[0] = head;
    while (i >= 0) {
        struct list_head *L = sl[i], *R = sr[i--];
        if (L->next == R)
            continue;
        struct list_head *pivot = L->next, *node = pivot;
        int cl = 0, cr = 0;
        while (node->next != R) {
            if (cmpint(&list_entry(node->next, struct listitem, list)->i,
                       &list_entry(pivot, struct listitem, list)->i) < 0)
                list_move(node->next, L), ++cl;
            else
                node = node->next, ++cr;
        }
        if (cl >= cr) {
            sl[++i] = L, sr[i] = pivot;
            sl[++i] = pivot, sr[i] = R;
        } else {
            sl[++i] = pivot, sr[i] = R;
            sl[++i] = L, sr[i] = pivot;
        }
    }
}

---

### 4.研讀 [Ching-Kuang Shene](https://zh.wikipedia.org/zh-tw/%E5%86%BC%E9%8F%A1%E5%85%89) 教授撰寫的 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中

> TODO

###### tags: `linux2021`