# 2020q1 Homework1 (lab0)
contributed by < `johnnycck` >
###### tags: `linux2020`
## 作業要求
1. 使用 git 版本控制，並熟悉 git 使用語法及規則
2. 修改 queue.c && queue.h，以 Linked-list 實做 queue，並完成以下功能
* `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`:以==遞增順序==來排序鏈結串列的元素
* `q_insert_tail` 和 `q_size` 需要將原本 $O(n)$ 時間複雜度的實作改寫為 $O(1)$ 時間複雜度，亦即無論佇列空間為何，該操作僅需要固定數量的步驟
3. 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
## 參考資料
* [2020 年系統軟體課程](https://www.facebook.com/groups/system.software2020/)
* [Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)
* [作業解說錄影](https://youtu.be/lAurEgzZ6YY?t=9912)
* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/)
* [為你自己學 Git](https://gitbook.tw/)
* [natural sort](https://github.com/sourcefrog/natsort)
## 實做紀錄
### Define queue_t
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
* 將queue的型態確定，因 `q_size` 需要 $O(1)$ ，所以在型態中配置 `int size` 紀錄 queue 元素個數
### q_new
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL && (sizeof(queue_t) > 0)) {
return NULL;
} else { /* What if malloc returned NULL? */
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
}
```
* 若是 `malloc` 失敗，回傳 `NULL`
* 若是 `malloc` 成功，初始化 `queue`
### q_free
```cpp
void q_free(queue_t *q)
{
if (q == NULL)
return;
else if (q->size == 1) {
q->size = 0;
free(q->head->value);
free(q->head);
free(q);
} else if (q->size == 0) {
free(q);
} else {
while (q->head != NULL) {
q->tail = q->head;
q->head = q->head->next;
free(q->tail->value);
free(q->tail);
}
q->size = 0;
free(q);
}
}
```
:::warning
考慮以下變更:
```diff
@@ -1,6 +1,5 @@
- while (q->head != NULL) {
+ for (;q->hea; q->head = q->head->next) {
q->tail = q->head;
- q->head = q->head->next;
free(q->tail->value);
free(q->tail);
- }
+ }
```
要點:
1. 用 `for` 迴圈改寫，讓程式碼更聚焦在 `q->tail` 的操作;
2. 日後可用 foreach 巨集改寫
:notes: jserv
:::
* 以 `queue` 中元素個數來做判定，分為三種方式解決
1. `queue` 沒有元素，直接 free(q)
2. `queue` 有一個元素，free `q->head` 的`value`及 `queue` 本身
3. `queue` 有多個元素，以 `while` 迴圈依次從 `queue->head` 開始 free，為了不浪費空間，將 `q->tail`當作指向 `q->head` 的指標
* 每一種方法都會將 `q->size` 歸零
### q_insert_head
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* Solve: What should you do if the q is NULL? */
if (q == NULL) {
return false;
} else {
q->size++;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
char *input;
size_t string_size;
string_size = strlen(s);
input = malloc(string_size + 1);
if (input == NULL) {
free(newh);
return false;
}
int i;
for (i = 0; s[i] != '\0'; i++) {
input[i] = s[i];
}
input[i] = '\0';
newh->value = input;
newh->next = q->head;
if (q->head == NULL && q->tail == NULL)
q->head = q->tail = newh;
else
q->head = newh;
return true;
}
}
```
1. 使用 `malloc` allocate一塊空間給 `q->value` ，為了避免使用**較不安全**的 `strcpy` ，複製 `string` 過程使用 `for` 迴圈完成
2. 若 `queue` 原先沒有元素，將 `q->head` && `q->tail` 都指向新增的元素：若 `queue` 原先已經有元素，只須將 `q->head` 指向新增的元素
### q_insert_tail
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
if (q == NULL) {
return false;
} else {
q->size++;
newt = malloc(sizeof(list_ele_t));
if (newt == NULL)
return false;
char *input;
size_t string_size;
string_size = strlen(s);
input = malloc(string_size + 1);
if (input == NULL) {
free(newt);
return false;
}
int i;
for (i = 0; s[i] != '\0'; i++) {
input[i] = s[i];
}
input[i] = '\0';
newt->value = input;
newt->next = NULL;
if (q->head == NULL && q->tail == NULL)
q->head = q->tail = newt;
else {
q->tail->next = newt;
q->tail = newt;
}
return true;
}
}
```
1. 操作基本上跟 `q_insert_head` 一樣，若 `queue` 原先沒有元素，將 `q->head` && `q->tail` 都指向新增的元素：若 `queue` 原先已經有元素，只須將 `q->tail` 指向新增的元素
2. 作業要求 `q_insert_tail` 時間複雜度為 $O(1)$，因有紀錄 `q->tail`，可以輕易做到
### q_remove_head
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if(q == NULL)
return false;
else if (q->size == 0 || sp == NULL) {
return false;
} else {
q->size--;
size_t i;
char *tmp;
list_ele_t *link;
tmp = q->head->value;
for (i = 0; tmp[i] != '\0'; i++) {
sp[i] = tmp[i];
if (i == bufsize - 2) {
i++;
break;
}
}
sp[i] = '\0';
link = q->head;
q->head = q->head->next;
free(link->value);
free(link);
return true;
}
}
```
1. 因為要將 remove 的 `q->value` 移至 `*sp`且要注意不能超過 `bufsize`，因此在複製階段以 `for` 迴圈控制，若是超過 `bufsize` 會立刻離開迴圈
2. 在 `trace-07-perf` 中有對空的 `queue` 做 `q_remove_head` ，原先程式碼為：
```cpp
if (q == NULL || q->size == 0 || sp == NULL)
return false;
```
會造成 `q->size` 是NULL pointer狀態下被判斷，會造成 `segmentation fault`，因此修改為：
```cpp
if (q == NULL)
return false;
else if (q->size == 0 || sp == NULL)
return false;
```
若是 `queue` 尚未被初始化就執行 `q_remove_head`，會直接 `return`，避免錯誤
### q_size
```cpp=
int q_size(queue_t *q)
{
if (q == NULL || q->size == 0)
return false;
else
return q->size;
}
```
:::warning
考慮以下變更:
```cpp=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
簡潔又清晰，後續程式碼可比照此手法改寫。
:notes: jserv
:::
> 謝謝老師的建議，已經做修改[name=johnnykao530]
* 因為 `queue`型態就有紀錄元素個數 `q->size`，因此只須 `return q->size`，即可達成時間複雜度 $O(1)$ 的條件
### q_reverse
```cpp
{
if (q != NULL && q->size > 0) {
list_ele_t *prev = NULL, *curr, *next = NULL, *tmp;
tmp = curr = q->head;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
q->tail = tmp;
q->head = prev;
}
}
```
:::warning
1. 可將 `q != NULL` 改寫為 `q`
2. 縮減 `list_ele_t *next` 的 scope，可挪到 `while` 迴圈內
:notes: jserv
:::
> 謝謝老師的建議，已將 `q_reverse()` 的 `list_ele_t *next` 的 scope挪到 `while` 迴圈內，並將使用的 tmp nodes 從原先的4個降至2個[name=johnnykao530]
#### Revised 版本
```cpp
void q_reverse(queue_t *q)
{
if (q && q->size > 0) {
list_ele_t *curr, *next;
q->tail = curr = q->head;
while (curr != NULL) {
next = curr->next;
curr->next = q->head;
q->head = curr;
curr = next;
}
q->tail->next = NULL;
}
}
```
* 使用三個指標依序指向 `queue` 元素的前、中、後，從 `q->head` 開始逐漸更改 `next` 指向的位置，最後完成 `q_reverse` 操作
* 一開始每次操作 `q_reverse` 都用迴圈來回跑 `queue`的元素，造成在 `perf` 測試到 `q_reverse` 時都會發生 `TLE`，上網查資料後才用了此方法(太久沒撰寫 linked list 程式，都還給大學老師了...)
### q_sort
分為四個 `function` 完成：
1. q_sort()
```cpp
void q_sort(queue_t *q)
{
if (q == NULL || q->size <= 1)
return;
else {
q->head = mergeSortList(q->head);
list_ele_t *tmp = q->head;
while (tmp->next)
tmp = tmp->next;
q->tail = tmp;
}
}
```
:::warning
考慮以下變更:
```diff
@@ -2,11 +2,10 @@
{
if (q == NULL || q->size <= 1)
return;
- else {
- q->head = mergeSortList(q->head);
- list_ele_t *tmp = q->head;
- while (tmp->next)
- tmp = tmp->next;
- q->tail = tmp;
- }
+
+ q->head = mergeSortList(q->head);
+ list_ele_t *tmp;
+ for (tmp = q->head; tmp->next; tmp = tmp->next)
+ ; /* iterate */
+ q->tail = tmp;
}
```
要點:
1. 移除非必要的 `else`，降低程式縮排的深度 (depth);
2. 將 `while` 改為 `for`，之後引入 foreach 巨集時，更易銜接;
:notes: jserv
:::
> 謝謝老師，已做修正[name=johnnykao530]
#### Revised 版本
```cpp=
void q_sort(queue_t *q)
{
if (q == NULL || q->size <= 1)
return;
q->head = mergeSortList(q->head);
list_ele_t *tmp = q->head;
for(tmp = q->head; tmp->next; tmp=tmp->next)
;
q->tail = tmp;
}
```
* `q_sort` 的主函式，負責將 `q->head` 傳送給 `mergeSortList`，並回傳得排序好的 `q->head`，並使用 `while` 迴圈重新得出 `q->tail`
2. mergeSortList()
```cpp
list_ele_t *mergeSortList(list_ele_t *head)
{
// merge sort
if (!head || !head->next) {
return head;
}
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
head = mergeSortList(head);
fast = mergeSortList(fast);
return merge(head, fast);
}
```
* 參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)，完成時間複雜度為 $O(nlog{n})$ 的 `merge sort`
:::warning
`mergeSortList` 函式僅限於同一個 C 原始程式碼中使用，於是可在宣告加上 `static`，表明其 visibility 不公開 (exposed)，有助於編譯器施加最佳化。
:notes: jserv
:::
3. merge()
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
// merge with pseudo node
list_ele_t *temp = NULL;
list_ele_t **p = &temp;
while (l1 && l2) {
if (natur_cmp(l1->value, l2->value) <= 0) {
*p = l1;
l1 = l1->next;
} else {
*p = l2;
l2 = l2->next;
}
p = &(*p)->next;
}
if (l1)
*p = l1;
if (l2)
*p = l2;
return temp;
}
```
* 若是使用 `recursive` 方法實做 `merge sort` ，在過大資料量時會發生 stack overflow 的狀況，因此在此使用 `iteration` 的方法實做
:::warning
需要解釋 stack overflow 的起因，以及到哪一個深度時候遇到，這部分的分析很重要！
:notes: jserv
:::
* 在 `compare` 時使用自製的 `natural sort`完成
4. natur_cmp()
```cpp
int natur_cmp(char *a, char *b)
{
if (strcasecmp(a, b) == 0)
return 0;
else {
int i = 0, dig_numa = 0, dig_numb = 0;
while (1) {
while (a[i] == b[i] && !isdigit(a[i]) && !isdigit(b[i]))
i++;
while (isdigit(a[i])) {
i++;
dig_numa++;
}
i -= dig_numa;
while (isdigit(b[i])) {
i++;
dig_numb++;
}
i -= dig_numb;
if (dig_numa > dig_numb)
return 1;
else if (dig_numb > dig_numa)
return -1;
else if (dig_numa == dig_numb) {
if (dig_numa == 0) {
return strcasecmp(a, b);
} else {
int j = dig_numa + i;
for (; i < j; i++) {
if (a[i] > b[i])
return 1;
else if (a[i] < b[i])
return -1;
else
continue;
}
if (strlen(a) > dig_numa) {
dig_numa = 0;
dig_numb = 0;
i++;
} else
return 0;
}
}
}
}
return false;
}
```
:::warning
上方程式碼過冗長，請思考縮減的方法
:notes: jserv
:::
* 原先使用 `strcasecmp()`來判斷 `q->value` 的大小（看到`qtest.c` 中的 `do_sort()`直接使用此函數），但之後發現要以 [natural sort](https://github.com/sourcefrog/natsort)方式完成，因此進行修改
* 自行編寫 `natural sort` 的判斷函式，並沒有使用 `library` 之 `natural sort`
* `trace-15-perf` && `trace-16-perf` 一直遇到 `TLE` ，在 trace code 後發現測試的程式碼大量 `insert` 相同的 `value` ，若是每個相同的 `value` 都要跑大量的 `loop` 以及 `branch` ，很容易造成 `TLE`的狀況，因此在執行`natur_cmp`時，優先判斷`value_a` && `value_b`的大小，若是相同直接回傳 *0* ，更改後也成功通過 `perf test`
* 作業要求要更改 `Simulation` 的判斷式，因此修改`qtest.c` 中的 `do_sort()`，將原先使用的 `strcasecmp()` 更改為 `natur_cmp()`
## Massif 的運用
## Dude, is my code constant time?
## select 系統呼叫
Sign in with Wallet
Connect another wallet