2018q3 Homework2 (lab0)

contributed by < wingard >

tags: `HW2`

作業進度表

在 GitHub 上 fork lab0-c
- 參閱 GitHub 設定指引
詳細閱讀 C Programming Lab
- (英文閱讀正是我們想強化的議題)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。
- 在提交程式前，務必詳閱如何寫好 Git Commit Message
- 不用理會 Autolab 和檔案下載的描述，這兩者都是 CMU 專屬
除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
- 解釋自動評分系統運作的原理
- 提及 qtest 的行為和裡頭的技巧

實驗環境

$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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 Commit Message – 重點摘要

好的 commit messages 的 7 個規則: Source
1. Separate subject from body with a blank line
  標題與內文以一個空白行分隔，這樣可在使用 $ git log 閱讀時較易區分標題
2. Limit the subject line to 50 characters
  標題字數最多 50。因為標題字數超過 50 在 github 上會被隱藏到 … 裡面，需要額外點開才能完整知道這個 commit 在做什麼。並且超過 50 字可能就不是一個精簡的標題
3. Capitalize the subject line
  標題首字大寫
4. Do not end the subject line with a period
  標題結尾不要句點
5. Use the imperative mood in the subject line
  標題用命令口吻
6. Wrap the body at 72 characters
  內文一行字數不超過 72
  這樣在 $ git log 裡面看會比較清楚，排版比較好看
7. Use the body to explain what and why vs. how
  內文說明是什麼、為什麼而不是如何做。因為看 commit 的人是想知道你為什麼要做這件事，而不是要知道你如何做這件事的 (動機比細節更重要)

標題

一個正確的 Git commit 標題應該要能夠讓完成下面的句子，使之完整：
- If applied, this commit will 你的標題

舉例而言：

If applied, this commit will refactor subsystem X for readability
If applied, this commit will update getting started documentation
If applied, this commit will remove deprecated methods
If applied, this commit will release version 1.0.0
If applied, this commit will merge pull request #123 from user/branch

如果你很難總結出標題，這代表你可能在一個 commit 裏面做了太多的改變。請儘量讓 commits 原子化 (atomic commits)。

內文

在大多數的情況下，你可以省略掉描述這些變更的細節。程式碼本身就已經能自我說明了 (如果程式碼太複雜，必須要有說明的話，這時候就是程式碼本身的註解啦)。你只需要專注在解釋做出這樣改變的原因 ─ 事情在改變前為什麼可行 (以及他的錯誤)，他們目前運作的狀況，以及為什麼你決定要以這個方法解決問題。

C Programming Lab

Overview

queue_t Structure
- singly-linked list
- Note: 在只有一個 element 時，head 與 tail 都會指向此 element

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

NULL queue: A NULL queue is one for which the pointer has value NULL.
- q==NULL
Empty queue: An empty queue is one pointing to a valid structure, but the head field has value NULL.
- q->head = NULL

queue_t struct 內容修改

增加 tail pointer 欄位
增加 number of elements 欄位






 /* Queue structure */
 typedef struct {
     list_ele_t *head; /* pointer to head */
     list_ele_t *tail; /* pointer to tail */
     unsigned int elementNum; /* Number of elements */
 } queue_t;

Programming Task

q_new: Create a new, empty queue.

註解有提到 Return NULL if could not allocate space ，故 malloc 失敗時可以直接 return NULL pointer，malloc 成功時對 q 作初始化
















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

    return q;
}

參考 Stackoverflow 的討論，由於 malloc 回傳的 pointer 由於已經是 generic pointer void *，故不需要再做轉型

queue_t *q = malloc(sizeof(queue_t)); //OK
queue_t *q = (queue_t *) malloc(sizeof(queue_t)); // Cast is not required

q_free: Free all storage used by a queue.

先確認 q 不是 null pointer
- 根據 malloc manpage ，傳 NULL pointer 進去 free() 不會有問題，但為了減少內層的處理成本，在外層先作判斷

The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc(), or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no operation is performed.

使用 *n 暫存當前 element 指向的下一個 element ，分別 free element 指向的 string 以及 element 自身後，將 *n 回存回 *pos
- 概念類似 linked list 和非連續記憶體操作課程提到的 list_for_each_safe





















/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if (!q)
    {
        return;
    }
    
    list_ele_t *pos = q->head;
    while(pos)
    {
        list_ele_t *n = pos->next;
        free(pos->value); /* free string */
        free(pos); /* free list element */
        pos = n;
    }
    
    /* Free queue structure */
    q->elementNum = 0;
    free(q);
}

q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).

基本操作
- 將新增的 element->next 指向當前的 head element
- 將 q->head 指向此 element
若 insert 時 queue 為 NULL queue ，則 queue->tail 必為 NULL
- 將 queue->tail 也指向此 element
最後將 queue->element 數目加 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 = malloc(sizeof(list_ele_t));

    if (!newh)
    {
        return false;
    }

    /* Don't forget to allocate space for the string and copy it */
    newh->value = malloc(strlen(s)+1);

    if (newh->value == NULL)
    {
        free(newh);
        return false;
    }
    
    memcpy(newh->value, s, strlen(s)+1);

    newh->next = q->head;
    q->head = newh;
    
    if (!q->tail)
    {
        q->tail = newh;
    }

    q->elementNum++;

    return true;
}

q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).

基本操作
- 原先 q->tail element的 next 指向此新增的 element
- 將 q->tail 指向此 element
- 新增的 element->next = NULL
若 insert 時 queue 為 NULL queue ，則 queue->head 必為 NULL
- 將 queue->head 也指向此 element
最後將 queue->element 數目加 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)
{
    list_ele_t *newt;
    
    if (!q) 
    {
        return false;
    }
    
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
    {
        return false;
    }

    /* Don't forget to allocate space for the string and copy it */
    newt->value = malloc(strlen(s)+1);
    if (!newt->value)
    {
        free(newt);
        return false;
    }

    memcpy(newt->value, s, strlen(s)+1);

    if (q->tail)
    {
        q->tail->next = newt;
    }

    q->tail = newt;
    newt->next = NULL;

    if (!q->head)
    {
        q->head = newt;
    }

    q->elementNum++;

    return true;
}

一開始作 q_insert_head() 與 q_insert_tail() 內的 allocate space for the string 時，是透過 strdup() ，但跑自動測試時會失敗，百思不得其解…
後來閱讀了 pjchiou 的共筆，才知道是 harness.c 的實作，對於 malloc() 與 free() 會導向自行定義的 test_malloc() 與 test_free()，如果呼叫 strdup() 會變成 malloc() 對應 test_free()，變成對不上而導致自動測試失敗



/* Tested program use our versions of malloc and free */
 #define malloc test_malloc
 #define free test_free

q_size: Compute the number of elements in the queue.

練習 ternary operator








/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    return q? q->elementNum; 0;
}

q_remove_head: Attempt to remove the element at the head of the queue.

指標 ptr 指向要移除的 head element
如果要移除的 element->next 為 NULL ，表示此時 queue 中只有一個 element ，移除 element 後需要同時將 q->tail 設為 NULL



































/*
  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)
{
    if (!q || !q->head) // NULL queue or empty queue 
    {
        return false;
    } 

    list_ele_t *ptr = q->head;
    q->head = q->head->next;
    if (!q->head) //case for only one element in the queue
    {
        q->tail = NULL;
    }

    if (sp) 
    {
        memcpy(sp, ptr->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    free(ptr->value);
    free(ptr);
    
    q->elementNum--;
    
    return true;
}

q_reverse: Reorder the list so that the queue elements are reversed in order.

最難的一個實作，看了 pjchiou 的共筆才理解
使用三個指標去暫存前一個/目前/下一個 element
- 三個指標同時往前移動一步後，將當前 element->next 指向前一個 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)
{
    if (!q || !q->head) {  // NULL or empty
        return;
    }

    list_ele_t *head = q->head;
    list_ele_t *tail = q->tail;
    list_ele_t *pos = q->head;
    list_ele_t *prev;
    list_ele_t *n = pos->next;

    while (n) {
        prev = pos;
        pos = n;
        n = n->next;
        pos->next = prev;
    }

    q->head = tail;
    q->tail = head;
    q->tail->next = NULL;
}

程式碼格式檢查(clang-format)

git add 時如果 source code 格式不符合規定的話，會跳出指示要求透過 clang-format -i <source code> 來修改格式
參考了 Kernel.org 上的 clang-format 簡介，透過 clang-format 可以將程式碼整理成統一格式，確保大家同步開發以及 code review 時，能有相同的 coding style

自動評分系統

從 C Programming Lab 可得知，$make test 與 scripts/driver.py 有相同效果，可以從 Makefile 中得到證實:

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

輸入-h 可以看使用說明
- -h: 印出
- -v: 印出訊息的資料量大小（類似debug message level )

$ ./scripts/driver.py -h
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)

help message 少提到一個 -A ，

qtest 之行為與技巧

設計一個 switch 來接受 command arguments
























while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
    switch (c) {
    case 'h':
        usage(argv[0]);
        break;
    case 'f':
        strncpy(buf, optarg, BUFSIZE);
        buf[BUFSIZE - 1] = '\0';
        infile_name = buf;
        break;
    case 'v':
        level = atoi(optarg);
        break;
    case 'l':
        strncpy(lbuf, optarg, BUFSIZE);
        buf[BUFSIZE - 1] = '\0';
        logfile_name = lbuf;
        break;
    default:
        printf("Unknown option '%c'\n", c);
        usage(argv[0]);
        break;
    }
}

queue_init()
init_cmd();
console_init();
set_verblevel(level);