# 2019q3 Homework 3(list) contributed by <`Ting199708`> --- ## Linux 風格的 linked list * 自我檢查事項 - [x] 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？ > 根據 [What is the difference between a macro and a function in C programming?](https://www.quora.com/What-is-the-difference-between-a-macro-and-a-function-in-C-programming)， macro 具有以下幾點優點使其優於 function call > * Make your program easier to read > * Improve efficiency(they can be calculated at compile time) > * They Can shorten long or complicated expressions that are used a lot - [ ] Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量 - [x] GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？ > typeof 也是一 macro ，其用法和 sizeof 非常類似，但是其回傳值為變數型態，可將某一變數的變數型態指定給另一變數，如： ==typeof(*x) y== - [x] 解釋以下巨集的原理 ```c #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` > 首先，先看到 `list.h` 內針對此 macro 的註解： > ==Calculate address of object that contains address ptr== > > 再來，我們將其逐一解開來了解內部運作 > * ==__typeof__(((type *) 0)->member)== : `((type *) 0)->member` 的資料型態 > * ==const __typeof__(((type *) 0)->member) *__pmember = (ptr)== : 定義一資料型態為 `((type *) 0)->member` 的指標變數 `*__pmember` ，並將 ptr 存入其中 > * ==offsetof(type, member)== : 為 member 在 type 中的偏移值，其回傳型態為 size_t > * ==(type *) ((char *) __pmember - offsetof(type, member))== : 將 __pmember 與上一點算出的偏移值相減，再轉回 type 的指標 - [x] 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？ > 在 list.h 中，除了 add 和 delete 相關操作外，另外還有 list_splice, list_cut_position, list_move 等函式。 > * list_splice: 拼接兩 linked_list ，根據檔案內註解，其功能和 add 很類似，但一次可新增多個 node 至 linked_list中。 > * list_cut_position: 此函式可將原本 list 中 @head_from 至 @node 移到新的 list 中。 > * list_move: 將 list 中某 node 移到 list 的開頭，可應用到做 list 排序時。 - [x] `LIST_POISONING` 這樣的設計有何意義？ > 根據 [`/include/list.h`](https://github.com/sysprog21/linux-list/blob/master/include/list.h) 內的註解 > ==LIST_POISONING can be enabled during build-time to provoke an invalid memory access when the memory behind the next/prev pointer is used after a list_del.== > 可見 LIST_POISONING 可以避免在執行 list_del 後訪問到 invalid 的 memory address。 - [x] linked list 採用環狀是基於哪些考量？ > linked list 的環狀結構可以在使用時增加效能，若是沒有環狀結構的設計，在讀取時皆要從 head 開始讀取，增加執行時間 - [ ] 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現 - [ ] 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？ - [x] list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？ > 先來看看兩者的原始碼 ```c #define list_for_each_safe(node, safe, head) for (node = (head)->next, safe = node->next; node != (head); node = safe, safe = node->next) #define list_for_each(node, head) for (node = (head)->next; node != (head); node = node->next) ``` > 兩者其實非常的類似，唯一差別在於 `safe` 在執行時將 node->next 存到 safe 做為緩衝，避免在有刪除節點的動作時產生 undefined 的情形。 - [x] for_each 風格的開發方式對程式開發者的影響為何？ > foreach 通常用於遍歷陣列或是集合中的元素，其作用和 for 迴圈類似，其不同點在於， foreach 不會有所謂的 off-by-one errors ，減少迴圈編寫時的錯誤 > 在其他程式語言中，如 Python ， for 迴圈即已導入foreach的概念，如下方範例 ```c sequences = [0, 1, 2, 3, 4, 5] for i in sequences: print(i) ``` - [x] 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？ > 根據 [The Linux Kernel](https://www.kernel.org/doc/html/v4.10/doc-guide/kernel-doc.html#writing-kernel-doc-comments) ， @parameter is name of a function parameter. (No cross-referencing, just formatting)。 > 在編寫大型專案時，如 linux kernel ，需要有一致的 coding style ，因此在註解符號的運用上也是非常重要的，可以方便自己或別人在日後閱讀時更加清楚。 - [x] `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？ > unit test 可以幫助程式開發者驗證程式內各單元的正確性，因為在大型專案中若是對整個程式去做測試往往很難抓出問題根源所在，因此 unit test 在程式開發中非常重要。 - [ ] `tests/` 目錄的 unit test 可如何持續精進和改善呢？ ## 實作 Linked list 待補充 ## Reference [What is the difference between a macro and a function in C programming?](https://www.quora.com/What-is-the-difference-between-a-macro-and-a-function-in-C-programming) [The Linux Kernel](https://www.kernel.org/doc/html/v4.10/doc-guide/kernel-doc.html#writing-kernel-doc-comments)