2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < `Wufangni` > ## 開發環境 ``` shell $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 16 On-line CPU(s) list: 0-15 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i5-12500H CPU family: 6 Model: 154 Thread(s) per core: 2 Core(s) per socket: 12 Socket(s): 1 Stepping: 3 CPU max MHz: 4500.0000 CPU min MHz: 400.0000 BogoMIPS: 6220.80 ``` ## 針對佇列操作的程式碼實作 ### `q_new` > [commit_0f1697a](<https://github.com/Wufangni/lab0-c/commit/0f1697a110a38c743e86abb1112b0807c2cb8880>) :::danger allocate 的翻譯是「配置」，以區格 dispatch (分發/分配) > 已更改 ::: 先建立指向 `list_head` 結構的 head 指標，並使用 `malloc` 配置一個記憶體空間，最後回傳經由 `INIT_LIST_HEAD` 初始化後的 head 指標。 :::danger 段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。 > 已更改 ::: :::danger 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。 ::: ### `q_free` > [commit_e34d5f1](<https://github.com/Wufangni/lab0-c/commit/e34d5f1ef1fb3fc3c23b87206753375cb9d0068f>) 利用 `list_for_each_entry_safe` 逐一走訪每個節點，並利用 `q_release_element` 釋放該節點的記憶體空間，最後釋放指向佇列第一個元素的 head 指標。 :::danger 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利) > 已更改 ::: ### `q_insert_head` > [commit_289d41c](<https://github.com/Wufangni/lab0-c/commit/289d41c5f2fc78f671774a4c35460a12a4d15b85>) :::danger 段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。 > 已更改 ::: 利用 `malloc` 配置記憶體空間給新增節點使用，並將欲新增的字元參數指定給新增節點的 value ,再使用 `list_add` 新增節點到 list 的前端。 ### `q_insert_tail` > [commit_9f62397](<https://github.com/Wufangni/lab0-c/commit/aed93dfb1ad8df5bb85d20f23cacbd69a61de1e8>) :::danger 段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。 > 已更改 ::: 與 `q_insert_head` 大致相同，差別在於 `list_add` 部份改為使用`list_add_tail`。 ### `q_remove_head` > [commit_ad185d6](<https://github.com/Wufangni/lab0-c/commit/ad185d6ed4d9e4c9191b9ab6387b96cea929b0fb>) 利用 `head->next` 建立欲刪除的 `remove_h_list`，先儲存 `remove_h_list` 的值到 `sp` 字元中，再對 `head->next` 所指節點做 `list_del`。 :::danger 段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。 > 已更改 ::: ### `q_remove_tail` 與 `q_remove_head` 大致相同，差別在於 `head->next` 部份改為 `head->prev`。 :::danger 段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。 > 已更改 ::: 實作程式碼在 [commit_ad185d6](<https://github.com/Wufangni/lab0-c/commit/d19396fc2ca837c6c02c1384ec371918b58cfbb0>)。 ### `q_size` 新增 `node_count` 變數計數每個節點數量再做回傳。實作程式碼在 [commit_ad4ada0](<https://github.com/Wufangni/lab0-c/commit/ad4ada0e1d27309c3716d556d04b5e97318fab18>)。 ### `q_delete_mid` 使用 `q_size` 抓取 list 總節點數，新增 `*cur` 指標，並用 for 迴圈到總節點數的一半逐一往下跳到中間節點。利用 `*cur` 建立`removed_element` ，使用 `list_del` 斷開 `*cur` 在 list 中的連結，最後用 `free` 釋放 `removed_element`。實作程式碼在 [commit_3bb6704](<https://github.com/Wufangni/lab0-c/commit/3bb67042fe2ea86cdd983b179877dca63f048da1>)。 ### `q_delete_dup` 新增 `*ori` 和 `*cur` 兩個指標，`*ori` 從第一個節點開始，`*cur` 指向 `*ori` 的下一個節點持續往下跑，直到 `*cur` 指到 head 才結束迴圈。設置布林值 flag 判斷是否 `*ori` 的 value 為重複值（初始值為 false ），若 `*ori` 和 `*cur` 節點的 value 不相同，且 flag 判斷先前沒有與 `*ori` 重複的值被刪除，則 `*ori` 與 `*cur` 皆往下一跳節點。 ``` c if (strcmp(cur_element->value, ori_element->value) != 0 && flag == false) { ori = cur; cur = cur->next; } ``` `*ori` 和 `*cur` 節點的 value 若相同，則刪除 `*cur` 所指節點，且 `*cur` 往下一跳節點，flag 設為 true 表示目前 `*ori` 所指節點的值有重複。 ``` c } else { flag = true; cur = cur->next; element_t *tmp_element = list_entry(cur->prev, element_t, list); list_del(&tmp_element->list); free(tmp_element->value); free(tmp_element); if (cur == head) { element_t *tmp2_element = list_entry(ori, element_t, list); list_del(&tmp2_element->list); free(tmp2_element->value); free(tmp2_element); break; } ``` `*ori` 和 `*cur` 節點的 value 不相同且 flag 為 true，刪除 `*ori` 所指節點，將 `*ori` 指到與 `*cur` 相同節點，`*cur` 往下一節點繼續執行。 ``` c } else if (strcmp(cur_element->value, ori_element->value) != 0 && flag == true) { element_t *tmp_element = list_entry(ori, element_t, list); list_del(&tmp_element->list); ori = cur; free(tmp_element->value); free(tmp_element); cur = cur->next; flag = false; } ``` 實作程式碼在 [commit_bcbeaf7](<https://github.com/Wufangni/lab0-c/commit/bcbeaf7b677f45a7b756db8f4b29b75dfc4142fa>)。 ### `q_swap` 新增 `*front` 和 `*behind` 兩指標對兩兩節點做互換。 ``` c while (true) { if (front == head || behind == head) break; (front->prev)->next = behind; behind->prev = front->prev; (behind->next)->prev = front; front->next = behind->next; front->prev = behind; behind->next = front; front = front->next; behind = front->next; } ``` 實作程式碼在 [commit_f6ddd47](<https://github.com/Wufangni/lab0-c/commit/f6ddd47f27dd0818c3b6d0549c494f838235f613>)。 ### `q_reverse` 使用 `list_for_each_safe` 對每個節點互換 `*prev` 和 `*next` 指標。 ``` c struct list_head *nex, *s; list_for_each_safe (nex, s, head) { element_t *tmp_element = list_entry(nex->next, element_t, list); nex->next = nex->prev; nex->prev = &tmp_element->list; } struct list_head *tmp_head_next = head->next; head->next = head->prev; head->prev = tmp_head_next; ``` 實作程式碼在 [commit_f6ddd47](<https://github.com/Wufangni/lab0-c/commit/b92088728cb41a80fdb31cd1bf64f5b59dc5baf8>)。 ### `q_reverseK` 新增 `*h` 及 `*t` 兩指標分別指向每組要替換的頭跟尾節點，將此組的頭與尾節點與原先 list 斷開並使用 `q_reverse` 做反轉，連回原本的list後將 `*cur` 指向反傳後在此組節點中最尾端的 `*h`，跑 k 次迴圈後停止。 ``` c struct list_head *h, *t, *cur = head; for (int i = 0; i < (q_size(head) / k); i++) { h = cur->next; t = h; for (int j = 1; j < k; j++) t = t->next; cur->next = t->next; (t->next)->prev = cur; t->next = h; h->prev = t; q_reverse(h); h->next = cur->next; (h->next)->prev = h; t->prev = cur; cur->next = t; cur = h; } ``` 實作程式碼在 [commit_ceb5070](<https://github.com/Wufangni/lab0-c/commit/ceb5070f50e8edf908e5ea17f7cf473e667b948a>)。 ### `q_sort` 先建立一個可回傳 `list_head` 的 function `merge`，用 `*pos1` 及 `*pos2` 分別指向兩個 list 的第一個節點，若 `*pos1` 所指節點值比較小則往下跳一節點再做比較，比較大則刪除 `*pos2` 所指節點並將 `*pos2` 往下一節點移動，直到 `*pos1` 或 `*pos2` 跳至 head 。若此時 `*pos2` 指向的list中尚有節點則從第一個節點逐一加到 `*pos1` 所在 list 最後端。 ``` c struct list_head *merge(struct list_head *head1, struct list_head *head2) { struct list_head *pos1 = head1->next, *pos2 = head2->next, *insert; while (pos1 != head1 && pos2 != head2) { element_t *ele1 = list_entry(pos1, element_t, list); element_t *ele2 = list_entry(pos2, element_t, list); if (strcmp(ele1->value, ele2->value) > 0) { insert = pos2; pos2 = pos2->next; list_del(&ele2->list); (pos1->prev)->next = insert; insert->next = pos1; insert->prev = pos1->prev; pos1->prev = insert; } else { pos1 = pos1->next; } } while (pos2 != head2) { insert = pos2; pos2 = pos2->next; list_del(&list_entry(insert, element_t, list)->list); list_add_tail(&list_entry(insert, element_t, list)->list, head1); } return head1; } ``` 實作出 merge sort 的遞迴 function `merge_divide`，再利用剛創好的 `merge` 合併兩 list 。 ``` c struct list_head *merge_divide(struct list_head *head) { struct list_head *mid = head->next, *mid_prev, new_head; if (q_size(head) <= 1) return head; for (int i = 0; i < q_size(head) / 2; i++) mid = mid->next; struct list_head *new_pos = &new_head; new_pos->next = mid; new_pos->prev = head->prev; (head->prev)->next = new_pos; mid_prev = mid->prev; mid->prev = new_pos; head->prev = mid_prev; mid_prev->next = head; return merge(merge_divide(head), merge_divide(new_pos)); } ``` 實作程式碼在 [commit_aed93df](<https://github.com/Wufangni/lab0-c/commit/aed93dfb1ad8df5bb85d20f23cacbd69a61de1e8>)。 ### `q_ascend` / `q_descend` `q_ascend` 對每個節點皆往下逐一檢查，若此節點往下有比它的值還小的節點存在則刪除此節點，且換下一節點檢查。 `q_dscend` 與 `q_ascend` 大致一樣，唯一差別在於 `q_dscend` 尋找比它大的節點，找到才做刪除。 ``` c for (int i = 0; i < len; i++) { bool delete = false; if (cur->next == head) break; struct list_head *node_ = cur->next; element_t *cur_element = list_entry(cur, element_t, list); for (int j = i + 1; j < len; j++) { element_t *nod_element = list_entry(node_, element_t, list); if (strcmp(cur_element->value, nod_element->value) < 0) { cur = cur->next; list_del(&cur_element->list); free(cur_element->value); free(cur_element); delete = true; break; } node_ = node_->next; } if (delete == false) cur = cur->next; } ``` `q_ascend` 實作程式碼在 [commit_5008760](<https://github.com/Wufangni/lab0-c/commit/50087600b8952fd86a62a440ff0f4eb52a3d7cbb>)。 `q_dscend` 實作程式碼在 [commit_8e8a14a](<https://github.com/Wufangni/lab0-c/commit/8e8a14a91c317b9eacb58b9e7a19a2b3066d1a10>)。 ### `q_merge` > [commit_aed93df](<https://github.com/sysprog21/lab0-c/commit/aed93dfb1ad8df5bb85d20f23cacbd69a61de1e8>) :::danger 對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋: * to fulfill; perform; carry out: * to put into effect according to or by means of a definite plan or procedure. * Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved. * to fill out or supplement 「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。 $\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: 實做 ```merge_two_list``` ，作法與上述提到的 ```merge``` 相似，差別在於沒有回傳值。利用 ```head``` 指向每個 ```queue_contex_t``` 位置串列，將第一個 ```queue_contex_t``` 包含的 ```q``` 分別與每個 ```queue_contex_t->q``` 做 merge。 ``` c int q_merge(struct list_head *head, bool descend) { if (!head || list_empty(head)) return 0; struct list_head *first_q = head->next, *next_q = first_q->next; queue_contex_t *first_queue = list_entry(first_q, queue_contex_t, chain); if (descend == true) q_reverse(first_queue->q); while (next_q != head) { queue_contex_t *next_queue = list_entry(next_q, queue_contex_t, chain); if (descend == true) q_reverse(next_queue->q); merge_two_list(first_queue->q, next_queue->q); next_q = next_q->next; } return q_size(first_queue->q); } ``` :::danger 你如何確認目前的測試程式已涵蓋排序演算法的最差狀況？ ::: --- ## 研讀並引入 `lib/list_sort.c` :::danger command 的翻譯是「命令」，而非「指令」(instruction)，這裡其實不是「命令」，而是編譯器提供的選項 (option)，查閱 GCC 手冊。 > 好的，謝謝老師。 ::: `__attribute__` 屬於 GCC 的一種編譯器命令，可用來指示編譯器進行一些高階處理和檢查工作，查閱 GCC 手冊得知 `nonnull(2,3,4)` 指示第 2 、 3 、 4 不能為空值。 ``` c __attribute__((nonnull(2,3,4))) ``` `*priv` 用來記錄傳入的 cmp function回傳的值，若 `cmp(priv, a, b) <= 0` 則表示 a < b ，將 a 加入尾端並把 `*a` 往後移一節，若 `*a` 為空串列則回 `*b` 做排序。 :::danger 段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。 > 已更改 ::: ``` c static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b) { struct list_head *head, **tail = &head; for (;;) { /* if equal, take 'a' -- important for sort stability */ if (cmp(priv, a, b) <= 0) { *tail = a; tail = &a->next; a = a->next; if (!a) { *tail = b; break; } } else { *tail = b; tail = &b->next; b = b->next; if (!b) { *tail = a; break; } } } return head; } ``` 先排除 list 為空值或只有一個節點的情況，再利用 `head->prev->next` 將 list 轉為單向鏈結串列。 ``` c struct list_head *list = head->next, *pending = NULL; size_t count = 0; /* Count of pending */ if (list == head->prev) /* Zero or one elements */ return; /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; ``` 將 list_sort.c 及 list_sort.h 引入 lab0-c ，在 qutest.c 中用 `extern` 外部宣告 `list_sort` 函式。 ```diff= +typedef int + __attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *, + const struct list_head *, + const struct list_head *); +extern void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp); ``` 定義 `cmp` 函式減少後續重複程式碼使用。 ```diff= +int cmp(void *priv, const struct list_head *a, const struct list_head *b) +{ + return strcmp(list_entry(a, element_t, list)->value, + list_entry(b, element_t, list)->value); +} ``` 新增 listsort 命令。 ```diff= ADD_COMMAND(reverse, "Reverse queue", ""); ADD_COMMAND(sort, "Sort queue in ascending/descening order", ""); + ADD_COMMAND(listsort, "Sort queue in ascending/descening order", ""); ADD_COMMAND(size, "Compute queue size n times (default: n == 1)", "[n]"); ADD_COMMAND(show, "Show queue contents", ""); ADD_COMMAND(dm, "Delete middle node in queue", ""); ``` 修改 Makefile。 ```diff= OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ shannon_entropy.o \ - linenoise.o web.o + linenoise.o web.o list_sort.o deps := $(OBJS:%.o=.%.o.d) ``` 詳細程式碼在 [commit_b8e0681](<https://github.com/Wufangni/lab0-c/commit/b8e0681edeac9fb56a32106fe5d7f0bfcc215a0f>)。 ## 提供新的命令 `shuffle` 參考 [Fisher–Yates shuffle](<https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm>) 實做洗牌演算法，新增 `q_shuffle` 函式根據下面步驟進行： 1. 確認鏈節串列不為空值。 2. 使用 `q_size` 計算鍊結串列長度，並用 for 迴圈從最尾端依序向前做交換。 3. 從目前要交換的節點之前找出隨機節點，使用 `srand(time(NULL))` 更改 `seed` 避免每次找隨機值結果不變。 4. 利用 `swap` 交換兩節點，直到 `*last` 指向第二節點時停止迴圈。 ``` c void q_shuffle(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *last = head->prev; for (int len = q_size(head); len > 1; len--) { srand(time(NULL)); int random_idx = rand() % len; struct list_head *random_node = head->next; while (random_idx--) random_node = random_node->next; swap(last, random_node); last = last->prev; } } ``` 使用 `ADD_COMMAND` 新增 `shuffle` 命令。 ```diff= ADD_COMMAND(reverse, "Reverse queue", ""); ADD_COMMAND(sort, "Sort queue in ascending/descening order", ""); ADD_COMMAND(listsort, "Sort queue in ascending/descening order", ""); + ADD_COMMAND(shuffle, "Shuffle the queue using Fisher-Yates Shuffle", ""); ADD_COMMAND(size, "Compute queue size n times (default: n == 1)", "[n]"); ADD_COMMAND(show, "Show queue contents", ""); ADD_COMMAND(dm, "Delete middle node in queue", ""); ``` 修改 Makefile。 ```diff= OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ shannon_entropy.o \ - linenoise.o web.o list_sort.o + linenoise.o web.o list_sort.o shuffle.o \ deps := $(OBJS:%.o=.%.o.d) ``` 詳細程式碼在[commit_adfc198](<https://github.com/Wufangni/lab0-c/commit/adfc19869c4d31a0446df73415a9f7dbf0906b38>)。 ## 研讀論文〈Dude, is my code constant time?〉 `Timing attacks` 是一種廣泛的 `side-channel attacks` ，不同於直接使用密碼學演算上的攻擊手段，他是利用系統執行時間的特性進行破解。舉例來說，在判斷一段密碼是否與原密碼相符時，若是從第一個字母逐一比對遇到不符合再回傳錯誤警告，就可利用回傳時間來判斷前面正確的字符有幾個，進而產生資安疑慮。有多數研究和偵測執行可變時間的方法被開發出來，例如 `ctgrind` 、`Flow-tracker` 或 `ctverif` ，大多需要對硬體進行建模，但困難點在於較難取得 CPU 細節資訊，此論文提出 `dudect` 方法可利用統計分析的程式判定是否達成 constant-time ，不用依靠靜態分析可避免硬體上的限制。 ### Step 1: Measure execution time - 針對不同輸入資料重複對執行時間進行觀察，第一種資料通常為固定的值，第二種為隨機產生。 - 現在 CPU 提供週期計數器（Cycle counters）可準確獲取執行時間。 - 最小化環境差異造成的影響，每次測量都會對應隨機產生的輸入分類。 ### Step 2: Apply post-processing 在進入統計分析之前會先對每個單獨的測量值進行一些後處理： - Cropping:可能會因為 OS 或一些外部因素導致時間分佈呈現 positive skew ，這時候可透過裁減 (crop) 掉一些超過 threshold 的測量結果。 - Higher-order preprocessing:使用高階的預處理方式有益於測量，例如`scentered product` 、`mimicking higher-order DPA attack` 。 ### Step 3: Apply statistical test 透過統計檢定來反駁兩執行時間相等的假設，有幾種檢測方式如 `t-test` 及 `Non-parametric tests` 等。 ## `dudect` 從每個 trace 中追蹤第17筆測資會無法通過，觀察內部指令為進入 `simulation` 判斷時造成的問題，回到 `qtest.c` 中觀察程式做 constant time 判斷使用到的兩函式分別為 `is_insert_tail_const()` 及 `is_insert_head_const()` ``` c if (simulation) { if (argc != 1) { report(1, "%s does not need arguments in simulation mode", argv[0]); return false; } bool ok = pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const(); if (!ok) { report(1, "ERROR: Probably not constant time or wrong implementation"); return false; } report(1, "Probably constant time"); return ok; } ``` 兩函式存放位置在 `fixture.h` 檔案中，裡面定義了 `DUT_FUNCS` 用來測試是否達到 constant time 。 ``` c #ifndef DUDECT_FIXTURE_H #define DUDECT_FIXTURE_H #include <stdbool.h> #include "constant.h" /* Interface to test if function is constant */ #define _(x) bool is_##x##_const(void); DUT_FUNCS #undef _ #endif ``` 到 `fixture.c` 中找到關於 constant time 的實作程式，與 [dudect](<https://github.com/oreparaz/dudect/blob/master/src/dudect.h>) 原始程式碼做比對發現缺漏了部份內容。 ``` c static void prepare_percentiles(dudect_ctx_t *ctx) { qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp); for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) { ctx->percentiles[i] = percentile( ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)), ctx->config->number_measurements); } } ``` 在 `fixture.c` 補上 `prepare_percentiles` 函式，且因 `prepare_percentiles` 使用了 `DUDECT_NUMBER_PERCENTILES` 定義及其餘函式所以需要一併補齊。 ``` c static int cmp(const int64_t *a, const int64_t *b) { if (*a == *b) return 0; return (*a > *b) ? 1 : -1; } static int64_t percentile(int64_t *a_sorted, double which, size_t size) { size_t array_position = (size_t)((double)size * (double)which); assert(array_position < size); return a_sorted[array_position]; } ``` 在 `doit` 函式中新增剛補上的 `prepare_percentiles` ，且修改有使用到 `DUDECT_NUMBER_PERCENTILES` 定義的 `update_statistics` 參數。 ``` diff= @@ -123,6 +161,7 @@ static bool doit(int mode) int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t)); uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t)); uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t)); + int64_t *percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t)); if (!before_ticks || !after_ticks || !exec_times || !classes || !input_data) { @@ -133,7 +172,8 @@ static bool doit(int mode) bool ret = measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); - update_statistics(exec_times, classes); + prepare_percentiles(percentiles, exec_times); + update_statistics(exec_times, classes, percentiles); ret &= report(); ``` 再使用 `make test` 測試所有 trace ，可發現所有測試項目都可通過。 ``` fangni@fangni-G5-KF:~/linux2024/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 5/5 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, remove_head, reverse and merge --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, swap, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort --- trace-05-ops 6/6 +++ TESTING trace trace-06-ops: # Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK --- trace-06-ops 6/6 +++ TESTING trace trace-07-string: # Test of truncated strings --- trace-07-string 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-robust: # Test operations on NULL queue --- trace-10-robust 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-malloc: # Test of malloc failure on new --- trace-13-malloc 6/6 +++ TESTING trace trace-14-perf: # Test performance of insert_tail, reverse, and sort --- trace-14-perf 6/6 +++ TESTING trace trace-15-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-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of insert_tail --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` 詳細程式碼在 [commit_50da0ff](<https://github.com/Wufangni/lab0-c/commit/50da0ff96351d714fc74f095861b27ceba3c3340>)。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.