# 2020q1 Homework1 (lab0)
contributed by < `Yu-Wei-Chang` >
## 實驗環境
```shell
$ uname -a
Linux ywc-ThinkPad-X220 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
```
## 作業要求
* ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
* 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
## 補充 CMU ISC [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 的queue實作
### ==q_size==
* 作業要求其時間複雜度必須要是 O(1) , 也就是說不能透過遍歷整個 queue 來計算 queue 的長度, 因此必須在 queue_t 中增加變數來記錄 queue 長度.
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
int size; /* Number of elements in queue */
} queue_t;
```
* 在 新增 queue /新增節點/刪除節點時必須要維護 ==q->size== , 以確保程式運行的正確性.
* NULL queue 時返回0.
### ==q_insert_head==
* 優先處理 q_insert_head() 是因為[程式碼](https://github.com/sysprog21/lab0-c)抓下來編譯並且執行後, 立即可以發現在 queue head 插入資料後, 在印出 queue 內容時就掛掉了, 原因是 q_insert_head() 未完成實作.
```shell
$ ./qtest
cmd> new
cmd> new
q = []
cmd> ih test
cmd> ih test
q = [Segmentation fault occurred. You dereferenced a NULL or invalid pointer
已經終止 (核心已傾印)
```
* 實作要點如下:
* 為新的節點分配空間, 分配失敗的話返回 false.
* 為新節點的資料 (string) 分配空間, 分配失敗的話需要釋放新結點的空間, 然後返回 false.
* 分配給字串資料的空間長度採用 ==strlen(s) + 1==
* strncpy() 將字串資料複製到新節點中 (==newh->value==), 記得字串結尾補上 null character (=='\0'==), 用 strncpy() 限制長度, 確保不要寫到其他空間.
* 將新節點插入到 queue 的頭.
* ==newh->next = q->head;==
* ==q->head = newh;==
* 新節點加入後記得更新 queue 的長度. (==q->size++==)
### ==q_new==
* 為新的 queue (queue_t)分配空間, 若分配失敗則返回 NULL.
* 初始化 queue 長度為0 (==q->size = 0;==)
### ==q_free==
* 當 queue == NULL 時什麼都不做, 直接返回.
* 當 queue 為空時, 釋放分配給 queue 的空間.
* 若 queue 不為空時, 一個一個節點分別釋放分配給節點的空間. (資料以及結點本身)
* ==list_ele_t *eleh== 用來接當前要釋放的節點, 在釋放空間前先用 ==list_ele_t *elen== 把下一個節點接下來.
* 釋放完後, 判斷下一個節點是否為 NULL , 是則繼續釋放, 否則離開迴圈, 如此直到所有節點都是放完成.
```cpp
/* Free all storage used by queue */
void q_free(queue_t *q)
{
if (!q)
return;
if (q->head) {
list_ele_t *eleh, *elen; /* element head and next */
eleh = q->head;
while (eleh) {
elen = eleh->next;
free(eleh->value);
free(eleh);
if (elen)
eleh = elen;
else
eleh = NULL;
}
}
/* Free queue structure */
free(q);
}
```
### ==q_insert_tail==
* 作業要求其時間複雜度必須要是 O(1) , 也就是說不能走訪整個 queue 到尾巴再加入新節點, 因此必須在 ==queue_t== 中增加指標來記錄 tail 節點, 每次都從 ==q->tail== 去插入新節點.
```clike=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of head element */
list_ele_t *tail; /* Linked list of tail element */
int size; /* Number of elements in queue */
} queue_t;
```
* 在新增 queue /增加節點/刪除節點時要維護好 ==q->tail== , 以確保行為正確.
* 實作內容跟 ==q_insert_head()== 大致相同, 只是需要考慮以下要點:
* 如果這是 queue 中的第一個節點的話, 那記得將 ==q->head== 指向此節點.
* ==q->tail== 指向此節點
* 記得 ==q->size++==
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
if ((newh = malloc(sizeof(list_ele_t))) == NULL)
return false;
if ((newh->value = malloc(strlen(s) + 1)) == NULL) {
/* Free this element if we allocat value space failed. */
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
newh->value[strlen(s)] = '\0';
/* FIFO */
newh->next = NULL;
if (q->size == 0) {
/* Points head to this element if this is the first element. */
q->head = newh;
} else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
```
### ==q_remove_head==
* NULL queue / empty queue 直接返回false.
* 正確的操作 q->head, q->tail 以及q->size.
* q->head 指向下一個節點
* 如果 queue 沒有結點了, 那 q->tail 也要指向 NULL
* 記得遞減 q->size
* 如果傳入的 sp 非 NULL 的話, 需要把資料字串複製到該空間中, 要注意複製進去的字串大小, 不要超出 bufsize.
* 釋放分配給節點的空間 (資料和節點本身都是)
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *ele;
if (!q || !q->head)
return false;
ele = q->head;
q->head = q->head->next;
q->size--;
if (q->size == 0)
q->tail = NULL;
if (sp) {
if (strlen(ele->value) > bufsize) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, ele->value, strlen(ele->value));
sp[strlen(ele->value)] = '\0';
}
}
free(ele->value);
free(ele);
return true;
}
```
### ==q_reverse==
:::danger
避免說「參考自網路上的資料」，需要具體說是哪一份，否則這跟某些記者有何區別？
:notes: jserv
:::
* <s>參考自網路上的資料</s> 實作概念如下:
* 從頭遍歷整個 queue 的各節點, 將各節點的 next 指向前一個節點, 這樣的操作需要三個 pointer:
* 當前要處理的節點(==ele_cur==): reverse 需要改變節點的next(改成反向指向前一個節點)
* 下一個要處理的節點(==ele_next==): 如上, 節點的 next 會被修改, 但是我們又需要透過 next 才能遍歷整個 queue, 所以在修改節點時需要先使用 ==ele_next== 接住 next.
* 已經處理過的節點(==ele_pre==): 由於是要 reverse, 所以 head 的 next 在 reverse 後會指向 NULL (queue 尾巴), 所以其初始值設定為NULL; 每處理完一個節點後就會將 ==ele_pre== 指向該節點, 當成下一個處理節點的 next.
* 注意 ==q->head== 和 ==q->tail== 要被正確的指向reversed queue.
```cpp
void q_reverse(queue_t *q)
{
list_ele_t *ele_prev, *ele_cur, *ele_next;
if (!q || !q->head)
return;
ele_prev = NULL;
q->tail = ele_cur = q->head;
while (ele_cur) {
ele_next = ele_cur->next;
ele_cur->next = ele_prev;
ele_prev = ele_cur;
ele_cur = ele_next;
}
q->head = ele_prev;
}
```
### ==q_sort==
* 沿用 [2020q1 Quiz1](https://hackmd.io/@nUXhrHY5Rqij-Pe-MddonQ/BkEWKWZLL)的合併排序法函式.
```cpp
static list_ele_t *q_mergeSort(list_ele_t *start)
{
if (!start || !start->next)
return start;
list_ele_t *left = start;
list_ele_t *right = start->next;
left->next = NULL;
left = q_mergeSort(left);
right = q_mergeSort(right);
for (list_ele_t *merge = NULL; left || right;) {
if (!right || (left && (strncmp(left->value, right->value,
strlen(left->value)) < 0))) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
return start;
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
list_ele_t *elet;
if (!q || !q->head)
return;
if (q->size <= 1)
return;
q->head = q_mergeSort(q->head);
elet = q->head;
while (elet->next) {
elet = elet->next;
}
q->tail = elet;
}
```
:::danger
注意共筆書寫慣例：中英文間以一個半形空白區隔，請及早修正內容
:notes: jserv
:::
## 已知問題
### 結果驗證死在第 15 和 16 項測試, 只要資料加到 8000 筆左右, sort 就會發生 segmentation fault.
#### 問題排除
根據以下訊息判斷這不是程式碼邏輯上的錯誤, 而是大量反覆呼叫遞迴函式而把 stack 塞滿而造成的錯誤.
* 小數量的資料在進行排序時不會發生問題.
* 從程式碼中印出訊息, 嘗試找出錯誤發生在哪行程式碼, 結果發現發生問題時執行到的程式行數都不同.
* 找到類似情況可見討論 [Segmentation fault when calling function recursively](https://stackoverflow.com/questions/8007808/segmentation-fault-when-calling-function-recursively), 推斷是因為大量資料需要多次反覆呼叫遞迴，從而達到 stack 空間的限制.
嘗試用 GDB 找出行程因為大量反覆呼叫遞迴函式而把 stack 塞滿的證據
* 從 [GNU Debugger 的文件](https://sourceware.org/gdb/current/onlinedocs/gdb/Stack.html#Stack)說明: 每當程式呼叫函式時, 呼叫函式的位置/傳入的參數/被呼叫函式的區域變數等資訊都會被儲存成 ==stack frame== 在 ==call stack== 之中, 使用 GDB 可以查看 stack frame 的內容, 這裡我的目標是使用 GDB 來檢查 qtest 行程是否真的是在排序時大量呼叫遞迴函式而使用超出 stack 空間的限制.
* 目前實驗環境的最大 stack size 為 8192 Kbyte.
```shell
$ ulimit -a
...
stack size (kbytes, -s) 8192
```
* 確認我們的作業 qtest 在編譯時有加入 gcc 的 [-g](http://man7.org/linux/man-pages/man1/gcc.1.html) 選項, 使 gcc 在編譯時加入 GDB 所需的除錯訊息, 並且降低 gcc 最佳化選項 (-O1 -> -O0) 以避免 GDB 除錯時看到 < optimized_out >.
```shell
$ make VERBOSE=1
gcc -o qtest.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .qtest.o.d qtest.c
gcc -o report.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .report.o.d report.c
gcc -o console.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .console.o.d console.c
gcc -o harness.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .harness.o.d harness.c
gcc -o queue.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .queue.o.d queue.c
gcc -o random.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .random.o.d random.c
gcc -o dudect/constant.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .dudect/constant.o.d dudect/constant.c
gcc -o dudect/fixture.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .dudect/fixture.o.d dudect/fixture.c
gcc -o dudect/ttest.o -O0 -g -Wall -Werror -Idudect -I. -c -MMD -MF .dudect/ttest.o.d dudect/ttest.c
gcc -o qtest qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o -lm
```
* ~~發現問題發生後 GDB 的 stack 訊息量很少(只跑到 do_sort() 而已), 目前還不知道確切原因, 為了用 GDB 找 stack overflow 的證據, 所以暫時先將 do_sort() 函式中的 exception_setup() 和 exception_cancle() 註解掉. (實際跑 qtest 的自動測試時不能這樣幹)~~ ==更新: 只要 gcc 降低編譯最佳化選項就不會遇到這個問題了, 跟 exception_setup() 和 exception_cancle() 無關.==
```shell
(gdb) info stack
#0 0x0000555555555cd2 in do_sort (argc=<optimized out>, argv=<optimized out>) at qtest.c:561
#1 0x00005555555579d3 in interpret_cmda (argc=argc@entry=1, argv=argv@entry=0x55555589b400) at console.c:220
#2 0x0000555555557f47 in interpret_cmd (cmdline=<optimized out>) at console.c:243
#3 0x00005555555586b6 in cmd_select (nfds=<optimized out>, nfds@entry=0, readfds=0x7fffffffd9b0, readfds@entry=0x0, writefds=writefds@entry=0x0,
exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x0) at console.c:607
#4 0x000055555555875d in run_console (infile_name=0x0) at console.c:628
#5 0x0000555555556e82 in main (argc=1, argv=0x7fffffffdea8) at qtest.c:772
```
```diff
@@ -548,9 +548,9 @@ bool do_sort(int argc, char *argv[])
error_check();
set_noallocate_mode(true);
- if (exception_setup(true))
- q_sort(q);
- exception_cancel();
+ // if (exception_setup(true))
+ q_sort(q);
+ // exception_cancel();
set_noallocate_mode(false);
```
* 透過 GDB 檢查行程起頭 (main 函式) 一直到排序還未完成就 Segmentation fault 的遞迴函式 (q_mergeSort 函式), 其使用的call stack size 就非常接近 8192 Kbyte了, 所以確認此問題是因為使用超出 stack size 而造成的.
* 行程執行的最後一個 stack frame (==0x7fffff7ff030==) , 而且它的區域變數 left 和 right 都是 NULL (0x0)
* main 函式的 stack frame (==0x7fffffffddd0==) , 兩者相距 8187K
```shell
(gdb) info frame
Stack level 0, frame at 0x7fffff7ff030:
rip = 0x555555559f11 in q_mergeSort (queue.c:193); saved rip = 0x555555559f5e
called by frame at 0x7fffff7ff070
source language c.
Arglist at 0x7fffff7ff020, args: start=<error reading variable: Cannot access memory at address 0x7fffff7feff8>
Locals at 0x7fffff7ff020, Previous frame's sp is 0x7fffff7ff030
Saved registers:
rbp at 0x7fffff7ff020, rip at 0x7fffff7ff028
(gdb) info locals
left = 0x0
right = 0x0
(gdb) info frame
Stack level 130989, frame at 0x7fffffffddd0:
rip = 0x555555557222 in main (qtest.c:772); saved rip = 0x7ffff7667b97
caller of frame at 0x7fffffffdb80
source language c.
Arglist at 0x7fffffffddc0, args: argc=1, argv=0x7fffffffdea8
Locals at 0x7fffffffddc0, Previous frame's sp is 0x7fffffffddd0
Saved registers:
rbp at 0x7fffffffddc0, rip at 0x7fffffffddc8
```
改寫合併排序的實作, 避免使用過多的遞迴
* 參考[npes87184's blog](https://npes87184.github.io/2015-09-12-linkedListSort/), 目標是將整個 queue 從中間切開, 變成兩個長度相當的 list:
* 作法類似[龜兔賽跑(Floyd's algorithm)](http://www.csie.ntnu.edu.tw/~u91029/Function.html#4), 只是不用去找循環點/循環長度等等.
* 只要判斷 queue 還有2個以上的節點, 就持續龜走一步, 兔走兩步的動作, 只要讓跑得比較快的兔子走到 queue 尾巴, 這時候就知道烏龜正在 queue 的中間點.
* ==假設有 N 個節點, 原本拆分要進行的遞迴次數為 $2N - 1$ 次; 以此法修正後, 遞迴只需要 $\lceil N/2\rceil$ 次.==
```diff
diff --git a/queue.c b/queue.c
index 66870db..18e828f 100644
--- a/queue.c
+++ b/queue.c
@@ -194,13 +194,22 @@ static list_ele_t *q_mergeSort(list_ele_t *start)
if (!start || !start->next)
return start;
+ /* Divide */
list_ele_t *left = start;
list_ele_t *right = start->next;
+ while (right && right->next) {
+ /* If there are two more element remained, keep going */
+ right = right->next->next;
+ left = left->next;
+ }
+ right = left->next;
left->next = NULL;
+ /* Now we divide whole queue into two equivalent length list */
- left = q_mergeSort(left);
+ left = q_mergeSort(start);
right = q_mergeSort(right);
+ /* Merge */
for (list_ele_t *merge = NULL; left || right;) {
if (!right || (left && (strncmp(left->value, right->value,
strlen(left->value)) < 0))) {
```
* 如此可以修正大量遞迴造成 stack overflow 的問題, 但是 trace-15-perf 依然 fail, 問題在執行時間過長.
```shell
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
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
```
### trace-15-perf, Time limit exceeded (WIP)
#### 問題排除
* 參考[Code Review 解說錄影](https://youtu.be/3k_tJa-f_4M), 理解其思路並改寫排序方式, 但依然無法通過測項.
* ==後來發現排序時使用 strncmp() 或是 strnatcmp() , 此測試項目都會 fail.==
* ==只有使用 strcmp() 可以通過此測項==, 在排序時暫時先此用 strcmp() (在插入資料時都有確實對處理字串的 null terminated , 所以使用 strcmp() 是安全的)
### trace-16-perf failed, Not sorted in ascending order
#### 問題排除
* 簡化問題發生的步驟
```shell
cmd> new
q = []
cmd> ih aa
q = [aa]
cmd> ih aaa
q = [aaa aa]
cmd> sort
q = [aa aaa]
cmd> sort
ERROR: Not sorted in ascending order
q = [aaa aa]
cmd> sort
q = [aa aaa]
```
* 從上面的結果可以發現相同兩筆資料每次執行排序時結果不同, 因為排序字串時使用 strncmp() , 而且長度的參數一律是帶入 left->value 的長度, 所以造成此問題.
* 解決方式: strncmp() 前先判斷哪邊的資料長度較長, 傳入較長的字串長度.
```diff
diff --git a/queue.c b/queue.c
index 18e828f..1868c4d 100644
--- a/queue.c
+++ b/queue.c
@@ -211,8 +211,11 @@ static list_ele_t *q_mergeSort(list_ele_t *start)
/* Merge */
for (list_ele_t *merge = NULL; left || right;) {
- if (!right || (left && (strncmp(left->value, right->value,
- strlen(left->value)) < 0))) {
+ if (!right ||
+ (left && (strncmp(left->value, right->value,
+ (strlen(left->value) > strlen(right->value))
+ ? strlen(left->value)
+ : strlen(right->value)) < 0))) {
if (!merge) {
start = merge = left;
```
## 結果驗證
### 自動測試結果
```shell
$ 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
```
### valgrind結果
```shell
$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/ywc/training_data/linux_kernel/Week1_homework/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 .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 *~ 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
LD qtest
make[1]: Leaving directory '/home/ywc/training_data/linux_kernel/Week1_homework/lab0-c'
cp qtest /tmp/qtest.lNO37o
chmod u+x /tmp/qtest.lNO37o
sed -i "s/alarm/isnan/g" /tmp/qtest.lNO37o
scripts/driver.py -p /tmp/qtest.lNO37o --valgrind
--- 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
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.lNO37o --valgrind -t <tid>
```
###### tags: `Linux核心課程筆記 - Homework`
Sign in with Wallet
Connect another wallet