# 2022q1 Homework1 (lab0)
contributed by < [`0n3t04ll`](https://github.com/0n3t04ll) >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 36 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 58
Model name: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
Stepping: 9
CPU MHz: 1300.000
CPU max MHz: 3100.0000
CPU min MHz: 1200.0000
BogoMIPS: 4988.51
Virtualization: VT-x
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 3 MiB
NUMA node0 CPU(s): 0-3
```
## 針對佇列的操作
依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
我的思路是先盡可能的利用 `list.h` 內的各個 function/macro 完成 list node 操作，避免自己進行手動操作，滿足評分系統後再對各項操作進行最佳化。
### q_new
> Create empty queue.
> Return NULL if could not allocate space.
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (head == NULL)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
這個實作困擾我最久的是不知道該不該新增一個用不到的 element 然後拿裡面 list 當作 head ，但看了 `list.h` 中的細節和回想起之前寫 leetcode linked list 相關題目提到的[虛擬頭節點](https://cloud.tencent.com/developer/article/1680952)，我決定用一個 `struct list_head *head` 當作 head node 就好。
### q_free
> Free all storage used by queue
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
struct list_head *node;
struct list_head *safe;
list_for_each_safe (node, safe, l) {
list_del(node);
element_t *ele = list_entry(node, element_t, list);
free(ele->value);
free(ele);
}
if (list_empty(node))
free(node);
}
```
利用 `list_for_each_safe` 走訪每個 node ，並利用 `list_entry` 拿到保存 node 的 element ，移除後 free 掉 element 所有分配的空間
### q_insert_node
>
> Attempt to insert element at head of queue.
> Return true if successful.
> Return false if q is NULL or could not allocate space.
> Argument s points to the string to be stored.
> The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *ele = (element_t *) malloc(sizeof(element_t));
if (ele == NULL)
return false;
ele->value = strdup(s);
if (ele->value == NULL) {
free(ele);
return false;
}
struct list_head *new_node = &(ele->list);
list_add(new_node, head);
// cppcheck-suppress memleak
return true;
}
```
新增節點的部分我直接分配一個 `element_t` 的變數 `ele`， `ele` 的 value 則直接用 `strdup(const char *)` 分配空間並保存 `s` 內容。
這邊讓我最為疑惑的是 cppcheck 會出現 `memleak` 錯誤訊息，我猜是因為 cppcheck 檢查時看到 `ele` 被分配出來卻沒檢查出哪裡可以 free 掉的原因，嘗試用 valgrind ，目前是沒發現有 memleak 問題，所以先用 `//cppcheck-suppress memleak` 關掉提醒。
### q_insert_tail
>
>Attempt to insert element at tail of queue.
>Return true if successful.
>Return false if q is NULL or could not allocate space.
>Argument s points to the string to be stored.
>The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *ele = (element_t *) malloc(sizeof(element_t));
if (ele == NULL)
return false;
ele->value = strdup(s);
if (ele->value == NULL) {
free(ele);
return false;
}
struct list_head *new_node = &(ele->list);
list_add_tail(new_node, head);
// cppcheck-suppress memleak
return true;
}
```
作法跟 `q_insert_head` 大同小異，差別在於因為要加到 tail ，所以用 `list_add_tail`。
這邊一樣有 memleak 警告問題，一樣用 `//cppcheck-suppress memleak` 解決
### q_remove_head
>Attempt to remove element from head of queue.
Return target element.
Return NULL if queue is NULL or empty.
If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
list_del_init(&(ele->list));
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
用 `list_first_entry` 取出第一個 entry 後根據此 element 進行字串複製和移除等操作。
要注意的是記得補個 terminate byte 在 sp 最後一個 byte 上
### q_remove_tail
>Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
element_t *ele = list_last_entry(head, element_t, list);
list_del_init(&(ele->list));
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
跟 `q_remove_head` 大同小異，差別在於取 first_entry 還是 last_entry 而已。
### q_size
>Return number of elements in queue.
Return 0 if q is NULL or empty
```c
int q_size(struct list_head *head)
{
if (head == NULL || list_empty(head))
return 0;
int size = 0;
struct list_head *node;
list_for_each (node, head)
size++;
return size;
}
```
以 `list_for_each` 走訪不包含 head 在內的所有節點並記錄數量。
### q_delete_mid
>Delete the middle node in list.
The middle node of a linked list of size n is the
⌊n / 2⌋th node from the start using 0-based indexing.
If there're six element, the third member should be return.
Return true if successful.
Return false if list is NULL or empty.
```c
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
struct list_head *two, *one, *end;
two = head->next;
one = two;
end = head->prev;
while (two->next != end && two != end) {
two = two->next->next;
one = one->next;
}
list_del(one);
element_t *ele = list_entry(one, element_t, list);
free(ele->value);
free(ele);
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
return true;
}
```
這題可以透過 two-pointer 技巧解決，概念是一個 pointer 一次走訪兩個，一個 pointer 一次走訪一個，當走訪兩個的走到底了則走訪的一個的位置就會是 middle node 。
查看了 `list.h` ，對於走訪相關的巨集，沒有直接自己手動操作來的方便，所以就直接操作。拿到 middle 後用將其從 list 中移除並 free 掉 ele 。
### q_delete_dup
>Delete all nodes that have duplicate string,
leaving only distinct strings from the original list.
Return true if successful.
Return false if list is NULL.
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (head == NULL)
return false;
if (list_empty(head) || list_is_singular(head) == 1)
return true;
struct list_head *curr = head->next;
element_t *curr_ele = list_entry(curr, element_t, list);
char *last_str = curr_ele->value;
curr = curr->next;
while (curr != head) {
curr_ele = list_entry(curr, element_t, list);
char *curr_str = curr_ele->value;
if (strcmp(curr_str, last_str) == 0) {
struct list_head *tmp = curr;
curr = curr->next;
list_del(tmp);
free(curr_ele->value);
free(curr_ele);
} else {
last_str = curr_str;
curr = curr->next;
}
}
return true;
}
```
因為註解有提到會在 sorted 後執行這個 function ，因此我假設 list 已經被 sorted ，用 `last` 和 `curr` 兩個 prefix 表示當前的 node 和 string 以及上一次的 node 和 string ，判斷一樣將 `curr` 從 list 中移除後 free 掉其空間
### q_swap
>Attempt to swap every two adjacent nodes.
```c
void q_swap(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
// https://leetcode.com/problems/swap-nodes-in-pairs/
struct list_head *fst, *sec;
fst = head->next;
sec = fst->next;
while (sec != head && fst != head) {
list_move(fst, sec);
fst = fst->next;
sec = fst->next;
}
}
```
這個實作就是把第二個 node 用 `list_move` 移動到第一個前面即可
### q_reverse
>Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
```c
void q_reverse(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
struct list_head *last = head->prev;
struct list_head *sec_last = last->prev;
struct list_head *last_tail = last;
while (sec_last != head) {
list_move(sec_last, last_tail);
last_tail = sec_last;
sec_last = last->prev;
}
}
```
這個實作我的想法是把最後一個 node 當 head ，然後把倒數第二個 node 移動到 head 的下一個，最後更新 head 到剛剛移動過來的 node 上，而最後一個 node 則被更新為 `last->prev`
### q_sort
>No effect if q is NULL or empty. In addition, if q has only one
element, do nothing.
原本評估一個沒品味的寫法應該一下子就能完成，之後再去研究怎麼最佳化，結果 commit 的時候直接被告知不能用 `malloc()` ，這個限制讓我想了好一陣子，少了任意增加 head node 對於想徹底利用 `list.h` function 的方式來說無疑會增加實作的複雜度。
[Merge two sorted linked lists](https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/) 一文的作法是利用 local variable 當作 head node ，因為是 local variable 所以可以繞過 malloc 檢查，而上一層的 local variable 當作 pointer 傳遞給下一層的 function 使用也不會出現問題，不過追根究柢本質上還是有 allocate 新的空間出來，並不符合要求。
> 我覺得儘管沒品味寫法的確比較不優雅，但因為都保持有 head node 的 circular doubly-linked list 模式所以多數情況能充分利用 `list.h` 提供的 function/macro 。
#### 沒品味寫法
我主要分為三個 function：
* merge_sort
```c
static void merge_sort(struct list_head *head)
{
if (head == NULL)
return;
else if (list_empty(head))
return;
else if (list_is_singular(head))
return;
struct list_head l, r;
INIT_LIST_HEAD(&l);
INIT_LIST_HEAD(&r);
struct list_head *mid = find_middle(head);
// split
list_cut_position(&l, head, mid);
list_cut_position(&r, head, head->prev);
merge_sort(&l);
merge_sort(&r);
merge(head, &l, &r);
return;
}
```
利用 local variable 當作左右切割後的 list 的 head node ，用 `list_cut_position` 切割原來的 list ，將其分為左右兩邊，左右兩邊的 list 也要繼續遞迴下去，最後用 `merge` 將 l 和 r 兩個 list 作合併並放入 head node 的 list 中
* merge
```c
static void merge(struct list_head *head,
struct list_head *a,
struct list_head *b)
{
struct list_head *curr_a = a->next;
struct list_head *curr_b = b->next;
struct list_head *last_b, *last_a;
while (curr_a != a && curr_b != b) {
if (cmp(curr_a, curr_b)) {
last_a = curr_a;
curr_a = curr_a->next;
list_move_tail(last_a, head);
} else {
last_b = curr_b;
curr_b = curr_b->next;
list_move_tail(last_b, head);
}
}
if (curr_a != a) {
list_splice_tail(a, head);
}
if (curr_b != b) {
list_splice_tail(b, head);
}
}
```
根據 `cmp` 結果，決定放入哪一個 list 的當前 node
* cmp
* 根據 strcmp 的 return 值判斷
#### 有品味寫法
老師的講義上其實就有關於 linked list merge sort 的實作方式，不過作法是基於 singly-linked list ，這次用的 linked list 是更高階的 circular doubly-linked list ，所以可以~~自廢武功降級~~退化成 singly-linked list ，然後套用相關作法，但事後要再補回 prev pointer 和 head node 的連接。
:::warning
這不是「降級」，只是某幾個工程選擇。工程師要解決各式難題，這個作業就是藉由事先給予的限制，讓學員進行練習。
:notes: jserv
:::
* q_sort
```c
void q_sort(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *list = head->next;
head->prev->next = NULL;
merge_sort(&list);
// recovery
struct list_head *curr = list->next;
struct list_head *last = list;
last->prev = head;
head->next = last;
while (curr) {
curr->prev = last;
curr = curr->next;
last = last->next;
}
last->next = head;
head->prev = last;
}
```
q_sort 負責初始的降級成 singly-linked list 和最後的恢復動作，其餘交給 merge_sort 負責。
* merge_sort
```c
void merge_sort(struct list_head **list)
{
*list = merge_sort_list(*list);
}
```
merge_sort 本身所傳參數 list 是負責保存最後 sorted list 的第一個 node 地址。
因為要讓傳入參數保持第一個 entry node 的定位，所以用 indirect pointer ，這樣透過 `*list` 就可以將新的 entry node address 保存在 q_sort 的 `list` 內，如此 q_sort 的 `list` 在 sort 前是 first entry node ，在 sort 後依然是 first entry node 。
* merge_sort_list
```c
struct list_head *merge_sort_list(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast, *slow;
slow = head;
fast = slow->next;
for (; fast && fast->next; fast = fast->next->next) {
slow = slow->next;
}
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *l = merge_sort_list(head), *r = merge_sort_list(mid);
return merge(l, r);
}
```
merge_sort_list 每次切割成左右兩個 list 都會需要對 list 進行 singly link list 相關處理，最後將被排序過後的兩個 list 放到 merge 合併。
* merge
```c
struct list_head *merge(struct list_head *l, struct list_head *r)
{
struct list_head *head = NULL;
struct list_head **ptr = &head;
for (; l && r; ptr = &(*ptr)->next) {
element_t *ele_l = list_entry(l, element_t, list);
element_t *ele_r = list_entry(r, element_t, list);
if (strcmp(ele_l->value, ele_r->value) <= 0) {
*ptr = l;
l = l->next;
} else {
*ptr = r;
r = r->next;
}
}
if (l)
*ptr = l;
if (r)
*ptr = r;
return head;
}
```
第一種寫法就像是在兩個 list 之外再用第三個 list 保存前兩個 list 的結果，如果利用上面的 indirect pointer 技巧相當於將兩個 list 根據需求取其中的 node 串連在一起，無須第三的 list 保存。
> 雖然 code 看得懂，但是對於 indirect pointer 的使用還沒到很熟悉，無法順暢想到寫出來。
:::warning
TODO：
* 合併最佳化
* 效能評估
* 圖形化顯示
:::
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
手動的部分在實作 queue operation 的時候就因為 cppcheck 的誤報而用 valgrind 檢測過，沒發現問題。
實作完成後自己添加了一些測試 .cmd 檔案給 `./qtest` 執行並用 `valgrind` 做 mem-leak check:
`$ valgrind --leak-check=full ./qtest -f ./cmd2`
出現如下錯誤訊息：
```
starpt@ubuntu:~/lab0-c$ valgrind --leak-check=full ./qtest -f cmd2
cmd> new
l = []
cmd> ih 1
l = [1]
cmd> quit
Freeing queue
==120066== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==120066== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==120066== by 0x4A5750E: strdup (strdup.c:42)
==120066== by 0x1108ED: linenoiseHistoryAdd (linenoise.c:1236)
==120066== by 0x111480: linenoiseHistoryLoad (linenoise.c:1325)
==120066== by 0x10C6B0: main (qtest.c:951)
==120066==
==120066== 88 bytes in 19 blocks are still reachable in loss record 2 of 3
==120066== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==120066== by 0x4A5750E: strdup (strdup.c:42)
==120066== by 0x110861: linenoiseHistoryAdd (linenoise.c:1236)
==120066== by 0x111480: linenoiseHistoryLoad (linenoise.c:1325)
==120066== by 0x10C6B0: main (qtest.c:951)
==120066==
==120066== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==120066== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==120066== by 0x1108AD: linenoiseHistoryAdd (linenoise.c:1224)
==120066== by 0x111480: linenoiseHistoryLoad (linenoise.c:1325)
==120066== by 0x10C6B0: main (qtest.c:951)
==120066==
```
原先以為是我的 code 寫錯了，所以一直修改 cmd2 ，想藉此查出是哪個操作寫錯，但用手動執行同樣的操作卻沒任何問題，透過 `valgrind` 提供的 backtrace 也可以看出問題不是出在我寫的 function 內，而是在 `linenoiseHistoryAdd`。
為了方便 trace code ，我根據 [[Linux] - 將vim打造成source insight](https://ivan7645.github.io/2016/07/12/vim_to_si/) 這篇文章安裝了 `cscope` 和 `ctags` 幫助我 debug 。
### Tracing
從上而下追蹤下去可以發現：
* main
```c
#define BUFSIZE 256
int main(int argc, char *argv[])
{
/* ... ignore ... */
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
`main` 會執行 history 相關初始化
* linenoiseHistoryLoad
```c
int linenoiseHistoryLoad(const char *filename)
{
FILE *fp = fopen(filename, "r");
char buf[LINENOISE_MAX_LINE];
if (fp == NULL)
return -1;
while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
char *p;
p = strchr(buf, '\r');
if (!p)
p = strchr(buf, '\n');
if (p)
*p = '\0';
linenoiseHistoryAdd(buf);
}
fclose(fp);
return 0;
}
```
`linenoiseHistoryLoad` 負責讀取 `filename` 的每一行並用 terminate byte 截斷再將處理過的字串放到 `linenoiseHistoryAdd`
* linenoiseHistoryAdd
```c
int linenoiseHistoryAdd(const char *line)
{
/* ...history initial...*/
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
/* ...linecopy check...*/
history[history_len] = linecopy;
history_len++;
return 1;
}
```
`linenoiseHistoryAdd` 會分配一個字元指標陣列 `char *[]` 給全域的 `history` 變數保存傳進來的，參數 `line` 透過 `strdup` 自動分配 heap 空間保存 `line` 字串，而後放入 `history` 陣列中，這也符合 `valgrind` backtrace 上面提示的位置。
### 手動操作的差異
我接著想到 `linenoiseHistoryLoad` 無論讀檔或標準輸入都會執行，所以標準輸入應該也有這個字元指標陣列，那為何不會出現 memleak ？
我的方法是用 [ag](https://github.com/ggreer/the_silver_searcher) 直接搜尋 `free(history[` ，從中發現了:
```
linenoise.c
786: free(history[history_len - 1 - l->history_index]);
910: free(history[history_len]);
935: free(history[history_len]);
1196: free(history[j]);
1240: free(history[0]);
1271: free(history[j]);
```
逐一對每一行進行 code review ，其中 `linenoise.c:1196` 是以下的程式碼：
```c
static void freeHistory(void)
{
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]); // line: 1196
free(history);
}
}
```
這邊應該就是負責結束的時候釋放掉 `history` 內所保存的字串和 `history` ，接著就是找是誰負責呼叫這個 function ，可以發現 `freeHistory` 在 `linenoiseAtExit` 中被呼叫，而 `linenoiseAtExit` 則是在 `enableRawMode` 中被當成參數傳給 `atexit` 。
### 產生 call graph 方便比較、查看
#### kcachegrind
根據 [Tools to get a pictorial function call graph of code [closed]](https://stackoverflow.com/questions/517589/tools-to-get-a-pictorial-function-call-graph-of-code) 這篇 stackoverflow 選用 `valgrind` + `kcachegrind` 組合輸出並查看 call graph:
`$ valgrind --tool=callgrind ./qtest`
這樣會輸出 `callgrind.out.[pid]` 的檔案，再用 `kcachegrind` 開啟：
`$ kcachegrind ./callgrind.out.[pid]`
根據需求選擇想要看的 function 後可以輸出 dot graph
這樣就會有 call graph 可以查看：
```graphviz
digraph "callgraph" {
F55a4db090870 [label="linenoise\n1 122"];
F55a4db297f90 [label="run_console\n1 122"];
F55a4db7d5710 [label="enableRawMode\n1 122"];
F55a4db7d5d10 [label="0x000000000010a520\n275"];
F55a4db7d64b0 [label="0x000000000010a790\n200"];
F55a4db7d68a0 [label="0x000000000010a7a0\n330"];
F55a4db7d6c90 [label="atexit\n78"];
F55a4db7df560 [label="0x000000000010a800\n74"];
F55a4db8152b0 [label="__cxa_atexit\n72"];
F55a4db819f90 [label="tcgetattr\n378"];
F55a4db81b6e0 [label="isatty\n265"];
F55a4db8371c0 [label="tcsetattr\n320"];
F55a4db090870 -> F55a4db7d5710 [weight=1,label="1 122 (5x)"];
F55a4db297f90 -> F55a4db090870 [weight=1,label="1 122 (1x)"];
F55a4db7d5710 -> F55a4db7d5d10 [weight=1,label="275 (5x)"];
F55a4db7d5710 -> F55a4db7d64b0 [weight=1,label="200 (5x)"];
F55a4db7d5710 -> F55a4db7d68a0 [weight=1,label="330 (5x)"];
F55a4db7d5710 -> F55a4db7d6c90 [weight=1,label="78 (1x)"];
F55a4db7d5d10 -> F55a4db81b6e0 [weight=1,label="265 (5x)"];
F55a4db7d64b0 -> F55a4db819f90 [weight=1,label="190 (5x)"];
F55a4db7d68a0 -> F55a4db8371c0 [weight=1,label="320 (5x)"];
F55a4db7d6c90 -> F55a4db7df560 [weight=1,label="74 (1x)"];
F55a4db7df560 -> F55a4db8152b0 [weight=1,label="72 (1x)"];
F55a4db81b6e0 -> F55a4db819f90 [weight=1,label="188 (5x)"];
}
```
>友情提示： kcachegrind 容量不小，要 193MB
#### gprof2dot
亦或者透過 `gprof2dot` 這個 python module 也可以根據 valgrind 產生的 `callgrind` 檔案輸出 dotgraph ：
`$ gprof2dot -e0 -n0 -f callgrind callgrind.out.120351 -z main -l enableRawMode`
說明：
* `-e0 -n0`：解除顯示限制，完整呈現所有調用鏈
* `-f callgrind` ：說明檔案是經過 `callgrind` 產稱
* `-z main -l enableRawMode`：設定 root 為 `main`，leaf 為 `enableRawMode`
簡單介紹可以參考 [動態分析 C 程序函數調用關係](https://www.cntofu.com/book/46/tinyclub/dong_tai_fen_xi_c_cheng_xu_han_shu_diao_yong_guan_.md)。
```graphviz
digraph {
graph [fontname=Arial, nodesep=0.125, ranksep=0.25];
node [fontcolor=white, fontname=Arial, height=0, shape=box, style=filled, width=0];
edge [fontname=Arial];
enableRawMode [color="#0d0e73", fontcolor="#ffffff", fontsize="10.00", label="qtest\nenableRawMode\n0.28%\n(0.06%)\n5×"];
linenoise [color="#0d1976", fontcolor="#ffffff", fontsize="10.00", label="qtest\nlinenoise\n2.93%\n(0.31%)\n6×"];
linenoise -> enableRawMode [arrowsize="0.35", color="#0d0e73", fontcolor="#0d0e73", fontsize="10.00", label="0.28%\n5×", labeldistance="0.50", penwidth="0.50"];
main [color="#13b809", fontcolor="#ffffff", fontsize="10.00", label="qtest\nmain\n51.39%\n(0.04%)\n1×"];
main -> "run_console" [arrowsize="0.50", color="#0c9393", fontcolor="#0c9393", fontsize="10.00", label="24.89%\n1×", labeldistance="1.00", penwidth="1.00"];
"run_console" [color="#0c9393", fontcolor="#ffffff", fontsize="10.00", label="qtest\nrun_console\n24.89%\n(0.02%)\n1×"];
"run_console" -> linenoise [arrowsize="0.35", color="#0d1976", fontcolor="#0d1976", fontsize="10.00", label="2.93%\n6×", labeldistance="0.50", penwidth="0.50"];
}
```
:exclamation: 不可以拿 `linenoiseAtExit` 當作參考搜尋 call graph ，因為 `linenoiseAtExit` 是當作參數傳入 `atexit` ，只會在 `exit` 的時候呼叫。
接著根據 call graph 分析 `run_console`:
```c=
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
line 10 的 `linenoise` 內部就會調用 `enableRawMode` 然後設定 `atexit(linenoiseAtExit)`
根據 code 可以得出 `infile_name` 為空則進入 `linenoise` 。
最後就是回到 `main` 找出 `infile_name` 為空的關鍵是**有無透過 `-f` 設定讀取的檔案**。
### 整理
簡單整理下：
* 沒有 `-f`：會設定清空 `history` 字元指標陣列，操作過程也會一直修改 `history` 陣列的內容，調用 `exit` 的時候會正常清空 `history`
* 有 `-f`：只會在剛開始初始化的時候用到，之後不會用到
因此我覺得把在 `main` 裡面的初始化 function ：`linenoiseHistorySetMaxLen` 、 `linenoiseHistoryLoad` 放到 `run_console` 處理沒有 `-f` 的 case 中應該比較恰當，也只有他會用到這些 history 。
### diff
```diff=
diff --git a/console.c b/console.c
index 6ad338a..e8e555b 100644
--- a/console.c
+++ b/console.c
@@ -17,6 +17,10 @@
#include "report.h"
+/* Settable parameters */
+
+#define HISTORY_LEN 20
+
/* Some global values */
int simulation = 0;
static cmd_ptr cmd_list = NULL;
@@ -644,6 +648,8 @@ bool run_console(char *infile_name)
}
if (!has_infile) {
+ linenoiseHistorySetMaxLen(HISTORY_LEN);
+ linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
diff --git a/qtest.c b/qtest.c
index dd40972..3845b55 100644
--- a/qtest.c
+++ b/qtest.c
@@ -947,8 +947,6 @@ int main(int argc, char *argv[])
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
- linenoiseHistorySetMaxLen(HISTORY_LEN);
- linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
set_verblevel(level);
if (level > 1) {
set_echo(true);
```
### 成果
```
starpt@ubuntu:~/lab0-c$ valgrind --leak-check=full ./qtest -f ./cmd2
cmd> new
l = []
cmd> ih 1
l = [1]
cmd> quit
Freeing queue
```
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
重新查看作業要求，發現少看了這一條。
在完成 queue operation 的前提下，我嘗試修改 `Makefile` 中的 `CFLAGS` ，試圖加上 `-fsanitize=address`
結果會出現：
```shell
/usr/bin/ld: linenoise.o: in function `_sub_D_00099_0':
/home/starpt/lab0-c/linenoise.c:1329: undefined reference to `__asan_unregister_globals'
/usr/bin/ld: linenoise.o: in function `_sub_I_00099_1':
/home/starpt/lab0-c/linenoise.c:1329: undefined reference to `__asan_init'
/usr/bin/ld: /home/starpt/lab0-c/linenoise.c:1329: undefined reference to `__asan_version_mismatch_check_v8'
/usr/bin/ld: /home/starpt/lab0-c/linenoise.c:1329: undefined reference to `__asan_register_globals'
collect2: error: ld returned 1 exit status
make: *** [Makefile:45: qtest] Error 1
```
因為錯誤太多，我只節錄一小段。
根據 [How to use AddressSanitizer with GCC?](https://stackoverflow.com/questions/37970758/how-to-use-addresssanitizer-with-gcc) ，不只 `CFLAGS` 要加，連 `LD_FLAGS` 也要加，不過在尋找的 `LD_FLAGS` 的時候發現：
```
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
```
其實只要用以下方式就可以開啟 sanitizer ：
```shell=
$ make SANITIZER=1
```
不過就算我退回到完成 queue operation 的 commit ，按照指示執行 `./qtest` 後輸入 `help` 還是沒觸發 sanitizer ，於是暫時擱置。
##
## 在 qtest 提供新的命令 shuffle
> 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
看了 README.md 沒找到如何新增新命令的說明，於是從現有的命令實作去推敲。
根據執行 `./qtest` 顯示的字串可以在 qtest.c 找到 `console_init` ：
```c
static void console_init()
{
ADD_COMMAND(new, " | Create new queue");
ADD_COMMAND(free, " | Delete queue");
ADD_COMMAND(
ih,
" str [n] | Insert string str at head of queue n times. "
"Generate random string(s) if str equals RAND. (default: n == 1)");
ADD_COMMAND(
it,
" str [n] | Insert string str at tail of queue n times. "
"Generate random string(s) if str equals RAND. (default: n == 1)");
ADD_COMMAND(
rh,
" [str] | Remove from head of queue. Optionally compare "
"to expected value str");
/* ... ignore other lines ...*/
```
根據格式可以新增命令 `shuffle` 如下：
```c
ADD_COMMAND(shuffle, " | Shuffle all the queue nodes");
```
`ADD_COMMAND` macro 會把 `shuffle` 加工，實際處理完的 function 名稱會是 `do_shuffle` 。
`do_shuffle` 則仿造其他 function ：
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Try to access null queue");
error_check();
if (l_meta.size == 1)
return true;
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
`l_meta` 是負責保存 queue 和 size 的結構，可以看成 queue 的包裝， `do_shuffle` 實際核心 function 是 `q_shuffle`。
我本來想在 `queue.c` 和 `queue.h` 裡面加上 `q_shuffle` ，但是 commit 時被警告不準修改 `queue.h` ，只好直接加在 `qtest.h` 內。
`q_shuffle` 主要由 `swap_ele_value` 和 `q_shuffle` 組成。
* `swap_ele_value`
直接交換兩個 node 的 value 比較方便
```c
static void swap_ele_value(struct list_head *a, struct list_head *b)
{
if (a == b)
return;
element_t *ele_a = list_entry(a, element_t, list);
element_t *ele_b = list_entry(b, element_t, list);
char *tmp = ele_a->value;
ele_a->value = ele_b->value;
ele_b->value = tmp;
}
```
* `q_shuffle`
shuffle 本體，從 `/dev/urandom` 取值當作隨機數種子，拿不到再考慮用時間。
```c
static void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
if (list_is_singular(head))
return;
// set random seed
int fd = open("/dev/urandom", O_RDONLY, 0);
if (fd < 0)
return;
int seed;
ssize_t nb = read(fd, &seed, sizeof(int));
if (nb < 0)
srand(time(NULL));
else
srand(seed);
close(fd);
struct list_head *last = head->prev;
struct list_head *chose = head->next;
int size = q_size(head);
while (size) {
int rand_idx = rand() % size;
if (rand_idx != size - 1) {
for (int i = 0; i < rand_idx; i++) {
chose = chose->next;
}
swap_ele_value(chose, last);
}
size--;
chose = head->next;
last = last->prev;
}
}
```
## 在 qtest 提供新的命令 web
Sign in with Wallet
Connect another wallet