# 2021q1 Homework1 (lab0)
contributed by < `mingyen066` >
## Checklist
* [x] q_new
* [x] q_free
* [x] q_insert_head
* [x] q_insert_tail
* [x] q_remove_head
* [x] q_reverse
* [x] q_sort
* [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
* [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
* [ ] 在 qtest 中實作 coroutine，並提供新的命令 web，提供 web 伺服器功能
* [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。
* [ ] 說明 antirez/linenoise 的運作原理，注意到 termios 的運用
* [ ] 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。
* [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request
# 安裝說明
因為去年有 fork 過 lab0 這個專案，但是原本專案內容有更新，
所以去查詢了如何使用 upstream 來更新 fork 的專案的方法
:::warning
更正：不要用 upstream 來 merge，該重新 fork 或用 rebase
:::
先進入到專案目錄底下，列出目前有的 stream
```bash=
$ git remote -v
origin https://github.com/mingyen066/lab0-c.git (fetch)
origin https://github.com/mingyen066/lab0-c.git (push)
```
再加入想要 Sync 的專案網址
```bash=
$ git remote add upstream https://github.com/sysprog21/lab0-c
```
確認已經加入完成
```bash=
$ git remote -v
origin https://github.com/mingyen066/lab0-c.git (fetch)
origin https://github.com/mingyen066/lab0-c.git (push)
upstream https://github.com/sysprog21/lab0-c (fetch)
upstream https://github.com/sysprog21/lab0-c (push)
```
再進行 fetch, fetch 下來的 code 會儲存在 upstream/`<branchname>`
```bash=
$ git fetch upstream
remote: Enumerating objects: 10, done.
remote: Counting objects: 100% (10/10), done.
remote: Total 17 (delta 10), reused 10 (delta 10), pack-reused 7
Unpacking objects: 100% (17/17), 4.44 KiB | 84.00 KiB/s, done.
From https://github.com/sysprog21/lab0-c
* [new branch] master -> upstream/master
```
再 merge 到自己的專案
```bash=
$ git merge upstream/master
Updating 959d72e..81079de
Fast-forward
.gitignore | 1 +
qtest.c | 12 ++++++++++--
scripts/commit-msg.hook | 3 +++
scripts/pre-commit.hook | 2 +-
4 files changed, 15 insertions(+), 3 deletions(-)
```
:::danger
不該用 merge，改用 git rebase 或者重建 repository
:notes: jserv
:::
:::info
已重建 repository
:::
## 實作說明
考慮到程式碼簡潔性，把所有下列類似程式碼
```c=
if (q == NULL)
if (q != NULL)
```
改成
```c=
if (q)
if (!q)
```
### queue.h
`struct list_ele_t` 維持不變
在 `struct queue_t` 中則加入指標 `tail` 以及整數`q_size`，以便達到 `insert_tail` 在時間複雜度 O(1) 完成的要求
```c=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int q_size;
} queue_t;
```
### queue.c
### q_new
需注意判斷 `malloc（）` 是否回傳NULL
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->q_size = 0;
q->tail = NULL;
q->head = NULL;
return q;
}
```
### q_free
當有節點不為空時，我們必須先釋放節點的 value ，再釋放節點，我原本擔心萬一節點的值是 NULL 怎麼辦，所以我查了 free() 的man page ， 根據free() 的 man page：
> The free() function frees the memory space pointed to by ptr ...
> If ptr is NULL, no operation is performed.
所以我們可以不用擔心 free 到 NULL pointer
```c=
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
### q_insert_head
如果 malloc 節點成功，但是 malloc 節點的 value 失敗，必須把節點的記憶體釋放掉。
另外要注意在 malloc 跟 strncpy 時，都要把 C 字串最後的 null charactor('\0') 考慮進去，因為 strlen() 並沒有算到 null charactor
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
q->q_size++;
newh->next = q->head;
q->head = newh;
if (q->q_size == 1) {
q->tail = q->head;
}
return true;
}
```
### q_insert_tail
跟 insert_head 要注意的地方相同，另外要考慮當 queue 為空時的特殊情況
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc(strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (!q->tail) {
q->tail = newt;
q->head = newt;
} else {
q->tail->next = newt;
q->tail = q->tail->next;
}
q->q_size++;
return true;
}
```
### q_remove_head
根據 strncpy 的 mag page:
> The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
了解當要移除字串的前 bufsize 長度裡，如果沒有 null byte，則 copy 到 sp 上也會沒有null byte，所以當要移除的字串長度 (strlen) 跟 bufsize 比，相同或較長時，必須在sp的結果加上 null charactor (`'\0'`)
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
if (strlen(q->head->value) >= bufsize)
sp[bufsize - 1] = '\0';
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
q->q_size--;
free(tmp->value);
free(tmp);
return true;
}
```
### q_reverse
這裡我用 \*prev 表示要反轉節點的前一個節點， \*next表示要移除節點的下個節點，
前一個節點跟目前節點已經斷開連結，換而言之，包含 prev 以前的串列是已經反轉過的。
圖例如下:
Linked List 結構為a->b->c，prev 指向 NULL， head 指向將要反轉的串列開頭
```graphviz
digraph {
rankdir=LR;
size=4;
node [shape=record]
subgraph pointer{
a [label = "{<in>NULL |<out>}"]
b [label = "{<in>a |<out>}"]
c [label = "{<in>b |<out>}"]
d [label = "{<in>c |<out>}"]
}
subgraph nodes{
label="pointer"
prev [label = "prev", shape=circle]
head [label = "head", shape=circle]
}
prev->a
b->c
c->d
head->b
}
```
接著把 next 指向 head 的下個節點 b，並把 a 的 next 改為 prev 所指的節點 NULL
```graphviz
digraph {
rankdir=LR;
size=4;
node [shape=record]
subgraph pointer{
a [label = "{<in>NULL |<out>}"]
b [label = "{<in>a |<out>}"]
c [label = "{<in>b |<out>}"]
d [label = "{<in>c |<out>}"]
}
subgraph nodes{
label="pointer"
prev [label = "prev", shape=circle]
head [label = "head", shape=circle]
next [label = "next", shape=circle]
}
prev->a
b->a
head->b
next->c
c->d
}
```
接著把 prev 指標改指到 head 所指節點 a，把 head 改指到 next 所指節點 b，這時 prev 指向已經反轉的串列開頭，head 指向將要反轉的串列，因此可繼續進行下一個迴圈，直到最後一個迴圈結束，head 會指向 NULL，而 prev 指向已經反轉完成的串列開頭
```graphviz
digraph {
rankdir=LR;
size=4;
node [shape=record]
subgraph pointer{
a [label = "{<in>NULL |<out>}"]
b [label = "{<in>a |<out>}"]
c [label = "{<in>b |<out>}"]
d [label = "{<in>c |<out>}"]
}
subgraph nodes{
label="pointer"
prev [label = "prev", shape=circle]
head [label = "head", shape=circle]
}
prev->b
b->a
head->c
c->d
}
```
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head) {
return;
}
list_ele_t *prev = NULL, *next;
q->tail = q->head;
while (q->head) {
next = q->head->next;
q->head->next = prev;
prev = q->head;
q->head = next;
}
q->head = prev;
}
```
### q_sort
[Reference](https://www.techiedelight.com/merge-sort-singly-linked-list/)
使用 Merge Sort，主程式說明如下：
使用完 mergeSort 之後，需要額外從頭到尾掃描一遍，來找出並維護 tail 指標
```c=
void q_sort(queue_t *q)
{
if (!q || !q->head)
return;
mergeSort(&(q->head));
list_ele_t *cur = q->head;
while (cur->next)
cur = cur->next;
q->tail = cur;
}
```
跟一般的mergeSort想法一樣，我們使用 frontBackSplit() 來找出鍊節串列的中點，
對左右各半的鍊節串列分別再做mergeSort，最後使用sortedMerge()合併兩個已排序好的練節串列
```c=
void mergeSort(list_ele_t **head)
{
if (!(*head) || !(*head)->next)
return;
list_ele_t *front, *back;
frontBackSplit(*head, &front, &back);
mergeSort(&front);
mergeSort(&back);
(*head) = sortedMerge(front, back);
}
```
frontBackSplit說明如下：
slow指標從頭開始一次走一步，fast指標則一次走兩步，當fast指標走到串列最尾端時，slow指標剛好走了串列一半的節點，slow->next也就是後半串列的開頭
```c
void frontBackSplit(list_ele_t *head, list_ele_t **front, list_ele_t **back)
{
list_ele_t *slow = head;
list_ele_t *fast = head->next;
while (fast) {
fast = fast->next;
if (fast) {
fast = fast->next;
slow = slow->next;
}
}
*front = head;
*back = slow->next;
slow->next = NULL;
}
```
sortedMerge合併兩個排序好的練結串列，這個問題剛好在 [Leetcode](https://leetcode.com/problems/merge-two-sorted-lists/) 上有出現過，我採用的是iterative 方法而不是 Reference 使用的遞迴方法。
比較特別的技巧是我們在串列前頭創建一個dummyHead，這樣就不用特殊處理初始串列為空的情況，當我們比較完任意一個串列時，只要再接上另外一個串列的開頭即可，相比於陣列則需要讀取完所有元素。
```c=
list_ele_t *sortedMerge(list_ele_t *a, list_ele_t *b)
{
list_ele_t dummyHead;
list_ele_t *cur = &dummyHead;
while (a && b) {
if (strcmp(a->value, b->value) <= 0) {
cur->next = a;
a = a->next;
} else {
cur->next = b;
b = b->next;
}
cur = cur->next;
}
cur->next = a? a: b;
return dummyHead.next;
}
```
## Address Sanitizer
在使用 Sanitizer 之後，執行 qtest 並輸入 help，會出現以下錯誤訊息：
```bash=
==6032==ERROR: AddressSanitizer: global-buffer-overflow on address 0x562c450ca400 at pc 0x562c450b390f bp 0x7ffccffa3db0 sp 0x7ffccffa3da0
READ of size 4 at 0x562c450ca400 thread T0
#0 0x562c450b390e in do_help_cmd /home/ming/linux2021/lab0-c/console.c:307
#1 0x562c450b3a22 in interpret_cmda /home/ming/linux2021/lab0-c/console.c:221
#2 0x562c450b4207 in interpret_cmd /home/ming/linux2021/lab0-c/console.c:244
#3 0x562c450b594a in run_console /home/ming/linux2021/lab0-c/console.c:660
#4 0x562c450b2531 in main /home/ming/linux2021/lab0-c/qtest.c:788
#5 0x7f47214880b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x562c450afb8d in _start (/home/ming/linux2021/lab0-c/qtest+0x8b8d)
0x562c450ca401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x562c450ca400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ming/linux2021/lab0-c/console.c:307 in do_help_cmd
```
但目前還不知道如何判讀錯誤訊息並排解錯誤
Sign in with Wallet
Connect another wallet