# 2018q3 Homework2 (lab0)
contributed by < `littlepee` >
>請補上實驗環境
>[name=課程助教][color=red]
## [E01:lab0](https://hackmd.io/s/BJp_jq-tm)

## GitHub
- 先把 [lab0-c](https://github.com/sysprog21/lab0-c) fork 到自己的 GitHub
- 參照 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github) ，榜定好 SSH Key
- 在 terminal 輸入 `ssh -T [e-mail]` 檢查是否成功榜定

## [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

- [你所不知道的 C 語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf)

### queue.h

- 先定義好 queue_t ，增添 q_tail 以及 q_size

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 *q_tail;
    int q_size;
} queue_t;

### q_new

- 開新的 q 就先幫它 initialization 好
- 增添:如果 malloc 失敗，就回傳 NULL

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)  // Return NULL if could not allocate space
        return NULL;
    q->head = NULL;

    q->q_tail = NULL;
    q->q_size = 0;

    return q;
}

### q_free

- 先判斷 head 是否為 NULL ，若不為 NULL ，則清掉該個 element ，並指向下一個 ，重複動作，直到 head 為 NULL ，則代表已全部清空
- 增添:如果 q 為 NULL ，就直接跳回

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    while (q->head) {
        list_ele_t *tmp = (q->head);
        q->head = (q->head)->next;
        free(tmp);
    }
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    free(q);
}

### q_insert_head

- 判斷 q 是否為 NULL
- 新開的 element 的 next 指向原本 head 所指向的 element
- head 指向新開的 element
- q_size + 1
- 增添: malloc 失敗，就回傳 false
- 增添: 當 q 是空的時

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)  // Return false if q is NULL
        return false;

    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)  // could not allocate space
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;

    newh->value = strdup(s);
    if (q->q_size == 0) {
        q->q_tail = newh;
    }

    q->head = newh;
    (q->q_size)++;

    return true;
}

### q_insert_tail

- 判斷 q 是否為 NULL
- 新開的 element 的 next 須指向 NULL
- 原本的 q_tail 指向新開的 element ，使之成為新的尾巴
- q_size + 1
- 增添: malloc 失敗時，接回傳 false

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 == NULL)  // Return false if q is NULL
        return false;

    list_ele_t *new;
    new = malloc(sizeof(list_ele_t));
    if (new == NULL)  //  could not allocate space
        return false;

    new->next = NULL;
    new->value = strdup(s);
    if (q->q_size == 0) {
        q->head = new;
    } else {
        q->q_tail->next = new;
    }

    q->q_tail = new;
    q->q_size++;

    return true;
}

### q_remove_head

- 判斷 q 是否為 NULL
- 判斷 sp 是否為 NULL ，若不為 NULL ，則將被刪除的 element copy 到 sp
- man strncpy 來確定一下 strcpy 與 strncpy 的差別
- q_size - 1
- 增添: q 是空的時候
- 增添: free 掉應被刪除的 element 所佔的空間

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if ((q == NULL) ||
        (q->q_size == 0))  // Return false if queue is NULL or empty.
        return false;

    if (sp) {  // If sp is non-NULL
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        int string_size = strlen(tmp->value);
        string_size =
            (string_size > (bufsize - 1))
                ? (bufsize - 1)
                : string_size;  // up to a maximum of bufsize-1 characters
        strncpy(sp, tmp->value, string_size);  // copy the removed string to *sp
        sp[string_size] = '\0';                // plus a null terminator
        free(tmp);
        q->q_size--;
        return true;
    }

    return false;
}

### q_size

- 直接回傳 q_size ，來達到 O(1) 的執行時間
- 增添: q 為 NULL

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 if q is NULL
        return 0;
    return q->q_size;
}

### q_size

- 判斷 q 是否為 NULL 或為空的
- 使用三個 pointer to list_ele_t 來分別指向下一個、現在、上一個 element ，完成反轉的功能

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if ((q == NULL) || (q->q_size == 0))  // No effect if q is NULL or empty
        return;

    list_ele_t *next_element;
    list_ele_t *current = q->head;
    list_ele_t *previous = NULL;

    q->q_tail = q->head;

    while (current) {
        next_element = current->next;
        current->next = previous;
        previous = current;
        current = next_element;
        q->head = previous;
    }
}

## 目前進度

- 除了 q_reverse 以外其他 function 皆打上
- 目前只有7分，還有很多地方需要調整

TOTAL		7/100

- 修正回傳值，例如當 malloc 失敗時，以及 q 為 NULL 時
- 在 q_remove_head 中， free 掉應被刪除的 element 所佔的空間

TOTAL		48/100

- 在 q_insert_head 中，增加 q 是空的的案例

TOTAL		81/100

- 加入 q_reverse

TOTAL	    100/100

## 實驗環境

fs@fs-ubuntu:~/lab0-c$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="16.04.3 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.3 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
fs@fs-ubuntu:~/lab0-c$ cat /proc/version
Linux version 4.10.0-28-generic (buildd@lgw01-12) (gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4) ) #32~16.04.2-Ubuntu SMP Thu Jul 20 10:19:48 UTC 2017

## Makefile

- 參考
- [簡單學 makefile：makefile 介紹與範例程式](http://mropengate.blogspot.com/2018/01/makefile.html)

- [make - 維基百科](https://zh.wikipedia.org/wiki/Make)

- make 會在當前目錄下按順序找尋文件名為 GNUmakefile、makefile 或 Makefile 的文件
- target（要生成的文件）: dependencies（被依賴的文件），換行後先用一個 TAB ，才開始打要執行的命令
- target擺放的顺序不重要，但第一个target是默认的target
- 宣告參數時使用 " = " 或 " := " 給予初始值，當要被使用時，則用 " (obj) " 或 " {obj} "

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

在作業中我們使用 ``` $make test ``` 來進行評分，代表要執行 test 這個 target ，需要使用到 qtest 以及 scripts/driver.py ，其命令為執行 scripts/driver.py。而恰巧 qtest 為另外一個 target ，所以需要將 qtest 這個 target 的部份完成。