# 2019q3 Homework3 (list)
contributed by < `colinyoyo26` >
## 自我檢查事項
#### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
==回答==
* 使用 macro preprocessor 會把 code 直接展開，而且不用重複寫相同的 code
* 一般 fucntion call 需要儲存 caller 所使用的暫存器以及傳遞 argument 的額外操作
#### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
#### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
==回答==
- 可以得到 operand 的 type
- 可以讓程式碼更有彈性且避免出錯，舉以下例子
- [GNU extension](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
- The reason for using names that start with underscores for the local variables is to avoid conflicts with variable names that occur within the expressions that are substituted for a and b.
> 避免替換 a b 時 conflicts with variable names
```cpp
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
#### 解釋以下巨集的原理
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
==回答==
- `const __typeof__(((type *) 0)->member) *__pmember`
- declare `_pmember` as pointer type of `(type *) 0)->member`
- (char *) `__pmember - offsetof(type, member)`
- `member` 的 base address 減掉 structure `type` 到 `member` 的 offset 得到 type 的 base address
#### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
==回答==
- 方便 programmer 開發，易讀性高，容易 reuse 以及 debug
* `LIST_POISONING` 這樣的設計有何意義？提示: 和 [Linux 核心記憶體管理](https://hackmd.io/@sysprog/rJBXOchtE)有關
* linked list 採用環狀是基於哪些考量？
* 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
#### 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
==回答==
- 需要一直 reuse 時先 sort 之後用 binary search （如果是 array）
- 若不用 reuse 則用 [selection algorithm](https://en.wikipedia.org/wiki/Selection_algorithm) 實作
#### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
==回答==
- `list_for_each_safe` 有段註解如下，比對可以看出 `list_for_each_safe` 刪除 current node 時其實不會有影響，但是 `list_for_each` 會產生 dereference null ptr 的情況
> The current node (iterator) is allowed to be removed from the list. Any other modifications to the the list will cause undefined behavior.
- list_for_each
```cpp
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
- list_for_each_safe
```cpp
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
#### for_each 風格的開發方式對程式開發者的影響為何？
> 提示：對照其他程式語言，如 Perl 和 Python
==回答==
- 可以抽象化資料結構細節，方便開發者撰寫 code
#### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
> 提示: 對照看 Doxygen
==回答==
- Doxygen 是程式文件產生工具，將程式特定註解轉換成說明文件，須遵循其註釋撰寫格式
- 延伸閱讀: [doxygen的注釋的寫法的介紹](https://b8807053.pixnet.net/blog/post/3612235-doxygen%E7%9A%84%E6%B3%A8%E9%87%8B%E7%9A%84%E5%AF%AB%E6%B3%95%E7%9A%84%E4%BB%8B%E7%B4%B9)
#### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
==回答==
- 確保 code quality
- Correctness
- Performance
- 方便維護
- 容易團隊合作
- 加速開發
- 延伸閱讀: [Unit Test 教學：核心觀念](https://medium.com/@ji3g4kami/unit-test-%E6%95%99%E5%AD%B8-ba39e54fcbc5)
#### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
## 修改過程
- 因為想要寫的自動化一點，所以把個 sort 的 main function 都拿出來利用 `strcmp` 選擇 method
- 但是這樣還是要寫很多類似的 code 在 makefile 我在想想怎麼改進
```cpp
#define ANALYSIS(name) \
do { \
clock_gettime(CLOCK_REALTIME, &start); \
list_##name##sort(&name##_list); \
clock_gettime(CLOCK_REALTIME, &end); \
printf("%lu ", end.tv_nsec - start.tv_nsec); \
} while (0)
```
```cpp
if (!strcmp("all", argv[2])) {
ANALYSIS(m);
ANALYSIS(q);
ANALYSIS(insert);
}
```
- gnuplot
- 在 Makefile 內用 -e 傳遞 command line argument
```cpp
set title "perf"
set xlabel "size"
set ylabel "time (ns)"
set terminal png font " Times_New_Roman,12 "
set key left
set yrange[0: 20881933]
set output filename
if (!exist("name3")){
plot \
"out.txt" using 1:2 title name1, \
"out.txt" using 1:3 title name2 \
}
else{
plot \
"out.txt" using 1:2 title name1, \
"out.txt" using 1:3 title name2, \
"out.txt" using 1:4 title name3
}
```
- common.h
- 增加以下 function 作為 increasing 測資
```cpp
static inline void increasing_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
operations[i] = i;
}
}
```
- benchmark.c
- 用 `#ifdef` 篩選 input
- 參考 [bauuuu102 的共筆](https://hackmd.io/@jD9XFdyQS0iyAaFMPYi5Ww/rkqu6rqBV)
```cpp
#ifdef RANDOM
random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
#elif INCREASE
increasing_array(values, (uint16_t) ARRAY_SIZE(values));
```
## 實作 Merge sort 效能分析
- 以下是 merge-sort 和 quick-sort insertion-sort 的效能比較 (random input)
- insertion-sort 如預期效能最差，mertge-sort 在 random input 時表現的比 quick sort 還差蠻多的，但下面改變 input 可以發現 merge-sort 表現的非常穩定
- 因為這個實作的 quick-sort 每次都取第一個元素當 pivot 所以當 input 數據有一定趨勢時會表現的很差
- 以下測試 increasing input
- 改成這樣 insertion-sort 效能就和 quick-sort 相近了，但是 merge-sort 還是遙遙領先
- 原本預期 insertion-sort 效能會最好，但是竟然只和 worst-case 的 quick-sort 相近，發現原因後再補上
## qtest
- queue.h
- 把原本 list_ele_t 資料結構刪掉
- queue_t 改成以下
```cpp
typedef struct {
struct list_head list;
char* value;
} queue_t;
```
- 接著把 queue.c qtest.c 改成對應的操作還有資料結構就好，比較值得提的是 qtest.c 中的 show_queue function 原本的 `e == NULL` 要改成以下
- 否則會出現 `"ERROR: Either list has cycle, or queue has more than %d elements"`錯誤訊息
```cpp
if (list_entry(&e->list, queue_t, list) == q) {
```
- q_reverse
- 原本有 segmentation fault 的問題，回去寫自我檢查事項就發現問題了
- 更動 current node 的 `next` 指標要用 `list_for_each_safe` 否則會直接回到 head
```cpp
void q_reverse(queue_t *q)
{
if (!q || size < 2)
return;
struct list_head *prev, *node, *safe;
list_for_each_safe (node, safe, &q->list) {
prev = node->prev;
node->prev = node->next;
node->next = prev;
}
prev = (q->list).prev;
(q->list).prev = (q->list).next;
(q->list).next = prev;
}
```
#### 加入 sort command
- qtest.c
- 加入 `do_sort` function
- `init_console`內加入 `add_cmd("sort", do_sort, " | Sort the queue")`
```cpp
bool do_sort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
bool ok = true;
error_check();
if (exception_setup(true))
q_sort(q);
exception_cancel();
show_queue(3);
return ok && !error_check();
}
```
- queue.h
- 加入以下宣告
- 並在 Makefile 內和 `merge-sort.c` link 在一起
- 目前是用 merge-sort 可以在 queue.c 內改成其他兩者
```cpp
void q_sort(queue_t *q);
extern void list_msort(struct list_head *head);
extern void list_qsort(struct list_head *head);
extern void list_insertsort(struct list_head *head);
```
- 成功 sort
```
q = [3 5 1 8 20]
cmd>sort
cmd>sort
q = [1 3 5 8 20]
```
- 交作業後發現忘記測試 make test 很多測資沒過，改完後再補上
```
TOTAL 51/100
```
## 參考資料
- [Unit Test 教學：核心觀念](https://medium.com/@ji3g4kami/unit-test-%E6%95%99%E5%AD%B8-ba39e54fcbc5)
- [bauuuu102 的共筆](https://hackmd.io/@jD9XFdyQS0iyAaFMPYi5Ww/rkqu6rqBV?type=view)
- [Unit Test 教學：核心觀念](https://medium.com/@ji3g4kami/unit-test-%E6%95%99%E5%AD%B8-ba39e54fcbc5)
Sign in with Wallet
Connect another wallet