# 2018q3 Homework2 ([lab0](https://github.com/ofAlpaca/lab-list))
contributed by < `ofAlpaca` >
###### tags: `CSIE5006` `HW`
## 實驗環境
```
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
```
---
## Makefile
可以透過了解 `Makefile` 來得知此程式的流程，以本次作業的 `Makefile` 為例 :
* 此處是變數宣告， `CC` 代表的是使用 GNU compiler ， `CFLAGS` 則是相關參數。其中的 `-O0` 是[最佳化參數](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)， `-Werror` 則是把所有警告都轉為錯誤 ([source](https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html))。
```clike
CC = gcc
CFLAGS = -O0 -g -Wall -Werror
```
* 在 `all` target 裡的相依性項目有 `GIT_HOOKS` 與 `qtest` ，前者會透過 script 去檢查是否有安裝 git hook 需要的套件並安裝上 git hook ，後者 `qtest` target 則會繼續照法則往下去找相依性項目。
```clike
GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest
$(GIT_HOOKS):
@scripts/install-git-hooks
@echo
```
* `queueu.o` target 下的相依性項目有 `queue.[ch]` 與 `harness.h` ，前者是本次作業的核心檔案，後者則是作業提供的 `malloc()` 與 `free()` ；經過編譯後產生 queue 的 object 檔，同時也是 `qtest` 的相依性項目。在 `qtest` target 執行編譯命令後會產生 `qtest` ，一個可執行檔。
```clike
queue.o: queue.c queue.h harness.h
$(CC) $(CFLAGS) -c queue.c
qtest: qtest.c report.c console.c harness.c queue.o
$(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o
```
* 可以使用 `make test` 或 `make clean` 來執行 Makefile 下相對應的命令，`make test` 就會去執行 `driver.py` 來跑測試並計算分數， `make clean` 則會清除過程中產生的多餘檔案。
```clike
test: qtest scripts/driver.py
scripts/driver.py
clean:
rm -f *.o *~ qtest
rm -rf *.dSYM
(cd traces; rm -f *~)
```
---
## Queue Structure
* 根據作業提供的文件有提到目前的 `queue_t` 結構不完整，需要再增加其他欄位。為了能以 $O(1)$ 的時間複雜度從尾端插入節點與計算 queue 的大小，增加了 `list_ele_t *tail` 與 `size_t size` 。
> The top-level representation of a queue is a structure of type queue_t. In the starter code, this structure contains only a single field head, but you will want to add other fields.
```clike=
typedef struct {
list_ele_t *head; /* Linked list of elements */
/*
You will need to add more fields to this structure
to efficiently implement q_size and q_insert_tail
*/
list_ele_t *tail; // ptr to tail of the queue
size_t size; // size of the queue
} queue_t;
```
---
## Operations of Queue
### `q_new()`
新增 if statement 來判斷佇列是否為 `NULL` ，並對 `tail` 與 `size` 初始化。
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0; // initialization
return q;
}
```
### `q_free()`
新增 if statement 來判斷佇列是否為空，如果是，則 do nothing ，否則宣告 nptr pointer 去尋訪佇列中的每一個節點並釋放它，最後再釋放佇列。
```clike=
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
if (q != NULL) {
list_ele_t *nptr = q->head;
list_ele_t *rm;
while (nptr != NULL) {
rm = nptr;
nptr = nptr->next;
// free(rm->value);
free(rm);
}
free(q);
}
}
```
### `q_insert_head()`
新增 if statement 來判斷佇列是否為 `NULL` ，是則回傳 false ，否則配置記憶體給 `newh` ，使用 `strdup()` 配置 string 的副本給 `newh->value` 接著把 `newh->next` 指向 `head `。如果 `head` 與 `tail` 皆為 `NULL` ，則表示目前新增的節點為佇列的第一個，故 `tail` 也需要指向此節點，最後再 `size++`。
```clike=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* What should you do if the q is NULL? */
if (q != NULL) {
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
newh = malloc(sizeof(list_ele_t));
if (newh != NULL) {
newh->value = strdup(s);
newh->next = q->head;
/* case : the first node */
if (q->head == NULL && q->tail == NULL)
q->tail = newh;
q->head = newh;
q->size++;
return true;
}
}
return false;
}
```
### `q_insert_tail()`
大致步驟和 `q_insert_head()` 相同，只差在換成從尾部接上。為了達到時間複雜度 $O(1)$ 的要求，所以使用 `tail` 而非從頭開始。
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
list_ele_t *newh;
if (q != NULL) {
newh = malloc(sizeof(list_ele_t));
if (newh != NULL) {
newh->value = strdup(s);
newh->next = NULL;
/* case : the first node */
if (q->head == NULL && q->tail == NULL)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
}
return false;
}
```
### `q_remove_head()`
除了判斷佇列與 `queue->head` 是否為 `NULL`外，還須判斷 `sp` 是否為 `NULL` ，如果不是，則需要將最長為 `bufsize` - 1 的字串複製至 `sp` 並在其尾部加上 terminator ，最後再更新 `head` 。
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (q != NULL) {
list_ele_t *rm_t = q->head;
if (rm_t != NULL) { // if the removed node is not NULL
if (sp != NULL) {
memcpy(sp, rm_t->value,
bufsize); // copy the removed string to sp
sp[bufsize - 1] = '\0'; // add terminator at the end
}
q->head = q->head->next; // move head ptr to next node
q->size--;
// free(rm_t->value);
free(rm_t); // free the removed node
rm_t = NULL; // tmp ptr to NULL
return true;
}
}
return false;
}
```
### `q_size()`
因為先前有新增刪除節點時都有維護 `size` ，所以此處只要判斷佇列是否為 `NULL` 並回傳就好。
```clike=
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
return q != NULL ? q->size : 0;
}
```
### `q_reverse()`
這裡使用的 reverse 算是最直觀的，先準備三個指標，分別指向現在節點、過去節點、下個節點。迴圈內的執行順序為：
1. 先將現在節點的 `next` 指向過去節點( #11 )
2. 過去節點指向現在節點( #12 )
3. 現在節點指向下個節點( #13 )
4. 下個節點指向現在節點的 `next` ( #14 )
5. 檢查下個節點是否為 `NULL` ，是則停止迴圈
6. 將最後一個節點的 `next` 指向過去節點
7. 最後再更新 `head` 與 `tail` 指標
```clike=
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (q != NULL && q->size != 0) {
list_ele_t *pre = NULL; // previous
list_ele_t *cur = q->head; // current
list_ele_t *nxt = cur->next; // next
q->tail = q->head;
while (nxt != NULL) {
cur->next = pre;
pre = cur;
cur = nxt;
nxt = cur->next;
}
cur->next = pre;
q->head = cur;
}
}
```
---
## 測試結果
==TOTAL 100/100==
```
$ make test
scripts/driver.py
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
........
--- TOTAL 100/100
```
---
## 自動評分系統
這裡主要是說明自動評分系統 `driver.py` 的運作流程。
:::success
前言
* 根據[**說明文件**](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)提到，可以透過下 `./driver.py` 或 `make test` 來執行自動評分。
* 再看看 Makefile 的 `test` tag 下執行的命令也是 `script/driver.py` 。
* 由此可知，自動評分的主要程式就是 `driver.py` 。
:::
```flow
st=>start: run()
e=>end: print total score
op=>operation: Tracer.run()
op2=>operation: Tracer.runTrace(trace_id)
op3=>operation: subprocess.call(qtest, cmd)
cond=>condition: Run all tests ?
st->op->op2->op3->cond
cond(yes)->e
cond(no)->op2
```
### `driver.py` 的運作流程
1. 當執行 `driver.py` 後，第一個被呼叫的函式為 `run()` 。
2. `run()` 主要是設定參數，例如要測試哪個程式，要測試什麼命令之類的。
* `-h` : 說明參數用途
* `-p` : 所要測試的程式， default "./qtest"
* `-v` : 測試訊息的 level (0-3) 設定， default 0
* `-t` : 所要測試的命令的編號， default 0
* `-A` : 自動產生 json 格式的成績單
* 下 `-A` 參數 :
```shell
$ ./scripts/driver.py -A
--- Trace Points
--- trace-01-ops 6/6
--- trace-02-ops 6/6
--- trace-03-ops 6/6
--- trace-04-ops 6/6
--- trace-05-ops 6/6
--- trace-06-string 7/7
--- trace-07-robust 7/7
--- trace-08-robust 7/7
--- trace-09-robust 7/7
--- trace-10-malloc 7/7
--- trace-11-malloc 7/7
--- trace-12-malloc 7/7
--- trace-13-perf 7/7
--- trace-14-perf 7/7
--- trace-15-perf 7/7
--- TOTAL 100/100
{"scores": {"Trace-01" : 6, "Trace-02" : 6, "Trace-03" : 6, "Trace-04" : 6, "Trace-05" : 6, "Trace-06" : 7, "Trace-07" : 7, "Trace-08" : 7, "Trace-09" : 7, "Trace-10" : 7, "Trace-11" : 7, "Trace-12" : 7, "Trace-13" : 7, "Trace-14" : 7, "Trace-15" : 7}}
```
> 預設參數 t = 0 會把所有的測試都跑過。
> [name=ofAlpaca][color=#bbff00]
3. 之後會產生 Tracer 的 instance ，並執行 method `Tracer.run()` ，此 method 會去把所有的測試透過 method `Tracer.runTrace()` 來執行一次，並根據回傳值決定此測試是否 "通過"。
> 所有的測試都放在 ./traces 這個資料夾裡。
> 這裡會用 "通過" 是因為程式碼裡面只有滿分跟 0 分兩種而已。
> [name=ofAlpaca][color=#bbff00]
4. `Tracer.runTrace()` 會呼叫 python 函式庫的 subprocess 來執行 `./qtest` 並傳入相關參數給 `qtest` ，通過就回傳 true 。
> subprocess 其用法為 `subprocess.call([./qtest -v 0 -f "trace-01-ops.cmd"])`[name=ofAlpaca][color=#bbff00]
6. 當所有測試都執行完後，便會印出總成績。
---
## qtest
### qtest 行為
1. 其本身是個 command line interpreter
2. 初始化各項參數，例如 : `-f FILE` 。
3. 命令是否合理，例如在 `q == NULL` 的情況下跑 `reverse` 指令則會讓 `do_reverse()` 產生 "Warning: Calling reverse on null queue" 的警告。
4. 檢查 `queue.[ch]`裡的佇列實作是否有誤，例如 `do_reverse()` 就是去檢查 `q_reverse()` 是否有 Timeout 或 Segmentation fault 的問題。
### Command information as linked list
`qtest` 其中有個吸引我注意的技巧，那就是所有的命令都是透過 linked list 結構來儲存的。在 `console.h` 可以看到其節點結構為下 :
```clike
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name; // 命令名稱
cmd_function operation; // 命令的 function pointer
char *documentation; // 命令的說明
cmd_ptr next;
};
```
過去在寫需要 command line 的程式時，通常都是用 `if-else` 或 `switch` 這種 hard-coded 的方式決定命令的流程，如果使用 linked list 的話就可以省去許多冗長的程式碼，例如 :
```clike=
switch(cmd) {
case "add" :
add();
break;
case "remove" :
remove();
break;
case "reverse" :
reverse();
break;
}
```
使用 linked list 可以改為 :
```clike=
while( strcmp(cmd, cmd_list->name) != 0 )
cmd_list = cmd_list->next;
cmd_list->operation();
```
如果命令很多，使用 `switch` 就會導致程式碼雜亂無章又不易維護，但使用 linked list 短短幾行就可以達到同樣的效果卻又有品味。另一點是，如果今天想要看到命令的說明或者其他操作，前者還要再跑一次 `switch` ，但後者卻只需要改為 `cmd_list->documentation` 就可以辦到。
### [Signal handling](https://notes.shichao.io/apue/ch10/)
在本次作業中， `qtest` 是透過 `void (*signal(int sig, void (*func)(int)))(int)` 這個函式來檢查程式是否 Timeout 或 Segmentation fault 的，以下一一講解。
* signal 是個軟體中斷，像 Ctrl-C 就是個中斷，而 `signal()` 函式提供了一個可以處理非同步事件的方法。
* `sig` 為 signal number ，為中斷的編號，定義在 C 函式庫的 `signal.h` 裡，變數是 SIG 開頭，像是 `SIGINT` 、 `SIGSEGV` 。
* `func` 可以有三種值 :
1. `SIG_IGN` ，訊號忽略。
2. `SIG_DEF` ，訊號會照預設情況處理。
3. 當訊號發生時的 `func` 就會被呼叫，此稱為 signal handler 或 signal-catching function。
* `qtest.c` 的 `queue_init()` 就可以見到其用法 :
```clike=
static void queue_init() {
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
* 第 4 行設置了 catch `SIGSEGV` 的訊號，當訊號發生時就呼叫 `sigsegvhandler` 。
* 第 5 行設置了 catch `SIGALRM` 的訊號，當訊號發生時就呼叫 `sigalrmhandler` 。
* 當發生了 `SIGSEGV` 、 `SIGALRM` 的中斷，便會呼叫其各自的 signal handler 。這也是為什麼每次 `queue.c` 一發生問題，就會產生這些錯誤訊息的原因。
```clike=
/* Signal handlers */
void sigsegvhandler(int sig)
{
trigger_exception(
"Segmentation fault occurred. You dereferenced a NULL or invalid "
"pointer");
}
void sigalrmhandler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
```
Sign in with Wallet
Connect another wallet