# 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))。

CC = gcc
CFLAGS = -O0 -g -Wall -Werror

* 在 `all` target 裡的相依性項目有 `GIT_HOOKS` 與 `qtest` ，前者會透過 script 去檢查是否有安裝 git hook 需要的套件並安裝上 git hook ，後者 `qtest` target 則會繼續照法則往下去找相依性項目。

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` ，一個可執行檔。

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` 則會清除過程中產生的多餘檔案。

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.

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` 初始化。

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 去尋訪佇列中的每一個節點並釋放它，最後再釋放佇列。

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++`。

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` 而非從頭開始。

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` 。

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` 並回傳就好。

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` 指標

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` 。
:::

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` 參數 :

    $ ./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` 可以看到其節點結構為下 :

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 的話就可以省去許多冗長的程式碼，例如 :

switch(cmd) {
    case "add" :
        add();
        break;
    case "remove" :
        remove();
        break;
    case "reverse" :
        reverse();
        break;
}

使用 linked list 可以改為 :

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()` 就可以見到其用法 :

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` 一發生問題，就會產生這些錯誤訊息的原因。

/* 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");
}