# 2020q1 Homework1 (lab0)
contributed by <`harunanase`>
## 開發環境
1. OS: Arch Linux 5.6.11-arch1-1
2. compiler version: gcc (Arch Linux 9.3.0-1) 9.3.0
3. debugger: GNU gdb (GDB) 9.1
## 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
我的 [GitHub Page](https://github.com/harunanase/lab0-c)
## `queue.[ch]` 的修改
實作預先定義好，操作 queue 的 functions，以下逐項針對各個 function 的修改以及相關內容做說明
### 新增 `struct queue_t` member
新增以下 member
```c
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* Points to the tail of queue */
int size; /* size of the queue */
} queue_t;
```
原本只有 `head`，新增了 `tail` 和 `size`，分別用來「指到 queue 的尾端」以及「紀錄 queue 的 size」。
### `q_new()` 的實作
此函式的目的為初始化一個 queue。
記得處理 `malloc()` failed 的情況以及 `head`、`tail` 、`size` 的初始化即可。
```c=
queue_t *q_new()
{
queue_t *q;
if (!(q = malloc(sizeof(queue_t)))) {
return NULL;
}
q->head = q->tail = NULL;
q->size = 0;
return q;
}
```
### `q_insert_head()` 的實作
大致上的思路為：
1. 檢查 queue 狀態後，分配 element 並檢查是否分配成功
2. 分配 element 的 member - `value`，同樣檢查是否分配成功
- 需要注意若分配失敗，要記得釋放前面所分配給 `newh` 的記憶體
- 分配的 size 為字串長度加上 1，因為要包含 ``'\0'``，在 [CMU 作業的說明文件](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)也有提到：
> String operations: Functions strlen, strcpy, and strncpy. (Beware of the behavior of strncpy when truncating strings!)
3. copy 要插入 queue 的字串到 `newh->value`
- 同上述，記得 size 要 +1，給 `'\0'` 的。
4. 把 element 插進 queue 的最前面，並同時紀錄 queue size
- 注意邊緣情況，當 queue 是 **empty** 時，要記得更新 `q->tail` 的值。
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* if the queue is NULL OR malloc() failed, return false */
if (q_status(q) == NOTHING || !(newh = malloc(sizeof(list_ele_t)))) {
return false;
}
if (!(newh->value = malloc(strlen(s) + 1))) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
if (q_status(q) == EMPTY) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
- 上述的實作有用到我自己定義的 function - `q_status()`，用來檢查 queue 的狀態，如老師以及 [CMU 作業說明文件](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 裡有提到，要特別注意 queue 的兩種狀態：
> - NULL 佇列：是指標值為 NULL;
> - 「空」(empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL;
```
#define NOTHING 0 // NULL 佇列
#define EMPTY 1 // EMPTY 佇列
#define OTHERS 2 // 正常，含有元素的佇列
```
```c=
int q_status(const queue_t *q)
{
if (!q) {
return NOTHING;
} else {
return (!q->head) ? EMPTY : OTHERS;
}
}
```
透過此函式讓我們可以快速的取得 queue 的狀態。
### `q_insert_tail()` 的實作
須在 $O(1)$ 內完成，這時前面所新增在 `queue_t` 的 member - `tail` 就可以發揮功效了。
思路上和 `q_insert_head()` 類似，在此不再贅述，
需要注意邊緣情況，當 queue 在 **EMPTY** 狀態時，注意要如何更新串連。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
/* if the queue is NULL OR malloc() failed, return false */
if (q_status(q) == NOTHING || !(newt = malloc(sizeof(list_ele_t)))) {
return false;
}
if (!(newt->value = malloc(strlen(s) + 1))) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
if (q_status(q) == EMPTY) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
newt->next = NULL;
q->size++;
return true;
}
```
### `q_remove_head()` 的實作
思路：
1. 先確認 queue 的狀態
2. 將要移出的 element 的 value 寫入 `sp`
- 先確認 `sp` 是否為 `NULL`，再開始 copy
- 一樣要注意 `'\0'` 的問題，需要自己手動給值
3. 移動指標，將 element 移出 queue
- 注意邊緣狀態，當移出最後一個 element 時，記得要更新 `q->tail`
4. 記得釋放掉 element 裡分配的記憶體與 element 本身
- 即 `beRemoved->value` 和 `beRemoved`
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q_status(q) == NOTHING || q_status(q) == EMPTY) {
return false;
}
list_ele_t *beRemoved = q->head;
if (sp) {
strncpy(sp, beRemoved->value, bufsize);
/* strncpy truncate problem, need to assign '\0' manually */
sp[bufsize - 1] = '\0';
}
q->head = q->head->next;
if (q_status(q) == EMPTY) {
q->tail = NULL;
}
free(beRemoved->value);
free(beRemoved);
q->size--;
return true;
}
```
### `q_free()` 的實作
檢查 queue 狀態後，呼叫 `q_remove_head()` 來依序釋放掉 element，最後再記得釋放 queue 本身即可。
```c=
void q_free(queue_t *q)
{
if (q_status(q) == NOTHING) {
return;
}
while (q_remove_head(q, NULL, 0)) {
;
}
free(q);
}
```
### `q_reverse()` 的實作
思路： 依序從頭到尾，第一個 element 移到最後面，再把第二個**移到第一個的前面**，以此類推做下去即可。
`q->head` 用作當前要移動的 element，`next` 和 `prev` 分別指到後一個與前一個 element
額外使用指標 `newt` 來指到 reverse 完成後，新的 `q->tail`
```c=
void q_reverse(queue_t *q)
{
if (q_status(q) == NOTHING || q_status(q) == EMPTY) {
return;
}
list_ele_t *newt = q->head;
list_ele_t *next = NULL;
list_ele_t *prev = NULL;
while (q->head) {
next = q->head->next;
q->head->next = prev;
/* move to next element */
prev = q->head;
q->head = next;
}
q->head = prev;
q->tail = newt;
}
```
### `q_size()` 的實作
多虧前面在 `queue_t` 結構裡新增的 member - `size`，我們可以在檢查完 queue 的狀態後直接 return 該值。
且其複雜度為 $O(1)$，比用 loop 整個 queue 得出來的 size，$O(n)$ 要好得多
```c=
int q_size(queue_t *q)
{
if (q_status(q) == NOTHING || q_status(q) == EMPTY) {
return 0;
}
return q->size;
}
```
### `q_sort()` 的實作
查看 `trace/trace-15-perf.cmd` 可以知道此程式會受到 $1,000,000$ 以上的資料做測試，且也有時間限制的程式在做檢測（測試程式的相關討論可見本文後半部），一般 sorting 複雜度為 $O(n^2)$ 的演算法勢必不可行。
這邊將採用複雜度為 $O(n\log{}n)$ 的 [merge sort](https://en.wikipedia.org/wiki/Merge_sort)。
以下將 merge sort 拆成一個個小部分來探討，方便開發與可讀性。
實作方法參考了老師在 [lab0說明文件](https://hackmd.io/JSFDnHn0Rpe0V7d-AqLAXA?view#追蹤記憶體配置和釋放的狀況) 裡所給的 [參考實作](https://npes87184.github.io/2015-09-12-linkedListSort/)
#### `compare()` - 比較函式
- `compare()`，比較大小的函式。由於是比較字串的長度與字母順序，直接使用 `strcmp()` 即可
```c=
int compare(const list_ele_t *a, const list_ele_t *b)
{
return strcmp(a->value, b->value);
}
```
#### `merge_sort()` - [merge sort](https://en.wikipedia.org/wiki/Merge_sort) 的主要邏輯函式
- 主要概念是切割 list，分別拿去做排序，之後再合併 (merge) 回去。
- 要注意檢查 `head` 以及 `head->next` 是否為空指標，此為 recursion 的終止條件。
- 切割 list 的方法是利用兩個移動速度不同的指標，最後 `fast` 指標會指到 list 的中間，我們會得到兩個 list。
1. `head` 指標所開始的 list，尾端為 `slow` 指標。
2. `fast` 指標所開始的 list (即 `slow->next`)，尾端為切割前，list 中最後一個元素。
```c=
list_ele_t *merge_sort(list_ele_t *head)
{
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;
list_ele_t *l1 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
return merge(l1, l2);
}
```
#### `merge()` - 合併兩個 list 的函式
分別取出兩個 list 的元素來比較大小、排列，並且合併成一個 list。
- 上面的 `merge_sort()`，這裡 `merge()` 的實作都是參考 [這個](https://npes87184.github.io/2015-09-12-linkedListSort)，但這裡在 `merge()` 做了一點小修改。
1. [原本的 `merge()` 實作](https://npes87184.github.io/2015-09-12-linkedListSort/) 有兩種版本，遞迴版和迭代版，這裡採用迭代版，避免大量測資下會 stack overflow 的問題。
2. 迭代版的實作有動態配置一個 pseudo node，來方便更新 head，但此作業在 sorting 中是不允許調用相關動態分配記憶體的函式的，可見 `lab0-c/qtest.c` 的 Line 551 ~ 555
```c=551
set_noallocate_mode(true);
if (exception_setup(true))
q_sort(q);
exception_cancel();
set_noallocate_mode(false);
```
3. 因此，在這邊我們使用了 pointer to pointer，指到 `head` 的地址。
- `head` 指標所指到的就是我們最後要 return 回去，合併完成的 list。
- 使用 `indirect` 來走訪 `l1`、`l2`，避免要用另一個指標去紀錄合併完成的 list 的開頭在哪。
- 此修改參考了老師的 [linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list?type=view)。
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *head = NULL;
list_ele_t **indirect = &head; // indirect points to the ADDRESS of head
while (l1 && l2) {
if (compare(l1, l2) < 0) {
*indirect = l1;
l1 = l1->next;
} else {
*indirect = l2;
l2 = l2->next;
}
indirect = &(*indirect)->next;
}
*indirect = (l1) ? l1 : l2;
return head;
}
```
## [natural sort](https://github.com/sourcefrog/natsort)
作業要求:
> 修改排序所用的比較函式，變更為 natural sort。
> 在 “simulation” 也該做對應的修改，得以反映出 natural sort 的使用。
### 比較函式變更為 natural sort
從 [natrual sort](https://github.com/sourcefrog/natsort)，clone 下來 `strnatcmp.c`，`strnatcmp.h` 兩個檔案，加入進我們的專案裡面。
1. `queue.c` 的修改
```c
#include "strnatcmp.h"
int compare(const list_ele_t *a, const list_ele_t *b)
{
// Origin comparision
// return strcmp(a->value, b->value);
// New one, using natural sort
return strnatcmp(a->value, b->value);
}
```
2. `Makefile` 的修改
```diff
diff --git a/Makefile b/Makefile
index 172a41f..f879cf0 100644
--- a/Makefile
+++ b/Makefile
@@ -26,7 +26,8 @@ $(GIT_HOOKS):
@echo
OBJS := qtest.o report.o console.o harness.o queue.o \
- random.o dudect/constant.o dudect/fixture.o dudect/ttest.o
+ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
+ strnatcmp.o
deps := $(OBJS:%.o=.%.o.d)
qtest: $(OBJS)
```
觀察 `Makefile`，可以發現我們在編譯時加入了 `-Werror` 選項，此選項會將所有的 warning 視為 error。
```Makefile
CC = gcc
CFLAGS = -O1 -g -Wall -Werror -Idudect -I.
```
由於我們只使用到 `natural sort` 模組裡的部分函式而已，有些並沒有使用到，這樣就會觸發到 `defined but unused` 的警告，我們只要將沒有用到的部分移除即可。
Sign in with Wallet
Connect another wallet