# 2018q3 Homework2 lab(0) Queue
###### tags: `C語言`
contributed by < `asd757817` >

實驗環境c
作業系統： Ubuntu 16.04 x64
kernel： 4.15.0-34-generic
gcc 版本： gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)

**github 使用 develop 分支**
>請補上實驗環境
>[name=課程助教][color=red]
## int q_size

- 規定時間複雜度為 O(1)
- 可以推測出這個函式是直接回傳長度，所以必須在 queue list 的結構中加入儲存長度的變數。每次呼叫 insert 長度增一、呼叫 remove 時長度減一。

**queue_t 中加入 size 儲存 queue 長度**

/\* 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
                      */
    int size;
} queue_t;

考慮 NULL queue 的情況，在 NULL queue 時直接回傳 0

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 q->size;
    else
        return 0;
}

**當創建一個 queue 時把長度設為0**

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    q->head = NULL;
    q->size = 0;
    return q;
}

## q_insert_head
- 規定執行成功回傳 true
- q 是 null 或不能配置記憶體則失敗回傳 faulse
- 配置空間儲存傳入的文字內容

bool q_insert_head(queue_t *q, char *s)
{
    /* 判斷 q 跟 s 是否為 NULL */
    if (q == NULL || s == NULL) {
        return false;
    } 
    /* 為新加入的節點配置空間、配置空間儲存 s 的內容 */
    else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        /* What should you do if the q is NULL? */
        int s_len = sizeof(s);
        char *s_cpy = malloc(s_len);
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        /* 判斷是否為 NULL ，並把配置的空間釋放 */
        if (newh == NULL || s_cpy == NULL) {
            free(newh);
            free(s_cpy)
            return false;
        } else {
            strncpy(s_cpy, s, s_len);
            newh->next = q->head;
            newh->value = s_cpy;
            q->head = newh;
            q->size += 1;
            return true;
        }
    }
### 
}

在測試時出現 ==ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer== 的錯誤警告，檢查後發現程式在 malloc failure 時會對 newh、s_cpy 都釋放記憶體，但兩者至少有一個是 NULL 就造成了這個錯誤。
把程式修正成：
- 兩者都不為 NULL 才進行 insertion
- 檢查 newh、s_cpy 不為 NULL 就釋放記憶體

bool q_insert_head(queue_t *q, char *s)
{
    if ( !q || !s ) {
        printf("false");
        return false;
    } else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        char *s_cpy = malloc(sizeof(s));
        /* What should you do if the q is NULL? */
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        if (newh && s_cpy) {
            strcpy(s_cpy, s);
            newh->next = q->head;
            newh->value = s_cpy;
            q->head = newh;
            if ( !q->tail )
                q->tail = newh;
            q->size += 1;
            return true;
        } else {
            if (newh)
                free(newh);
            if (s_cpy)
                free(s_cpy);
            return false;
        }
    }
}

## bool q_insert_tail
- 在 queue 的結尾加入新的物件
- 時間複雜度要求 O(1)
一般在結尾加入新的物件必須走訪至物件的 next 為 NULL 時，把 next 從 NULL 指向新的物件，但因為需要走訪整個 queue 所以時間複雜度為 O(n)，為了在 O(1)找到 queue 結尾，因此需要新增一個指在 queue 結尾的指標。

修正 queue_t

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

bool q_insert_tail 大致上內容與 insert_head 相似，只有部份地方需要修改
- 新加入的物件由 tail 的 next 指向
- 若 queue 的 head 還是 NULL 時需把 head 設定成新加入的物件

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 */
    /* 判斷傳入的兩個指標是否為 NULL */
    if (q == NULL || s == NULL) {
        return false;
    } else {
    /* 為新加入 queue 的物件配置空間、為新物件的 value 配置空間 */
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        int s_len = sizeof(s);
        char *s_cpy = malloc(s_len);
    /* 檢查配置空間是否成功 */
        if (newh == NULL || s_cpy == NULL) {
            free(newh);
            free(s_cpy);
            return false;
        } else {
            strncpy(s_cpy, s, s_len);
            newh->next = NULL;
            newh->value = s_cpy;
        /* 若 head 為 NULL 表示目前 queue_size 為 0，此時加入的物件同時也是 head */
            if (q->head == NULL)
                q->head = newh;
        /* 若 tail 不是 NULL 則把 tail->next 指向新加入的物件 */
            if (q->tail != NULL)
                q->tail->next = newh;
        /*  把 tail 設成新加入的物件 */
            q->tail = newh;
            q->size += 1;
            return true;
        }
    }
}

在 test 時會出現 ==ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer==
檢查後發現是判斷 newh、s_cpy 在釋放記憶體時出錯，原本是只要其中一個為 NULL 就釋放記憶體並回傳 false，但這樣當會對 NULL 的部份也進行一次 free ，應該改為其中一個為 NULL而另一個不為 NULL 的情況釋出不為 NULL 的記憶體才對

修改後的為

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 || !s) {
        return false;
    } else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        char *s_cpy = malloc(sizeof(s));
        if( newh && s_cpy) {
            //strncpy(s_cpy, s, s_len);
            s_cpy = strcpy(s_cpy,s);
            newh->next = NULL;
            newh->value = s_cpy;
            if (q->head == NULL) {
                q->head = newh;
            }
            if (q->tail != NULL)
                q->tail->next = newh;
            q->tail = newh;
            q->size += 1;
            return true;
        }
        else{
            if(s_cpy)
                free(s_cpy);
            if(newh)
                free(newh);
            return false;
        }

    }
}

## void q_free 將所有配置過的空間釋放
所有配置過的空間有：
- queue_t
- list_ele_t
- space for list_ele_t->value

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *to_be_free = q->head; //把要 free 的對象指定成當前的 head
    while(to_be_free){
        q->head = q->head->next; // 走訪 queue 中的所有物件
        free(to_be_free->value); // free value 
        free(to_be_free);        // free list_ele_t
        to_be_free = q->head;    // 更新要 free 的目標
    }
    free(q);                     // free queue_t    
}

## bool q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    /* 當 queue 是 NULL 時回傳 false */
    if (q == NULL) {
        return false;
    }
    /* 當 queue head 為 NULL 時回傳 NULL */
    else if(q->head == NULL){
        return false;
    }else {
        /* You need to fix up this code. */
        /* 把原本 value 的內容複製到 sp */
        list_ele_t *old_head = q->head;
        int str_len = sizeof(old_head->value);
        strncpy(sp, old_head->value, str_len);
        /* 更新 queue head */
        q->head = q->head->next;
        /* 釋放原本 queue head 的空間 */
        free(old_head->value);
        old_head->value = NULL;
        free(old_head);
        old_head = NULL;
        q->size -= 1;
        return true;
    }
}

在 make test 時一直出現錯誤訊息，目前已知是```strncpu```出現問題，但仍在處理中。

ERROR:  Removed value meerkat_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat
Error limit exceeded.  Stopping command execution

仔細重新閱讀了題目
:::info
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.)
:::
真正要取的字串長度是==bufsize-1==，最後一位要補成結尾符號('\0')，而 strncpy 只是將長度 n 的字串複製到目標中，**並沒有加入結尾符號**，因此我的作法：
- 把目標內 bufsize 長度都設成結尾符號再使用 strncpy 複製字串

修改後的 q_remove_head 如下：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q) {
        return false;
    } else if (!q->head) {
        return false;
    } else {
        /* You need to fix up this code. */
        /* How about freeing the list elements and the strings? */
        /* Free queue structure */
        if (sp) {
            memset(sp,'\0',bufsize);
            strncpy(sp, q->head->value + '\0', bufsize-1);
            printf("%s\n",sp);
        }
        list_ele_t *to_be_free = q->head;
        q->head = q->head->next;
        if (q->size == 1 && !q->head) {
            q->tail = NULL;
        }
        free(to_be_free->value);
        free(to_be_free);
        q->size -= 1;
        return true;
    }
}

### void q_reverse
題目要求：
- 不能配置額外的記憶體空間
- 對於 NULL queue or empty queue 沒有影響
- 作法：
* 對 NULL queue 和 empty queue 不做任何事情

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if( q && q->head){
        q->tail = q->head;
        list_ele_t *pre_node = NULL;
        list_ele_t *next_node = q->head->next;

        while(next_node){
            q->head->next = pre_node;
            pre_node = q->head;
            q->head = next_node;
            next_node = q->head->next;
        }
        q->head->next = pre_node;
    }
}

## 評分機制相關
### Makefile 撰寫
- 以 "=" 或是 ":=" 賦予數值
- target: dependencies
* target 是要產生的目標物件，dependencies 是產生目標需要引入的物件，若找不到物件會在 makefile 中尋找是否有產生該物件的規則
* : 後以 tab 隔開，不是空格(空白鍵)
* all 是一個最終的目標，只有輸入 make 時，就是以產生 all 為目標進行動作

以這次作業的 makefile 為例子：
- 只輸入 make 指令是，程式的目標是產生 all 這個檔案，而產生這個檔案需要 $(GIT_HOOKS)、qtest，所以程式接著尋找產生這兩個檔案所需要的動作。
- 測試分數時會使用指令 make test，指定產生的目標檔案為 test，因此會執行

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

### Git hook
是一個在執行 commit 或是 merge 指令時會觸發的一個腳本，又可以分成 pre-hook 或是 post-hook，一個是在指令輸入後執行前觸發；一個是在指令執行完畢後觸發。

這一次作業使用的是 pre-hook，當我們要進行提交的時候會觸發腳本，檢查這次提交之前是不是有執行過 clang-format 的排版檢查，而這次作業會使用的 clang-format、cppcheck 在腳本內也會檢查是否安裝，若是未安裝會以文字警告尚未安裝。

### Clang-format
調整 C 語言的原始碼的格式，以方便開發人員閱讀，由於不同的開發人員有不同的習慣，在團隊開發時為了使團隊間的溝通順利，可以利用 clang-format 調整程式碼的格式，原本套件就有預設Google、Chromium、Mozilla 等程式，開發人員也可以自行定義團隊的開發格式。

實際操作：

### cppcheck
一個靜態分析的工具，不用實際運行程式只透過原始碼分析找出程式的問題，所找的問題類型是編譯器難以察覺的。

檢查項目包括：
- double free
- 自動變量生存週期檢查
- 空指針引用
- sizeof內的計算
- 檢查動態配置是否被釋放
- ...等功能

在這次的作業中使用 cppcheck 檢查動態配置的記憶體是否有正確釋放、程式是否操作 null pointer 等，檢查可以編譯執行但卻有疑慮的問題。

### 評分機制
- qtest.c 是用來對 queue 進行操作的介面
- report.c 定義了對 queue 進行操作後**預期**得到的結果，若是結果和預期不符會輸出錯誤訊息
- harness.c 裡面定義了 malloc、free 記憶體的行為，用來測我們所做的是否有在正確的時間點進行 malloc、free
- 輸入指令 ```make test``` 可以測試程式並計算分數。在 Makefile 中得知這行指令會運行 driver.py 檔案。
- driver 檔案內引入了許多測試用的腳本(trace-01 ~ trace-01)，在 trace 資料夾中可以看見每個腳本內對 queue 進行的操作，測試程式開啟 qtest並依據腳本內的指令進行操作，根據 report、harness 回傳的訊息給分。




### 效能改善
- 反轉陣列
    * 由於原本是 queue 的結構是 singly linked list ，在做反向運算時需要額外紀錄當前節點、當前節點的前一個節點跟當前節點的下一個節點，才能完成反轉，但是若把結果修改成 doubly linked list 直接由節點本身就可以取得前一個節點與下一個節點，如此一來可以節省做反向運算的時間。