# 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; ``` ![](https://i.imgur.com/tkmeg0w.png) * 一些 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,示意圖如下: ![](https://i.imgur.com/4PwueuT.png) ```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/)