---
tags: linux2021,
---

# 2021q1 Homework1 (lab0)
contributed by < `Masa1u` >

## 簡介
lab 中使用許多工具協助養成良好的寫程式習慣，包含：
* Git pre-commit hook
* [git-good-commit](https://github.com/tommarshall/git-good-commit): 學習撰寫良好的 Git commit message
* [cppcheck](http://cppcheck.sourceforge.net/): 靜態程式碼分析工具
* [clang-format](https://clang.llvm.org/docs/ClangFormat.html): 確保一致的程式風格
* [GNU Aspell](http://aspell.net/): 拼字檢查
* [valgrind](https://valgrind.org/): 動態程式分析工具
* [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer): 檢查記憶體的使用

等......

詳細的環境設定以及lab的相關說明請參閱 [I01: lab0](https://hackmd.io/@sysprog/2020-lab0?fbclid=IwAR2YOjtMYzE_kB5vqvBUOSM9OlR5hgvz7NHUGg21NOcN9Hb8vccxEV-yC3o)、[C Programming Lab: Assessing Your C Programming Skills](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)

## 如何測試
測試所有的測資:
> make test

針對單一個測試可以用:
> ./qtest -f <command file>

得到更詳細的程式運行狀況，方便修改程式的錯誤
## 基本實作

詳細的程式內容請參見 [GitHub](https://github.com/yppan/lab0-c)，此文件只著重於重點解說

### Queue structure
Implement in `queue.h` file.

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size;
} queue_t;

除了原始的head之外，為了使 insert_tai() 和 size() 兩函式都在 $O(1)$ 的時間複雜度，我們增加兩個 Object, tail 和 size。

### New
產生一個新的 queue，記得初始化 queue 相關的資料結構即可。

### Free
釋放 queue 前務必先檢查 queue 是否為 NULL。之後，先釋放 queue 上的每個 element 所用的空間(包含字串 allocate 的)，再釋放掉 queue 本身。

### Insert head/tail
為新的 list element 和儲存的字串分配出相應的空間，串接在 queue 的 head / tail 端，再更新 q->head / q->tail 即可。需注意在 queue 為空(q->size = 0)的特例處理，此時需同時把 q->head, q->tail 指向新增的 element。

另外有幾個需要特別小心的地方:
:::info
:bell: snprintf 的使用方式
將可變個引數(...)按照format格式化成字串，然後將其複製到str中

(1) 如果格式化後的字串長度 < size，則將此字串全部複製到str中，並給其後新增一個字串結束符('\0')；

(2) 如果格式化後的字串長度 >= size，則只將其中的(size-1)個字元複製到str中，並給其後新增一個字串結束符('\0')，返回值為欲寫入的字串長度。

int snprintf(char *str, size_t size, const char *format, ...)

和 strcpy, strncpy, strncpy_s 比較起來，不用考慮`\0`符號，較不容易出錯

:::

::: info
:bell: [被禁止的 strcpy](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)

:::

### Remove head
Remove 之前，首先要檢查 queue 是否為空，以及參數中的 sp 是否為具有空間的 buffer。q->head 指到的 element 是移除的目標，根據要求，先把目標中儲存字串複製到 sp 中，調整 q->head 指到的地方後，再釋放原本 q->head 的 element 所使用的空間。

::: info
:bell: 在釋放 element 本身前，記得先釋放 element 中使用的 char pointer

  free(tmp->value);
  free(tmp);

:::

### Get size
我們在 add / remove node 時會維護 queue 的大小，因此直接回傳 q->size 即可達到 $O(1)$ 的執行速度

### Reverse
大致上，只要注意在調整 next 指向的 element 時，先讓 next 原本指向的 element 有一個 temp pointer 追蹤，避免遺失掉某個 element 的 referenece 即可。

### Sort
[Merge sort of linked list](https://www.techiedelight.com/merge-sort-singly-linked-list/)

但要記得排序後把 q->head / q->tail 也指去對的地方！

:::info
:bell: 為什麼不用 quick sort 處理 sorting
ANS: 因為 merge sort 在 worst case 也是 $O(n \log n)$，但 quick sort 有可能是 $O(n^2)$
:::

:::info
:bell: 使用strcmp來做字串的比大小!
:::

### 使用 make test

Run `make test `


測試程式發現在的程式在第八個腳本時會出錯

./qtest -v 3 -f traces/trace-08-robust.cmd
cmd> # Test operations on empty queue
cmd> option fail 10
cmd> option malloc 0
cmd> new
q = []
cmd> rh
Warning: Calling remove head on empty queue
Removal from queue failed
q = []
cmd> reverse
q = []
cmd> size
Queue size = 0
q = []
cmd> sort
Warning: Calling sort on single node
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
[1]    11901 abort (core dumped)  ./qtest -v 3 -f traces/trace-08-robust.cmd

由上面腳本的執行結果可得知是在 sort 之前的 null check 出了問題。

**原本：**

void q_sort(queue_t *q)
{
    if (!q || q->size == 1) {
        return;
    }

    // Merge sort
    merge_sort(&q->head);

    // locate tail pointed to the last element of the list
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

**修正後：**

void q_sort(queue_t *q)
{
    if (!q || !q->head || q->size == 1) {
        return;
    }

    // Merge sort
    merge_sort(&q->head);

    // locate tail pointed to the last element of the list
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

:::info
:bell: 所有的 function 都必須處理 queue == NULL 以及 q->head == NULL(empty)，防止使用者錯誤的使用。
:::

最後 make test 結果滿分

---	TOTAL		100/100

### 小結論（心得）

這一個 queue 的練習，雖然看起來是滿分，但我完完全全不認為自己不錯，反而是覺得自己在軟體測試有很大的不足。

1. 我還沒有辦法像老師一樣自己寫測試程式、做 C 語言的 Unit Test (在Rust還可以)
2. Valgrind, Gcc 的使用上，我還無法透過裡面錯誤的訊息判斷自己程式的錯誤在哪裡

認清自己所缺、誠實面對自己、.***Just Keep Learning!***