# 2021q1 Homework1 (lab0)
contributed by < [bobhsiao0306](https://github.com/bobhsiao0306) >
> [GitHub repository](https://github.com/bobhsiao0306/lab0-c)
###### tags: `linux2021` `lab0`
:::danger
注意共筆書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::
### Reviewed by `robertlin0401`
1. 觀察其他同學的開發紀錄可發現大部分的人仍是使用遞迴的 merge sort 且沒有遭遇 stack overflow，因此以下探討此實作所產生的 stack overflow 問題所在
* 首先，我們將 merge sort 的遞迴呼叫視覺化（假設資料總數為 $n$，且 $n$ 為 2 的冪次）
```graphviz
digraph {
node1 [label="n"];
node2 [label="n / 2"];
node_invis1 [label=""; style=invis];
node3 [label="n / 2"];
node4 [shape=none; label="．\n．\n．"];
node6 [shape=none; label="． ． ． ． ． ．"];
node7 [shape=none; label="．\n．\n．"];
node8 [label="2"];
node09 [style=invis];
node12 [shape=none; label="． ． ． ． ． ．"];
node14 [style=invis];
node15 [label="2"];
node16 [label="1"];
node17 [label="1"];
node24 [shape=none; label="． ． ． ． ． ．"];
node30 [label="1"];
node31 [label="1"];
level1 [shape=none; label="1"];
level2 [shape=none; label="2"];
level_before_end [shape=none; label="logn"];
level_end [shape=none; label="logn+1"];
node1 -> node2;
node1 -> node_invis1 [style=invis];
node1 -> node3;
node2 -> node4;
node2 -> node6 [style=invis];
node3 -> node6 [style=invis];
node3 -> node7;
node4 -> node8;
node4 -> node09 [style=invis];
node6 -> node12 [style=invis];
node7 -> node14 [style=invis];
node7 -> node15;
node8 -> node16;
node8 -> node17;
node12 -> node24 [style=invis];
node15 -> node30;
node15 -> node31;
node1 -> level1 [style=invis];
node3 -> level2 [style=invis];
node15 -> level_before_end [style=invis];
node31 -> level_end [style=invis];
{ rank=same; node1; level1; }
{ rank=same; node3; level2; }
{ rank=same; node15; level_before_end; }
{ rank=same; node31; level_end; }
}
```
* 圖中每個 node 代表一次 `mergesort` 的執行，node 中的數字表示該次呼叫所排序的資料量，每層最右邊的數字表示當前的函式呼叫深度，故 `mergesort` 本身的最大呼叫深度為 $logn+1$
* 接著觀察 `mergesort` 中呼叫到的 `sortedMerge` 函式，它也是一個遞迴函式，會在 `mergesort` 中滿足當前資料量 $k>1$ 時被呼叫，而其每次呼叫之深度即為 $k$，$k=\dfrac{n}{2^{i-1}}$，$1\leq i\leq logn+1$
```c
list_ele_t* sortedMerge(list_ele_t* a, list_ele_t* b)
{
// base cases
if (a == NULL)
return b;
else if (b == NULL)
return a;
list_ele_t* result = NULL;
// pick either `a` or `b`, and recur
if (strcmp(a->value, b->value) <= 0) {
result = a;
result->next = sortedMerge(a->next, b);
} else {
result = b;
result->next = sortedMerge(a, b->next);
}
return result;
}
```
* 綜上分析，此實作的最大函式呼叫深度為 $\displaystyle\max_{1\leq i\leq logn}\{i+k\ ,\ \ logn+1\}=1+n$，而最小呼叫深度則為 $logn+1$，即為 `mergesort` 本身之最大呼叫深度。故使用遞迴函式 `sortedMerge` 會使函式呼叫最大深度多出 $n-logn$，且在 $n$ 愈大時所多花費的 stack 空間愈多，換句話說，遞迴函式 `sortedMerge` 為 stack overflow 發生之主因
* 以下針對 `sortedMerge` 函式，改成非遞迴之實作，經測試可發現 stack overflow 問題已解決
```c
list_ele_t *sortedMerge(list_ele_t *a, list_ele_t *b)
{
list_ele_t *result = NULL, *tail = NULL;
while (a != NULL && b != NULL) {
if (strcmp(a->value, b->value) <= 0) {
if (result == NULL)
result = a;
else
tail->next = a;
tail = a;
a = a->next;
} else {
if (result == NULL)
result = b;
else
tail->next = b;
tail = b;
b = b->next;
}
tail->next = NULL;
}
tail->next = (a != NULL) ? a : b;
return result;
}
```
2. [commit 8082cb](https://github.com/bobhsiao0306/lab0-c/commit/8082cb36f918e4a6db301e4f0d51e56d2b939fa3) 將遞迴的 merge sort 改為非遞迴，則原本的遞迴程式碼片段可以直接刪除以保持程式碼的整潔。若是希望留下舊版本的紀錄，可以使用 `git tag` 在舊版本的 commit 上新增標籤，方便日後回頭尋找
3. 在函式 `frontBackSplit` 中，存在一段不需要的條件判斷：
```c
void frontBackSplit (list_ele_t *source, ...)
{
// if the length is less than 2, handle it separately
if (source == NULL || source->next == NULL) {
/* some operations */
}
...
}
```
* 此函式會在 `mergesort` 函式中被呼叫，而 `mergesort` 中已存在相同意義的判斷式，若此條件成立，則 `mergesort` 會直接回傳而不會呼叫到 `frontBackSplit`，故 `frontBackSplit` 中的條件永不成立。以下截自 `mergesort` 函式：
```c
// base case — length 0 or 1
if (*head == NULL || (*head)->next == NULL) {
return;
}
// split `head` into `a` and `b` sublists
list_ele_t *a, *b;
frontBackSplit(*head, &a, &b);
```
---
## 作業要求
在 ``queue.[c/h]`` 中完成以下實作
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* ==`q_sort`==: 以==遞增順序==來排序鏈結串列的元素
## 作業實做
### Queue structure
```cpp=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
在 Queue structure 中加入 ==tail== 以及 ==size== 使得 `q_insert_tail` 和 `q_size` 從原本 $O(n)$ 時間複雜度降低為 $O(1)$ 時間複雜度
### q_new
```cpp=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL) /*malloc return NULL*/
{
return NULL;
} else /*malloc succeed*/
{
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
### q_free
```cpp=
void q_free(queue_t *q)
{
if (q == NULL)
return;
list_ele_t *p = q->head;
while (p) {
list_ele_t *tmp = p;
p = p->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
### q_insert_head
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (q == NULL)
return false;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newh->value == NULL) {
free(newh);
return false;
} else {
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
q->head = newh;
q->size++;
if (q->size == 1)
q->tail = q->head;
return true;
}
}
```
### q_insert_tail
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
if (q == NULL)
return false;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newh->value == NULL) {
free(newh);
return false;
} else {
strncpy(newh->value, s, strlen(s) + 1);
newh->next = NULL;
if(q->tail != NULL)
q->tail->next = newh;
q->tail = newh;
q->size++;
if (q->size == 1)
q->head = q->tail;
return true;
}
}
```
### q_remove_head
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL || sp == NULL)
return false;
list_ele_t *tmp = q->head;
q->head = q->head->next;
if (strlen(tmp->value) >= bufsize){
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else{
strncpy(sp, tmp->value, strlen(tmp->value));
sp[strlen(tmp->value)] = '\0';
}
free(tmp->value);
free(tmp);
q->size--;
if(q->size == 0)
q->tail = NULL;
return true;
}
```
### q_size
```cpp=
int q_size(queue_t *q)
{
if(q == NULL)
return 0;
return q->size;
}
```
因為 `q_size()` 之執行時間與 input 之 size 沒有關係，所以 `q_size()` 之時間複雜度為$O(1)$
### q_reverse
```cpp=
void q_reverse(queue_t *q)
{
if (q == NULL)
return;
q->tail = q->head;
list_ele_t *x = q->head;
list_ele_t *y = NULL;
list_ele_t *z = NULL;
while (x) {
z = y;
y = x;
x = x->next;
y->next = z;
}
q->head = y;
}
```
### q_sort
>Reference:[Merge sort algorithm for a singly linked list](https://www.techiedelight.com/merge-sort-singly-linked-list/)
```cpp=
void q_sort(queue_t *q)
{
if (q == NULL || q->size == 0 || q->size == 1)
return;
mergesort(&q->head);
list_ele_t *buf = q->head;
while (buf)
{
q->tail = buf;
buf = buf->next;
}
}
void mergesort(list_ele_t** head)
{
// base case — length 0 or 1
if (*head == NULL || (*head)->next == NULL) {
return;
}
list_ele_t* a;
list_ele_t* b;
// split `head` into `a` and `b` sublists
frontBackSplit(*head, &a, &b);
// recursively sort the sublists
mergesort(&a);
mergesort(&b);
// answer = merge the two sorted lists
*head = sortedMerge(a, b);
}
void frontBackSplit (list_ele_t *source,
list_ele_t **frontRef,
list_ele_t **backRef)
{
// if the length is less than 2, handle it separately
if (source == NULL || source->next == NULL)
{
*frontRef = source;
*backRef = NULL;
return;
}
list_ele_t* slow = source;
list_ele_t* fast = source->next;
// advance `fast` two nodes, and advance `slow` one node
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
// `slow` is before the midpoint in the list, so split it in two
// at that point.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
list_ele_t* sortedMerge(list_ele_t* a, list_ele_t* b)
{
// base cases
if (a == NULL)
return b;
else if (b == NULL)
return a;
list_ele_t* result = NULL;
// pick either `a` or `b`, and recur
if (strcmp(a->value, b->value) <= 0)
{
result = a;
result->next = sortedMerge(a->next, b);
}
else {
result = b;
result->next = sortedMerge(a, b->next);
}
return result;
}
```
## 問題與解決方法
### trace-06-string
在執行 `trace-06-string.cmd` 時因為將 string 的最大長度改小之後遇到 error
> 在 [qtest.c](https://github.com/bobhsiao0306/lab0-c/blob/master/qtest.c) 中發現 length 的值即為傳入 `q_remove_head` 的 bufsize 參數
> 所以需要先比較 queue head 的字串長度與 bufsize 的大小來決定 `strncpy` 函式第三個參數要放什麼
### trace-15-perf
執行此測資時會發生 segmentation fault
再進一步利用 valgrind 檢測記憶體的使用狀況才發現是 stack overflow
> 因為用 recursive 的方式實做 merge sort，空間複雜度為 $O(n)$，導致此 process stack overflow。將 merge sort 演算法用迴圈的分式改寫即可解決此問題。
Sign in with Wallet
Connect another wallet