# 2020q1 Homework1 (lab0)
contributed by < [mtbehisseste](https://github.com/mtbehisseste) >
###### tags: `linux2020`
作業說明 : [lab0-c](https://hackmd.io/@sysprog/linux2020-lab0)
## Environment
Docker for Mac
```shell
$ uname -a
Linux ubuntu18-docker 4.9.125-linuxkit #1 SMP Fri Sep 7 08:20:28 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
```
## Prework study
### Git Hooks
git hook 是一些在特定 git 操作時會執行的腳本，對於開發中的一些規範或風格都可以透過 git hook 來達到自動化檢查。當執行 `git init` 時，在 `.git/hooks` 底下會生成一些範例腳本（ `*.sample` ）。若要使用客製化腳本的話，則將檔案放在 `.git/hooks` 下即可（檔案須為 executable）。本專案則是用 link 的方式將檔案連到統一放置的 `scripts/` 目錄下的執行檔。
觀察一下腳本內容： `commit-msg.hook` 檢查 commit message 是否符合裡面的 9 個規則，包括使用祈使語氣、句尾不加句號等等。 `pre-commit.hook` 使用 `cppcheck` 、 `aspell` 、 `clang-format` 等工具做檢查，也過濾 unsafe function 的使用。另外
```bash
FILES=`git diff --cached --name-only --diff-filter=ACMR | grep -E "\.(c|cpp|h)$"`
```
的用法可以只檢查現階段還沒被 commit 的那些 c/cpp/h 檔，有 cache 的效果。
`pre-push.hook` 會先確認是不是從 sysprog21/lab0-c 某次 commit 之後才 fork 的。而如果要 push 到 master 的話會先做一次 `make` 確保遠端的程式碼是可以成功編譯的。
### scripts/driver.py
自動化將 trace 輸入到 `qtest` 的腳本，裡面使用 `subprocess.call()` 來執行 `qtest` 的指令。因為平時我多用 `os.system()` 所以我順手搜尋了兩者的比較：
- `os.system()` 會產生一個 subshell 來執行指令，底層實作是呼叫 C 的 `system()` ，所有產生的結果會在 stdout 輸出
- 而 `subprocess.call()` （Python 3.5 後可用 `subprocess.run()` 代替）除了在給定參數 `shell=True` 之外，不會產生新的 shell 。另外也有 `capture_output` 等參數可以選擇，功能也比 `os.system()` 多
*Reference: https://docs.python.org/3/library/subprocess.html#subprocess.run*
另外這邊使用 `getopt()` 來解析命令列參數，與我平時使用的 `argparse()` 不同，使用方法與 C 語言中相同：
```cpp
getopt(args, shortopts, longopts = []);
```
- `args` 是待解析的參數 list，通常傳入 `sys.argv[1:]`
- `shortopts` 是一串待辨認的字母選項，若字母後有冒號表示該選項後面需接上參數。如 `hp:t:`， `h` 後不需接東西， `p` 及 `t` 則要
- `longopts` 為支援的選項名字，以 list 表示。如 `['valgrind']` 代表可以用 `./driver.py --valgrind` 。若 `longopts` 須帶參數，則在字串後加上等號
最後回傳一個 (option, value) pair 的 list 以及剩餘的 args。
### clang-format
過去在寫程式的時候一直希望自己能夠保持一致的程式風格，但卻都沒有參閱 [Google C++ Style Guide](https://google.github.io/styleguide/cppguide.html) 這類大型專案所採取的風格規範，導致自己可能會憑"感覺"去寫，像下面這樣的情況就會發生:
```cpp
for (i = 0; i < 10; i++) // 正確
for (i=0; i<10; i++) // 自己覺得太長就把空格省略了
```
使用 `clang-format` 讓一些沒注意到的地方可以自動改成符合風格的，且在 `sysprog21/lab0-c` 最近的 [commit](https://github.com/sysprog21/lab0-c/commit/affbb8013a4db8fb8d66d80113dc2e207e02b296) 提到，可以將 `clang-format` 與 vim 整合，對於往後程式開發更加便利。
### Valgrind
### Address Sanitizer
## Implementation
queue 結構包含兩指標 `head`、 `tail` 及一整數 `size`， `tail` 為方便實作 `q_insert_tail` 及 `q_reverse` 等； `size` 為使 `q_size` 複雜度為 $O(1)$ ：
```cpp
typedef struct {
list_ele_t *head; /* Head of linked list of elements */
list_ele_t *tail; /* Tail of linked list of elements */
int size;
} queue_t;
```
### q_new
初始化 queue，首先宣告一 `queue_t` 結構的指標 `q` 指向一塊記憶體區塊，其大小為 `queue_t` 結構的大小；並分別初始化 `queue_t` 中每個成員。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
將傳入的指標 `q` 所指向的記憶體釋放，不斷呼叫 `q_remove_head` 直到其回傳 `false`（當 `q` 為空或 NULL），並 `free(q)` 。
在 [ISO/IEC 9899](http://www.open-std.org/JTC1/SC22/wg14/www/docs/n1124.pdf) 7.20.3.2 中提到：
> The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs.
因此在 `free(q)` 前我們不必費心考慮 `q` 為空或 NULL。
```cpp
void q_free(queue_t *q)
{
/* Free head element until there's no element left,
* since q_remove_head() return false when q is NULL or empty */
while (q_remove_head(q, NULL, 0))
;
free(q);
}
```
### q_insert_head
產生一新 element `newh`，將給定的字串複製到 `newh` 中的 `value` 成員並將 `newh` 接在 `q` 的頭。若 `q` 為 NULL 或無法配置記憶體則回傳 false，成功回傳 true 。
首先要 malloc 一塊 `list_ele_t` 結構大小的記憶體並由 `newh` 指向，接著 malloc 一塊大小為 `(strlen(s) + 1) * sizeof(char)` 的記憶體，由於 `char` 為 1 byte，可以直接用 `s` 的長度來知道所需記憶體大小。而 `strlen` 只回傳字串本身，並不包含字串後的 terminator，因此要多要 1 byte。這邊要注意的是：若是 malloc 失敗，則必須將剛剛 malloc 的 `newh` 的記憶體也釋放掉，並且將 `newh` 指向 `NULL` ，這是我一開始疏忽掉的。
字串複製我使用 `strncpy`，相較於 `strcpy`，指定複製長度更安全。長度則是 `s` 長度加上 terminator。另外我也有看到其他同學使用 `memcpy` 不過我想既然是字串的處理使用專門處理字串的函式可以讓未來更方便。
最後將 `newh` 擺到 `q` 的頭並增加 `q->size` 即可，要注意的是若 `q` 目前為空，`newh` 將成為 `q` 中唯一元素，則 `q->tail` 也必須指向 `newh`。
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh; /* Add a new head */
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc((strlen(s) + 1) * sizeof(char));
if (!newh->value) {
free(newh); /* Free the allocated space */
newh = NULL;
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
q->head = newh;
if (!q_size(q)) /* The queue is empty */
q->tail = newh;
q->size++;
return true;
}
```
### q_insert_tail
作法與 `q_insert_head` 雷同，當 `q` 為空亦須將 `q->head` 指向 `newt` ，唯最後 `newt->next` 指向 NULL 並成為新的 `q->tail`。
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt; /* Add a new tail */
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc((strlen(s) + 1) * sizeof(char));
if (!newt->value) {
free(newt); /* Free the allocated space */
newt = NULL;
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (!q_size(q)) /* The queue is empty */
q->head = newt; /* This handles inserting to tail when queue is empty */
else
q->tail->next = newt;
q->tail = newt;
q->size++;
return true;
}
```
### q_remove_head
當 `q` 為空或 NULL 則回傳 false，否則新增一指摽 `newh` 指向新的 `q->head` （即 `q->head->next` ）。當 `sp` 為非 NULL，代表對應到 `qtest` 中的 `rh [str]` 命令，須將 `head->value` 複製到 `sp` 中。使用 `strncpy` 複製長度 `bufsize - 1` 的字串到 `sp`，最後再加上字串 terminator。
最後 free 掉 `q->head->value` 及 `q->head` 指向的元素，將兩者指向 `NULL` ，並將 `q->head` 指向 `newh`。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q_size(q))
return false;
list_ele_t *newh;
newh = q->head->next; /* Points to new head element */
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
free(q->head->value);
q->head->value = NULL;
free(q->head);
q->head = NULL;
q->head = newh;
q->size--;
return true;
}
```
### q_size
函式中的註解要求此函式必須為 $O(1)$ ，因此在 struct `queue_t` 另外新增一成員 `size` 是必要的，每次 `q_size` 只需回傳該成員即可。
```cpp
int q_size(queue_t *q)
{
if (!q || !q->size)
return 0;
return q->size;
}
```
### q_reverse
這邊用到資料結構中的反轉 linked list，宣告三個指摽 `pre` 、 `cur` 、 `pos` 來操作，流程如下：
```cpp
pre(head) cur pos
| | |
v v v
+----+ +----+ +----+ +----+
|ele1|->|ele2|->|ele3|->|ele4|->...
+----+ +----+ +----+ +----+
pre cur pos
| | |
v v v
+----+ +----+ +----+ +----+
|ele1|<=>|ele2| |ele3|->|ele4|->... // cur->next=pre
+----+ +----+ +----+ +----+
pre,cur pos
| |
v v
+----+ +----+ +----+ +----+
|ele1|<=>|ele2| |ele3|->|ele4|->... // pre = cur
+----+ +----+ +----+ +----+
pre cur,pos
| |
v v
+----+ +----+ +----+ +----+
|ele1|<=>|ele2| |ele3|->|ele4|->... // cur = pos
+----+ +----+ +----+ +----+
pre cur pos
| | |
v v v
+----+ +----+ +----+ +----+
|ele1|<=>|ele2| |ele3|->|ele4|->... // pos = pos->next
+----+ +----+ +----+ +----+
... // loop the above steps
head pre,cur(tail) pos
| | |
v v |
+----+ +------+ +----+ v
|ele1|...|eleN-1|<-|eleN| NULL // if (!pos) { break; }
+----+ +------+ +----+
head,tail pre,cur pos
| | |
v v |
+----+ +------+ +----+ v
|ele1|...|eleN-1|<-|eleN| NULL // q->tail = q->head
+----+ +------+ +----+
// now ele1->next still points to ele2
head,tail pre,cur pos
| | |
v v |
+----+ +------+ +----+ v
NULL <-|ele1|...|eleN-1|<-|eleN| NULL // q->tail->next = NULL
+----+ +------+ +----+
tail head
| |
v v
+----+ +------+ +----+
NULL <-|ele1|...|eleN-1|<-|eleN| // q->head = cur
+----+ +------+ +----+
```
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q_size(q) || q_size(q) == 1)
return;
list_ele_t *pre = q->head;
list_ele_t *cur = pre->next;
list_ele_t *pos = cur->next;
while (1) {
cur->next = pre;
pre = cur;
if (!pos)
break;
cur = pos;
pos = pos->next;
}
q->tail = q->head;
q->tail->next = NULL;
q->head = cur;
}
```
### q_sort
`q_sort` 原本使用 bubble sort 但由於時間複雜度太高，因此後來選擇 merge sort 實作。 `merge_sort` 參數為 `q->head` 的 reference，在 `merge_sort` 結束後不必多餘的指派， `q->head` 即指向整個排序後的 queue。
```cpp
void q_sort(queue_t *q)
{
if (!q || !q_size(q) || q_size(q) == 1)
return;
merge_sort(&q->head);
}
```
`merge_sort` 流程為將 queue 平均分為兩 queue，分別由 `front` 、 `back` 指向；再分別對兩 queue 遞迴的作 `merge_sort` 直到 queue 為 NULL 或剩餘一元素。
參數的 `**q_head` 為一指向 head pointer 的指標，目的是為了將 head pointer 本身傳入，並且在函式結束後讓 head pointer 指向最終結果。 後面遞迴的時候 `front` 及 `back` 會分別代表新的 head pointer ，最後 `merge` 會將兩 queue 合併並回傳排序後 queue 的 head pointer，指派給最初傳入的 `*q_head`。
```cpp
void merge_sort(list_ele_t **q_head)
{
/* q_head is the pointer point to the address of the
* head element pointer, dereference to get pointer itself */
list_ele_t *head = *q_head;
if (!head ||
!head->next) /* Return if q_head is NULL or there's only one element */
return;
/* Split the queue into two queue */
list_ele_t *front = NULL;
list_ele_t *back = NULL;
split_queue(head, &front, &back);
/* Sort each queue */
merge_sort(&front);
merge_sort(&back);
*q_head = merge(front, back);
}
```
`split_queue` 將 `q_head` 指向的 queue 均分為二，方法為使用兩指標 `fast` 及 `slow` 並讓 `fast` 以兩倍 `slow` 的速度迭代整個 queue，當 `fast` 為 NULL 代表到底了，此時 `slow` 會指向中間元素的前一元素。將 `q_head` 指派給 `*front_p` ； `slow->next` 指派給 `*back_p` ，並將 `slow->next = NULL` 可分為兩 queue。
要注意的是 `split_queue` 後兩參數為 pointer to `front` 及 pointer to `back` 並且 `front` 及 `back` 亦分別為指標，因此呼叫的時候是把 `front` 及 `back` 指標本身的 reference 傳入：`split_queue(head, &front, &back);` 。且在最後是使用`*front_p` 及 `*back_p` 來拿到 pointer 本身。
```cpp
void split_queue(list_ele_t *q_head, list_ele_t **front_p, list_ele_t **back_p)
{
list_ele_t *fast;
list_ele_t *slow;
slow = q_head;
fast = q_head->next;
/* fast iterates two times faster than slow.
* So that when fast reaches the end of queue,
* slow is at middle of the queue. */
while (fast) {
fast = fast->next;
if (fast) {
fast = fast->next;
slow = slow->next;
}
}
*front_p = q_head;
*back_p = slow->next;
slow->next = NULL;
}
```
`merge` 將傳入的兩 head pointer 指向的 queue 合併，首先決定新 queue 的 head 並由 `result` 、 `current` 兩指標指向。並且在分別迭代 `a` 、 `b` 兩 queue，比較大小決定 `current->next` 直到其中一者取完為止，並將另一者剩餘部分接在新 queue 後完成，最後 `result` 會指向新 queue 的頭，回傳後會直接指派給 `merge_sort` 的 `*q_head`（即傳入 `merge_sort` 的 `q->head`）完成排序。
另外原本使用遞回版本的 `merge` 會遇到 stack 空間不足的情況。
```cpp
list_ele_t *merge(list_ele_t *a, list_ele_t *b)
{
list_ele_t *result, *current;
if (!a)
return b;
else if (!b)
return a;
/* Initialize the head of result */
if (strcmp(a->value, b->value) < 0) {
result = a;
a = a->next;
} else {
result = b;
b = b->next;
}
current = result;
/* Iterative version of merge */
while (1) {
if (!a) {
current->next = b;
break;
}
if (!b) {
current->next = a;
break;
}
if (strcmp(a->value, b->value) < 0) {
current->next = a;
a = a->next;
} else {
current->next = b;
b = b->next;
}
current = current->next;
}
return result;
/* Recursive version of merge, this might cause stack
* explosion where there are too many elements. */
/*
* if (strcmp(a->value, b->value) < 0) {
* result = a;
* result->next = merge(a->next, b);
* } else {
* result = b;
* result->next = merge(a, b->next);
* }
*
* return result;
list_ele_t *result_head = result;
*/
}
```
Sign in with Wallet
Connect another wallet