# G04: list :::info 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2019 年系統軟體課程](https://www.facebook.com/groups/system.software2019/) :mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表 ::: ==[作業說明直播錄影](https://youtu.be/HlvvnRXzleQ)== ## 預期目標 * 學習 Linux 核心原始程式碼的資料結構 * 資料封裝和 C 語言程式設計技巧 * 設計 unit test ## Linux 風格的 linked list 閱讀 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) 共筆和觀看解說錄影。 ```shell $ git clone https://github.com/sysprog21/linux-list $ cd linux-list $ make ``` 預期會得到以下輸出: ``` CC tests/containerof.o LD tests/containerof *** Validating tests/containerof *** [ Verified ] ... CC tests/list_cut_position.o LD tests/list_cut_position *** Validating tests/list\_cut\_position *** [ Verified ] ``` 其中 `include/list.h` 學習 Linux 核心原始程式碼的 linked list 資料結構實作程式碼。 - [ ] 自我檢查事項: * 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？ * Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量 * GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？ * 解釋以下巨集的原理 ```cpp #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` * 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？ * `LIST_POISONING` 這樣的設計有何意義？提示: 和 [Linux 核心記憶體管理](https://hackmd.io/@sysprog/rJBXOchtE)有關 * linked list 採用環狀是基於哪些考量？ * 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現 * 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？ * `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？ * for_each 風格的開發方式對程式開發者的影響為何？ * 提示：對照其他程式語言，如 Perl 和 Python * 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？ * 提示: 對照看 Doxygen * `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？ * `tests/` 目錄的 unit test 可如何持續精進和改善呢？ ## 作業要求 * 回答上述「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼 * 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list) 並學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，進而實作出 merge sort * 附上你的修改過程，也需要讓 `qtest` 得以支援 * 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入 * 思考提升排序效率的方法，需要做平均和最壞狀況的分析 ## 繳交方式 * 編輯 [Homework3 作業區共筆](https://hackmd.io/@sysprog/BJCG-HGdS)，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆 ## 截止日期 * Oct 16, 2019 (含) 之前 * 越早在 GitHub 上有動態、越早接受 code review，評分越高 ## 參考資料 * [2019 年春季班作業區](https://hackmd.io/s/SJ4kPZYS4) * [2018 年秋季班作業區](https://hackmd.io/s/SkJbKd1c7) * [2018 年春季班作業區](https://hackmd.io/s/S1iCyyziG)