# 2018q3 Homework2 (lab0)
contributed by < [`letticee`](https://github.com/letticee) >
>* 請持續更新進度！
>* [Fix code command](v) 應修正為 "Modify comment"
>
>[name=課程助教][color=red]
>>已改
作業說明：[E01: lab0](https://hackmd.io/s/BJp_jq-tm)
* 實驗環境
* 學習 git 與 開發工具
* 實作內容
* 研究自動測試機制
## 實驗環境
```shell
$ uname -a
Darwin Cynthia-8.local 17.7.0 Darwin Kernel Version 17.7.0: Thu Jun 21 22:53:14 PDT 2018; root:xnu-4570.71.2~1/RELEASE_X86_64 x86_64
```
## 學習 git 與 開發工具
###
### 遇到的問題
* 在 macOS 上跑 cppcheck 時，會出現一個錯誤，導致無法 commit
:::danger
[harness.c:147]: (error) Address of auto-variable 'new_block->payload' returned
Fail to pass static analysis.
:::
猜測是因為他 return 了一個 local variable 的reference，出function就會消失了 (?
* 目前處理方法：到 `./lab0-c/scripts/pre-commit.hook` 加入一個 cppcheck 的 option --suppress 來擋住那個 error
:::success
```shell
CPPCHECK_OPTS="-I. -I./include --error-exitcode=1 . --suppress=*:./harness.c:147 ./"
```
:::
## 實作內容
### [queue.h](https://github.com/letticee/lab0-c/blob/7c1d71c20769347cd165529dfc030b316ae3b013/queue.h#L19)
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
* 在 `queue_t` 中加入
* `list_ele_t *tail`
* 指向 queue 的尾端，使 `q_insert_tail()` 可以在常數時間內完成
* `int size`
* 紀錄 queue 的大小，使 `q_size()` 可以在常數時間內回傳 queue 的大小
### [q_new()](https://github.com/letticee/lab0-c/blob/7c1d71c20769347cd165529dfc030b316ae3b013/queue.c#L25)
1. 當 malloc 失敗時回傳 `NULL`
2. 初始化 `head = NULL`, `tail = NULL`, `size = 0`
### [q_free()](https://github.com/letticee/lab0-c/blob/7c1d71c20769347cd165529dfc030b316ae3b013/queue.c#L40)
1. q 是 NULL 的話直接 return
2. q 不是 empty 的話，先將 head 的指標複製一份到 `ele`，將 `head` 指標指到下一個元素。再 free 掉 `ele` 所指到的 value 跟 `ele` 指標
3. free 掉 q
* $T(n) = O(n)$
### [q_insert_head()](https://github.com/letticee/lab0-c/blob/7c1d71c20769347cd165529dfc030b316ae3b013/queue.c#L65)
1. q 是 `NULL` 的話回傳 `false`
2. malloc 新的 head 的空間，如果失敗就回傳 `false`
3. malloc 新的 head 的 value 空間，如果失敗 free 掉新的 head 、回傳 `false`
4. 將傳入的字串複製到新的 head 的 value
5. 將新的 head 的 `next` 指到原本 q 的 `head`，然後將 q 的 `head` 指到新的 head
6. 如果 q 的 `head` 是 `NULL` (原本是 empty queue)，將 `tail` 也指到新的 head
7. 將 q 的 `size` 加 1
* $T(n) = O(1)$
* 在配置空間和複製字串的部分，原本想要使用 `strdup()` 做到配置空間和複製字串的功能，但因為在 `harness.h` 裡有 define 使用自定義的 `test_malloc()` 取代 `malloc()`。實驗過後，發現 `strdup()` 在配置空間的時候不會呼叫到自定義的 `test_malloc()`，所以會造成 test 不過。
* `strdup()` 版本
```c=
(newh->value) = strdup(s);
if ((newh->value) == NULL) {
free(newh);
return false;
}
```
* `malloc()` + `strcpy()` 版本
```c=
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newh->value == NULL) {
free(newh);
return false;
}
strcpy(newh->value, s);
```
### [q_insert_tail()](https://github.com/letticee/lab0-c/blob/406eaf85a8e511dc231f0dfe0b542a9db3d78639/queue.c#L109)
1. q 是 `NULL` 的話回傳 `false`
1. malloc 新的 tail 的空間，如果失敗就回傳 `false`
1. malloc 新的 tail 的 value 空間，如果失敗 free 掉新的 tail 、回傳 `false`
1. 將傳入的字串複製到新的 tail 的 value
1. 將原本 q 的 `head` 的 `next` 指到新的 tail，新的 tail 的 `next` 指到 `NULL`
1. 將 q 的 `tail` 指到新的 tail
1. 將 q 的 `size` 加 1
* $T(n) = O(1)$
### [q_remove_head()](https://github.com/letticee/lab0-c/blob/406eaf85a8e511dc231f0dfe0b542a9db3d78639/queue.c#L149)
1. q 是 `NULL` 或 empty ( `head` 是 `NULL` )的話回傳 `false`
2. 如果 sp 不是 `NULL`，將 `sp` 空間內的 `bufsize` 大小範圍都設為 `'\0'`，然後將 `head` 的 `value` 中 `bufsize - 1` 大小的字串複製到 `sp`
3. 先將原本的 `head` 的指標複製一份到 `oldh`，將 `head` 指到原本的 head 的下一個元素。再 free 掉 `oldh` 所指到的 `value` 跟 `oldh` 指標
4. 將 q 的 size 減 1
* $T(n) = O(1)$
### [q_size()](https://github.com/letticee/lab0-c/blob/406eaf85a8e511dc231f0dfe0b542a9db3d78639/queue.c#L174)
1. q 是 `NULL` 或 empty ，回傳 0
2. 回傳 q 的 `size`
* $T(n) = O(1)$
### [q_reverse()](https://github.com/letticee/lab0-c/blob/406eaf85a8e511dc231f0dfe0b542a9db3d78639/queue.c#L190)
1. q 是 `NULL` 或 empty 的話，直接 return
2. 初始化 `pre`, `itr`, `post` 三個指標，分別指到 `NULL`, `head`, `itr->next`，然後將 `tail` 指到 `head`
3. 迴圈內將 `itr` 的 `next` 指到 `pre`，`pre` 指到 `itr` ，`itr` 指到 `post`，`post` 指到 `post` 的 `next` ( 將所有元素的 `next` 指到前一個元素 )，直到 `post` 是 `NULL`，也就是 `itr` 指到的是 q 的最後一個元素
4. 將 `itr` 的 `next` 指到 `pre`，將 `head` 指到 `itr`
* $T(n) = O(n)$
## 研究自動測試機制
### Makefile
* 從 `Makefile` 可以得知 `make` 完後會產生一個 `qtest` 的可執行檔
* `make test` 指令會去執行 `driver.py`
* `make clean` 指令會清除 `make` 產生的檔案
### 自動評分系統運作的原理
* 自動評分的主要程式是 `driver.py`
* `driver.py`
* 首先會呼叫 `run()`，`run()` 主要是處理參數（`-h` `-p` `-t` `-v` `-a`），接著呼叫`Tracer.run()`
* `-h`：印出參數說明
* `-p`：要測試的程式，預設是 `./qtest`
* `-t`：要測試的命令在 traceDict 裡的編號
* `-v`：測試訊息的詳細程度（0 - 3），預設是 1
* `-v 0` 參數：僅列出每個測驗的分數
```
--- 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
```
`-v 1`：多印出測驗內容
```
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
```
`-v 2`：多印出測驗的指令內容
```
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
cmd>ih gerbil
cmd>ih bear
cmd>ih dolphin
cmd>rh dolphin
Removed dolphin from queue
cmd>rh bear
Removed bear from queue
cmd>rh gerbil
Removed gerbil from queue
cmd>
--- trace-01-ops 6/6
```
`-v 3`：多印出 queue 裡面儲存的內容
```
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head 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>rh dolphin
Removed dolphin from queue
q = [bear gerbil]
cmd>rh bear
Removed bear from queue
q = [gerbil]
cmd>rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
--- trace-01-ops 6/6
```
* `-A`：在最後產生 JSON 格式的成績單
* `Tracer.run()` 中會將 trace-01 -- trace-15 依序執行一次 `Tracer.runTrace()`，根據回傳值判斷該測驗的分數、計算總分並印出成績
* `Tracer.runTrace()` 呼叫 `subprocess.call()` 並傳入參數來執行 `qtest`
### qtest 的行為和裡頭的技巧
* `qtest.c`
* 處理參數（`-h` `-f` `-v` `-l`）
* `-h`：印出參數說明
* `-f`：要讀入的 command 檔
* `-v`：測試訊息的詳細程度
* `-l`：將測試訊息輸出成檔
* 在 `console_init()` 內呼叫 `add_cmd()` 來加入 cmd 指令
* 處理每個指令的實作內容，包括檢查指令的參數、呼叫 `queue` 的 function 去操作 q、輸出警告和錯誤訊息（包括檢查 `queue.c` 的實作是否會發生 segmentation fault 和 timeout）
* `test_malloc()` 和 `test_free()`
* 在 `harness.h` 中可以看到有 define 使用自定義的 `test_malloc()` 取代 `malloc()`、 `test_free()` 取代 `free()`
* 在 `harness.c` 的 `test_malloc()` 中會呼叫 `fail_allocation()` 根據現在的 `fail_probability` 機率回傳 `NULL` 。並將 malloc 的空間以 double linked list 儲存，以知道 malloc 了幾個 block (?，`test_free()` 也是從 linked list 去釋放空間
Sign in with Wallet
Connect another wallet