# 2018q3 Homework2 (lab0)
contributed by <`brian208579`>

## 測試環境

bri@bri-BM6820-BM6620-BP6320-Invalid-entry-length-16-Fixed-up-to-11:~$ cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.5 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.5 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

## 作業預期
- 複習 Link list 並加強實作觀念
- 實作 q_new
- 實作 q_free
- 實作 q_insert_head
- 實作 q_insert_tail
- 實作 q_remove_head
- 實作 q_size
- 實作 q_reverse
- 了解 qtest 行為

### Introduction to Computer Systems (ICS) 的第一份作業

CMU [Introduction to Computer Systems (ICS)](http://www.cs.cmu.edu/~213/index.html) 準備了 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 作為檢閱學生 C 語言程式設計的認知:
* Explicit memory management, as required in C.
* Creating and manipulating pointer-based data structures.
* Working with strings.
* Enhancing the performance of key operations by storing redundant information in data structures.
* Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

實驗目標為實作 queue
* first in, first out (FIFO)
* last in, first out (LIFO)

### 自動評分系統

`qtest` 執行檔內有包裝許多測試這次作業可用的工具，執行 `qtest` 後可打 `help` 即有各指令解說

make
./qtest
cmd>help
Commands:
        #        ...            | Display comment
        free                    | Delete queue
        help                    | Show documentation
        ih       v [n]          | Insert v at head of queue n times (default: n == 1)
        it       v [n]          | Insert v at tail of queue n times (default: n == 1)
        log      file           | Copy output to file
        new                     | Create new queue
        option   [name val]     | Display or set options
        quit                    | Exit program
        reverse                 | Reverse queue
        rh       [v]            | Remove from head of queue.  Optionally compare to expected value v
        rhq      [v]            | Remove from head of queue without reporting value
        show                    | Show queue contents
        size     [n]            | Compute queue size n times (default: n == 1)
        source   file           | Read commands from source file
        time     cmd arg ...    | Time command execution
Options:
        echo    1       Do/don't echo commands
        error   5       Number of errors until exit
        fail    30      Number of times allow queue operations to return false
        malloc  0       Malloc failure probability percent
        verbose 4       Verbosity level

qtest 使用範例:

# 確認目前 queue 內容（一開始應該是空的 q = NULL）
show
# 新建一個 queue (q = [])
new
# 在 head 新增數值
ih 2
ih 1
ih 3
# 結果：
#q = []
#cmd>ih 1
#cmd>ih 1
#q = [1]
#cmd>ih 2
#cmd>ih 2
#q = [2 1]
#cmd>ih 3
#cmd>ih 3
#q = [3 2 1]
# 現在從尾巴加（應該會失敗因為還沒實作)
it 5
4
it 1
# 反轉 queue, 算長度, 釋放記憶體等..（應該都會失敗因為還沒實作)
reverse
size
free
# 離開
quit

* 計算得分：

make test

## < 過程 >

- **q_new**

依照提示去思考，如果malloc失敗時該如何 ?

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)  // 如果q=NULL，代表malloc失敗，故回傳fales
    {
        return NULL;
    } 
    else 
    {
        q->tail = NULL;
    }
    q->head = NULL;
    q->size = 0;
    return q;
}

- **q_insert_head**

依照提示去思考
如果 q 為 NULL 時該如何處理 ?
如果 malloc 失敗該如何處理 ?
別忘了分配空間給字串和複製他們

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false; }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {       // 如果newh=NULL，代表malloc失敗，故回傳fales
        return false; }

    newh->value = strdup(s);  // new 的 value 為你輸入的值
    newh->next = q->head;     // q 的 next = 原本的 head
    q->head = newh;           // newh = 新的 head

    if (q->size == 0)         // 如果 q 裡面沒有 node
    {
        q->tail =
            newh;  // q 的 head 就等於 q 的 tail ( 此時的 newh = q 的 head )
    }
    q->size += 1;  // 計算 q 裡面目前有幾個 node
    return true;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
}

- **q_insert_tail**

與 inster_head 大同小異，故無太大問題

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        return false; }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {       // 如果newh=NULL，代表malloc失敗，故回傳fales
        return false; }
    newh->value = strdup(s);  // new 的 value 為你輸入的值
    newh->next = NULL;     // 因是從 tail 開始加，故新增加的 newh 的 next 要為 NULL
    if (q->size == 0) {    // 如果 q 裡面沒有 node
        q->head = newh; }    // q 的 head 就為 newh
    else { 
           q->tail->next = newh; }   // q 的 tail 的 next 指向 newh
    q->tail = newh;    // newh 為新的 tail
    q->size += 1;
    return true;
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
}

- **q_free**

void q_free(queue_t *q)
{
    if (q == NULL) {
        return; 
    }    
    list_ele_t *t, *c;
    c = q->head;
    while (c != NULL) {
        t = c;
        c = c->next;
        free(t); }
    if (q != NULL) {
        free(q);
    }
}

- **q_remove_head**

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0) {
        return false;
    }
    list_ele_t *aa;
    aa = q->head;
    if (sp == NULL) {
        return false;
    }
    strncpy(sp, q->head->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    q->head = q->head->next;
    free(aa);
    q->size -= 1;
    return true;
}

- **q_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 == NULL) {
        return 0;
    }
    return q->size;
}

- **q_reverse**

修改前原本的程式碼為

    if (q == NULL || q->size <= 1) {
        return;
    }
    
    list_ele_t *pre = NULL; 
    list_ele_t *cur = q->head;
    list_ele_t *temp = q->head->next;
    
    q->tail = q->head;

    while (temp != 0) {
        pre = cur->next;
        pre = cur;
        cur = temp;
        temp = temp->next;
    }
    cur->next = pre;
    q->head = cur;

不過 make test 後卻只得到 67 分，之後參考一些同學們的程式碼後，把程式碼更改為以下

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q || q->size == 0)
        return;

    list_ele_t *pre = NULL, *temp, *cur = q->head;
    q->tail = q->head;

    while (cur != NULL) {
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    q->head = pre;
}

### 實作驗證測試結果


### 探討 qtest 行為

:::warning
待更新中。。。
:::