# 2019q3 Homework2 (lab0)
contributed by < `Shengyuu` >

## 說明

- [作業要求](https://hackmd.io/s/BJA8EgFB4)
- [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

## 實驗環境

$ uname -a
Linux yao 4.15.0-45-generic #48-Ubuntu SMP Tue Jan 29 16:28:13 UTC 2019 x86_64 x86_64 x86_64 GNU/Linu
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

## 作業需求
### 實作 FIFO & LIFO Queue

- 要求
- `q_new`: 新增一空的 queue
- `q_free`: 清除 queue
- `q_insert_head`: 在 queue 的頭插入一元素（LIFO)
- `q_insert_tail`: 在 queue 的尾插入一元素（FIFO)
- `q_remove_head`: 移除 queue 的開頭元素並輸出
- `q_size`: 回傳 queue 有多少個元素
- `q_reverse`: 反轉 queue 中元素的順序
--- 以上節錄自 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
- 注意
- 傳入的 queue 是否為 NULL
- malloc 是否成功
- malloc 後記憶體的歸還
- `q_insert_tail` ＆ `q_size` 的複雜度要是 $O(1)$

## 實作
### 程式碼說明：
- ### `queue.h`
- 為了達成作業要求，讓 `q_insert_tail` & `q_size` 的複雜度為 $O(1)$，在 struct 裡面新增 head, size 兩元素

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

- ### `queue_new()`
- 新建一大小為 0 的 queue ，且 head、tail皆指向 NULL
- **若 malloc 失敗要回傳 NULL**

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return NULL;
    else {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
        return q;
    }
}

:::danger
注意程式碼縮排風格是 4 個空白字元和 K&R，連同共筆列出的程式碼也需要變更
:notes: jserv
:::

- ### `q_free()`
- queue 為 element 陣列，而 element 陣列中含有一 char 陣列，因此在清除 queue 時需將此兩陣列的空間歸還
- **注意傳入的 queue 是否為 NULL**
- **若該 element 的 value 為 NULL 則不能 free**

void q_free(queue_t *q)
{
    if (q) {
        list_ele_t *tmp = q->head;
        while (q->head) {
            if (q->head->value)
                free(q->head->value);  // avoid free NULL
            q->head = q->head->next;
            free(tmp);
            tmp = q->head;
        }
        /* Free queue structure */
        free(q);
    }
}

- ### `q_insert_head()`
- 為了將傳近來的 char 陣列 s 插入 queue 中，我們必須新建一個 list_ele_t 的實體 newh ，將 s 複製進 newh 後再將 newh 插入 queue 的開頭
- 新建實體，而用到了 malloc 動態配置記憶體，注意若陣列 s 是空的，則要將 newh 分配的記憶體歸還回去
:::warning
注意：程式碼的排版有明確要求，在 HackMD 和 GitHub 都嚴格遵守，請留意。需要變更本共筆所有程式列表 (可自 GitHub 的分支上複製)
:notes: jserv
:::
> 已更改
> [name=Shengyuu]

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) {
        printf("The queue is NULL\n");
        return false;
    }
    /* What should you do if the q is NULL, malloc is NULL and s is NULL? */
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    /* fail to malloc*/
    if (!newh) {
        printf("Fail to allocate list\n");
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    /* fail to malloc*/
    if (!newh->value) {
        printf("Fail to allocate value\n");
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    /* queue is empty before insert*/
    if (q->size == 0) {
        newh->next = NULL;
        q->size++;
        q->head = newh;
        q->tail = newh;
        return true;
    } else {
        newh->next = q->head;
        q->head = newh;
        q->size++;
        return true;
    }
}

> 一開始將三種需要 return false 的可能寫在同一個 if case 裡面統一判斷，但 qtest 一直出現 error 訊息，後來才想到若第一次 malloc 給 newh 記憶體 失敗的話，第二次 malloc 給 newh->value 記憶體就會是個有問題的寫法

- ### `q_insert_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 */
    if (!q) {
        printf("The queue is NULL\n");
        return false;
    }
    list_ele_t *newt = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newt) {
        printf("Fail to allocate list\n");
        return false;
    }
    newt->value = malloc(strlen(s) + 1);
    if (!newt->value) {
        printf("Fail to allocate value\n");
        free(newt);
        return false;
    }
    strcpy(newt->value, s);
    if (!q->size) {
        q->size++;
        newt->next = NULL;
        q->head = newt;
        q->tail = newt;
        return true;
    } else {
        q->size++;
        newt->next = NULL;
        q->tail->next = newt;
        q->tail = newt;  // error
        return true;
    }
}

◎**第一次完成這個 function 時只記得做 q->tail->next = newt ，而忘了 q->tail = newt ，造成tail都沒有被更新到**

- ### `q_remove_head()`
- 這裡除了要檢查傳入的 queue 是否為 NULL 之外，還要多檢查 q->head 是否為空，一樣要注意不能將這些檢查工作放在同一個 if case 內，若 q 為 NULL 則 q->head 就會是個有問題的指令
- 按照作業的要求，即使傳入的 sp 為 NULL ，我們還是需要將 queue->head 做移除的動作
- 這裡一樣記得要作兩次 free 的動作，將 value、element 的空間都歸還

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q) {
        printf("The queue is NULL\n");
        return false;
    }
    if (!q->head) {
        printf("The head is NULL\n");
        return false;
    }
    if (!sp) {
        printf("sp is NULL\n");
    }
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    if (q->size == 1) {
        q->size--;
        free(q->head->value);
        free(q->head);
        q->head = NULL;
        q->tail = NULL;
        return true;
    } else {
        list_ele_t *tmp = q->head;
        q->size--;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
        return true;
    }
}

◎ **在做 free(q->head->value) 的時候若 value 的值為 NULL 應該未出問題**----待修改

- ### `q_size()`
- 檢查傳入的 queue 是否為 NULL，若否則直接回傳 size

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (!q)
        return false;
    return q->size;
}

- ### `q_reverse()`
- 對 queue 做翻轉，需要修改 queue 中的兩個元素，分別為 head、tail ，而修改 head、tail 指向的 element 時只需修改其中的 next ，不需要修改 value 的部份。
- 因為我們設計的 element 裡面只有存取下一筆資料的位置（next)，而沒有存取上一筆資料，所以在將資料拿出的時候一定得從開頭開始拿，也因此在做 reverse 的時候我們需要以"這筆資料的下一筆資料的 next 會指向這筆資料"的邏輯去實踐

void q_reverse(queue_t *q)
{
    if (!q) {
        printf("The queue is NULL\n");
    } else {
        int count = q->size;
        if (count > 0) {
            q->tail = q->head;
            list_ele_t *tmp_ele;
            list_ele_t *tmp_ele_next;
            tmp_ele = NULL;
            while (count > 0) {
                tmp_ele_next = tmp_ele;
                tmp_ele = q->head;
                q->head = q->head->next;
                tmp_ele->next = tmp_ele_next;
                count--;
            }
            q->tail->next = NULL;
            q->head = tmp_ele;
        } else
            printf("queue is empty\n");
    }
}

◎ **剛開始完成這段程式碼的時候是將 q->head = q->head->next 寫在下面一行 tmp_ele... 的後面，編譯後 qtest 顯示 error ，回去檢查程式碼才發現 q->head... 一定要寫在前面，因為此時的 tmp_ele 和 q->head 是除存同一個記憶體位置的，若先將 tmp_ele->next 改掉，就沒辦法找到我們要的下一筆資料了**

:::warning
避免用「噴出」這種語意不明的詞彙，改為「qtest 顯示...」
:notes: jserv
:::
>已更改
>[name=Shengyuu]

### 驗證程式碼：

$make test


## 自動評分系統

### Makefile
在終端機上輸入 `$make test` 即可使用自動評分系統，第一步先去 Makefile 內看 `test` 做了什麼事

test: qtest scripts/driver.py
         scripts/driver.py

從這裡可以看出來當我們在下指令 `make test` 的時候其實是去執行 `scripts/driver.py` ，下一步去看 `driver.py` 做了些什麼

### driver
在 `driver.py` 中主要執行 test 的部份都被包在 class Tracer 內， `run` 函式只負責處理參數、創建 class Tracer 和呼叫 Tracer 內的 `run` 函式 ，下面程式碼是 `run` 函式創建 class Tracer 程式碼

t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde, useValgrind = useValgrind)
     t.run(tid)

#### class Tracer
Tracer 最前面將測試檔案的路徑以及每小題的分數都存在陣列型態的變數中，如下：

traceDirectory = "./traces"
...
...
...
traceDict = { 
         1 : "trace-01-ops",
         2 : "trace-02-ops",
         3 : "trace-03-ops",
         4 : "trace-04-ops",
         5 : "trace-05-ops",
         6 : "trace-06-string",
         7 : "trace-07-robust",
         8 : "trace-08-robust",
         9 : "trace-09-robust",
         10 : "trace-10-malloc",
         11 : "trace-11-malloc",
         12 : "trace-12-malloc",
         13 : "trace-13-perf",
         14 : "trace-14-perf",
         15 : "trace-15-perf"
         }
...
...
...
maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

Trce 的邏輯則是透過物件內的 `run` 函式以 for 迴圈的方式將每筆資料都送進 `runTrace` 函式進行 Trace 的動作，如下：

for t in tidList:
             tname = self.traceDict[t]
             if self.verbLevel > 0:
                 print("+++ TESTING trace %s:" % tname)
             ok = self.runTrace(t)
             maxval = self.maxScores[t]
             tval = maxval if ok else 0

`runTrace` 函式內透過 `clist` 變數儲存執行 qtest 的命令，並透過 subprocess 的技巧創建一個子進程執行 qtest，程式碼如下：

     def runTrace(self, tid):
         if not tid in self.traceDict:
             print("ERROR: No trace with id %d" % tid)
             return False
         fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
         vname = "%d" % self.verbLevel
         clist = [self.command, self.qtest, "-v", vname, "-f", fname]
         print("%s" % " ".join(clist))
         try:
             retcode = subprocess.call(clist)
         except Exception as e:
             print("Call of '%s' failed: %s" % (" ".join(clist), e))
             return False
         return retcode == 0

clist 儲存的命令如下：

./qtest  -v 1 -f ./traces/trace-01-ops.cmd

### qtest
qtest 才是整個自動評分系統的主體，系統將測試時會用到的 function 都當成一個一個 cmd ，並且給予每個 cmd 獨有的 name 和 documents ，將這些資料都存在 `struct cmd_ptr` 中並用 linked list 結構將所有 cmd 串接起來，`struct cmd_ptr` 如下：

/* Organized as linked list in alphabetical order */  
 typedef struct CELE cmd_ele, *cmd_ptr;  
 struct CELE {                 
     char *name; 
     cmd_function operation;       
     char *documentation; 
     cmd_ptr next;              
 };   

#### cmd 的建立
利用 `add_cmd` 函式將 cmd 串接在全域變數 `cmd_list` ， `qtest.c` 提供一些對 queue 進行操作的 cmd 如下：

static void console_init()
 {
     add_cmd("new", do_new, "                | Create new queue");
     add_cmd("free", do_free, "                | Delete queue");
     add_cmd("ih", do_insert_head,
             " str [n]        | Insert string str at head of queue n times "
             "(default: n == 1)");
     add_cmd("it", do_insert_tail,
             " str [n]        | Insert string str at tail of queue n times "
             "(default: n == 1)");
     add_cmd("rh", do_remove_head,
             " [str]          | Remove from head of queue.  Optionally compare "
             "to expected value str");
     add_cmd(
         "rhq", do_remove_head_quiet,
         "                | Remove from head of queue without reporting value.");
     add_cmd("reverse", do_reverse, "                | Reverse queue");
     add_cmd("size", do_size,
             " [n]            | Compute queue size n times (default: n == 1)");
     add_cmd("show", do_show, "                | Show queue contents");
     add_param("length", &string_length, "Maximum length of displayed string",
               NULL);
     add_param("malloc", &fail_probability, "Malloc failure probability percent",
               NULL);
     add_param("fail", &fail_limit,
               "Number of times allow queue operations to return false", NULL);
 }

`console.c` 也提供了一些和 queue 無關的操作，如下：

void init_cmd()
   {
       cmd_list = NULL;
       param_list = NULL;
       err_cnt = 0;
       quit_flag = false;
       add_cmd("help", do_help_cmd, "                | Show documentation");
       add_cmd("option", do_option_cmd,
               " [name val]     | Display or set options");
       add_cmd("quit", do_quit_cmd, "                | Exit program");
       add_cmd("source", do_source_cmd,
               " file           | Read commands from source file");
       add_cmd("log", do_log_cmd, " file           | Copy output to file");
       add_cmd("time", do_time_cmd, " cmd arg ...    | Time command execution");
       add_cmd("#", do_comment_cmd, " ...            | Display comment");
       add_param("verbose", &verblevel, "Verbosity level", NULL);
       add_param("error", &err_limit, "Number of errors until exit", NULL);
       add_param("echo", &echo, "Do/don't echo commands", NULL);
   #if 0
       add_param("megabytes", &mblimit, "Maximum megabytes allowed", NULL);
       add_param("seconds", &timelimit, "Maximum seconds allowed",
                 change_timeout);
   #endif
       init_in();
       init_time(&last_time);
       first_time = last_time;
   }

#### cmd 的執行

qtest 的 `main` 函式將基本的參數初始化後會呼叫 `run_console` 函式， `run_console` 函式用 while 迴圈包住 `cmd_select` 函式，直到使用者 quit 才會離開，`run_console` 函式如下：

   bool run_console(char *infile_name)
   {
       if (!push_file(infile_name)) {
           report(1, "ERROR: Could not open source file '%s'", infile_name);
           return false;
       }
       while (!cmd_done()) {
           cmd_select(0, NULL, NULL, NULL, NULL);
       }
       return err_cnt == 0;
   }

`cmd_select` 會呼叫 `read_line` 函式將指令 parse 出來，並透過 `interpret_cmd` 函式在 cmd_list 中搜尋對應指令且執行，下面為搜尋指令過程的程式碼：

   static bool interpret_cmda(int argc, char *argv[])
   {
       if (argc == 0)
           return true;
       /* Try to find matching command */
       cmd_ptr next_cmd = cmd_list;
       bool ok = true;
       while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
           next_cmd = next_cmd->next;
       if (next_cmd) {
           ok = next_cmd->operation(argc, argv);
           if (!ok)
               record_error();
       } else {
           report(1, "Unknown command '%s'", argv[0]);
           record_error();
           ok = false;
       }
       return ok;
   }

###### tags: `進階電腦系統理論與實作 (Fall 2019)`
###### tags: `Linux 核心設計 2019`