# 2019q1 Homework1 (list)
contributed by < `Laurora`>
* [F02: list](https://hackmd.io/s/S12jCWKHN#F02-list)
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* macro表示方式為`#define MACRONAME 指令或常數`
* 用 `#define` 定義一段指令或常數，當 preprocessor 掃描到程式中 macroname 表示時，便會使該 macro 表示的指令或常數替換。
:::info
看起來和 function call 很像，為什麼不用 function call 就好了？
:::
- [x] 在呼叫 function call 時需要 stack 的 `push` 和 `pop` 來存取傳入變數和 function 位置，時間成本增加，當 function call 大量使用時便會浪費掉許多時間。
- [x] 使用 macro 時則是直接將程式碼替換，須增加指令空間，若指令複雜相對指令空間就必須分配較多，且維護不易，因此 macro 適合替換簡單且大量重複的指令。
:::danger
設計實驗來驗證上述說法，搭配反組譯結果的解讀
:notes: jserv
:::
---
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
---
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* typeof 是 gcc 對 C 語言中的一個 extension
* 主要功能是回傳參數的 type
* 傳入 typeof 的參數可以有兩種形式： expression 或是 type
* expression
```clike
typeof (x[0](1))
```
>這邊假設陣列 x 存取指向 function 的 pointer， typeof 便可以得到 function 回傳的 type
* type
```clike
typeof (int *)
```
>也可以直接輸入 type ， typeof 得到的就是 int *
```clike
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
>當使用 macro 定義 type 時，因不確定傳入的變數的 type ，因此需要 typeof 找到該變數的 type 避免執行錯誤。
---
### 解釋以下巨集的原理
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* `((type *) 0)->member` ： `0` 的 type 是 pointer to type 並指向 `master`
* `__typeof__(((type *) 0)->member)` ： 用 typeof 取得 `master` 的 type
* `__typeof__(((type *) 0)->member) *__pmember` ：宣告 `*__pmember` ， type 為 `master` 的 type
* `__typeof__(((type *) 0)->member) *__pmember = (ptr);` ： `*__pmember` 的位址為 `(ptr)`
* [offsetof](http://man7.org/linux/man-pages/man3/offsetof.3.html) 的用途是計算 structure member 的 offset ，以 byte 為單位 return structure memeber的 offset
* `__extension__` ： 告訴 gcc 不要提出警告
* `(char *) __pmember - offsetof(type, member);` ： 則以 `__pmember` 減去 `member` 在 `type` 這個 structure 的 offset，可以得到這個 type 的起始位址
* `(type *) ((char *) __pmember - offsetof(type, member)); ` ：宣告此起始位址為 pointer to type
---
### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
更完善 `list.h` 的功能，考量不同情況的呼叫，避免發生程式嚴重錯誤。
:::danger
不要用字面意思解讀，善用案例解釋 (及早脫離「文組^TM^」)
show me the code!
:notes: jserv
:::
---
### `LIST_POISONING` 這樣的設計有何意義？
---
### linked list 採用環狀是基於哪些考量？
---
### 什麼情境會需要對 linked list 做排序呢？
排序可以使資料搜尋變得更快，現實生活中的應用如：
* 排序好以後可以快速尋找整個 list 最小和最大的元素
* Heap Sort 是圖論中實現 priority queue 的一種方式，可應用在 Dijkstra's algrithm （尋找最短路徑）、 Huffman 編碼（資料壓縮）
在 Linux kernel 中的應用如：
* file system management
* garbage collection
參考：[Basic Data Structures and Algorithms in the Linux Kernel](http://luisbg.blogalia.com/historias/74062)
:::danger
用實際程式碼解說，附上分析和實驗
:notes: jserv
:::
---
### 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
---
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
* `list_for_each_safe`：會額外將 node 的下一個記錄在 `save` ，可避免刪除 node 後會找不到下一個 node。
```clike
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
* `list_for_each` ：不紀錄 node->next ，因此在刪除 node 時可能產生 dangling pointer
```clike
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
---
### for_each 風格的開發方式對程式開發者的影響為何？
<s>for_each 是 c++ 提供的 funtion templete ，可直接呼叫該函式回傳開發者要的結果。</s>
:::danger
本處是探討 Linux linked list macro，而不是 C++ 語言特徵
:notes: jserv
:::
* Linux linked list macro 在單向鍊結和雙向鍊結分別 define 了 `FOREACH` 和 `FOREACH_SAFE` 幫助迭代整個 list ，若需要從 list 中刪除元素則需要用到 `FOREACH_SAFE`
下面是 linux 中 定義單向鍊結的 `FOREACH` 和 `FOREACH_SAFE`
```clike
#define LL_FOREACH(head,el)
for(el=head;el;el=el->next)
```
```clike
#define LL_FOREACH_SAFE(head,el,tmp)
for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
```
對開發者而言， for_each 提供了一個比較通用的函式幫助迭代，只要呼叫函式，將需要處理的變數傳入函式即可，而不需要自己從 for/while 迴圈開始寫，不只可讓程式可讀性變得更高，開發者所遇到的錯誤會更少。
而在編譯器的處理上，編譯器對於這種已經包裝好的函式——不同於 for/while 必須對迴圈內的程式有 break, continue 的可能——不須多做預測與處理，讓編譯器可對整個程式效能做更好的改進。
若要將 array 中的所有 element 相加，不使用 for_each 實做可能會長這樣：
```clike
int main() {
int a[] = { 1, 2, 3, 4 };
int i;
int sum=0;
for (i=0;i<4;i++)
sum += a[i];
}
```
在 Python 中可以直接用三行程式碼就達到上面程式碼的效果
```python
a = [ 1, 2, 3, 4 ]
for i in a:
sum += a[i]
```
在函式導入或是物件呼叫變得複雜，開發者所遇到的困難或是錯誤可能會更多，此時 for_each 風格的使用能更簡化程式的呈現。
---
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
Doxygen 能自動從程式中生成註解， `@` 符號的功能是讓開發者呼叫特定的註解。
---
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
---
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
Sign in with Wallet
Connect another wallet