# 2020q3 Homework1 (lab0)
contributed by < s1041562 >
## Outline
* [Environment](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?both#Environment)
* [開發紀錄](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?both#%E9%96%8B%E7%99%BC%E7%B4%80%E9%8C%84)
* [queue_t](https://hackmd.io/@s1041562/2020q3-lab0?view#queue_t)
* [q_new](https://hackmd.io/@s1041562/2020q3-lab0?view#q_new)
* [q_free](https://hackmd.io/@s1041562/2020q3-lab0?view#q_free)
* [q_insert_head](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?view#q_insert_head)
* [q_insert_tail](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?view#q_insert_tail)
* [q_remove_head](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?view#q_remove_head)
* [q_size](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?view#q_size)
* [q_reverse](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?view#q_reverse)
* [q_sort](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?view#q_sort)
* [測試](https://hackmd.io/JXwu90ReQ0eb_WnhCpbyTQ?both#%E9%99%A4%E9%8C%AF%E9%81%8E%E7%A8%8B66100)
## Environment
```
$ uname -r
Linux oslab 5.4.0-42-generic #46-Ubuntu SMP Fri Jul 10 00:24:02 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 開發紀錄
### queue_t
* 因為要在 O(1) 時間內執行完成，所以除原本新增的 size 以外，需要新增一個 list_ele_t *tail 來讓 q_insert_tail 得以在 O(1) 時間內完成
```C=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### q_new
* 宣告一個新的空佇列，如果宣告失敗的話則返回 NULL ，成功的話則初始化
```C=
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
* 要注意釋放記憶體的時候要記得 value 也必須釋放
```C=
void q_free(queue_t *q)
{
if (!q) {
return;
}
while (q->head) {
list_ele_t *temp = q->head;
q->head = q->head->next;
free(temp->value);
free(temp);
}
free(q);
}
```
### q_insert_head
* 因為作業要求避免使用 strcpy ，參考 CERN 建議使用 strncpy ，搭配 memset 來解決 strncpy 不會自動填入 '\0' 的問題
* 要注意假如 malloc 分配失敗的情況
* 考慮第一次插入 newh 時要另外設定 q->tail
* 要注意 memory leak (line 12)
```C=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!q || !newh) {
return false;
}
int length = strlen(s) + 1;
newh->value = malloc(length * sizeof(char));
if (!newh->value) {
/*Avoid memory leak.*/
free(newh);
return false;
}
memset(newh->value, '\0', length);
strncpy(newh->value, s, strlen(s));
newh->next = q->head;
q->head = newh;
/* Check newh is the only element*/
if (!q->tail) {
q->tail = newh;
}
return true;
}
```
### q_insert_tail
* 作法跟 q_insert_head 類似，只是要記得把 newh->next 指向 NULL
```C=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if(!q || !newh) {
return false;
}
int length = strlen(s) + 1;
newh->value =malloc(length * sizeof(char));
if(!newh->value) {
free(newh);
return false;
}
memset(newh->value, '\0', length);
strncpy(newh->value, s, strlen(s));
q->tail->next = newh;
q->tail = newh;
if(!q->head) {
q->head = newh;
}
newh->next = NULL;
q->size++;
return true;
}
```
### q_remove_head
```C=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
list_ele_t *temp;
temp = q->head;
if (sp) {
memset(sp, '\0', bufsize);
strncpy(sp, temp->value, bufsize - 1);
}
q->head = q->head->next;
free(temp->value);
free(temp);
return true;
}
```
### q_size
* 這裡只要增加邊界的判斷
```C=
int q_size(queue_t *q)
{
if (!q) {
return 0;
}
return q->size;
}
```
### q_reverse
* 先檢查元素數量
* 使用 temp 來幫助反轉
* 最後 q->tail->next 要記得指向NULL
```C=
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1) {
return;
}
list_ele_t *temp;
q->tail->next = q->head;
temp = q->head;
q->head = q->head->next;
while (q->head != q->tail) {
/* 拿住接下來要接上去的元素*/
q->tail->next->next = q->head;
/* head 往下個元素移動避免下一個節點丟掉*/
q->head = q->head->next;
/* 把元素接上去*/
q->tail->next->next->next = temp;
/* 把 temp 移到佇列的最前面*/
temp = q->tail->next->next;
}
q->tail = q->tail->next;
q->head->next = temp;
q->tail->next = NULL;
return;
}
```
### q_sort
* 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的merge sort 方法，修改成可以排序字串
q_sort 主要檢查邊界以及要記得把 tail 移動到最後面
```C=
void q_sort(queue_t *q)
{
if (!q || q->size <= 1) {
return;
}
q->head = merge_sort_list(q->head);
while(q->tail->next){
q->tail = q->tail->next;
}
return;
}
```
merge_sort_list 用來分割 list
```C=
list_ele_t *merge_sort_list(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *fast = head->next;
list_ele_t *slow = head;
/* spilt list */
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = merge_sort_list(head);
list_ele_t *l2 = merge_sort_list(fast);
return merge(l1, l2);
}
```
merge 判斷大小
```C=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t q;
list_ele_t *temp = &q;
size_t len = (strlen(l1->value) < strlen(l2->value)) ? strlen(l1->value) : strlen(l2->value);
while (l1 && l2) {
if (strncmp(l1->value, l2->value, len) < 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
if (l1) {
temp->next = l1;
}
if (l2) {
temp->next = l2;
}
return q.next;
}
```
### 測試
先來看看分數
```
$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
ERROR: Computed queue size as 6, but correct value is 2
--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
ERROR: Computed queue size as 6, but correct value is 5
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-05-ops 0/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-06-string 0/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-07-robust 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 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
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
--- trace-16-perf 0/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Testing insert_tail...(0/10)
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-17-complexity 0/5
--- TOTAL 66/100
```
只有66分
* 先看 trace-04-ops 錯誤
ERROR: Computed queue size as 6, but correct value is 2
看起來是 size 算錯，回頭查看發現 q_remove_sort 移除後沒有做 q->size--
修正之後
trace-01-ops 6/6
trace-02-ops 6/6
trace-03-ops 6/6
trace-04-ops 6/6
trace-05-ops 5/5
trace-06-string 6/6
trace-07-robust <font color="#f00">0/6</font>
trace-08-robust 6/6
trace-09-robust 6/6
trace-10-malloc 6/6
trace-11-malloc 6/6
trace-12-malloc 6/6
trace-13-perf 6/6
trace-14-perf 6/6
trace-15-perf 6/6
trace-16-perf <font color="#f00">0/6</font>
trace-17-complexity <font color="#f00">0/5</font>
TOTAL <font color="#f00">83/100</font>
剩下三個測試沒有過了
* 觀察錯誤訊息
```=
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-07-robust 0/6
```
發現下方 code
```=
if (!q || !newh) {
return false;
}
```
沒有在 return 以前把宣告的 newh 釋放，於是改成
```=
if (!q || !newh) {
free(newh);
return false;
}
```
再次測試
```=
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 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
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
--- trace-16-perf 0/6
```
```=
==411606== 1 bytes in 1 blocks are still reachable in loss record 1 of 258
==411606== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==411606== by 0x490350E: strdup (strdup.c:42)
==411606== by 0x124A98: xstrdup (in /usr/bin/make)
==411606== by 0x1308DD: define_variable_in_set (in /usr/bin/make)
==411606== by 0x111B70: main (in /usr/bin/make)
==411606==
==411606== 1 bytes in 1 blocks are still reachable in loss record 2 of 258
==411606== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==411606== by 0x490350E: strdup (strdup.c:42)
==411606== by 0x124A98: xstrdup (in /usr/bin/make)
==411606== by 0x1308DD: define_variable_in_set (in /usr/bin/make)
==411606== by 0x111BA4: main (in /usr/bin/make)
```
雖然 qtest 給出的錯誤是 Not sorted in ascending order 但是 Valgrind 卻偵測到
still reachable
由於不清楚 trace-16-perf 的錯誤與 Valgrind 的錯誤有沒有關聯
因此手動分別對第 16 17 測資做測試
發現 Valgrind 在第 17 測資給出下面錯誤
```=
==3584== Invalid write of size 8
==3584== at 0x10DF7A: q_insert_tail (queue.c:97)
==3584== by 0x10E473: measure (constant.c:69)
==3584== by 0x10E678: doit (fixture.c:136)
==3584== by 0x10E8D0: is_insert_tail_const (fixture.c:168)
==3584== by 0x10B592: do_insert_tail (qtest.c:259)
==3584== by 0x10CB87: interpret_cmda (console.c:220)
==3584== by 0x10D10F: interpret_cmd (console.c:243)
==3584== by 0x10D808: cmd_select (console.c:607)
==3584== by 0x10D923: run_console (console.c:628)
==3584== by 0x10BFE1: main (qtest.c:772)
==3584== Address 0x8 is not stack'd, malloc'd or (recently) free'd
==3584==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
==3584== 3 bytes in 1 blocks are still reachable in loss record 1 of 36
==3584== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3584== by 0x10C780: strsave_or_fail (report.c:230)
==3584== by 0x10D0D1: parse_args (console.c:190)
==3584== by 0x10D0D1: interpret_cmd (console.c:242)
==3584== by 0x10D808: cmd_select (console.c:607)
==3584== by 0x10D923: run_console (console.c:628)
==3584== by 0x10BFE1: main (qtest.c:772)
```
回頭看 q_insert_tail 發現在執行 q->tail->next = newh 時，沒有先確定 q->tail 是否存在導致程式有可能崩潰，把修改成下面在測試
```=C=
if (!q->tail) {
q->tail = q->head = newh;
} else {
q->tail->next = newh;
q->tail = newh;
}
newh->next = NULL;
```
```=
+++ 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 94/100
```
這樣就剩下第 16 測資了
Sign in with Wallet
Connect another wallet