# 2019q1 Homework1 (list)
contributed by < `rebvivi` >
###### tags: `linux2019`
* [F02: list](https://hackmd.io/s/S12jCWKHN#F02-list)
## 作業要求
- 回答「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
- 從 linux-list 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
* 附上你的修改過程，也需要讓`qtest` 得以支援
* 可將 dict 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
## 自我檢查清單
1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
2. Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
3. GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
4. 解釋以下巨集的原理
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr);\
(type *) ((char *) __pmember - offsetof(type, member));\ })
```
5. 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
6. `LIST_POISONING`這樣的設計有何意義？
7. linked list 採用環狀是基於哪些考量？
8. 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
9. 什麼情境會需要需要找到第 k 大/小元素呢？又，你打算如何實作？
10. `list_for_each_safe` 和 `list_for_each` 的差異在哪？“safe” 在執行時期的影響為何？
11. for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
12. 程式註解裡頭大量存在 `@`符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
13. `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
14. `tests/` 目錄的 unit test 可如何持續精進和改善呢
### 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- macro：用 `#define` 這個語法，描述一段`算式或變數`，在 compile 之前， preprocessor 就會將所有`算式或變數`用 `macro_name` 做代換，執行時不需要 function call 一樣有 stack 的 push 或是 pop，讓執行的速度變快
但隨著呼叫 macro 的次數增加，會大大的增加記憶體的使用量，是一種用==空間換取時間==的方法
```cpp
#define macro_name 算式或變數
```
- function call：
執行時需要有 stack 的 push 或是 pop ，也就是主要的成本，會讓執行的時間變慢
但是所有相同的算式都共用同一部份 code (共用同一部份記憶體) ，相對 macro 來說比較節省記憶體空間，是一種用==時間換取空間==的方法
### 2. Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
- 在 Linux kernel 中，有叫做 `list_head` 的 `doubly linked list`，包含 next 和 prev 兩個 pointer ，分別指向下一個跟前一個 node
```clike
struct list_head {
struct list_head *next, *prev;
};
```
一開始都會把 next 和 prev 指向自己做 initialization
之後就可以藉此判斷 list 是否是空的
```clike
int list_empty(const struct list_head *head)
{
return head->next == head;
}
```
參考資料：[Linked Lists - Linux Device Drivers, Second Edition](https://www.oreilly.com/library/view/linux-device-drivers/0596000081/ch10s05.html)
### 3. GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色
[typeof](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Typeof.html) 是 C 語言的 extension，用於傳回物件的 type
typeof 的參數可以有兩種：
- expression
>假設 x 是一個 array of pointers to functions ，我們可以得到這個 function 回傳值的 type
```cpp
typeof (x[0](1))
```
- type
>我們得到的 type 是 pointers to int
```cpp
typeof (int *)
```
>在 macro 的時候，可能無法判斷 a 和 b 的 type，所以如果使用 typeof 的話可以讓 macro 動態的接受不同的 type ，除了避免 type 轉換中產生錯誤，也可以讓程式更有彈性
```clike
#define max(a,b)
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
### 4. 解釋以下巨集的原理
```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 轉型為 pointer to type 並將它指向 member
- `__typeof__(((type *) 0)->member)`：
取得 "member 的 type"
- `__typeof__(((type *) 0)->member) *__pmember`:
將 __pmember 宣告為 pointer to "member 的 type"
- `__typeof__(((type *) 0)->member) *__pmember = (ptr)`:
將 ptr 的位址 assign 給 __pmember
[offsetof 的 Linux Man Page](http://man7.org/linux/man-pages/man3/offsetof.3.html) 寫到：
```cpp
size_t offsetof(type, member);
```
> The macro offsetof() returns the offset of the field member from the start of the structure type.
- `offsetof(type, member)`：
member 在 type 這個 structure 的 offset
- `(char *) __pmember - offsetof(type, member)`：
__pmember 是指向 “member 的 type” 的，如果再減去 “member 的 type” 在 type 這個 structure 的 offset，可以得到 type 這個 structure 的起始位置
- `(type *) ((char *) __pmember - offsetof(type, member))`：
將 type 這個 structure 的起始位置轉型為 type
- `__extension__`：
避免 gcc 提出警告
### 5. 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
- 這樣 list 在做這一系列操作的時候，能夠讓速度變得更快，將 time complexity 盡量壓在 O(1) 之內
- list 在做這一系列操作的時候，只有改變 list 指的位置，並沒有改變記憶體本身的資料，所以我們在放資料的時後就可以自由的放置在記憶體，並不因為使用 `linkes list` 這個 structure 而受到限制
參考資料：[Linux source code: include/linux/list.h](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h)
### 6. `LIST_POISONING`這樣的設計有何意義
>如果我們將一個 `doubly linked list` 中的 node 刪除
```cpp
* 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.
* This only works on systems which prohibit access to the predefined memory
* addresses.
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
>在刪除 node 之後， node 變成一個 uninitialized node，當我們去 access 這個 node 會變得不安全，所以我們會將 node 的 next 和 prev 指向不合法的記憶體位址，之後如果我們試圖去 access 這個被刪除的 node，就會直接產生 page fault，確保我們 access 資料時的安全性
### 7. linked list 採用環狀是基於哪些考量？
如果 linked list 採用環狀的結構，就沒有一般 linked list 那些 head 和 tail 的問題，對每個 node 來說並沒有操作上的不同，而且能夠任意一個 node 去 traverse 整個 linked list ，並不一定限制要從 head 開始
### 8. 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
當我們在搜尋網頁的時候，網頁往往會有 page rank ，用來分析網頁的相關性和重要性，而 page rank 會隨著網頁的點擊率而上升或下降，所以我們就要使用 sorting 來幫我們依照 page rank 的大小做排序
### 9. 什麼情境會需要需要找到第 k 大/小元素呢？又，你打算如何實作？
- 當搜尋引擎依照 page rank 的大小做排序之後，會需要找到第 k 大元素，把最大的 k 個網頁排在搜尋結果的前面
- 利用 worst-case linear-time selection 實作
1. Divide the n elements into groups of 5. Find the median of each 5-element group by rote
2. Recursively SELECT the median x of the n/5 group medians to be the pivot.
3. Partition around the pivot x. Let k = rank(x).
4. * if(i = k)
return x
* else if (i < k)
recursively SELECT the ith
smallest element in the lower part
* else
recursively SELECT the (i–k)th
smallest element in the upper part
### 10. `list_for_each_safe` 和 `list_for_each` 的差異在哪？“safe” 在執行時期的影響為何？
- list_for_each
>我們並不能更改任何一個 node ，假如我們 delete 掉一個 node ，我們會因此找不到原本 node 的下一個 element，因此失去 node 的後面那些資料
```clike
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
- list_for_each_safe
> `list_for_each_safe` 相對 `list_for_each` 多了一個 safe 的暫存空間，而 safe 指向 node 的下一個 element ，避免我們將 node 給 delete 掉之後，會找不到原本 node 的下一個 element
```clike
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
### 11. for_each 風格的開發方式對程式開發者的影響為何？(提示：對照其他程式語言，如 Perl 和 Python)
for_each 不像一般我們在 C 語言使用的 for 需要有一個 counter ， for_each 會將所有的 element 都跑過一遍
```clike
mylist = ['a', 'b', 'c']
for item in mylist:
print item
```
>輸出結果
```cpp
a
b
c
```
for_each 對我們人來說，使用起來更為精簡方便，可讀性也更高
### 12. 程式註解裡頭大量存在 `@`符號，這有何意義？你能否應用在後續的程式開發呢？(提示: 對照看 Doxygen）
- Doxygen 是一個可以自動產生文件的程式，它能夠抓取程式的內容，自動產生說明程式的文件
我們在註解的前方加入一些 Doxygen 支援的指令，比如說`@` 這個符號，可以告訴 Doxygen 這是特殊的指令，例如：
>以下用於說明一個 function ， parameter 是參數的名稱，而後方往往會連接對這個 parameter 的說明
```
@parameter：parameter 的說明
```
>以下是 `list_head` 上方的註解，也是`@` 這個符號的實際應用
```
* @prev: pointer to the previous node in the list
* @next: pointer to the next node in the list
```
在註解前方加入`@`等等的指令之後，能夠讓 Doxygen 更容易辨識一些關鍵字，更容易產生說明程式的文件
- 之後多人共同開發一些大型程式的時候，往往需要有這些註解，能夠幫助其他共同開發者可以快速看懂彼此的程式，增快開發程式的效率
### 13. `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
- unit test：針對程式裡最小的邏輯單元為對象，寫一個測試的程式，來檢驗這些邏輯單元是否正確
- * 從最小的邏輯單元開始測試，可以確保程式的正確性
* 我們輸入 make ，執行 unit test ，可以用自動化的方式測試我們的程式，而不用靠我們手動自己輸入測試資料
* 運用 unit test 能夠幫我們測試如果程式在面對一些極端情況的 input ，是否也能如期的產生我們所希望的 output
### 14. `tests/` 目錄的 unit test 可如何持續精進和改善呢？
可以根據一些極端值或邊界值做測試，看看程式會不會因此產生錯誤，讓程式能夠因應各式各樣的 input
Sign in with Wallet
Connect another wallet