# 2024q1 Homework1 (lab0)
contributed by < `zoo868e` >
## 開發環境
```shell
$ uname -a
Linux mattjan 5.15.0-92-generic #102-Ubuntu SMP Wed Jan 10 09:33:48 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
```
## 指定佇列的操作
通過 `make test` 的所有測試。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
由於作業中操作的鏈結串列已經實作了一些功能，所以我先了解了 `list.h` 中的所有功能。
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
### list utilities in `list.h`
- [Declaration, initialization, and common utilities](#Declaration-initialization-and-common-utilities)
- [Add node into list](#Add-node-into-list)
- [Remove the node from the list](#Remove-the-node-from-the-list)
- [The status of list](#The-status-of-list)
- [Add list nodes from a list to another](#Add-list-nodes-from-a-list-to-another)
- [Move list nodes from a list to another](#Move-list-nodes-from-a-list-to-another)
- [Get the entry by list node](#Get-the-entry-by-list-node)
- [Iterate the list](#Iterate-the-list)
#### Declaration, initialization, and common utilities
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
`list_head`: 定義`list_head`結構。這個結構包含兩個指標`prev`和`next`，分別指向上一個和下一個節點，以形成雙向環狀鏈結串列。
```c!
struct list_head {
struct list_head *prev;
struct list_head *next;
}
```
`container_of`：獲取 `type` 的起始地址。`type` 包含 `ptr` 所指向的物件。
```c!
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
```
`LIST_HEAD`: 宣告一個新的 `list_head`，並將其初始化為空佇列。
```c!
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
```
`INIT_LIST_HEAD`: 將傳入的指標所指向的物件內容初始化為空的鏈結串列。
```c!
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
#### Add node into list
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
`list_add`: 在鏈結串列的起點新增一個新的節點
```c!
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
`list_add_tail`: 在鏈結串列的尾端新增一個新的節點
```c!
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
#### Remove the node from the list
:::danger
改進你的漢語表達
:::
`list_del`: 從鏈結串列中移除節點。在註解中，老師詳細說明了 Remove 與 Delete 的不同之處。雖然這個功能使用 `del` 命名，但實際上的行為是 Remove，因為它操作結束後，節點仍然存在，並沒有被刪除。
```c!
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
`list_del_init`: 與 `list_del` 相同的操作，只是會重設移除的節點所指向的前一個與下一個節點，以免造成使用者可以透過這個節點非法訪問其他節點。
```c!
static inline void list_del_init(struct list_head *node)
{
list_del(node);
INIT_LIST_HEAD(node);
}
```
#### The status of list
`list_empty`: 返回鏈結串列是否為空。
```c!
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
`list_is_singular`: 回傳鏈結串列中除了開頭以外，是否只有一個節點。
```c!
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
#### Add list nodes from a list to another
`list_splice`：將鏈結串列`list`中的所有節點都添加到`head`的開頭，是複數版本的`list_add`。
```c!
static inline void list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *head_first = head->next;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->next = list_first;
list_first->prev = head;
list_last->next = head_first;
head_first->prev = list_last;
}
```
`list_splice_tail`: 將鏈結串列`list`中的所有節點都添加到`head`的尾端，是複數版本的`list_add_tail`。
```c!
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
```
#### Move list nodes from a list to another
`list_splice_init`: 功能與 `list_splice` 相同，但會重新初始化 `list`，以防止使用者透過此節點非法訪問其他節點。
```c!
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
list_splice(list, head);
INIT_LIST_HEAD(list);
}
```
`list_splice_tail_init`：與 `list_splice_init` 功能類似，不同之處在於將節點們添加到尾端。
```c!
static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
{
list_splice_tail(list, head);
INIT_LIST_HEAD(list);
}
```
`list_cut_position`: 將`head_from`的下一個節點包含`node`切割出來，再將`head_to`指向切割出來的鏈結串列。需要注意的是，`head_to`將等於被切割出來的鏈結串列，而不是將其新增到原始鏈結串列中。
```c!
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
`list_move`: 將`node`從原本的鏈結串列中移動到指定的鏈結串列的開頭。
```c!
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
- `list_move_tail`: 將`node`從原本的鏈結串列中移動到指定的鏈結串列的末端
```c!
static inline void list_move_tail(struct list_head *node,
struct list_head *head)
{
list_del(node);
list_add_tail(node, head);
}
```
#### Get the entry by list node
`list_entry`: 取得 `type` 的起始地址，`type` 的成員包括 `node` 所指的物件。
```c!
#define list_entry(node, type, member) container_of(node, type, member)
```
`list_first_entry`: 取得鏈結串列中的第一個 `type` 的起始位址
```c!
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
`list_first_entry`: 取得鏈結串列中的最後一個 `type` 的起始位址
```c!
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
```
#### Iterate the `list`
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
`list_for_each`: 逐一走訪鏈結串列中的每個節點。在這個過程中，如果更改節點指向下一個節點的指標，可能會導致多次走訪同一節點或者跳過節點。
```c!
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
`list_for_each_entry`: 逐一遍歷鏈結串列中的每個節點，並且`entry`會指向包含當前節點的物件。同樣的，途中若修改物件所包含的節點，也可能導致多次遍歷同一節點或者跳過節點。
```c!
#ifdef __LIST_HAVE_TYPEOF
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
#endif
```
`list_for_each_safe`: 逐一遍歷鏈結串列中的每個節點，期間會使用變數`safe`保留當前節點的下一個節點位址，這樣使用者可以對當前節點進行任意操作，而不會造成問題。
```c!
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
`list_for_each_entry_safe`：同時具有 `list_for_each_entry` 和 `list_for_each_safe` 的功能，用於逐一遍歷鏈結串列中的每個節點，並且 `entry` 會指向包含當前節點的物件。期間會使用變數 `safe` 保留當前節點的下一個節點位址，這樣使用者可以對 `entry` 進行任意操作，而不會造成問題。
```c!
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
#undef __LIST_HAVE_TYPEOF
#ifdef __cplusplus
}
#endif
```
### 指定佇列的操作
- `q_new`: 配置記憶體並初始化，失敗時回傳 `NULL` 。
- `q_free`: 使用 `list_for_each_entry_safe` 走訪佇列中的每一個物件，將每個物件的內容透過 `q_release_element` 釋放，最後再使用 `free` 釋放 `head` 節點佔據的記憶體。
- `q_release_element`: 原本就已經實作好的方法，會使用 `test_free` 釋放物件中 `value` 指向的空間以及將 `list` 從鏈結串列中移除
- `q_insert_head`, `q_insert_tail`: 在佇列中新增物件到起點/尾端，由於這兩個方法都需要建立新的物件，所以實作了 `q_new_element` 。這兩個方法的差異在於插入時的位置，可以分別使用` list_add` 以及 `list_add_tail` 兩個功能插入
- `q_new_element`: 原先使用 `strlen` 算出字串長度，然後用 `malloc` 配置包含 `'\0'` 的記憶體空間，再使用 `memcpy` 複製內容到配置的空間中，但是這樣的方法遍歷了兩次 `s` ，所以後來改用`strdup`將內容複製出來。
- `q_remove_head`, `q_remove_tail`: 將物件從佇列中移除，並且必要時複製出物件的 `value` 。原先使用 `memcpy` 將 `value` 複製 `bufsize` 個內容到輸出 `sp` 中，但是透過 `make valgrind` 發現這樣的方法沒有考慮到原先 `value` 中的長度，因此改為使用 `strncpy` 。
```c
- if (ret && sp && bufsize > 0) {
- memcpy(sp, ret->value, bufsize - 1);
+ if (sp && bufsize - 1 > 0) {
+ strncpy(sp, ret->value, bufsize - 1);
```
- `q_size`: 用 `list_for_each` 走訪所有節點，算出佇列的節點個數。
- `q_delete_mid`: 用兩個指標分別代表快跟慢的移動，所以當移動較快的指標走訪到 `head` 節點或者走到已經走過的節點時，代表較慢的指標所指向的節點為要刪除的節點。
- `q_delete_dup`: 由於這個功能預設輸入為已排序佇列，所以只要依序走訪所有節點，就可以很簡單的將所有重複 `value` 的物件刪除。
- `q_reverse`: 透過 `list_for_each_safe` 把每個物件用 `list_move` 搬移到 `head` 的開頭。
- `q_reverseK`: 將每個節點搬移到一個暫存的鏈結串列(`tmp`)的開頭，再使用 `list_splice_init` 將暫存的節點們搬回原本的list中。若 `tmp` 的長度不足 `k` ，則會先使用 `q_reverse` 將內容反轉，再搬回原本的list中。
- `q_swap`: 這個功能跟 `q_reserveK` , `k` 等於2時的需求相同，所以直接呼叫 `q_reserveK(head, 2)`
- `q_sort`: 實作merge sort，先使用與 `q_delete_mid` 相同的方法找到中間的節點，再透過 `list_cut_position` 將鏈結串列切成兩份，然後遞迴的呼叫 `q_sort` 將兩個鏈結串列排序好，再將兩個鏈結串列合併。
- `q_ascend`, `q_descend`: 用 `list_for_each_entry_safe` 走訪所有節點，每個節點都會嘗試刪除之前的節點，直到之前的節點比他大/小。由於大部分的功能幾乎相同，所以分別實作了 `greater` 以及 `less` 傳入 `q_remove_unorder_part` ，來當作判斷是否刪除的依據。
- `q_merge`: 將所有的鏈結串列都合併到第一個鏈結串列中，最後再用 `q_size` 回傳第一個鏈結串列的長度
### `make test`
在本地端執行`make test`之後發現第 14~16 個測試項目失敗。
`make test` result
```
$ 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
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
qtest: malloc.c:2617: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
--- trace-14-perf 0/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
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-15-perf 0/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
qtest: malloc.c:2617: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
--- trace-16-perf 0/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 82/100
make: *** [Makefile:61: test] Error 1
```
從第14個測試項目的輸出可以發現在 `q_insert_head` 的時候會失敗，失敗的原因是 `sysmalloc` 中的 Assertion。
因此，接著執行 `make valgrind` 來找出可能存在的問題，發現有許多的 `Invalid read` 發生在 `q_remove` 的時候，但是第14~16個測試案例都能夠通過。
```
$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/matt_jan/lab0-c'
rm -f 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 .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
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 shannon_entropy.o
CC linenoise.o
CC web.o
LD qtest
make[1]: Leaving directory '/home/matt_jan/lab0-c'
cp qtest /tmp/qtest.XDdHJ4
chmod u+x /tmp/qtest.XDdHJ4
sed -i "s/alarm/isnan/g" /tmp/qtest.XDdHJ4
scripts/driver.py -p /tmp/qtest.XDdHJ4 --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==141925== Invalid read of size 8
==141925== at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==141925== by 0x10F908: memcpy (string_fortified.h:29)
==141925== by 0x10F908: q_remove (queue.c:101)
==141925== by 0x10F932: q_remove_head (queue.c:112)
==141925== by 0x10C714: queue_remove (qtest.c:353)
==141925== by 0x10C8BC: do_rh (qtest.c:410)
==141925== by 0x10DFD1: interpret_cmda (console.c:181)
==141925== by 0x10E586: interpret_cmd (console.c:201)
==141925== by 0x10E987: cmd_select (console.c:610)
==141925== by 0x10F273: run_console (console.c:705)
==141925== by 0x10D3C3: main (qtest.c:1258)
==141925== Address 0x4b7a448 is 8 bytes before a block of size 2,049 alloc'd
==141925== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==141925== by 0x10C4B3: queue_remove (qtest.c:318)
==141925== by 0x10C8BC: do_rh (qtest.c:410)
==141925== by 0x10DFD1: interpret_cmda (console.c:181)
==141925== by 0x10E586: interpret_cmd (console.c:201)
==141925== by 0x10E987: cmd_select (console.c:610)
==141925== by 0x10F273: run_console (console.c:705)
==141925== by 0x10D3C3: main (qtest.c:1258)
--- trace-01-ops 0/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 0/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
--- trace-03-ops 0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 0/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
--- trace-06-ops 0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 0/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 0/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 53/100
make: *** [Makefile:73: valgrind] Error 1
```
:::danger
適度刪減以上輸出，保留關鍵的訊息來討論。
:::
將`memcpy`改為`strncpy`之後，`make valgrind`的分數得到了滿分，但是在`make test`中仍然無法獲得14~16測試案例的分數。有趣的是當將改動推送到Github時，Git Action的結果表示只有第17項測試案例失敗。
```
$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/matt_jan/lab0-c'
rm -f 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 .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
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 shannon_entropy.o
CC linenoise.o
CC web.o
LD qtest
make[1]: Leaving directory '/home/matt_jan/lab0-c'
cp qtest /tmp/qtest.sPHpZr
chmod u+x /tmp/qtest.sPHpZr
sed -i "s/alarm/isnan/g" /tmp/qtest.sPHpZr
scripts/driver.py -p /tmp/qtest.sPHpZr --valgrind
--- 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
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.sPHpZr --valgrind -t <tid>
```
:::warning
研讀指定的論文
:::
Sign in with Wallet
Connect another wallet