# 2018q3 Homework2 (lab0)
contributed by <[`yungchuan`](https://github.com/yungchuan)>

## 開發環境

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.5 LTS"

$ uname -a
Linux yungchuan-D830MT 4.15.0-34-generic #37~16.04.1-Ubuntu SMP Tue Aug 28 10:44:06 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 158
Model name:            Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
Stepping:              9
CPU MHz:               1394.599
CPU max MHz:           4200.0000
CPU min MHz:           800.0000
BogoMIPS:              7200.00
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d

## Github 設定
由於是第一次使用 github ，所以先進行相關設定
### ssh key
先設定本機端的 ssh key ，在終端機輸入以下指令

$ ssh-keygen -t rsa -C "[e-mail]"
$ ssh-agent -s
$ ssh-add ~/.ssh/id_rsa
$ cat < ~/.ssh/id_rsa.pub

依照顯示的訊息設定，最後會顯示出一串文字，就是 ssh key 。將這串 ssh key 複製到 github 上，就可以連結 github 與本機。
最後輸入以下指令驗證

$ ssh -T [e-mail]

輸入 yes ，看到`Hi yungchuan! You've successfully authenticated, but GitHub does not provide shell access.` 也就是說成功連上 github 了。

### fork 專案及安裝 git
* 將老師提供的 lab0-c 專案 fork 至我的 github
* 在本機端安裝 git
* 用 `git config --global user.email "[e-mail]"` 設定 email
* 用 `git config --global user.name "Your Name"` 設定使用者名稱
* 用 git clone 將專案複製到本機端進行修改

## 程式開發
### q_new 與 q_free
依照題目的需求完成

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if(!q) return q;
    q->head = NULL;
    return q;
}

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if(!q) return;
    list_ele_t *node = q->head;
    while(node){
        node = node->next;
        free(q->head);
        q->head = node;
    }
    free(q);
}

這邊主要的概念是：
* 若無法成功配置記憶體空間 (malloc return NULL) 則必須 return NULL。
* 必須檢查傳進來的 queue 本身是否為 NULL ，避免多餘的動作
* 要清空 linked list 必須將每個 node 的記憶體空間釋放

接著輸入

$ git add .
$ git commit -m "Implement the function new and free of queue"

將結果 commit 到 git 中

### q_insert_head 及 q_insert_tail
首先，看到要求 q_insert_tail 要在 O(1) 的時間內完成就知道在 queue_t 結構裡面應該需要別的參數，否則難以達到要求。所以藉此機會順便稍微瀏覽一下後面的 function ，發現還有 q_size ，同樣要求 O(1) 的時間，所以接著去修改 queue.h 檔案中 queue_t 的結構，如下：

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

既然動到了結構定義，就必須要先去看先前完成的函式是否需要更動。所以將 q_new 改寫如下：

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

而 q_free 的部份則不需要更動。
接著實做 q_insert_head 及 q_insert_tail 的部份

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if(!q) return false;
    newh = malloc(sizeof(list_ele_t));
    if(!newh) return false;
    newh->value = strdup(s);
    if(newh->value == NULL){
        free(newh);
        return false;
    }
    if(q->head == NULL) q->tail = newh;
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    return true;
}

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    if(!q) return false;
    newt = malloc(sizeof(list_ele_t));
    if(!newt) return false;
    newt->value = strdup(s);
    if(newt->value == NULL){
        free(newt);
        return false;
    }
    q->tail->next = newt;
    q->tail = newt;
    newt->next = NULL;
    q->size += 1;
    return true;
}

> 有個地方我不太懂，這裡的 insert 都使用到 strdup 這個 function ，而 strdup 的實做應該是藉由 malloc 去配置等量的記憶體空間在複製字串的，所以在刪除的時候必須要 free 其配置的空間。但是在 q_free 實做的時候，卻被測試程式 qtest 回報錯誤，而如果不用 free 則可以正確執行。但是我認為這應該不是正確的方式，所以在最後我會另外使用 malloc 重新撰寫這兩個函式以及隨之更改 q_free 還有後面會提到的 q_remove_head 的內容。

接著輸入

$ git add .
$ git commit -m "Implement the function both insert of queue"

### q_remove_head, q_size, and q_reverse

接著將剩下的 q_remove_head, q_size, 以及 q_reverse 實做出來：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if(!q || !(q->head)) return false;
    list_ele_t *node = q->head;
    q->head = q->head->next;
    if(!(q->head)) q->tail = NULL;
    if(sp){
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    free(node);
    q->size -= 1;
    return true;
}

int q_size(queue_t *q)
{
    if(!q) return 0;
    return q->size;
}

void q_reverse(queue_t *q)
{
    if(!q || !(q->head) || !(q->head->next)) return;
    list_ele_t *pre_node, *nxt_node;
    q->tail = q->head;
    nxt_node = q->head->next;
    do{
        pre_node = q->head;
        q->head = nxt_node;
        nxt_node = q->head->next;
        q->head->next = pre_node;
    }while(nxt_node);
    q->tail->next = NULL;
}

這邊要注意 strncpy 的操作，避免存取到超過預定的空間。
接著一樣 commit

$ git add .
$ git commit -m "Implement the function remove_head, size, and reverse of queue"

### 自動測試
先使用 `clang-format -i *.[ch]` 整理程式碼風格
使用 make test 來自動測試：

$ make test
gcc -O0 -g -Wall -Werror -c queue.c 
gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o
scripts/driver.py
---	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
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		100/100

### 將成果上傳
使用 `git push` 將結果傳回 github 上。

### 用 malloc 實做 insert
在 insert 的時候有發現，當使用 strdup 的時候，無法如預期的釋放其配置的記憶體空間，所以我決定改用 malloc 來實做 insert 函式，實做如下：

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc((strlen(s)+1)*sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->head == NULL)
        q->tail = newh;
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    return true;
}

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    if (!q)
        return false;
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
    newt->value = malloc((strlen(s)+1)*sizeof(char));
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);
    q->tail->next = newt;
    q->tail = newt;
    newt->next = NULL;
    q->size += 1;
    return true;
}

與原本的作法不同的地方在於，在第 9 行的地方，將原本的 strdup 改成 malloc 來配置記憶體，配置完記憶體以及檢查成功配置後，多加了第 14 行的字串複製，讓要 insert 的字串複製到 linked list 的 node 中；而 insert_tail 也是用一樣的概念實做。
接著因為用 malloc 實做了 insert ，所以在刪除的時候也就需要把配置的記憶體空間釋放。因此改寫 q_free 以及 q_remove_head 兩個函式如下：

void q_free(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *node = q->head;
    while (node) {
        node = node->next;
        free(q->head->value);
        free(q->head);
        q->head = node;
    }
    free(q);
}

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !(q->head))
        return false;
    list_ele_t *node = q->head;
    q->head = q->head->next;
    if (!(q->head))
        q->tail = NULL;
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    free(node->value);
    free(node);
    q->size -= 1;
    return true;
}

為了將配置的記憶體釋放，在第 8 行以及第 27 行加上了 free 來釋放配置給字串的記憶體。
如此就完成了用 malloc 以及 free 來處理字串的實做，一樣執行評分程式 `make test` 得到結果如下：

$ make test
gcc -O0 -g -Wall -Werror -c queue.c 
gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o
scripts/driver.py
---	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
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		100/100

這次的修改一樣通過評分程式的測試，接著一樣統一格式後執行 git

$ git add .
$ git commit -m "Change strdup to malloc"
$ git push

將結果上傳至 github 。