2018q3 Homework3 (list)
===
contributed by < `chenishi` >

# Linux 風格的 linked list

> ### Q: 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
>
> Linux 風格的程式專案無論是 `branch condition`，`function definition`，`loop iteration`等等程式片段，都非常頻繁的使用 macro 來動態產生；其原因可能如下
> 1. macro 在前處理器時期便會將程式碼展開，可以減少在程式實際編譯的速度
> 2. `Function definition` 比較簡單的 (像是沒有其他自定義的 function call ) 直接用 macro 實做可以減少 function call stack 的使用，進而減少 content switch 時間
> 3. 相較於 C99 `inline` ，`inline`必須開啟最佳化才會在編譯時期將函式呼叫展開，但在某些編譯情況下無法對整份程式碼開啟最佳化（像是嵌入式系統），但又因為 linked list 這樣的功能用處實在是太廣了，有沒有做最佳化對整體效能有所影響，因此用 macro 來強制展開該程式碼

> ### Q: Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
> 1. File System

> ### Q: GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
> `typeof` 的用法類似 `sizeof`， 不過 `typeof` 提供的是動態辨識變數型態並回傳的功能，`typeof`在變數型態複雜隱晦的時候有用
> 不過值得注意的是， `typeof`並不是 iso c 的規格， 而是 gnu c 的規格
> 因此使用 `-std=c90` 時會出現錯誤
>
> 在 linux 2.6.7 kernel 中的 include/linux/kernel.h 有使用到類似的技巧

#define min(x,y) ({   \
 typeof(x) _x = (x);  \
 typeof(y) _y = (y);  \
 (void) (&_x == &_y); \
 _x < _y ? _x : _y; })

上述範例就是一個用 macro 達到 C語言多型函式 的例子之一
透過使用 `typeof()` 可以達到泛行輸入的目的
而第三行的判斷意在檢查 比較雙方型態是否相符合
不符程式編譯時會有 warning 警告兩邊型態不合需要 cast 轉型
配合上編譯選項 `warning as error` 就可以防止誤用
不過沒有加上 `warning as error` 還是可以編譯
不過 gdb 在編譯 macro 時會有 `[Inferior 1 (process 5388) exited normally]` 的警告

> ### Q: 解釋以下巨集的原理
> >#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})

> ### Q: 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？

> `LIST_POISONING` 這樣的設計有何意義？