--- tags: linux-internal-2023 --- # 2023q1 Homework (quiz1) contributed by < [LambertWSJ](https://github.com/LambertWSJ) > ==[測驗連結](https://hackmd.io/@sysprog/linux2023-quiz1)== / [GitHub](https://github.com/LambertWSJ/Linux-Internal-2023/tree/main/quiz1) # 測驗 `1` ## 程式碼填空 - [ ] `AAA` $\to$ item - [ ] `BBB` $\to$ list `list_first_entry` 要傳入指標的型態還有成員，從而得知 `AAA` 跟 `BBB` 為 `item` 跟 `list`，目的是從 `list` 的偏移量(offset) 計算出 `item` 的地址。 - [ ] `CCC` $\to$ `list_for_each_entry_safe` - [ ] `DDD` 與 `EEE` $\to$ `list_move` / `list_move_tail` quicksort 的這個階要將 list 分成比 pivot 大以及比 pivot 小的串列。觀察傳入 `CCC` 的參數還有數量，可以得知 `CCC` 為 `list_for_each_entry_safe`。 本測驗的 quicksort 要將串列的內涵值按遞增順序排列，排序完後會得到如下的串列，因此串列的節點如果比 `pivot` 小的話要將節點移動到 `list_less`，反之則要將節點移動到 `list_greater`。 為什麼無論是用 `list_move` 或是 `list_move_tail` 都可以? 因為遞迴到最後只會剩下一個節點，亦即排序好的節點，在依據節點是 less 或是 greater 放在 pivot 的前面或是後面，`list_move/_tail` 的目的是為了分類。 ```graphviz digraph { node[shape=box] rankdir=LR less->pivot->greater greater->pivot->less } ``` - [ ] `FFF` $\to$ `list_splice_tail` 最後的階段要將比 pivot 內涵值小的串列放在 pivot 前面，反之則要放在 pivot 後面，這樣串列的內涵值才會是遞增的，因此 list_greater 要透過 `list_splice_tail` 放在 `pivot`。 ```c list_add(&pivot->list, head); list_splice(&list_less, head); FFF(&list_greater, head); ``` 上面三行程式碼的圖解如下，其中 `FFF` 為 `list_splice_tail` `list_add(&pivot->list, head)` ```graphviz digraph { node[shape=box] rankdir=LR head->pivot } ``` `list_splice(&list_less, head)` ```graphviz digraph { node[shape=box] rankdir=LR head->list_less->pivot } ``` `list_splice_tail(&list_greater, head)` ```graphviz digraph { node[shape=box] rankdir=LR head->list_less->pivot->list_greater } ``` ## 延伸問題 TODO # 測驗 `2` ## 程式碼填空 以下將 `list_less` 跟 `list_greater` 分別稱為大串列跟小串列。 `GGGG` $\to$ `list_for_each_safe_entry` 跟測驗`1`一樣的原理，透過 `list_for_each_safe_entry` 將原串列依據 pivot 的內涵值分成大串列跟小串列。 `HHHH` $\to$ `list_move_tail` `IIII` $\to$ `&stack[++top]` `JJJJ` $\to$ `&stack[++top]` 將 pivot 合併到小串列，因為排序完要得到內涵值遞增的串列，而 pivot 的內涵值比小串列還大，因此要用 `list_move_tail`。 另外，stack 具有 LIFO 的特性，所以先推入大串列，再推入小串列，這樣再推出後要合併的時候才會是內涵值遞增的串列。 ```c if (!list_empty(&list_greater)) list_splice_tail(&list_greater, &stack[++top]); if (!list_empty(&list_less)) list_splice_tail(&list_less, &stack[++top]); ``` 當大小串列分割完後，要將其推入到 stack，stack 用來模擬遞迴的過程，保存的是每次遞回分割的大小串列。 `KKKK` $\to$ `&stack[top--]` 如果下一輪迴圈從 stack 推出的串列單一節點，表示串列是排序好的節點，這時候就可以將節點添加到 head， ## 延伸問題 TODO # 測驗 `3` ## 程式碼填空 ```c ```