---
# System prepended metadata

title: 2020q1 Homework1 (lab0)

---

# 2020q1 Homework1 (lab0)
contributed by <`harunanase`>



## 開發環境
1. OS: Arch Linux 5.6.11-arch1-1![](https://i.imgur.com/RiFvaqw.png)
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` 的警告，我們只要將沒有用到的部分移除即可。