# 2019q1 Homework1 (list)
contributed by < `evanjack2002` >
###### tags: `linux2019`

## [F02: list](https://hackmd.io/s/S12jCWKHN)

### Purpose
- 學習 Linux 核心原始程式碼的資料結構
- 資料封裝和 C 語言程式設計技巧
- 設計 unit test

### 作業要求
- 回答上述「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
- 從 linux-list 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
- 附上你的修改過程，也需要讓 qtest 得以支援
- 可將 dict 裡頭的測試資料拿來作效能分析的輸入
- 思考提升排序效率的方法，需要做平均和最壞狀況的分析
- 截止日期 Mar 3, 2019 (含) 之前

## 自我檢查事項
### 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- 採用 macro 來實作 linked list？
- 減少 function call 成本
- 空間換取時間。
- 一般的 function call 有何成本？
- `jump` 和 `return`。

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

### 3. GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
- 找到 expression 所歸屬的 data type。
- e.g. `typeof(a)` 為 `struct listitem`，`typeof(b)` 為 integer。

    struct listitem {
        uint16_t i;
        struct list_head list;
    };

    struct listitem a;
    int b;

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

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

- 宣告一個 `__pmember` 常數變數 point to `member` 的 data type，並 assign `ptr` 值給 `__pmember` 常數變數。
- 此 `__pmember` 常數變數的 lifecycle 只在此 `{...}` 內。
- 透過 `__pmember` 的位址，減去在 `type` 裡到 `member` 的位移量，得到 point to `type` 的位址。
- 意旨透過 structure member 的 address，去找到包含此 memeber 的 structure。
- e.g. 把 `&a->list` 的位址，減去 2 (`offsetof(struct listitem, list)` 為 2)，會得到 `&a` 的位址

    struct listitem {
        uint16_t i;
        struct list_head list;
    };

    struct listitem a;

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

### 6. `LIST_POISONING` 這樣的設計有何意義？

### 7. linked list 採用環狀是基於哪些考量？

### 8. 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

### 9. 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？

### 10. `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- `list_for_each_safe` 允許在 iterate 過程中，移除 list entry，也不會影響 linked list 的連結。
- `safe` 為 `node` 的下一個 entry，`node` 被刪除，`safe` 仍可以繼續尋訪下一個 entry。

#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

### 12. 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
- `@` 為 Doxygen [Special Commands](http://www.doxygen.nl/manual/commands.html)。
- [Doxygen](http://www.doxygen.nl/) 能從 source code 中，產生出文件。
- 透過 `doxygen -g` 產生 `Doxyfile` 設定檔
- 修改 `Doxyfile` 設定
- 使用`doxygen Doxyfile` 產生文件
- 透過 soure code 的文件，讓新接觸的人，可以比較快瞭解 source code。
- e.g. `listitem` 的文件說明

### 13. `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
- unit test 的作用為何？
- 驗證 `list.h` 所提供的 functions。
- 軟體工程來說的精神為何？
- 減少開發與維護成本。
- 出現 bug 時，可以排除是這些 functions 照成。

### 14. `tests/` 目錄的 unit test 可如何持續精進和改善呢？

## 實作出 merge sort

Implement the recursive `list_merge_sort()` function

static void list_merge_sort(struct list_head *head, size_t merge_size)
{
    ...
    list_merge_sort(&list_left, i);
    list_merge_sort(&list_right, merge_size - i);
    ...

## Notes
- [Linux 核心設計 (Spring 2019) Wiki](http://wiki.csie.ncku.edu.tw/linux/schedule)
- [2019q1 Homework1 (作業區)](https://hackmd.io/s/SJ4kPZYS4?fbclid=IwAR2XVQp1_WsWFlxoAPggK2cTCSBje-YAoAmrmPHiDJ8_KQIRzf-qtm2sz70#2019q1-Homework1-%E4%BD%9C%E6%A5%AD%E5%8D%80)
- [Linux 核心設計: 第 1 週發展回顧](https://hackmd.io/s/B1RmWVGUE)

### Suffix Rules

.c.o:
	@echo $@
	$(VECHO) "  CC\t$@\n"
	$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF $@.d $<

Source [10.7 Old-Fashioned Suffix Rules](https://www.gnu.org/software/make/manual/html_node/Suffix-Rules.html)
- `.c.o:`
- if you define a rule whose target is ‘.c.o’, `make` takes it to be a double-suffix rule with source suffix ‘.c’ and target suffix ‘.o’.