# 2019q1 Homework1 (list)
contributed by < `fwfly` >

# 紀錄

## Makefile
依照原本的 makefile 拼出一個 makefile 去 build merge-sort

CFLAGS = -I ../include -I ../private
CFLAGS += -std=c99 -pedantic -Wall -W -Werror

.PHONY: all
all: test

include ../common.mk

test: merge-sort

merge-sort: merge-sort.c
        $(VECHO) "  CC\$@.c\n"
        $(Q)$(CC) -o $@ $(CFLAGS) $@.c

還不了解 .PHONY 跟 .DEFAULT_GOAL 的部分

Merge-sort reference:

# To do:
## Merge-sort
* 實作 merge-sort 部分
* 了解 dict 即 測試

## 自我檢查
* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* 用 linux header 關鍵字搜尋 linux sort
* GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
* 解釋以下巨集的原理

#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 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
* tip: 從 list_for_each 去搜尋 linux code
* 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
* list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
* for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
* tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* tests/ 目錄的 unit test 可如何持續精進和改善呢？

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