# 2020q3 Homework1 (lab0)
contributed by <`Sisker1111`>
###### tags: `進階電腦系統理論與實作`
[TOC]
## 簡介
### 養成良好coding習慣
lab 中使用許多工具協助養成良好的寫程式習慣，包含：
* Git pre-commit hook
* [git-good-commit](https://github.com/tommarshall/git-good-commit): 學習撰寫良好的 Git commit message
* [cppcheck](http://cppcheck.sourceforge.net/): 靜態程式碼分析工具
* [clang-format](https://clang.llvm.org/docs/ClangFormat.html): 確保一致的程式風格
* [GNU Aspell](http://aspell.net/): 拼字檢查
* [valgrind](https://valgrind.org/): 動態程式分析工具
* [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer): 檢查記憶體的使用
等......
詳細的環境設定以及lab的相關說明請參閱 [I01: lab0](https://hackmd.io/@sysprog/2020-lab0?fbclid=IwAR2YOjtMYzE_kB5vqvBUOSM9OlR5hgvz7NHUGg21NOcN9Hb8vccxEV-yC3o)、[C Programming Lab: Assessing Your C Programming Skills](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)
### :rocket: 改寫自 CMU 計算機概論的作業
[CMU](https://www.cmu.edu/) (位於美國賓州匹茲堡的卡內基美隆大學) 電腦科學系的 [Introduction to Computer Systems (ICS)](http://www.cs.cmu.edu/~213/index.html) 課程準備了 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) 作為檢閱學生 C 語言程式設計的認知:
* 記憶體管理;
* 建立並管理需要透過指標操作的資料結構;
* 字串操作;
* 改善特定關鍵操作的效能;
* 提高程式碼的穩固程度，例如能夠處理無效的參數，包含 NULL 指標;
在給定的程式碼中，[queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 包含以下鏈結串列 ([linked list](https://en.wikipedia.org/wiki/Linked_list)) 結構定義:
```cpp
/* Linked list element */
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
```
接著用鏈結串列來實作佇列 ([queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)))
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
/* 其他自行定義的結構成員 */
} queue_t;
```
這過程可用下圖來表示：佇列的上層建構於 `queue_t` 類型的物件。一開始，此資料結構僅包含單一成員 `head`，之後陸續以鏈結串列增添給定的字串，如 `"cab"`, `"bead"`, `"cab"` 等等。佇列內的每個元素由單向的鏈結串列構成，每個元素由 `list_ele_t` 類型的物件來表示，後者包含真正保存字串的 `value` 和指向下個鏈結串列元素開頭地址的 `next`。
> 圖 1: 透過鏈結串列實作的佇列。每個鏈結串列元素都有個 `value` 指標，指向一段連續的記憶體 (即 C-style string，以 NULL 字元結尾的字串)，字元依據 ASCII 編碼 (以十六進位顯示)。
C 語言中，字串以連續的`char` 型態物件的排列來表示，對多數的硬體來說，`char` 型態表示為 1 個 byte。，而為了儲存長度 `l` 的字串，需要至少 `l + 1` 個 `char` 元素，並在最後設定為 `\0` 字元。上圖的 `[cab, bead, cab]`，其中字元 `a` 和 `e` 以十六進位表示為 ASCII 編碼的 `61` 和 `65`。觀察上圖，字串 `"cab"` 和 `"bead"` 在執行時期可能對應到兩段不相鄰的記憶體。
在給定的 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 程式碼中，佇列透過 `queue_t *` 指標型態來操作，程式碼需要考慮以下二種特別狀況，作出對應的處置:
1. `NULL` 佇列：是指標值為 `NULL`;
2. 「空」(empty) 的佇列是指向有效結構，但開頭 (`head`) 的值為 `NULL`;
:::info
另一種解讀方式:
若你有空的紅包袋，裡面的東西是 empty;
若你連紅包袋都沒有，就可以說 NULL;
:::
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* ==`q_sort`==: 以==遞增順序==來排序鏈結串列的元素。
## 如何測試
測試所有的測資:
> make test
# 基本實作
## Queue structure
``` c=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
除了原始的head之外，加入了
* tail: 指向 queue 的尾端，目的是為了 $O(1)$ 的 insert tail
* size: 計算 queue 的大小，目的是為了 $O(1)$ 得到 queue size
## q_new
```c=1
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->tail = NULL;
q->head = NULL;
q->size = 0;
return q;
}
```
建立一個新的 queue，如果 malloc 失敗，則return`NULL`，成功則 return 一個空的 queue.
## q_free
```c=1
void q_free(queue_t *q)
{
if (!q)
return;
if (q->head) {
list_ele_t *tmp = q->head;
while (q->head) { // free all element in link-list
q->head = q->head->next;
free(tmp->value);
free(tmp);
tmp = q->head;
}
}
free(q);
}
```
必須先檢查 queue 是否為NULL，將現有的 queue 整個釋放掉，注意要先將 queue 上的每個 element 都釋放掉，最後才釋放 queue 本身.
## q_insert_head
```c=1
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
/* TODO: What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
if (!newh) // queue q is not exist || malloc return NULL
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
if (!q->head) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
### Code Description
1. 開頭一樣先判斷 queue 是否 為 `NULL`.
2. 7~9行 malloc 一個新點`newh`並檢查是否有 malloc 成功.
3. 11~15行 malloc 一個空間用來存放字串，同樣需檢查 malloc 是否成功，失敗需要將`newh`釋放.
4. 16行 將 input 字串指派給`newh->value`
5. 18~24行 將`q->head`指到`newh`，也將`q->tail`指到 queue 的最後一個 element .
## q_insert_tail
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh) // queue q is not exist || malloc return NULL
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
if (!q->head) {
newh->next = q->head;
q->head = newh;
q->tail = newh;
q->size++;
return true;
}
newh->next = NULL;
q->tail->next = newh;
q->tail = q->tail->next;
q->size++;
return true;
}
```
### Code Description
1. 開頭先判斷 queue 是否 為 `NULL`.
2. 16~22行 用`q->head`是否為`NULL`來判斷要字串`s`是否為 queue 的第一個字串.
3. 23~27行 把`q->tail->next`指到新點`newh`，並把`q->tail`指到`newh`.
## q_remove_head
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || !q->head) // queue q is not exist
return false;
if (sp) {
if (bufsize > strlen(q->head->value)) {
strncpy(sp, q->head->value, strlen(q->head->value));
sp[strlen(q->head->value)] = '\0';
} else {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### Code Description
remove 一個 queue 中存在`head`的字串，並把此字串存入`sp`
1. 7~15行 用來限制可以存入`sp`的最大字串長度.
2. 17~22行 把`q->head`找到`q->head->next`並釋放原本`head`的記憶體.
## q_size
```c=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
回傳 queue 的 size.
## q_reverse
```c=
void q_reverse(queue_t *q)
{
if (!q)
return;
list_ele_t *cursor = NULL;
list_ele_t **indirect = &q->head;
q->tail = q->head;
while (*indirect) {
list_ele_t *next = (*indirect)->next;
(*indirect)->next = cursor;
cursor = *indirect;
*indirect = next;
}
*indirect = cursor;
}
```
將 queue 中的 element 反向串接，記得要把`q->head` & `q->tail`指到新的位置，方法類似於
quiz1 的 reverse .
## q_sort
這題要自己從頭想真的有點難，最後還是參考網路上其他人的作法，參考網址如下:
https://www.techiedelight.com/merge-sort-singly-linked-list/
```c=
list_ele_t *merge(list_ele_t *left_list, list_ele_t *right_list)
{
list_ele_t *tmp = NULL;
if (strcmp(left_list->value, right_list->value) <= 0) {
tmp = left_list;
left_list = left_list->next;
} else {
tmp = right_list;
right_list = right_list->next;
}
list_ele_t *head = tmp;
while (left_list && right_list) {
if (strcmp(left_list->value, right_list->value) <= 0) {
tmp->next = left_list;
tmp = tmp->next;
left_list = left_list->next;
} else {
tmp->next = right_list;
tmp = tmp->next;
right_list = right_list->next;
}
}
if (left_list) tmp->next = left_list;
if (right_list) tmp->next = right_list;
return head;
}
void merge_sort(list_ele_t **head)
{
if (!(*head) || !(*head)->next)
return;
list_ele_t *fast = (*head)->next;
list_ele_t *slow = *head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
merge_sort(head);
merge_sort(&fast);
*head = merge(*head, fast);
}
void q_sort(queue_t *q)
{
if (!q)
return;
merge_sort(&q->head);
if(!q->tail)
return;
while(q->tail->next)
q->tail = q->tail->next;
}
```
### Code Description
1. 使用stcmp來做字串的比大小
2. 排序時也會順便將`q->head`指到正確的位置，排序後記得也要把`q->tail`指到正確的地方
# 測試與分析
## 使用自動評分系統評分
* trace-15-perf 我原本照著網址的做法直接做會跑不過，推測是因為memory過多或者遞迴太多次導致，後來簡化了一些寫法，以及把function合併後就對了.
* trace-17-complexity 這個trace有時候會突然跑不過，目前還不確定是什麼原因.
## Valgrind
可使用指令:
```
$ valgrind --tool=massif ./qtest -f ./traces/trace-02-ops.cmd
$ ms_print massif.out.PID
$ massif-visualizer massif.out.PID
```
#### 分析`trace-02-ops.cmd`
執行結果:
```cmd> # Test of insert_head, insert_tail, and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
q = [bear gerbil meerkat bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil meerkat bear gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = [meerkat bear gerbil]
cmd> rh meerkat
Removed meerkat from queue
q = [bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
Freeing queue
```
#### 分析`trace-09-robust.cmd`
執行結果:
```cmd> # Test remove_head with NULL argument
cmd> option fail 10
cmd> option malloc 0
cmd> new
q = []
cmd> ih bear
q = [bear]
cmd> rhq
Removed element from queue
q = []
cmd>
Freeing queue
```
#### 分析`trace-17-complexoty.cmd`
執行結果:
```cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> it
Probably constant time
cmd> size
Probably constant time
cmd> option simulation 0
Freeing queue
```
Sign in with Wallet
Connect another wallet