2018q3 Homework2 (lab0)

contributed by < TerryShu >

lab0
目標:

英文閱讀
[ ]C 語言程式設計基礎
[ ]準備 GNU/Linux 開發工具
[ ]學習使用 Git 與 GitHub
[ ]學習效能分析
[ ]研究自動測試機制

英文閱讀

C Programming Lab: Assessing Your C Programming Skill

準備 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.

將此次作業clone下來

$ git clone https://github.com/TerryShu/lab0-c.git

Makefile

可以透過 Makefile 了解此次作業的流程


CC = gcc
CFLAGS = -O0 -g -Wall -Werror

此兩行是在宣告變數 CC 代表使用 GNU 的 gcc
CFLAGS 是在宣告使用的參數
-O 是表示使用最佳化的程度 -O0 表示沒有進行優化還有 -O1 -O2 -O3 ，O3 是優化程度最高
-g 代表編入除錯的資訊（使用GDB時使用）
-Wall 代表顯示所有的 Warnings
-Werror 將所有 Warnings 轉為 errors






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 對應的執行方法





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 的執行檔


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

test 的相依項目有 qtest scripts/driver.py 會先檢查這兩個項目是否存在，若存在則執行 driver.py 去測試並計算分數




clean:
	rm -f *.o *~ qtest 
	rm -rf *.dSYM
	(cd traces; rm -f *~)

clean 清除編譯完後的 .o 檔和 qtest 執行檔以及一些執行過程中生成的檔案

lab0

題目敘述






/*
 * 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

資料結構

















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`











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`














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`
























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`
























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 時會發生錯誤

操作指標要小心
忘記更改時很容易發生錯誤

`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->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`









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`



















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

接著我們將 cur 指向 head ， nxt 指向 head->next

接著我們利用 temp 來交換 head 和 tail

接著進入迴圈，迴圈停止條件為 nxt 為 NULL 時停止
從原先的 head 處開始反轉
利用 temp 來達成交換
下方圖示對應上方程式碼 12~15 行

12₁ temp = cur;

13₁ cur = nxt;

14₁ nxt = nxt->next;

15₁ cur->next = temp; 未達迴圈停止條件

12₂ temp = cur;

13₂ cur = nxt;

14₂ nxt = nxt->next;

15₂ cur->next = temp; 跳出迴圈並更新 tail->next

測試結果

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


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)

-v 這個參數有點特別，是設定 verbosity level 中文翻譯有點像冗長或贅詞的程度，就我認知，在他設定為0時，有點像 black test 就是只告訴你對或錯，而設成1時會跟你說 test1 測試了那些 function 而設成 2 , 3 時則接露更多資訊方便使用者 debug

另外還有一個參數是 -A 會產生一個分數的 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}}

此次的自動測試機制流程如下圖

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.