# 2020q1 第 1 週隨堂測驗解題思路
contributed by < `ryanwang522` >
> [完整測驗題目描述](https://hackmd.io/@sysprog/linux2020-quiz1)
## 測驗 1
定義了一個單向 linked list:
```cpp
typedef struct __list {
int data;
struct __list *next;
} list;
```
在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:
```cpp
list *sort(list *start) {
if (!start || !start->next)
return start;
list *left = start;
list *right = left->next;
LL0; /* 待補 */
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right; ) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
LL1; /* 待補 */
} else {
LL2; /* 待補 */
merge = merge->next;
}
LL3;
} else {
if (!merge) {
LL4; /* 待補 */
} else {
LL5; /* 待補 */
merge = merge->next;
}
LL6;
}
}
return start;
}
```
## 思考過程
### 理解 recursive function
* 首先，可以看到 `sort` 是一個遞迴函式，這個遞迴的終止條件是：只要輸入的 linked list (以下簡稱 list) 為空或是只有一個元素，就返回自己。
* 如果為空，return `NULL`，代表 empty list
* 如果 `start != NULL`，且 `start->next == NULL`，代表只有一個元素存在在該 list，返回他自己。
* 上述兩個 base case 回傳的都是一串排序好的 list（單一元素或空串列，本身就是排序好的）。
* 注意 `sort` 這個函式一旦回傳，回傳的就是一串排序好的 list
* 所以接下來看到 `left` 和 `right`，想到的是將 list 拆成兩個部分
* 馬上聯想到 merge sort，但看一下後面的實作並沒有將 list 拆成等長的兩部分，<s>感覺不是</s> 不同於預期。
:::warning
理工人應避免在報告中提及「感覺」，這不是文學創作，是分析推論和系統開發!
:notes: jserv
:::
* 再從 `LL0` 的選項中看到 `left->next = NULL;`，如果是此選項的話就代表每次都把 list 最左邊的元素獨立出來，再分別對左右兩個 list 遞迴呼叫，先假設是這樣，繼續往下看。
```
LL0 => left->next = NULL
```
* 接下來是對左右遞迴呼叫
* 這裡比較好想的想法是假設輸入是一個長度為 2 的 list，`left` `right` 回傳後就分別指向 list 的第一個跟第二個元素。
* 若是長度大於 2 的情況下，`left` 就指向由輸入 list 最左邊第一個元素所構成的 sublist，`right` 則指向由剩下的元素所構成的 sublist 的開頭，並且`right = sort(right)` 回傳後，`right` 就是 **已經排序好的**
* 接者的問題就變成 -- 要**怎麼 combine `left`、`right` 兩個 sublist 成為一個一樣是由小到大的 list**， 並且讓 start 指向該 sorted list 的開頭。
* 想到這裡，合理猜測是 Insertion sort 的 linked list 版本
* 每次都把 left 的單一個元素 insert 到 sorted right list 裡面，不一樣的是從右到左，而不是習慣的從左到右
### 分析 for-loop
* left、right 分別指向左右兩個 sublist，且 `right` 是排序好的(**`right->data` 是 right list 中的最小值**)，從其各自所指向的值來看，根據三一律，以下分成三種情況討論，來推測實作應該長怎樣：
* `left->data` < `right->data`
* `line12` 的 if 敘述條件為真，並且一開始 `merge` 為 `NULL` --> 進入 `LL1`、`LL3`
* 思考時間到！此時 list 有兩個元素而且已經知道 `left` 是最小了，所以～把要回傳的開頭 `start` 指向最小元素才是 `LL1` 合理的選項。*加上 `merge` 為 `NULL` 才進來 `LL1` 的目的猜測是要初始化 `merge`*，選擇
> - [ ] start = left;
> - [x]start = merge = left;
* 針對 `LL3`，選項 \(c\) (d) 沒有意義，且 `left` 已經被 `merge` 所暫存，合理選擇
> left = left->next;
* `left->data` = `right->data`
* `line12` 的 if 敘述條件為 false，並且一開始 `merge` 為 `NULL` --> 進入 `LL4`、`LL6`
* 此時左右的最小值相同，`start` 指向左右都是合理選項，先跳過
* `left->data` > `right->data`
* `line12` 的 if 敘述條件為 false，並且一開始 `merge` 為 `NULL` --> 進入 `LL4`、`LL6`
* 此時 `right` 指向左右 list 中的最小，`start` 應該指向 `right`，和 `LL1` 同理，選擇
> - [ ] start = right;
> - [ ] start = merge = right;
* 和 `LL3` 同理，選擇
> right = right->next;
* 從上面 `left->data` < `right->data` 之後繼續推理，此時 `left` 為 `NULL`，`merge` 和 `start` 指向原本的左串列，`right` 依然指向右串列開頭 (注意`left` `right` 其中之一不為空，迴圈繼續)
* 此時 `line12` 的 if 條件皆不成立 --> 進入 `LL5` `LL6`
* 因為原本左邊的值比右邊排序好的串列的最小（開頭）還要更小，所以這時應該把 `merge` 所指的 node 連接到 `right` 的開頭，因此選擇
> merge->next = right;
* 並且執行 `LL6` `right = right->next`
* 在這之後 `right` 跟 `merge` 就會不斷右移直到 `right` 跑到最末端指向 `NULL`，此時 `left` `right` 都為空，跳出迴圈 return 排序好的串列給上一層呼叫。
* 從上面 `left->data` >= `right->data` 之後繼續推理，此時 `left` 依然指向左元素，`merge` 和 `start` 指向原本的右串列的最小，`right` 指向右串列的下一個元素
* 此時看 `line12`
* 如果右邊串列還沒走到底，`!right` 為 false
* `if` 後半部條件成立 (e.g. left:6, right:4->7) --> `LL2` `LL3`
* `LL2` : 把 `left` 指到的 node 插在 `merge` 後 `right` 之前
* `LL3` : `left` 指向 NULL
* `if` 後半部條件不成立 (e.g. 左元素已經放置完了，但 right 還沒走到底) --> **透過 `LL5` `LL6` 持續平移直到 `right` 走到底**
* 這裡就是可以改善的地方！
* 如果右邊串列走到底了（`right` 指到 NULL），`!right` 為真 --> `LL2` `LL3`
* `LL2` : 把 `left` 指到的 node 插在 merge 後 right 之前
* `LL3` : `left` 指向 NULL
## follow-up questions
### 解釋上述程式運作原理
```cpp
list *sort(list *start) {
if (!start || !start->next)
return start;
list *left = start;
list *right = left->next;
left->next = NULL; // partition input list into left and right sublist
left = sort(left); // list of single element is already sorted
right = sort(right); // sorted right sublist
// insertion until the two sublists both been traversed
// merge is always infront of the insertion position
for (list *merge = NULL; left || right;) {
// right list hasn't reach the end or
// left node has found its position for inserting
if (right == NULL || (left && left->data < right->data)) {
if (!merge) {
// start points to the node with min value
// merge starts from min value
start = merge = left; // LL1
}
else {
// insert left node between merge and right point to
merge->next = left; // LL2
merge = merge->next;
}
left = left->next; // LL3
}
else {
if (!merge) {
start = merge = right; // LL4
} else {
// shift until right == NULL or
// inset merge(=left) in front of right when min is in left sublist
// (LL1->LL5-> shift until right == NULL)
merge->next = right; // LL5
merge = merge->next;
}
right = right->next; // LL6
}
}
return start;
}
```
### 擴充為 circular doubly-linked list 並重新實作對應的 sort
* 定義 circular doubly-linked list 的節點資料結構
```cpp
typedef struct __list {
int data;
struct __list *next;
struct __list *prev;
} list;
```
* 一些 utilization functions
```cpp
/* push a new node to the head of the list */
void push(list **head_ref, int data) {
list *new_head = malloc(sizeof(list));
new_head->data = data;
if (!*head_ref) {
// the list is empty, create a single node
new_head->next = new_head->prev = new_head;
*head_ref = new_head;
return;
}
list *last = (*head_ref)->prev;
new_head->next = *head_ref;
new_head->prev = last;
last->next = (*head_ref)->prev = new_head;
*head_ref = new_head;
return;
}
void print(list *head, bool newline) {
list *curr = head;
if (!curr)
printf("The linked list is empty!\n");
while (curr->next != head) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("%d ", curr->data);
if (newline)
printf("\n");
}
```
* 要注意的是，新增一個新節點到一串 list 的最前面 (e.g. push) 跟插入一個新節點到一串 list 的中間 (e.g. insert)，兩著的實作是不一樣的
* **在原本的版本中 `LL2`、`LL5` 其實是不同概念**，只是實做起來剛好寫法相同
* 根據原本的程式邏輯，實作 circular doubly-linked list 由右到左的 insertion sort
* 想法相同，每一次呼叫都把長度 n 的 input 切成左右兩個 sublists 長度分別為 (1, n-1)。
* 處理插入的邏輯也跟上述相同，但由於資料結構的不同，有些寫法需要替換
```cpp
list *sort(list *start) {
// check if input contains only 0/1 node,
if (!start || start->next == start)
return start;
list *left = start;
list *right = left->next;
// one element in left list
left->next = left;
// tail element's next point to the begin of right
left->prev->next = right;
// right head's prev point to the tail element
right->prev = left->prev;
// one element in left list
left->prev = left;
left = sort(left);
right = sort(right);
// insert to the sorted right list
// loop until all elements are traversed
for (list *merge = NULL; left || right != start;) {
// right list hasn't reach the end (go back to the head of sorted list) or
// left node has found its position for inserting
if (right == start || (left && left->data < right->data)) {
if (!merge) {
start = merge = left;
} else {
// merge is among right list
// insert left node after the node pointed by merge
left->prev = merge;
left->next = merge->next;
merge->next = left;
left->next->prev = left;
// shift merge pointer
merge = merge->next;
}
left = NULL; // LL3
} else {
if (!merge) {
start = merge = right;
} else {
// when merge points to the left element
// (left sublist contains only one element)
if (merge == merge->next) {
// push merge on to right's head
merge->next = right;
merge->prev = right->prev;
right->prev->next = merge;
right->prev = merge;
}
// shift merge pointer
merge = merge->next;
}
right = right->next;
}
}
return start;
}
```
* 最後簡單的測試一下，隨機產生 100 個長度為 10 的陣列，跟 `qsort` 的結果比較。
```cpp
bool test(list *head, int* ans, int len) {
list *curr = head;
if (!curr) {
printf("The linked list is empty!\n");
return false;
}
qsort(ans, len, sizeof(int), cmp);
curr = sort(head);
int i = 0;
while (i < len) {
if (curr->data != ans[i]) {
return false;
}
curr = curr->next;
i++;
}
print(curr, false);
return true;
}
int main() {
int correct = 0;
srand(time(NULL));
for (int i = 0; i < 100; i++) {
int testcase[10] = {0};
for (int j = 0; j < 10; j++)
testcase[j] = rand() % 50;
list *head = NULL;
for (int j = 9; j >= 0; j--)
push(&head, testcase[j]);
printf("Testcase %d: ", i+1);
print(head, false);
printf(" --> ");
if (test(head, testcase, 10))
correct++;
list_free(&head);
printf("\n");
}
printf("%d/100 passed.\n", correct);
return 0;
}
```
* 測試結果
```
Testcase 1: 22 36 43 33 7 26 31 1 27 35 --> 1 7 22 26 27 31 33 35 36 43
...
Testcase 99: 12 26 47 17 47 17 49 21 1 23 --> 1 12 17 17 21 23 26 47 47 49
Testcase 100: 17 37 31 0 10 21 21 14 40 1 --> 0 1 10 14 17 21 21 31 37 40
100/100 passed.
```
## 依循 Linux 核心 `include/linux/list.h` 的實作
### 了解 Linux kernel list.h
首先，先找到 list.h [本人](https://github.com/torvalds/linux/blob/master/include/linux/list.h)， 裡面定義了 `list_head` 的結構
```cpp
struct list_head {
struct list_head *next, *prev;
};
```
它的作用是拿來串接自己定義的結構 (i.e. 作為該 struct 其中一個 member)。
以 quiz1 作為例子，在結構中增加一個型態為 `list_head` 的變數，如下：
```cpp
typedef struct Node {
int data;
struct list_head list_h;
} Node;
```
接著，我們可以利用以下的 macro，初始化一個 `list_head` ，用來代表一串 linked-list 的開頭。
```cpp
LIST_HEAD(list_start)
// struct list_head list_start = { &(list_start), &(list_start) };
```
把 macro 替代後發現
* `LIST_HEAD` 是拿來宣告一個 `list_head` 型態的變數，並且進行初始化，將他的 `prev`、`next` 都指向自己。
```cpp
#define LIST_HEAD_INIT(name) \
{ \
&(name), &(name) \
}
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
```
接著來嘗試利用 `list.h` 提供的函式實作 `push()` ，將一個新的 node 串接到目前 linked-list 的開頭。
```cpp
typedef struct list_head list_head;
void push(list_head list_start, int data)
{
Node *tmp = malloc(sizeof(Node));
tmp->data = data;
INIT_LIST_HEAD(&(tmp->list_h));
list_add(&(tmp->list_h), head_ref);
}
```
其中 `list_add` 函式在 `list.h` 中定義如下
* 先看 `__list_add()`，他會將一個新的 node 串接 `prev`、`next` 兩個節點之間
* 而 `list_add` 則是呼叫 `__list_add(new, head, head->next);`
* 實作中將 `new` 這個 node 插入到當前的 `head`、`head->next`之間
* 想反地，如果要插入尾端呢？利用 Circular linked list 特性其實很簡單
* 透過 `__list_add(new, head->prev, head);`
```cpp
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
```
看到這裡，簡單做了一些摘要
* 透過 `LIST_HEAD(list_start)` 可以宣告一個 `list_head` 型態的變數並初始化，代表一串 list 的起始點
* 而這個 `list_start` 由於是 `list_head` 型態，**代表它其實是一個 dummy head**，不存資料
* `list_start->next` 表示第一個元素
* `list_start->prev` 表示最後一個元素
```
list_start --> 1 --> 3 --> 5 ---
(不存data) |
^ |
| |
----------------------------
```
### 如何遍歷
假設我們有一串 `Node` 型態的資料，每一個都透過各自結構中的 `list_head` 中的 `prev`、`next` 互相串聯，如果我們想遍歷這串 list，很直覺的用 for-loop:
```cpp
list_head *curr;
list_head *head = &list_start;
for (curr = head->next; curr != &head; curr = curr->next) {
...
}
```
接著遇到了一個問題，要怎麼從 `list_head` 型態的 `curr` 取得當前所屬 `Node` 結構中的 `data` 呢？接著我看到了一個 macro
```cpp
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
```
從註解上來看，`container_of` 透過當前的 `list_head` 指標 (e.g. `curr`)，回傳一個指向 `curr` 所屬的結構的 pointer，示意圖如下：
```cpp
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) ); })
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
```
一個部分一個部分來看：
* `gcc` extension -- Statements in Expressions
* 根據 `gcc` 的 [online doc](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)，`{}` 的回傳值為最後一個 expression。
> The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.
* 舉例來說 `int x = ({1; 2;}) + 3;`，`x` 的值為 2 + 3 = 5
* Referring to a Type with `typeof`
* 根據 `gcc` 的 [online doc](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)，它可以以某一個變數的型態來宣告另一個變數
> `typeof (*x) y;` declares y with the type of what x points to.
* Zero Pointer Dereference
* `((Node *)0)->list` ，segmentation fault
* `printf("%zu\n", (size_t) &((Node *)0)->list)`，因為有 address-of 運算子的關係，這段程式碼可以正常執行，回傳 `list`的這個 member 在 `Node` 結構中從起始位置到他的位址 offset。
**透過 `list_entry(ptr, type, member)` 將遍歷得到的 `curr` 減去他在 `Node` 結構中的 offset，就能得到該指向當前結構的指標**。
因此現在我們能夠透過 `list_head` 結構成員遍歷整個 list，並取得結構中的 `data`。
### 實作 quiz 中的 sorting algorithm
邏輯相同，先將 list 切成左右部分，把 `left` 插入到排序好的 `right` 中正確的位置。
* 由於實作中需要 include `list.h`，於是我稍微改寫 `include/linux/list.h` ，使其成為可以在 userspace 下使用的標頭檔，可參考 Github 中的 `list.h`。
```cpp
void sort(list_head *start) {
// check if list is empty or contains only 1 element
if (list_empty(start) || start->next == start->prev)
return;
// initialize left list and perform partition
LIST_HEAD(new_start);
list_head *left = &new_start;
list_cut_position(left, start, start->next);
list_head *right = start;
// recursivly sort
sort(left);
sort(right);
// insertion
list_head *merge;
int left_data = list_entry(left->next, Node, list)->data;
// find the position for insertion
list_for_each(merge, right)
if (left_data < list_entry(merge, Node, list)->data)
break;
// merge is pointing to the first element bigger
// than the data in left list.
// Note that left is a dummy head
// __list_add(left->next, merge->prev, merge)
list_add_tail(left->next, merge);
INIT_LIST_HEAD(left);
return;
}
```
### 對不同實作進行封裝
因為有三種不同的 sorting 實作 (i.e. singular、doubly、list.h)，避免 `main` 充斥著 `if-else`， 所以我定義了一個函式介面，對主要的幾個函式進行封裝，並且在`sort_orig.c`、`sort_dbly.c`、`sort_kernel_list.c` 中對各自函式進行實作，最後在 `main.c` 中，在執行時期才透過 argument 參數決定要執行哪一個實作。
* 節點結構
* singular、doubly，singular linked-list 實作只用到 `next`
```cpp
typedef struct __list {
int data;
struct __list *next;
struct __list *prev;
} list;
```
* list.h
```cpp
typedef struct Node {
int data;
struct list_head list_h;
} Node;
```
* `sort.h`
* 因為 `list.h` 中節點結構跟前兩個差異太多，所以主要函式的參數及回傳值都運用 `void *` 統一
```cpp
#ifndef _SORT_H
#define _SORT_H
#include <stdbool.h>
typedef struct __list {
int data;
struct __list *next;
struct __list *prev;
} list;
/* for qsort */
extern int cmp(const void *a, const void *b);
typedef struct __INTERFACE {
void *(*initialize)();
void (*push)(void **head_ref, int data);
void (*print)(void *head, bool new_line);
void *(*sort)(void *start);
bool (*test)(void **head_ref, int *ans, int len, struct __INTERFACE *sorting);
void (*list_free)(void **head);
} Sorting;
extern Sorting orig_sorting;
extern Sorting dbly_sorting;
extern Sorting kernel_list_sorting;
#endif
```
* sort_kernel_list.c
```cpp
...
static LIST_HEAD(list_start);
static void *init()
{
return (void *)&list_start;
}
static void print(void *start, bool newline)
{
Node *curr_node;
list_for_each_entry(curr_node, (list_head *)start, list_h)
printf("%d ", curr_node->data);
if (newline)
printf("\n");
}
static void push(void **head_ref, int data)
{
...
}
static void *sort(void *start)
{
if (list_empty(start) || ((list_head *)start)->next == ((list_head *)start)->prev)
return start;
LIST_HEAD(new_start);
list_head *left = &new_start;
list_cut_position(left, (list_head *)start, ((list_head *)start)->next);
list_head *right = (list_head *)start;
left = sort(left);
right = sort(right);
// insertion
struct list_head *merge;
int left_data = list_entry(left->next, Node, list_h)->data;
list_for_each(merge, right)
if (left_data < list_entry(merge, Node, list_h)->data)
break;
list_add_tail(left->next, merge);
INIT_LIST_HEAD(left);
return right;
}
static void list_free(void **head_ref)
{
...
}
static bool test(void *head, int* ans, int len, Sorting *sorting)
{
...
}
Sorting kernel_list_sorting = {
.initialize = init,
.push = push,
.print = print,
.sort = sort,
.test = test,
.list_free = list_free,
};
```
* main.c
```cpp
...
Sorting *impl_provider[] = {
&orig_sorting,
&dbly_sorting,
&kernel_list_sorting,
};
int main(int argc, char *argv[])
{
assert((argc == 2) && "Usage: ./sorting impl_selector");
assert((atoi(argv[1]) < 3) && "Can't find impl");
Sorting *sorting_impl = impl_provider[atoi(argv[1])];
int correct = 0;
srand(time(NULL));
for (int i = 0; i < 100; i++) {
int testcase[10] = {0};
for (int j = 0; j < 10; j++)
testcase[j] = rand() % 50;
void *head = sorting_impl->initialize();
for (int j = 9; j >= 0; j--)
sorting_impl->push((void **)&head, testcase[j]);
printf("Testcase %d: ", i+1);
sorting_impl->print(head, false);
printf(" --> ");
if (sorting_impl->test(&head, testcase, 10, sorting_impl))
correct++;
sorting_impl->list_free((void **)&head);
printf("\n");
}
printf("Testcases %d/100 passed.\n", correct);
return 0;
}
```
---
- [ ] 指出程式改進空間，特別是考慮到 Optimizing merge sort;
- [x] 依循 Linux 核心 `include/linux/list.h` 程式碼的方式，改寫上述排序程式
- [ ] 嘗試將原本遞迴的程式改寫為 iterative 版本
## References
[Doubly Circular Linked List](https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/)
[Linux kernel list efficient generic linked-list ](http://www.davidespataro.it/kernel-linux-list-efficient-generic-linked-list/)
[magical container_of macro](https://radek.io/2012/11/10/magical-container_of-macro/)
Sign in with Wallet
Connect another wallet