---
tags: Course
---
# 2020q1 Homework1 (lab0)
contributed by < `zoo868e` >
## 開發環境
```shell
$ uname -a
Linux zoo868e 4.15.0-88-generic #88-Ubuntu SMP Tue Feb 11 20:11:34 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
```
## 作業要求
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
* 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 不用理會 [Autolab](http://www.autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
* 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
* 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2020-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理;
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
## 開發過程
#### `q_size`
在`queue_t`結構中新增`int size`，若`q`為空則回傳0，否則回傳`q->size`。
```c=
int q_size(queue_t *q)
{
if(!q) return 0;
return q->size;
}
```
#### `q_new`
若 `malloc` 失敗時，回傳`NULL`。
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (!q) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### `q_free`
清空`q`所用到的空間，並釋放所有記憶體，用`*ptr`把每個節點做清空。
要注意`ptr->value`所使用的空間也要做釋放。
```c=
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
list_ele_t *ptr;
if(!q) return;
while (q->head) {
ptr = q->head;
q->head = ptr->next;
free(ptr->value);
free(ptr);
}
/* Free queue structure */
free(q);
}
```
#### `q_insert_head`
檢查`q`是否存在，若無則回傳`false`。
檢查新節點是否`malloc`成功，失敗則回傳`false`。
檢查節點中`value`是否`malloc`成功，失敗則釋放新節點空間，並回傳`false`。
`value`在`malloc`時，要注意給的空間為`strlen(s) + 1`，若沒有+1會有亂碼產生。
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q) {
return false;
}
/* TODO: What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
memcpy(newh->value, s, strlen(s) + 1);
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
newh->next = q->head;
q->head = newh;
if (q->size == 0) {
q->tail = newh;
}
q->size = q->size + 1;
return true;
}
```
#### `q_insert_tail`
在`queue_t`結構中新增`list_ele_t *tail`，由`tail`紀錄當前最後一個元素的位址，使`q_insert_tail`可在 $O(1)$ 時間內完成。
其餘要注意的細節跟`q_insert_head`大同小異。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
if (!q) {
return false;
}
newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
newt->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
if (!newt->value) {
free(newt);
return false;
}
memcpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (q->size == 0) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
q->size = q->size + 1;
return true;
}
```
#### `q_remove_head`
檢查`q`是否存在、有沒有內容，若否則回傳`false`。
把刪除節點之`value`放進`sp`中，並加上結束字元`\0`。
在`qtest.c`的`do_remove_head`會檢查刪除節點之`value`是否跟指令輸入的內容相同。
其餘跟`q_free`大同小異，只是從刪除所有節點變成刪除一個節點。
qtest.c
```c=
if (ok && check && strcmp(removes, checks)) {
report(1, "ERROR: Removed value %s != expected value %s", removes,checks);
ok = false;
}
```
queue.c
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *ptr;
if (q == NULL || q->size == 0) {
return false;
}
ptr = q->head;
if (sp) {
memcpy(sp, ptr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
q->head = q->head->next;
free(ptr->value);
free(ptr);
q->size = q->size - 1;
return true;
}
```
#### `q_reverse`
首先檢查`q`之大小是否需要reverse，再透過ptr將原本的順序做反向。
先將`ptr->next`存放在`nxt`，再把`ptr->next`指向`pre`，再把`pre`指向`ptr`，`ptr`指向`nxt`，迴圈重複直到`ptr`在最後一個節點，離開迴圈後把`ptr->next`指向`pre`，最後再把`q->head`指向`ptr`。
```c=
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1) {
return;
}
list_ele_t *ptr, *pre = NULL, *nxt;
q->tail = q->head;
ptr = q->head;
while (ptr->next) {
nxt = ptr->next;
ptr->next = pre;
pre = ptr;
ptr = nxt;
}
ptr->next = pre;
q->head = ptr;
}
```
#### `q_sort`
用merge sort做排序，使用`strnatcmp`做比較，但是結果跟`strcmp`相同，還在找是哪裡出了問題
```c=
void q_sort(queue_t *q)
{
if (!q || q->size <= 1) {
return;
}
q->head = merge_sort(q->head);
list_ele_t *t = q->head;
while (!t->next) {
t = t->next;
}
q->tail = t;
}
list_ele_t *merge_sort(list_ele_t *start)
{
if (!start || !start->next)
return start;
list_ele_t *left = start;
list_ele_t *right = start->next;
list_ele_t *head, *now;
while (right && right->next) {
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
left = merge_sort(start);
right = merge_sort(right);
if (strnatcmp(left->value, right->value) < 0) {
head = left;
left = left->next;
} else {
head = right;
right = right->next;
}
now = head;
while (left && right) {
if (strnatcmp(left->value, right->value) < 0) {
now->next = left;
left = left->next;
} else {
now->next = right;
right = right->next;
}
now = now->next;
}
if (!left) {
now->next = right;
}
if (!right) {
now->next = left;
}
return head;
}
```
:::danger
文字訊息不要用圖片來展現。
:notes: jserv
:::
執行`＄ make test`
```shell
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
```
執行`$ make valgrind`
有許多要改進的地方
```shell
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o strnatcmp.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 .strnatcmp.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 strnatcmp.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
make[1]: Leaving directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
cp qtest /tmp/qtest.PyDV22
chmod u+x /tmp/qtest.PyDV22
sed -i "s/alarm/isnan/g" /tmp/qtest.PyDV22
scripts/driver.py -c -p /tmp/qtest.PyDV22 --valgrind -v 3
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> rh dolphin
==21552== Invalid read of size 8
==21552== at 0x4C368AC: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21552== by 0x10CD4F: memcpy (string_fortified.h:34)
==21552== by 0x10CD4F: q_remove_head (queue.c:132)
==21552== by 0x10A118: do_remove_head (qtest.c:365)
==21552== by 0x10B952: interpret_cmda (console.c:220)
==21552== by 0x10BEC6: interpret_cmd (console.c:243)
==21552== by 0x10C494: cmd_select (console.c:571)
==21552== by 0x10C6DC: run_console (console.c:630)
==21552== by 0x10AE01: main (qtest.c:771)
==21552== Address 0x55cedf8 is 8 bytes before a block of size 2,049 allocated
==21552== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21552== by 0x109F76: do_remove_head (qtest.c:331)
==21552== by 0x10B952: interpret_cmda (console.c:220)
==21552== by 0x10BEC6: interpret_cmd (console.c:243)
==21552== by 0x10C494: cmd_select (console.c:571)
==21552== by 0x10C6DC: run_console (console.c:630)
==21552== by 0x10AE01: main (qtest.c:771)
==21552==
Removed dolphin from queue
q = [bear gerbil]
cmd> rh bear
==21552== Invalid read of size 8
==21552== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21552== by 0x10CD4F: memcpy (string_fortified.h:34)
==21552== by 0x10CD4F: q_remove_head (queue.c:132)
==21552== by 0x10A118: do_remove_head (qtest.c:365)
==21552== by 0x10B952: interpret_cmda (console.c:220)
==21552== by 0x10BEC6: interpret_cmd (console.c:243)
==21552== by 0x10C494: cmd_select (console.c:571)
==21552== by 0x10C6DC: run_console (console.c:630)
==21552== by 0x10AE01: main (qtest.c:771)
==21552== Address 0x55cea50 is 3 bytes after a block of size 45 allocated
==21552== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21552== by 0x10C777: test_malloc (harness.c:137)
==21552== by 0x10CBF2: q_insert_head (queue.c:62)
==21552== by 0x10A7CF: do_insert_head (qtest.c:213)
==21552== by 0x10B952: interpret_cmda (console.c:220)
==21552== by 0x10BEC6: interpret_cmd (console.c:243)
==21552== by 0x10C494: cmd_select (console.c:571)
==21552== by 0x10C6DC: run_console (console.c:630)
==21552== by 0x10AE01: main (qtest.c:771)
==21552==
==21552== Invalid read of size 8
==21552== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21552== by 0x10CD4F: memcpy (string_fortified.h:34)
==21552== by 0x10CD4F: q_remove_head (queue.c:132)
==21552== by 0x10A118: do_remove_head (qtest.c:365)
==21552== by 0x10B952: interpret_cmda (console.c:220)
==21552== by 0x10BEC6: interpret_cmd (console.c:243)
==21552== by 0x10C494: cmd_select (console.c:571)
==21552== by 0x10C6DC: run_console (console.c:630)
==21552== by 0x10AE01: main (qtest.c:771)
==21552== Address 0x55cea68 is 24 bytes after a block of size 48 in arena "client"
==21552==
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
--- trace-01-ops 0/6
+++ TESTING trace trace-02-ops:
cmd> # Test of insert_head, insert_tail, and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> rh dolphin
==21553== Invalid read of size 8
==21553== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21553== by 0x10CD4F: memcpy (string_fortified.h:34)
==21553== by 0x10CD4F: q_remove_head (queue.c:132)
==21553== by 0x10A118: do_remove_head (qtest.c:365)
==21553== by 0x10B952: interpret_cmda (console.c:220)
==21553== by 0x10BEC6: interpret_cmd (console.c:243)
==21553== by 0x10C494: cmd_select (console.c:571)
==21553== by 0x10C6DC: run_console (console.c:630)
==21553== by 0x10AE01: main (qtest.c:771)
==21553== Address 0x55cecf0 is 0 bytes after a block of size 48 allocated
==21553== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21553== by 0x10C777: test_malloc (harness.c:137)
==21553== by 0x10CBF2: q_insert_head (queue.c:62)
==21553== by 0x10A7CF: do_insert_head (qtest.c:213)
==21553== by 0x10B952: interpret_cmda (console.c:220)
==21553== by 0x10BEC6: interpret_cmd (console.c:243)
==21553== by 0x10C494: cmd_select (console.c:571)
==21553== by 0x10C6DC: run_console (console.c:630)
==21553== by 0x10AE01: main (qtest.c:771)
==21553==
==21553== Invalid read of size 8
==21553== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21553== by 0x10CD4F: memcpy (string_fortified.h:34)
==21553== by 0x10CD4F: q_remove_head (queue.c:132)
==21553== by 0x10A118: do_remove_head (qtest.c:365)
==21553== by 0x10B952: interpret_cmda (console.c:220)
==21553== by 0x10BEC6: interpret_cmd (console.c:243)
==21553== by 0x10C494: cmd_select (console.c:571)
==21553== by 0x10C6DC: run_console (console.c:630)
==21553== by 0x10AE01: main (qtest.c:771)
==21553== Address 0x55ced08 is 24 bytes after a block of size 48 in arena "client"
==21553==
Removed dolphin from queue
q = [bear gerbil meerkat bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil meerkat bear gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = [meerkat bear gerbil]
cmd> rh meerkat
Removed meerkat from queue
q = [bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
Freeing queue
--- trace-02-ops 0/6
+++ TESTING trace trace-03-ops:
cmd> # Test of insert_head, insert_tail, reverse, and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih dolphin
q = [dolphin]
cmd> ih bear
q = [bear dolphin]
cmd> ih gerbil
q = [gerbil bear dolphin]
cmd> reverse
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> reverse
q = [gerbil bear meerkat gerbil bear dolphin]
cmd> it squirrel
q = [gerbil bear meerkat gerbil bear dolphin squirrel]
cmd> reverse
q = [squirrel dolphin bear gerbil meerkat bear gerbil]
cmd> rh squirrel
==21554== Invalid read of size 8
==21554== at 0x4C368AC: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21554== by 0x10CD4F: memcpy (string_fortified.h:34)
==21554== by 0x10CD4F: q_remove_head (queue.c:132)
==21554== by 0x10A118: do_remove_head (qtest.c:365)
==21554== by 0x10B952: interpret_cmda (console.c:220)
==21554== by 0x10BEC6: interpret_cmd (console.c:243)
==21554== by 0x10C494: cmd_select (console.c:571)
==21554== by 0x10C6DC: run_console (console.c:630)
==21554== by 0x10AE01: main (qtest.c:771)
==21554== Address 0x55cfa58 is 8 bytes before a block of size 2,049 allocated
==21554== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21554== by 0x109F76: do_remove_head (qtest.c:331)
==21554== by 0x10B952: interpret_cmda (console.c:220)
==21554== by 0x10BEC6: interpret_cmd (console.c:243)
==21554== by 0x10C494: cmd_select (console.c:571)
==21554== by 0x10C6DC: run_console (console.c:630)
==21554== by 0x10AE01: main (qtest.c:771)
==21554==
Removed squirrel from queue
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> ih vulture
q = [vulture dolphin bear gerbil meerkat bear gerbil]
cmd> reverse
q = [gerbil bear meerkat gerbil bear dolphin vulture]
cmd> rh gerbil
==21554== Invalid read of size 8
==21554== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21554== by 0x10CD4F: memcpy (string_fortified.h:34)
==21554== by 0x10CD4F: q_remove_head (queue.c:132)
==21554== by 0x10A118: do_remove_head (qtest.c:365)
==21554== by 0x10B952: interpret_cmda (console.c:220)
==21554== by 0x10BEC6: interpret_cmd (console.c:243)
==21554== by 0x10C494: cmd_select (console.c:571)
==21554== by 0x10C6DC: run_console (console.c:630)
==21554== by 0x10AE01: main (qtest.c:771)
==21554== Address 0x55cf4c0 is 1 bytes after a block of size 47 allocated
==21554== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21554== by 0x10C777: test_malloc (harness.c:137)
==21554== by 0x10CC9D: q_insert_tail (queue.c:96)
==21554== by 0x10A548: do_insert_tail (qtest.c:298)
==21554== by 0x10B952: interpret_cmda (console.c:220)
==21554== by 0x10BEC6: interpret_cmd (console.c:243)
==21554== by 0x10C494: cmd_select (console.c:571)
==21554== by 0x10C6DC: run_console (console.c:630)
==21554== by 0x10AE01: main (qtest.c:771)
==21554==
==21554== Invalid read of size 8
==21554== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21554== by 0x10CD4F: memcpy (string_fortified.h:34)
==21554== by 0x10CD4F: q_remove_head (queue.c:132)
==21554== by 0x10A118: do_remove_head (qtest.c:365)
==21554== by 0x10B952: interpret_cmda (console.c:220)
==21554== by 0x10BEC6: interpret_cmd (console.c:243)
==21554== by 0x10C494: cmd_select (console.c:571)
==21554== by 0x10C6DC: run_console (console.c:630)
==21554== by 0x10AE01: main (qtest.c:771)
==21554== Address 0x55cf4d8 is 24 bytes after a block of size 48 in arena "client"
==21554==
Removed gerbil from queue
q = [bear meerkat gerbil bear dolphin vulture]
cmd> rh bear
Removed bear from queue
q = [meerkat gerbil bear dolphin vulture]
cmd> rh meerkat
Removed meerkat from queue
q = [gerbil bear dolphin vulture]
cmd> rh gerbil
Removed gerbil from queue
q = [bear dolphin vulture]
cmd> rh bear
Removed bear from queue
q = [dolphin vulture]
cmd> rh dolphin
Removed dolphin from queue
q = [vulture]
cmd> rh vulture
Removed vulture from queue
q = []
Freeing queue
--- trace-03-ops 0/6
+++ TESTING trace trace-04-ops:
cmd> # Test of insert_head, insert_tail, size, and sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> size
Queue size = 3
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> size
Queue size = 6
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> sort
q = [bear bear dolphin gerbil gerbil meerkat]
cmd> rh bear
==21555== Invalid read of size 8
==21555== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21555== by 0x10CD4F: memcpy (string_fortified.h:34)
==21555== by 0x10CD4F: q_remove_head (queue.c:132)
==21555== by 0x10A118: do_remove_head (qtest.c:365)
==21555== by 0x10B952: interpret_cmda (console.c:220)
==21555== by 0x10BEC6: interpret_cmd (console.c:243)
==21555== by 0x10C494: cmd_select (console.c:571)
==21555== by 0x10C6DC: run_console (console.c:630)
==21555== by 0x10AE01: main (qtest.c:771)
==21555== Address 0x55cf290 is 3 bytes after a block of size 45 allocated
==21555== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21555== by 0x10C777: test_malloc (harness.c:137)
==21555== by 0x10CC9D: q_insert_tail (queue.c:96)
==21555== by 0x10A548: do_insert_tail (qtest.c:298)
==21555== by 0x10B952: interpret_cmda (console.c:220)
==21555== by 0x10BEC6: interpret_cmd (console.c:243)
==21555== by 0x10C494: cmd_select (console.c:571)
==21555== by 0x10C6DC: run_console (console.c:630)
==21555== by 0x10AE01: main (qtest.c:771)
==21555==
==21555== Invalid read of size 8
==21555== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21555== by 0x10CD4F: memcpy (string_fortified.h:34)
==21555== by 0x10CD4F: q_remove_head (queue.c:132)
==21555== by 0x10A118: do_remove_head (qtest.c:365)
==21555== by 0x10B952: interpret_cmda (console.c:220)
==21555== by 0x10BEC6: interpret_cmd (console.c:243)
==21555== by 0x10C494: cmd_select (console.c:571)
==21555== by 0x10C6DC: run_console (console.c:630)
==21555== by 0x10AE01: main (qtest.c:771)
==21555== Address 0x55cf2a8 is 24 bytes after a block of size 48 in arena "client"
==21555==
Removed bear from queue
q = [bear dolphin gerbil gerbil meerkat]
cmd> rh
Removed bear from queue
q = [dolphin gerbil gerbil meerkat]
cmd> rh
Removed dolphin from queue
q = [gerbil gerbil meerkat]
cmd> rh
Removed gerbil from queue
q = [gerbil meerkat]
cmd> size
Queue size = 2
q = [gerbil meerkat]
cmd>
Freeing queue
--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
cmd> # Test of insert_head, insert_tail, remove_head, reverse, size, and sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih dolphin
q = [dolphin]
cmd> ih bear
q = [bear dolphin]
cmd> ih gerbil
q = [gerbil bear dolphin]
cmd> reverse
q = [dolphin bear gerbil]
cmd> size
Queue size = 3
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> size
Queue size = 6
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> rh dolphin
==21556== Invalid read of size 8
==21556== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21556== by 0x10CD4F: memcpy (string_fortified.h:34)
==21556== by 0x10CD4F: q_remove_head (queue.c:132)
==21556== by 0x10A118: do_remove_head (qtest.c:365)
==21556== by 0x10B952: interpret_cmda (console.c:220)
==21556== by 0x10BEC6: interpret_cmd (console.c:243)
==21556== by 0x10C494: cmd_select (console.c:571)
==21556== by 0x10C6DC: run_console (console.c:630)
==21556== by 0x10AE01: main (qtest.c:771)
==21556== Address 0x55ce9a0 is 0 bytes after a block of size 48 allocated
==21556== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21556== by 0x10C777: test_malloc (harness.c:137)
==21556== by 0x10CBF2: q_insert_head (queue.c:62)
==21556== by 0x10A7CF: do_insert_head (qtest.c:213)
==21556== by 0x10B952: interpret_cmda (console.c:220)
==21556== by 0x10BEC6: interpret_cmd (console.c:243)
==21556== by 0x10C494: cmd_select (console.c:571)
==21556== by 0x10C6DC: run_console (console.c:630)
==21556== by 0x10AE01: main (qtest.c:771)
==21556==
==21556== Invalid read of size 8
==21556== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21556== by 0x10CD4F: memcpy (string_fortified.h:34)
==21556== by 0x10CD4F: q_remove_head (queue.c:132)
==21556== by 0x10A118: do_remove_head (qtest.c:365)
==21556== by 0x10B952: interpret_cmda (console.c:220)
==21556== by 0x10BEC6: interpret_cmd (console.c:243)
==21556== by 0x10C494: cmd_select (console.c:571)
==21556== by 0x10C6DC: run_console (console.c:630)
==21556== by 0x10AE01: main (qtest.c:771)
==21556== Address 0x55ce9b8 is 24 bytes after a block of size 48 in arena "client"
==21556==
Removed dolphin from queue
q = [bear gerbil meerkat bear gerbil]
cmd> reverse
q = [gerbil bear meerkat gerbil bear]
cmd> size
Queue size = 5
q = [gerbil bear meerkat gerbil bear]
cmd> sort
q = [bear bear gerbil gerbil meerkat]
cmd> rh bear
Removed bear from queue
q = [bear gerbil gerbil meerkat]
cmd> rh bear
Removed bear from queue
q = [gerbil gerbil meerkat]
cmd> rh gerbil
Removed gerbil from queue
q = [gerbil meerkat]
cmd> rh gerbil
Removed gerbil from queue
q = [meerkat]
cmd> rh meerkat
Removed meerkat from queue
q = []
cmd> size
Queue size = 0
q = []
cmd> free
q = NULL
Freeing queue
--- trace-05-ops 0/5
+++ TESTING trace trace-06-string:
cmd> # Test of truncated strings
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih aardvark_bear_dolphin_gerbil_jaguar 5
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> it meerkat_panda_squirrel_vulture_wolf 5
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf]
cmd> rh aardvark_bear_dolphin_gerbil_jaguar
==21557== Invalid read of size 8
==21557== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21557== by 0x10CD4F: memcpy (string_fortified.h:34)
==21557== by 0x10CD4F: q_remove_head (queue.c:132)
==21557== by 0x10A118: do_remove_head (qtest.c:365)
==21557== by 0x10B952: interpret_cmda (console.c:220)
==21557== by 0x10BEC6: interpret_cmd (console.c:243)
==21557== by 0x10C494: cmd_select (console.c:571)
==21557== by 0x10C6DC: run_console (console.c:630)
==21557== by 0x10AE01: main (qtest.c:771)
==21557== Address 0x55cecc0 is 4 bytes after a block of size 76 allocated
==21557== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21557== by 0x10C777: test_malloc (harness.c:137)
==21557== by 0x10CBF2: q_insert_head (queue.c:62)
==21557== by 0x10A7CF: do_insert_head (qtest.c:213)
==21557== by 0x10B952: interpret_cmda (console.c:220)
==21557== by 0x10BEC6: interpret_cmd (console.c:243)
==21557== by 0x10C494: cmd_select (console.c:571)
==21557== by 0x10C6DC: run_console (console.c:630)
==21557== by 0x10AE01: main (qtest.c:771)
==21557==
==21557== Invalid read of size 8
==21557== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21557== by 0x10CD4F: memcpy (string_fortified.h:34)
==21557== by 0x10CD4F: q_remove_head (queue.c:132)
==21557== by 0x10A118: do_remove_head (qtest.c:365)
==21557== by 0x10B952: interpret_cmda (console.c:220)
==21557== by 0x10BEC6: interpret_cmd (console.c:243)
==21557== by 0x10C494: cmd_select (console.c:571)
==21557== by 0x10C6DC: run_console (console.c:630)
==21557== by 0x10AE01: main (qtest.c:771)
==21557== Address 0x55cecd8 is 24 bytes after a block of size 80 in arena "client"
==21557==
Removed aardvark_bear_dolphin_gerbil_jaguar from queue
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf]
cmd> reverse
q = [meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> rh meerkat_panda_squirrel_vulture_wolf
Removed meerkat_panda_squirrel_vulture_wolf from queue
q = [meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> option length 30
cmd> rh meerkat_panda_squirrel_vulture
Removed meerkat_panda_squirrel_vulture from queue
q = [meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> reverse
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf]
cmd> option length 28
cmd> rh aardvark_bear_dolphin_gerbil
Removed aardvark_bear_dolphin_gerbil from queue
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf]
cmd> option length 21
cmd> rh aardvark_bear_dolphin
Removed aardvark_bear_dolphin from queue
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf]
cmd> reverse
q = [meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> option length 22
cmd> rh meerkat_panda_squirrel
Removed meerkat_panda_squirrel from queue
q = [meerkat_panda_squirrel_vulture_wolf meerkat_panda_squirrel_vulture_wolf aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> option length 7
cmd> rh meerkat
Removed meerkat from queue
q = [meerkat_panda_squirrel_vulture_wolf aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar]
cmd> reverse
q = [aardvark_bear_dolphin_gerbil_jaguar aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf]
cmd> option length 8
cmd> rh aardvark
Removed aardvark from queue
q = [aardvark_bear_dolphin_gerbil_jaguar meerkat_panda_squirrel_vulture_wolf]
cmd> option length 100
cmd> rh aardvark_bear_dolphin_gerbil_jaguar
==21557== Invalid read of size 2
==21557== at 0x4C36750: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21557== by 0x10CD4F: memcpy (string_fortified.h:34)
==21557== by 0x10CD4F: q_remove_head (queue.c:132)
==21557== by 0x10A118: do_remove_head (qtest.c:365)
==21557== by 0x10B952: interpret_cmda (console.c:220)
==21557== by 0x10BEC6: interpret_cmd (console.c:243)
==21557== by 0x10C494: cmd_select (console.c:571)
==21557== by 0x10C6DC: run_console (console.c:630)
==21557== by 0x10AE01: main (qtest.c:771)
==21557== Address 0x55ce8b0 is 16 bytes before a block of size 56 freed
==21557== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21557== by 0x10C977: test_free (harness.c:209)
==21557== by 0x10CD70: q_remove_head (queue.c:137)
==21557== by 0x10A118: do_remove_head (qtest.c:365)
==21557== by 0x10B952: interpret_cmda (console.c:220)
==21557== by 0x10BEC6: interpret_cmd (console.c:243)
==21557== by 0x10C494: cmd_select (console.c:571)
==21557== by 0x10C6DC: run_console (console.c:630)
==21557== by 0x10AE01: main (qtest.c:771)
==21557== Block was allocated at
==21557== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21557== by 0x10C777: test_malloc (harness.c:137)
==21557== by 0x10CBCE: q_insert_head (queue.c:58)
==21557== by 0x10A7CF: do_insert_head (qtest.c:213)
==21557== by 0x10B952: interpret_cmda (console.c:220)
==21557== by 0x10BEC6: interpret_cmd (console.c:243)
==21557== by 0x10C494: cmd_select (console.c:571)
==21557== by 0x10C6DC: run_console (console.c:630)
==21557== by 0x10AE01: main (qtest.c:771)
==21557==
Removed aardvark_bear_dolphin_gerbil_jaguar from queue
q = [meerkat_panda_squirrel_vulture_wolf]
cmd> reverse
q = [meerkat_panda_squirrel_vulture_wolf]
cmd> sort
Warning: Calling sort on single node
q = [meerkat_panda_squirrel_vulture_wolf]
cmd> rh meerkat_panda_squirrel_vulture_wolf
Removed meerkat_panda_squirrel_vulture_wolf from queue
q = []
cmd> free
q = NULL
cmd> quit
Freeing queue
--- trace-06-string 0/6
+++ TESTING trace trace-07-robust:
cmd> # Test operations on NULL queue
cmd> option fail 10
cmd> option malloc 0
cmd> free
Warning: Calling free on null queue
q = NULL
cmd> ih bear
Warning: Calling insert head on null queue
Insertion of bear failed
q = NULL
cmd> it dolphin
Warning: Calling insert tail on null queue
Insertion of dolphin failed
q = NULL
cmd> rh
Warning: Calling remove head on null queue
Removal from queue failed
q = NULL
cmd> reverse
Warning: Calling reverse on null queue
q = NULL
cmd> size
Warning: Calling size on null queue
Queue size = 0
q = NULL
cmd> sort
Warning: Calling sort on null queue
Warning: Calling sort on single node
q = NULL
Freeing queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
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
q = []
Freeing queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
cmd> # Test remove_head with NULL argument
cmd> option fail 10
cmd> option malloc 0
cmd> new
q = []
cmd> ih bear
q = [bear]
cmd> rhq
Removed element from queue
q = []
cmd>
Freeing queue
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
cmd> # Test of malloc failure on new
cmd> option fail 10
cmd> option malloc 50
cmd> new
WARNING: Malloc returning NULL
q = NULL
cmd> new
WARNING: Malloc returning NULL
q = NULL
cmd> new
WARNING: Malloc returning NULL
q = NULL
cmd> new
q = []
cmd> new
Freeing old queue
q = NULL
q = []
cmd> new
Freeing old queue
q = NULL
q = []
cmd>
cmd>
Freeing queue
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
cmd> # Test of malloc failure on insert_head
cmd> option fail 30
cmd> option malloc 0
cmd> new
q = []
cmd> option malloc 25
cmd> ih gerbil 20
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
q = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil]
cmd>
cmd>
cmd>
Freeing queue
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
cmd> # Test of malloc failure on insert_tail
cmd> option fail 50
cmd> option malloc 0
cmd> new
q = []
cmd> ih jaguar 20
q = [jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar]
cmd> option malloc 25
cmd> it gerbil 20
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
WARNING: Malloc returning NULL
Insertion of gerbil failed
q = [jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar jaguar gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd>
cmd>
cmd>
Freeing queue
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
cmd> # Test performance of insert_tail
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih dolphin 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 1000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
q = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> it jaguar 1000
q = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
Freeing queue
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
cmd> # Test performance of size
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih dolphin 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> size 1000
Queue size = 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd>
Freeing queue
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
cmd> # Test performance of insert_tail, size, reverse, and sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih dolphin 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> size 1000
Queue size = 2000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
q = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> size 1000
Queue size = 2000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd>
Freeing queue
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
cmd> # Test performance of sort with random and descending orders
cmd> # 10000: all correct sorting algorithms are expected pass
cmd> # 50000: sorting algorithms with O(n^2) time complexity are expected failed
cmd> # 100000: sorting algorithms with O(nlogn) time complexity are expected pass
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih RAND 10000
q = [nnzqrox osfqt siochggpl pkhwivwac dzthwscic inmehxmyq jkovrsqn tojktz wfxvulg qklumfb hlctppf uberxx fxiobzr oivafjbnm hxflkqxu ymlfvjhe yytvkek hfszquzen hmvgif nlxmj zxnrm kaqwzf bzhpjxxq ptrekf wefztee knpni afsvhsnp pdxcvb gcbvy tcargsjp ... ]
cmd> sort
q = [aaacovyr aacbioip aacwgebh aaeiko aafih aafoeynq aagtrzfey aaqrccvr aargge aarzvjg aasfyhzmd aasgivfqf aaufka aauoa aaydcid aazra abcbcapz abcqy abcrdu abedbkjf abkjte abkrfpz ablywoqmo abmljem abnqdnb absnljfvn abszn abvgmawrx abwave abyfinygc ... ]
cmd> reverse
q = [zzzfa zzyuc zzsew zzrlwq zzpqlsw zzorse zzoohvq zzoaae zzhkija zzetkrcav zzdyolsqn zzcltwls zzcfhyo zzbwt zzbjqlonz zzahihuis zyyaeka zyxbfgzu zyvwop zyvjv zyuqbnj zytsinip zyrqeq zyptuu zynnfttn zymyvigf zymrjb zymippj zygbg zyejo ... ]
cmd> sort
q = [aaacovyr aacbioip aacwgebh aaeiko aafih aafoeynq aagtrzfey aaqrccvr aargge aarzvjg aasfyhzmd aasgivfqf aaufka aauoa aaydcid aazra abcbcapz abcqy abcrdu abedbkjf abkjte abkrfpz ablywoqmo abmljem abnqdnb absnljfvn abszn abvgmawrx abwave abyfinygc ... ]
cmd> free
q = NULL
cmd> new
q = []
cmd> ih RAND 50000
q = [hxqmhea xgfgcafr stgkrplk wprwoosgf rzuhhyl phhzmgi inqwyz airrsqh qieyj renumigz olghwzpkx lrwvy zlaftxbft frjth cjkfnsh gxvkwj tenocdsl eznvuourl vynchke syvztr ayrvyxx shjva axilurlft clphbgd hyibk wdqpvemv uohizom ruzfabfn tuwzsgtq xjzfsqo ... ]
cmd> sort
q = [aaaboj aaafoqg aaaikm aaapl aaauxtm aabcegwz aabep aabfvo aabmc aabmnihn aabtp aacidcwtn aacsogh aadcuc aaddoxdxr aadwwj aadyloqhw aaeam aaenmr aafdewhq aaflyf aafpmfx aaftrsuij aagluh aagndlfqt aagnfrc aagyejctq aagzvumd aahbf aahcd ... ]
cmd> reverse
q = [zzzwiasac zzzddmqfz zzypcjuk zzxyv zzxvudzm zzxuuu zzxrd zzxokqfa zzxlwsxe zzxgpayd zzxbed zzwzz zzwrcxii zzwjx zzwgarclk zzvosflcq zzvgjn zzvdu zzuwhdvjz zzukqogca zzueltsd zzudxhjo zztuxhk zztaf zzsql zzsihnz zzrtlhg zzrnkqk zzrleoypb zzqnh ... ]
cmd> sort
q = [aaaboj aaafoqg aaaikm aaapl aaauxtm aabcegwz aabep aabfvo aabmc aabmnihn aabtp aacidcwtn aacsogh aadcuc aaddoxdxr aadwwj aadyloqhw aaeam aaenmr aafdewhq aaflyf aafpmfx aaftrsuij aagluh aagndlfqt aagnfrc aagyejctq aagzvumd aahbf aahcd ... ]
cmd> free
q = NULL
cmd> new
q = []
cmd> ih RAND 100000
q = [okrocp nozal luebxor smryswq baqxfk fqkjsbys fuvphsvq nxcnfinjc xggfi fgrfu jjvkafe uoivvtic isyvn gknzkymrk wbctawb cbrhlvk njzzc kobdx zfyqjjfjc tzrmtt hwysh snprbjmy rlrrak jigllxjly xadmfxor zlmmhpyl wgsolxaa dviifp vxkqmludm jfunlgaef ... ]
cmd> sort
q = [aaaaba aaacong aaaetnx aaafe aaawtrw aaaye aabco aabfr aabiwytu aabksuhov aacaqxja aacdrdd aacduakwc aaclzzyr aacmbsnyv aacmui aacuw aacwp aadclag aadeieuni aadhfb aadjravdd aadjrm aadljot aaelwel aaepazer aaesans aaffpzqnv aafmc aafpg ... ]
cmd> reverse
q = [zzznp zzznjnb zzzlghrk zzzhyeb zzzczbiyg zzysx zzyrnczxy zzylzihz zzylakgmp zzykdwrb zzydr zzxnseygk zzxncwwui zzxmpjiz zzxir zzxdpltps zzwxemvb zzwuluffo zzwudu zzwozti zzwowbvnp zzwothnx zzwncqsmq zzvui zzvpk zzvdfi zzvbbuw zzuvodjy zzuuxxn zzurbi ... ]
cmd> sort
q = [aaaaba aaacong aaaetnx aaafe aaawtrw aaaye aabco aabfr aabiwytu aabksuhov aacaqxja aacdrdd aacduakwc aaclzzyr aacmbsnyv aacmui aacuw aacwp aadclag aadeieuni aadhfb aadjravdd aadjrm aadljot aaelwel aaepazer aaesans aaffpzqnv aafmc aafpg ... ]
cmd> free
q = NULL
Freeing queue
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> it
Probably constant time
cmd> size
Probably constant time
cmd> option simulation 0
Freeing queue
--- trace-17-complexity 5/5
--- TOTAL 65/100
Test with specific case by running command:
scripts/driver.py -c -p /tmp/qtest.PyDV22 --valgrind -v 3 -t <tid>
```
## 用Valgrind做改進
### 改寫 MakeFile
由於想在`$ make valgrind`時只做其中一項測試，所以修改 MakeFile 讓每個測試可以單獨運行，下面是針對`trace-01-ops`做的改寫，其他測試依`scripts/driver.py`中的編號類推
```shell=
valgrind_01: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -c -p $(patched_file) --valgrind -v 3 -t 01
```
:::warning
或者搭配環境變數，例如讓 (修改過的) Python script 參照一個環境變數 `$QITEM`，於是就可以 `$ QITEM=01 make valgrind`
:notes: jserv
:::
:::success
根據老師的建議，在Python script參照環境變數`$QITEM`，沒學過Python所以直覺的認為是在某個文件裡面興增變數`$QITEM`，依序找到
* [Making Use of Environment Variables in Python](https://www.nylas.com/blog/making-use-of-environment-variables-in-python/)
* [Python dotenv 介紹與使用教學](https://myapollo.com.tw/zh-tw/python-dotenv/)
* [ theskumar / python-dotenv ](https://github.com/theskumar/python-dotenv)
並建立檔案`.env`存放變數，並在`scripts/driver.py`引入變數
`.env`
```shell=
QITEM='0'
```
`scripts/driver.py`
```python=
import os
from dotenv import load_dotenv
load_dotenv()
os.getenv("QITEM")
tid = os.environ['QITEM']
```
實做後發現沒辦法在`driver.py`執行期間修改`.env`的內容，又與老師建議的 command 不同，於是猜測根本不須要存變數，執行 command 時變數會自動引入`os.environ`中，於是修改`scripts/driver.py`
```python=
import os
#from dotenv import load_dotenv
#load_dotenv()
#os.getenv("QITEM")
tid = 0
if(os.environ.get('QITEM')):
tid = int(os.environ['QITEM'])
```
執行`$ QITEM=1 make valgrind`
```shell
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o strnatcmp.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 .strnatcmp.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 strnatcmp.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
make[1]: Leaving directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
cp qtest /tmp/qtest.fyA42u
chmod u+x /tmp/qtest.fyA42u
sed -i "s/alarm/isnan/g" /tmp/qtest.fyA42u
scripts/driver.py -c -p /tmp/qtest.fyA42u --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
--- TOTAL 6/6
Test with specific case by running command:
scripts/driver.py -c -p /tmp/qtest.fyA42u --valgrind -v 3 -t <tid>
```
發現跟猜想的一樣，參數會自動放進`os.environ`中，完成老師建議的方法
> [name=zoo868e] [time=Thu, Mar 5, 2020 2:16 AM]
:::
### trace-01-ops
執行`$ scripts/driver.py -c -p /tmp/qtest.8Km0GI --valgrind -v 3 -t 01`
``` shell
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> rh dolphin
==5008== Invalid read of size 8
==5008== at 0x4C368AC: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5008== by 0x10CD4A: memcpy (string_fortified.h:34)
==5008== by 0x10CD4A: q_remove_head (queue.c:129)
==5008== by 0x10A118: do_remove_head (qtest.c:365)
==5008== by 0x10B952: interpret_cmda (console.c:220)
==5008== by 0x10BEC6: interpret_cmd (console.c:243)
==5008== by 0x10C494: cmd_select (console.c:571)
==5008== by 0x10C6DC: run_console (console.c:630)
==5008== by 0x10AE01: main (qtest.c:771)
==5008== Address 0x55cedf8 is 8 bytes before a block of size 2,049 allocated
==5008== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5008== by 0x109F76: do_remove_head (qtest.c:331)
==5008== by 0x10B952: interpret_cmda (console.c:220)
==5008== by 0x10BEC6: interpret_cmd (console.c:243)
==5008== by 0x10C494: cmd_select (console.c:571)
==5008== by 0x10C6DC: run_console (console.c:630)
==5008== by 0x10AE01: main (qtest.c:771)
==5008==
Removed dolphin from queue
q = [bear gerbil]
cmd> rh bear
==5008== Invalid read of size 8
==5008== at 0x4C367EE: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5008== by 0x10CD4A: memcpy (string_fortified.h:34)
==5008== by 0x10CD4A: q_remove_head (queue.c:129)
==5008== by 0x10A118: do_remove_head (qtest.c:365)
==5008== by 0x10B952: interpret_cmda (console.c:220)
==5008== by 0x10BEC6: interpret_cmd (console.c:243)
==5008== by 0x10C494: cmd_select (console.c:571)
==5008== by 0x10C6DC: run_console (console.c:630)
==5008== by 0x10AE01: main (qtest.c:771)
==5008== Address 0x55cea50 is 3 bytes after a block of size 45 allocated
==5008== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5008== by 0x10C777: test_malloc (harness.c:137)
==5008== by 0x10CBF2: q_insert_head (queue.c:62)
==5008== by 0x10A7CF: do_insert_head (qtest.c:213)
==5008== by 0x10B952: interpret_cmda (console.c:220)
==5008== by 0x10BEC6: interpret_cmd (console.c:243)
==5008== by 0x10C494: cmd_select (console.c:571)
==5008== by 0x10C6DC: run_console (console.c:630)
==5008== by 0x10AE01: main (qtest.c:771)
==5008==
==5008== Invalid read of size 8
==5008== at 0x4C367E0: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5008== by 0x10CD4A: memcpy (string_fortified.h:34)
==5008== by 0x10CD4A: q_remove_head (queue.c:129)
==5008== by 0x10A118: do_remove_head (qtest.c:365)
==5008== by 0x10B952: interpret_cmda (console.c:220)
==5008== by 0x10BEC6: interpret_cmd (console.c:243)
==5008== by 0x10C494: cmd_select (console.c:571)
==5008== by 0x10C6DC: run_console (console.c:630)
==5008== by 0x10AE01: main (qtest.c:771)
==5008== Address 0x55cea68 is 24 bytes after a block of size 48 in arena "client"
==5008==
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
--- trace-01-ops 0/6
--- TOTAL 0/6
```
發現在 `queue.c` 中的 `q_remove_head` 使用到 `memcpy` 會有invalid memory access 的問題，修改 `q_remove_head` 中`memcpy` 讀取 `ptr->value` 的長度，解決 invalid memory access的 問題。
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *ptr;
if (q == NULL || q->size == 0 || !q->head || !q->head->value) {
return false;
}
ptr = q->head;
if (sp && ptr->value) {
if(strlen(ptr->value) <= bufsize){
memcpy(sp, ptr->value, strlen(ptr->value));
sp[strlen(ptr->value)] = '\0';
}else{
memcpy(sp, ptr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
q->head = q->head->next;
free(ptr->value);
free(ptr);
q->size = q->size - 1;
return true;
}
```
執行 `$ make valgrind_01`，可以看到已經不存在 invalid memory access
```shell
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o strnatcmp.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 .strnatcmp.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 strnatcmp.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
make[1]: Leaving directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
cp qtest /tmp/qtest.hAgmkX
chmod u+x /tmp/qtest.hAgmkX
sed -i "s/alarm/isnan/g" /tmp/qtest.hAgmkX
scripts/driver.py -c -p /tmp/qtest.hAgmkX --valgrind -v 3 -t 01
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
q = [bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
--- trace-01-ops 6/6
--- TOTAL 6/6
```
### trace-02-ops
修改完 `q_remove_head` 的 `memcpy` 造成的 invalid memory access，執行`$ make valgrind_02`，發現原本的錯誤已經被解決
```shell
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o strnatcmp.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 .strnatcmp.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 strnatcmp.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
make[1]: Leaving directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
cp qtest /tmp/qtest.Nlmlwj
chmod u+x /tmp/qtest.Nlmlwj
sed -i "s/alarm/isnan/g" /tmp/qtest.Nlmlwj
scripts/driver.py -c -p /tmp/qtest.Nlmlwj --valgrind -v 3 -t 02
--- Trace Points
+++ TESTING trace trace-02-ops:
cmd> # Test of insert_head, insert_tail, and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih gerbil
q = [gerbil]
cmd> ih bear
q = [bear gerbil]
cmd> ih dolphin
q = [dolphin bear gerbil]
cmd> it meerkat
q = [dolphin bear gerbil meerkat]
cmd> it bear
q = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
q = [dolphin bear gerbil meerkat bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
q = [bear gerbil meerkat bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil meerkat bear gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = [meerkat bear gerbil]
cmd> rh meerkat
Removed meerkat from queue
q = [bear gerbil]
cmd> rh bear
Removed bear from queue
q = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
q = []
Freeing queue
--- trace-02-ops 6/6
--- TOTAL 6/6
```
懷疑有重複的問題發生在 `q_remove_head`，於是再次執行 `$ make valgrind`，確定之前所有的問題都在 `memcpy` 讀取的 `ptr->value` 上
```shell
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o strnatcmp.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 .strnatcmp.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 strnatcmp.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
LD qtest
make[1]: Leaving directory '/home/zoo868e/Desktop/learn_linux/lab0-c'
cp qtest /tmp/qtest.MroSIp
chmod u+x /tmp/qtest.MroSIp
sed -i "s/alarm/isnan/g" /tmp/qtest.MroSIp
scripts/driver.py -c -p /tmp/qtest.MroSIp --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 -c -p /tmp/qtest.MroSIp --valgrind -v 3 -t <tid>
```
### 參考資料
[Making Use of Environment Variables in Python](https://www.nylas.com/blog/making-use-of-environment-variables-in-python/)
[Python dotenv 介紹與使用教學](https://myapollo.com.tw/zh-tw/python-dotenv/)
[ theskumar / python-dotenv ](https://github.com/theskumar/python-dotenv)
Sign in with Wallet
Connect another wallet