2019q1 Homework1 (list)

contributed by < evanjack2002 >

tags: `linux2019`

F02: list

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 有何作用？在程式碼中扮演什麼角色？

找到 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 大/小元素呢？又，你打算如何實作？

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。
Doxygen 能從 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

Suffix Rules

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

Source 10.7 Old-Fashioned Suffix Rules

.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’.