# 2021q1 Homework1 (lab0)
contributed by < `jasonmatobo`
## Reviewed by yuchun1214
關於 Valgrind 的部分， `linenoise.c` 中確有寫關於 `free histroy` 的函式，但程式實際上不一定會使用到，如果用 `--show-reachable=no` 的方式去修改得先證明 `valgrind` 誤判。
:::info
:alien: 補充
* 書本模式請使用以下連結 : [Linux 核心設計筆記(2021)](https://hackmd.io/@jasonmatobo/Linux_Kernel_Note_2021/)
* <s>內容進度 : 10%</s>
> 不需要過早量化進度，你只要詳實記錄你的學習歷程和對應的疑惑即可
> :notes: jserv
:::
:::danger
共筆書寫已有規範：中英文間以一個半形空白區隔。請務必遵守。
:notes: jserv
:::
# 作業要求
作業給出部分程式碼的 `interface` ，需要完成實作，實做順序由上往下
| Interface | 說明 | command |
| ----------------- | ------------------- | ---|
| :ballot_box_with_check: queue new | 建立 empty queue | new |
| :ballot_box_with_check: queue insert head | 試圖 Insert element 到 queue 的 head | ih |
| :ballot_box_with_check: queue insert tail | 試圖 Insert element 到 queue 的 tail | it |
| :ballot_box_with_check: queue free | Free queue 所佔用的 memory | free |
| :ballot_box_with_check: queue remove head | 試圖 remove queue 中 head element | rh
| :ballot_box_with_check: queue size | 計算 queue 中有幾個 element | size
| :ballot_box_with_check: queue reverse | 將 queue link 做反向 | reverse
| :ballot_box_with_check: queue sort | 以遞增順序來排序 queue 中的 element | sort
| Tool | 說明 |
| ----------------- | ------------------- |
| :ballot_box_with_check: 排除 Address Sanitizer error | 靜態分析記憶體問題
| :ballot_box_with_check: 運用 Valgrind 透過 Massif 視覺化 “simulation” 過程 | 動態分析記憶體問題
| :black_square_button: 已整合 `tiny` ，但 `git commit` 會擋，需要花時間修改 `tiny` 檔案 |
| :black_square_button: 研究如何改寫為 `coroutine` |
## 目標
* 完成 `interface` 實作
* `q_insert_tail` & `q_size` 時間複雜度改為 $O(1)$ (常數時間)
## 課程補充
* 學習使用 Valgrind
* 學習使用 Address Sanitizer
* 引入 Git pre-commit hook 提升 commit code 時的程式品質
* 引入 Git pre-push hook 提升 push code 時的程式品質
* 時間複雜度改進，參考論文: Dude, is my code constant time?
* 改善 Makefile
:::info
:alien: 補充
* git commit 代表你的 code 完成一個段落，可以當作你把目前的版本存一份起來
* git push 代表你的 code 完成多個段落後，你要將目前的 code 上傳到主要 branch 上面
> 上方說法有誤！git push 並非「上傳 code」，實際上是發布 changeset objects (物件)，請詳細閱讀 git 手冊 (可執行 `git push --help`)。工程人員說話應當精準。
> :notes: jserv
:::
# 環境準備
## Ubuntu 環境
```c=
$ uname -a
Linux jason 5.8.0-44-generic #50~20.04.1-Ubuntu SMP Wed Feb 10 21:07:30 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
```
:::info
:alien: 補充
* 如果有獨立<s>顯卡</s> 圖形處理器 (GPU) 且安裝完 Ubuntu 之後解析度無法調整，可用以下 command 安裝 driver
```shell
sudo add-apt-repository ppa:graphics-drivers/ppa
sudo apt-get update
// 顯示可以安裝的 driver
sudo ubuntu-drivers devices
sudo apt-get install nvidia-driver-460
```
> 現代 GPU 所做之事遠超過「顯示」功能，因此不該稱為「顯示卡」
> :notes: jserv
:::
## 安裝必要工具
```c=
$ sudo apt install build-essential git-core valgrind
$ sudo apt install cppcheck clang-format aspell colordiff
$ sudo apt install tig
```
| 名稱 | 作用 |
| --------------- | ----------------- |
| build-essential | compiler Tool |
| git-core | git Tool |
| valgrind | debug & analysis Tool |
| cppcheck | static C/C++ code analysis |
| clang-format | format C/C++/Obj-C code |
| aspell | spell-checker |
| colordiff | colorize 'diff' output |
| tig | text-mode interface for Git|
:::info
:alien: 補充
* [開發環境設定](https://hackmd.io/@sysprog/linux2021-lab0) : 這篇第 2 行 command 多打一個 valgrind
> 路見不平，動手去改！等你的貢獻
> :notes: jserv
* 如果要看詳細 Tool 內容可以輸入 apt show，舉例
```shell
$ apt show build-essential
```
* Cppcheck 版本要大於 v1.90，如果小於可以用以下 command 升級
```shell
$ sudo apt remove cppcheck
$ git clone git://github.com/danmar/cppcheck.git
$ cd cppcheck
$ make
$ sudo cp ./cppcheck /usr/bin/
$ cppcheck --version
Cppcheck 2.3
```
:::
## 取得 lab0 程式碼
首先 `fork` 作業說明指定的 repository: [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c)
接下來 `clone` 自己的 `github`
```shell=
$ mkdir -p linux2021
$ cd linux2021
$ git clone https://github.com/jasonmatobo/lab0-c.git
$ cd lab0-c
$ make
Git hooks are installed successfully.
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
```
可以觀察一下 `Makefile` ，大概分為 3 個部分
* 設定專有變數 : 例如 `CC = gcc` 就是設定你要使用 `gcc` 編譯器
* 檢查參數 : 例如輸入 `make VERBOSE=1` ， `VERBOSE` 就是你帶的參數
* 設定自訂變數 : 例如輸入 `make check` ，那就會執行 `check` 下面的區塊 `./$< -v 3 -f traces/trace-eg.cmd`
# 實做 Interface
## Debug
測試過程常會加入 `printf` 做 Debug
可以用 `define` 將 `printf` 包裝，之後比較好替換
```cpp
#define DEBUG(format, ...) printf("[ %s:%d ] "format"", __FUNCTION__, __LINE__ , ##__VA_ARGS__);
// 舉例:
DEBUG("Input string len : %zu\n",strlen(s));
[ q_insert_head:69 ] Input string len : 5
```
## q_new
由 `traces folder` 底下的 `script` 可以知道一開始都會執行 `new`
而 `new` 在 `qtest.c` 中對應為 `do_new` ，其中就會呼叫 `q_new`
所以首先實做 `q_new`
```cpp
queue_t *q_new()
{
/*
man malloc: If size is 0, then malloc() returns either NULL...
檢查 q 是否為 NULL，如果是 return NULL
*/
queue_t *q = malloc(sizeof(queue_t));
if(!q) return NULL;
/* 初始化 head & tail 指向 NULL */
q->head = q->tail = NULL;
q->size = 0;
return q;
}
```
## q_insert_head
* 建立一個`static function`，用來建立新的`element`
* `strlen` 會由目前`pointer`往後找，直到發現結束字元`\0`，假設字串為`dolphin`，`strlen`會回傳`7`(不會算到結束字元)，所以`+1`是要額外放結束字元
* 也可使用`strdup` 來取代`malloc` & `string copy`
:::info
:alien: 補充
* `static function`只有此檔案才可使用
* 建立額外`static function`是因為`insert_head`和`insert_tail`都會用到
* `strlen` 實做可以參考 [glibc/strlen.c](https://code.woboq.org/userspace/glibc/string/strlen.c.html)
* `strdup` 實做可以參考 [glibc/strdup.c](https://code.woboq.org/userspace/glibc/string/strdup.c.html)
:::
```cpp
static bool _create_element( list_ele_t **new, char *s )
{
/* 檢查 new 是否為 NULL，如果是 return false */
*new = malloc(sizeof(list_ele_t));
if(!*new) return false;
(*new)->next = NULL;
(*new)->value = 0;
size_t str_len = strlen(s) + 1;
(*new)->value = (char*) malloc( str_len * sizeof(char));
if(!((*new)->value)){
free(*new);
return false;
}
//snprintf( (*new)->value, str_len, "%s", s);
memcpy((*new)->value, s, str_len);
return true;
}
bool q_insert_head(queue_t *q, char *s)
{
if(!q) return false;
/* 檢查 _create_element 是否成功 */
list_ele_t *newh;
if(!_create_element(&newh, s)){
return false;
}
/* 將新增的 newh insert 到最前面 */
newh->next = q->head;
q->head = newh;
/* 只有當 tail == NULL 才會紀錄 */
if (!q->tail) {
q->tail = newh;
}
++(q->size);
return true;
}
```
## q_insert_tail
前面和 `q_insert_head` 差不多
主要是在 `queue_t` 新增一個 `list_ele_t *tail;` 來紀錄最後一個 `element`
:::info
:alien: 補充
* 沒有 `*tail` ，每次都要從頭依序走訪才能找到尾，時間複雜度使用 $O(n)$
* 有用 `*tail` ，只要直接插入 `tail` 的位置就好，時間複雜度達到 $O(1)$
:::
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if(!q) return false;
/* 檢查 _create_element 是否成功 */
list_ele_t *newt;
if(!_create_element(&newt, s)){
return false;
}
/*
q head is NULL : 將 head & tail 都指向 newt
q head is not NULL : 將目前 tail->next 指向 newt
*/
newt->next = NULL;
if (!q->head) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
++(q->size);
return true;
}
```
## q_free
可以參考 `qtest` 中 `show` 走訪節點的作法
```cpp
list_ele_t *e = q->head;
if (exception_setup(true)) {
while (ok && e && cnt < qcnt) {
if (cnt < big_queue_size)
report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", e->value);
e = e->next;
cnt++;
ok = ok && !error_check();
}
}
```
要 `free` 整個 `queue` 也是走訪每個 `element`
先 `free string` 再 `free list_ele_t struct`
```cpp
void q_free(queue_t *q)
{
if(!q) return;
list_ele_t *e = q->head;
while(e){
list_ele_t *next = e->next;
free(e->value);
free(e);
e = next;
}
free(q);
}
```
## q_remove_head
可以觀察 `qtest` 呼叫 `q_remove_head` 有 2 種情況
所以在 `q_remove_head` 中分別處理這 2 種情況
```cpp
// In qtest.c
// 只要單純移除 head 即可
q_remove_head(q, NULL, 0);
// 移除 head 之外，還需要把 head value copy 給 removes
// copy 長度根據第3個參數決定
q_remove_head(q, removes, string_length + 1);
```
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if( !q || !q->head ) return false;
if (sp) {
size_t val_len = strlen(q->head->value);
size_t realcpy = (bufsize-1) > val_len ? val_len : (bufsize-1);
//snprintf( sp, bufsize, "%s", q->head->value);
memcpy(sp, q->head->value, realcpy);
*( sp + realcpy ) = '\0';
}
list_ele_t *e = q->head;
q->head = e->next;
free(e->value);
free(e);
--(q->size);
return true;
}
```
## q_size
在 `queue.h` 新增 `size` 紀錄長度
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
// 用 unsigned 是因為長度沒有負數
// 範圍是 0 到 4,294,967,295，所以如果超過上限會有問題
// 可再 insert 時判斷是否可以插入避免錯誤
unsigned long size;
} queue_t;
int q_size(queue_t *q)
{
if (!q) return 0;
return q->size;
}
/*
需要更新以下 fcuntion
q_new : q->size = 0;
q_insert_head : ++(q->size);
q_insert_tail : ++(q->size);
q_remove_head : --(q->size);
*/
```
## q_reverse
可以用簡單的遞迴完成，此處新增遞迴函式
要注意的是 `q->tail` & `q->head` 結束指向的位置
```cpp
static list_ele_t* reverse_list(list_ele_t* head) {
if( !head || !head->next ) return head;
list_ele_t* p = reverse_list(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
void q_reverse(queue_t *q)
{
q->tail = q->head;
q->head = reverse_list(q->head);
}
```
:::info
:alien: 補充
測試發現如果 `element` 太多會`crash`
這是因為預設 `stack` 太小，可以在 `Makefile` 加上 `-fsplit-stack` 解決
:::
## q_sort
這題沒有給出太明確的 `sort` 條件
例如是根據字串長度？還是以字串字母大小為主？字母大小是否有影響？
所以還是先看 `qtest.c` 的判斷條件
```cpp
for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
if (strcasecmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
```
所以由檢查機制來看是從頭走訪每個 `element` ，並且用 `strcasecmp` 來判斷
`strcasecmp` 只有單純判斷字串長度而已
代表越前面字串長度要越短，越往後字串長度長，字串長度如果相等就不在意位置順序
而排序演算法有很多種，不同演算法的時間/空間複雜度都不同
可以參考此網站 [BigO](https://www.bigocheatsheet.com/) 列出不同演算法的效能
由上表得知 `Mergesort` or `Heapsort` 都是不錯的選擇
以下是第一版 `sort` ，目的是希望可以同時更新 `tail` 狀態，不過測試會失敗
```cpp
static list_ele_t* merge_list(list_ele_t* list1, list_ele_t* list2, list_ele_t** tail)
{
if(list1 == NULL) return list2;
if(list2 == NULL) return list1;
if( strcasecmp(list1->value, list2->value) < 0 ){
list1->next = merge_list(list1->next, list2, tail);
if( strcasecmp(list2->value, (*tail)->value) > 0 ){
*tail = list2;
}
return list1;
}else{
list2->next = merge_list(list1 ,list2->next, tail);
if( strcasecmp(list1->value, (*tail)->value) > 0 ){
*tail = list1;
}
return list2;
}
}
static list_ele_t* find_mid(list_ele_t* head)
{
list_ele_t * slow = head;
list_ele_t * fast = head;
list_ele_t * prev = NULL;
while( fast && fast->next )
{
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
return slow;
}
static list_ele_t* merge_sort(list_ele_t* head, list_ele_t** tail)
{
if (head->next == NULL) return head;
list_ele_t* mid = find_mid(head);
list_ele_t* list1 = merge_sort(head, tail);
list_ele_t* list2 = merge_sort(mid, tail);
return merge_list(list1, list2, tail);
}
void q_sort(queue_t *q)
{
if (!q || !(q->head) ) return;
q->head = merge_sort(q->head, &(q->tail));
}
```
所以改為 `sort` 完之後在更新 `tail` 這樣反而會過，比較奇怪
```cpp
static list_ele_t *merge_list(list_ele_t *list1, list_ele_t *list2)
{
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
if (strcasecmp(list1->value, list2->value) < 0) {
list1->next = merge_list(list1->next, list2);
return list1;
} else {
list2->next = merge_list(list1, list2->next);
return list2;
}
}
static list_ele_t *find_mid(list_ele_t *head)
{
list_ele_t *slow = head;
list_ele_t *fast = head;
list_ele_t *prev = NULL;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
return slow;
}
static list_ele_t *merge_sort(list_ele_t *head)
{
if (head->next == NULL)
return head;
list_ele_t *mid = find_mid(head);
list_ele_t *list1 = merge_sort(head);
list_ele_t *list2 = merge_sort(mid);
return merge_list(list1, list2);
}
void q_sort(queue_t *q)
{
if (!q || !(q->head))
return;
q->head = merge_sort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
# 測試結果
```shell=
jason@jason:~/linux2021/lab0-c$ make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
## Address Sanitizer
```shell=
$ make clean
$ make SANITIZER=1
$ ./qtest -v 3 -f traces/trace-17-complexity.cmd
```
出現錯誤訊息如下
```shell=
jason@jason:~/linux2021/jason/lab0-c$ ./qtest -v 3 -f traces/trace-17-complexity.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
=================================================================
==4595==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5594d5aaf600 at pc 0x5594d5a95567 bp 0x7ffe2806fff0 sp 0x7ffe2806ffe0
READ of size 4 at 0x5594d5aaf600 thread T0
#0 0x5594d5a95566 in do_option_cmd /home/jason/linux2021/jason/lab0-c/console.c:369
#1 0x5594d5a940fb in interpret_cmda /home/jason/linux2021/jason/lab0-c/console.c:221
#2 0x5594d5a949fb in interpret_cmd /home/jason/linux2021/jason/lab0-c/console.c:244
#3 0x5594d5a95d92 in cmd_select /home/jason/linux2021/jason/lab0-c/console.c:594
#4 0x5594d5a96390 in run_console /home/jason/linux2021/jason/lab0-c/console.c:667
#5 0x5594d5a92821 in main /home/jason/linux2021/jason/lab0-c/qtest.c:780
#6 0x7ffb2c9070b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x5594d5a8fd0d in _start (/home/jason/linux2021/jason/lab0-c/qtest+0x8d0d)
0x5594d5aaf601 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5594d5aaf600) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/jason/linux2021/jason/lab0-c/console.c:369 in do_option_cmd
Shadow bytes around the buggy address:
0x0ab31ab4de70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab31ab4de80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab31ab4de90: 00 00 00 00 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
0x0ab31ab4dea0: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
0x0ab31ab4deb0: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
=>0x0ab31ab4dec0:[01]f9 f9 f9 f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9
0x0ab31ab4ded0: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ab31ab4dee0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab31ab4def0: 00 00 00 00 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
0x0ab31ab4df00: f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ab31ab4df10: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==4595==ABORTING
```
錯誤訊息表示"讀取"全域變數 `simulation` 時發生越界
至於是哪裡讀取時發生問題？ ASan 有告訴我們是 `console.c:369`
```cpp
while (!found && plist) {
if (strcmp(plist->name, name) == 0) {
int oldval = *plist->valp; -----------------> X
*plist->valp = value;
if (plist->setter)
plist->setter(oldval);
found = true;
```
因為這邊讀取時是用 `int` 型態來讀，所以會讀 4 byte
但 `simulation` 宣告時為 `bool` 為 1 byte，所以會越界
```cpp
bool simulation = false;
```
所以把 `bool` 改為 `int` 即可
```cpp
bool simulation = false; -> int simulation = false;
extern bool simulation; -> extern int simulation;
```
同理 `help` 會 `crash` 也是要修改 `echo` 全域變數
```cpp
static bool echo = 0; -> static int echo = 0;
```
## valgrind
這邊會遇到一個 `blocks are still reachable in loss record`
這個問題是紀錄 `command history` 時會 `malloc` 一塊記憶體到 `history` 後面
不過最後會 `free history` 所以應該算誤判。
解決方法是修改 `./.valgrindrc`，增加最後一行
```shell=
--quiet
--memcheck:leak-check=full
--memcheck:show-leak-kinds=all
--error-exitcode=1
--show-reachable=no
```
以下使用 `massif-visualizer` 呈現數據
```shell=
$ make valgrind
$ sudo apt-get install massif-visualizer
$ valgrind --tool=massif ./qtest -f ./traces/trace-16-perf.cmd
$ massif-visualizer massif.out.20303
```
以下使用 `massif-visualizer` 呈現數據
```shell=
$ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd
$ massif-visualizer massif.out.10738
```
另外也推薦一套工具 `valgrind + kcachegrind` (安裝/使用)
```shell=
$ sudo apt-get install valgrind kcachegrind graphviz
$ valgrind --tool=callgrind ./qtest -f ./traces/trace-01-ops.cmd
$ kcachegrind callgrind.out.19434
```
# 上傳
```shell=
$ clang-format -i *.[ch]
```
# 改進想法
這裡先記錄可能可以改進的想法
:::info
:alien: 補充
* 由於 `sort` 過程會計算字串長度，是否可以在 `insert` 時就先把長度紀錄到 `element` 中，減少 `sort` 時的計算
* 可以增加額外的 `sorted_queue` ，此 `queue` 在 `insert` 時就會進行排序，當使用者呼叫 `sort` 時，直接把此 `sorted_queue` 回傳，缺點是會額外增加空間
* 此 `sorted_queue` 由於都是排序狀態，所以 `insert` 時可以使用 `binary insert` ，增加 `insert` 效能
:::
# 參考連結
* [HackMD_教學](https://hackmd.io/c/tutorials-tw/)
* [C Programming Lab: Assessing Your C Programming Skills](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [ASCII_Table](http://www.asciitable.com/)
* [BigO](https://www.bigocheatsheet.com/)
###### tags `lab`
Sign in with Wallet
Connect another wallet