# 2018q3 Homework3 (list)
###### tags: `C語言`
contributed by < `asd757817` >
## 自我評量
**為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？**
- 以 macro 實作的目的在於將資料型態抽象化，開發者不用理會 list 內的資料型態，型態的問題會由 macro 展開程式碼的機制而解決。
- 以 function call 的方式實作，要以同一個函式處理多種型態就必須在函式內定義所有型態，如此一來會使程式碼過於繁瑣，且遇到定義外的情況時將無法運作。
**Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量。**
**GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？**
- typeof 的功用在於取得變數型態或函式回傳的型態，如 typeof(\*x) y，以 x 指向的型態作為 y 的型態進行宣告
- 以 typeof 取得函式回傳型態時函式並不會執行
- 在使用 macro 處理多種形態的問題時，除了傳入的參數外，還會使用新的變數且變數型態需要與傳入的參數相符，此時就需要利用 typeof 取得傳入的參數型態
- 在撰寫 header file 且會被 ISO C 引用時，會以 \_\_typeof\_\_ 取代 type
**解釋以下巨集的原理**
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- (type \*) 0： 把 0 轉換成 pointer to type
- ((type \*) 0)->member： 取的 type struct 裡面的 member 變數
- \_\_typeof\_\_(((type \*) 0)->member)： 取得 memeber 的型態，並且以這個型態宣告指標\*\_\_pmember，並讓 \*\_\_pmember = (ptr)
- offsetof(type, member)： member 在 type (通常是 struct) 中的 offset
- 以 \_\_pmember 的位置減去 member 在 type 中的 offset 可以獲得 pmember 所在的 type 的地址，其型態為 pointer to type，(char \*) 轉換指標型態，如此一來在運算時才會以一個 byte 為單位進行加減。
- 這個巨集的功能是已知 struct 的 member 找出 struct (傳入 A -> member 找出 A 的 ptr)
:::info
:question: 既然做運算時會強制轉型成 (char \*)，為什麼不在一開始就以 char 宣告？
:::
**除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？**
**`LIST_POISONING` 這樣的設計有何意義？**
**linked list 採用環狀是基於哪些考量？**
- 在一個特定的排序中不斷循環時就需要使用到 circular linked list，在 CPU 排程就會使用到
- 環狀能夠處理單向的工作，但是以單向來處理環狀的情況會複雜很多，雖然相較之下單向所需要的成本較少，但節省的成本並不至於特地使用單向來實作，反而全部統一以環狀實作在開發上較為方便。
Reference: [1](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel)
**`list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？**
- 走訪結束的條件為：pos = head，而 pos 改變是在當次迴圈動作結束後，因此考慮一個情況：當 pos->next = head，正常情況下這次迴圈結束後 pos = pos->next 會使 pos = head，但若是 pos 或 pos->next 經過某些運算使得迴圈執行結束後，pos = pos->next pos 不等於 head，迴圈將沒辦法正確停止。
- list_for_each_safe 則是改善了這個情形，多了一個 n 變數儲存 pos->next 的內容，在每次迴圈結束將 pos 移動到 n 的位置上，在上述情況時，即使把 pos 或者是 pos->next 經過修改，n 的內容仍然是 head，所以在這次迴圈結束後 pos 仍然可以指向 head 滿足迴圈結束的條件。
**for_each 風格的開發方式對程式開發者的影響為何？**
* 提示：對照其他程式語言，如 Perl 和 Python
**程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？**
* 提示: 對照看 Doxygen
**`tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？**
軟體開發的過程以 waterfall model 為例可分為：
```graphviz
digraph linked_list{
node[shape=record]
rec1 [label="<f0> Requirements"];
rec2 [label="<f0> Design"];
rec3 [label="<f0> Implementation"];
rec4 [label="<f0> Verification"];
rec5 [label="<f0> Maintenance"];
rec1 -> rec2;
rec2 -> rec3;
rec3 -> rec4;
rec4 -> rec5;
}
```
- 第三個階段 Implementation 指的是程式開發，包含程式碼撰寫、測試、除錯等，在這個階段必須確定開發的程式能夠運行，各函式功能正常，才能移動到下一個階段，unit test 就是屬於這個階段的工作，程式必須通過 unit test 開發才會繼續至下一個階段。
- 第四階段的 Verification 驗證整體程式運作是否符合 requirement 階段時所提出的要求，會有系統地進行測試，除了驗證程式可以正確輸入、輸出以外還會驗證程式的效能是否符合要求。
- 在軟體工程的精神上，程式開發就像是堆積木一樣，各個部分逐一完成，對應到實際開發就是一個函式一個函式逐步完成，unit test 的作用在於驗證各函式是否運作正常，當這個函式撰寫完畢且驗證正確後再接著開發下一個函式，如此一來開發的程式才更具可靠性。
在 test 資料夾中可以發現程式碼使用了許多 assert，其功能是進行比較，若比較結果不符合預期就回報錯誤訊息。
以 containerof.c 內容為例：
```C
#include <assert.h>
#include <stddef.h>
#include "list.h"
struct teststruct {
int a;
int b;
};
int main(void)
{
struct teststruct item;
assert(&item == container_of(&item.b, struct teststruct, b));
return 0;
}
```
container_of 的功能找到所屬 struct 的地址，所以這份測試檔案先宣告了一個 struct，
以 & 取得該 struct 的地址與 container_of 取得的地址進行比較，若兩者不相等 assert 就會發出錯誤訊息。
Reference: [waterfall model](https://zh.wikipedia.org/wiki/%E7%80%91%E5%B8%83%E6%A8%A1%E5%9E%8B)
**`tests/` 目錄的 unit test 可如何持續精進和改善呢？**
## queue 修改
### singly linked list 改為 doubly linked list
- 基於原本的 queue 結構，新增 prev 指標
- 呼叫 insert、remove 時更新 prev 指標
**queue.h 修正**
更新每個節點的結構：
```C
typedef struct ELE {
char *value;
struct ELE *next;
struct ELE *prev;
} list_ele_t;
```
**queue.c 修正**
q_insert_head 函式加入 prev 更新機制
```C
bool q_insert_head(queue_t *q, char *s)
{
if (!q || !s) {
return false;
} else {
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
char *s_cpy = malloc(strlen(s) + 1);
if (newh && s_cpy) {
strcpy(s_cpy, s);
newh->value = s_cpy;
newh->next = q->head;
/* 因為是加入的位置在 head，prev 為 NULL*/
newh->prev = NULL;
/* 如果 head 存在，把 head->prev 指向 newrec */
if (q->head) {
q->head->prev = newh;
}
q->head = newh;
if (!q->tail)
q->tail = newh;
q->size += 1;
return true;
} else {
if (newh)
free(newh);
if (s_cpy)
free(s_cpy);
return false;
}
}
}
```
q_insert_tail 函式加入 prev 更新機制
```C
bool q_insert_tail(queue_t *q, char *s)
{
if (!q || !s) {
return false;
} else {
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
char *s_cpy = malloc(strlen(s) + 1);
if (newh && s_cpy) {
s_cpy = strcpy(s_cpy, s);
newh->next = NULL;
newh->value = s_cpy;
/* 因為是加入在 tail，newrec->prev 直接指向原本的 tail */
newh->prev = q->tail;
if (q->head == NULL)
q->head = newh;
if (q->tail != NULL)
q->tail->next = newh;
q->tail = newh;
q->size += 1;
return true;
} else {
if (s_cpy)
free(s_cpy);
if (newh)
free(newh);
return false;
}
}
}
```
參考 qtest.c 的 show_queue，加入 show_queue_reverse，從 tail 開始，透過 prev 指標走訪至開頭，顯示的結果應與 show_queue 結果相反，以此測試是否成功改為 doubly linked list
```C
static bool show_queue_reverse(int vlevel)
{
bool ok = true;
if (verblevel < vlevel)
return true;
int cnt = 0;
if (q == NULL) {
report(vlevel, "q = NULL");
return true;
}
report_noreturn(vlevel, "reverse_q = [");
// 從 tail 開始走訪
list_ele_t *e = q->tail;
if (exception_setup(true)) {
while (ok && e && cnt < qcnt) {
// 走訪次數由 queue_size 決定
if (cnt < big_queue_size)
report_noreturn(vlevel, cnt == 0 ? "%s" : " %s",
// 每次替換為前一個節點
e = e->prev;
cnt++;
ok = ok && !error_check();
}
}
exception_cancel();
if (!ok) {
report(vlevel, " ... ]");
return false;
}
/*
走訪完 queue_size 後，e 正常情況為 head，而 head 的 prev 為 NULL，
若 head->prev 不為 NULL 表示: 1. queue_size 有錯
2. queue 為 circular
*/
if (e == NULL) {
if (cnt <= big_queue_size)
report(vlevel, "]");
else
report(vlevel, " ... ]");
} else {
```
測試 doubly linked list 是否建立成功
```shell
$ make && ./qtest
gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o
cmd>new
cmd>new
q = []
reverse_q = []
cmd>ih a
cmd>ih a
q = [a]
reverse_q = [a]
cmd>ih b
cmd>ih b
q = [b a]
reverse_q = [a b]
cmd>ih c
cmd>ih c
q = [c b a]
reverse_q = [a b c]
cmd>it t
cmd>it t
q = [c b a t]
reverse_q = [t a b c]
cmd>
```
輸入結果符合預期，接著以 make test 檢查是否影響原本的程式
```shell
$ make test
...略...
--- trace-15-perf 7/7
--- TOTAL 100/100
```
沒有影響原先程式，記憶體空間也有正確配置、釋放，截至目前為止修改為 doubly linked list 成功。
Sign in with Wallet
Connect another wallet