# 2018q3 Homework3 (list)
contributed by <`AlecJY`>

## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
像是底下這段程式碼

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

這段是 define 一個 macro 再去呼叫另一個 macro，假設兩個都是用 fuction 的情況，就會多浪費一些 stack 空間存放 return address 等等資料，直接利用 macro 展開的話就不需要了

還有像 `list_for_each` 這種走訪整個 list 的 macro

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

如果使用 function 來實作類似的功能的話，目前只有想到傳一個 function pointer 當作參數進去走訪的 function ，每走訪一個元素就呼叫一次當參數傳入的 function。這樣做的話除了有消耗 stack 的問題以外使用上也沒有 macro 直覺。

還有使用 macro 在訂定 struct 的彈性上比較高，可以使用自己定義的 struct 而不需要使用 function 預先定義好的 struct

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

### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
根據 [GCC 文件](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 的說明， `typeof` 是用來取得 type ，在語法上用起來像由 typedef 定義出來的 type name。

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

這段程式碼中的第 3 行就有使用 `typeof` ，利用 `typeof` 取得 `type` 結構中 `member` 欄位的 type

### 解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

第三行利用 `typeof` 取得 `type` 結構中 `member` 欄位的 type ，因為只是要取得 type ，不會實際存取到結構，所以記憶體位置可以是任意記憶體位置，這邊就直接填 0 。之後定義一個 `member` 的型別的指標變數 `__pmember` 給予 `ptr` 的值。
第四行的 `offsetof` 是用來算出一個結構和它的欄位間的距離，所以利用欄位的實際位址減掉結構和欄位的距離就可以找出結構的實際位址了

### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
像是 `list_splice()` 這個 function 可以把一個 list 跟另一個 list 接起來，在純粹只用提供的 API 操作的時候，如果只有使用 add 和 delete 時間複雜度就會高達 O(n) ，如果使用 list_splice() 就可以在常數時間完成了

### `LIST_POISONING` 這樣的設計有何意義？
`LIST_POISONING` 的運作是當把一個節點從 list 中刪除的時候，把被刪除的節點的 `prev` 和 `next` 都指向無法存取的記憶體位置。如果利用這個節點存取 list 的話就不會存取到原來的 list 而會觸發 segmentation fault

### linked list 採用環狀是基於哪些考量？
採用環狀的好處是沒有一個節點作為真正的開始，所以無論從哪個節點開始走訪都可以走訪全部的節點

### `list_for_each_safe` 和 `list_for_each` 的差異在哪？“safe” 在執行時期的影響為何？
把這兩段程式碼放在一起看

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

主要就差在多了一個 safe 變數，用來保存 node 的下一個位置。根據程式碼上方註解說明， `list_for_each_safe` 允許刪除當前的 node ，而 `list_for_each` 如果對當前 node 操作則會導致 undefined behavior。而讓 `list_for_each_safe` 可以順利刪除當前 node 而不會導致問題主要是靠 safe 變數儲存 node 的下一個位置，在執行迴圈移動到下一個 node 的時候會將 node 指向 safe ， 再將 safe 指向新 node 的下一個位置，不像 `list_for_each` 只是將 node 直接指向原先 node 的下一個位置。

### for_each 風格的開發方式對程式開發者的影響為何？
Python 的 foreach 語法風格大概如下

for x in arr:
    print(x)

順便補上 C# 的 foreach 語法

foreach (var x in collections) {
    Console.Writeln(x);
}

基本上 foreach 就只是一個語法糖，主要功能是走訪過一個集合，例如 array 或是 list 之類的資料結構，雖然可以很容易地拿 for 之類的語法取代，但是 foreach 可以避免使用者因為邏輯錯誤等因素錯誤的少走訪或多走訪一個元素，某些情況也可以減少一個無意義的 index 變數讓程式碼看起來比較精簡。

### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？

根據提示查了一下 Doxygen 的功能和用法，調了一下參數就產生了如下圖的文件