# 2020q1 Homework1 (lab0)
contributed by < `Jadezzz` >
[作業要求](https://hackmd.io/@sysprog/linux2020-lab0)
[作業區](https://hackmd.io/@sysprog/linux2020-homework1)
## queue.h 實作
### 增加 queue_t 欄位
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head, *tail; /* Head and tail of the linked list of elements */
unsigned long size; /* Size of the linked list */
} queue_t;
```
根據作業要求， ```q_insert_tail``` 以及 ```q_size``` 函數需要達到 $O(1)$ 的時間複雜度，所以對 ```queue_t``` 的欄位做以下修改：
1. 新增 ```tail``` 指標記錄 queue 最末端的元素
2. 新增 ```size``` 記錄 queue 當前的大小（因爲 size 不爲負數，使用 ```unsigned long``` 能記錄最多 $2^{32}-1$ 個元素）
## queue.c 實作
### 實作 q_new 函數
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* Return NULL if malloc failed */
if (!q)
return NULL;
/* Initialization of fields */
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
1. 如果 ```malloc()``` 執行失敗，則回傳 ```NULL```
2. 初始化 queue 的各個欄位
### 實作 q_insert_head 函數
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
char *value;
/* Return false if q is NULL */
if (!q)
return false;
/* Allocate space for list_ele_t */
newh = malloc(sizeof(list_ele_t));
/* Check if space is allocated */
if (!newh) {
return false;
}
unsigned int value_length = strlen(s);
/* Allocate space for string value */
value = malloc(value_length + 1);
/* Check if space is allocated */
if (!value) {
free(newh);
return false;
}
memset(value, '\0', value_length + 1);
/* Copy input string to allocated space */
strncpy(value, s, value_length);
/* Assign value and change head */
newh->value = value;
newh->next = q->head;
/* If the queue was empty, assign tail pointer to its new head */
if (q->size == 0) {
q->head = q->tail = newh;
} else
q->head = newh;
/* Update the size of the queue */
q->size++;
return true;
}
```
1. 檢查傳入的 ```q``` ，如果爲 ```NULL``` 則回傳 ```false```
2. 分別爲新的 list 元素和 value 獲取空間
3. 分別檢查獲取空間是否失敗，若失敗，則回傳 ```false```
4. 將傳入的 value 複製到新的 value 空間
5. 將新的元素串接至原 queue 的前端
6. 判斷 queue 原先是否爲空:
* 若爲空則將 head 與 tail 設定爲新的 list 元素
* 若不爲空則將 head 指向新的 list 元素
7. 設定 queue 的 head 爲新的 list 元素
8. 修改 queue 的個數
### 實作 q_insert_tail 函數
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
char *value;
/* Return false if q is NULL */
if (!q)
return false;
/* Allocate space for list_ele_t */
newh = malloc(sizeof(list_ele_t));
/* Check if space is allocated */
if (!newh) {
return false;
}
unsigned int value_length = strlen(s);
/* Allocate space for string value */
value = malloc(value_length + 1);
/* Check if space is allocated */
if (!value) {
free(newh);
return false;
}
memset(value, '\0', value_length + 1);
/* Copy input string to allocated space */
strncpy(value, s, value_length);
/* Assign value and change head */
newh->value = value;
newh->next = q->head;
/* If the queue was empty, assign tail pointer to its new head */
if (q->size == 0) {
q->head = q->tail = newh;
} else
q->head = newh;
/* Update the size of the queue */
q->size++;
return true;
}
```
1. 檢查傳入的 ```q``` ，如果爲 ```NULL``` 則回傳 ```false```
2. 分別爲新的 list 元素和 value 獲取空間
3. 分別檢查獲取空間是否失敗，若失敗，則回傳 ```false```
4. 將傳入的 value 複製到新的 value 空間
5. 判斷 queue 原先是否爲空
* 若爲空則將 head 與 tail 設定爲新的 list 元素
* 若不爲空則將新的 list 元素串接在 queue 後端，並將 tail 指向新的 list 元素
6. 設定 queue 的 tail 爲新的 list 元素
7. 修改 queue 的個數
### 實作 q_remove_head 函數
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* Return false if queue is NULL or empty */
if (!q || q->size == 0) {
return false;
}
/* Extract current queue head */
list_ele_t *oldh = q->head;
/* Change queue head to next element */
if (q->size == 1) {
/* If the queue only got 1 element */
q->head = q->tail = NULL;
} else {
q->head = oldh->next;
}
q->size--;
/* Copy removed string to sp if sp exists*/
if (sp) {
strncpy(sp, oldh->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
/* Free old value space and list element space*/
free(oldh->value);
free(oldh);
return true;
}
```
1. 若 q 爲 NULL 或者 queue 個數爲 0 則回傳 ```false```
2. 從原 queue 中取出將移除的元素 ```oldh```
3. 檢查原 queue 大小
* 若原 queue 大小爲 1，則把原 queue 的 head 和 tail 指向 ```NULL```
* 若原 queue 大小不爲 1，則把原 queue 的 head 指向 ```oldh``` 的下一個元素
4. 根據題目要求，若 sp 不爲空，則把原 value 存入 sp 中
5. 將 ```oldh->value``` 的記憶體空間釋放
6. 將 ```oldh``` 本身的記憶體空間釋放
### 實作 q_free 函數
```cpp
void q_free(queue_t *q)
{
/* If queue is NULL, no need to free */
if (!q) {
return;
}
/* Extract first element */
list_ele_t *cur = q->head;
list_ele_t *tmp = NULL;
while (cur) {
tmp = cur;
cur = cur->next;
/* Free value space */
free(tmp->value);
/* Free element structure */
free(tmp);
}
/* Free queue structure */
free(q);
}
```
1. 若傳入的 ```q``` 爲 ```NULL``` ，直接回傳
2. 將每個 element 的 value 以及結構釋放
3. 將 queue 結構釋放
### 實作 q_reverse 函數
```cpp
void q_reverse(queue_t *q)
{
/* q is NULL or empty */
if (!q || q->size == 0) {
return;
}
/* Queue has only 1 element */
if (q->size == 1) {
return;
}
/* Initialize prev, curr and next pointers */
list_ele_t *prev = NULL;
list_ele_t *curr = q->head;
list_ele_t *next = NULL;
/* Reverse the linked list using 3 pointers method */
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
/* Exchange the original head and tail pointers */
list_ele_t *tmp = q->head;
q->head = q->tail;
q->tail = tmp;
return;
}
```
1. 若 queue 爲 ```NULL``` 或空，直接回傳
2. 若 queue 只有 1 個元素，直接回傳
3. 使用三指針方式進行 linked list 反轉
[圖片來源](https://www.geeksforgeeks.org/reverse-a-linked-list/)
4. 交換原本的 ```head``` 和 ```tail```
### 實作 q_sort 函數
由於題目要求 ```q_sort```
#### 嘗試 1 —— Merge Sort (Recursive split and Recursive merge)
參考 [Lisked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 使用 Recursive 的方式進行 split 以及 merge
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
/* Return the other list when one of the list is empty */
if (!l2)
return l1;
if (!l1)
return l2;
/* Concat list in ascending order */
if (strcmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
list_ele_t *merge_sort_list(list_ele_t *head)
{
/*
* Do nothing if head is NULL
* or the list has only one element
*/
if (!head || !head->next)
return head;
/* Use fast and slow pointers to seperate the list into two halves */
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
/* Sort each half of the list */
list_ele_t *l1 = merge_sort_list(head);
list_ele_t *l2 = merge_sort_list(fast);
/* merge sorted lists */
return merge(l1, l2);
}
void q_sort(queue_t *q)
{
/* Return if q is NULL or empty or has only one element */
if (!q || q->size == 0 || q->size == 1)
return;
/* Change the head to sorted list */
q->head = merge_sort_list(q->head);
/* Change the new tail */
list_ele_t *tail = q->head;
while (tail->next) {
tail = tail->next;
}
q->tail = tail;
}
```
執行 ```make test``` 後測試結果，發現 test case 中 **只有第 15 個** 出現 Segmentation Fault，其餘正常
```
...
--- trace-15-perf 0/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
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
...
```
查看 trace 後發現第 15 個 test case 會插入 2000000 個元素後進行排序，推測是使用 Recursive 導致 Stack Overflow 造成 Segmentation Fault
```
# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000
```
使用 ```make valgrind``` ，運用 Valgrind 工具檢查記憶體使用狀況，發現果然是 Stack Overflow
```
...
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==11113== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==11113== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==11113== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==11113== no stack segment
...
```
#### 嘗試 2 —— Merge Sort (Recursive split and Iterative merge)
將 merge 的部分改用 Iterative 方式，減少 stack 的使用量，避免 stack overflow
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
/* Concat list in ascending order iteratively */
list_ele_t *head = NULL;
list_ele_t *cur = NULL;
/* While l1 and l2 both have elements */
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
if (!head) {
head = cur = l1;
} else {
cur->next = l1;
cur = cur->next;
}
l1 = l1->next;
} else {
if (!head) {
head = cur = l2;
} else {
cur->next = l2;
cur = cur->next;
}
l2 = l2->next;
}
}
/* Concat the rest of the list */
if (!l1)
cur->next = l2;
if (!l2)
cur->next = l1;
return head;
}
```
1. 使用 ```head``` 記錄 merge 過後的 linked list 起始位置
2. 使用 ```cur``` 記錄 merge 過程中 linked list 的最後一個 element 位置
3. 在 ```l1``` 和 ```l2``` 都還沒有被使用完時，將 value 比較小的接在 ```cur``` 後
4. 當 ```l1```/```l2``` 其中一個用完時，將剩下的接在 ```cur``` 後
## 變更排序方法爲 natural sort
使用 [natsort](https://github.com/sourcefrog/natsort) 方式實作
### strcmp v.s. natural sort
[C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)，7.21.4 Comparison functions 可以找到 ```strcmp``` 比較的原則：
>The sign of a nonzero value returned by the comparison functions memcmp, strcmp,
and strncmp is determined by the sign of the difference between the values of the first
pair of characters (both interpreted as unsigned char) that differ in the objects being
compared.
也就是說，```strcmp``` 比較的原則是將兩個 string 內容以 ```unsigned char``` 比對，當碰到不一樣的 ```unsigned char``` 時，就返回 ```unsigned char``` 相差的值
e.g.
```cpp
strcmp("a", "b");
```
返回值爲 -1，因爲 a 的 ASCII code - b 的 ASCII code 結果爲 -1
以爲這樣的機制，所以考慮以下的三個子串 ```rfc1.txt```、```rfc2086.txt```、```rfc822.txt```
如果以 ```strcmp``` 作爲排序依據，則結果爲：
```rfc1.txt``` < ```rfc2086.txt``` < ```rfc822.txt```
但是通常我們希望 **數字部分能按照大小進行排列**，所以使用 natural sort
natural sort 的機制是：
> Strings are sorted as usual, except that decimal integer substrings are compared on their numeric value.
所以考慮上述的子串，使用 natural sort 結果爲：
```rfc1.txt``` < ```rfc822.txt``` < ```rfc2086.txt```
### 將 natural sort 整合
1. 從 [natsort](https://github.com/sourcefrog/natsort) 中下載 ```strnatcmp.h``` 和 ```strnatcmp.c``` 並加入專案目錄
2. 修改 Makefile，使 ```strnatcmp.c``` 被編譯
```
--- a/Makefile
+++ b/Makefile
@@ -25,7 +25,7 @@ $(GIT_HOOKS):
@scripts/install-git-hooks
@echo
-OBJS := qtest.o report.o console.o harness.o queue.o \
+OBJS := qtest.o report.o console.o harness.o queue.o strnatcmp.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o
deps := $(OBJS:%.o=.%.o.d)
```
3. 在 ```q_sort()``` 函數中，變更原 ```strcmp``` 爲 ```strnatcmp```
Sign in with Wallet
Connect another wallet