# 2020q1 Homework1 (lab0)
contributed by < `nickyanggg` >
###### tags: `linux2020`
## 作業說明
- [lab0](https://hackmd.io/@sysprog/linux2020-lab0)
- [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 作業要求
依照作業說明完成 queue.c & queue.h 二個檔案，主要功能如下：
- `q_new` 建立新的 empty queue
- `q_free` 釋放 queue 所用到的空間
- `q_insert_head` 插入新的 element 至 queue 的開頭
- `q_insert_tail` 插入新的 element 至 queue 的尾端
- `q_remove_head` 刪除 queue 的開頭的 element
- `q_size` 計算 queue 中的 element 數量
- `q_reverse` 將 queue 中的 element 依反向順序排列
- `q_sort` 將queue 中的 element 依遞增順序排列
## 實驗環境
```shell
$ uname -a
Linux ginoah-ubuntu-18 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.4.0-1ubuntu1~18.04.1) 7.4.0
```
## 實作流程
### **queue.h**
由於 `q_insert_tail`、`q_size` 皆要求複雜度 $O(1)$，因此將 `queue_t` 修改如下：
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
如此，當實作 `q_insert_tail`、`q_size` 時，可以不用重頭 traverse 一遍，前者可以直接利用 `tail` 去做串接，而後者則是可以直接回傳 `size` 的值。
### **queue.c**
- **`q_new`**
- 確認 malloc 是否成功。
```c=
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`**
- 確認 queue 是否存在。
- 依序釋放各個 element 所用到的空間。
- 最後在釋放 empty queue 所用到的空間。
```c=
void q_free(queue_t *q)
{
/* Free queue structure */
if (!q)
return;
list_ele_t *curr = q->head;
list_ele_t *temp;
for (int i = 0; i < q->size; ++i) {
free(curr->value);
temp = curr->next;
free(curr);
curr = temp;
}
free(q);
}
```
- **`q_insert_head`**
- 確認 queue 是否存在。
- 確認 malloc 是否成功。
- 若在 malloc 空間給 `value` 失敗時，要回頭去 free 前面 malloc 給新進 element 的空間。
- 維護 `head`、`tail`、`size`。
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
if (!q->head)
q->tail = newh;
q->head = newh;
q->size++;
return true;
}
```
- **`q_insert_tail`**
- 同 `q_insert_head` 的注意事項。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc(strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (!q->head)
q->head = newt;
else
q->tail->next = newt;
q->tail = newt;
q->size++;
return true;
}
```
- **`q_remove_head`**
- 確認 queue 是否存在，以及 `size` 是否為 0。
- 若 `sp` 存在，copy 欲刪的 element 的 value 進去，記得在最後面補上結束字元 `'\0'`，詳情請參考 [strncpy](https://linux.die.net/man/3/strncpy)。
- 釋放所用到的空間，並且維護 `head`、`tail`、`size`。
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->size)
return false;
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
free(q->head->value);
list_ele_t *head = q->head;
q->head = q->head->next;
free(head);
if (!q->head)
q->tail = NULL;
q->size--;
return true;
}
```
- **`q_size`**
- 確認 queue 是否存在。
```c=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
- **`q_reverse`**
- 確認 queue 是否存在以及 `size <= 1` 的狀況。
- 利用 `curr`、`prev`、`temp` 來把 queue 中所有的 elements 逆向接起來。
- 將 `head`、`tail` 的值調換。
```c=
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1)
return;
list_ele_t *curr, *prev, *temp;
curr = q->head;
prev = NULL;
for (int i = 0; i < q->size; ++i) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
temp = q->head;
q->head = q->tail;
q->tail = temp;
}
```
- **`q_sort`**
- 確認 queue 是否存在以及 `size <= 1` 的狀況。
- 由於複雜度得為 $O(nlogn)$ ，這邊是直接 call 另外實作的 `merge_sort`。
- 維護 `tail` 的值。
```c=
void q_sort(queue_t *q)
{
if (!q || q->size <= 1)
return;
q->head = merge_sort(q->head);
list_ele_t *curr = q->head;
for (int i = 0; i < q->size; ++i) {
q->tail = curr;
curr = curr->next;
}
}
```
- **`merge_sort`**
- 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的實作方式。
- `merge_sort`
- 由於假如每次在 divide 的時候 `left` 都 assign 成 `head`，而 `right` 則是 `head->next` 的話，也就是左半段的 queue 只有一個 element，而右半段的 queue 則是剩下的所有 element，這樣子的複雜度仍為 $O(n^2)$，因此下面會介紹將 `left`、`right` 平均分配的方式。
- `left`、`right` 前者每次跳一個 element，後者每次跳二個 element，當 right 到 queue 的尾端時，`left` 所指向的 element 剛好位於 queue 的中間，接著再將 `right` assign 成 `left->next` ( 也就是右邊半段的頭 )，再把 `left->next` assign 成 `NULL` ( 也就是斷開成二個 queue )，最後再把 `left` assign 成 `head` 即可，此時 `left`、`right` 各代表著左半段的 `head` 以及右半段的 `head`。
- 最後再利用遞迴去一直 divide，最後再 call `merge` 來把二段已經 sort 好的 queue 給 merge 起來。
```c=
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *left = head;
list_ele_t *right = head->next;
while (right && right->next) {
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
left = merge_sort(head);
right = merge_sort(right);
return merge(left, right);
}
```
- **`merge`**
- 由於測資所塞進的 element 過多，因此在呼叫 `merge` 的時候，不可利用遞迴的方式，不然會發生 `stack overflow` 導致 `segmentation fault`。
```c=
// 非遞迴的版本
list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
list_ele_t *head, *curr;
if (strcmp(left->value, right->value) <= 0) {
head = left;
left = left->next;
} else {
head = right;
right = right->next;
}
curr = head;
while (left && right) {
if (strcmp(left->value, right->value) <= 0) {
curr->next = left;
left = left->next;
} else {
curr->next = right;
right = right->next;
}
curr = curr->next;
}
if (left)
curr->next = left;
if (right)
curr->next = right;
return head;
}
```
```c=
// 遞迴的版本
list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
if (!left)
return right;
if (!right)
return left;
if (strcmp(left->value, right->value) < 0) {
left->next = merge(left->next, right);
return left;
}
else {
right->next = merge(left, right->next);
return right;
}
}
```
## 測試結果
利用 `make test` 觀看結果
```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
```
Sign in with Wallet
Connect another wallet