2018q3 HomeWork2 (lab0)
===
contributed by <[LiuJuiHung](https://github.com/LiuJuiHung)>
---
- [ ] 英文閱讀
- [ ] 準備 GNU/Linux 開發工具
- [ ] 學習使用 Git 與 GitHub
- [ ] 學習效能分析
- [ ] 研究自動測試機制
## 英文閱讀
[C Programing Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 學習使用 Git 與 GitHub
1. [GitHub 使用方法](http://wiki.csie.ncku.edu.tw/github)
2. 先建立出自己的 SSH key , 在 terminal 輸入以下指令
```
$ ssh-keygrn -t rsa -C "ray9956666@gmail.com"
$ ssh-agent -s
$ ssh-add ~/.ssh/id_rsa
```
3. 將電腦上的 SSH key (輸入以下指令)複製到 GitHub 的 SSH key 裡
```
$ cat ~/.ssh/id_rsa.pub
```
4. 在 terminal 中輸入以下指令驗證
```
$ ssh -T git@github.com
```
5. 本機安裝 git
6. [初次設定 Git](https://git-scm.com/book/zh-tw/v1/%E9%96%8B%E5%A7%8B-%E5%88%9D%E6%AC%A1%E8%A8%AD%E5%AE%9A-Git)
* `git config --global user.name "your_name"` 設定使用者名稱
* `git config --global user.email yourmail@example.com` 設定 email
7. 將老師提供的 lab0-c 作業 fork 到自己的 github
8. 在 terminal 輸入以下指令，將作業 git clone 下來
```
$ git clone git@github.com:LiuJuiHung/lab0-c.git
```
9. 程式碼更改後
* `git add .` 加入更改過的全部的檔案
* `git commit` 撰寫 commit message
* `git push` 將檔案 push 到 github 上
```
$ git add .
$ git commit
$ git push
```
---
### Makefile
了解 Makefile 運作
```C=1
CC = gcc
CFLAGS = -O0 -g -Wall -Werror
```
* CC 表示使用 gcc
* CFLAGS：宣告使用的參數
* -O：表示最佳化的程度
* -O 預設就是 -O1，你可以指定成 -O2 或 -O3 ，數字越大表示最佳化程度越好，但是會增加編譯時間
* -g：編入偵錯資訊
* 當使用 GDB 軟體進行偵錯，必須加入 -g 使 GDB 能夠讀取。一般情況下可以不用 -g，因為他也會增加 binary 大小
* -Wall：顯示警告訊息
* 使用這個參數會在編譯時顯示更多的警告訊息
* 這個參數相當有用，特別是找不到 libs/headers 之類的問題
* -Werror：將警告訊息轉為錯誤訊息
* [GCC 常用參數詳解](http://maxubuntu.blogspot.com/2010/02/makefile.html)
---
```C=1
GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest
```
* all：預設執行的目標，這裡包含 `GIT_HOOKS` 和 `qtest`
---
```C=1
$(GIT_HOOKS):
@scripts/install-git-hooks
@echo
```
* 確認是否有安裝 githooks
---
```C=1
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
```
* queue.o 的項目裡有 `queue.c`、`queue.h`、 `haeness.h`
* 輸入 `make qtest` 會依照 `CFLAGS` 所定義的參數進行編譯，編譯出一個 `qtest` 執行檔
---
```C=1
test: qtest scripts/driver.py
scripts/driver.py
clean:
rm -f *.o *~ qtest
rm -rf *.dSYM
(cd traces; rm -f *~)
```
* 執行 `make test` 會先查看是否有 `qtest` `scripts/driver.py` 這兩個檔案，若存在則執行 `driver.py` 測試並計算分數
* `clean` 是清除編譯出的 `*.o` `qtest` 和其他生成的檔案
## Queue 開發過程
題目敘述：
1. This program implements a queue supporting both FIFO and LIFO operations
2. It uses a singly-linked list to represent the set of queue elements
### Queue Structure
* 增加 queue 內的總數 size
* 增加 pointer to tail node
```C=1
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int q_size;
} queue_t;
```
### Create empty queue
* 為一個新的 queue 配置一個記憶體空間，將此空間初始化並回傳
```C=1
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->q_size = 0;
}
return q;
}
```
### Free all storage used by queue
* 主要目的：free 掉整個 queue 的空間
* 在 insert 每個 element 時，都會配置一個記憶體空間，因此利用 while 迴圈將每個 element 的記憶體空間循環的 free 掉
```C=1
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
if (!q)
return;
while(q->head)
{
list_ele_t *tmp = q->head;
q->head = tmp->next;
free(tmp);
}
free(q);
}
```
### Insert element at head of queue
* 主要目的：在前端 insert 一個新的 element
* 判斷 queue 是否為 NULL
* 利用 strdup() 將 s 複製到 newh->value
* 判斷為第一筆 element 時，tail pointer 要指向此 element
* q_size 要增加
```C=1
/*
Attempt to insert element at head of queue.
Return true if successful.
Return false if q is NULL or could not allocate space.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(queue_t *q, char *s)
{
if(!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
/* What should you do if the q is NULL? */
if(!newh)
return false;
if(newh)
{
newh->value = strdup(s);
if(q->q_size == 0)
{
q->tail = newh;
newh->next = NULL;
}
else
{
newh->next = q->head;
}
q->head = newh;
q->q_size++;
return true;
}
return false;
}
```
### Attempt to insert element at tail of queue
* 主要目的：在後端 insert 一個新的 element
* 判斷 queue 是否為 NULL
* 利用 strdup() 將 s 複製到 newt->value
* 判斷為第一筆 element 時，head pointer 要指向此 element
* q_size 要增加
```C=1
/*
Attempt to insert element at tail of queue.
Return true if successful.
Return false if q is NULL or could not allocate space.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
*/
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)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if(newt)
{
newt->value = strdup(s);
if(q->q_size == 0)
q->head = newt;
else
{
q->tail->next = newt;
}
newt->next = NULL;
q->tail = newt;
q->q_size++;
return true;
}
return false;
}
```
### Attempt to remove element from head of queue
* 主要目的：刪除前端的 element
* 判斷 sp 是否為 NULL
* 利用 strncpy() 將要被移除的 element 複製到 sp
* 並將此 element free
```C=1
/*
Attempt to remove element from head of queue.
Return true if successful.
Return false if queue is NULL or empty.
If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if(!q || !q->head)
return false;
if(sp)
{
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp);
q->q_size--;
return true;
}
return false;
}
```
### Return number of elements in queue
* 主要目的：回傳 queue 的 size
* 若 queue = NULL ，則回傳 '0'
* 將 element 的個數回傳
```C=1
/*
Return number of elements in queue.
Return 0 if q is NULL or empty
*/
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 0;
return q->q_size;
}
```
### Reverse elements in queue
* 將 element 反轉
```C=1
/*
Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
It should rearrange the existing ones.
*/
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if(!q || !q->head)
return;
list_ele_t *cur, *next, *pre, *shead, *stail;
shead = q->head;
stail = q->tail;
next = q->head->next;
cur = q->head;
while(next)
{
pre = cur;
cur = next;
next = next->next;
cur->next = pre;
}
q->head = stail;
q->tail = shead;
q->tail->next = NULL;
}
```
### 評分結果
```
$ make test
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-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
```
## 自動評分系統運作原理
當執行 `$ make test` 時，會執行 `Makefile` 裡的以下這段程式
```
test:qtest scripts/driver.py
scripts/driver.py
```
Sign in with Wallet
Connect another wallet