2018q3 HomeWork2 (lab0)

contributed by <LiuJuiHung>

---

• 英文閱讀
• 準備 GNU/Linux 開發工具
• 學習使用 Git 與 GitHub
• 學習效能分析
• 研究自動測試機制

英文閱讀

C Programing Lab

學習使用 Git 與 GitHub

1. GitHub 使用方法
2. 先建立出自己的 SSH key , 在 terminal 輸入以下指令

$ ssh-keygrn -t rsa -C "[e-mail]"
$ ssh-agent -s
$ ssh-add ~/.ssh/id_rsa

3. 將電腦上的 SSH key (輸入以下指令)複製到 GitHub 的 SSH key 裡

$ cat ~/.ssh/id_rsa.pub

4. 在 terminal 中輸入以下指令驗證

$ ssh -T [e-mail]

5. 本機安裝 git
6. 初次設定 Git
   • git config --global user.name "your_name" 設定使用者名稱
   • git config --global user.email [e-mail] 設定 email
7. 將老師提供的 lab0-c 作業 fork 到自己的 github
8. 在 terminal 輸入以下指令，將作業 git clone 下來

$ git clone [e-mail]:LiuJuiHung/lab0-c.git

9. 程式碼更改後
   • git add . 加入更改過的全部的檔案
   • git commit 撰寫 commit message
   • git push 將檔案 push 到 github 上

$ git add . 
$ git commit
$ git push

---

Makefile

了解 Makefile 運作

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 常用參數詳解

---

GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest

• all：預設執行的目標，這裡包含 GIT_HOOKS 和 qtest

---

$(GIT_HOOKS):
    @scripts/install-git-hooks
    @echo

• 確認是否有安裝 githooks

---

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

---

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

/* 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 配置一個記憶體空間，將此空間初始化並回傳

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 掉

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 要增加

/*
  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 要增加

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

/*
  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 的個數回傳

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

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