2018q3 Homework2 (lab0)

2018q3 Homework2 (lab0) === contributed by < [`TerryShu`](https://github.com/TerryShu) > --- [lab0](https://hackmd.io/s/BJp_jq-tm) 目標: - [ ] 英文閱讀 - [ ]C 語言程式設計基礎 - [ ]準備 GNU/Linux 開發工具 - [ ]學習使用 Git 與 GitHub - [ ]學習效能分析 - [ ]研究自動測試機制 --- 英文閱讀 --- [C Programming Lab: Assessing Your C Programming Skill](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) --- 準備 GNU/Linux 開發工具 --- ### 環境 ``` $ cat /etc/os-release NAME="Ubuntu" VERSION="18.04.1 LTS (Bionic Beaver)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 18.04.1 LTS" VERSION_ID="18.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=bionic UBUNTU_CODENAME=bionic ``` --- 學習使用 Git 與 GitHub --- 先建立 SSH key 然後上傳綁定 ``` $ ssh-keygen -t rsa -C "wind850101@gmail.com" Generating public/private rsa key pair. Enter file in which to save the key (/home/terry/.ssh/id_rsa): Enter passphrase (empty for no passphrase): Enter same passphrase again: Your identification has been saved in /home/terry/.ssh/id_rsa. Your public key has been saved in /home/terry/.ssh/id_rsa.pub. ``` ![](https://i.imgur.com/lNNnt38.png) 將此次作業clone下來 ``` $ git clone https://github.com/TerryShu/lab0-c.git ``` Makefile --- 可以透過 `Makefile` 了解此次作業的流程 ```clike= CC = gcc CFLAGS = -O0 -g -Wall -Werror ``` * 此兩行是在宣告變數 `CC` 代表使用 GNU 的 `gcc` * `CFLAGS` 是在宣告使用的參數 * `-O` 是表示使用最佳化的程度 `-O0` 表示沒有進行優化還有 `-O1` `-O2` `-O3` ，`O3` 是優化程度最高 * `-g` 代表編入除錯的資訊（使用GDB時使用） * `-Wall` 代表顯示所有的 Warnings * `-Werror` 將所有 Warnings 轉為 errors ```clike= GIT_HOOKS := .git/hooks/applied all: $(GIT_HOOKS) qtest $(GIT_HOOKS): @scripts/install-git-hooks @echo ``` * 在 `all` 的相依項目裡面有 `GIT_HOOKS` 和 `qtest` * `GIT_HOOKS` 會透過 script 去檢查是否有安裝過 git-hook 若沒有則安裝 * `qtest` 則會往下找到 `qtest` 對應的執行方法 ```clike= 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` `harness.c` * `queue.c` `queue.h` 是本次作業的核心，裡面將此次的架構規劃出來，包含資料的結構以及所需要用到的 function 等 * `harness.h` 則是提供了這次作業會用到的 `malloc()` 和 `free()` * 輸入 `make qtest` 後會執行 `qtest` 會依照上面的 `CC` `CFLAGS` 定義的編譯器以及參數去編譯出一個 `qtest` 的執行檔 ```clike= test: qtest scripts/driver.py scripts/driver.py ``` * `test` 的相依項目有 `qtest` `scripts/driver.py` 會先檢查這兩個項目是否存在，若存在則執行 `driver.py` 去測試並計算分數 ```clike= clean: rm -f *.o *~ qtest rm -rf *.dSYM (cd traces; rm -f *~) ``` * `clean` 清除編譯完後的 `.o` 檔和 `qtest` 執行檔以及一些執行過程中生成的檔案 lab0 --- ### 題目敘述 ```clike= /* * This program implements a queue supporting both FIFO and LIFO * operations. * * It uses a singly-linked list to represent the set of queue elements */ ``` * 要實作一個 queue 同時支援 FIFO 和 LIFO * 用 singly-linked list ### 資料結構 ```clike= typedef struct ELE { /* Pointer to array holding string. This array needs to be explicitly allocated and freed */ char *value; struct ELE *next; } list_ele_t; /* Queue structure */ 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 *tail; // ptr to the tail of queue size_t size; // the size of queue } queue_t; ``` * 因為題目要求新增移除 `tail` 故增加一個 `*tail` 指向此 `queue` 的 `tail` 以便進行新增移除的操作 * 題目要求須回傳 `queue` 的長度，故新增 `size` 紀錄此queue長度 ### 開發過程 #### `q_new` ```clike= queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); /* What if malloc returned NULL? */ if (q == NULL) return NULL; // if malloc fail return NULL q->head = NULL; // if malloc success do init q->tail = NULL; q->size = 0; return q; } ``` * 一開始先判斷此 `queue` 是否被配置成功 * 若成功則對 `head` `tail` `size` 進行初始化，若失敗則 `return NULL` #### `q_free` ```clike= void q_free(queue_t *q) { /* How about freeing the list elements and the strings? */ /* Free queue structure */ if (q != NULL) { list_ele_t *removePtr; while (q->head != NULL) { removePtr = q->head; q->head = q->head->next; free(removePtr); } // free from the head of queue free(q); } } ``` * 此段程式碼為把 `queue` 配置的空間 `free` 掉 * 設置一個 `removePtr` 做為移除的 pointer * 從原先 `queue` 所指的 `head` 開始向後移除每個 node * 最後移除 `queue` 的空間 #### `q_insert_head` ```clike= bool q_insert_head(queue_t *q, char *s) { if (q != NULL) { list_ele_t *newh; /* What should you do if the q is NULL? */ newh = malloc(sizeof(list_ele_t)); /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ if (newh != NULL) { newh->value = strdup(s); if (q->head == NULL && q->tail == NULL) { // insert first node newh->next = NULL; q->head = newh; q->tail = newh; } else { newh->next = q->head; q->head = newh; } q->size++; return true; } } return false; // if malloc fail or q is NULL return false } ``` * 在 `insert_head` 前先判斷此 `queue` 是否存在 * 接著判斷是否有成功 `malloc` 出一個空間給 `newh` 使用 * 若成功 `malloc` 出一個 `newh` 的空間則開始更改 `head` * 此處要注意若為第一個 `node` 則 `tail` 也需要更改 * 新增成功後更新 `q->size` #### `q_insert_tail` ```clike= 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) { list_ele_t *newt; newt = malloc(sizeof(list_ele_t)); if (newt != NULL) { newt->value = strdup(s); if (q->head == NULL && q->tail == NULL) { // insert first node newt->next = NULL; q->head = newt; q->tail = newt; } else { q->tail->next = newt; newt->next = NULL; q->tail = newt; } q->size++; return true; } } return false; // if malloc fail or q is NULL return false } ``` * 與 `insert_head` 基本相同 * 一樣須注意第一個 `node` 需同時修改 `head` 和 `tail` 所指向的位置 * 需注意要將 `newt->next` 指向 `NULL` 否則下次使用 `insert_tail` 時會發生錯誤 :::warning 操作指標要小心忘記更改時很容易發生錯誤 ::: #### `q_remove_head` ```clike= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { /* You need to fix up this code. */ if (q != NULL && q->head != NULL) { list_ele_t *removePtr = q->head; if (sp != NULL) { memcpy(sp, removePtr->value, bufsize); // copy the removed string to *sp sp[bufsize - 1] = '\0'; // plus a null terminator } q->size--; q->head = q->head->next; // move head to next node free(removePtr); // free remove node return true; } return false; } ``` * 根據題目要求移除的同時需同時記錄移除 `node` 所儲存的值 * 一開始先判斷 `queue` 和 `head` 是不是 NULL * 若不是，設置一個 `removePtr` 指向 `head` * 使用 `memcpy` 複製將被移除的節點的值 * 更新 `q->size` #### `q_size` ```clike= 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; } ``` * 因為在 `insert` 和 `remove` 內有維護 `q->size` * 所以只需簡單判斷 `queue` 是否為 `NULL` 後決定是回傳 0 或是 `q->size` #### `q_reverse` ```clike= void q_reverse(queue_t *q) { /* You need to write the code for this function */ if (q != NULL && q->size != 0) { list_ele_t *cur = q->head; // current ptr point to queue head list_ele_t *nxt = q->head->next; // next ptr point to queue head->next list_ele_t *temp; temp = q->tail; // store the address of tail q->tail = q->head; // let tail pointer to head q->head = temp; // let head pointer to temp(tail) while (nxt != NULL) { // reverse middle node from orignal head temp = cur; cur = nxt; nxt = nxt->next; cur->next = temp; } q->tail->next = NULL; } } ``` 反轉的部分以圖示說明假設 `queue` 存在3個 `node` ![](https://i.imgur.com/xVgSkqY.png) 接著我們將 `cur` 指向 `head` ， `nxt` 指向 `head->next` ![](https://i.imgur.com/En8NMA8.png) 接著我們利用 `temp` 來交換 `head` 和 `tail` ![](https://i.imgur.com/UfoL1Le.png) 接著進入迴圈，迴圈停止條件為 `nxt` 為 NULL 時停止從原先的 `head` 處開始反轉利用 `temp` 來達成交換下方圖示對應上方程式碼 12~15 行 **12~1~** `temp = cur;` ![](https://i.imgur.com/WBj2sJP.png) **13~1~** `cur = nxt;` ![](https://i.imgur.com/1voUK5C.png) **14~1~** `nxt = nxt->next;` ![](https://i.imgur.com/673voNG.png) **15~1~** `cur->next = temp;` 未達迴圈停止條件 ![](https://i.imgur.com/rGM3PS1.png) **12~2~** `temp = cur;` ![](https://i.imgur.com/yUkDViH.png) **13~2~** `cur = nxt;` ![](https://i.imgur.com/0tDyfjN.png) **14~2~** `nxt = nxt->next;` ![](https://i.imgur.com/OlrdoRm.png) **15~2~** `cur->next = temp;` 跳出迴圈並更新 `tail->next` ![](https://i.imgur.com/YVpW52v.png) #### 測試結果 **TOTAL 100/100** ``` $ 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 ....... +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, and reverse --- trace-15-perf 7/7 --- TOTAL 100/100 ``` ### 自動測試機制 ``` test: qtest scripts/driver.py scripts/driver.py ``` 可以看見執行 `make test` 時會執行 `script/driver.py` 觀察 `driver.py` ```python= if __name__ == "__main__": run(sys.argv[0], sys.argv[1:]) ``` 發現一開始執行 `driver.py` 時會去執行 `run` 這個 function 其中 `sys.argv[0]` 是指在 cmd 內執行的指令而 `sys.argv[1:]` 是輸入的參數可以輸入的參數以及使用方法如下 ``` Usage: ./scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL] -h Print this message -p PROG Program to test -t TID Trace ID to test -v VLEVEL Set verbosity level (0-3) ``` :::info -v 這個參數有點特別，是設定 `verbosity level` 中文翻譯有點像冗長或贅詞的程度，就我認知，在他設定為0時，有點像 `black test` 就是只告訴你對或錯，而設成1時會跟你說 `test1` 測試了那些 function 而設成 2 , 3 時則接露更多資訊方便使用者 debug ::: 另外還有一個參數是 -A 會產生一個分數的 JSON 字串 ```json= {"scores": {"Trace-01" : 6, "Trace-02" : 6, "Trace-03" : 6, "Trace-04" : 6, "Trace-05" : 6, "Trace-06" : 7, "Trace-07" : 7, "Trace-08" : 7, "Trace-09" : 7, "Trace-10" : 7, "Trace-11" : 7, "Trace-12" : 7, "Trace-13" : 7, "Trace-14" : 7, "Trace-15" : 7}} ``` 此次的自動測試機制流程如下圖 ![](https://i.imgur.com/DTLpeGW.png)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.