# 2019q1 Homework1 (list)
contributted by < [`chengWei1123`](https://github.com/chengWei1123) >
---
## 開發環境
```shell
$ uname -a
Linux wei-X550JX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
```
---
## 作業要求
> 節錄自： [F02: list](https://hackmd.io/s/S12jCWKHN)
* 回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
- [ ] 自我檢查事項:
* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* 解釋以下巨集的原理
```Clike
#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` 這樣的設計有何意義？
* 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-list](https://github.com/sysprog21/linux-list) 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
* 附上你的修改過程，也需要讓 `qtest` 得以支援
* 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
---
## 自我檢查清單
### 為何 Linux 採用 macro 來實作 linked list？
macro 只是單純的文字替換，雖然會增加 code section 的大小，但能省去 call function 時對stack 的操作，進而加快執行速度。
另外，我覺得 macro 在某些情況會比 function 更具彈性，例如 list.h 中的 list_for_each
```clike
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
programmer 只要在呼叫 macro 後加上對 list node 的操作就好，而這一點使用 function 可能就比較難做到（可能要把對 list node 的操作寫成 function ，再把 function pointer 當成參數傳入 list_for_each function ）。
下面是我在 [Macro vs Function in C](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c) 看到有人對 macro 和 function 的優缺點所做的統整
* Macro features:
* Macro is Preprocessed
* No Type Checking
* Code Length Increases
* Use of macro can lead to side effect
* Speed of Execution is Faster
* Before Compilation macro name is replaced by macro value
* Useful where small code appears many time
* Macro does not Check Compile Errors
* Function features:
* Function is Compiled
* Type Checking is Done
* Code Length remains Same
* No side Effect
* Speed of Execution is Slower
* During function call, Transfer of Control takes place
* Useful where large code appears many time
* Function Checks Compile Errors
:::danger
不要只摘錄網路上的討論文字，設計實驗來檢驗，附上組合語言和 cycle count 分析，及早脫離「文組^TM^」
:notes: jserv
:::
考慮以下程式碼 ```test.c```
```clike=
#include <stdlib.h>
#define add_m(a,b,c) a+b+c
int add_f(int a,int b,int c){
return a+b+c;
}
int main(int argc, char *argv[]) {
int i,j,k,result;
int opt = atoi(argv[1]);
int times = atoi(argv[2]);
if(opt == 0){
for(i=0;i<times;i++)
for(j=0;j<times;j++)
for(k=0;k<times;k++)
result = add_m(i,j,k);
}
else{
for(i=0;i<times;i++)
for(j=0;j<times;j++)
for(k=0;k<times;k++)
result = add_f(i,j,k);
}
}
```
argv[1] 為 0 則使用 macro, 否則用 function ; argv[2] 則為各層迴圈數。
**result :**
* ```
$ sudo perf record ./test 0 1000
$ sudo perf report
```
* ```
$ sudo perf record ./test 1 1000
$ sudo perf report
```
* 不同迴圈次數下使用 macro 和 function 的 cycle count
### Linux 應用 linked list 在哪些場合？
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？
typeof(x) 會回傳 x 的 type
其中 x 可以是變數也可以是 type
例如：
1. ```clike
int x;
typeof (x) y = 0;
```
相當於
```clike
int y = 0;
```
2. ```clike
typeof (typeof (char *)[4]) y;
```
相當於
```clike
char *y[4];
```
### 解釋以下巨集的原理
```Clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* ```__extension__```
* 使用 GNU C extensions 編譯時可能會產生 warning ，可以在 expression 前加上 ```__extension__``` 來避免
* [Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords)
* ```{ }```
* braced-group within expression， compiler 會把大括號中所有 statement 當成一個 expression，並用最後一則 statement 的值作為此 expression 的結果
* [Statements and Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html#Statement-Exprs)
* ```__typeof__(((type *) 0)->member) *__pmember = (ptr);```
* ```(type *) 0```:
把0位置強制轉型成為一個指向 type 型別的指標
* ```__typeof__(((type *) 0)->member)```：
取得 type 所有的 member 之型別
* ```__typeof__(((type *) 0)->member) *__pmember```：
將 __pmember 宣告為指向 member 的 pointer
* ```__typeof__(((type *) 0)->member) *__pmember = (ptr)```
將 ptr 的位址 assign 給 __pmembe
::: warning
雖然看得懂這行在做什麼，但不太明白其中的必要性
:::
* ```offsetof(type, member)```:
struct 和 member 記憶體位置的差值
* ```(char *) __pmember - offsetof(type, member)```:
得到 struct 的起始位置
### 為何除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作？
### `LIST_POISONING` 這樣的設計有何意義？
### linked list 採用環狀是基於哪些考量？
### 什麼情境會需要對 linked list 做排序呢？
### 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？
### for_each 風格的開發方式對程式開發者的影響為何？
### 程式註解裡頭大量存在 `@` 符號，這有何意義？
### `tests/` 目錄底下的 unit test 的作用為何？
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
---
## Merge Sort
:::danger
應列出你的思路和規劃，不是急著列出程式碼。
需要提及驗證正確性和時間/空間複雜度分析
:notes: jserv
:::
* [程式碼](https://github.com/chengWei1123/linux-list/blob/master/examples/merge-sort.c)
* 思路分析
* merge sort 主要有三個工作
1. 把 input list 分成 2 等分
2. 再分別對這兩個 list 做排序
3. 把排序過的兩個 list 合併成一個排序好的 list
* 把 input list 分成 2 等分
* 首先要找到 list 的中點，我原本用的方法是先走訪 list 所有點的到總點數，再走訪一半的點找到中點，但後來改用直接把 list 長度當參數傳入，便可以少一次走訪全部點的時間
* 接著用 list_cut_position() 把 list 前半移到一個 list，另一半移到另一個 list
* 分別對這兩個 list 做排序
* 遞迴呼叫 merge sort 就好
* 合併兩個 sorted list
* 當其中一個 list 為空時，只要把另一個 list 用 list_splice_tail() 接在 result list 後面
* 當兩者都不為空時, 比較持有兩個 list 第一個 node 的 listitem 中 member i 的大小，將具有較小的 member i 者，移至 result list 的尾巴(使用 list_del()、list_add_tail() )
---
## 效能分析
random_shuffle_array 所產生的數據 (average case for all)
---
Sign in with Wallet
Connect another wallet